Future let++ Bindings

In a previous post we wrote about the challenges of implementing DAG scoping model for bindings in certain Qi forms. Today we are about to witness an attempt to bring similar scoping rules to plain Scheme and we may reason a bit whether it could be useful in practice.

The story begins with simple let construct we all know and love. It allows the programmer to introduce new bindings, meaning it binds identifiers to some computed values like in the following program:

(let ((a 1)
      (b 2))
  (displayln (+ a b)))

This binds a to 1, b to 2, and then the body expression prints the result of summing the two values together. Running this program would produce "3" as exprected.

The let form can be seen as an instance of the following template:

(let ((id val) ...)
  body ...)

It is quite easy to implement the let bindings form using the core lambda form. The aforementioned example could be transformed into the following chunk of code:

((lambda (a b)
   (displayln (+ a b)))
 1 2)

Typically Scheme programmers do not write these transformations by hand but rather use define-syntax and syntax-rules (see r5rs Chapter 5 for more) to perform this transformation during program expansion:

(define-syntax let
  (syntax-rules ()
    ((_ ((id val) ...) body ...)
     ((lambda (id ...)
        body ...)
      val ...))))

The obvious limitation is that we cannot use the introduced identifiers in subsequent bindings of the same let form. The following would signal an error:

(let ((a 1)
      (b (+ a 1)))
  (displayln (+ a b)))

However there is a way out - the let* form. Adding a single * makes it all work:

(let* ((a 1)
       (b (+ a 1)))
  (displayln (+ a b)))

The question is - of course - how? And the answer is rather simple. The let* is converted into nested let's and that is all:

(let ((a 1))
  (let ((b (+ a 1)))
    (displayln (+ a b))))

Obligatory syntactic macro would be:

(define-syntax let*
  (syntax-rules ()
    ((_ () body ...)
     (let ()
       body ...))
    ((_ ((id val) more ...) body ...)
     (let ((id val))
       (let* (more ...)
         body ...)))))

Of course, this implementation is far from optimal (for whatever meaning you might give to the word "optimal"), however it shows the corresponding isomorphism between core lambda, let and let* forms.

The interesting question is whether we can create something similar to what we were discussing in the "Tree versus dag bindings" post. And the answer is yes. We can introduce a new let+ form that allows binding multiple ids within each branch where former identifiers can be used in subsequent bindings within the same branch. Using introduced identifiers across binding branches would be forbidden though. Yet finally using all the introduced bindings would be possible in body expressions. A typical usage would look like:

(let+ (((a 1)
        (b 2)
        (c (+ a b)))
       ((d 4)))
  (displayln (+ a b c d)))

On its own it does not seem very useful - but before we move on to turning it into something truly helpful, it seems to be a verifiable step which should be taken. It turns out that such form is easy to implement:

(define-syntax let+
  (syntax-rules ()
    ((_ (((id expr) ...) ...) body ...)
     (let-values (((id ...)
                   (let* ((id expr) ...)
                     (values id ...))) ...)
       body ...))))

For those not familiar with the let-values form, it just allows to bind multiple identifiers at once using the ability of procedures to return multiple values at once. The explanation would be more complex as the protocol for multiple values arises naturally from generalization of single-valued continuations which is beyond the scope of this article.

Now how can we do something useful? By ensuring the individual branches are independent on each other and yet by allowing using the identifiers introduced within each of them for creating subsequent bindings within the same branch, we can compute all the binding branches in parallel. For more complex operations this may amount to a massive speedup.

In order to achieve the parallel computation, we look into futures and leverage their ability to be computed speculatively in advance:

(require racket/future)

(define-syntax let++
  (syntax-rules ()
    ((_ (((id expr) ...) ...) body ...)
     (let++ "temp"
            ()
            (((id expr) ...) ...) body ...))
    ((_ "temp" ((I (id expr) ...) ...) () body ...)
     (let ((I (future
               (lambda ()
                 (let* ((id expr) ...)
                   (values id ...))))) ...)
       (let-values (((id ...) (touch I)) ...)
         body ...))
     )
    ((_ "temp" (gen ...) (((id expr) ...) more ...) body ...)
     (let++ "temp"
            (gen ... (I (id expr) ...))
            (more ...)
            body ...))))

Yes, the Racket's futures implementation is the easiest way to demonstrate this capability and yes, when using Racket, the macro could be expressed in a more concise way using syntax-case. However this implementation can be used with any Scheme implementation providing any kind of speculative computation of futures or future-like forms.

This one was a bit of a blast - but hopefully you found it useful. Stay tuned to see what we may find exploring alternative binding scopes and their applications. See ya next time!