17.10.6 The SCC transformation algorithm

The SCC algorithm builds a directed graph representation of the bindings in a single recbind or rec*bind structure, outlining the dependencies among right–hand side expressions; in the graph each binding is a vertex (also called node). It then applies Tarjan’s algorithm to the graph and partitions the bindings into clusters of Strongly Connected Components (SCC).

Here is the gist of the algorithm:

1. Given the core language letrec form:

   (letrec ((D (lambda () B))
            (C D)
            (B C)
            (A B))
     ?body)
   

   we build a directed graph of dependencies between the bindings; the graph of dependencies for the given form is:

   A --> B --> C
         ^     |
         |     |
         D <---
   

2. We perform a depth–first visit of the directed graph; during the visit we step from the current vertex to a successor one, following an outgoing edge, if it has not already been visited; a depth–first visit is like entering a maze and always turn right at cross roads. While visiting the vertexes: we push each visited vertex on a stack; we rank each vertex with a zero–based serial index.

   The following picture shows an ongoing visit with path ‘A’, ‘B’, ‘C’, ‘D’; the serial index of each vertex is in square brackets:

   A[0] --> B[1] --> C[2]     STK == A, B, C, D
              ^       |
              .       |
              .       |
            D[3] <----
   

   let’s say we are visiting ‘D’ and considering the successor vertex ‘B’ as next step.

   1. ‘B’ has already been visited, so we do not enter it; the index of ‘B’ is ‘1’, less than the index of ‘D’ which is ‘3’, so we mutate the index of ‘D’ to be ‘1’:

      A[0] --> B[1] --> C[2]     STK == A, B, C, D
                 ^        |
                 .        |
                 .        |
               D[1] <-----
      

      there are no more successor vertexes from ‘D’ so we step back to ‘C’; notice that we leave the stack unchanged.

   2. Upon stepping back to ‘C’: we recognise that the index of ‘C’ is ‘2’, less than the index of ‘D’ which is ‘1’; so we mutate the index of ‘C’ to be ‘1’:

      A[0] --> B[1] --> C[1]     STK == A, B, C, D
                 ^        .
                 .        .
                 .        .
               D[1] <.....
      

      there are no more successor vertexes from ‘C’ so we step back to ‘B’; notice that we leave the stack unchanged.

   3. Upon stepping back to ‘B’: we recognise that the index of ‘B’ is ‘1’, greater than or equal to the index of ‘C’ which is ‘1’; we leave the index of ‘B’ unchanged. Now we recognise that: after visiting all the vertexes successors to ‘B’, the index of ‘B’ is unchanged; we conclude that all the nodes on the stack up to and including ‘B’ are part of a Strongly Connected Component:

      STK == A, B, C, D
               |-------| SCC
      

      so we pop them from the stack and form a cluster with them. The vertexes in a cluster are marked as “done” and will be skipped in further steps of the visit, as if they are not there.

3. Clusters of SCCs are formed and accumulated while stepping back from the depth–first visit, the accumulated clusters are in reverse order. This implementation of Tarjan’s algorithm guarantees that the returned list of clusters is in the correct order for RHS evaluation in recbind or rec*bind structs:
   • The RHS of bindings in the first cluster from the list, must be evaluated before the RHS of bindings in the second cluster.
   • The RHS of bindings in the second cluster from the list, must be evaluated before the RHS of bindings in the third cluster.
   • And so on.

   So we can arrange the evaluation as if each cluster comes from a nested binding form; if the returned list is:

   ((?cluster-binding-1 ...)
    (?cluster-binding-2 ...)
    (?cluster-binding-3 ...))
   

   the equivalent nested binding forms are:

   (recbind (?cluster-binding-3 ...)
     (recbind (?cluster-binding-2 ...)
       (recbind (?cluster-binding-1 ...)
         ?body)))
   

4. Each cluster of SCCs generates a nested hierarchy of bindings; first the bindings are partitioned into fixable and non–fixable, the a form like the following is generated:

   (bind ((?complex.lhs '#!void) ...)
     (fix ((?fixable.lhs ?fixable.rhs) ...)
       (assign ?complex.lhs ?complex.rhs) ...
       ?body))