| author | Alan Dipert
<alan@dipert.org> 2026-11-11 00:39:40 UTC |
| committer | Alan Dipert
<alan@dipert.org> 2026-11-11 00:40:03 UTC |
| parent | 30994041d160ed740db412f9e72084500c253947 |
| test/com/tailrecursion/assignment_model.clj | +76 | -0 |
| test/com/tailrecursion/blacktide/assignment_test.clj | +29 | -14 |
| test/com/tailrecursion/blacktide/backend_fixture.clj | +0 | -1 |
| test/com/tailrecursion/blacktide/control_test.clj | +1 | -16 |
| test/com/tailrecursion/nanopass/annotations.clj | +1 | -6 |
| test/com/tailrecursion/nanopass/assignment_test.clj | +2 | -74 |
| test/com/tailrecursion/nanopass/check.clj | +13 | -29 |
| test/com/tailrecursion/nanopass/clients/flow.clj | +0 | -112 |
| test/com/tailrecursion/nanopass/clients/flow_languages.clj | +0 | -35 |
| test/com/tailrecursion/nanopass/flow_test.clj | +0 | -102 |
| test/com/tailrecursion/test_runner.clj | +0 | -1 |
diff --git a/test/com/tailrecursion/assignment_model.clj b/test/com/tailrecursion/assignment_model.clj new file mode 100644 index 0000000..54b1be9 --- /dev/null +++ b/test/com/tailrecursion/assignment_model.clj @@ -0,0 +1,76 @@ +(ns com.tailrecursion.assignment-model + "Independent assignment semantics, event traces, and bounded source generators. + Shared by the nanopass client tests and the real Loophole compiler tests." + (:require [clojure.test.check.generators :as gen])) + +(defn lit [value] {:op :const :value value}) +(defn read-var [name] {:op :read :binding name}) +(defn batch [op & writes] {:op op :writes (mapv vec (partition 2 writes))}) +(defn sequence-of [& forms] {:op :do :forms (vec forms)}) +(defn event [tag value] {:op :event :tag tag :value value}) + +(defn evaluate [form state] + (let [run #(evaluate % %2) + binding (:binding form)] + (case (:op form) + :const [(:value form) state] + :read [(get-in state [:vars binding]) state] + :temp (let [id (:id form)] + (when-not (contains? (:temps state) id) + (throw (ex-info "Unbound temporary" {:id id}))) + [(get-in state [:temps id]) state]) + :add (let [[a state] (run (:left form) state) + [b state] (run (:right form) state)] [(+ a b) state]) + :do (reduce (fn [[_ state] form] (run form state)) [nil state] (:forms form)) + :if (let [[test state] (run (:test form) state)] + (run (if test (:then form) (:else form)) state)) + :event (let [[value state] (run (:value form) state)] + [value (update state :trace conj [(:tag form) value])]) + :throw (throw (ex-info "Source exception" {:status :throw :tag (:tag form) :state state})) + ;; Source assignments define their semantics directly, independent of + ;; the pass's generated binding tree and the output's write primitive. + :setq (reduce (fn [[_ state] [name rhs]] + (let [[value state] (run rhs state)] + [value (assoc-in state [:vars name] value)])) + [nil state] (:writes form)) + :psetq (let [[values state] + (reduce (fn [[values state] [_ rhs]] + (let [[value state] (run rhs state)] + [(conj values value) state])) + [[] state] (:writes form))] + [nil (update state :vars merge (zipmap (map first (:writes form)) values))]) + ;; The output interpreter knows only a single write and lexical temps. + :write (let [[value state] (run (:value form) state)] + [value (assoc-in state [:vars binding] value)]) + :bind (let [[value state] (run (:value form) state) + temps (:temps state) + [result state] (run (:body form) (assoc-in state [:temps (:id form)] value))] + [result (assoc state :temps temps)])))) + +(defn execute [form vars] + (let [state {:vars vars :temps {} :trace []}] + (try + (let [[value state] (evaluate form state)] + (assoc (select-keys state [:vars :trace]) :value value :status :return)) + (catch clojure.lang.ExceptionInfo e + (let [{:keys [state status tag]} (ex-data e)] + (if status + (cond-> (assoc (select-keys state [:vars :trace]) :status status) + tag (assoc :tag tag)) + (throw e))))))) + +(defn expression [depth] + (let [leaf (gen/one-of [(gen/fmap lit (gen/choose -5 5)) + (gen/fmap read-var (gen/elements '[x y]))])] + (if (zero? depth) leaf + (let [child (expression (dec depth)) + writes (gen/vector (gen/tuple (gen/elements '[x y]) child) 0 3)] + (gen/one-of + [leaf + (gen/let [a child b child] {:op :add :left a :right b}) + (gen/let [a child b child] (sequence-of a b)) + (gen/let [test gen/boolean then child else child] + {:op :if :test (lit test) :then then :else else}) + (gen/let [tag (gen/elements [:a :b :c]) value child] (event tag value)) + (gen/let [writes writes] (sequence-of {:op :setq :writes writes} (read-var 'x))) + (gen/let [writes writes] (sequence-of {:op :psetq :writes writes} (read-var 'y)))]))))) diff --git a/test/com/tailrecursion/blacktide/assignment_test.clj b/test/com/tailrecursion/blacktide/assignment_test.clj index 484b2ab..0e26566 100644 --- a/test/com/tailrecursion/blacktide/assignment_test.clj +++ b/test/com/tailrecursion/blacktide/assignment_test.clj @@ -2,10 +2,13 @@ "Assignment semantics, saved operands, and independent interpreter comparisons." (:require [clojure.test :refer [deftest is]] [clojure.test.check :as tc] + [clojure.test.check.clojure-test :refer [defspec]] + [clojure.test.check.generators :as gen] [clojure.test.check.properties :as prop] [com.tailrecursion.blacktide :as lh :refer [loophole setq psetq]] + [com.tailrecursion.blacktide.backend-fixture :as backend] [com.tailrecursion.blacktide.source-test :as source] - [com.tailrecursion.nanopass.assignment-test :as oracle])) + [com.tailrecursion.assignment-model :as oracle])) (defn add [a b] (+ a b)) (defn event! [events tag value] (swap! events conj [tag value]) value) @@ -70,26 +73,27 @@ :add (list '+ (render (:left node)) (render (:right node))) :do (list* 'do (map render (:forms node))) :if (list 'if (render (:test node)) (render (:then node)) (render (:else node))) - :event (list 'event! 'events (:tag node) (render (:value node))) + :event (list 'com.tailrecursion.blacktide.assignment-test/event! 'events (:tag node) (render (:value node))) (:setq :psetq) (list* (symbol (name (:op node))) (mapcat (fn [[name rhs]] [name (render rhs)]) (:writes node))))) -(defn execute [node x y] - (binding [*ns* (the-ns 'com.tailrecursion.blacktide.assignment-test)] - (try - (eval (list 'let ['events '(atom [])] - (list 'loophole ['x x 'y y] - (list 'let ['result (render node)] - {:status :return :value 'result :trace '(deref events) - :vars {(list 'quote 'x) 'x (list 'quote 'y) 'y}})))) - (catch Throwable e {:compiler-error (class e) :message (ex-message e)})))) +(defn compile-node [node] + ;; Preserve known Long producers while reusing code across initial states. + ((backend/compile-program + (list 'fn '[x y] + (list 'let ['events '(atom [])] + (list 'loophole '[x (long x) y (long y)] + (list 'let ['result (render node)] + {:status :return :value 'result :trace '(deref events) + :vars {(list 'quote 'x) 'x (list 'quote 'y) 'y}})))) :default) nil)) (deftest generated-assignment-programs ;; Reuse only the independent source interpreter, not its lowering algorithm. (let [property (prop/for-all [node (oracle/expression 3)] - (every? true? - (for [[x y] [[0 0] [1 2] [-7 5] [10 -3]]] - (= (oracle/execute node {'x x 'y y}) (execute node x y)))))] + (let [compiled (compile-node node)] + (every? true? + (for [[x y] [[0 0] [1 2] [-7 5] [10 -3]]] + (= (oracle/execute node {'x x 'y y}) (compiled x y))))))] (doseq [seed [712381 314159]] (let [result (tc/quick-check 100 property :seed seed)] (is (:pass? result) (pr-str result)))))) @@ -100,3 +104,14 @@ form (list 'loophole '[f vector x 0] [(cons 'f args) '(f :after) 'x]) expected [(vec (concat (range 1 (inc n)) [n n])) '(:after) n]] (is (= expected (source/run-form form)) (pr-str {:arity (+ n 2) :form form}))))) + +(defspec generated-effectful-conditions {:num-tests 100 :seed 20261104} + (prop/for-all [test (gen/elements [(oracle/batch :psetq 'x (oracle/read-var 'y) 'y (oracle/read-var 'x)) + (oracle/batch :setq 'x (oracle/lit 0)) + (oracle/read-var 'x)]) + then (oracle/expression 2) else (oracle/expression 2)] + (let [node {:op :if :test (oracle/event :test test) :then then :else else} + compiled (compile-node node)] + (every? true? + (for [[x y] [[0 0] [1 2] [-7 5] [10 -3]]] + (= (oracle/execute node {'x x 'y y}) (compiled x y))))))) diff --git a/test/com/tailrecursion/blacktide/backend_fixture.clj b/test/com/tailrecursion/blacktide/backend_fixture.clj index d39eee3..1076334 100644 --- a/test/com/tailrecursion/blacktide/backend_fixture.clj +++ b/test/com/tailrecursion/blacktide/backend_fixture.clj @@ -38,4 +38,3 @@ (defn run-machine [machine] (binding [*ns* (the-ns 'com.tailrecursion.blacktide.backend-fixture)] (eval (emit/program-form machine)))) - diff --git a/test/com/tailrecursion/blacktide/control_test.clj b/test/com/tailrecursion/blacktide/control_test.clj index 7e48d70..5c08b27 100644 --- a/test/com/tailrecursion/blacktide/control_test.clj +++ b/test/com/tailrecursion/blacktide/control_test.clj @@ -1,13 +1,8 @@ (ns com.tailrecursion.blacktide.control-test "Source control flow and live values across state-machine transitions." (:require [clojure.test :refer [deftest is]] - [clojure.test.check.clojure-test :refer [defspec]] - [clojure.test.check.generators :as gen] - [clojure.test.check.properties :as prop] [com.tailrecursion.blacktide :refer [loophole setq psetq]] - [com.tailrecursion.blacktide.source-test :as source] - [com.tailrecursion.blacktide.assignment-test :as assignment] - [com.tailrecursion.nanopass.assignment-test :as oracle])) + [com.tailrecursion.blacktide.source-test :as source])) (defn record! [events tag value] (swap! events conj tag) value) @@ -64,13 +59,3 @@ (doseq [form ['(if true) '(if true 1 2 3) '(throw) '(throw nil nil)]] (is (= (if (= 'if (first form)) :invalid-if :invalid-throw) (:kind (source/rejection (list 'loophole [] form))))))) - -(defspec generated-effectful-conditions {:num-tests 100 :seed 20261104} - (prop/for-all [test (gen/elements [(oracle/batch :psetq 'x (oracle/read-var 'y) 'y (oracle/read-var 'x)) - (oracle/batch :setq 'x (oracle/lit 0)) - (oracle/read-var 'x)]) - then (oracle/expression 2) else (oracle/expression 2)] - (let [node {:op :if :test (oracle/event :test test) :then then :else else}] - (every? true? - (for [[x y] [[0 0] [1 2] [-7 5] [10 -3]]] - (= (oracle/execute node {'x x 'y y}) (assignment/execute node x y))))))) diff --git a/test/com/tailrecursion/nanopass/annotations.clj b/test/com/tailrecursion/nanopass/annotations.clj index 1c5a9dd..142b410 100644 --- a/test/com/tailrecursion/nanopass/annotations.clj +++ b/test/com/tailrecursion/nanopass/annotations.clj @@ -5,15 +5,10 @@ [com.tailrecursion.nanopass.pipeline :as pipeline] [com.tailrecursion.nanopass.fixtures :as f] [com.tailrecursion.nanopass.passes :as p] - [com.tailrecursion.nanopass.clients.assignment :as assignment] - [com.tailrecursion.nanopass.clients.flow :as flow] - [com.tailrecursion.nanopass.clients.flow-languages :as flow-languages])) + [com.tailrecursion.nanopass.clients.assignment :as assignment])) (np/ann-languages f/Source f/Core f/Literals f/Mutual f/Stopped) (np/ann-passes pipeline/map-value) (np/ann-passes p/lower p/lower-binding p/rename p/rename-binding p/count-step p/lower-envelope) (np/ann-languages assignment/Source assignment/Core) (np/ann-passes assignment/lower assignment/sequential-writes assignment/parallel-writes) -(np/ann-languages flow-languages/Syntax flow-languages/Bound flow-languages/Machine) -(np/ann-passes flow/bind-expr flow/bind-exprs flow/bind-local flow/fresh-block flow/fresh-value - flow/emit-op flow/seal flow/start flow/lower flow/lower-exprs flow/compile-program) diff --git a/test/com/tailrecursion/nanopass/assignment_test.clj b/test/com/tailrecursion/nanopass/assignment_test.clj index e33d91f..918b62c 100644 --- a/test/com/tailrecursion/nanopass/assignment_test.clj +++ b/test/com/tailrecursion/nanopass/assignment_test.clj @@ -3,65 +3,9 @@ The interpreter is test instrumentation; the compiler pass only constructs data." (:require [clojure.test :refer [deftest is testing]] [clojure.test.check :as tc] - [clojure.test.check.generators :as gen] [clojure.test.check.properties :as prop] - [com.tailrecursion.nanopass.clients.assignment :as lower])) - -(defn lit [value] {:op :const :value value}) -(defn read-var [name] {:op :read :binding name}) -(defn batch [op & writes] {:op op :writes (mapv vec (partition 2 writes))}) -(defn sequence-of [& forms] {:op :do :forms (vec forms)}) -(defn event [tag value] {:op :event :tag tag :value value}) - -(defn evaluate [form state] - (let [run #(evaluate % %2) - binding (:binding form)] - (case (:op form) - :const [(:value form) state] - :read [(get-in state [:vars binding]) state] - :temp (let [id (:id form)] - (when-not (contains? (:temps state) id) - (throw (ex-info "Unbound temporary" {:id id}))) - [(get-in state [:temps id]) state]) - :add (let [[a state] (run (:left form) state) - [b state] (run (:right form) state)] [(+ a b) state]) - :do (reduce (fn [[_ state] form] (run form state)) [nil state] (:forms form)) - :if (let [[test state] (run (:test form) state)] - (run (if test (:then form) (:else form)) state)) - :event (let [[value state] (run (:value form) state)] - [value (update state :trace conj [(:tag form) value])]) - :throw (throw (ex-info "Source exception" {:status :throw :tag (:tag form) :state state})) - ;; Source assignments define their semantics directly, independent of - ;; the pass's generated binding tree and the output's write primitive. - :setq (reduce (fn [[_ state] [name rhs]] - (let [[value state] (run rhs state)] - [value (assoc-in state [:vars name] value)])) - [nil state] (:writes form)) - :psetq (let [[values state] - (reduce (fn [[values state] [_ rhs]] - (let [[value state] (run rhs state)] - [(conj values value) state])) - [[] state] (:writes form))] - [nil (update state :vars merge (zipmap (map first (:writes form)) values))]) - ;; The output interpreter knows only a single write and lexical temps. - :write (let [[value state] (run (:value form) state)] - [value (assoc-in state [:vars binding] value)]) - :bind (let [[value state] (run (:value form) state) - temps (:temps state) - [result state] (run (:body form) (assoc-in state [:temps (:id form)] value))] - [result (assoc state :temps temps)])))) - -(defn execute [form vars] - (let [state {:vars vars :temps {} :trace []}] - (try - (let [[value state] (evaluate form state)] - (assoc (select-keys state [:vars :trace]) :value value :status :return)) - (catch clojure.lang.ExceptionInfo e - (let [{:keys [state status tag]} (ex-data e)] - (if status - (cond-> (assoc (select-keys state [:vars :trace]) :status status) - tag (assoc :tag tag)) - (throw e))))))) + [com.tailrecursion.nanopass.clients.assignment :as lower] + [com.tailrecursion.assignment-model :refer [lit read-var batch sequence-of event execute expression]])) (deftest values-and-sequencing (let [x (read-var 'x) y (read-var 'y)] @@ -108,22 +52,6 @@ (is (= expected (execute source {'x 1 'y 2}))) (is (= expected (execute (lower/lower source) {'x 1 'y 2}))))))) -(defn expression [depth] - (let [leaf (gen/one-of [(gen/fmap lit (gen/choose -5 5)) - (gen/fmap read-var (gen/elements '[x y]))])] - (if (zero? depth) leaf - (let [child (expression (dec depth)) - writes (gen/vector (gen/tuple (gen/elements '[x y]) child) 0 3)] - (gen/one-of - [leaf - (gen/let [a child b child] {:op :add :left a :right b}) - (gen/let [a child b child] (sequence-of a b)) - (gen/let [test gen/boolean then child else child] - {:op :if :test (lit test) :then then :else else}) - (gen/let [tag (gen/elements [:a :b :c]) value child] (event tag value)) - (gen/let [writes writes] (sequence-of {:op :setq :writes writes} (read-var 'x))) - (gen/let [writes writes] (sequence-of {:op :psetq :writes writes} (read-var 'y)))]))))) - (deftest generated-assignment-combinations (let [property (prop/for-all [source (expression 4)] (let [lowered (lower/lower source)] diff --git a/test/com/tailrecursion/nanopass/check.clj b/test/com/tailrecursion/nanopass/check.clj index 9bdfb0d..5b6892c 100644 --- a/test/com/tailrecursion/nanopass/check.clj +++ b/test/com/tailrecursion/nanopass/check.clj @@ -1,6 +1,6 @@ (ns com.tailrecursion.nanopass.check "Compile-time probes for generated recursive languages." - (:require [clojure.test :refer [deftest is run-tests]] + (:require [clojure.test :refer [deftest is]] [clojure.core.typed :as checker] [typed.clojure :as t] [com.tailrecursion.nanopass :as np] @@ -9,7 +9,7 @@ [com.tailrecursion.nanopass.fixtures :as f] [com.tailrecursion.nanopass.passes :as p] [com.tailrecursion.nanopass.clients.assignment :as assignment] - [com.tailrecursion.nanopass.assignment-test :as semantics])) + [com.tailrecursion.assignment-model :as semantics])) (defn check-form [form expected] (binding [*ns* (the-ns 'com.tailrecursion.nanopass.check) @@ -17,12 +17,15 @@ (checker/check-form-info form :expected expected :type-provided? true :check-config {:check-form-eval :never}))) -(defn accepts? [expected form accepted] - (let [{:keys [ex delayed-errors]} (check-form (list 'quote form) expected) +(defn checks? [expected form accepted] + (let [{:keys [ex delayed-errors]} (check-form form expected) errors (concat delayed-errors (:errors (ex-data ex)))] (is (or (nil? ex) (= :top-level-error (:type-error (ex-data ex)))) (str ex)) (is (= accepted (empty? errors)) (pr-str [form errors])))) +(defn accepts? [expected form accepted] + (checks? expected (list 'quote form) accepted)) + (deftest recursive-languages (doseq [[accepted form] [[true {:op :literal :value '{:op :assign :value Expr}}] @@ -58,8 +61,7 @@ (deftest checked-passes (is (t/check-ns-clj 'com.tailrecursion.nanopass.pipeline)) (is (t/check-ns-clj 'com.tailrecursion.nanopass.passes)) - (is (t/check-ns-clj 'com.tailrecursion.nanopass.clients.assignment)) - (is (t/check-ns-clj 'com.tailrecursion.nanopass.clients.flow))) + (is (t/check-ns-clj 'com.tailrecursion.nanopass.clients.assignment))) (deftest pipeline-contracts (doseq [[accepted form] @@ -75,11 +77,7 @@ (->> [state tree] (pipeline/map-value p/lower) (apply (fn [state tree] [tree state]))))]]] - (let [{:keys [ex delayed-errors]} - (check-form form '[t/Int f/Source-Expr :-> (t/HVec [t/Int f/Core-Expr])]) - errors (concat delayed-errors (:errors (ex-data ex)))] - (is (or (nil? ex) (= :top-level-error (:type-error (ex-data ex)))) (str ex)) - (is (= accepted (empty? errors)) (pr-str [form errors]))))) + (checks? '[t/Int f/Source-Expr :-> (t/HVec [t/Int f/Core-Expr])] form accepted))) (defn generated-function [clause] (let [[_ _ _ args body] @@ -104,10 +102,7 @@ [false (generated-function 'node)] [false (generated-function '{:op :write :name 42 :value (p/lower (:value node))})] [false '(fn [node] (p/lower (p/lower node)))]]] - (let [{:keys [ex delayed-errors]} (check-form form '[f/Source-Expr :-> f/Core-Expr]) - errors (concat delayed-errors (:errors (ex-data ex)))] - (is (or (nil? ex) (= :top-level-error (:type-error (ex-data ex)))) (str ex)) - (is (= accepted (empty? errors)) (pr-str [form errors])))))) + (checks? '[f/Source-Expr :-> f/Core-Expr] form accepted)))) (deftest recursive-processor-bodies-are-checked (doseq [[accepted value] [[true '(:value node)] [false 'node]]] @@ -125,11 +120,8 @@ [head bindings signatures] (binding [*ns* (the-ns 'com.tailrecursion.nanopass.check)] (macroexpand-1 (cons 'np/defpasses definitions))) - form (list head bindings signatures 'expression) - {:keys [ex delayed-errors]} (check-form form '[f/Source-Binding :-> f/Core-Binding]) - errors (concat delayed-errors (:errors (ex-data ex)))] - (is (or (nil? ex) (= :top-level-error (:type-error (ex-data ex)))) (str ex)) - (is (= accepted (empty? errors)) (pr-str errors))))) + form (list head bindings signatures 'expression)] + (checks? '[f/Source-Binding :-> f/Core-Binding] form accepted)))) (deftest assignment-contract-probes (doseq [form @@ -143,10 +135,7 @@ (fn [node] (case (:op node) :const node ((fn [^{:typed.clojure/- typed.clojure/Nothing} missing] (throw (ex-info "unhandled" {:node missing}))) node)))]] - (let [{:keys [ex delayed-errors]} (check-form form '[assignment/Source-Expr :-> assignment/Core-Expr]) - errors (concat delayed-errors (:errors (ex-data ex)))] - (is (or (nil? ex) (= :top-level-error (:type-error (ex-data ex)))) (str ex)) - (is (seq errors) (pr-str form))))) + (checks? '[assignment/Source-Expr :-> assignment/Core-Expr] form false))) (deftest structural-types-do-not-prove-order (let [form '(fn [node] @@ -160,8 +149,3 @@ (is (empty? delayed-errors)) (is (= {'x 2 'y 2} (:vars (semantics/execute (wrong source) {'x 1 'y 2})))) (is (= {'x 2 'y 1} (:vars (semantics/execute (assignment/lower source) {'x 1 'y 2})))))) - -(defn -main [& _] - (let [{:keys [fail error]} (run-tests 'com.tailrecursion.nanopass.check)] - (shutdown-agents) - (when (pos? (+ fail error)) (System/exit 1)))) diff --git a/test/com/tailrecursion/nanopass/clients/flow.clj b/test/com/tailrecursion/nanopass/clients/flow.clj deleted file mode 100644 index 582b71e..0000000 --- a/test/com/tailrecursion/nanopass/clients/flow.clj +++ /dev/null @@ -1,112 +0,0 @@ -(ns ^:typed.clojure com.tailrecursion.nanopass.clients.flow - "Lexical binding followed by CFG construction, with immutable explicit state. - This independent toy language has integer conditions: zero is false." - (:require [com.tailrecursion.nanopass :as np] - [com.tailrecursion.nanopass.clients.flow-languages :as l] - [typed.clojure :as-alias t])) - -(np/defpasses - (bind-exprs - {:from [l/Syntax Exprs] :to (t/HVec [t/Int (t/Vec l/Bound-Expr)]) - :args [(t/Map t/Sym t/Sym) t/Int] :body true} - [env supply forms] - (reduce (fn [^{::t/- (t/HVec [t/Int (t/Vec l/Bound-Expr)])} acc ^{::t/- l/Syntax-Expr} form] - (let [[supply out] acc [supply form] (bind-expr env supply form)] - [supply (conj out form)])) [supply []] forms)) - - (bind-local - {:from [l/Syntax Binding] :to (t/HVec [t/Int l/Bound-Binding]) - :args [(t/Map t/Sym t/Sym) t/Int] :body true} - [env supply node] - (let [[supply init] (bind-expr env supply (:value node))] - [(inc supply) {:op :binding :id (symbol (str "local__" supply)) :value init}])) - - (bind-expr - {:from [l/Syntax Expr] :to (t/HVec [t/Int l/Bound-Expr]) :args [(t/Map t/Sym t/Sym) t/Int]} - [env supply node] - :int [supply node] - :read [supply {:op :ref :id (or (get env (:name node)) (throw (ex-info "Unbound name" {:name (:name node)})))}] - :set (let [id (or (get env (:name node)) (throw (ex-info "Unbound name" {:name (:name node)}))) - [supply value] (bind-expr env supply (:value node))] - [supply {:op :write :id id :value value}]) - :plus (let [[supply left] (bind-expr env supply (:left node)) - [supply right] (bind-expr env supply (:right node))] - [supply {:op :plus :left left :right right}]) - :let (let [[supply local] (bind-local env supply (:binding node)) - env (assoc env (:name (:binding node)) (:id local)) - [supply body] (bind-expr env supply (:body node))] - [supply {:op :let :binding local :body body}]) - :if (let [[supply test] (bind-expr env supply (:test node)) - [supply yes] (bind-expr env supply (:then node)) - [supply no] (bind-expr env supply (:else node))] - [supply {:op :if :test test :then yes :else no}]) - :while (let [[supply test] (bind-expr env supply (:test node)) - [supply body] (bind-expr env supply (:body node))] - [supply {:op :while :test test :body body}]) - :do (let [[supply forms] (bind-exprs env supply (:forms node))] - [supply {:op :do :forms forms}]))) - -(np/defpass fresh-block {:from [l/Machine Builder] :to (t/HVec [l/Machine-Builder t/Int]) :body true} - [state] - [(assoc state :next (inc (:next state))) (:next state)]) - -(np/defpass fresh-value {:from [l/Machine Builder] :to (t/HVec [l/Machine-Builder t/Sym]) :body true} - [state] - [(assoc state :next-value (inc (:next-value state))) (symbol (str "value__" (:next-value state)))]) - -(np/defpass emit-op {:from [l/Machine Operation] :to [l/Machine Builder] :args [l/Machine-Builder] :body true} - [state op] - (assoc state :ops (conj (:ops state) op))) - -(np/defpass seal {:from [l/Machine Term] :to [l/Machine Builder] :args [l/Machine-Builder] :body true} - [state term] - (assoc state :blocks (assoc (:blocks state) (:current state) {:ops (:ops state) :term term}) :ops [])) - -(np/defpass start {:from [l/Machine Builder] :to [l/Machine Builder] :args [t/Int] :body true} - [id state] - (assoc state :current id :ops [])) - -(np/defpasses - (lower-exprs - {:from [l/Bound Exprs] :to (t/HVec [l/Machine-Builder l/Machine-Operand]) :args [l/Machine-Builder] :body true} - [state forms] - (reduce (fn [^{::t/- (t/HVec [l/Machine-Builder l/Machine-Operand])} acc ^{::t/- l/Bound-Expr} form] - (lower (first acc) form)) [state {:op :literal :value 0}] forms)) - - (lower - {:from [l/Bound Expr] :to (t/HVec [l/Machine-Builder l/Machine-Operand]) :args [l/Machine-Builder]} - [state node] - :int [state {:op :literal :value (:value node)}] - :ref (let [[state id] (fresh-value state)] - [(emit-op state {:op :put :id id :value {:op :register :id (:id node)}}) {:op :register :id id}]) - :write (let [[state value] (lower state (:value node))] - [(emit-op state {:op :put :id (:id node) :value value}) value]) - :plus (let [[state left] (lower state (:left node)) - [state right] (lower state (:right node)) - [state id] (fresh-value state)] - [(emit-op state {:op :add :id id :left left :right right}) {:op :register :id id}]) - :let (let [local (:binding node) [state init] (lower state (:value local))] - (lower (emit-op state {:op :put :id (:id local) :value init}) (:body node))) - :do (lower-exprs state (:forms node)) - :if (let [[state test] (lower state (:test node)) - [state yes] (fresh-block state) [state no] (fresh-block state) [state join] (fresh-block state) - [state result] (fresh-value state) - state (seal state {:op :branch :test test :yes yes :no no}) - [state a] (lower (start yes state) (:then node)) - state (seal (emit-op state {:op :put :id result :value a}) {:op :jump :target join}) - [state b] (lower (start no state) (:else node)) - state (seal (emit-op state {:op :put :id result :value b}) {:op :jump :target join})] - [(start join state) {:op :register :id result}]) - :while (let [[state header] (fresh-block state) [state body] (fresh-block state) [state exit] (fresh-block state) - state (seal state {:op :jump :target header}) - [state test] (lower (start header state) (:test node)) - state (seal state {:op :branch :test test :yes body :no exit}) - [state _] (lower (start body state) (:body node)) - state (seal state {:op :jump :target header})] - [(start exit state) {:op :literal :value 0}]))) - -(np/defpass compile-program {:from [l/Syntax Expr] :to [l/Machine Graph] :body true} - [source] - (let [[_ source] (bind-expr {} 0 source) - [state value] (lower {:next 1 :current 0 :next-value 0 :ops [] :blocks {}} source)] - {:entry 0 :blocks (:blocks (seal state {:op :return :value value}))})) diff --git a/test/com/tailrecursion/nanopass/clients/flow_languages.clj b/test/com/tailrecursion/nanopass/clients/flow_languages.clj deleted file mode 100644 index cf279db..0000000 --- a/test/com/tailrecursion/nanopass/clients/flow_languages.clj +++ /dev/null @@ -1,35 +0,0 @@ -(ns com.tailrecursion.nanopass.clients.flow-languages - "Source, bound, and graph contracts for the independent flow compiler client." - (:require [com.tailrecursion.nanopass :as np] - [typed.clojure :as-alias t])) - -(np/deflanguage Syntax - {Expr (t/U (t/HMap :mandatory {:op ':int :value t/Int :note t/Any} :complete? true) - (t/HMap :mandatory {:op ':read :name t/Sym} :complete? true) - (t/HMap :mandatory {:op ':set :name t/Sym :value Expr} :complete? true) - (t/HMap :mandatory {:op ':plus :left Expr :right Expr} :complete? true) - (t/HMap :mandatory {:op ':let :binding Binding :body Expr} :complete? true) - (t/HMap :mandatory {:op ':if :test Expr :then Expr :else Expr} :complete? true) - (t/HMap :mandatory {:op ':while :test Expr :body Expr} :complete? true) - (t/HMap :mandatory {:op ':do :forms Exprs} :complete? true)) - Binding (t/HMap :mandatory {:op ':binding :name t/Sym :value Expr} :complete? true) - Exprs (t/Vec Expr)}) - -(np/derive-language Bound Syntax - {:remove {Expr #{:read :set}} - :add {Expr [(t/HMap :mandatory {:op ':ref :id t/Sym} :complete? true) - (t/HMap :mandatory {:op ':write :id t/Sym :value Expr} :complete? true)]} - :replace {Binding (t/HMap :mandatory {:op ':binding :id t/Sym :value Expr} :complete? true)}}) - -(np/deflanguage Machine - {Operand (t/U (t/HMap :mandatory {:op ':literal :value t/Int} :complete? true) - (t/HMap :mandatory {:op ':register :id t/Sym} :complete? true)) - Operation (t/U (t/HMap :mandatory {:op ':put :id t/Sym :value Operand} :complete? true) - (t/HMap :mandatory {:op ':add :id t/Sym :left Operand :right Operand} :complete? true)) - Term (t/U (t/HMap :mandatory {:op ':jump :target t/Int} :complete? true) - (t/HMap :mandatory {:op ':branch :test Operand :yes t/Int :no t/Int} :complete? true) - (t/HMap :mandatory {:op ':return :value Operand} :complete? true)) - Block (t/HMap :mandatory {:ops (t/Vec Operation) :term Term} :complete? true) - Graph (t/HMap :mandatory {:entry t/Int :blocks (t/Map t/Int Block)} :complete? true) - Builder (t/HMap :mandatory {:next t/Int :current t/Int :next-value t/Int - :ops (t/Vec Operation) :blocks (t/Map t/Int Block)} :complete? true)}) diff --git a/test/com/tailrecursion/nanopass/flow_test.clj b/test/com/tailrecursion/nanopass/flow_test.clj deleted file mode 100644 index d5ca22a..0000000 --- a/test/com/tailrecursion/nanopass/flow_test.clj +++ /dev/null @@ -1,102 +0,0 @@ -(ns com.tailrecursion.nanopass.flow-test - "Execute a client's graphs against independent arithmetic and scope results. - This bounded VM is test instrumentation, not a library or Loophole backend." - (:require [clojure.test :refer [deftest is]] - [clojure.test.check.clojure-test :refer [defspec]] - [clojure.test.check.generators :as gen] - [clojure.test.check.properties :as prop] - [com.tailrecursion.nanopass.clients.flow :as flow])) - -(defn number-node [n] {:op :int :value n :note '{:op :read :name opaque}}) -(defn read-node [name] {:op :read :name name}) -(defn plus [a b] {:op :plus :left a :right b}) -(defn set-node [name value] {:op :set :name name :value value}) -(defn let-node [name value body] {:op :let :binding {:op :binding :name name :value value} :body body}) -(defn forms [& nodes] {:op :do :forms (vec nodes)}) - -(defn execute [{:keys [entry blocks]}] - (let [value (fn [registers operand] - (case (:op operand) - :literal (:value operand) - :register (let [id (:id operand)] - (when-not (contains? registers id) - (throw (ex-info "Uninitialized register" {:id id}))) - (get registers id))))] - (loop [pc entry registers {} steps 0] - (when (> steps 10000) (throw (ex-info "Nonterminating test graph" {:pc pc}))) - (let [{:keys [ops term] :as block} (get blocks pc) - _ (when-not block (throw (ex-info "Missing block" {:pc pc}))) - registers (reduce (fn [registers op] - (assoc registers (:id op) - (case (:op op) - :put (value registers (:value op)) - :add (+ (value registers (:left op)) (value registers (:right op)))))) - registers ops)] - (case (:op term) - :return (value registers (:value term)) - :jump (recur (:target term) registers (inc steps)) - :branch (recur (if (zero? (value registers (:test term))) (:no term) (:yes term)) - registers (inc steps))))))) - -(defn sum-program [n] - (let-node 'n (number-node n) - (let-node 'total (number-node 0) - (forms {:op :while :test (read-node 'n) - :body (forms (set-node 'total (plus (read-node 'total) (read-node 'n))) - (set-node 'n (plus (read-node 'n) (number-node -1))))} - (read-node 'total))))) - -(deftest contextual-bindings-and-snapshots - (let [source (let-node 'x (number-node 7) - (plus (let-node 'x (plus (read-node 'x) (number-node 1)) (read-node 'x)) - (read-node 'x))) - [supply bound] (flow/bind-expr {} 0 source)] - (is (= 2 supply)) - (is (= 15 (execute (flow/compile-program source)))) - (is (not= (get-in bound [:binding :id]) (get-in bound [:body :left :binding :id]))) - (is (= '{:op :read :name opaque} (get-in bound [:binding :value :note])))) - (is (= 17 (execute (flow/compile-program - (let-node 'x (number-node 7) - (plus (read-node 'x) (set-node 'x (number-node 10)))))))) - (is (thrown-with-msg? clojure.lang.ExceptionInfo #"Unbound name" - (flow/compile-program (read-node 'missing))))) - -(deftest joins-backedges-and-repeated-execution - (doseq [n (range 31)] - (let [program (sum-program n) graph (flow/compile-program program)] - (is (= (reduce + (range (inc n))) (execute graph) (execute graph))) - (is (= graph (flow/compile-program program))))) - (doseq [n (range 10)] - (let [source (let-node 'x (number-node n) - (forms {:op :if :test (read-node 'x) - :then (set-node 'x (plus (read-node 'x) (number-node 4))) - :else (set-node 'x (number-node 19))} - (read-node 'x)))] - (is (= (if (zero? n) 19 (+ n 4)) (execute (flow/compile-program source))))))) - -(defn inconvenient-program [n initial pivot bias offset] - (let-node 'n (number-node n) - (let-node 'a (number-node initial) - (forms - {:op :while :test (read-node 'n) - :body (forms - (let-node 'snapshot (read-node 'a) - {:op :if :test (plus (read-node 'n) (number-node (- pivot))) - :then (set-node 'a (plus (read-node 'a) - (set-node 'a (plus (read-node 'n) (number-node offset))))) - :else (set-node 'a (plus (read-node 'snapshot) - (let-node 'a (read-node 'snapshot) - (set-node 'a (plus (read-node 'a) (number-node bias))))))}) - (set-node 'n (plus (read-node 'n) (number-node -1))))} - (read-node 'a))))) - -(defspec generated-scope-and-control-combinations {:num-tests 250 :seed 271828} - (prop/for-all [n (gen/choose 0 12) initial (gen/choose -5 5) - pivot (gen/choose 0 15) bias (gen/choose -3 3) offset (gen/choose -3 3)] - (let [source (inconvenient-program n initial pivot bias offset) - expected (loop [i n result initial] - (if (zero? i) result - (recur (dec i) (if (= i pivot) (+ result result bias) (+ result i offset)))))] - (every? true? - (for [variant [source (forms source) (let-node 'unused (number-node 999) source)]] - (= expected (execute (flow/compile-program variant)))))))) diff --git a/test/com/tailrecursion/test_runner.clj b/test/com/tailrecursion/test_runner.clj index 9ffa39f..abd6467 100644 --- a/test/com/tailrecursion/test_runner.clj +++ b/test/com/tailrecursion/test_runner.clj @@ -6,7 +6,6 @@ '[com.tailrecursion.nanopass.language-test com.tailrecursion.nanopass.pass-test com.tailrecursion.nanopass.assignment-test - com.tailrecursion.nanopass.flow-test com.tailrecursion.blacktide.machine-test com.tailrecursion.blacktide.backend-test com.tailrecursion.blacktide.numeric-test