Conditional statements, the lambda calculus and early/late binding

By: on December 22, 2010

Soon after I started learning Smalltalk, I found my brain broken. Smalltalk doesn’t have control structures. No ifs, no whiles, no for loops. All these structures are instead patterns of message
passing [1].

Conditionals in Smalltalk work like this: the class Boolean has two subclasses, True and False. Each has a well-known instance, true and false, respectively [2].

The equivalent of C’s

  if (condition) {
    one_func();
  } else {
    other_func();
  }

is

  condition
    ifTrue: [ self oneMethod ]
    ifFalse: [ self anotherMethod ]

How does it work? Boolean defines a method #ifTrue:ifFalse: taking two blocks as parameters. (Remember, what Smalltalkers call a block other folks call a closure. A Lisper might call the parameterless blocks that #ifTrue:ifFalse: takes thunks.) True and False in turn implement #ifTrue:ifFalse: thusly:

  True>>ifTrue: trueBlock ifFalse: falseBlock
    ^ trueBlock value.

  False>>ifTrue: trueBlock ifFalse: falseBlock
    ^ falseBlock value.

So we evaluate condition to either true or false, send it the #ifTrue:ifFalse: message, and we’re done.

After reading Peter Seibel’s Practical Common Lisp I had the mistaken impression that IF was a necessary special form, and I couldn’t understand why that would be the case, when Smalltalk manages to avoid the issue.

I grabbed Wikipedia (font of all true information, of course) and looked at the lambda calculus. You can implement conditionals like this, in the untyped lambda calculus:

  TRUE = λxy. x
  FALSE = λxy. y
  IFTHENELSE = λcxy. c x y

Hang on, that looks a bit familiar! True is a function that takes two thunks and returns the value of the first, and False one that returns the second? And a conditional’s a function taking a condition and two thunks?

And lo and behold, I recently finally finished reading – after three attempts, I’m ashamed to admit – William Cook’s rather excellent On Understanding Data Abstraction, Revisited, and there in section 5.4 Cook says just that – “The implementation of Booleans and conditionals [in Smalltalk] is exactly the same as for Church booleans in the lambda-calculus.”

So then I went back to Common Lisp, boggling anew. And then I realised what I’d missed. PCL says “Because all the arguments to a function are evaluated before the function is called, there’s no way to write a function that behaves like the IF operator you used in Chapter 3.” But the way to avoid evaluation of an argument is to wrap it up in a thunk. And then I realised what I had missed: In Smalltalk, true and
false are functions, but in Common Lisp they’re just values, not functions [3]. So when you turn true and false into values, you then have to make your conditional special. It, too, needs to be early bound.

[1] Semblance to Hewitt’s paper Viewing Control Structures as Patterns of Passing Messages entirely deliberate.

[2] That uses two of Smalltalk’s 5 reserved words, but I see no reason why true and false couldn’t simply be in the Smalltalk dictionary (as opposed to being used by the VM as a(n important) optimisation). If I’m talking nonsense, and you simply have to have these as reserved words, feel free to correct me!

[3] I’m not knocking Common Lisp here! You prematurely bind T and NIL for efficiency. Smalltalk does the same: #ifTrue:ifFalse: and friends are all inlined.

FacebookTwitterGoogle+

2 Comments

  1. It is funny to me that ultimately, this boils down to smalltalk having very convenient lambda syntax and lisp not having such. You could certainly write an if-ish function in CL:

    (defun applicative-if (condition) true-thunk false-thunk)
    (if condition (funcall true-thunk) (funcall false-thunk)))

    Which you’d use:

    (applicative-if t
    (lambda () ‘true)
    (lambda () ‘false))

    But those lambdas are uglyish. If you extend the reader to support blocks with a reader macro, you could write instead

    (applicative-if t
    [ 'true ]
    [ 'false ])

    Where [...] expands to (lambda () …)

    And you are most of the way there. I feel like a large amount of code I write is to get around how clunky the syntax for anonymous functions is in most languages, which is why I like lightweight syntax like Clojure’s fn or factor’s quotations.

Post a comment

Your email address will not be published.

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>