Source §3 Non-Det is a small programming language, designed for the fourth chapter of the textbook Structure and Interpretation of Computer Programs, JavaScript Adaptation (SICP JS).
What is nondeterministic programming?
Source 3 Non-Det is a version of Source 3 with a built-in search mechanism. Programmers can specify sets of values, and requirements that the values must satisfy. The program evaluator then automatically identifies the values that meet the requirements.
What names are predeclared in Source §3 Non-Det?
On the right, you see all predeclared names of Source §3 Non-Det, in alphabetical order. Click on a name to see how it is defined and used. They come in these groups:
- AUXILIARY: Auxiliary constants and functions
- MISC: Miscellaneous constants and functions
- MATH: Mathematical constants and functions
- LISTS: Support for lists
- PAIRMUTATORS: Mutating pairs
- ARRAYS: Support for arrays
- STREAMS: Support for streams
- NON-DET: Support for nondeterminism
What can you do in Source §3 Non-Det?
You can use all features of Source §3 and all features that are introduced in chapter 4.3 of the textbook.
Below are the features that Source §3 Non-Det adds to Source §3.
amb operator
A set of values can be specified with the amb operator.
In the following example, we specify two possible choices for a value we want:
amb('hello', 'bye') + 'world!'; // 'hello world!'
To obtain the next value, 'bye', enter the command try_again in the playground REPL.
This will give the result 'bye world!'.
ambR operator
The ambR operator functions similarly to amb but makes choices randomly
instead of sequentially.
Upon running the above example, we may randomly obtain the result 'hello world!' first and 'bye world! second
or 'bye world! first and 'hello world!' second.
require function
Requirements can be specified with the require function.
In the following example, we add the requirement that the number chosen should be greater than 3:
const f = amb(1, 2, 3, 4, 5, 6); require(f > 3); f; // 4
To obtain the next value 5, enter the command try_again in the playground REPL.
Entering try_again once more will give the final value of 6.
cut operator
In order to obtain only the first possible value which satisfies given requirements,
the cut operator can be used to prevent backtracking beyond the current statement.
In the following example, we are able to obtain only a single value:
const f = amb(1, 2, 3, 4, 5, 6); require(f > 3); cut(); f; // 4
Entering try_again in the playground REPL will not give the subsequent values that were specified,
5 and 6.
implication function
The implication function can be used to model logical implication between two boolean expressions.
bi_implication function
The bi_implication function can be used to model logical bi-implication between two boolean expressions.
an_element_of function
The an_element_of function can be used to nondeterministically obtain an element from a list.
It functions similarly to amb but takes in a list of choices as argument instead of the choices being arguments themselves.
an_integer_between function
The an_integer_between function can be used to nondeterministically obtain an integer between a specified range (inclusively).
You want the definitive specs?
For our development team, we are maintaining a definitive description of the language, called the Specification of Source §3 Non-Det. Feel free to take a peek!