The Misp Chronicles XI: Closure Currying

What’s a Curry?

A curry is a special way of defining functions. Functional curries are only accidentally related to Thai and Indian cuisine. Functional curries come from Haskell, not the programming language, not originally, rather the man Haskell B. Curry. And not him either, really, because Christopher Strachey coined the term and Frege was currying long before Haskell. Others were currying long before that and I’m sure you’ve curried too since comes up in a elementary algebra.

When I first learned algebra, I was told that a ^ (b * c) is the same as (a ^ b) ^ c. I couldn’t tell you why that’s true because they don’t teach math in school (or science for that matter) instead they teach dogma. I did poorly in my mathematical dogma classes so I needed remedial education: I majored in math. Math requires logic. I’m not a very logical person, so I got my Masters in Philosophy. Philosophy was far too tricky, so I got a job programming computers. Computers, as we all know, are remarkably stupid. You have to explain everything, and they’re inclined to misunderstand. It’s easy to mistake their ignorance for malice. Or in the immortal words of Cleveland the Janitor, “It’s a dumb beast you be foolin’ with. It don’t never sleep.”

Algebra class curring is the process of converting an expressions of the form a ^ (b * c) to (a ^ b) ^ c. As applied to functional programming (and Misp in particular), its the process of converting an expression of the form {|a b| c} to {|a| {|b| c}}. Let’s consider a specific example. The function which forwards directly to pair is {|a b| (pair a b)}. The curried version is {|a| {|b| (pair a b)}}. This difference, though small, has practical uses. Rather than building a pair all at once, you can supply part at a time: the head first and the tail later. From what I hear, Python is adding this spiffy trick.

Let’s see an example of curried pairing in action:

(({|a| {|b| (pair a b)}} ‘serpents-head) ‘lions-tail)

This expression evaluates to (serpents-head . lions-tail): it makes a chimera. How so? Let’s look at the steps. We start with a curried pair. After add a serpents head, the resulting mixture is a potion of hydradic growth. When applied to a lions tail. The lion becomes a chimera. (We still need to add the goat head, but you get the idea.) Using the environment building transformation we talked about previously, we can make all the steps explicit:

({|curried-pair| ({|hydradic-growth| (hydradic-growth ‘lions-tail)} (curried-pair ‘serpents-head))} {|a| {|b| (pair a b)}})

Whoa. After reading that, I need a break.

Sugar Break

Improving the environment on mountain of Misp is wonderful service oriented activity. But it’s pretty hard for a regular guy. It’s a job for Context Free Man, and I’m not up to the challenge. Building the environment is a balancing act like balancing parenthesis. The rule for balanced parenthesis is simple:

paren-wrapped ::= ( yummy-goodness )

As you add yummy goodness, the open and close parenthesis get further and further apart. It’s the context-free-separation-disaster, and we need a super hero to take it on.

The disaster gets worse when you try to enrich the Misp environment:

rich-environment ::= ({|object-name| yummy-goodness} object-value)

See how the name of an object gets separated from its definition as you add yummy goodness. That’s crazy-go-nuts! It’s so crazy that Lisps resort to macros to combat the problem. In the Misp world, hiring Macro Man is out the the question: he’s too expensive. All we can afford is some more meta-level syntactic sugar. It’s empty calories, but Misp has been scare on programmable substance from the start. Misp proper doesn’t have strings or numbers or files or IO of any kind—just symbols and pairs. We have ways of writing down symbols and pairs, but it’s all meta-language. Meta-language is cheap since you can’t program with it. It won’t break the bank if we add one more bit. Here’s the rule:

Instead of: ({|object-name| yummy-goodness} object-value)
We write: object-name = object-value; yummy-goodness

If the expression takes more than one line, we can (and will) leave off the semicolon. The sugared chimeric formula is:

curried-pair    = {|a| {|b| (pair a b)}}
hydradic-growth = curried-pair 'serpents-head
partial-chimera = hydradic-growth 'lions-tail

Syntactic sugar does a body good.

The Closure Conundrum

Curry is yummy, but making it is tricky. See curried-pair is function which returns a function such as hydradic-growth. hydradic-growth has the effect of causing its argument to sprout a serpent’s head by pairing it with serpents-head. Thus our partial-chimera looks like (serpents-head . lions-tail). So hydradic-growth does the same thing as the function {|b| (pair ‘serpents-head b)}. It’s as though the a in curried-pair was replaced with ‘serpents-head. That’s a natural way to think about it, but it isn’t what Lisps do. Why? Well suppose that the inner body of curried-pair was complex with many occurrences of a. Replacing every a would require scanning the whole body. If the body contained conditionals, then you might end up doing a lot of work that no one ever sees. Lisps work differently.

Instead of replacing every a, Lisps usually make a table to represent the environment. In hydradic-growth, the symbol a is paired with the symbol serpents-head. Most Lisps have no way of representing these so called closures. Since we need to talk about them, we should have a way of writing them. We’ll use a Misp expression for it! We’ll represent hydradic-growth with the expression (closure ((a . serpents-head)) (b) (pair a b)). Notice that the body of the closure is the same as the body of curried-pair. We use the list of pairs ((a . serpents-head)) to show that a refers to serpents-head.

Finally, when we apply a closure hydradic-growth ‘lions-tail each time we come across a variable we first check if its an argument, and if not we see if it has an associated value in the environment. That’s all there is to it. And now we’re ready to write a Misp interpreter in Misp.