17.20.3 Combinators and non–combinators

To discuss the transformations we define:

combinator

A Scheme function without free variables; a combinator does not capture any binding. The closure object implementing a combinator can be created once and for all at compile–time; for example:

(define (compute x y z)
  (define (lincomb a b c)
    (+ (* a b) (* a c)))
  (lincomb x y z))

assuming function integration is disabled: the closure object implementing the function lincomb can be created once at compile–time and reused at every call to compute.

non–combinator

A Scheme function with free variables, whose current value must be captured at run–time. To implement a non–combinator: a new closure object must be created at run–time every time the control flow reaches the lambda form, to capture the current values of the free variables; for example:

(define (adder x)
  (lambda (x)
    (+ x y)))

at every call to the function adder a new closure object must be created and returned, capturing the value of the argument x.

We want to discuss how to recognise combinators and non–combinators among the bindings defined by a fix struct. Let’s consider the recordised code:

(bind ((?lhs1 ?rhs1) ...)
  (fix ((?lhs0 ?rhs0) ...)
    (bind ((?lhs2 ?rhs2) ...)
      ?body)))

at this point in the sequence of compiler passes, we know that all the ?rhs0 are closure-maker structs. The var structs ?lhs0 and ?lhs1 may appear in the body of each ?rhs0, while the internally defined var structs ?lhs2 cannot; so the ?lhs2 do not influence the nature of the ?rhs0 expressions: we can ignore all the internally defined bindings. So let’s switch to inspect the recordised code:

(bind ((?lhs1 ?rhs1) ...)
  (fix ((?lhs0 ?rhs0) ...)
    ?body))

the var structs ?lhs0 and ?lhs1 may appear in the body of each ?rhs0; this includes the case of recursive ?rhs0, in which a ?lhs0 var appears in the list of free variables of the associated ?rhs0.

• If a list of free variables is empty: the corresponding ?rhs0 is a combinator. For example, in the recordised code:

  (bind ((a ?rhs-a) (b ?rhs-b))
    (fix ((f (closure-maker (lambda () '3) no-freevars))
          (g (closure-maker (lambda () '4) no-freevars)))
      ?body))
  

  both the fix–bound functions have empty list of free variables, so both functions are combinators.

• If a list of free variables contains only externally defined ?lhs1 structs: the corresponding ?rhs0 is a non–combinator. For example, in the recordised code:

  (bind ((a ?rhs-a) (b ?rhs-b))
    (fix ((f (closure-maker (lambda () a)
                            (freevars: a)))
          (g (closure-maker (lambda () (constant 3))
                            no-freevars)))
      ?body))
  

  the function bound to f has the var a in its free variables list; the value of the free variable a is known only at run–time, so the closure maker must capture a run–time value, so the function f is a non–combinator.

• If a list of free variables contains only ?lhs0 structs defined at by the same fix and bound to combinators: the corresponding ?rhs0 is a combinator. For example, in the recordised code:

  (bind ((a ?rhs-a) (b ?rhs-b))
    (fix ((f (closure-maker (lambda () (constant 3))
                            no-freevars))
          (g (closure-maker (lambda () (funcall f))
                            (freevars: f))))
      ?body))
  

  the function bound to f has no free variables, so it is a combinator; the function bound to g has f in its list of free variables; the value of f is known at compile–time, so the closure maker of g does not need to capture a free variable’s run–time value, so the function g is a combinator too.

• If every list of free variables contains only ?lhs0 structs defined by the same fix: all the corresponding ?rhs0 are combinators. For example, in the recordised code:

  (bind ((a ?rhs-a) (b ?rhs-b))
    (fix ((f (closure-maker (lambda () (funcall g))
                            (freevars: g)))
          (g (closure-maker (lambda () (funcall f))
                            (freevars: f))))
      ?body))
  

  both the functions have lists of free variables including only var structs defined by the same fix; the values of the free variables is known at compile–time, so the closure makers do not need to capture the free variables’ run–time values, so both the functions are combinators.

• If a list of free variables contains a ?lhs0 struct bound to a non–combinator, the corresponding ?rhs0 is a non–combinator too. For example, in the recordised code:

  (bind ((a ?rhs-a) (b ?rhs-b))
    (fix ((f (closure-maker (lambda () a)
                            (freevars: a)))
          (g (closure-maker (lambda () (funcall f))
                            (freevars: f))))
      ?body))
  

  the function bound to f is a non–combinator; the function bound to g has f in its free variables list; the value of f includes the run–time value of a, so the value of the free variable f is known only at run–time, so the closure maker of g must capture the run–time value, so the function g is a non–combinator too.