3 ms·
LC is only computationally foundational; it describes recursive functions. It's just another universal turing machine. LC has a great disadvantage: it's diffic
by kazinator 4y ago
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.
- somewhereoutth 4y agoPerhaps LC is telling us that maybe macros weren't such a good idea after all??
- anderskaseorg 4y agoThere is. Using the Mogensen–Scott encoding, a self-interpreter can be written in lambda calculus as (λf.ff)(λf.λt.t(λx.x)(λm.λn.ffm(ffn))(λm.λv.ff(mv))), which is a direct translation of the equivalent Haskell code data Term t = Var t | App (Term t) (Term t) | Abs (t -> Term t) newtype Function = Function {apply :: Function -> Function} interpret :: Term Function -> Function interpret (Var x) = x interpret (App m n) = apply (interpret m) (interpret n) interpret (Abs m) = Function (\v -> interpret (m v)) https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin...
- kazinator 4y agoI don't see what in the interpreter converts the lambda calculus into the Morgensen-Scott encoding. The Wikipedia page describes a "mse" function that is in some meta-language which is not lambda calculus. So first wee need a Lambda Calculus based interpreter for the meta-language, which can run this "mse" function. It looks like mse[x] is supposed to match a variable term, and mse[M N] matches a function application and so on. There are no such concepts and representations in lambda calculus, not to mention shape matching on them. The meta language might as well just be a paragraph of English: instructions on how to hand-compile the lambda calculus into a bunch of thunks which the interpreter can just invoke in certain ways to bring about the evaluation.
- tromp 4y agoYou're claiming that LC cannot implement a quoting operator. Which is quite wrong. What you misunderstand is that a LC quote would not work on arbitrary lambda terms. A Mogensen quote operator would take a Mogensen encoding, and output a Mogensen encoding of that Mogensen encoding. Or a BLC quote operator would take a bitstring like 0010 which encodes the identity function λ 1, and output the blc encoding of the nil-terminated list of 4 booleans that represents that bitstring: 01000101100000110010110000011001011000001001011000001100101100000100000100000000101101110110
- kazinator 4y ago> would take a Mogensen encoding obtained where? > output a Mogensen encoding of that Mogensen encoding That's not what a quote operator does; it does precisely nothing, yielding the argument formula without evaluating it. No encoding-of-encoding. Just the encoding. > output the blc encoding of the nil-terminated list of 4 booleans that represents that bitstring Where/how does that become λ 1 again?
- tromp 4y ago> That's not what a quote operator does; it does precisely nothing, This is what gives Lisp murky semantics; you need something (quote) to do nothing, while having nothing (no quote) does something (evaluate). Lisp lacks referential transparency, even without the use of variables. An evaluated term can be evaluated again, yielding something different. > Where/how does that become λ 1 again? By decoding it, which is what mostly what the LC self-interpreter does, as detailed on pages 6,7 of [1]. [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
- kazinator 4y ago> 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.
- lisper 4y ago> it's difficult to write a LC interpreter in LC. Why? It's pretty easy to write Lisp in LC (a simple Lisp, not the feature-full version described in TFA) and it's pretty easy to write an LC interpreter in Lisp. I'll bet that an LC interpreter in LC could be done in only a few hundred lambda terms.
- tromp 4y ago> an LC interpreter in LC could be done in only a few hundred lambda terms. Make that a few dozen...
- lisper 4y agoYeah, I should have realized that. In fact, I had seen your BLC interpreter some time ago but for some reason it didn't come to mind as I was writing that. I must be getting old.
- haskellandchill 4y agolisper and kazinator need to put down the keyboard and spare some time for reflection. thanks tromp for your tireless efforts at education. big fan of your work!
- kazinator 4y agoGood point; a minimal Lisp needed for processing LC doesn't require the 42 page formula. That has features like mutable global variables.
- tromp 4y ago> LC has a great disadvantage: it's difficult to write a LC interpreter in LC. It's not; here it is quoted from [1]: (λ 1 1) (λ λ λ 1 (λ λ λ λ 3 (λ 5 (3 (λ 2 (3 (λ λ 3 (λ 1 2 3))) (4 (λ 4 (λ 3 1 (2 1)))))) (1 (2 (λ 1 2)) (λ 4 (λ 4 (λ 2 (1 4))) 5)))) (3 3) 2) (λ 1 ((λ 1 1) (λ 1 1))) > LC does not know what a LC expression is. Again, it's trivial to encode LC terms as bitstrings [1], which are trivially decoded back into lambda terms. That is exactly what the above lambda expression does. Alternatively, you can encode LC terms with Mogensen's encoding, but that one doesn't give you a textual representation like a bitstring. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Lambda_encoding https://tromp.github.io/cl/Binary_lambda_calculus.html#Lambd...
- kazinator 4y ago> BLC requires translating bitstrings into lambda terms, to which the machine (itself a lambda term) can be readily applied. I.e. a man behind the curtain is required to complete the "interpreter".
- bidirectional 4y agoCan you explain at a high level what you think a valid LC-in-LC interpreter looks like then? Because it's very hard to understand what your objection is to the examples in this thread.
- heavenlyblue 4y agoThe objection to them is that they are trivial and lead to none of the profound truth that is usually implied by their presentation.
- kazinator 4y agoA 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.