rcdomigan / atl

The ATL language

atl

I started re-writing in Rust, as you do [https://github.com/rcdomigan/atl-rs]

One day, I hope this will be A Typed Lisp; the ATL language. For now it's a barely functioning and feature incomplete VM and byte-code complier, along with the detritus of a partially working interpreter which they are replacing.

The code is not now suitable for any purpose and is a a mess. I'm bringing it into github so I can start at least using an issues tracker.

atl's Issues

Type infrerence for multi arg application

The W lamba inference rule supports multiple arguments, the application rule needs to be extended

Resizeable DynamicVector

The DynamicVector allocation type needs to be resizable. It could also use a better name.

I am using pointers into the Ast arrays, which are allocated on DynamicVectors, which is something I need to keep working since one Ast can point into another.

Get rid of Slice

Slice is annoying to deal with. Right now I don't think I need it, but at very least I think it should be allocated inline to an Ast backer, something like:

 ____________________________________________________
| Tag         | pointer to || Tag       | pointer to |
| slice-begin |    begin|  || slice-end |  end |     |
 -----------------------|----------------------|-----
                         ->...                 |
                                                ->...

Declare function types

I would like to be able to annotate the type of functions. I need to:

1. Unit-test and debug annotating an expression in the application position.
2. Unit-test and debug the 'Type' type
3. Unit-test and debug the function type constructor '->'

This is a precursor to variable arity function signatures #6, and related to improving the type reporting of wrapped C++ functions #29

Code sections

I need to divide definitions from runnable code so the VM doesn't do the wrong thing when it gets the output of an incremental compilation

Variable arity type signature

I would like to at least support functions taking a variable number of arguments of the same type.

I may need variable arity types working for issue #5 to work.

generate better type signatures from C++ functions

make sure the type signatures that work with the type inference implementation

Get encode.hpp working with compile.hpp

I need to get encode working so primitives setup before ATL starts are resolved when it's compiling to byte-code.

Unit test primitive macros

There's a stub file now, I should add some actual tests.
See also #3

recursive function type inference

define a 'fix' operator in gamma

Improve make_ast

I could automatically 'lift' integral and string arguments to make_ast::make.

I also think a better name for make_ast::make is make_ast::ast

An algebraic data type

Something like haskell data, and be able to unpack it with 'match'

Macros

ATL programs which modify an ATL AST

Raw function pointers

I'm calling wrapped std::functions from my VM. Dispatching function pointers directly where possible is probably a good optimization.

Unpack Ast in lambda formals

I would like general pattern matching for parameters, but handling Ast as a special case is enough to start writing some native functions.

Compiler should return Pointer type where appropriate

A pointer to an Any is supposed to be the Pointer type. Ran into this trying to get the 'nth' element function working.

Unit tests for the VM

I need to be reasonably sure the VM works as I expect before I can establish byte code spit out by my compiler is any good.

Allow multiple Compile instances

I'm getting segfaults if I make more than one instance of my Compile type. Each one should be independent, so this is something I should look into (problem with the primitives being initialized multiple times?).

Better primitive macro API

The PrimitiveMacro interface should be something like (Evaluator, Ast) -> ResultType

Right now it uses the CxxFunctor interface; it takes begin/end pointers into the PCode stack and puts its result-type into begin[0].

Definitions redux

Definitions need to store their value at run-time. My current implementation basically makes a function for each definition and calls that function each time the value is accessed.

I'm running into problems (efficiency issues aside) since a lone definition coming to the VM from the compiler looks like a procedure with no enclosing frame, which means my multi-expression tests have to handle expressions differently at the C++ (and I haven't tried using the REPL for a while). There are other ways to solve that problem, but I think having a transient procedure section and using define to store a value in the environment when it runs would be best.

Closures

There are a couple ways I could approach this. It seems like none of them would be great from a performance perspective, but maybe it doesn't matter.

1. I could pass an arg(-1) to each procedure which points to an on-heap struct. Populating the struct by copying current closure values should be adequate if I'm barring mutation.
2. I could copy any returned procedure and put any values from the outer scope inline.
3. I could pass in closure values as arguments on the stack.
4. I could use some or all of the above according to some compiler heuristic.

Dynamically sized programs

Right now I can have up to 100 instructions in an ATL program. That is not going to work for much longer.

Garbage collection

Enable the GC and get it working.

It may be easier to test if I can construct the algebraic data-types #9

New PrimitiveMacro interface

I'm starting to make PrimitiveMacros which compile something which should be applied. The current implementation works if the macro produces an argument to something else, but it doesn't have a way to pass the function address out to the compiler.

The PrimitiveMacros could return a tuple<type_tag, fn_address>, or take and allocator and Ast argument and return an Ast to be evaluated in place of the macro. The former would be more tightly coupled to the compiler implementation, which is probably a bad thing in the long run.

A Maybe monad

Maybe is about the simplest Monad in Haskell.

A preliminary version can probably be done with algebraic types #9 and macros #11. For general macro use I'll need type classes #17 or some other generic function mechanism.

Remove boost::mpl where there is a good C++11 alternative

It looks like the C++11 stdlib will be adequate for many of my purposes.

• I should be able to replace TypesVec with a wrapped argument pack.
• Dig around a bit and see if I can replace mpl::map

Fix type deduction tests

The simple type deduction tests should all pass and be included in the main test runner.

Define 'make' and 'amake' in terms of AllocatorBase

make and amake are templates, if they were functions rather than methods they could work with Arena in addition to GC.

C++ Quote should return a Pointer

When compiling Quote the 'quoted' expression needs to retain its type tag. I think the simplest way to do that is to return a Pointer to the quoted type and have the accepting function (like nth or eval) take a Pointer argument.

I'm currently planning to overload the ':' type operator to check the tag of a pointed type at run-time and push its value to the stack, in addition to asserting the type of its argument at compile time.

Funtion table for byte code

I'd like to store a map of function names to locations. Initially this is so I can annotate my byte-code during debugging, but it could also be used for simple 'linking'.

Ast RAII

I can build an Ast on a DynamicVector by keeping a pointer to where the Ast is allocated and setting it's end point when I've added all its contained data. It would be nice to have an AstRAII which which sets its end-point when it goes out of scope.

Return procedure from 'eval'

When an eval form finishes its byte-code is discarded and an atom is all that's returned. That works for some things but not for functions.

move semantics for the 'assembler'

The 'assembler' wraps code so it can be appended to. While the assembler is wrapping the code, the code shouldn't be run (as it's missing it's 'finish' instruction). I should use std::move to take the Code in and out of the assembler to prevent mistakes

Quasi-quote and assosiated forms

Macros would be easier to make with the quasi-quote/unquote/unquote-splice forms.

Fix types reported to compile by wrapped C++ functions

The current implementation types a pointer to a type the same as the type. That's working for now, but seems like it's asking for trouble.

Resizeable VM stack

I should at check that the "program counter" is in bounds of VM's stack. It may be worth making the stack re-sizeable..

Byte code

The little VM I've got stores every instruction in a pointer sized int. I could switch to chars and read them back 8 at a time for the 64bit pointers to save space.

Use abstract types in the compiler

When the PCode compiler encounters an 'Undefined' symbol, it should check and update the associated abstract-type object. I should at least issue type exceptions if there is an obvious problem.

Performance wise, I don't currently know how much space to reserve for the Undefined Value, so I put down a procedure call and append a thunk to the end of the PCode once I know what the value is.

Type classes

I'd like to start experimenting with a monad interface, which means multiple classes with return and bind defined for them.

I'll need struct support first so this probably depends on at least algebraic data types #9

C++ fixed sized Ast builder

I'd like to conveniently make nested Asts for primitive macros and for testing. For dynamically sized Asts I think the push-value/push-nested approach works OK, but a variadic function would be more convenient for generating Asts of a known size.

Break the implementation out of my #11/Macro branch

Wrapped Ast type

I made the 'Ast' container so a continuous array could contain nested data. To avoid copying, I want to be able to embed a pointer in one Ast to another Ast.

Ast location as collection beginning

I could save two uintptr_t per Ast if I get rid of the AstData type and use just the Ast as the collection beginning. This would mean that Asts could not be passed by value (since you'd loose the location of the collection), which is a bit of a pain with how things are written now (particularly the compiler).

I'm going to file a ticket and move on after a night working on this.