For education and fun I wrote a small untyped non-strict lambda
calculus evaluator in python. One of the goals was to keep it
fairly small and simple, and to do most of the work in the implemented
scripting language itself. For that reason, I added macros to allow
things like "let" and "letrec" to be defined as syntactic sugar
easily outside of the evaluation engine itself.
The result is 244 lines of python, a small prelude that implements
tuples, lists and the state monad, and some small example scripts.
The prelude and scripts are heavily influenced by Haskell, the main
differences being a much simpler syntax, lack of pattern matching
and lack of a type system. Data structures aren't supported but
are implemented fairly easily using lambda expressions as described
in
http://www.cs.nott.ac.uk/~nhn/TFP2006/Papers/03-JansenKoopmanPlasmeijer-EfficientInterpretation.pdf
This is all available at
http://www.thenewsh.com/%7Enewsham/lambda/
as extracted package and .tgz. The README file has documentation
including small examples. Accompanying scripts provide more
complete examples, such as:
[WITHLIST
[LET from2 (iter (add 1) 2)
[LET primes (nubBy (\x \y (eq (mod y x) 0)) from2)
(traceList Val (take 10 primes))
]]]
which calculates the first 10 primes.
Exercise to the reader: I bet the evaluator could all be written much more
compactly in Haskell.
Tim Newsham
http://www.thenewsh.com/~newsham/
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
