* 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.

<<categories>> Tutorial