Next: , Previous: , Up: compiler lifting   [Index]

17.20.5 Examples of combinators and non–combinators

Let’s consider some examples of code creating a function and reason about the function being a combinator or a non–combinator; in these examples function integration has been disabled.

Standalone combinator

This core language expression: 

(lambda () ((primitive read)))

is transformed into: 

(codes
  ((lambda (label: asmlabel:anonymous:clambda)
     () (funcall (primref read))))
  (closure-maker (code-loc asmlabel:anonymous:clambda)
                 no-freevars))

the returned function looks like it is closed upon the binding read, but in truth read is a primitive function whose value is known at compile–time; so the returned function is a combinator.

Simple combinators definition

This core language expression: 

(let ((f (lambda () '1))
      (g (lambda () '2)))
  ((primitive list) (f) (g)))

defines two combinator functions; the closure-maker struct is introduced at the functions’ call site: 

(codes
  ((lambda (label: asmlabel:g:clambda) () (constant 2))
   (lambda (label: asmlabel:f:clambda) () (constant 1)))
  (funcall (primref list)
    (jmpcall asmlabel:f:clambda:case-0
             (closure-maker (code-loc asmlabel:f:clambda)
                            no-freevars))
    (jmpcall asmlabel:g:clambda:case-0
             (closure-maker (code-loc asmlabel:g:clambda)
                            no-freevars))))

Multiple calls to single combinator

This core language form: 

(let ((f (lambda () '1)))
   ((primitive list) (f) (f)))

defines a combinator function; multiple closure-maker structs are introduced at the call site for the same function: 

(codes
  ((lambda (label: asmlabel:f:clambda) () (constant 1)))
  (funcall (primref list)
    (jmpcall asmlabel:f:clambda:case-0
             (closure-maker (code-loc asmlabel:f:clambda)
                            no-freevars))
    (jmpcall asmlabel:f:clambda:case-0
             (closure-maker (code-loc asmlabel:f:clambda)
                            no-freevars))))

Non–combinator definition

In the core language expression: 

(let ((a ((primitive read))))
  (lambda () a))

the returned function is a non–combinator because its return value depends upon the value of the binding a at the time the closure object is created; a is a free variable in the body of the function and the function is closed upon it. Indeed such form is transformed into: 

(codes
  ((lambda (label: asmlabel:anonymous:clambda) () a_0))
  (bind ((a_0 (funcall (primref read))))
    (fix ((tmp_0 (closure-maker
                   (code-loc asmlabel:anonymous:clambda)
                   (freevars: a_0))))
      tmp_0)))

Multiple calls to non–combinator

In this example a single non–combinator is called twice: 

(let ((a ((primitive read))))
  (let ((f (lambda () a)))
    ((primitive list) (f) (f))))

the result of the transformation is: 

(codes
  ((lambda (label: asmlabel:f:clambda) () a_0))
  (bind ((a_0 (funcall (primref read))))
    (fix ((f_0 (closure-maker (code-loc asmlabel:f:clambda)
                              (freevars: a_0))))
      (funcall (primref list)
               (jmpcall asmlabel:f:clambda:case-0 f_0)
               (jmpcall asmlabel:f:clambda:case-0 f_0)))))

we see that a single closure-maker is introduced.

Recursive combinator and non–combinator

A self reference in a recursive function does not necessarily make it a non–combinator. For example: 

(letrec ((f (lambda () (f))))
  ?body)

is transformed into: 

(codes
  ((lambda (label: asmlabel:f:clambda) ()
     (jmpcall asmlabel:f:clambda:case-0
              (closure-maker (code-loc asmlabel:f:clambda)
                             no-freevars))))
  (closure-maker (code-loc asmlabel:f:clambda) no-freevars))

there are no free variables other than the recursive reference, so the function is a combinator. Conversely, in the expression: 

(let ((a ((primitive read))))
  (letrec ((f (lambda (x) (f a))))
    (f '1)))

in addition to the self reference there is a non–removable free variable, so the result of the transformation is: 

(codes
  ((lambda (label: asmlabel:f:clambda) (x_0)
      (jmpcall asmlabel:f:clambda:case-1 f_0 a_0)))
  (bind ((a_0 (funcall (primref read))))
    (fix ((f_0 (closure-maker (code-loc asmlabel:f:clambda)
                              (freevars: a_0))))
      (jmpcall asmlabel:f:clambda:case-1 f_0 (constant 1)))))

Cycle of combinator calls

In this expression functions defined at the same lexical contour call each other in a cycle: 

(letrec* ((a (lambda () (d)))
          (b (lambda () (a)))
          (c (lambda () (b)))
          (d (lambda () (c))))
  ((primitive list) (a) (b) (c) (d)))

there are no true free variables, so all the functions are implemented as combinators: 

(codes
 ((lambda (label: asmlabel:a:clambda) ()
     (jmpcall asmlabel:d:clambda:case-0
              (closure-maker (code-loc asmlabel:d:clambda)
                             no-freevars)))
  (lambda (label: asmlabel:d:clambda) ()
     (jmpcall asmlabel:c:clambda:case-0
              (closure-maker (code-loc asmlabel:c:clambda)
                             no-freevars)))
  (lambda (label: asmlabel:c:clambda) ()
     (jmpcall asmlabel:b:clambda:case-0
              (closure-maker (code-loc asmlabel:b:clambda)
              no-freevars)))
  (lambda (label: asmlabel:b:clambda) ()
     (jmpcall asmlabel:a:clambda:case-0
              (closure-maker (code-loc asmlabel:a:clambda)
              no-freevars))))
 (funcall (primref list)
   (jmpcall asmlabel:a:clambda:case-0
            (closure-maker (code-loc asmlabel:a:clambda)
                           no-freevars))
   (jmpcall asmlabel:b:clambda:case-0
            (closure-maker (code-loc asmlabel:b:clambda)
                           no-freevars))
   (jmpcall asmlabel:c:clambda:case-0
            (closure-maker (code-loc asmlabel:c:clambda)
                           no-freevars))
   (jmpcall asmlabel:d:clambda:case-0
            (closure-maker (code-loc asmlabel:d:clambda)
            no-freevars))))

Cycle of non–combinator calls

In this expression functions defined at the same lexical contour call each other in a cycle; one of them has a true free variable, causing all of them to be non–combinators: 

(let ((v ((primitive read))))
  (letrec* ((a (lambda (x) (d x)))
            (b (lambda (x) (a x)))
            (c (lambda (x) (b x)))
            (d (lambda (x) (c v))))
    ((primitive list) (a '1) (b '2) (c '3) (d '4))))

the result of the transformation is: 

(codes
 ((lambda (label: asmlabel:a:clambda) (x_0)
     (jmpcall asmlabel:d:clambda:case-1 d_0 x_0))
  (lambda (label: asmlabel:d:clambda) (x_1)
     (jmpcall asmlabel:c:clambda:case-1 c_0 v_0))
  (lambda (label: asmlabel:c:clambda) (x_2)
     (jmpcall asmlabel:b:clambda:case-1 b_0 x_2))
  (lambda (label: asmlabel:b:clambda) (x_3)
     (jmpcall asmlabel:a:clambda:case-1 a_0 x_3)))
 (bind ((v_0 (funcall (primref read))))
   (fix ((a_0 (closure-maker (code-loc asmlabel:a:clambda)
                             (freevars: d_0)))
         (d_0 (closure-maker (code-loc asmlabel:d:clambda)
                             (freevars: c_0 v_0)))
         (c_0 (closure-maker (code-loc asmlabel:c:clambda)
                             (freevars: b_0)))
         (b_0 (closure-maker (code-loc asmlabel:b:clambda)
                             (freevars: a_0))))
     (funcall (primref list)
       (jmpcall asmlabel:a:clambda:case-1 a_0 (constant 1))
       (jmpcall asmlabel:b:clambda:case-1 b_0 (constant 2))
       (jmpcall asmlabel:c:clambda:case-1 c_0 (constant 3))
       (jmpcall asmlabel:d:clambda:case-1 d_0 (constant 4))))))

Next: , Previous: , Up: compiler lifting   [Index]