XDEFiANCE Online Shop

“You’re not the first candidate to show up here and reinvent programming from first principles using lambda calculus.”

“Look,” she says. “We’ve all read Programming with Nothing. We’ve all seen What is PLUS times PLUS. You’re not breaking any new ground here.”

You shake your head vigorously. “I would never be caught dead using Lambda calculus. It’s a bloated language.”

You scribble in your notepad briefly. Showing all your work would be tedious, but you should at least walk her through the interesting parts.

“I won’t bother making the formatters point-free, since they’re just output,” you say, as if Dana cares.

Combinatory logic is a model of computation that is extremely minimal. All you start with are two functions: S and K.

You can compute anything you want just by passing these two functions into each other. For example, the identity function I = (x) => x can be expressed as S(K)(K).

Combinatory logic is basically lambda calculus without variables. Despite this limitation, combinatory logic is still Turing complete.

If you found this post interesting (whether or not you understood it), the following resources would be good places start exploring:

After reading To Mock a Mockingbird, I wanted to program in combinatory logic but found existing tools lacking. So I spent a weekend building Skoobert, which is intended to be the ideal programming language for experimenting with lambda calculus and combinatory logic. Give it a try and let me know what you think!

“So,” she says, “walk me through FizzBuzz.”

“That should do it,” you say to yourself. “Just need to combine these a few times.”

Bluebird, cardinal, warbler, thrush. Avian friends you know well.

“First, we add combinators until n is by itself on the right.”

“It’s JavaScript. You can literally do recursion without it.”

“JavaScript but lazy,” you explain. “And without the bloat.”

Variables are for wimps. You replace each with its definition.

And you can build up arbitrarily complex functions from there. There is no limit.

Dana. The interviewer. Friendly, efficient. She leans forward.

You could do this in your sleep. “Is JavaScript okay?”

Dana looks puzzled. “Are we still doing FizzBuzz?”

She stands. “Okay,” she says finally. “Let me stop you there.”

Dana leans forward. She seems interested now. “Church numerals?”

Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.”

You saw this coming. You paste your code into Skoobert.

You sigh. Perfect code tarnished by human consumption.

Just a few more loose ends. Numbers to digits. Digits to strings. Strings to output.

“Are you satisfied?” she cries. But you aren’t. Not yet.