7
\$\begingroup\$

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!

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ May 1 at 17:52
  • 1
    \$\begingroup\$ @RedwolfPrograms Thanks! \$\endgroup\$
    – Andrew Li
    May 1 at 17:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Aug 17 at 7:43
3
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.