Lecture overview -- Keyboard shortcut: 'u'  Previous page: Sequential Control -- Keyboard shortcut: 'p'  Next page: Selection Control -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Lecture 3 - Page 15 : 43
Programming Paradigms
Simulation of other Paradigms and Continuations
Jumps in Functional Programs

A tail call in Scheme is like a goto with parameters

[Insight originally observed by Guy Steele]

Imperative

Functional - Scheme

Begin  
  L1: if B1 then goto L2;
      S1;
      if B2 then goto L2;
      S2;
      goto L1;
  L2: S3;
End
-
/* Rewritten - equivalent */
Begin  
  L1: if B1 
      then goto L2;
      else begin
             S1;
             if B2 
             then goto L2;
             else begin
                    S2;
                    goto L1;
                  end
           end
  L2: S3;
End
(letrec ((L1 (lambda ()
                (if B1 
                    (L2)
                    (begin
                      S1
                      (if B2 
                         (L2)
                         (begin 
                            S2
                            (L1)))))))
         (L2 (lambda ()
                S3)))
  (L1))
#include 
#define DUMMY 0

int main(void) {
  int B1 = 1, B2 = 1;
  int S1 = DUMMY, S2 = DUMMY, S3 = DUMMY;
  
  L1: if (B1) goto L2;
      S1;
      if (B2) goto L2;
      S2;
      goto L1;
  L2: S3;
}
Same

Programs with goto. In the Scheme expression, notice that the calls of L2 (twice) and L1 (once) in L1 are all tail calls. Therefore in these calls, there is no need to return to L1 after the simulation of a goto. Consequently, we simple leave L1 when/if L1 or L2 is called.

 

A labelled program part becomes a function

A goto statement becomes a tail call to one of the functions