9
\$\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\$ Commented May 1, 2021 at 17:52
  • 1
    \$\begingroup\$ @RedwolfPrograms Thanks! \$\endgroup\$
    – user101133
    Commented May 1, 2021 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
    Commented Aug 17, 2021 at 7:43

1 Answer 1

2
\$\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 and acknowledge you have read our privacy policy.