# 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).