[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]
----
See also [If we had no proc] - [If we had no variables]
----
[Arts and crafts of Tcl-Tk programming] [Category Concept]