# Source §3 Non-Det

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!