Below is the executable code for generating the Fibonacci numbers in SML. You can directly copy paste the source code in sml to compile and run. If any issues, kindly submit the form below specifying the errors.
s(* To Compile : Login to sml, type sml <nameoffile.sml> *)
(************************* SAMPLE PROGRAM ***********************)
The program is used to calculate Fibonacci(number), in the sample program, number = 16;
Fib(n) = 0 n=0
Fib(n) = 1 n=1
Fib(n) = Fib(n-1)+fib(n-2) n>1
PROGRAM fib
{
number Integer; result Integer; i Integer; first Integer; second Integer; temp Integer;
number = 16;
IF (number Eq 0) THEN result=0
ELSE
{
IF (number Eq 1) THEN result=1
ELSE
{
first = 0; second = 1; i = 1; REPEAT
temp = second;
second = second Plus first; first = temp; i = i Plus 1; UNTIL (i Eq number)
result = second;
}
}
}
******************SAMPLE PROGRAM REVISED******************
IF (number Eq 0) THEN result=0
ELSE
{
IF (number Eq 1) THEN result=1
ELSE
{
first = 0; second = 1; i = 1; REPEAT
temp = second;
second = second Plus first; first = temp; i = i Plus 1; UNTIL (i Eq number)
result = second;
}
}
*********************** END OF SAMLE PROGRAM **********************
(***************STEP1 – GRAAL like data type definition****************)
datatype Variable = id of string;
type Integer_constant = int;
type Boolean_constant = bool;
datatype Arithmetic_op = Plus | Minus | Times | Div;
datatype Relational_op = Lt | Le | Eq | Ne | Ge | Gt;
datatype Boolean_op = And | Or | Nand | Nor | Xor;
datatype Operator = bool_op of Boolean_op |
rel_op of Relational_op |
arith_op of Arithmetic_op;
datatype Expression = int_const of Integer_constant |
bool_const of Boolean_constant |
vExp of Variable |
bExp of Expression * Expression * Operator;
datatype Instruction = skip |
Assignment of Variable * Expression |
Compound of Instruction list |
Conditional of Instruction * Instruction * Expression |
Loop of Instruction * Expression;
datatype Type = Boolean_type | Integer_type;
type Declaration = Variable * Type;
type Declaration_list = Declaration list;
type Program = Declaration_list * Instruction;
val number = id(“number”);
val result = id(“result”);
val i = id(“i”);
val first = id(“first”);
val second = id(“second”);
val temp = id(“temp”);
val my_dec_list = [(number, Integer_type),
(result, Integer_type),
(i, Integer_type),
(first, Integer_type),
(second, Integer_type),
(temp, Integer_type)];
val a1 = Assignment(number,int_const(16)); (** Change number here for generating Fib series**)
val a2 = Assignment(first,int_const(0));
val a3 = Assignment(second,int_const(1));
val a4 = Assignment(i,int_const(1));
val loop_body = Compound([(Assignment(temp,vExp(second))),
(Assignment(second,bExp(vExp(second),vExp(first),arith_op(Plus)))),
(Assignment(first,vExp(temp))),
(Assignment(i,bExp(vExp(i),int_const(1),arith_op(Plus))))]);
val loop_test = bExp(vExp(i), vExp(number), rel_op(Ne));
val loop_main = Loop (loop_body, loop_test);
val a5 = Assignment(result, vExp(second));
val thenbranch_inner = Assignment(result, int_const(1));
val elsebranch_inner = Compound[a2, a3, a4, loop_main, a5];
val test_inner = bExp(vExp(number), int_const(1), rel_op(Eq));
val inner = Conditional(thenbranch_inner, elsebranch_inner, test_inner);
val thenbranch_outer = Assignment(result, int_const(0));
val elsebranch_outer = inner;
val test_outer = bExp(vExp(number), int_const(0), rel_op(Eq));
val outer = Conditional(thenbranch_outer, elsebranch_outer, test_outer);
val my_ins_list = Compound([a1, outer]);
val fib = (my_dec_list, my_ins_list);
(******************END of STEP1 – Data Definition **********************)
(****************** BEGIN STEP2 – Static Semantics ********************)
fun num_of_occurrences([], v:Variable) = 0 |
num_of_occurrences((x:Variable, t:Type)::dec_list_tail, v:Variable)=
let val M = ( if x=v then 1 else 0 ) in M+num_of_occurrences(dec_list_tail, v)
end;
(* Check validity of Variables. Variable can only be declared once. *)
fun Vdec_list([]) = true |
Vdec_list((v:Variable, t:Type)::dec_list_tail) = (num_of_occurrences(dec_list_tail, v) = 0)
andalso Vdec_list(dec_list_tail);
val test_Vdec_t = Vdec_list(my_dec_list);
(* Bad case testing, Variables repeated more than once*)
val test_Vdec_f1 = Vdec_list([(id(“aa”), Integer_type),
(id(“bb”), Integer_type),
(id(“cc”), Integer_type),
(id(“aa”), Integer_type)]);
val test_Vdec_f2 = Vdec_list([(id(“aa”), Integer_type),
(id(“bb”), Integer_type),
(id(“cc”), Integer_type),
(id(“aa”), Boolean_type)]);
(* TypeValue *)
datatype TypeValue = intt | boolt | undefinedt;
(* TypeMap *)
type TypeMap = (Variable*TypeValue) list;
(* Declare a function to create a TypeMap *)
val rec Typing = fn ([]) => [] |
((v:Variable, t:Type)::dec_list_tail) =>
let val M = (if t = Integer_type then intt else boolt)
in (v, M)::Typing(dec_list_tail)
end;
val test_my_Typing = Typing(my_dec_list);
(* Location *)
type Location = int;
(* Environment *)
type Environment = Variable -> Location;
(* Create Environment for a declaration list *)
fun createEnvironment([]) = (fn (x:Variable)=> 0) |
createEnvironment((v:Variable, t:Type)::dec_list_tail) = (fn(x:Variable) =>
if x=v then 1+length(dec_list_tail)
else createEnvironment(dec_list_tail)(x));
(* 9.GetTypeValue *)
fun GetTypeValue([], v:Variable) = undefinedt |
GetTypeValue(((s:Variable, tv:TypeValue)::tail), v:Variable) = (if v=s then tv
else GetTypeValue(tail, v));
val test_my_GTV = GetTypeValue(test_my_Typing, result);
val boolVariable = id(“boolVariable”);
val boolTyping = Typing[(boolVariable, Boolean_type)];
val test_GTV_bool = GetTypeValue(boolTyping, boolVariable);
val undefVariable = id(“undef”);
val undefTyping = Typing[(undefVariable, Integer_type)];
val test_GTV_undef_NotInTM = GetTypeValue(test_my_Typing, undefVariable); (* The variable was not defined in this TypeMap *)
val test_GTV_undef_InTM = GetTypeValue(undefTyping, undefVariable); (* The variable was defined in this TypeMap *)
(* 10.ExpressionType *)
fun ExpressionType(int_const(i), tm:TypeMap) = intt |
ExpressionType(bool_const(b), tm) = boolt |
ExpressionType(vExp(v), tm) = GetTypeValue(tm,v) |
ExpressionType(bExp(e1,e2,arith_op(x)), tm) = intt |
ExpressionType(bExp(e1,e2,rel_op(x)), tm) = boolt |
ExpressionType(bExp(e1,e2,bool_op(x)), tm) = boolt;
(*Good Case TEsting : Define three different kinds of binary expression for testing purpose*)
val expForTest_arith1 = bExp(vExp(second),vExp(first),arith_op(Plus));
val expForTest_arith2 = bExp(vExp(number),vExp(i),arith_op(Minus));
val expForTest_rel = bExp(expForTest_arith2, vExp(result), rel_op(Ne));
val expForTest_bool = bExp(expForTest_rel,bool_const(false),bool_op(Xor));
(* Test cases for ExpressionType*)
val test_ET_intt = ExpressionType(int_const(16), []);
val test_ET_boolt = ExpressionType(bool_const(true), []);
val test_ET_vExp = ExpressionType(vExp(result), test_my_Typing);
val test_ET_bExp_arith = ExpressionType(expForTest_arith2, test_my_Typing); (* arithmetic operation, return intt *)
val test_ET_bExp_rel = ExpressionType(expForTest_rel, test_my_Typing); (* relational operation, return boolt *)
val test_ET_bExp_bool = ExpressionType(expForTest_bool, test_my_Typing); (* boolean operation, return boolt *)
(* 11.VExpression *)
fun VExpression(int_const(i), tm:TypeMap) = true |
VExpression(bool_const(b), tm) = true |
VExpression(vExp(v), tm) = (GetTypeValue(tm, v) <> undefinedt) |
VExpression(bExp(e1,e2,arith_op(_)), tm) = VExpression(e1, tm) andalso
VExpression(e2, tm) andalso
ExpressionType(e1, tm) = intt andalso
ExpressionType(e2, tm) = intt |
VExpression(bExp(e1,e2,rel_op(_)), tm) =
VExpression(e1, tm) andalso
VExpression(e2, tm) andalso
ExpressionType(e1, tm) = intt andalso
ExpressionType(e2, tm) = intt |
VExpression(bExp(e1,e2,bool_op(_)), tm) =
VExpression(e1, tm) andalso
VExpression(e2, tm) andalso
ExpressionType(e1, tm) = boolt andalso
ExpressionType(e2, tm) = boolt;
val test_VE_vExp = VExpression(vExp(result), test_my_Typing);
val test_VE_vExp_NotInTM = VExpression(vExp(undefVariable), test_my_Typing);
val test_VE_bExp_arith = VExpression(bExp(expForTest_arith1,expForTest_arith2, arith_op(Plus)), test_my_Typing); (* arithmetic operation *)
val test_VE_bExp_arith_NotInTM = VExpression(bExp(vExp(undefVariable),vExp(first),arith_op(Plus)), test_my_Typing); (* expression types are mathched, but the variable was not defined in this TypeMap *)
val test_VE_bExp_rel = VExpression(expForTest_rel, test_my_Typing); (* relational operation *)
val test_VE_bExp_bool = VExpression(expForTest_bool, test_my_Typing); (* boolean operation, return boolt *)
val test_VE_bExp_nested = VExpression(bExp(expForTest_rel, (bExp(expForTest_arith1,expForTest_arith2, rel_op(Ne))),bool_op(Or)), test_my_Typing);
val test_VE_bad1 = VExpression(bExp(expForTest_arith1, expForTest_rel, arith_op(Plus)), test_my_Typing);
val test_VE_bad2 = VExpression(bExp(expForTest_rel,bExp(vExp(i),int_const(1),arith_op(Plus)),rel_op(Ge)), test_my_Typing);
val test_VE_bad3 = VExpression(bExp(expForTest_bool, expForTest_arith2, bool_op(Or)), test_my_Typing);
(* 12.Vinstruction *)
val rec VInstruction = fn(skip) => ( fn(tm:TypeMap) => true ) |
(Assignment(v,e)) => ( fn(tm) => (GetTypeValue(tm,v) = ExpressionType(e,tm)) andalso
GetTypeValue(tm,v) <> undefinedt andalso
VExpression(e,tm)) |
(Compound([])) => ( fn(tm) => true) |
(Compound(head::tail)) => ( fn(tm) => VInstruction(head)(tm) andalso
VInstruction(Compound(tail))(tm)) |
(Conditional(i1,i2,test)) => ( fn(tm) => VInstruction(i1)(tm) andalso
VInstruction(i2)(tm) andalso
VExpression(test,tm) andalso
(ExpressionType(test,tm) = boolt)) |
(Loop(i,test)) => ( fn(tm) => VInstruction(i)(tm) andalso
VExpression(test,tm) andalso
(ExpressionType(test,tm) = boolt));
val test_VI_Assignment = VInstruction(a1)(test_my_Typing);
val test_VI_Compound = VInstruction(loop_body)(test_my_Typing);
val test_VI_Conditional = VInstruction(inner)(test_my_Typing);
val test_VI_Loop = VInstruction(loop_main)(test_my_Typing);
val test_VI_myIns = VInstruction(my_ins_list)(test_my_Typing);
val test_VI_badTM = VInstruction(a1)(undefTyping); (*bad TypeMap*)
val test_VI_badA = VInstruction(Assignment(boolVariable,int_const(1)))(test_my_Typing); (*bad assignment*)
val test_VI_badCond = VInstruction(Conditional(a1,a2,expForTest_arith1))(test_my_Typing); (*bad expression type for test*)
val test_VI_badLoop = VInstruction(Loop(a1,bExp(expForTest_bool, expForTest_arith2, bool_op(Or))))(test_my_Typing); (*bad expression for test*)
(* 13.Exception *)
exception InvalidDeclist;
(* 14.VProgram *)
fun VProgram(decl:Declaration_list, body:Instruction) = if Vdec_list(decl) then VInstruction(body)(Typing(decl))
else raise InvalidDeclist;
val test_my_prog = VProgram(fib);
(****************** END of STEP2 Static Semantics ****************)
(***************** STEP 3: Dynamic Semantics*********************)
(* [1]. Value *)
datatype Value = IntV of int |
BoolV of bool |
unknown;
(* [2]. Content *)
type Content = Location -> Value;
(* [3]. Program State *)
type PrgState = Variable -> Value;
(* [4]. Content Initial *)
val ContentInitial = (fn l: Location => unknown);
ContentInitial(5);
ContentInitial(10);
ContentInitial(0);
(* [5]. Content Change *)
(* type ContentChange = Content -> Location -> Value -> Location -> Value;*)
fun ContentChange(C1: Content)(l: Location)(vl: Value) =
(fn (ll:Location)=> if ll = l then vl
else C1(ll)
);
(* Testing for [5] : Good Case *)
val mymemory1 = ContentChange(ContentInitial)(5)(IntV(100));
mymemory1(5);
mymemory1(1);
val mymemory2 = ContentChange(mymemory1)(10)(IntV(50));
mymemory2(5);
mymemory2(10);
(* Testing for [5] : Bad Case *)
mymemory1(6);
mymemory2(3);
(* [6]. Exception Handling *)
exception WrongCombintaion;
(* [7]. Binary Operator *)
fun OpBinary(IntV(i), arith_op(Plus), IntV(j)) = IntV(i+j) |
OpBinary(IntV(i), arith_op(Minus), IntV(j))= IntV(i-j) |
OpBinary(IntV(i), arith_op(Times), IntV(j))= IntV(i*j) |
OpBinary(IntV(i), arith_op(Div), IntV(j)) = IntV(i div j) |
OpBinary(IntV(i), rel_op(Lt), IntV(j)) = BoolV(i<j) |
OpBinary(IntV(i), rel_op(Le), IntV(j)) = BoolV(i<=j) |
OpBinary(IntV(i), rel_op(Eq), IntV(j)) = BoolV(i=j) |
OpBinary(IntV(i), rel_op(Ne), IntV(j)) = BoolV(i<>j) |
OpBinary(IntV(i), rel_op(Ge), IntV(j)) = BoolV(i>=j) |
OpBinary(IntV(i), rel_op(Gt), IntV(j)) = BoolV(i>j) |
OpBinary(BoolV(i), bool_op(And), BoolV(j)) = BoolV(i andalso j) |
OpBinary(BoolV(i), bool_op(Or), BoolV(j)) = BoolV(i orelse j) |
OpBinary(_, _, _) = raise WrongCombintaion;
(* Testing Good Case *)
val testOP_good1 = OpBinary(IntV(1), arith_op(Plus), IntV(2));
val testOP_good2 = OpBinary(IntV(1), rel_op(Lt), IntV(2));
val testOP_good3 = OpBinary(BoolV(true), bool_op(Or), BoolV(false));
(*
(* Testing for Bad Cases *)
val opbin_bad0 = OpBinary(BoolV(true), rel_op(Ge), BoolV(false));
val opbin_bad1 = OpBinary(IntV(1), bool_op(And), IntV(2));
val opbin_bad2 = OpBinary(IntV(1), arith_op(Plus), IntV(1));
val opbin_bad3 = OpBinary(BoolV(true),bool_op(And), IntV(1));
val opbin_bad4 = OpBinary(IntV(1), rel_op(Ge), BoolV(false));
val opbin_bad5 = OpBinary(IntV(1), arith_op(MINUS), unknown);
*)
(* [8]. MExpression *)
fun MExpression(int_const(i))(e:Environment, c:Content) = IntV(i) |
MExpression(bool_const(b))(e,c) = BoolV(b)|
MExpression(vExp(v))(e,c) = c(e(v))|
MExpression(bExp(e1,e2,someOp))(e,c) = OpBinary((MExpression(e1)(e,c)),someOp, (MExpression(e2)(e,c)) );
(* Testing for MExpression *)
val my_env = createEnvironment(my_dec_list);
val my_Content_Init = ContentInitial;
(* Good cases *)
val testME_good1 = MExpression(int_const(20))(my_env, my_Content_Init);
val testME_good2 = MExpression(bool_const(true))(my_env, my_Content_Init);
val testME_good3 = MExpression(bExp(int_const(3),int_const(5),arith_op(Times)))(my_env, my_Content_Init);
val testME_good4 = MExpression(bExp(int_const(12),int_const(6),rel_op(Gt)))(my_env, my_Content_Init);
val testME_good5 = MExpression(bExp(bool_const(true),bool_const(false),bool_op(Or)))(my_env, my_Content_Init);
val testME_good6 = MExpression(vExp(number))(my_env, my_Content_Init); (*number has not been assigned to a value yet*)
(* Additional test cases are in the following of the definition of MInstruction *)
(* [9]. MInstruction *)
fun MInstruction(skip)(e:Environment, c: Content) = (e,c) |
MInstruction(Assignment(v, exp))(e,c) = (e, ContentChange(c)(e(v))(MExpression(exp)(e,c))) |
MInstruction(Compound([]) )(e,c) = (e,c) |
MInstruction(Compound(head::tail))(e,c) = MInstruction(Compound(tail))(MInstruction(head)(e,c))|
MInstruction(Conditional(i1, i2, exp))(e,c) = if MExpression(exp)(e,c) = BoolV(true)
then MInstruction(i1)(e,c)
else MInstruction(i2)(e,c) |
MInstruction(Loop(body, exp))(e,c) = if MExpression(exp)(e,c) = BoolV(true)
then MInstruction(Loop(body, exp))(MInstruction(body)(e,c))
else(e,c);
exception BadProgram;
(* test cases for MInstruction and MExpression *)
val testMI_good1 = MInstruction(skip)(my_env, my_Content_Init); (* returns the Environment*Content after execution *)
val testMI_number1 = MExpression(vExp(number))testMI_good1;
val testMI_good2 = MInstruction(Assignment(number, int_const(25)))(my_env, my_Content_Init);
val testMI_number2 = MExpression(vExp(number))testMI_good2;
val testMI_good3 = MInstruction(Compound([]))(my_env, my_Content_Init);
val testMI_number3 = MExpression(vExp(number))testMI_good3;
val testMI_good4 = MInstruction(Compound([Assignment(number, int_const(25)), Assignment(number, int_const(26)), skip]))(my_env, my_Content_Init);
val testMI_number4 = MExpression(vExp(number))testMI_good4;
val testMI_good5 = MInstruction(Conditional(Assignment(number, int_const(12)), Assignment(number, int_const(24)), bool_const(true)))(my_env, my_Content_Init);
val testMI_number5 = MExpression(vExp(number))testMI_good5;
val testMI_good6 = MInstruction(Conditional(Assignment(number, int_const(12)), Assignment(number, int_const(24)), bool_const(false)))(my_env, my_Content_Init);
val testMI_number6 = MExpression(vExp(number))testMI_good6;
(* simple loop:
number = 1;
i = 10;
while (number < i)
number = number + 1;
*)
val simple1 = Compound([Assignment(number, int_const(1)), Assignment(i, int_const(10))]);
val simple_loopbody = Assignment(number, (bExp(vExp(number),int_const(1),arith_op(Plus))));
val simple_looptest = bExp(vExp(number),vExp(i),rel_op(Lt));
val simple_loop = Loop(simple_loopbody, simple_looptest);
val testMI_good7 = MInstruction(Compound([simple1, simple_loop]))(my_env, my_Content_Init);
val testMI_number7 = MExpression(vExp(number))testMI_good7;
fun MProgram(decl:Declaration_list, body:Instruction)= if VProgram(decl, body)
then MInstruction(body)((createEnvironment(decl)), ContentInitial)
else raise BadProgram;
val finalTest = (MProgram(fib));
val finalnumber = MExpression(vExp(number))finalTest;
val finali = MExpression(vExp(i))finalTest;
val finalfirst = MExpression(vExp(first))finalTest;
val finalsecond = MExpression(vExp(second))finalTest;
val finaltemp = MExpression(vExp(temp))finalTest;
val finalresult = MExpression(vExp(result))finalTest;
(******************* End of STEP3 *******************)
Basic Educational Tutorials 