EXAMPLE

The following program computes the Mandelbrot set by determining the number of iterations of the function required to send each point in a given region of the complex plane to a point outside the circle of radius 2:

-- Computation engine for the X mandelbrot program.
#include "aslib.as"

-- Macros
I  ==> SingleInteger
F  ==> DoubleFloat
CF ==> Complex DoubleFloat

maxIters: I == 100

import from CF -- Make operations from CF visible.
inline from CF -- Give optimizer permission to depend on CF.

default ar, br, ai, bi: F
default nr, ni: I

++ Draw the Mandelbrot set in the given region.
++ The pixel drawing function is passed as a parameter.

drawMand(ar,br,nr, ai,bi,ni, draw: (I,I,I,I)->I): () ==

   mandel(c: CF): I ==
      z: CF := 0
      n: I  := 0
      for it in 1..maxIters while norm z < 4.0 repeat
         z := z*z + c
         n := it
      n

   for i in step(ni)(ai,bi) for ic in 0..ni-1 repeat
      for r in step(nr)(ar,br) for rc in 0..nr-1 repeat
         nit := mandel complex(r, i)
         draw(rc, ic, maxIters, nit)

The function drawMand illustrates several interesting features of the language: domains (the DoubleFloat argument to Complex) and functional closures (the draw parameter to drawMand) as first-class objects, domains parameterized over other domains (Complex(DoubleFloat)), cross-file inlining, inlining of functions from parameterized domains, and iteration using generator functions (step(ni)(ai,bi)) These features are described in more detail in [24].

The non-optimized intermediate Foam code generated from the above program illustrates the character of the abstract machine. The code fragment shown below is produced from the inner loop which steps the variables SPMquotr" and SPMquotrc" in parallel.

(Label 2)
(Set (Loc 10 r) (CCall Word (Loc 13)))
(If (EElt 4 (Loc 12) 0 0 done) 3)
(Set (Loc 9 rc) (CCall Word (Loc 16)))
(If (EElt 4 (Loc 15) 0 0 done) 3)
(Set (Loc 0 nit)
     (OCall Word (Const 2 mandel) (Env 0)
            (CCall Word (Lex 1 18 complex)
                   (Loc 10 r) (Loc 2 i))))
(CCall Word (Par 6 draw) (Loc 9 rc) (Loc 1 ic)
       (Lex 1 1 maxIters) (Loc 0 nit))
(Goto 2)

A few words might make this code less cryptic. The instructions SPMquotPar" and SPMquotLoc" refer to the current function's parameters and temporary variables. They are annotated with the name from the user-level program, when there is one. The SPMquotLex" instruction refers to variables in the lexical environment of the current function. SPMquotEElt" refers to variables in other lexical environments. The SPMquotOCall" and SPMquotCCall" instructions call programs as function-environment pairs or closures respectively. The first parameter in SPMquotOCall" and SPMquotCCall" special form is the Foam type of the return value. The second argument to the SPMquotIf" instruction is a branch label.

The optimized Foam code demonstrates the level of efficiency which can be realized by programs written in :

(If (Loc 33 done) 39)
(Set (Loc 35 f0) (DFlo 4.000000e+00))
(Set (Loc 38 f0) (BCall DFloTimes (Loc 57 f0) (Loc 57 f0)))
(Set (Loc 39 f0) (BCall DFloTimes (Loc 58 f0) (Loc 58 f0)))
(Set (Loc 40 f0) (BCall DFloPlus (Loc 38 f0) (Loc 39 f0)))
(If (Cast Word (BCall DFloLE (Loc 35 f0) (Loc 40 f0))) 39)
(Set (Loc 41 f0) (BCall DFloTimes (Loc 57 f0) (Loc 57 f0)))
(Set (Loc 42 f0) (BCall DFloTimes (Loc 58 f0) (Loc 58 f0)))
(Set (Loc 55 f0) (BCall DFloMinus (Loc 41 f0) (Loc 42 f0)))
(Set (Loc 43 f0) (BCall DFloTimes (Loc 57 f0) (Loc 58 f0)))
(Set (Loc 44 f0) (BCall DFloTimes (Loc 58 f0) (Loc 57 f0)))
(Set (Loc 56 f0) (BCall DFloPlus (Loc 43 f0) (Loc 44 f0)))
(Set (Loc 57 f0) (BCall DFloPlus (Loc 55 f0) (Loc 52 f0)))
(Set (Loc 58 f0) (BCall DFloPlus (Loc 56 f0) (Loc 48 f0)))
(Set (Loc 9) (Loc 11))
(Goto 38)
(Label 39)
(Set (Loc 0 nit) (Loc 9))
(CCall Word (Par 6 draw) (Loc 2 rc) (Loc 1 ic)
       (Lex 1 1 maxIters) (Loc 0 nit))
(Goto 2)

The above code fragment is the body of the same loop, after functions (e.g. SPMquotmandel") have been inlined and non-escaping record values (e.g. complex numbers) have been replaced by collections of temporaries.

As might be expected, the concrete C code generated by the back-end of the compiler closely parallels the optimized Foam code:

        if (T33_done) goto L39;
        T35_f0 = 4.000000e+00;
        T38_f0 = T57_f0*T57_f0;
        T39_f0 = T58_f0*T58_f0;
        T40_f0 = T38_f0 + T39_f0;
        if ((FiWord) (T35_f0 <= T40_f0)) goto L39;
        T41_f0 = T57_f0*T57_f0;
        T42_f0 = T58_f0*T58_f0;
        T55_f0 = T41_f0 - T42_f0;
        T43_f0 = T57_f0*T58_f0;
        T44_f0 = T58_f0*T57_f0;
        T56_f0 = T43_f0 + T44_f0;
        T57_f0 = T55_f0 + T52_f0;
        T58_f0 = T56_f0 + T48_f0;
        T9 = T11;
        goto L38;
L39:    T0_nit = T9;
        fiCCall4(FiWord, P6_draw, T2_rc, T1_ic,
                 l1->X1_maxIters, T0_nit);
        goto L2;

Each identifier is starts with a letter to indicate its kind (e.g., T: local, P: parameter, X: lexical, etc.) and is enumerated to handle name overloading. The statement fiCCall4 is a macro to call a functional closure which takes four arguments. It takes the function return type, then the closure value, followed by the four function parameters.

The corresponding Lisp code is similar and is omitted for brevity. Macros are used for the various primitive operations to allow the Lisp compiler to generate better code. For example, the multiplications in this example would be generated as calls to ``DFloTimes,'' which is defined for Common Lisp as

(defmacro |DFloTimes| (x y)
   `(the |DFlo| (* (the |DFlo| ,x) (the |DFlo| ,y))))

and SPMquotDFlo" is defined using SPMquotdeftype".