Roots
This post is in celebration of receiving an A in a humanities course (and a projected D in Computer Science, but their grading is screwed up and they are fixing it right now).
I figured it would be nice to re-affirm that I am still a "hardcore science person" (as someone attributed to me), I decided to take a look at my homework submissions in CS. Now our CS class homeworks are/were the most engaging and "hardcore" assignments because of two facts - the pace of the course is incredibly fast. One week you start to learn about boolean circuits and next week you are already writing compilers. The other reason being that we had 'encounters' with no less than 10 programming languages* through the course of our freshman year - but settled on using an arcane, esoteric functional programming language called Standard ML. We never used 'for' loops!
One of our assignments was to use SML to write an interpreter for a register machine (assembly language interpreter, in other words). That was one behemoth of an assignment. A full night of coding in the lab (how nerdy) and by 6 am I had my submission ready - 6 hours after the deadline. (please no comments).
The grader's comments - "Nothing much to say. 100/100. You came, you saw, you owned."
The next assignment was to write a Fibonacci sequence generator using pure assembly (and a rather restricted subset of assembly... we had only 4 registers in total, among other things). The real fun was to write this program and test it on the register machine (affectionately called the REGMA) we had just built. It worked beautifully. Now some of you might laugh at all this hyperexcitement, but believe me, for someone who has coded in VB and C++ for basically half his life, writing his own language, compiler, interpreter; not just from an implementation point of view, but from understanding the theory behind it, is incredibly exciting.
Another assignment was to create a compiler for our own imperative (C-like) language. It was called SW (Simple While - because it only had a simple while loop instead of for loops). Our job was to convert programsn written in this single-typed (integer only), rigid syntax language into a stack-based virtual machine code (also a severely restricted subset of any commercial VM implementation). That was rather fun.
So, not forgetting that I straight out failed the first humanities course (Intro to Social Psychology), I present hereforth, my code for the REGMA.
Cheers.
I figured it would be nice to re-affirm that I am still a "hardcore science person" (as someone attributed to me), I decided to take a look at my homework submissions in CS. Now our CS class homeworks are/were the most engaging and "hardcore" assignments because of two facts - the pace of the course is incredibly fast. One week you start to learn about boolean circuits and next week you are already writing compilers. The other reason being that we had 'encounters' with no less than 10 programming languages* through the course of our freshman year - but settled on using an arcane, esoteric functional programming language called Standard ML. We never used 'for' loops!
One of our assignments was to use SML to write an interpreter for a register machine (assembly language interpreter, in other words). That was one behemoth of an assignment. A full night of coding in the lab (how nerdy) and by 6 am I had my submission ready - 6 hours after the deadline. (please no comments).
The grader's comments - "Nothing much to say. 100/100. You came, you saw, you owned."
The next assignment was to write a Fibonacci sequence generator using pure assembly (and a rather restricted subset of assembly... we had only 4 registers in total, among other things). The real fun was to write this program and test it on the register machine (affectionately called the REGMA) we had just built. It worked beautifully. Now some of you might laugh at all this hyperexcitement, but believe me, for someone who has coded in VB and C++ for basically half his life, writing his own language, compiler, interpreter; not just from an implementation point of view, but from understanding the theory behind it, is incredibly exciting.
Another assignment was to create a compiler for our own imperative (C-like) language. It was called SW (Simple While - because it only had a simple while loop instead of for loops). Our job was to convert programsn written in this single-typed (integer only), rigid syntax language into a stack-based virtual machine code (also a severely restricted subset of any commercial VM implementation). That was rather fun.
So, not forgetting that I straight out failed the first humanities course (Intro to Social Psychology), I present hereforth, my code for the REGMA.
Cheers.
(******************************************************************************************************************)
(* Problem 1.4 - REGISTER MACHINE SIMULATOR *)
exception UnhaltedProgram; (* raised when program counter goes beyond the last instruction but there was no STOP *)
exception AccessViolation; (* heavy MS-Windows influence to be seen here.. ;) *)
exception FatalException; (* not used.. just for fun :D *)
exception InvalidJump; (* self explanatory *)
datatype instruction =
(* Basic *) load | store | add | sub | loadi | addi | subi |
(* Index *) loadin1 | loadin2 | storein1 | storein2 |
(* Moves *) moveaccin1 | moveaccin2| movein1acc| movein2acc| movein1in2| movein2in1|
(* Jumps *) jump | jumpeq | jumpne | jumpless | jumpleq | jumpgeq | jumpmore |
(* Other *) nop | stop;
type datastore = int array;
type programstore = (instruction * int) array;
datatype CPUState = CPUState of int * int * int * int;
(* Stores the 4 registers : ACC PC IN1 IN2 *)
datatype Computer = Computer of programstore * datastore * CPUState;
(* Represents the whole computer... we'll toss it around between functions *)
fun change(arr, i, x) =
let
val blah = Array.update(arr, i, x)
in
arr
end;
(* quick function to update an array AND return it *)
(* The following function will take a "Computer" and an (instruction * int) and run that instruction on The computer.
Because the Computer datatype has the complete data store as well as the 4 register values, that one instruction
will be run in the proper context and environment. The function then returns the resultant Computer, with possibly
modified values of the registers or the data store *)
fun parseInstruction(The:Computer, a:(instruction * int)) =
let
(* First we get some values out of the Computer and into some variables *)
val Computer(Program, Data, CPU) = The
val CPUState(ACC, PC, IN1, IN2) = CPU
val (opcode, operand) = a
in
(* now the command execution.. after each operation, we return the computer.
basically I reconstruct the whole computer from its various parts, possibly changing some values
depending on the instruction being executed. For example, LOAD will rebuild the computer
but with a changed ACC in the CPUState *)
if opcode = nop then Computer(Program, Data, CPU) else (* just return same computer back *)
if opcode = load then
(* make sure that the guy is not trying to load from a non existent location *)
if operand >= Array.length(Data) orelse operand < 0 then raise AccessViolation
else Computer(Program, Data, CPUState(Array.sub(Data, operand), PC+1, IN1, IN2)) else
if opcode = store then
if operand >= Array.length(Data) orelse operand < 0 then raise AccessViolation
else Computer(Program, change(Data, operand, ACC), CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = add then Computer(Program, Data, CPUState(ACC+Array.sub(Data, operand), PC+1, IN1, IN2)) else
if opcode = sub then Computer(Program, Data, CPUState(ACC-Array.sub(Data, operand), PC+1, IN1, IN2)) else
if opcode = loadi then Computer(Program, Data, CPUState(operand, PC+1, IN1, IN2)) else
if opcode = addi then Computer(Program, Data, CPUState(ACC+operand, PC+1, IN1, IN2)) else
if opcode = subi then Computer(Program, Data, CPUState(ACC-operand, PC+1, IN1, IN2)) else
if opcode = loadin1 then
(* same boilerplate checking...*)
if IN1+operand >= Array.length(Data) orelse IN1+operand < 0 then raise AccessViolation else
Computer(Program, Data, CPUState(Array.sub(Data, IN1+operand), PC+1, IN1, IN2)) else
if opcode = storein1 then
if IN1+operand >= Array.length(Data) orelse IN1+operand < 0 then raise AccessViolation
else Computer(Program, change(Data, IN1+operand, ACC), CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = loadin2 then
if IN2+operand >= Array.length(Data) orelse IN2+operand < 0 then raise AccessViolation else
Computer(Program, Data, CPUState(Array.sub(Data, IN2+operand), PC+1, IN1, IN2)) else
if opcode = storein2 then
if IN2+operand >= Array.length(Data) orelse IN2+operand < 0 then raise AccessViolation
else Computer(Program, change(Data, IN2+operand, ACC), CPUState(ACC, PC+1, IN1, IN2)) else
(* move commands... pretty self explanatory. Only change is in the CPUState that's returned with the Computer *)
if opcode = moveaccin1 then Computer(Program, Data, CPUState(ACC, PC+1, ACC, IN2)) else
if opcode = moveaccin2 then Computer(Program, Data, CPUState(ACC, PC+1, IN1, ACC)) else
if opcode = movein1acc then Computer(Program, Data, CPUState(IN1, PC+1, IN1, IN2)) else
if opcode = movein2acc then Computer(Program, Data, CPUState(IN2, PC+1, IN1, IN2)) else
if opcode = movein1in2 then Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN1)) else
if opcode = movein2in1 then Computer(Program, Data, CPUState(ACC, PC+1, IN2, IN2)) else
(* here are the jump commands.. instead of increasing PC by 1, we increase it by the operand.
I will NOT check for invalid jumps here. One simple check in the Boot function will do the trick *)
if opcode = jump then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2)) else
if opcode = jumpeq then
if ACC=0 then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2))
else Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = jumpne then
if ACC<>0 then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2))
else Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = jumpleq then
if ACC<=0 then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2))
else Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = jumpgeq then
if ACC>=0 then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2))
else Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = jumpless then
if ACC<0 then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2))
else Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN2)) else
if opcode = jumpmore then
if ACC>0 then Computer(Program, Data, CPUState(ACC, PC+operand, IN1, IN2))
else Computer(Program, Data, CPUState(ACC, PC+1, IN1, IN2)) else Computer(Program, Data, CPU)
end;
(* This is the recursive function that takes a Computer and runs the instruction which is pointed to by the PC.
If the instruction is a STOP then it returns the value of ACC otherwise after executing the instruction it
feeds the computer back to itself to run the next instruction. The PC was incremented already *)
fun Boot(The:Computer) =
let
val Computer(Program, Data, CPU) = The
val CPUState(ACC, PC, IN1, IN2) = CPU
in
if PC >= Array.length(Program) then (* ..and the PC goes beyond the last line *) raise UnhaltedProgram else
if PC < 0 then (* negative PC... how the hell? *) raise InvalidJump else
let
val (operator, operand) = Array.sub(Program, PC)
in
if operator = stop then ACC else Boot(parseInstruction(The, Array.sub(Program, PC)))
end
end;
(* AND FINALLY.... THE REGMA FUNCTION. Just convert the prog and data to a Computer, initialize the registers to zero and Boot The Computer! *)
fun regma(prog,data) = Boot(Computer(prog,data,CPUState(0,0,0,0)));
(* Test cases .. *)
(* NOTE - 1) memory cells start from number 0, not one. so to load first number, load 0 will be the command *)
(* 2) the data store is NOT expandable. so if the assembly program uses let's say memory cells upto no. 5,
then the input data store must be at least 6 in length... no auto memory resizing (come on, not
even real computers do that.. they all have fixed memory! *)
(* simple program to add 3 numbers and store in the 4th cell *)
val prog1 = Array.fromList( [(load,0),(add,1),(add,2),(store,3),(stop,0)] );
val data1 = Array.fromList( [2,3,5,0] );
regma(prog1, data1); (* so result should be... 10 i think? .. and that 0 will be overwritten with the result but we cant see that of course *)
(* yep it was 10 ! *)
(*
you can test different programs by changing it above ^
try replacing (stop, 0) by something like (jump,~50)... you will get a nice InvalidJump exception.
or maybe load,~2 to get the equivalent thing of a Blue Screen :-P
I really wanted to return the whole data store. But since i'm not asked to do that in the problem statement, I won't.
But it's easy to do. Just have to change the "if operator = stop then ACC" in the Boot function
to "if operator = stop then Data" or maybe even the whole Computer together with the data, registers, program store.
*)
