Whiteboard problems in pure Lambda Calculus

I&#x27;m confused by their &quot;3 part linked list&quot;. I always thought the elegance of lambda calculus was that each data structure was equivalent to the method by which you use it. A boolean <i>is</i> a function that does a conditional statement. A number <i>is</i> a function that does a loop. So logically, a list <i>is</i> a function that does a fold, like &quot;LIST :: (a -&gt; b -&gt; a) -&gt; a -&gt; a&quot;.

It&#x27;s things like this that make me wonder what the world would be like if we had embraced the Church-style Lambda Calculus model instead of the Turing system. I don&#x27;t know if it would be better or worse, but I think it&#x27;s an interesting thought experiment.

I&#x27;ve been wondering why a lot of things are the way they are in functional programming, not being very lambda inclined myself, I didn&#x27;t seek it out, but this post summarized a lot that has been on my mind lately.<p>In particular, and with apologies for being so clueless – it never occurred to me why currying was necessary – I didn&#x27;t realize lambda calculus required functions to take only one argument. With that limitation, currying is genius.

Tangential book recommendation: I have found the first chapters of &quot;Type Theory and Formal Proof&quot; a great in-depth introduction into lambda calculus and its typed variations.

Thou shalt not make use of French if thou doest not know the language. Deaux is a village in France (you can google it).

A while ago I wrote a Brainfuck interpreter in lambda calculus. I abused the Clojure macro system to make my job a little easier, and of course, I wrapped it in an interface that could do IO, but this does compile to a single pure lambda calculus function which takes a (church encoded) brainfuck program and input string and returns an output string.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;MichaelBlume&#x2F;lambdafuck&#x2F;blob&#x2F;master&#x2F;src&#x2F;lambdafuck&#x2F;core.clj" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;MichaelBlume&#x2F;lambdafuck&#x2F;blob&#x2F;master&#x2F;src&#x2F;l...</a>

I often feel that Alan gets adequate credit but Alonzo too little. There must be something I don&#x27;t get.

Factorials in pure lambda calculus:<p><a href="http:&#x2F;&#x2F;www.flownet.com&#x2F;ron&#x2F;lambda-calculus.html" rel="nofollow">http:&#x2F;&#x2F;www.flownet.com&#x2F;ron&#x2F;lambda-calculus.html</a>

See, the original post about white boarding in LISP was original with certain humor to it.<p>I can&#x27;t say this was even close in terms of enjoyment or originality. Maybe I missed the point?

Another tangential reading recommendation: I only started reading about Lambda Calculus a few days ago. The Imposter&#x27;s Handbook does a good job covering it, but also praises this medium article that&#x27;s super helpful (and also explains the y combinator): <a href="https:&#x2F;&#x2F;medium.com&#x2F;@ayanonagon&#x2F;the-y-combinator-no-not-that-one-7268d8d9c46#.m4mobqry9" rel="nofollow">https:&#x2F;&#x2F;medium.com&#x2F;@ayanonagon&#x2F;the-y-combinator-no-not-that-...</a>

Reminded me about good old <a href="https:&#x2F;&#x2F;codon.com&#x2F;programming-with-nothing" rel="nofollow">https:&#x2F;&#x2F;codon.com&#x2F;programming-with-nothing</a>

&gt; Anyway, here’s fizz buzz in pure lambda calculus:<p>Serious question: if the code is legit and can&#x27;t be simplified any shorter (like you could in any C style lang), can we consider lambda calculus the string theory of programming? By that I mean lots of work for little gain (as it turned out to be nowadays) ((I know it has gains in other fields)).<p>I can imagine it like an assembly like compile target and it can explain the verboseness.

The same thing, but in Ruby stabby-proc notation (from 2012) by Tom Stuart:<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=VUhlNx_-wYk" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=VUhlNx_-wYk</a><p>Well, perhaps not <i>exactly</i> the same thing, but only because Ruby requires the Z-combinator due to applicative order.

Instead of pure lambda calculus, another less severe route would be to simply restrict yourself to Church-encoded or Scott-encoded formulations of data structures.

I love this so much.

Nice article! But you have a typo.<p>(λx.x y)<p>does not return y, though<p>(\x.x) y<p>does.