Debugging GNU Guile

The following schematic shows the compilation phases in GNU Guile:

One can compile from any host language to any target language using the compile procedure: For example we may compile Scheme to the CPS intermediate language:

(compile '(car (list 1 2 3)) #:from 'scheme #:to 'cps)

#<intmap 0-4>

The compile procedure will use the associated reader procedure for the source language specified. The result, an intmap, will be explained later in the CPS section.

Here is the list of Tree-IL records (documented in the Guile manual's section on CPS in Guile). The first field of every record is always for the source metadata and is not shown, with the exception of <lambda-case>, <prompt>, and <abort> which do not have such a field, and <letrec> which has it as the second field.

As you can see, the Tree-IL language is small.¹ A lot of functionality is performed by <primcall>, which refers to primitive procedures that are provided by Guile. Once the Tree-IL has been generated and optimized, it is converted into CPS by the (language tree-il compile-cps) module.

At this point one may reasonably ask how Tree-IL terms are created (remember how we mentioned serialization earlier?) You'd need to know this information to write your own compiler targeting Tree-IL. Guile offers parse-tree-il from (language tree-il) for this purpose:

(use-modules (language tree-il))
(let ((x 2))
  (parse-tree-il `(call (toplevel +) (const 1) (const ,x))))

#<tree-il (call (toplevel +) (const 1) (const 2))>

Thus one builds a symbolic s-expression and converts it to Tree-IL with parse-tree-il.

What is CPS? This quote gives a good hint:

A programmer can discover continuation-passing style by themselves if subjected to one constraint:

No procedure is allowed to return to its caller—ever.

One hint makes programming in this style possible:

Procedures can take a callback to invoke upon their return value. —Matt Might, By example: Continuation-passing style in JavaScript

In short, every procedure takes an extra argument, which it uses to return its computed value. Here's an example in Python of what this style would look like:

def func(x, y, z, ret):
  ret(x + y*z)

The above is a only a hint as to what CPS is. There are two aspects to CPS:

1. The call/cc facility (e.g. what Scheme offers) as a programming technique.
2. The formal language, as a compiler technique.

I have spent some time studying the first point and I came to the conclusion that I did not need call/cc; it seemed like a smart goto facility that I could not come up with uses for. It took me many years to realize that there is a deeper aspect to CPS, which is what the second point expresses. Not only it is deeper, but it felt much more interesting to study: theoretically, I was on much firmer ground as CPS is a variation of lambda calculus, a very familiar topic, and practically, the CPS language manifests as an intermediate language in the compiler tower of GNU Guile.²

This content is taken from How to compile with continuations.

Consider the grammar of lambda calculus:

<expr> ⩴ (λ (<var>) <expr>)
       │ <var>
       │ (<expr> <expr>)

(Note that we write terms in lisp syntax, i.e. we write (λ (x) f) instead of λx.f.) The lambda calculus language is transformed into the CPS language (similarly written in lisp syntax):

<aexp> ⩴ (λ (<var>*) <cexp>)
       │ <var>
<cexp> ⩴ (<aexp>+)

Observe that these are almost the same, barring that <cexp> (complex expressions) can have a variable number of <aexp> (atomic expressions) unlike lambda application, and atomic expessions can have any number of variables, unlike lambda functions. However it is exactly this property of functions having multiple variables and being applied multiple values that allows us to define CPS-style, as we will use one additional argument for the continuation!

Now let's take a look at CPS in Guile. Let's compile some simple source code:

(define im (compile '(let ((x 36)) (+ x 6)) #:to 'cps))
im

#<intmap 0-4>

As a result we get an intmap, a record defined in (language cps intmap). Intmaps are hashmaps with integer keys. We can convert the intmap into an assoc list if we'd like:

<<intmap-def>>
(use-modules (language cps intmap)
             (ice-9 pretty-print))
(define al (intmap-fold-right acons im '()))
(pretty-print al)

((0 . #<cps (kfun () 0 1 4)>)
 (1 . #<cps (ktail)>)
 (2 . #<cps (kargs (val) (1) (continue 1 (values 1)))>)
 (3 . #<cps (kargs () () (continue 2 (const 42)))>)
 (4 . #<cps (kclause (() () #f () #f) 3)>))

Don't be fooled by the #<cps> type! It's not a real type, it's just how the different CPS records from the (language cps) module, such as $kfun, $ktail, $kargs and $kclause, are printed (see the manual's CPS in Guile section for all the records). It is worthwhile familiarizing yourself with how this printer works, because it does not simply list all the record fields; you may also write your own examination facilities if you'd like.

The output above is not to be read from top to bottom like a regular program. Instead, starting at 0, we must follow the continuation labels every time we wish to discover the next operation to be performed.

It is important to understand that there are two sets of indices: continuation labels (the keys of the intmap) and variable labels (also integers). It is possible to have a continuation and a variable share the same numeric label; they are kept distinct by context.

The zeroth record is the entry, so let us start examining from there. (Note that the #<cps> printer, like the #<tree-il> printer, does not print the src parameter.)

1. The self label is 0, the tail label is 1 and the clause label is 4. The tail label is where this $kfun finishes; the entry in 1 is a $ktail, which designates termination. The clause label is points to the invocation of a procedure; it points to 4.
2. The entry indexed by 4 is a $kclause which is the invocation of a procedure, here called as a thunk.
3. The procedure called is indexed by 3. The $kargs binds names to values, but here there's nothing, and then passes to the next continuation the value 42 (here the constants 36 and 6 have been folded into 42 and the addition operation has been eliminated).
4. The procedure indexed by 2 has been assigned to its val variable the value 42. The val variable is indexed by 1. In its body, it returns the value of the variable indexed by 1, i.e. val, to the continuation indexed by 1.
5. That continuation indexed by 1 is the return of the kfun entry, and thus the compiled program returns the value 42.

Consider the function

(define (add-simple x) (+ x 42))

The disassembly³ yields:

Disassembly of #<procedure add-simple (x)> at #x55eabd867298:

   0    (instrument-entry 76)                                 at (unknown file):12:0
   2    (assert-nargs-ee/locals 2 0)    ;; 2 slots (1 arg)
   3    (call-scm<-scm-uimm 1 0 42 1)   ;; add/immediate      at (unknown file):12:14
   5    (reset-frame 1)                 ;; 1 slot
   6    (handle-interrupts)
   7    (return-values)

Consider the procedure:

(define (string-ref-0 s) (string-ref s 0))

Let's examine it under the three different compilation options, -Ocps, -Oresolve-primitives, and when they're specified together.