Hi,
After reading John Tromp's paper [1] (also see De Bruijn Index [2]) I
got very interested in Binary Lambda Calculus (BLC). In my little spare
time I implemented a BLC interpreter in C [3, 4].
I thought it would be interesting to share it on this mailing list since
the motivation behind BLC is similar to the one behind VPRI's Nile [5] and
Maru [6]. The test suite [7] gives a rough overview on how BLC works:
* 10, 110, 1110, ... are variables. 10 refers to the top of the
stack (the local environment), 110 refers to the next variable in the
stack and so on.
* 00M, where M is a term, defines a lambda expression expecting one value
on the stack. E.g. 0010 is the identity function which in Scheme
would be (lambda (x) x).
* 01MN, where M and N are terms, is a function application. E.g.
0100100010 is the same as ((lambda (x) x) (lambda (x) x)) in Scheme.
John Tromp's paper furthermore shows how boolean values are
represented using 0000110 and 000010 (i.e. functions taking two
arguments and returning the first or second argument). Scheme's cons is
represented by a function accepting a boolean and returning the head or
the tail of the list. An empty list is represented by 000010 (false). The
paper shows a meta-circular interpreter implemented in 210 bits!
I'm still undecided about how to approach some things:
* How does parallel processing fit into the picture?
* What's the best way to implement a DSL including booleans, integers,
floating point numbers, strings, .. on top of BLC?
* Is it possible to describe the electronics of integer addition and
multiplication in BLC and still have it jit-compiled to run efficiently on
x86 hardware?
* How to implement I/O (maybe use monadic objects)? Could the I/O
implementation provide equivalent functions to Scheme's quote and eval,
too?
Any comments and suggestions are welcome :)
Regards Jan
BTW I am looking forward to the VPRI report on the STEPS project and I
hope there will be future work to make computing suck less.
[1] http://homepages.cwi.nl/~tromp/cl/LC.pdf
[2] http://en.wikipedia.org/wiki/De_Bruijn_index
[3] https://github.com/wedesoft/blc/
[4] https://github.com/wedesoft/blc/blob/master/blc.c
[5] https://github.com/damelang/nile/
[6] http://piumarta.com/software/maru/
[7] https://github.com/wedesoft/blc/blob/blc/spec_blc.c#L94
_______________________________________________
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc
