type ID = string; datatype operand = Number of real |VarName of ID |Empty; type variable = ID * operand; (* Opcodes *) datatype opcode = opPush of operand | opAdd | opSub | opMul | opDiv | opGt | opGtEq | opLt | opLtEq | opEq | opNEq | opNeg | opAnd | opOr | opNot | opXor | opBrT of ID| opBrF of ID| opJmp of ID| opPop of ID | Label of ID; datatype arith_exp = Term of operand |Add of arith_exp * arith_exp |Subtract of arith_exp * arith_exp |Multiply of arith_exp * arith_exp |Divide of arith_exp * arith_exp |Negate of arith_exp; datatype bool_exp = Gt of arith_exp * arith_exp |Lt of arith_exp * arith_exp |Eq of arith_exp * arith_exp |LtE of arith_exp * arith_exp |GtE of arith_exp * arith_exp |NEq of arith_exp * arith_exp |And of bool_exp * bool_exp |Or of bool_exp * bool_exp |Xor of bool_exp * bool_exp |Not of bool_exp; datatype statement = Assign of ID * arith_exp |Loop_PreTest of bool_exp * statement list |Loop_PostTest of statement list * bool_exp |Iterate of ID * arith_exp * arith_exp * arith_exp * statement list |If_Then of bool_exp * statement list |If_Then_Else of bool_exp * statement list * statement list; fun setvar([], n:ID, v:operand) = [(n,v)] |setvar(((N, V)::T), n :ID, v :operand) = if N < n then (N,V)::setvar(T, n, v) else if N = n then (N, v)::T else (n,v)::(N,V)::T; fun getvar([], n:ID) = Empty |getvar(((N, V)::T), n:ID) = if N < n then getvar(T, n) else if N = n then V else Empty; fun interpExp(Term(Empty), Vs) = 0.0 |interpExp(Term(Number(r)), Vs) = r |interpExp(Add(A,B), Vs) = interpExp(A, Vs) + interpExp(B, Vs) |interpExp(Subtract(A,B), Vs) = interpExp(A, Vs) - interpExp(B, Vs) |interpExp(Multiply(A,B), Vs) = interpExp(A, Vs) * interpExp(B, Vs) |interpExp(Divide(A,B), Vs) = interpExp(A, Vs) / interpExp(B, Vs) |interpExp(Negate(A), Vs) = ~(interpExp(A, Vs)) |interpExp(Term(VarName(v)), Vs) = interpExp(Term(getvar(Vs, v)), Vs); fun interpBool(Gt(A1, A2), Vs) = interpExp(A1, Vs) > interpExp(A2, Vs) |interpBool(Lt(A1, A2), Vs) = interpExp(A1, Vs) < interpExp(A2, Vs) |interpBool(Eq(A1, A2), Vs) = interpExp(A1, Vs) = interpExp(A2, Vs) |interpBool(LtE(A1, A2), Vs) = interpExp(A1, Vs) <= interpExp(A2, Vs) |interpBool(GtE(A1, A2), Vs) = interpExp(A1, Vs) >= interpExp(A2, Vs) |interpBool(NEq(A1, A2), Vs) = (interpExp(A1, Vs)) <> (interpExp(A2, Vs)) |interpBool(And(A1, A2), Vs) = interpBool(A1, Vs) andalso interpBool(A2, Vs) |interpBool(Or(A1, A2), Vs) = interpBool(A1, Vs) orelse interpBool(A2, Vs) |interpBool(Xor(A1, A2), Vs) = (not (interpBool(A1, Vs)) andalso not (interpBool(A2, Vs))) orelse (interpBool(A1, Vs) andalso interpBool(A2, Vs)) |interpBool(Not(A), Vs) = not (interpBool(A, Vs)); fun interpret([], Vs:variable list) = Vs |interpret((Assign(V, E)::P), Vs) = interpret(P, setvar(Vs, V, Number(interpExp(E, Vs)))) |interpret((If_Then(B, St)::P), Vs) = if interpBool(B, Vs) then interpret(P, interpret(St, Vs)) else interpret(P, Vs) |interpret((If_Then_Else(B, St, Sf)::P), Vs) = if interpBool(B, Vs) then interpret(P, interpret(St, Vs)) else interpret(P, interpret(Sf, Vs)) |interpret((Loop_PreTest(B, S)::P), Vs) = if interpBool(B, Vs) then interpret((Loop_PreTest(B, S)::P), Vs) else interpret(P, Vs) |interpret((Loop_PostTest(S, B)::P), Vs) = let val Vs = interpret(S, Vs) in if interpBool(B, Vs) then interpret((Loop_PostTest(S, B)::P), Vs) else interpret(P, Vs) end |interpret((Iterate(V, L, H, I, S)::P), Vs) = let Vs = setvar(Vs, V, Num(interpExp(L, Vs))) in let NewL = Term(Num(interpExp(Add(L, I), Vs))) in if interpBool(GtE(L, H), Vs) then interpret((Iterate(V, NewL, H, I, S)::P), interpret(S, Vs)) else interpret(P, Vs)) end; load "Int"; open Int; fun compExp(Term(Empty)) = [opPush(Empty)] |compExp(Term(Number(r))) = [opPush(Number(r))] |compExp(Term(VarName(v))) = [opPush(VarName(v))] |compExp(Add(A,B)) = compExp(A) @ compExp(B) @ [opAdd] |compExp(Subtract(A,B)) = compExp(A) @ compExp(B) @ [opSub] |compExp(Multiply(A,B)) = compExp(A) @ compExp(B) @ [opMul] |compExp(Divide(A,B)) = compExp(A) @ compExp(B) @ [opDiv] |compExp(Negate(A)) = compExp(A) @ [opNeg]; fun compBool(Gt(A1, A2)) = compExp(A1) @ compExp(A2) @ [opGt] |compBool(Lt(A1, A2)) = compExp(A1) @ compExp(A2) @ [opLt] |compBool(Eq(A1, A2)) = compExp(A1) @ compExp(A2) @ [opEq] |compBool(LtE(A1, A2)) = compExp(A1) @ compExp(A2) @ [opLtEq] |compBool(GtE(A1, A2)) = compExp(A1) @ compExp(A2) @ [opGtEq] |compBool(NEq(A1, A2)) = compExp(A1) @ compExp(A2) @ [opNEq] |compBool(And(A1, A2)) = compBool(A1) @ compBool(A2) @ [opAnd] |compBool(Or(A1, A2)) = compBool(A1) @ compBool(A2) @ [opOr] |compBool(Xor(A1, A2)) = compBool(A1) @ compBool(A2) @ [opXor] |compBool(Not(A)) = compBool(A) @ [opNot]; fun compile1([], label) = ([], label) |compile1((Assign(V,E)::Prog), label) = let val (prog_ops, label) = compile1(Prog, label) in ( compExp(E) @[opPop(V)] @prog_ops, label ) end |compile1((If_Then(B, St)::Prog), label) = let val DoneLabel = label; val (stmt_ops, label) = compile1(St, label+1); val (prog_ops, label) = compile1(Prog, label) in ( compBool(B) @[opBrF(DoneLabel)] @stmt_ops @[Label(DoneLabel)] @prog_ops, label ) end |compile1((If_Then_Else(B, St, Sf)::Prog), label) = let val ElseLabel = label; val DoneLabel = label+1; val (stmtT_ops, label) = compile1(St, label+2); val (stmtF_ops, label) = compile1(Sf, label); val (prog_ops, label) = compile1(Prog, label) in ( compBool(B) @[opBrF(ElseLabel)] @stmtT_ops @[opJmp(DoneLabel)] @[Label(ElseLabel)] @stmtF_ops @[Label(DoneLabel)] @prog_ops, label) end |compile1((Loop_PreTest(B, St)::Prog), label) = let val TestLabel = label; val DoneLabel = label+1; val (stmt_ops, label) = compile1(St, label+2); val (prog_ops, label) = compile1(Prog, label) in ( [Label(TestLabel)] @compBool(B) @[opBrF(DoneLabel)] @stmt_ops @[opJmp(TestLabel)] @[Label(DoneLabel)] @prog_ops, label ) end |compile1((Loop_PostTest(St, B)::Prog), label) = let val TestLabel = label; val (stmt_ops, label) = compile1(St, label+1); val (prog_ops, label) = compile1(Prog, label) in ( [Label(TestLabel)] @stmt_ops @compBool(B) @[opBrT(TestLabel)] @prog_ops, label) end |compile1((Iterate(V, El, Eh, Ei, St)::Prog), label) = let val AssignLabel = label; val DoneLabel = label+1; val (stmt_ops, label) = compile1(St, label+2); val (prog_ops, label) = compile1(Prog, label) in ( compExp(El) @[Label(AssignLabel)] @[opPop(V)] @compExp(Eh) @[opPush(VarName(V))] @[opGt] @[opBrT(DoneLabel)] @stmt_ops @compExp(Ei) @[opPush(VarName(V))] @[opAdd] @[opJmp(AssignLabel)] @[Label(DoneLabel)] @prog_ops, label ) end; fun compile(Prog) = let val (oplist, lbl) = compile1(Prog, "main", 0) in oplist end; fun findLabel([], L) = [] |findLabel((Label(l)::P), L) = if l = L then P else findLabel(P, L) |findLabel((_::P), L) = findLabel(P, L); (*fun evaluate(wholeprogram, current, state, stack) *) load "Real"; open Real; fun evaluate1(_, [], S, _) = S |evaluate1(WP, (opPush(Empty)::P), S, Q) = evaluate1(WP, P, S, Q) |evaluate1(WP, (opPush(Number(V))::P), S, Q) = evaluate1(WP, P, S, [Number(V)]@Q) |evaluate1(WP, (opPush(VarName(V))::P), S, Q) = evaluate1(WP, P, S, [getvar(S,V)]@Q) |evaluate1(WP, (opAdd::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(op1+op2)]@Q) |evaluate1(WP, (opSub::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(op1-op2)]@Q) |evaluate1(WP, (opDiv::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(op1/op2)]@Q) |evaluate1(WP, (opMul::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(op1*op2)]@Q) |evaluate1(WP, (opGt::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if op1op2 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opLtEq::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if op1<=op2 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opEq::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if op1=op2 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opNEq::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if op1<>op2 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opNeg::P), S, (Number(op1)::Q)) = evaluate1(WP, P, S, [Number(~op1)]@Q) |evaluate1(WP, (opNot::P), S, (Number(op1)::Q)) = evaluate1(WP, P, S, [Number(if op1<>0.0 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opAnd::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if op1<>0.0 andalso op2<>0.0 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opOr::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if op1<>0.0 orelse op2<>0.0 then 1.0 else 0.0)]@Q) |evaluate1(WP, (opXor::P), S, (Number(op1)::Number(op2)::Q)) = evaluate1(WP, P, S, [Number(if (op1<>0.0 andalso op2<>0.0) orelse (op1=0.0 andalso op2=0.0) then 1.0 else 0.0)]@Q) |evaluate1(WP, (opBrT(L)::P), S, (Number(op1)::Q)) = evaluate1(WP, (if op1<>0.0 then findLabel(WP,L) else P), S, Q) |evaluate1(WP, (opBrF(L)::P), S, (Number(op1)::Q)) = evaluate1(WP, (if op1=0.0 then findLabel(WP,L) else P), S, Q) |evaluate1(WP, (opJmp(L)::P), S, Q) = evaluate1(WP, findLabel(WP,L), S, Q) |evaluate1(WP, (opPop(V)::P), S, (op1::Q)) = evaluate1(WP, P, setvar(S, V, op1), Q) |evaluate1(WP, (Label(_)::P), S, Q) = evaluate1(WP, P, S, Q) |evaluate1(WP, (_::P), S, (Number(op1)::[])) = evaluate1(WP, P, S, [Number(op1)]) |evaluate1(WP, (_::P), S, []) = evaluate1(WP, P, S, []); fun evaluate(P) = evaluate1(P, P, [], []); fun statesEqual([], []) = true |statesEqual([], _) = false |statesEqual(_, []) = false |statesEqual(((N1,V1)::L1),((N2,V2)::L2)) = N1=N2 andalso V1=V2 andalso statesEqual(L1,L2); val prog = [ (* x2 = x^2 *) Assign("x2", Multiply(Term(VarName("x")), Term(VarName("x")))), (* if x2 < x*2+1 then x = 50 if x == 0 then y = 10 else y = -10 *) If_Then(Gt(Term(VarName("x2")),Add(Multiply(Term(VarName("x")),Term(Number(2.0))),Term(Number(1.0)))),[ Assign("x", Term(Number(50.0))), If_Then_Else(Eq(Term(VarName("x")),Term(Number(0.0))),[ Assign("y",Term(Number(10.0)))],[ Assign("y",Term(Number(~10.0)))]) ]), (* while z < 100 z = z + 1 do z = z - 1 while z < 1000 *) Loop_PreTest(Lt(Term(VarName("z")),Term(Number(1.0))), [ Assign("z", Add(Term(VarName("z")),Term(Number(1.0)))), Loop_PostTest([Assign("z",Subtract(Term(VarName("z")),Term(Number(1.0))))],Lt(Term(VarName("z")),Term(Number(1000.0)))) ]) (* term = x^2/3! *) Assign("term", Divide(Term(VarName("x2")), Multiply(Term(Number(2.0)), Term(Number(3.0))))), (* sin = 1 *) Assign("sin", Term(Number(1.0))), (* sin = sin - term *) Assign("sin", Subtract(Term(VarName("sin")),Term(VarName("term")))), (* term = (term*(x^2))/(4*5) *) Assign("term", Divide(Multiply(Term(VarName("term")), Term(VarName("x2"))), Multiply(Term(Number(4.0)), Term(Number(5.0))))), (* sin = sin + term *) Assign("sin", Add(Term(VarName("sin")), Term(VarName("term")))), (* sin = term*x *) Assign("sin", Multiply(Term(VarName("term")), Term(VarName("x")))), If_Then(Gt(Term(VarName("x")),Term(Number(0.0))), [Assign("TEST", Term(Number(100.0)))]), If_Then_Else(Lt(Term(VarName("x")),Term(Number(0.0))), [Assign("TEST2", Term(Number(200.0)))], [Assign("TEST2", Term(Number(300.0)))]) ];