If we had no if

Richard Suchenwirth 2002-11-28 - Imagine the makers of Tcl had failed to provide the if command. All the rest would be there. Doing more steps towards functional programming, I came upon this interesting problem, and will shortly demonstrate that it can easily be solved in pure-Tcl.

We still have the canonical truth values 0 and 1 as returned from expr with a comparison operator. The idea in the paper I read is to use them as names of very simple functions:

 proc 0 {then else} {uplevel 1 $else}
 proc 1 {then else} {uplevel 1 $then} ;# the famous K combinator

Glory be to the 11 rules of man Tcl that this is already a crude though sufficient reimplementation:

 set x 42
 [expr {$x<100}] {puts Yes} {puts No}

The bracketed expr command is evaluated first, returning 0 or 1 as result of the comparison. This result (0 or 1) is substituted for the first word of this command. The other words (arguments) are not substituted because they're curly-braced, so either 0 or 1 is invoked, and does its simple job. (I used uplevel instead of eval to keep all side effects in caller's scope). Formally, what happened to the bracketed call is that it went through "applicative order" evaluation (i.e., do it now), while the braced commands wait for "normal order" evaluation (i.e., do when needed, maybe never - the need is expressed through eval/upvar or similar commands).

Though slick at first sight, we actually have to type more. As a second step, we create the If command that wraps the expr invocation:

 proc If {cond then else} {
    [uplevel 1 [list expr !!($cond)]] {uplevel 1 $then} {uplevel 1 $else}
 }
 If {$x>40} {puts Indeed} {puts "Not at all"}

This again passes impromptu tests, and adds the feature that any non-zero value counts as true and returns 1 - if we neglect the other syntactic options of if, especially the elseif chaining. However, this is no fundamental problem - consider that

 if A then B elseif C then D else E

can be rewritten as

 if A then B else {if C then D else E}

so the two-way If is about as mighty as the real thing, give or take a few braces and redundant keywords (then, else).

Luckily we have an if in Tcl (and it certainly fares better in byte-code compilation), but on leisurely evenings it's not the microseconds that count (for me at least) - it's rather reading on the most surprising (or fundamental) ideas, and demonstrating how easily our good old Tcl can bring them to life...

fut This is in fact how Smalltalk does if, and also how boolean values are expressed in lambda calculus.

Next you should show us how to do everything using just NAND. - RS: Not everything, but all Boolean functions - follow that link ;-)

Well, I say his article on Gödel-number source code is long overdue.

DKF - Note that the most trivial way of discovering a Gödel-number for a Tcl script is using the binary command but you are going to run into problems with scripts of any length more than a few bytes:

  proc Gödel {script} {
     binary scan $script c* bytes
     set result 0
     foreach b $bytes {
        set result [expr {$result*256+$b}]
     }
     return $result
  }

Mind you, in general Gödel-numbers are very big anyway. IMO, it's easier to work with strings...

See Brute force meets Goedel for Gödel numbers at work :)

FW: I'm probably being overly facetious here, but you can also just use

 proc If {cond then else} {
   set false 1
   while $cond {set false 0; uplevel 1 $then; break}
   while $false {uplevel 1 $else; break}
 }

if while is still available to you. - RS: Sure enough, but the idea was rather to do without any branching control structures - switch could have been used too...

KBK See Combinator engine for how all control structures can be expressed with two functionals:

    K a b = a
    S a b c = a c {b c}

With these in your pocket, you don't need named variables, named functions, [if], [while], ... These operations plus simple arithmetic are Turing complete.

DKF Technically, you don't need simple arithmetic either. You can construct things that behave just like integers (well, something that obeys Peano Arithmetic Axioms) from S and K on their own using things like Church Numerals (I think that's the right name).

KBK Hmmm, I think that I had the Church numerals in the combinator engine page even before I wrote the above; you're perfectly right, of course, that S and K can do arithmetic. Just chalk it up to a "Homer moment." (D'oh!)

What other commands could we get rid of? Tcl in tcl

Arts and crafts of Tcl-Tk programming

Category Concept