* Section 0 - Sugar

• Section 1 - Sugar command macros
• Section 2 - Sugar syntax macros
• Section 3 - Sugar transformers (what you are reading)

Tail call optimization

We saw two kind of macros: command macros, and syntax macros. They actually are the same thing, just the second type can be registered to be called with any command name.

This kind of macros are already quite powerful, but their environment is limited to commands. To perform more complex works we need a more general source transformation tool, that can see a whole script at once, process it, and return a new one.

In Sugar this kind of macros, are called transformer macros, and are exported to the user in two different ways: the first is an API with just two commands:

• sugar::scriptToList - translates the text of a script into a Tcl list representation of this script.
• sugar::listToScript - translates a list representation of a script, in the script text.

There are other procedures that helps to work with the script in its list representation, but the core are this two commands. Using this API the programmer may create new versions of proc that are able to do some kind of transformation, to create more complex static checkers, optimizations, and many other tasks about analysis and transformation of source code.

The second way to use transformers, is to register a transformer macro with the sugar::transformermacr command. It's very similar to a syntax macro, that instead to be called for every command processed, is called for every script. We will see transformer macros in the next section, for now we will see how to directly use the API to write custom versions of proc.

To show transformers we will develop a new version of proc, called [tailrec_proc], able to translate normal Tcl code that contains tail recursive calls, in a semantically equivalent script that runs with a different space complexity (and actually even a bit faster).

To write transformers is exactly like to write macros, we need before to figure how to do the transformation, so the first question is if it's possible to find an algorithm to automatically find and translate tail recursive calls in Tcl code.

I guess that if you are still reading this document, you perfectly know what tail recursion is, but it's better to go incremetally to be more clear. We start writing a recursive call that counts from N to 0.

 proc counter n {
    puts $n
    if {$n} {
        counter [expr {$n-1}]
    }
 }

[counter 3] will output 3 2 1 0, and so on. The procedure has a recursive tail call at the end of the if block. as you can see, the [counter $n] call is the last call that will be executed in the procedure. This means that the procedure is semantically equivalent to this (with an immagination effort, I'll use goto in Tcl):

 proc counter n {
    start:
    puts $n
    if {$n} {
        set n [expr {$n-1}]
        goto start
    }
 }

Because Tcl does not have goto, is it still possible to jump at the start of the procedure to reiterate in some way? It is, using while, we can write a (this time valid) Tcl procedure with the tail call optimized away:

 proc counter n {
    while 1 {
        puts $n
        if {$n} {
            set n [expr {$n-1}]
            continue
        }
        break ; # note the final break
    }
 }

Now that the while 1 is sorrounding the procedure code, we can use continue to jump at the start of the procedure. And it will work inside conditionals: we at least need to ensure that tail calls will be optimized inside if branches, as nested as the programmer like, if there are tail recursive call inside.

There is another problem, as we did with the 'n' variable in the previous example, we need to setup the formal arguments of the procedure to the right value before to call continue and jump at the start. The basic work to do is to set every parameter to the value passed at it's position in the tail call, so if the recursive tail call of a procedure foobar accepting {x y z} as arguments is called with A B C, like in:

  foobar A B C

We will translate it to:

  set x A
  set y B
  set z C
  continue

Actually, it's not enough. The following is the recursive GCD algorithm:

 proc gcd {a b} {
    if {$b == 0} {
        return $a
    } else {
        gcd $b [expr {$a%$b}]
    }
 }

According to the previous rule, we may translate the recursive call to:

  set a $b
  set b [expr {$a%$b}]
  continue

But this will not work, because $a gets replaced with $b before expr can compute $a%$b. To avoid this problem, we need to use some temp variable, and translate the script in this way:

  set __t0 $b
  set __t1 [expr {$a%$b}]
  set a $__t0
  set b $__t1
  continue

Note that the creation of variables before a tail call is unlikely to create collision problems because even if the procedure were using a __t0 variable, it's value is no longer useful, but still in the real implementation you may want to call the temp variables __tailcall__t0 or something like this.

Finally we know how our transformation will look like:

• take the procedure body (fake step.. ;)
• recursively search for tail calls at "top level" and inside conditionals.
• translate every call as commands to set formal parameters and then call continue
• add a 'break' command at the end of the code
• use it as while 1 script argument

And we are done. It's as simple as a nightmare to do without a macro system capable to translate the script in a simple to process form, and then back again to a script, that's why Sugar provides this API.

Now you may wonder what's this easy to process form that is returned by sugar::scriptToList. Actually it is a list (representing the whole script) of lists (representing every command), where every element of a command is represented by a two-elements list, the first element being the type, and the second the value. The following types are possible:

 SPACE - a valid argument separator in a Tcl script, like " ", or "\t".
 TOK   - a valid argument in a Tcl script, that can be just a string, or a command or variable substitution form, or any mix of they.
 EOL   - a valid command separator in a Tcl script, like "\n", or ";".

Spaces are reported varbatim, so a transformer is able to process the script without to mess with the identation. Commands may be empty, with just an element of type EOL. This happens when there are newlines or ";" between differnet commands:

 # like this
 puts foo

 puts bar ; ; ; puts foobar

This means that a transformer is able to create semantic from spaces in extreme cases, like in a transformer that simulates the Python way to create blocks of code.

That's an example of output of sugar::scriptToList. For the following code:

 {
    puts [string length $foo]
    puts $foo$bar
    if {$j} {
        command arg arg
    }
 }

the equivalent translation to a list is:

 {EOL {
 }}
 {SPACE {    }} {TOK puts} {SPACE { }} {TOK {[string length $foo]}} {EOL {
 }}
 {SPACE {    }} {TOK puts} {SPACE { }} {TOK {$foo$bar}} {EOL {
 }}
 {SPACE {    }} {TOK if} {SPACE { }} {TOK {{$j}}} {SPACE { }} {TOK {{
         command arg arg
     }}} {EOL {
 }}
 {EOL {}}

The API guarantees that the opposite transformation from list to a script is performed by mere concatenation of all the tokens, so "types" are information only useful for the transformer, but not for sugar::listToScript.

There is an important thing to note in the example output. The code of if is not automagically converted to a list. This is intentional, because if you want to, you can call again scriptToList against it, or better use a normal registered transformer macro instead to use the API directly. It depends on your transformation, sometimes it's better to have only the first level, and recusively transform to scripts only the wanted parts. When instead we want to do some processing in every part of the Tcl program that is a script, we register a transformer macro, that like command and syntax macros are automatically called against arguments that are known to be scripts (thanks to the macros we already shown).

(Note: there is a middle point between this two extremes: the programmer may want to perform a transformation that's not global to the whole Tcl program, so doesn't want to register a transformer macro but to use the low level API, but for the spirit of the transformation it can be useful to call it recursively in all the tokens that are scripts. Actually it's possible to register a transformer macro, then call sugar::expand $myscript, and then unregister the macro, but I'll experiment with other ways as well in the future. Another solution is to add some redundant code inside the transformer that checks if the command name is while/if/for/switch/ .... and so on, or write a function that is able to automatically recognize such commands)

In the case of our transformer for tail recursive procedures the low-level API is just fine.

Now we are ready to show the actual [tailrec_proc] implementation:

 proc tailrec_proc {name arglist body} {
    # Convert the script into a Tcl list
    set l [sugar::scriptToList $body]
    # Convert tail calls
    set l [tailrec_convert_calls $name $arglist $l]
    # Add the final break
    lappend l [list {TOK break} {EOL "\n"}]
    # Convert it back to script
    set body [sugar::listToScript $l]
    # Add the surrounding while 1
    set body "while 1 {$body}"
    # Call [proc]
    uplevel proc [list $name $arglist $body]
 }

 # Convert tail calls. Helper for tailrec_proc.
 # Recursively call itself on [if] script arguments.
 proc tailrec_convert_calls {name arglist code} {
    # Search the last non-null command.
    set lastidx -1
    for {set j 0} {$j < [llength $code]} {incr j} {
        set cmd [lindex $code $j]
        if {[sugar::indexbytype $cmd TOK 0] != -1} {
            set lastidx $j
            set cmdidx [sugar::indexbytype $cmd TOK 0]
        }
    }
    if {$lastidx == -1} {
        return $code
    }
    set cmd [lindex $code $lastidx]
    set cmdname [lindex $cmd $cmdidx 1]
    if {$cmdname eq $name} {
        set c 0
        set recargs [lrange [sugar::tokens $cmd] 1 end]
        foreach v $recargs {
            set t [list [list TOK set] [list SPACE " "] \
                        [list TOK __t$c] [list SPACE " "]\
                        [list TOK $v] [list SPACE " "]\
                        [list EOL "\n"]]
            set code [linsert $code $lastidx $t]
            incr c
            incr lastidx
        }
        set c 0
        foreach a $arglist {
            set a [lindex $a 0]
            set t [list [list TOK set] [list SPACE " "] \
                        [list TOK $a] [list SPACE " "]\
                        [list TOK \$__t$c] [list SPACE " "]\
                        [list EOL "\n"]]
            set code [linsert $code $lastidx $t]
            incr c
            incr lastidx
        }
        lset code $lastidx [list [list TOK continue] [list EOL "\n"]]
    } elseif {$cmdname eq {if}} {
        for {set j 0} {$j < [llength $cmd]} {incr j} {
            if {[lindex $cmd $j 0] ne {TOK}} continue 
            switch -- [lindex $cmd $j 1] {
                if - elseif {
                    incr j 2
                }
                else {
                    incr j 1
                }
                default {
                    set script [lindex $code $lastidx $j 1]
                    set scriptcode [sugar::scriptToList [lindex $script 0]]
                    set converted [tailrec_convert_calls $name $arglist $scriptcode]
                    lset code $lastidx $j 1 [list [sugar::listToScript $converted]]
                }
            }
        }
    }
    return $code
 }

Well.. I wrote a lot, to show this, but actually is very simple as you can see. Usually transformers have to deal with a particular construct, and use recursion to deal with nested levels.

This transformer uses sugar::token command, it's very simple, just it takes a list representing a command and returns only the values of the elements of type TOK as a list.

With this list as input:

 {SPACE {    }} {TOK puts} {SPACE { }} {TOK {[string length $foo]}} {EOL {}}

It returns this list:

 puts {[string length $foo]}

It's just a facility to have access to the meaningful parts of the command in a simple way.

That's a more complex example of what the macro does. Writing the following ackermann function implementation:

 tailrec_proc ack {m n} {
    if {$m == 0} {
        return [expr {$n + 1}]
    } elseif {$n == 0} {
        ack [expr {$m - 1}] 1
    } else {
        ack [expr {$m - 1}] [ack $m [expr {$n - 1}]]
    }
 }

The procedure body is translated to:

 while 1 {
     if {$m == 0} {
         return [expr {$n + 1}]
     } elseif {$n == 0} {
 set __t0 [expr {$m - 1}]
 set __t1 1
 set m $__t0
 set n $__t1
 continue
     } else {
 set __t0 [expr {$m - 1}]
 set __t1 [ack $m [expr {$n - 1}]]
 set m $__t0
 set n $__t1
 continue
     }
 break
 }

Of the three calls to [ack], only one is left (the only that is not tail-recursive).

Note that it's possible to extend the macro to optimize recursive tail calls inside switch, but actually if is the thing that's really needed to write most tail recursive functions. Other two examples of tail calls:

 tailrec_proc dohanoi {n to from using} {
    if {$n > 0} {
        dohanoi [expr {$n-1}] $using $from $to
        moveit $from $to
        dohanoi [expr {$n-1}] $to $using $from
    }
 }

and

 tailrec_proc show_list l {
    if {[llength $l]} {
        puts [lindex $l 0]
        show_list [lrange $l 1 end]
    }
 }

The programmer should care to don't use return, because the macro for semplicity does not check for "return [call ...]": with tail recursive calls return is always not need.

4) Transformer macros allows to implement features that may otherwise require changes to the compiler itself. It's possible, for example, to translate a program in one semantically equivalent, but with different space complexity.

if with C-like block indentation

While it's quite ideal to build a specialized version of proc, the API from transformer should not be called to perform general transformations in the whole source code at all levels. Instead, it's possible to register a transformer macro with this API:

 sugar::transformermacro foobar list {
    ... do something with the list representation of the script ...
    return $list
 }

The transformer macro will be called for every part of the script that is recognized as a script, and is re-called after other macro expansions (actually all the macros are guaranteed to be called in turn until there is something to expand, so you don't have to care about the registered order, at the same time you *can't* write different macros conceived to run at a given order, the behaviour of every macro must be self-contained).

The following is an example of a simple transformer macro that translates occurrences of if indented with a newline before the expression and the body:

 if {$test}
 {
     set a [+ 1 2]; # Of course, + can be a simple command macro.
 }

The above code will be translated to:

 if {$test} \
 {
     set a ....
 }

It's a very *bad* example of what you can do with transfomers :) The macro doesn't implement support for elseif/else and so on, but it's trivial to add. That's the implementation:

 sugar::transformermacro sillyindentation list {
    for {set i 0} {$i < [llength $list]} {incr i} {
        set tokens [::sugar::tokens [lindex $list $i]]
        if {[llength $tokens] == 2 && [lindex $tokens 0] eq {if}} {
            set nexttokens [::sugar::tokens [lindex $list [expr {$i+1}]]]
            if {[llength $nexttokens] == 1 && [string index [lindex $nexttokens 0] 0] eq "\{"} {
                lset list $i end 1 " "
            }
        }
    }
    return $list
 }

That's all for now. Positive and negative feedbacks are welcomed.

---