Let's Talk About Lambda Functions!

[Ian Bicking]

I know this is getting off topic (or at least into another language),
but I am weak and my ego does not allow me to let you tell me I am wrong
when I am not ;-)

On Wed, 2002-07-31 at 15:16, James J. Besemer wrote:
> 
> Ian Bicking wrote:
> 
> > Well, it looks a lot like lambda calculus, because True and False are
> > two different classes, with definitions like:
> 
> > This should remind one of true/false in lambda calculus (though
> > obviously with a very different notation).
> 
> Narrowly interpreted, there is a similarity, in that both systems
> build up their "control flow" abstractions from True and False,
> as opposed to, say, COND.  Further, they both define True
> and False in terms of each language's fundamental abstraction
> mechanism, class definitions in Smalltalk's case and and Lambda
> expressions for Lambda Calculus.

You really can't see the similarity?

In lambda calculus (in Python syntax):

  True = lambda t, f: t()
  False = lambda t, f: f()

Translating traditional Python:

  if something: # Where something is True or False, nothing else
      doA()
  else:
      doB()

In lambda calculus:

  something(doA, doB)

That is, "if" becomes a function call, where true evaluates the first
argument, and false evaluates the second argument.  Obviously, you need
a better lambda syntax to do this nicely, but the lambda calculus is
still possible to implement in Python.
 
So trueness or falseness is an object/function that reacts in a certain
way -- calling the first function/argument if true, calling the second
if not.

This is exactly how Smalltalk works.  You have to write ifTrue:ifFalse:
instead of parenthesis, but that's incidental.  If you pass that message
to a True object, if evaluates the first argument/block, if you pass it
to False it evaluates the second.

Traditional control structures have a Mind that looks upon the
conditional value, and decides what to do next based on it.  In lambda
calculus, true/false *is* the Mind, there is no outside logical force
directing computation.  At least, that's how I see the essence of the
distinction -- in this way Smalltalk is like the lambda calculus (or at
least pretends to be -- in fact the VM is actually the Mind just like
always, at least for true and false values).

> > That is, you can't (usefully) implement ifTrue: in your own custom
> > class.
> 
> Absolutely not true.

I really don't know about anything but Squeak, but it's absolutely true
in Squeak (even more annoyingly you can't reimplement to:do:, but that's
another issue).  I have gotten the impression that other implementations
of Smalltalk act the same way.

This isn't true of most other control structures in Smalltalk/Squeak,
just ifTrue:ifFalse: and maybe a handful of others (ifNil:?)

It means that:

x ifTrue: [a] ifFalse: [b].
y

gets compiled into something like (very rough bytecode):

push x
(if popped value is True) goto loop_a else goto loop_b
# (if popped value is True) being a primitive bytecode
loop_a:
a
goto loop_y
loop_b:
b
loop_y:
y

That is, the ifTrue:ifFalse: message is never passed to x, and no
closure is created for [a] and [b].  (And, of course, if you did
something like "x ifTrue: a ifFalse: b" it'll compile slightly
differently)

You'll never notice this unless you try to implement an ifTrue:ifFalse
message in your custom class.  If you do, and you try to use it, you'll
find it doesn't work like you'd have expected (it'll should cause an
error).  This does *not* happen for messages like do: or whileTrue,
which are not optimized in this way.

  Ian