Reading Time: 7 minutes

I recently took Dave Beazley’s week-long course on The Structure and Interpretation of Computer Programs. In this series, I’ll share memorable insights from the course (here’s where you can see all the posts so far).

In the last post, we talked about delayed evaluation—specifically, about the implementation details of building an interpreter for a Scheme like-language that defaults to lazy evaluation instead of eager evaluation.

In this post, we look at the implementation details of building yet another metacircular Scheme interpreter. This time, it’s for a version for the language that supports nondeterministic programming.

Hold up. What is nondeterministic programming?

If you’ve written automated software tests, chances are you’ve written example-based tests. You initialized some values, ran a method on them, and asserted that some outputs were what you expected. This works when the code is deterministic—when the same inputs should always produce the same result.

Nondeterminstic programs can produce different results as long as all results are circumscribed within a set of constraints. It’s frustrating as all hell to test, but it’s a powerful, elegant  way to express an acceptable set of outcomes.

Suppose you have a problem like this (from section 4.3.2 of SICP):

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that  contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper, Smith does not live on a floor adjacent to Fletcher’s. Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?

How would you solve this problem in a deterministic programming language? (Tip: go with whatever language comes to mind. Unless it’s Prolog or maybe Haskell, it’s probably deterministic).

Seriously. Take a second.

The solution in something like Java, Ruby, Python, or Swift requires translating those constraints into a set of conditions that make choices based on the results.

Then, when other programmers need to read that code, they need to study the conditions and the results to backtranslate, so they can understand the set of constraints that the program is meant to enforce. This is one of the things that makes debugging hard: we’re often tasked with finding the misrepresentation of an edge case that isn’t explicitly represented, but rather somehow encoded in a deterministic format.

A nondeterministic language abstracts away the condition-based choice points so we can express the constraints directly in our code, like this:

This code defines, at the start, all the possibilities for each variable; each of the people described in the problem must live on floor 1, 2, 3, 4, or 5. Then, the code expresses all of the constraints.

The amb evaluator at the top means ‘ambiguous.’ Each of these variables takes any one of these values. Which one, or ones, each variable can take depends on which one satisfy the constraints described in the require below.

The word problem above seems like a contrived example, but we run into analogous situations in programming all the time. Take this frontend example: “If the viewspace is large enough, this button and this blurb should both always be visible, each with a margin of 15. If the viewspace is not large enough, both margins can decrease all the way to zero. In a really small viewspace, the button can go on top of the blurb. And if the viewspace is still too small for that, the padding between the blurb text and the border should decrease. Meanwhile, if the button is on top of the blurb, the blurb should get darker and blurry and the button should get brighter.” We have eight ambiguous variables here: the margins on both the button and the blurb, the paddings on both the button and the blurb, the background colors of both the button and the blurb, the relative positioning (flexbox, in browsers) setting on the button relative to the blurb, and the blur setting on the blurb.

This can get messy enough that both iOS and Android both have introduced whole constraint-based DSLs to handle it.

How does an amb evaluator work?

You can see the full interpreter example right here; we’ll focus on three salient pieces.

1. We don’t return a result from evaluation: we succeed or fail.

We talked about introducing lazy evaluation at length in the last post, and we use it here to determine which options for our ambiguous variables satisfy our constraints at the choice points.

Because we wait to evaluate each expression until we absolutely must, we don’t return values upon processing them that require us to evaluate them. Instead, we supply two branches of behavior: success and failure.

2. Define the procedures for amb in our interpreter.

Our interpreter will evaluate ambiguous values by determining if the first one in the list succeeds, then if it fails, moving on to the next on in the list, and so forth until it reaches the end. If it reaches the end without finding a choice that satisfies the constraints, it fails.

This biases evaluation toward the left. So the order in which we pass options to the amb evaluator matters. The following two implementations each endeavor to find any number between (inclusive) a lower and upper bound. The only difference between them is the order in which options are passed to the amb evaluator:

They each consistently pick the first viable option from the left. So this evaluation strategy does not ambiguously choose any ol’ thing in the solution space that satisfies the constraints.

3. Define an operator for describing constraints.

This is the operator we see at work in the above example.

When a requirement is met, it returns true. Otherwise it returns amb with no choices, which fails.

Logic Programming Languages

Our interpreter cobbles together a sort-of amb evaluator for Scheme…except that we know which choice it will select given a list of multiple viable options that are always in the same order. As I understand it, true ambiguous evaluation is not predictable in this way given multiple viable options.

Scheme doesn’t have the amb evaluator out of the box. That said, logic programming languages like prolog are designed around the concept. This was my favorite of the intro videos that I found:

This is also as far as we made it into the book during the SICP course.

As expected, the takeaways around language design blew me away, and I’m sure that I’ll return to things we discussed in this course over and over as I continue my studies in more concrete terms through Crafting Interpreters and beyond.

If you liked this piece, you might also like:

This series on a framework for feature engineering (fun for the data scientists and ML engineers)

The risk-oriented testing screencast (example in Ruby, concept useful everywhere)

The time and space efficiency series (again, example in Ruby, concept applicable in other languages)