[kazinator]

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.

[woodrush]

The basic tools required for implementing a LC interpreter in LC is demonstrated in LambdaLisp. Although LambdaLisp implements Lisp, the same tools can be used to implement a LC interpreter in LC.

The largest concern in question here may be how I/O is done. I/O can be done by viewing a lambda term as a function that takes a string as an input and outputs a string. Here, a "string" can be expressed as a "list" of "characters", where lists can be encoded using the Scott encoding, and characters can be encoded as a list of bits, and "bits" can be encoded as 0=\x.\y.x, 1=\x.\y.y. This I/O strategy is used in LambdaLisp as well, and is explained in my post in [1].

How Lisp terms are encoded as lambda terms in LambaLisp is explained in [2].

To implement a LC interpreter instead of a Lisp interpreter in LC, it then remains to somehow encode and quote a lambda calculus term into a lambda calculus term. The function described by tromp's reply in this thread, called the Universal Machine, does this - it does so by using an encoding called the binary lambda calculus (BLC) notation for encoding lambda terms into lambda terms. In this notation, an arbitrary lambda term in the usual plaintext notation such as \x.\y.\z.(x y z) can be encoded into a bitstream. The converse is also always possible. The Universal Machine uses the BLC notation for expressing lambda terms, with the same 0/1 bit encoding and list encoding mentioned earlier, and outputs a bitstream (encoded as lambda terms) representing the evaluation result. The BLC notation is described in my post in [3].

[1] https://woodrush.github.io/blog/lambdalisp.html#handling-io-...

[2] https://woodrush.github.io/blog/lambdalisp.html#basic-data-s...

[3] https://woodrush.github.io/blog/lambdalisp.html#the-binary-l...

[kazinator]

Statements like "IO can be done [in lambda calculus] by ..." really mean "lambda calculus doesn't have IO but can be extended by ...".

Here's what it means to have an LC in LC interpreter. Firstly pick what LC means. Choose a representation for it. Exactly one. Show that this is lambda calculus with no extensions. Then show how an embedded expression of this can be interpreted.

For instance supposed we have a lambda calculus which is based on a three letters M I and U. Spaces are insignificant.

Say that MUIMUIMMU is a valid expression. Then a self-interpreting situation might look like this:

  IMUMIUMM...MUI MUIMUIMMU UMI

The to-be-interpreted expression appears embedded. I set it off with spaces for clarity. It is not translated into any different representation. The surrounding material represents the interpreter. There needn't be an epilogue piece after the embedded expression. Important: no part of this interpreter depends on the embedded expression. We can swap in arbitrary other expressions without changing the interpreter; will correctly interpret those expressions.

I am skeptical that this is possible with standard, unextended lambda calculus, whether regular or de Bruin.

[kazinator]

Under these rules, an identity function can serve as an interpreter. This is valid. Empty text (nothing wrapped around the input case) is also an instance of interpretation. The question is, can it be achieved without just throwing the expression into the path of the host evaluator in these kinds of ways.