CS 425 - Ass 7 (Part 1)

uyuyuy99

Jun 9th, 2025 (edited)

305

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

StandardML 5.84 KB | None | 0 0

raw download clone embed print report

(* Given datatypes *)
datatype term = AST_ID of string
| AST_NUM of int
| AST_TRUE
| AST_FALSE
| AST_SUCC
| AST_PRED
| AST_ISZERO
| AST_IF of term * term * term
| AST_FUN of string * term
| AST_APP of term * term
| AST_LET of string * term * term;
datatype result = RES_ERROR of string
| RES_NUM of int
| RES_TRUE
| RES_FALSE
| RES_SUCC
| RES_PRED
| RES_ISZERO
| RES_FUN of (string * term)
| RES_CLOSURE of (string * term * env)
and env = Env of (string -> result);
(* Helpers previously given, and slightly modified.
You will need to modify these when using static scope
and call-by-name *)
exception UnboundID of string
exception Unimplemented
fun emptyenvFun (x : string) : result = (print (x ^ " is unbound"); raise (UnboundID x));
val emptyenv = Env emptyenvFun
(* This is the environment from the typechecker
Note that it returns string -> result so you will
have to tag the return with Env *)
(* Env -> string -> result -> string -> result *)
fun update (Env e) (x : string) (v: result) y = if x = y then v else e y;
(* Interpret function *)
fun interp (Env env) (AST_ID i) = env i
| interp env (AST_NUM n) = RES_NUM n
| interp env AST_TRUE = RES_TRUE
| interp env AST_FALSE = RES_FALSE
| interp env AST_SUCC = RES_SUCC
| interp env AST_PRED = RES_PRED
| interp env AST_ISZERO = RES_ISZERO
| interp env (AST_IF (b, e1, e2)) =
let
val res = interp env b
in
case res of
RES_TRUE => interp env e1
| RES_FALSE => interp env e2
| _ => RES_ERROR "b must be a bool"
end
| interp env (AST_FUN (i, b)) = RES_FUN (i, b)
| interp env (AST_APP (f, p)) =
let
val res_f = interp env f
val res_p = interp env p
in
case res_f of
RES_SUCC =>
(case res_p of
RES_NUM n => RES_NUM (n + 1)
| _ => RES_ERROR "param must be a number")
| RES_PRED =>
(case res_p of
RES_NUM n =>
if n = 0 then RES_NUM 0
else RES_NUM (n - 1)
| _ => RES_ERROR "param must be a number")
| RES_ISZERO =>
(case res_p of
RES_NUM n =>
if n = 0 then RES_TRUE
else RES_FALSE
| _ => RES_ERROR "param must be a number")
| RES_FUN(param, body) =>
let
val env_new = Env (update env param res_p)
in
interp env_new body
end
| _ => RES_ERROR "f must be a function"
end
| interp env (AST_LET (x, e1, e2)) =
let
val v1 = interp env e1
val env_new = Env (update env x v1)
in
interp env_new e2
end
(* Static-scoped *)
fun interp_static (Env env) (AST_ID i) = env i
| interp_static env (AST_NUM n) = RES_NUM n
| interp_static env AST_TRUE = RES_TRUE
| interp_static env AST_FALSE = RES_FALSE
| interp_static env AST_SUCC = RES_SUCC
| interp_static env AST_PRED = RES_PRED
| interp_static env AST_ISZERO = RES_ISZERO
| interp_static env (AST_IF (b, e1, e2)) =
let
val res = interp_static env b
in
case res of
RES_TRUE => interp_static env e1
| RES_FALSE => interp_static env e2
| _ => RES_ERROR "b must be a bool"
end
| interp_static env (AST_FUN (i, b)) = RES_CLOSURE (i, b, env)
| interp_static env (AST_APP (f, p)) =
let
val res_f = interp_static env f
val res_p = interp_static env p
in
case res_f of
RES_SUCC =>
(case res_p of
RES_NUM n => RES_NUM (n + 1)
| _ => RES_ERROR "param must be a number")
| RES_PRED =>
(case res_p of
RES_NUM n =>
if n = 0 then RES_NUM 0
else RES_NUM (n - 1)
| _ => RES_ERROR "param must be a number")
| RES_ISZERO =>
(case res_p of
RES_NUM n =>
if n = 0 then RES_TRUE
else RES_FALSE
| _ => RES_ERROR "param must be a number")
| RES_FUN(param, body) =>
let
val env_new = Env (update env param res_p)
in
interp_static env_new body
end
| RES_CLOSURE(param, body, env1) =>
let
val env_new = Env (update env1 param res_p)
in
interp_static env_new body
end
| _ => RES_ERROR "f must be a function"
end
| interp_static env (AST_LET (x, e1, e2)) =
let
val v1 = interp_static env e1
val env_new = Env (update env x v1)
in
interp_static env_new e2
end
(* Tests *)
(* ------------ *)
(* Dynamic vs static scope *)
(* let x = 0
in let f = fn z => x
in let x = 100
in f x *)
val test0 = AST_LET ("x", AST_NUM 0,
AST_LET("f",AST_FUN("z",AST_ID "x"),
AST_LET("x",AST_NUM 100,
AST_APP(AST_ID "f", AST_ID "x"))));
val res_test0 = interp_static emptyenv test0;
(* Call-By-Value vs Call-By-Name *)
(* (fn x => 42) ((fn x => x x) (fn x => x x)) *)
val test1 =
AST_APP
(AST_FUN ("x",AST_NUM 42)
,AST_APP
(AST_FUN ("x",AST_APP(AST_ID "x",AST_ID "x"))
,AST_FUN ("x",AST_APP(AST_ID "x",AST_ID "x"))));
val res_test1 = interp emptyenv test1;
(* ((fn x => fn y => x 42) (fn y => y)) 0 *)
val test2 =
AST_APP
(AST_APP
(AST_FUN ("x",AST_FUN ("y", AST_APP (AST_ID "x",AST_NUM 42))) ,AST_FUN ("y",AST_ID "y"))
,AST_NUM 0)
val res_test2 = interp emptyenv test2;
OS.Process.exit(OS.Process.success);

Add Comment

Please, Sign In to add comment