non-deterministic-source

Metacircular evaluator for the non-deterministic Source 4.3 programming language with John McCarthy's amb operator for ambiguous choice.

Implementation is in: evaluator.js

Run using parse_and_eval

Example:

Find integers between 0 and 12 (inclusive) that are divisible by 2 or 3.

parse_and_eval("function int_between(low, high) {\
                    return low > high ? amb() : amb(low, int_between(low + 1, high));\
                }\
                function is_even(x) { return (x % 2) === 0;}\
                function divisible_by_three(x) { return (x % 3) === 0;}\
                let integer = int_between(0, 12);\
                require(is_even(integer) || divisible_by_three(integer));\
                integer;");

// result: 0

Subsequent values can be generated by typing:

try_again(); // result: 2
try_again(); // result: 3
try_again(); // result: 4
try_again(); // result: 6
try_again(); // result: 8
try_again(); // result: 9
try_again(); // result: 10
try_again(); // result: 12
try_again(); // result: null

Other quick examples

/* SAT solving */
parse_and_eval("\
let P = amb(true, false); \
let Q = amb(true, false); \
let R = amb(true, false); \
let S = amb(true, false); \
\
let formula = (P || !Q || R) && (!P || Q || S) && (Q || !S) && (R || S) && (P || !R); \
require(formula === true); \
\
display('Satisfying Assignment:');\
display(P, 'P:'); \
display(Q, 'Q:'); \
display(R, 'R:'); \
display(S, 'S:'); \
");

// use `try_again()` to view all satisfying assignments.

parse_and_eval("const integer_from = n => amb(n, integer_from(n + 1)); integer_from(1);");
// result: 1
try_again(); // result: 2
try_again(); // result: 3
try_again(); // result: 4 ... and so on...

parse_and_eval("const f = amb(1, 2, 3); const g = amb(5, 6, 7); f;");
// Result: 1, 1, 1, 2, 2, 2, 3, 3, 3 (use the try_again() function)

parse_and_eval("const f = amb(1, 2, 3); const g = amb(5, 6, 7); g;");
// Result: 5, 6, 7, 5, 6, 7, 5, 6, 7 (use the try_again() function)

Running Tests

1. Copy the code from the following files into the playground:

   • evaluator.js
   • test.js
   • source-test/main.js

2. Remove one of the two instances of the repeated function variable_declaration_name (from evaluator.js and source-test/main.js)

Changes from SICP JS

This implementation of the evaluator contains several changes from that shown in the textbook. These consist of enhancements as well as bug fixes.

In descending order of complexity:

• Added logic to correctly evaluate return statements. #3, #26
• Added tests for deterministic and non-deterministic functionality. #8
• Fixed execute_application to ensure that when a function is applied, the extended environment includes names declared in the function body.
• Solved SICP JS exercise 4.45 by implementing analyze_require.
• Provided a more convenient method of running programs. The textbook implementation accepts programs via a continuously running prompt. In our implementation, users can instead use the parse_and_eval and try_again functions to run programs. This allows longer programs to be written easily. #6, #16
• Added support for logical operators && and ||. #9
• Added the unary minus operator. #22
• Prevented re-assignment to constants. #13
• Added support for lists via the list function. #5
• Improved documentation of some functions. #11

Acknowledgements

This metacircular evaluator is built based on SICP JS, Chapter 4.3. We used a metacircular evaluator for Source 1, provided in CS4215 materials, as a starting point for this evaluator.

It also uses the parse function of the Source Academy