The lessons of Apollo
Tough and competent.
Tough and competent.
What sort of people will vote for Trump in 2020, if he lasts that long?
All serious historians agree that the Apollo programme of the 1960s and early 1970s was the highpoint of western civilisation.
Sometime in the middle of 2019, the UK will have a new prime minister. He1 will have considerable power to control whether, when and how the UK leaves the EU.
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 bindings1.
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.
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
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 reference2.
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 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.
This, in turn, is distantly descended from a post on comp.lang.lisp
by Erik Naggum. ↩
I think Fortran is allowed to implement its ‘by reference’ calls by copying any modified bindings back to the bindings in the parent procedure, and this is largely equivalent, at least for single-threaded code. ↩
I find the best way to think about this is to think in terms of bindings, rather than environments or frames, which are simply containers for bindings.
A binding is an association between a name and a value. The name is often called a ‘variable’ and the value is, well, the value of the variable. The value of a binding can be any object that the language can talk about at all. Bindings, however, are behind-the-scenes things (sometimes this is called ‘not being first-class objects’): they’re not things that can be represented in the language but rather things that you can use as part of the model of how the language works. So the value of a binding can’t be a binding, because bindings are not first-class: the language can’t talk about bindings.
There are some rules about bindings:
lambda
and define
;set!
;Obviously these rules need to be elaborated significantly (especially with regards to global bindings & forward-referenced bindings) and mare formal, but these are enough to understand what happens. In particular I don’t really think you need to spend a lot of time worrying about environments: the environment of a bit of code is just the set of bindings accessible to it, so rather than worry about the environment just worry about the bindings.
So, what ‘call by value’ means is that when you call a procedure with an argument which is a variable (a binding) what is passed to it is the value of the variable binding, not the binding itself. The procedure then creates a new binding with the same value. Two things follow from that:
So, here are some examples of these rules.
(define (silly x)
(set! x (+ x 1))
x)
(define (call-something fn val)
(fn val)
val))
> (call-something silly 10)
10
So, here we are creating two top-level bindings, for silly
and call-something
, both of which have values which are procedures. The value of silly
is a procedure which, when called:
x
and whose value is the argument to silly
;The value of call-something
is a procedure which, when called:
fn
and one named val
;fn
binding with the value of the val
binding;val
binding.Note that whatever the call to fn
does, it can not mutate the binding of val
, because it has no access to it. So what you can know, by looking at the definition of call-something
is that, if it returns at all (it may not return if the call to fn
does not return), it will return the value of its second argument. This guarantee is what ‘call by value’ means: a language (such as Fortran) which supports other call mechanisms can’t always promise this.
(define (outer x)
(define (inner x)
(+ x 1))
(inner (+ x 1)))
Here there are four bindings: outer
is a top-level binding whose value is a procedure which, when it is called, creates a binding for x
whose value is its argument. It then creates another binding called inner
whose value is another procedure, which, when it is called, creates a new binding for x
to its argument, and then returns the value of that binding plus one. outer
then calls this inner procedure with the value of its binding for x
.
The important thing here is that, in inner
, there are two bindings for x
which are potentially lexically visible, but the closest one — the one established by inner
— wins, because only one binding for a given name can ever be accessible at one time.
Here is the previous code (this would not be equivalent if inner
was recursive) expressed with explicit lambda
s:
(define outer
(λ (x)
((λ (inner)
(inner (+ x 1)))
(λ (x)
(+ x 1)))))
And finally an example of mutating bindings:
(define (make-counter val)
(λ ()
(let ((current val))
(set! val (+ val 1))
current)))
> (define counter (make-counter 0))
> (counter)
0
> (counter)
1
> (counter)
2
So, here, make-counter
(is the name of a binding whose value is a procedure which, when called,) establishes a new binding for val
and then returns a procedure it has created. This procedure makes a new binding called current
which catches the current value of val
, mutates the binding for val
to add one to it, and returns the value of current
. This code exercises the ‘if you can ever see a binding, you can always see it’ rule: the binding for val
created by the call to make-counter
is visible to the procedure it returns for as long as that procedure exists (and that procedure exists at least as long as there is a binding for it), and it also mutates a binding with set!
.
SICP, in chapter 3, introduces the ‘environment model’, where at any point there is an environment, consisting of a sequence of frames, each frame containing bindings. Obviously this is a fine model, but it introduces three kinds of thing — the enviromnent, the frames in the environment and the bindings in the frame — two of which are utterly intangible. At least for a binding you can get hold of it in some way: you can see it being created in the code and you can see references to it. So I prefer not to think in terms of these two extra sorts of thing which you can never get any kind of handle on.
However this is a choice which makes no difference in practice: thinking purely in terms of bindings helps me, thinking in terms of environments, frames & bindings may well help other people more.
In what follows I am going to use a shorthand for talking about bindings, especially top-level ones:
x
is a procedure which …’ means ’x
is the name of a binding whose value is a procedure which, when called, …’;y
is …’ means ’y
is the name of a binding the value of which is …’;x
is called with y
’ means ‘the value of the binding named by x
is called with the value of the binding named by y
’;x
to …’ means ’… creates a binding whose name is x
and whose value is …’;x
’ means ‘the value of x
’;Describing bindings like this is common, as the fully-explicit way is just painful: I’ve tried (but probably failed in places) to be fully explicit above.
And finally, after this long preamble, here’s the answer to the question you asked1.
(define (make-withdraw balance)
(λ (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
make-withdraw
binds balance
to its argument and returns a procedure it makes. This procedure, when called:
amount
to its argument;amount
with balance
(which it can still see because it could see it when it was created);balance
binding, decrementing its value by the value of the amount
binding, and returns the new value;"Insuficient funds"
(but does not mutate the balance
binding, so you can try again with a smaller amount: a real bank would probably suck some money out of the balance
binding at this point as a fine).Now
(define x (make-withdraw 100))
creates a binding for x
whose value is one of the procedures described above: in that procedure balance
is initially 100
.
(define (f y) (y 25))
f
is a procedure (is the name of a binding whose value is a procedure, which, when called) which binds y
to its argument and then calls it with an argument of 25
.
(f x)
So, f
is called with x
, x
being (bound to) the procedure constructed above. In f
, y
is bound to this procedure (not to a copy of it, to it), and this procedure is then called with an argument of 25
. This procedure then behaves as described above, and the results are as follows:
> (f x)
75
> (f x)
50
> (f x)
25
> (f x)
0
> (f x)
"Insufficient funds"
Note that:
I hope this makes some kind of sense.
Something you might want to be able to do is to back out a transaction on your account. One way to do that is to return, as well as the new balance, a procedure which undoes the last transaction. Here is a procedure which does that (this code is in Racket):
(define (make-withdraw/backout
balance
(insufficient-funds "Insufficient funds"))
(λ (amount)
(if (>= balance amount)
(let ((last-balance balance))
(set! balance (- balance amount))
(values balance
(λ ()
(set! balance last-balance)
balance)))
(values
insufficient-funds
(λ () balance)))))
When you make an account with this procedure, then calling it returns two values: the first is the new balance, or the value of insufficient-funds
(defaultly "Insufficient funds"
), the second is a procedure which will undo the transaction you just did. Note that it undoes it by explicitly putting back the old balance, because you can’t necessarily rely on (= (- (+ x y) y) x)
being true in the presence of floating-point arithmetic I think. If you understand how this works then you probably understand bindings.
This originated as an answer to this Stack Overflow question. ↩
In 1990, Richard Gabriel gave a talk from which Jamie Zawinski later extracted a section called ‘worse is better’ which he distributed widely. It’s strange but, perhaps, interesting, how prescient this idea was.
In June 2017 I argued that people who voted for Trump were racists: I’m very unhappy with that conclusion.
The UK keeps its laws on vellum: this seems to be a ludicrously archaic thing to do: is it?
As card-carrying members of the liberal elite we have to understand why so many people are so cross. Obviously it is our fault: with our awful progressive views we have prospered at their expense and it is only natural that they should express their anger by supporting politicians who are explicitly racist and misogynistic. That’s just a natural reaction: the people we have oppressed so horribly aren’t actually racists and misogynists, no, they just support politicians who are. It’s all our fault1.