LC is only computationally foundational; it describes recursive functions. It's just another universal turing machine.
LC has a great disadvantage: it's difficult to write a LC interpreter in LC. This project shows exactly what that means. To write an LC interpreter, you need a data structure for representing expressions. You need a symbolic data type.
LC does not know what a LC expression is. Papers about LC know what that is, but they are not executable.
In Lisp we can say, okay, lambda calculus can be represented sort of like this:
(lambda (x) x)
and so on. That's a nested list. It contains symbols. We can use an assoc list to associate symbols with the terms that are their values. And so on ...
Lisp has the programmatic vocabulary to talk about lambda calculus formally, in a way that is executable.
I don't suspect there is a significantly easier way for LC to interpret LC than to use the 42 page expression to create a Lisp, and then write the interpreter in that lisp.
LC has a great disadvantage: it's difficult to write a LC interpreter in LC. This project shows exactly what that means. To write an LC interpreter, you need a data structure for representing expressions. You need a symbolic data type.
LC does not know what a LC expression is. Papers about LC know what that is, but they are not executable.
In Lisp we can say, okay, lambda calculus can be represented sort of like this:
and so on. That's a nested list. It contains symbols. We can use an assoc list to associate symbols with the terms that are their values. And so on ...Lisp has the programmatic vocabulary to talk about lambda calculus formally, in a way that is executable.
I don't suspect there is a significantly easier way for LC to interpret LC than to use the 42 page expression to create a Lisp, and then write the interpreter in that lisp.