Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

Thanks for your feedback, I forgot to mention the execution speed in the post. The number guessing game example (44 lines long) in the Usage section actually runs with an instantaneous response time on the terminal. I added some remarks on the execution speed.

> The situation with Lisp is exactly the same.

No it isn't, because the Lisp code is already understood to have an encoding. So we don't have to play any Gödel-numbering-like games to get the code to be able to talk about code. That battery is included.

> gives us a more convenient syntax for the latter, in the form of the quote macro

The ' in (cons 'lambda ...) is an instance of quote!

You must write (cons (intern "lambda") ...) to remove quote. Oops, now you're using a different kind of quote: a string literal quote. If you remove that, you will have character literals to otherwise build the symbol name.

I agree that quote is not essential: take out quote and you can still do useful symbolic processing. Just doing interactive testing and writing unit tests will be inconvenient, mainly.

The requirement for quote has a different effect. If we have quote, we can make the additional step in the documentation that all code has the representation produced by quote, even when quote is not being used. When lambda is seen in code, that is actually the same thing that (quote lambda) produces or that (intern "lambda") produces.

The above is almost inescapable if user-defined macros are supported. When code is read, it is not determined at read time what is a macro and what isn't. Therefore it is not known what parts of the form may need to be passed to a user-defined expander function without having been evaluated (and thus in the quote representation). The whole thing is in the quoted encoding, so that quote doesn't have to do anything other than pass through its interior.

> An evaluated term can be evaluated again, yielding something different.

Yes, and a Mogensen-Scott encoding can be Mogensen-Scott-encoded again, requiring two rounds of decoding, and so on.

Multiple rounds of encoding and evaluation seem inescapable of you have the entanglement of homoiconicity.

The quote operator in Lisp is designed exactly right.

In mathematics there are literals like the number 3 or the set {}. These objects stand for themselves and are not understood as requiring any calculation: they just are.

Symbols like x do not stand for themselves. If you want to talk about x literally as the symbol object, it is inescapable that there is some quoting operator to indicate that the usual semantics of x denoting something else do not apply. (Oxford's A Dictionary of Computer Science has a definition of literal which acknowledges this very issue.)

Literals being constants, it means that when they are concretely implemented in a computer, in the best possible way, they do nothing other than trivially reproduce a canned value that already exists before the program starts.

A LC interpreter (whether in LC or anything else) has to process the actual syntax with the lambdas and symbols (or integer literals, in the case of De Bruin).

If it is necessary to translate that representation to something else, the interpreter must do that itself.

You can take a LC expression and write some other LC expression which encodes it; but if that is done outside of LC in some meta-language, then that has to be counted as part of the interpreter's implementation, which means that it's not in LC any more.

Based on that, I think it's not actually possible without extensions to LC.

You need to be able to read the syntax with the lambda symbols and names (or integer constants in the case of De Bruin), so I/O is needed. Or else, if that is unacceptable, you need to be able to embed the representation of the code as a quoted literal.

Without I/O or quoting, you have no way to express the test cases.

Yes, I was clear above that I know ' means quote. My experiment is to compare Lisp to a restriction of Lisp where quote only works on symbols. This restriction doesn’t make it any harder to write a self-interpreter.

> If we have quote, we can make the additional step in the documentation that all code has the representation produced by quote, even when quote is not being used. When lambda is seen in code, that is actually the same thing that (quote lambda) produces or that (intern "lambda") produces.

I’m not sure what you’re suggesting here. Certainly the number (+ 2 2) must be distinguishable from the list '(+ 2 2). Even lambda expressions must be distinguishable from their quoted encodings, because otherwise lexical scoping breaks. If you make (lambda () x) equivalent to '(lambda () x), then this breaks:

    (let ((x 1)) (funcall (let ((x 2)) (lambda () x))))

and if you make (lambda () x) equivalent to `(lambda () ',x), then this breaks:

    (let ((x 1)) (funcall (lambda () (let ((x 2)) x))))

Macros expand at compile time, not runtime. Macros are also cool, but not fundamental, and don’t contribute to the ease of writing a self-interpreter.