Playing Scheme

aspect 2011-05-21: Tcl is an amazing language, capable of radical language modification. Scheme is another such language, with some features in common:

It also has two killer features which I miss dearly when coding Tcl:

These are becoming more popular as the great unwashed discover their benefits through Javascript, Python, Ruby and other "modern" dynamic languages. It saddens me that Tcl is left behind -- I really like closures, and I really like Tcl. Can't they be brought together?

A morning epiphany and a Saturday's coding led me to the following, which adds these features to Tcl, in just a couple of dozen lines, with only minimal impact on existing code.

Side effects:

  • proc now creates variables. This means that procedures are local to the scope where they are defined: you get private inner functions, but self-modifying code require a different pattern.
  • [x y z] is now equivalent to [apply $x [list y z]]], unless a command called x already exists
  • variables with spaces in their names cannot be used as commands

Otherwise, this should co-exist neatly with existing Tcl code. Unless you indulge in braintwisters and have procedures with spaces in their names or use variables which share their names with procedures, no code should break.

The pure-Tcl implementation of closures does not permit garbage collection .. in theory, a C implementation which creates opaque objects could fix this. It could also byte-compile procedure bodies, so there should be no performance penalty.

# scheme in tcl

# this gives us first-class functions, and only breaks code which does either:
#  - uses procedures and variables with the same name
#  - uses procedures (or variables) with spaces in their name
proc unknown {cmd args} {
    if {[llength $cmd] > 1} {
        uplevel 1 [list apply $cmd {*}$args]
    } else {
        upvar 1 $cmd cmdvar
        uplevel 1 [list $cmdvar {*}$args]
    }
}

set lambda {{args body} {list $args $body}}
# now we can dispense with [proc]!
set proc {{name args body} {uplevel 1 [list set $name [list $args $body]]}}

# scheme's (define) for Tcl
set define {{name value} {
    if {[llength $name] > 1} {
        set args [lassign $name name]
        set value [list $args $value]
    }
    uplevel 1 [list set $name $value]
}}

# now we have three equivalent forms for defining procedures that live
# in variables and can be invoked normally:
#   proc foo {args} {body}
#   set foo {{args} body}
#   set foo [lambda {args} body]
#
# Strictly [lambda] is unneccessary (just use [list]), but it makes Schemers feel more at home.


# holder for closed-over variables
namespace eval closed {
    proc K {x args} {set x}
    variable nextsym 0  ;# for gensym
    proc gensym {} {
        variable nextsym
        K $nextsym [incr nextsym]
    }
}

proc closure {vars bvl body} {
    set map {}
    foreach name $vars {
        set sym [::closed::gensym]
        upvar 1 $name var
        # quoting hell:
        # First, try to [upvar] $name into ::closed::$sym.
        # If that fails, it is a proc-local variable and we have to copy its
        # value into ::closed::$sym, then [unset $name] in our caller and
        # replace it with a link using [upvar].
        if [catch [list namespace eval ::closed [list upvar 2 $name $sym]]] {
            namespace eval ::closed [list variable $sym $var]  ;# copy value
            uplevel 1 [list unset $name]
            uplevel 1 [list namespace upvar ::closed $sym $name]     ;# create reference
        }
        lappend map $name $sym
    }
    return [list $bvl [string map [list @MAP@ $map @BODY@ $body] {
        foreach {name closed_name} {@MAP@} {
            upvar #0 ::closed::$closed_name $name
        }
        @BODY@
    }]]
}

# now we can go full circle:
define {lambda bvl body} {closure {} bvl body}

We can take advantage of the new features by implementing objects via closures. Here's an example derived from gadgets:

define {Number {x 0}} {
    ::closure x {args} {
        if {[llength $args] == 0} {
            set x
        } else {
            set args [lassign $args action]
            switch -exact $action {
                + {  incr x [lindex $args 0] }
                - {  incr x -[lindex $args 0] }
                * {  set x [expr {$x*[lindex $args 0]}] }
                / {  set x [expr {$x/[lindex $args 0]}] }
                = {  set x [expr $args] }
                adder {  ::closure x {} {incr x} }
                default {  return -code error "Unsupported action: $action" }
            }
        }
    }
}

set x [Number]
set y [Number 42]
x + 3
y / 2
puts "[x], [y]"   ;# 3, 21
set a [x adder]
set b [y adder]
puts "[a], [a], [a]"  ;# 4, 5, 6
puts "[b], [b], [b]"  ;# 22, 23, 24
puts "[x], [y]"       ;# 6, 24

A few questions remain:

  • does this break any existing functionality that I haven't noticed?
  • do my closures break under any conditions that I haven't picked up on?
  • what considerations are there to getting this into the core? (closure as a native command and type?)
  • can I get this on the TIP track for inclusion in Tcl9?

RLE 2011-05-21: Note, for a different take on gensym that uses some of Tcl's introspection features, the code inside your ::closed:: namespace can be replaced with this:

proc gensym { {val 0} } {
    proc gensym "{val [ incr val ]}" [ info body gensym ]
    return $val
}

Which uses no non-local variables, yet returns an increasing sequence number with each call.

aspect: nice! With my replacement of proc that won't work quite the same now -- you would need to say proc ::gensym. Your example also illustrates that the idiom of self-rewriting code will need significant restructuring to work under this page's redefinition of proc.

RLE 2011-05-21: Ah, yes, that would foobar it a bit. You could alternately do this in your initialization code:

# keep original Tcl "proc" around for some needed uses
rename proc ::tcl::proc

And then the ::closed:: namespace contents could become:

::tcl::proc gensym { {val 0} } {
  ::tcl::proc gensym "{val [ incr val ]}" [ info body gensym ]
  return $val
}

aspect: that would do it, but it takes us futher away from all procedures being first-class functions. I would prefer to preserve this, but to recover the capability for self-modifying code will require some care. Here's a version of gensym that works by closing over itself:

set gensym [closure {gensym} {{i 0}} {
    set gensym [list "{i [incr i]}" [lindex $gensym 1]]
    set i
}]

.. and after a bit of experimenting, a version that works as either an ordinary ::tcl::proc and as a lambda. info body is the only function that needs to be wrapped:

proc my_name {} {lindex [dict get [info frame -2] cmd] 0}

proc info_body {fun} {
    if {[llength $fun]>1} {
        lindex $fun 1
    } else {
        info body $fun
    }
}

proc gensym {{val 0}} {
    set name [my_name]
    uplevel 1 "proc gensym {{val [incr val]}} \[info_body $name]"
    set val
}

puts [gensym]
puts [gensym]
puts [gensym]

Curiosities and connections:

NEM 2011-09-29 You might also enjoy Locally-scoped command aliases are fun!