alisp is an implementation of Lisp in C. The implementation contains a mark-and-sweep garbage collector and function continuation.
Execute the following commands in order to compile and run the unit tests.
$ make check gen-cmake
$ make check
Requires libedit.
On Ubuntu:
$ sudo apt-get install libedit-dev
$ bind/alisp
alisp is a Lisp interpreter. It reads on expression at a time from the standard input, evaluates it, and prints the return value of the expression. Here is an exmaple of a valid input:
> (+ 1 2)
The above expression prints "3".
alisp supports integer literals, (), t, nil, symbols, strings, and lists.
- Integer literals are positive or negative integers.
(), ornil, are the only false values. They also represent the empty list.tis a predefined variable evaluated to itself. It is the preferred way to represent a true value.- Symbols are objects with unique name. They are used to represent identifiers.
- String literals are surrounded by
"". - List literals are cons cells. They are either regular lists whose last element's cdr is
()or a dotted list ending with any non-()value. Dotted lists are written as(a . ).
cons takes two arguments and creates a new cons cell where the first argument is the car and the second the cdr.
> cons(1 2)
car and cdr are accessors for con cells.
+ returns the sum of the arguments
> (+ 1)
> (+ 1 2)
> (+ 1 2 3)
- returns negates the argument if there is only one. Else, it substracts each arguments from the first one
>(- 2)
>(- -2)
> (- 5 2 7)
* returns the product of two arguments
> (* 3 4)
/ returns the quotient of two arguments
> (/ 4 2)
= returns t if the two arguments are the same integer and () if they are different
> (= 2 1)
< returns t if the first argument is smaller than the second
> (< 2 1)
(if cond then else). It evaluates cond, and if it is true, then is evaluated. Otherwise, else is evaluated.
> (if (= 2 3) 4 5)
eq takes two arguments and returns t if the objects are the same.
> (eq NIL 2)
User defined variables and functions are supported by alisp. Functions can defined using lamda.
(lambda (args ...) expr ...) returns a function object which can be assign to a variable using define.
> (define square (lambda (x) (* x x)))
The lambda can also be omitted in the following way:
> (define (square x) (* x x))
The two expressions will be evaluated to the same result.
alisp uses continuations and tail recursions to be able to use recursion as without being limited by the stack of the interpreter. To do so, evaluated arguments and pending evaluations are kept in a stack that is manipulated directly instead of using the machine code stack.
Tail calls do not require a new stack frame to the call stack, so they can recurse as many levels as necessary without increasing the stack depth.
alisp supports quotes, or ', which can be used to manipulate expressions without evaluating them.
> '((lambda (x) (- x 2)) 7)
A mark-and-sweep algorithm is used to collect memory. Since all the data is allocated through the cons, it is possible to keep track of every allocation by tracking the cons atoms in a linked list.
Every 100'000 evaluations, the garbage collector goes through the tree of pairs, and mark them as "in used". It then traverses the linked list of allocations and free any atom that is not marked. The marks are then cleared, and the application can continue running.
alisp as a small library with some useful functions.
> (not t)
> (or () t)
> (and t ())
> (list 1 2 3)
> (len list 1 2 3)
> (first (list 2 3 1))
> (last (list 2 3 1))
> (init (list 2 3 1))
> (tail (list 1 2 3))
> (reverse (list 1 2 3))
> (foldl + 2 (list 10 20 30))
> (foldr + 2 (list 10 20 30))
> (map + '(1 2 3) '(4 5 6))
> (abs -2)
- Add missing unit tests for expression.c
- Add integration tests for gc.c
- Add missing unit tests for parser.c
- Add missing unit tests for expression.c
- Add missing unit tests for builtin_apply
- Add missing unit tests for apply
- Add missing unit tests for builtin_eq
- Assert type in add_symbol_to_table + test
- Assert atom is pair in car/cdr + test
- Add useful error messages through macros
- Add strings manipulation
- Add double
- Be able to manipulate double and long
- Add booleans?
- Implement better gc algorithm
- Add more functions to std
- Add load from file builtin import files
- User defined types
- quasiquotation
- List literal ? (use [] to give literal notation for lists of evaluated values lists)
- OS interaction
- Pool allocation?
- Lexical scoping?
- Static typing ?
- Use hashtable for environment?
- Exit function for stopping the prompt and exit cleanly
- Add language features documentation
- Quasiquotes
Here are some references that helped me implement alisp