Thought you all might be interested in this article I wrote.  It 
discusses recursive programming techniques, which is interesting for 
those of you who do non-assembly.  But the assembly part I thought you 
might be interested in was that I have a section in there on how to do 
tail-call optimizations using assembly language.

http://www-128.ibm.com/developerworks/library/l-recurs.html?ca=dnt-624

Enjoy.

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

Jonathan Bartlett wrote:
> Thought you all might be interested in this article I wrote.  It
> discusses recursive programming techniques, which is interesting for
> those of you who do non-assembly.  But the assembly part I thought you
> might be interested in was that I have a section in there on how to do
> tail-call optimizations using assembly language.
>
> http://www-128.ibm.com/developerworks/library/l-recurs.html?ca=dnt-624
>
> Enjoy.
>
> Jon

Hi Jon,

While hacking with the stack is a cool and interesting application
(demonstrating something you can't do in a HLL like C, if the C
compiler's optimizer doesn't do this for you), you're still executing a
lot of extra code in order to be able to do this "clean" implementation
of tail recursion.

A simpler, and more efficient approach, is to simply use a jump
instruction and jump past the stack frame initialization rather than
jumping to the beginning of the function and rebuilding the stack frame
on each tail-recursive call. Of course, you might argue that this is
spaghetti coding and defeats the whole purpose of using tail recursion
(rather than loops) for inductive proof  purposes. However, with a
sufficiently sophisticated macro system, you can create a macro to
overcome the spaghetti mess you get when you use a JMP instruction.
Consider the following HLA code:

program main;
?@noframe := true;    // Turn off HLA's automatic stack
?@nodisplay := true;  // frame generation so we can see all
                      // the actual code used here.

#include( "stdlib.hhf" )

    // Here is a dummy "action" function to pass as a parameter
    // to the "recursive" function that expects a single-parameter
    // procedure as its third parameter. This trivial little
    // procedure simply prints the value of the parameter as
    // an integer.

    procedure toDo( i:uns32 );
    begin toDo;

        push( ebp );
        mov( esp, ebp );
        stdout.put( "toDo: ", i, nl );
        pop( ebp );
        ret( _parms_ );

    end toDo;


    // Here is a macro that is used to automatically generate
    // "tail recursion" code for the "recursive" procedure. Though
    // this particular macro is specific to the "recursive" procedure,
    // it actually wouldn't be that hard to write a macro that
    // automatically generates a macro like this one for any procedure.
    //
    // This macro is used as follows:
    //
    // tail_recursive   -- Everything from this point to the "end_tail"
    //                  -- statement expands "tail_recursive" to a
    //                  -- tail recursive call to recursive.
    //
    //     recursive( a, b, c);         -- actual recursive call
    //     tail_recursive( a, b, c );   -- tail recursive call.
    //      .
    //      .
    //      .
    // end_tail -- Beyond this point, tail_recursive is not defined.


    #macro begin_tail:_recursive_entry_;

        // Upon encountering "begin_tail", emit a label that the
        // tail_recursive invocation will transfer to:

        _recursive_entry_:

        // The following is the "tail_recursive" macro that
        // emits the code to set up the parameters and transfer
        // control back to the beginning of the recursive section.

    #keyword tail_recursive( _initial_, _ending_, _doIt_ );

        // Copy the parameters passed to this macro into
        // the original "recursive" procedure parameters.
        // Because this is a tail recursive call, the original
        // parameter values are now dead and we can simply reuse
        // their memory locations for the new parameter values.
        //
        // Note that this code doesn't emit any code if you pass
        // the original parameters on through to the new call.
        // Yes, HLA will support memory to memory moves, if needed,
        // by subsituting a push/pop sequence for the moves below.

        #if( @string( _initial_ ) <> "initial" )

            mov( _initial_, initial );

        #endif
        #if( @string( _ending_ ) <> "ending" )

            mov( _ending_, ending );

        #endif
        #if( @string( _doIt_ ) <> "doIt" )

            mov( _doIt_, doIt );

        #endif
        jmp _recursive_entry_;  // Transfer control to the beginning
                                // of the tail recursive section.


        // The "end_tail" macro marks the end of the tail recursive
        // section.

    #terminator end_tail;
        // No need to do anything at end of tail recursion section.
    #endmacro





    procedure recursive( initial:uns32; ending:uns32; doIt:procedure(
i:uns32 ));
    begin recursive;

        // Set up the activation record (stack frame):

        push( ebp );
        mov( esp, ebp );
        push( eax );        // Save EAX's value, don't do this
                            // on tail recursive calls, though

        // In the following begin_tail..end_tail sequence, the
        // tail_recursion call uses tail recursion to transfer
        // control back to the "begin_tail" point in the code.

        begin_tail;

            // Here's our "basis" step (using induction terminology).
That is,
            // this handles the one, non-recursive case.

            mov( initial, eax );
            if( eax <= ending ) then

                // Here's the work (doIt) and the tail-recursive call:

                doIt( eax );
                tail_recursive( inc( eax ), ending, doIt );

            endif;

        end_tail;

        pop( eax );
        pop( ebp );
        ret( _parms_ );

    end recursive;


begin main;

    recursive( 1, 10, &toDo );

end main;


For those who don't immediately see what this code does (okay, that's
probably everyone), here's the output:

c:\hla>t
toDo: 1
toDo: 2
toDo: 3
toDo: 4
toDo: 5
toDo: 6
toDo: 7
toDo: 8
toDo: 9
toDo: 10

That is, the "recursive" function is basically a "interator" that
executes the procedure specified by the third parameter for the range
of values specified by the first and second parameters. In this
particular program, the procedure specified by the third parameter
simply prints the current iterator index value. (That is, this simple
example behaves not unlike a simple FOR loop executing from 1 to 10,
printing out the loop index.)


The interesting thing to note is that the begin_tail and end_tail
macros delineate a block of statements that define the scope of the
"tail_recursive" invocation. Whenever a "tail_recursive" invocation
occurs, the code copies the parameter values (if necessary) over the
top of recursive's current parameters and transfers control to the
statement immediately following "tail_recursive" (which you'd generally
put immediately after the code that constructs the activation record).

BTW, here's the MASM code that HLA generates for the "recursive"
procedure, so you can see how the macro expands in this particular
case:

L831_recursive__hla_ proc  near32
           push    ebp
           mov     ebp, esp
           push    eax

L833__0340__recursive_entry____hla_:
           mov     eax, dword ptr [ebp+16] ;/* initial */
           cmp     eax, dword ptr [ebp+12]
           jnbe    L834_false__hla_
           push    eax
           call    dword ptr [ebp+8]   ; doIt
           inc     eax
           mov     dword ptr [ebp+16], eax ;/* initial */
           jmp     L833__0340__recursive_entry____hla_
L834_false__hla_:
           pop     eax
           pop     ebp
           ret     12
xL831_recursive__hla___hla_:
L831_recursive__hla_ endp

As you can see, the code this scheme emits is quite efficient.

Of course, an experienced assembly programmer might argue that coding
the jmp directly is less effort than using this macro scheme, but that
would be missing the point -- spaghetti code is *difficult* to prove
correct. If you can prove that the macro generates correct code (not
hard to do), then it's fairly easy to prove that code using the macro
is correct (at least, "easy" as defined in the article).

In this particular example, the "begin_tail" macro has been written
specifically for the "recursive" procedure and does not immediately
generalize for use by other procedures (largely because of the way it
handles exactly three parameters). It would be relatively easy for an
advanced HLA user to create a macro that you use to generate procedure
declarations that automatically create such a macro for those
procedures.
Cheers,
Randy Hyde

Very nice, indeed!

My option was dedicated specifically to showing how tail-call
elimination can work generically within the C calling convention, but
that is an awesome example of doing tail-recursion *the-right-way* (tm)
in assembly language.

I'll have to keep that around for future reference!

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

One of the thing I found reasonably easy to do was to set up a
recursion depth indicator and in the context where I used it, tere was
no performance penalty from doing so. A recursive Quick Sort is a very
standard use of recursion and if you can get the pivot code efficient
enough, it does not need the small count additional sort like an
insertion sort or bubble sort or similar.

The win with a recursion depth indicator if you are interested in
saving the time collapsing back through a large count of stack frames
is that you can calculate the stack correction based on the count
multiplied by the byte count of parameters and locals used in the
procedure.

I tend to see recursion as useful where the algo and the data
dynamically construct a tree so the recursion depth is changing on a
regular basis depending on the ordering of the data but I have also
seen recursive algos that are better suited as iterative algos where
you save the stack overhead and don't have the problem to start with.

Compliments to both Jon on his article and Randy for the technique he
has published here.

Regards,

hutch at movsd dot com

Here is another neat thing you can do directly in assembly. This
corresponds to iterators and somewhat corresponds to "continuations" as
mentioned in the article.

The following program is an example of an "iterator" in assembly
language. Two versions are provided: the standard HLA iterator (which
does some code generation behind your back) and and "pure assembly"
version of the iterator.

The sample iterators I've provide generate a sequence of values in the
range m..n (m<=n) on each iteration of the loop. They return the
current "loop iteration value" in the EAX register. Of course, using
iterators for such a trival loop control is rather silly, but this
example does not diminish the power of an iterator. Iterators are fully
recursive (the tie-in to this thread), so you can easily use them to
iterate through all the nodes of a tree or other graph that you would
normally process in a recursive fashion. Because iterators are
recursive (being functions), the whole concept of proof of correction
by induction applies (assuming, of course, that you write the code in
an appropriate fashion, the following examples are not so written).
Cheers,
Randy Hyde

program main;
//?@noframe := true;
?@nodisplay := true;
?@nostackalign := true;

#include( "stdlib.hhf" )


// range iterator-
//
// Repeats the body of the corresponding foreach loop start..stop
// times (start <= stop). Currents current "loop index value" in
// the EAX register.

iterator range( start:int32; stop:int32 );
begin range;

    mov( start, eax );
    while( eax <= stop ) do

        // The "Yield" function (actually, it's technically
        // called a "thunk") calls the body of the foreach
        // loop in the caller's code:

        yield();

        // Increment the value that the iterator
        // returns on each yield (could do this
        // using "tail recursion", but this scheme
        // is probably easier to read by most
        // people):

        inc( start );
        mov( start, eax );

    endwhile;

end range;


// Okay, you're not using HLA and you don't have
// the ability to write "iterators". How can you
// write an iterator in "pure assembly?"  No sweat.
// The following iterator is the same as the above,
// but written in "pure" assembly:

procedure range2( start:int32; stop:int32; terminalAdrs:dword );
@noframe;
begin range2;

    push( ebp );
    mov( esp, ebp );
    mov( start, eax );
    jmp continueWhile;
    whileLoop:

        // Yield:

        push( (type dword [ebp]) );
        call( (type dword [ebp+4]) );

        inc( start );
        mov( start, eax );

    continueWhile:
        cmp( eax, stop );
        jle whileLoop;

    mov( ebp, esp );
    pop( ebp );

    // Iterators have two return address. The
    // standard 80x86 return address points at
    // the loop body, and the second return
    // address points beyond the loop. The
    // following add removes the loop body return
    // address from the stack so we can return
    // via the second return address.

    add( 4, esp );
    ret( _parms_ );

end range2;


begin main;


    stdout.put( "Range:" nl );
    foreach range( 1, 10 ) do

        stdout.puti32( eax );
        stdout.newln();

    endfor;

    // Same loop as above, but written in "pure" assembly:

    stdout.put( "Range2:" nl );

    // Pass parameters to the range2 iterator on the stack:

    pushd( 1 );
    pushd( 10 );
    pushd( &exitFor );  // 2nd return address, points beyond
    call range2;        // the foreach loop.

    // Loop Body:

    push( ebp );            // Save iterator's EBP and
    mov( [esp+8], ebp );    // restore our EBP (always at
                            // [esp+8]),

    stdout.puti32( eax );
    stdout.newln();

    pop( ebp );     // Restore iterator's ebp value

    // The follwing is the end of the loop, rather than
    // jumping to the beginning of the loop (as we would
    // in a traditional loop), we *return* back to the
    // iterator, transferring control to just beyond the
    // YIELD "thunk" invocation.

    ret(4);         // Returns back to iterator code.'

  // Here's where the iterator returns when the loop
  // termination condition occurs:

  exitFor:

end main;


Output from the program:

Range:
1
2
3
4
5
6
7
8
9
10
Range2:
1
2
3
4
5
6
7
8
9
10