Last Updated: January 04, 2021
·
1.433K
· memowe

Implementing your own Lisp

Implementing your own Lisp dialect is a cool exercise! And it's fun to see many deep recursion warnings in the "run-a-lisp-that-is-written-in-lisp-that-runs-itself" test.

Some examples from the PerLisp shell

(bind to-ten '(1 2 3 4 5 6 7 8 9 10))
(1 2 3 4 5 6 7 8 9 10)
(define (add-1 x) (+ x 1))
Function: (x) -> (+ x 1)
(map add-1 to-ten)
(2 3 4 5 6 7 8 9 10 11)

(filter (lambda (n) (= (% n 2) 0)) to-ten)
(2 4 6 8 10)

(define (sum l) (reduce + l 0))
Function: (l) -> (reduce + l 0)
(sum '(1 -1))
0
(sum to-ten)
55

(define (product l) (reduce * l 1))
Function: (l) -> (reduce * l 1)
(product '(6 7))
42
(product to-ten)
3628800

Code snippets

The eval method of my PerLisp class. I think it's pretty straightforward: it transforms an input string to a stream of tokens which will be parsed into a list of expressions. All expressions have to implement an eval method that could depend on the surrounding context. The method's return value is the resulting list of values or (in scalar context) the first value:

sub eval {
    my ($self, $string) = @_;

    # lex
    my $token_stream = $self->lexer->lex($string);

    # parse
    my @exprs = $self->parser->parse($token_stream);

    # eval
    my @values = map { $_->eval($self->context) } @exprs;

    # return
    return wantarray ? @values : shift @values;
}

A symbol expression for example looks itself up in the given context:

sub eval {
    my ($self, $context) = @_;
    return $context->get($self->name);
}