Proof-of-concept Lisp/Scheme interpreter
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
README
console1.py
dollop.py
test_dollop.py

README

# README
# Crude notes about how this interpreter works.

This interpreter uses a call stack that works as follows.

Let's say we evaluate an expression E. If it's atomic, then we evaluate it and
return its value. If it's composite (i.e. a list), then we evaluate all its
elements, then treat it as a function call.

Subexpressions that need evaluated go up the stack.  E.g.

    (+ 1 2)

First, we evaluate +. We put a placeholder in its place ($$) and push the
subexpression + on the stack:

    ($$ 1 2) +

Now we evaluate that subexpression. + is a symbol, which is looked up as a
name, which refers to the built-in function <+>. We put that back and get the
next element ready for evaluation:

    (<lambda:+> $$ 2) 1

    (<lambda:+> 1 $$) 2

    (<lambda:+> 1 2)

Now we are done, and the whole expression can be evaluated. In this case, it's
a call to a built-in function. The result is 3.

    => 3

If we apply a user-defined function, things look different. Let's say we have
this function:

    (define twice (lambda (x) (* x 2)))

First steps look the same:

    (twice 3)
    ($$ 3) twice
    (<lambda:twice> $$) 3
    (<lambda:twice> 3)      ;; ready to apply

But when we apply the lambda, we do the following:

1. We create a new environment with as parent, the environment the lambda was
defined in.
2. In that new environment, we bind parameters to the values passed. (In this
case, x = 3)
3. We substitute the function call with the lambda body, associated with this
new environment.  (In other words, the lambda body (* x 2) will be evaluated
in an environment that has x=3.)

So:

    (* x 2)
    ($$ x 2) *
    (<lambda:*> $$ 2) x
    (<lambda:*> 3 $$) 2
    (<lambda:*> 3 2)      ;; ready to apply

Here's another function application... but this one is built-in, so there are
no more substitutions to be done:

    => 6

Special forms have different evaluation rules. Internally, the sf_next()
function determines which elements have to be evaluated, and sf_apply()
handles the actual application (e.g. define a variable, create a Lambda
instance, etc).

sf_apply() is also the place where tail recursion is handled. Currently only
for BEGIN and IF; later, other special forms may follow. According to R*RS,
the last expression inside a lambda body is also in tail position, but in our
implementation lambda bodies can only contain one expression, so it doesn't
apply here. (For multiple expressions use BEGIN, which *does* use TCO.)

#
# CONTINUATIONS

Work like this:

(+ 1 (call/cc (lambda (k) (+ 2 (k 3)))))
($$ 1 (call/cc ...)) +
(<+> $$ (call/cc ...)) 1
(<+> 1 $$) (call/cc (lambda (k) (+ 2 (k 3))))
(<+> 1 $$) ($$ (lambda (k) (+ 2 (k 3)))) call/cc
(<+> 1 $$) (<call/cc> $$) (lambda (k) (+ 2 (k 3)))
(<+> 1 $$) (<call/cc> $$) <lambda>
(<+> 1 $$) (<call/cc> <lambda>)

At this point, we execute (<call/cc> <lambda>)...

Now what? 
- We create a continuation (i.e. a snapshot of the current stack)
- We create a function that takes an argument x, and that, when called, restores
  the call stack to the snapshot stored in the continuation, and then returns x
- We replace the (<call/cc> <lambda>) with the lambda body, associated
  with an environment which has the lambda's variable bound to said function

(<+> 1 $$) (+ 2 (k 3))    with k = {continuation}
(<+> 1 $$) ($$ 2 (k 3)) +
(<+> 1 $$) (<+> $$ (k 3)) 2
(<+> 1 $$) (<+> 2 $$) (k 3)
(<+> 1 $$) (<+> 2 $$) ($$ 3) k
(<+> 1 $$) (<+> 2 $$) ({cont} $$) 3
(<+> 1 $$) (<+> 2 $$) ({cont} 3)

At this point, we're ready to call (k 3). As said, it restores the stack to
the way it was, then collapses the value 3. So:

(<+> 1 $$) 3
(<+> 1 3)
=> 4

The other, partially evaluated expressions, DO NOT MATTER as soon as we call
(k 3).