Add Lambda Calculus Lang

[Shanethegamer]

I think it would be a fun addition as an esolang. Of course Lambda Calculus itself isn't a programming language so it needs an implementation as a programming language. Binary Lambda Calculus and Universal Lambda exist but don't seem suited for code.golf since you can't easily write the binary directly. Ideally it shouldn't need impure functions for IO like Unlambda so that the pure nature of Lambda Calculus can be preserved. I think being able to create immutable bindings on the top level as syntactic sugar is fine though. I would like for the code to just be a function from input to output. Also, encodings will need to be chosen for a couple data types so that the input and output can be translated from strings to functions and vice versa. Performance may be an issue but if calculation can be done in sed fast enough with unary than hopefully Lambda Calculus will also be fast enough for most holes. I don't have prior experience writing compilers but I would be willing to try to help with making an implementation. This lang would surely be niche but I know there would be at least a few people willing to golf in it.

[Kacarott]

For syntax, I would like to propose the syntax used in the Lambda Calculus lang for Codewars which I helped create. (The lang/compiler itself however isn't suitable for code.golf).

A summary of the syntax:

• Top level bindings are allowed
• Lambdas are written using \ and .
• Identifiers can be any length and are whitespace separated (though presumably most of the time for golfing single char names would be used)
• Multiple lambdas can be written together in shorter form: \ a . \ b . \ c . b c a == \ a b c . b c a
• functions can span multiple lines as long as subsequent lines are indented
• unused arguments can be called _ (potentially allowing some slight optimisations by never loading that arg)
• () can be used as an undefined value, throws an error if ever evaluated
• Comments are denoted with #

Some sample code of how that might look:

# Booleans
true  = \ a b . a
false = \ a b . b

# Numbers
zero = false
succ = \ n f x . f (n f x)

y = \ f . (\ x . f (x x)) (\ x . f (x x))

counter = y (\ count n b . b (count (succ n)) (n) ) zero

Open questions would be, should direct recursion be allowed (ie. should a top level defined function be allowed to refer to itself?). In Codewars this is configurable, when enabled functions that refer to themselves implicitly have a Y combinator added to their definition to allow it. Another question is how the "main" function should be defined. A top level function called main? Or just an anonymous function after the named functions?

[Kacarott]

As for encodings, my idea would be a List of Bytes, where List is a Scott list:

nil = \ n _ . n
cons = \ x xs . \ _ c . c x xs

And bytes are little-endian fixed width Scott Binary numbers.