Repository files navigation

Metacircular evaluator for the non-deterministicSource 4.3 programming language with John McCarthy'samb operator for ambiguous choice.

Implementation is in:evaluator.js

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: 2try_again();// result: 3try_again();// result: 4try_again();// result: 6try_again();// result: 8try_again();// result: 9try_again();// result: 10try_again();// result: 12try_again();// result: null

/* 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: 1try_again();// result: 2try_again();// result: 3try_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)

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

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

2. Remove one of the two instances of the repeated functionvariable_declaration_name (fromevaluator.js andsource-test/main.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
• Fixedexecute_application to ensure that when a function is applied, the extended environment includesnames declared in the function body.
• Solved SICP JS exercise 4.45 by implementinganalyze_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 theparse_and_eval andtry_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 thelist function.#5
• Improved documentation of some functions.#11

This metacircular evaluator is built based onSICP 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 theparse function of theSource Academy