Function calling conventions and bindings

An attempt to describe three well-known function calling conventions in terms of bindings.

A little while ago I wrote an article on bindings which, in turn, was based on my answer to this Stack Overflow question. I have since written another answer to a more recent question and I thought it would be worth summarising part of that to describe how three famous function calling conventions can be described in terms of bindings¹.

Bindings in brief

A binding is an association between a name (a variable) and a value, where the value can be any object the language can talk about. In most Lisps (and other languages) bindings are not first-class: the language can not talk about bindings directly, and in particular bindings can not be values. Bindings are, or may be, mutable: their values (but not their names) can be changed by assignment. Many bindings can share the same value. Bindings have scope (where they are accessible) and extent (how long they are accessible for) and there are rules about that.

Call by value

In call by value the value of a binding is passed to a procedure. This means that the procedure can not mutate the binding itself. If the value is a mutable object it can be altered by the procedure, but the binding can not be.

Call by value is the convention used by all Lisps I know of. Here is a function which demonstrates that call by value can not mutate bindings:

(defun pbv (&optional (fn #'identity))
  ;; If FN returns then the first value of this function will be T
  (let ((c (cons 0 0)))                 ;first binding
    (let ((cc c))                       ;second binding, shares value with first
      (funcall fn c)                    ;FN gets the *value* of C
      (values (eq c cc) c))))           ;C and CC still refer to the same object

Call by reference

In call by reference, procedures get the bindings themselves as arguments. If a procedure modifies the binding by assignment, then it is modified in the calling procedure as well.

Lisp does not use call by reference: Fortran does, or can, use a calling mechanism which is equivalent to call by reference².

It is possible to implement what is essentially call by reference in Lisp (here Common Lisp, but any Lisp with lexical scope, indefinite extent & macros can do this) using some macrology:

(defmacro capture-binding (var)
  ;; Construct an object which captures a binding
  `(lambda (&optional (new-val nil new-val-p))
     (when new-val-p
       (setf ,var new-val))
     ,var))

(declaim (inline captured-binding-value
                 (setf captured-binding-value)))

(defun captured-binding-value (cb)
  ;; value of a captured binding
  (funcall cb))

(defun (setf captured-binding-value) (new cb)
  ;; change the value of a captured binding
  (funcall cb new))

And now, given

(defun mutate-binding (b v)
  (setf (captured-binding-value b) v))

(defun sort-of-call-by-reference ()
  (let ((c (cons 1 1)))
    (let ((cc c))
      (mutate-binding (capture-binding cc) 3)
      (values c cc))))

> (sort-of-call-by-reference)
(1 . 1)
3

The trick here is that the procedure created by the capture-binding macro has access to the binding being captured, and can mutate it.

Call by name

Call by name is the same as call by value, except the value of a binding is only computed at the point it is needed. Call by name is a form of delayed evaluation or normal-order evaluation strategy.

Lisp (at least Common Lisp: Lisps which have normal-order evaluation strategies exist) does not have call by name, but again it can be emulated with some macrology:

(defmacro delay (form)
  ;; simple-minded DELAY.  FORM is assumed to return a single value,
  ;; and will be evaluated no more than once.
  (let ((fpn (make-symbol "FORCEDP"))
        (vn (make-symbol "VALUE")))
    `(let ((,fpn nil) ,vn)
       (lambda ()
         (unless ,fpn
           (setf ,fpn t
                 ,vn ,form))
         ,vn))))

(declaim (inline force))

(defun force (thunk)
  ;; forcd a thunk
  (funcall thunk))

(defmacro funcall/delayed (fn &rest args)
  ;; call a function with a bunch of delayed arguments
  `(funcall ,fn ,@(mapcar (lambda (a)
                            `(delay ,a))
                          args)))

And now

(defun return-first-thunk-value (t1 t2)
  (declare (ignorable t2))
  (force t1))

(defun surprisingly-quick ()
  (funcall/delayed #'return-first-thunk-value
                   (cons 1 2)
                   (loop repeat 1000000
                         collect
                         (loop repeat 1000000
                               collect
                               (loop repeat 1000000
                                     collect 1)))))

> (time (surprisingly-quick))
Timing the evaluation of (surprisingly-quick)

User time    =        0.000
System time  =        0.000
Elapsed time =        0.001
Allocation   = 224 bytes
3 Page faults
(1 . 2)

The second argument to return-first-thunk-value was never forced, and so the function completes in reasonable time.