A Gentle Introduction to Non-determinism in Scheme

2019-03-08 13:39:30 +0800

Some of the most crucial steps in mental growth are based not simply on acquiring new skills, but on acquiring new administrative ways to use what one already knows.
—Marvin Minsky

wallhaven-333472

Introduction
The current continuation
- Examples
The call/cc operator
The amb operator
Closing remarks

Introduction

Nondeterministic programming is a technique wherein the flow of an algorithm is not linear, and there exists multiple possible continuations. The behavior of a computation can also change with the same inputs. There are several methods to achieve nondeterminism. In this article the method that I’ll use is backtracking.

Additionally, I’ll use Scheme to do it. In Scheme, you are permitted to go back in an early computation and back, later, with ease.

I will also discuss the prerequisite topics to make nondeterminism in Scheme easier to understand.

In this article, I’ll be using the symbol λ for lambda. If you can’t type that symbol, you may use lambda, instead.

The current continuation

In Scheme, the current continuation or the remaining computation is the remaining work to evaluate the rest of the computation.

In the expression

the current continuation—the remaining computation—is

(λ (v) v)

and the remaining operation is

((λ (v) v) 0)

which returns

That is the result because the remaining computation on that level—the top-level—is the identity function.

Bear in mind, that the name of the argument of the lambda is not important. It can be v, x, or dog-cat-mouse:

((λ (dog-cat-mouse) dog-cat-mouse) 0)

Examples

In the expression

(* 1 2)

the remaining computation for 2—the second argument of *—is

(λ (v) (* 1 v))

and the remaining operation is

((λ (v) (* 1 v)) 2)

which, in that level of computation returns

Consequently, the remaining computation is

(λ (v) v)

and the remaining operation is

((λ (v) v) 2)

which finally returns, at the top-level:

In the expression

(+ (* 1 2) 3)

the flow of the computation is

   (* 1 2)
(+         3)

Firstly, (* 1 2) will be evaluated then the result becomes the first argument for (+ 3). In that empty space, the remaining computation is

(λ (v) (+ v 3))

and the remaining operation is

((λ (v) (+ v 3)) (* 1 2))

The call/cc operator

In Scheme, you can capture the current continuation—the next computation—as a variable. You can do that with call/cc. It is an operator which accepts only one argument exclusively—a lambda—an anonymous function, with one argument:

(call/cc (λ (k) k))

If you don’t have call/cc define it with:

(define call/cc call-with-current-continuation)

The phrase call with current continuation can also be treated as call with next computation. The function that it calls is the lambda. Additionally, call/cc passes the current continuation—the next computation—to that anonymous function.

In this lambda:

(λ (k) k)

k is a function itself which accepts one argument. So, in

(call/cc (λ (k) k))

call/cc returns the current continuation—simply the function. However, in

(call/cc (λ (k) (k 0)))

call/cc simply returns 0 because in that level—the top-level—k is

(λ (v) v)

—the identity function. Because of that, the function

(call/cc (λ (k) (k 0)))

is functionally equivalent to

((λ (v) v) 0)

Capturing

Going back to the earlier example:

(+ (* 1 2) 3)

you can capture the current continuation of (* 1 2) with call/cc:

(+ (call/cc (λ (k) (* 1 2))) 3)

However, you may notice that you did not apply the function k to anything. The expression (* 1 2) is evaluated, then the result goes to (+ _ 3). In other words, that expression is functionally equivalent to:

(+ (* 1 2) 3)

Application

Using the same example, let’s apply the function k:

(+ (call/cc (λ (k) (k (* 1 2)))) 3)

Inside the call of call/cc:

            (λ (k) (k (* 1 2)))

the variable k is the current continuation—the remaining computation. What is the remaining computation? This:

(+                               3)

the addition to 3. In order to represent that computation as function, it becomes:

(λ (v) (+ v 3))

Wherein (+ _ 3) is going to be represented by this lambda.

So, the role of call/cc is to call a lambda, which accepts the remaining computation. Here, the remaining computation is called k. Because of that, the consequence of:

(+ (call/cc (λ (k) (k (* 1 2)))) 3)

is functionally equivalent to

((λ (v) (+ v 3)) (* 1 2))

Escaping

(define z #f)
(+ (call/cc (λ (k) (set! z k) (* 1 2))) 3)

normally the result is

however, because we saved the current continuation—k—in z, we can return to that saved location with:

(z 1)

which returns

—another value. That mechanisms gives us the capability to escape computations, whether with a new value, an old value, or nothing.

For the reason that the current continuation is:

(λ (v) (+ v 3))

the call

(z 1)

is functionally equivalent to

((λ (v) (+ v 3)) 1)

instead of

((λ (v) (+ v 3)) (* 1 2))

Examples

(let ((x (call/cc (λ (k) k)))) (x (λ (o) "hi")))

the call

(x (λ (o) "hi"))

becomes

((call/cc (λ (k) k)) (λ (o) "hi"))

there, the remaining computation is

(λ (o) "hi")

which goes to the variable k in the body of call/cc. Like earlier, we apply k to (λ (o) "hi") inside another lambda:

((λ (v) (v (λ (o) "hi"))) (λ (o) "hi"))

which returns

"hi"

(((call/cc (λ (k) k)) (λ (x) x)) "hi")

the key is

((call/cc (λ (k) k)) (λ (x) x))

In the body of call/cc, the remaining computation is

(λ (x) x)

which goes to the variable k in the body of call/cc. Like earlier again, we apply it to the lambda:

((λ (v) (v (λ (x) x))) (λ (x) x))

which returns

#<procedure x>

It means, that you can now apply this function to the remaining argument:

(((λ (v) (v (λ (x) x))) (λ (x) x)) "hi")

which returns

"hi"

The amb operator

One of the uses of the famous amb operator in Scheme is to implement non-deterministic programming by means of backtracking. With that mechanism, the computation can go to an earlier state; carry computations; change change; escape computations; and more.

In this article we’re going to use the amb operator to enable the backtracking mechanism.

Definition

The definition that we’ll use is the one by shido.info/lisp. It is a macro to ensure that the arguments are not evaluated. Additionally, it uses lists internally.

(define call/cc call-with-current-continuation) ;  1
                                                ;  2
(define f #f)                                   ;  3
                                                ;  4
(define-syntax amb                              ;  5
  (syntax-rules ()                              ;  6
    ((_) (f))                                   ;  7
    ((_ a) a)                                   ;  8
    ((_ a b ...)                                ;  9
     (let ((s f))                               ; 10
       (call/cc                                 ; 11
        (λ (k)                                  ; 12
          (set! f (λ ()                         ; 13
                    (set! f s)                  ; 14
                    (k (amb b ...))))           ; 15
          (k a)))))))                           ; 16
                                                ; 17
(define (really? x y)                           ; 18
  (if (equal? x y)                              ; 19
      (list x y)                                ; 20
      (amb)))                                   ; 21
                                                ; 22
(call/cc                                        ; 23
 (λ (k)                                         ; 24
   (set! f (λ ()                                ; 25
             (k 'no-choices)))))                ; 26

These definitions work on MIT/GNU Scheme, Guile, Scheme48, Scsh, chibi-scheme, Gerbil, Chez Scheme, Chicken, Bigloo, Gauche, and Racket.

Deconstruction

In this section, we are going to deconstruct the definitions of the amb operator and other functions. The function really? technically is not part of the definition, however, we’ll use it to demonstrate the functionality of amb.

Here are superficial steps of the definitions:

In line 1 call/cc is bound to call-with-current-continuation mainly for implementations which doesn’t have that definition.
In line 3 f is bound to a default value.
In lines 5 to 16 is the body of amb.
In lines 18 to 21 is an example function: if x and y are equal, it returns a list; if not, amb is called.
In lines 23 to 26, call/cc is called, in which the true initial value of f is initialized with a lambda which returns 'no-choices.
Let’s go back to the body of amb in lines 5 to 16. In line 7, if amb is called as such:
```
(amb)
```
the function f is called, with whatever that f can do.
In line 8, if amb is called as such:
```
(amb "dog")
```
the argument "dog" is simply returned.
However, with more than one arguments, the behavior of amb changes. Firstly, in line 10, the current value of f is bound to s, next in line 11, call/cc is called, capturing the current continuation to k.
Inside the body of the lambda, the global variable f will have a new value—another lambda—which will not be evaluated until it is explicitly requested. In that body, f will have the earlier value of s, then k will be called with the value b ..., which are the remaining arguments for amb.
Lastly, the k function—the remaining computation—will be applied to the value a.

Evaluation

Using really? we will watch the evaluation steps in the use of amb. If we have the following expression,

(really? (amb "dog" "cat" 9) (amb "mouse" 9))

here are the simplified evaluation steps:

(amb "dog" "cat" 9) will be evaluated;
For the reason that more than one argument is passed to amb let’s go to line 9;
The local variable s will have the current value of f in the top-level:
```
(λ () (k 'no-choices))
```
The lambda in line 12 will be called with the remaining computation to k;
In line 13 f will have a new value. The value will be a lambda;
When the lambda is called, k again will have the value of s, which is the lambda in step 3.
k will be applied to a, wherein, (k a) is:
```
((λ (v) (really? v (amb "mouse" 9))) "dog")
```
which consequently becomes
```
((λ (v) ((λ (w) (really? v w)) "dog")) "mouse")
```
because of the call (amb "mouse" 9);
Because "dog" is not equal to "mouse" the amb operator will be called like:
```
(amb)
```
Because (amb) doesn’t have arguments, the expression in line 7 happens;
```
(f)
```
wherein the value of k is the lambda in lines 13 to 15. The value of f again becomes:
```
(λ () (k 'no-choices))
```
Then, in line 15 k will be called like (k "cat" 9).

The steps will be repeated, calling really? many times. The steps will look like:

(really? "dog" "mouse")
(really? "dog" 9)
(really? "cat" "mouse")
(really? "cat" 9)
(really? 9 "mouse")
(really? 9 9)

Because 9 is equal to 9, the expression
```
(list 9 9)
```
will be evaluated in the body of really? which finally returns
```
'(9 9)
```

Closing remarks

In this article, we noticed that with call/cc we have easily achieved non-determinism through backtracking with amb and basic Scheme functions. However, there are more elaborate and better methods of achieving this.

The type of continuations that we dealt with is the non-delimited continuation in contrast with a delimited continuation. I must also mention, that there’s an argument against the use of call/cc.

Anyway, I hope that you learned something good from this post.