church encoding
i was showing my friend this website and telling them the story behind my header and all of the lambda branding that i have and he encouraged me to share this as a blog post as well.
during my freshman year of college, i was really struggling in my introduction to computer science course: nothing was clicking to me and i was constantly reconsidering going into the major. i ended up choosing to “lock in” and spent a lot of time/effort studying. i did well in the course after that, but i still didn’t feel like i was any “good” since my classmates were throwing around these fancy terms at the time like “inheritance” and “polymorphism”.
one day, one of my favorite professors (samTH!), gave my intro class a little brainteaser to think about after we learned about lambdas: he introduced the concept of church numerals to us; something like:
\[\begin{align*} 0 &= \lambda f.\, \lambda x.\, x \\ 1 &= \lambda f.\, \lambda x.\, f\, x \\ 2 &= \lambda f.\, \lambda x.\, f\, (f\, x) \\ & \; \; \vdots \\ n &= \lambda f.\, \lambda x.\, f^{\circ n}\, x \\ \end{align*}\]and then asked us if we could think about how to define addition, multiplication, and exponentiation in church encoding where we could only use pure untyped lambda calculus:
\[\begin{array}{rcll} \text{exp} & ::= & x & \quad\text{variable} \\ & \mid & \lambda x.\, \text{exp} & \quad\text{abstraction} \\ & \mid & \text{exp} \; \text{exp} & \quad\text{application} \end{array}\]i really enjoyed the lesson and thought about this problem in passing a bit, messed around with church numerals and the lambda calculus syntax, and the answer came to me while i was sleeping. i tested it out after i woke up and ended up getting the definition for all three (i think the others were more straightforward to derive since multiplication is just repeated addition and exponentiation repeated multiplication) and showed it to samTH!
he then asked me if i could do subtraction…
either way, it was the first moment that i felt like i chose the right major. as a result, i try to just have a little lambda everywhere i code as a reminder
so fun fact my terminal at work looks like this:
