Scheme does not specify the order in which the arguments of a procedure call are evaluated. Most Scheme compilers, including Twobit, use parallel assignment optimization to find an efficient order of evaluation for each call.
Consider, for example, the internal definition
(define .loop_3 (lambda (.f_2 .l_5 .x_5) (if (pair? .l_5) (.loop_3 .f_2 (cdr .l_5) (cons (.f_2 (car .l_5)) .x_5)) .x_5)))
are symbolic names for registers
which are the first three registers used to pass arguments.
To evaluate the arguments for the tail-recursive call to
.loop_3, the compiler must therefore
achieve the effect of performing the following assignment
statements in parallel:
REG1 := REG1 REG2 := (cdr REG2) REG3 := (cons (REG1 (car REG2)) REG3)
On a sequential machine, the effect of this parallel assignment can be achieved most efficiently by performing the third assignment first, followed by the second assignment. The first assignment does not need to be performed at all.
Twobit performs parallel assignment optimization by
constructing the dependency graph for the parallel
<= to mean "depends on",
the dependency graph for the example above is
REG1 <= REG1 REG2 <= REG2 REG3 <= REG1, REG2, REG3
Twobit then attempts a topological sort of the dependency graph. If a topological sort can be found, then it represents an order of evaluation that will evaluate each argument expression directly into its target register.
Parallel assignment optimization reduces the size of the Scheme standard library by about 6%.