Tips for golfing in Binary Lambda Calculus

BLC (Binary Lambda Calculus) is a binary encoding of untyped lambda calculus which was created to “provide a very simple and elegant concrete definition of descriptional complexity.”

What are some tips on how to golf down BLC programs/functions?

Please submit only one tip per answer!

• Welcome to Code Golf! May 1 at 17:52
• @RedwolfPrograms Thanks! May 1 at 17:54
• May I broaden the scope of this question to "all functional Turing tarpits" such as SKI calculus, Iota and Jot, etc? I think many tips can be shared between these. Aug 17 at 7:43

1 Answer

This is fairly obvious but I'll put it here for completeness sake. It also applies to untyped lambda calculus in general so I'll write it like that for readability.

Anywhere you want reuse a value/function that is at least as long as this expression

$$(\lambda v.p) \space d$$

you can declare it as a variable. Here "p" is the original program with all the original instances of your repeated value replaced by "v". "d" is the definition of the repeated value itself.

A contrived example

A program like this

$$(\lambda f.\lambda z.f f f f f z) (\lambda f.\lambda z.f f f f f z)(\lambda f.\lambda z.f f f f f z)$$

can be written as

$$(\lambda v.vvv)(\lambda f.\lambda z.f f f f f z)$$

This is a simple example but it's a neat abstraction because "v" can be used however deeply nested you decide to make "p".