Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus
As author of the Binary Lambda Calculus (BLC), I find this quite fascinating.
It implements LISP in 163,654 bits of BLC.
For comparison, minimal esoteric languages like BLC itself can be implemented in 232 bits of BLC, and Brainfuck in 893 bits.<p>I'm still reading the document, but one thing that caught my eye is the List encoding with cons and nil, which is claimed to be a Mogensen-Scott one.<p>Rather, cons \x\y\c. c x y is the Scott encoding of infinite lists that have no nil terminator (also known as streams) and thus only one constructor, while nil is the Scott encoding in nil-terminated lists with 2 constructors.<p>Thus the given encoding is some non-standard hybrid of streams and lists that helps BLC achieve its conciseness. In Wikipedia [1] it's described as<p>> Alternatively, with NIL := FALSE, the construct l (λh.λt.λz.deal_with_head_h_and_tail_t) (deal_with_nil) obviates the need for an explicit NULL test<p>[1] <a href="https://en.wikipedia.org/wiki/Lambda_calculus#Pairs" rel="nofollow">https://en.wikipedia.org/wiki/Lambda_calculus#Pairs</a>