PyLambda

Overview

PyLambda is a language and compiler for if you want to mess around with various lambda expression encodings (as emitted into valid python code). In particular, PyLambda takes in a simple imperative language frontend and produces terms of lambda calculus to be interpreted by Python. The full specification of the language can be seen in specification.md

All expressions generated by PyLambda are either boilerplate, definitions, interpretations, or, of course, lambda expressions. There are a few cases where exceptions come up, but that's about it.

WARNING: This is not a serious language and should not be used as such. Code will be slow and may cause python to crash very easily. Any number over 1000 or so, along with significant control flow...will crash. So keep that in mind

Installation and Execution

To install PyLambda, simply git clone this GitHub and have Python 3.7+ installed (tested on 3.9.4, may not work below this)

To test that the installation works as intended, run:

python test.py tests

To interpret a pylambda file without any input, run:

python pylambda.py file.pylambda | python -

To write the compiled results to a file (for inspection or running a code with input):

python pylambda.py file.pylambda > out.py

To get a (somewhat) readable translation, use the --debug flag, e.g.:

python pylambda.py file.pylambda --debug > out.py

All errors can be reported directly to Checkmate#0888 on discord or filed as an issue in this GitHub

Examples

To understand the basics of the lambda calculus and encodings, I recommend either a good PL book or the intro Wikipedia article.

PyLambda can generate code for a variety of standard commands. For example, you may write

print true;

PyLambda will produce the valid python code

# Boilerplate
print((lambda _x : lambda _y : _x) (True) (False))

Which is just the usual lambda calculus encoding of True. When run, this produces, of course, the single term True.

A more complicated example may include an operation, say print true or false;. PyLambda will produce:

# boilerplate
print((lambda _b1 : lambda _b2 : ((lambda _b : lambda _c : lambda _d : (_b (_c) (_d))) (_b1) ((lambda _x : lambda _y : _x)) (_b2))) ((lambda _x : lambda _y : _x)) ((lambda _x : lambda _y : _y)) (True) (False))

Which can be read as if b1 then true else b2, where b1=true and b2=false in this case. If in debug mode, in particular, this same code will produce:

# boilerplate and declarations
_value = LOR (TRUE) (FALSE)
print(_value (True) (False))

Which highlights the "interpretive" nature of the PyLambda compiler on constants.

Flags

PyLambda, at the time of this writing, supports three flags. All flags must be given after the filename, in any order:

Flag	Description
--debug	Outputs "readable code"
--raw	Prints raw lambdas
--no-input	Replaces input with 0

In more detail, raw causes the resulting python code to print out the lambda expression of each term rather than the actual value.

No-input replaces all cases of input x with x = ZERO, for example, where ZERO is the Lambda-calculus encoding of 0.