#32: Promises from Scratch

Tagged as challenge

Written on 2018-01-31

In the first challenge, we created a syntactic primitive called a thunk to construct delayed computations, which could later be run by simply calling them.

However, there is a slight problem. Suppose we make the following thunk:

(define x (thunk (display "Hello!") (+ 1 1)))

Then when we run the thunk by doing (x) in Scheme or (funcall x) in Common Lisp, it will print "Hello!" and compute 2 on each invocation. In Common Lisp notation:

(defvar *thunk*
  (thunk
    (format t "Hello!")
    (+ 1 1)))

(funcall *thunk*)
  ; Prints: Hello!
  ; Returns: 2

(funcall *thunk*)
  ; Prints: Hello!
  ; Returns: 2

This may not be desirable if we want to simulate things such as call-by-need evaluation semantics.

In this exercise, create two abstractions, delay and force to ameliorate this issue. The delay abstraction should be similar to thunk in that it creates a delayed computation using lambda. We call the result of delay a promise.

The abstraction force is responsible now for actually evaluating the promise and producing an answer. However, using force a second time will give back a cached result.

Here's an example in Common Lisp notation:

(defvar *promise*
  (delay
    (format t "Hello!")
    (+ 1 1)))

(force *promise*)
  ; Prints: Hello!
  ; Returns: 2

(force *promise*)
  ; Does not print.
  ; Returns: 2

Unless otherwise credited all material copyright © 2010–2018 by Robert Smith