Created
April 23, 2024 10:35
-
-
Save segeljakt/9959febdf4c98bc4345e4d115b73c36b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (datatype Expr | |
| ; Arithmetic | |
| (Num i64) | |
| (Add Expr Expr) | |
| (Var String) | |
| (Let String Expr Expr)) | |
| (function path (Expr Expr) i64 :merge (min old new)) | |
| (function edge (Expr Expr) i64 :merge (min old new)) | |
| ; Map expressions to edges | |
| (rule [(= e (Add a b))] | |
| [(set (edge e a) 1) | |
| (set (edge e b) 1)]) | |
| (rule [(= e (Let x a b))] | |
| [(set (edge a b) 1) | |
| (set (edge b e) 1)]) | |
| ; Shortest path | |
| (rule [(= (edge a b) ab)] | |
| [(set (path a b) ab)]) | |
| (rule [(= (path a b) ab) | |
| (= (edge b c) bc)] | |
| [(set (path a c) (+ ab bc))]) | |
| (push 1) | |
| (let e0 (Num 1)) | |
| (let e1 (Num 2)) | |
| (let e3 (Add e0 e1)) | |
| (let e4 (Add e3 e0)) | |
| (run 10) | |
| (check (= (path e3 e0) 1)) | |
| (check (= (path e3 e1) 1)) | |
| (check (= (path e4 e3) 1)) | |
| (check (= (path e4 e0) 1)) | |
| (check (= (path e4 e1) 2)) | |
| (pop 1) | |
| ; CSE | |
| (rule [(path a b) | |
| (path a c) | |
| (= b c)] | |
| [(union a (Let "x" b a)) | |
| (union b (Var "x")) | |
| (union c (Var "x"))]) | |
| (push 1) | |
| (let e0 (Num 1)) | |
| (let e1 (Num 2)) | |
| (let e3 (Add e0 e1)) | |
| (let e4 (Add e0 e1)) | |
| (let e5 (Add e3 e4)) | |
| ; (1+2) + (1+2) | |
| ; => | |
| ; let x = 1+2 in x+x | |
| (run 10) | |
| (let expected (Let "x" (Add e0 e1) (Add (Var "x") (Var "x")))) | |
| (check (= e5 expected)) | |
| (pop 1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment