woodrush

I too suspect that writing in lambda's native functional style could save a lot of space. Compiling lisp.c from the ELVM repository generates a code much longer than LambdaLisp [1], which empirically shows that well I believe.

As for the pages of PDF, in mathematical terms, since any variable encodes to weight 1, I believe it would be something close to an encoding that degenerates all De Bruijn indices to 1, or in other words, one that only tries to weigh (or gives larger weight to) the complexity of abstraction depths and applications. Since that erases information about the variable I would guess it's not a universal method for weighing lambda sizes.

In this particular case for LambdaVM programs however, since the memory initialization clause nor the instruction clause never increases the maximum De Bruijn index value, I believe both the BLC size and "lambda page size" approximately grows linearly with the number of instructions, so I thought it would serve as an approximately-off-by-a-factor metric for weighing its size.

As for the ELVM lambda calculus back-end, I'll be sending the pull request very soon!

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].