With this change, the repl/evaluator now supports binding names to
values using a def form. We also endeavor to lookup the values of bound
names when encountered and carry context mutations across repl states.
This slightly tweaks our approach to environments. Additionally, it
introduces an execution context, which keeps track of different scopes
(which each have an environment) throughout the course of a program's
execution.
We define a basic interface for managing definitions in the programming
environment. This will permit users defining their own functions and
other forms.
`letrec` bindings may refer to themselves in their bodies. We achieve
this by replacing all binding values in a letrec form with an
application of the Y combinator to express the recursion. Since we don't
evaluate eagerly, it's important to note that for simple values the form
will yield an anonymous function awaiting subsequent evaluation.
This new form permits definitions such as:
(letrec [f (fn [n] (if (= n 0) 1 (* n (f (- n 1)))))] (f 3))
=> 6
I've also added a special pattern syntax for this form.
Let transformations are not dependent on evaluation. Since they are part
of the enriched lambda calculus, it makes sense to define them in
Lambda.
This commit also breaks out a number of utility transformations on
s-expressions into the Util module, which makes our definitions of let
transformations more concise.
In addition to re-implementing the Y combinator as a primitive (and
eliminating another special case in the evaluator), this commit adds a
function for making Unary primitive functions, which need to be handled
slightly differently than binary primitives (namely, they do not return
a partial function on a unary argument).
Reimplementing alpha as a primitive allows us to remove a special case
from the Evaluator, simplifying it.
In the process of implementing alpha as a primitive, I caught a bug in
the implementation of partial functions for primitives, which is also
fixed here. We'll also need to implement separate primitive creation
functions for unary and binary primitives after this change.
This commit makes our implementation of primitives much dryer by
leveraging a lambda expression. Primitives are now binary function as
well, and typically expect two atoms as arguments (expecting unary
primitives, which will expect Nil). This simplifies the passing of
arguments to primitives, since we decompose expressions beforehand.
This commit adds an evalPrim function to clean up our handling of the
evaluation of primitives. Additionally, it makes various improvements to
the handling of a few forms.
This evaluator, equipped with Y and equality, can compute the factorial
of a number:
(let [f (fn [fac n] (if (= n 0) 1 (* n (fac (- n 1)))))] ((Y f) 3))
=> 6
Let bindings are only valid if they contain an even number of forms:
[x 1 y 2] (ok) [x] (not ok) [x 1 y] (not ok)
This commit fixes a small bug whereby valid forms were sometimes
misidentified as erroneous.
This commit implements basic equality on atoms as a primitive of the
language. Two atoms are equivalent precisely when their internal
representations are equivalent.
Sometimes, it can be a bit difficult to debug evaluated expressions when
they're printed in the normal fashion. This commit adds a `showDebug`
function that prints expressions tagged with corresponding internal data
structures, for example,
(a b nil)
becomes:
(<Expression> <atom>a (<Expression> <atom>b <Nil>))
under `showDebug`.
The Y combinator allows us to express recursion in the lambda calculus
without relying on recursion itself. This isn't an appropriate place to
delve into the complete background, but the gist of the combinator is
that it applies a function to itself. Internally, this may be expressed
as a simple reduction rule:
Y H -> H (Y H)
Which is precisely the approach we take in this implementation. We use Y
to support direct recursion in the rose language.
Alpha conversion renames bound terms in lambda abstractions to prevent
collisions between variables in nested abstraction contexts.
Alpha conversion is a prerequisite to supporting recursion in the lambda
calculus, otherwise the Y combinator can replace bindings incorrectly on
application and lead to unintentional infinite loops.
This initial implementation of alpha is naive and can probably be
improved. Aside from the ugly code repetition, there are quite a few
list and data s-expression traversals here that can likely be fused
using a fold.
Let expressions allow users to define local bindings. Let expressions in
Rose follow the classic lisp form:
(let (bindings) body)
Where bindings must be an even number of names and values, and body is
an evaluable function body. Let expressions are transformed into an
anonymous function application that applies the values in the `bindings`
form to the variables in `bindings`. Since let expressions may occur in
large contexts, such as function bodies, they can cause name
collisions/shadowing. For now, we don't perform any renaming or
collision detection.
Originally, the evaluator was defined by pattern matching on top level
arguments to a call to `evaluate`. However, the only discriminant in
`evaluate` at the moment is the form being evaluated, and the top-level
patten matching code was a bit difficult to read.
This commit refactors evaluate into a series of mutually recursive
functions, one specialized to each form of input. The `go` function
handles matching on forms and dispatching to the appropriate function.
Technically, if is implementable in pure lambda calculus equipped with
boolean reductions. For convenience, however, I've defined if as a
special case in the evaluator.
We don't want to accept every type of s-expression it's possible to
form. Ideally, all s-expressions terminate in either:
- Nil
- An Expression that terminates in Nil
We want to reject expressions such as:
((a b ()) c)
since this expression ends in an atom `c` and not `Nil`.
Form.idr now checks whether or not expressions it receives are
well-formed, returning an error if they aren't.
As of this inaugural commit, Rose is a dumb repl that supports some of
the lambda calculus and three basic arithmetic operations.
Of course, we also have a lexer, parser, and the underlying data
structures/types we need to represent s-expressions and evaluate lisp
forms.
Onward march from here!
fool
scottolsen