CSC 7B/FC Programming Assignment, Year 7E3 Edition Due One Week From Date Assigned Study the program am7b19.fs which implements "Abstract Machine AM7B" in F#. Compile (fsc/fsharpc) am17b19.fs and run the sample program test1.7b with (mono) am7b19.exe < test1.7b (feed file to stdin) You should see that the top of stack holds 20, which is the result of the computation. The assembler skips blank lines and lines that start with '#'. AM7B.fs has also been compiled into am7b19.dll, which you can use in your program (see below). Please note that the last line trace_advice(run); was commented out when producing the .dll, so you need to add that line to your program in order for it to run. Also, in case you run into compatibility problems with this .dll version (generated by mono), you may recompile the original program into a .dll after commenting out the run line, but that is all you can do to the original program. You can compile a program with this .dll with the -r am7b19.dll option, be sure you 'open CSC7B;' at the top of your own program The program as given can only handle test1.7b (and test0.7b) but not the other tests. Your assignment is to extend AM7B to a fuller set of instructions (AM7B+) so that all tests can be executed (except for test2.7b, which is supposed to fail). In particular, you need to be able to handle the following new features: New type of operand: [bx] refers to the memory content at location addressed by bx. Because of the way your imaginary cpu is wired, only the bx register can be used to address memory, so [bx] is the one and only legal memory operand; anything else inside [] is illegal. The type definition of 'operand' already includes Mem, but note that in abstract syntax, [bx] is Mem(Reg("bx")). The Mem constructor takes another operand. We may in the future expand the instruction set to allow other forms of addressing (register-offset, etc). In terms of the simulation, operand [bx] refers to the value stored in RAM.[REGS.["bx"]]. New Types of Instructions (explained by example): idiv ax bx : This should have the effect of storing the quotient of bx/ax in : bx and the remainder in dx. dx thus serves a special purpose. : The destination register of this instruction cannot be dx. : idiv should be treated separately from the other ALU ops. add 3 bx : ALU operations can have an immediate (constant) source operand mov 3 ax : move immediate value to register (REGS.["ax"] <- 3) mov ax bx : move register to register (REGS.["bx"] <- REGS.["ax"]) mov ax [bx] : move register to memory location addressed by bx Only register bx can be used to address memory. mov [bx] ax : move from memory to register. Memory to memory ops are not allowed (this is a RISC machine) jnz 3 : jump to instruction 3 if the value in register cx is not zero (REGS.[2] <> 0). The first instruction is the 0th. jz 0 : jump to first instruction if cx holds value 0. jn 1 : jump to second instruction if cx holds a negative value call 4 : push the current value of pc on the stack, then jump to instruction 4 (5th instruction). ret : pop value from stack into the pc register, which should cause instruction no. pc+1 to be executed next. With these instructions your machine becomes a true Turing Machine, with random access to memory and the ability to execute general algorithms. For example, to compare two values for equality, subtract one from the other and see if it's zero. Unconditional jumps can be made by mov 0 cx followed by jz. Also, be aware that the jump instructions directly take an int, not an operand as argument, i.e., it's represented as in JZ(3). You may implement other instructions to prove that you're a hot shot engineer, but these are the minimum. Test your machine on test3.7b: (mono) machine.exe < test3.7b mov 8 bx mov 3 ax add 2 ax mov ax [bx] mov [bx] cx push cx This program should store 5 in RAM.[8] and push 5 on the stack ... and this program (test4.7b): mov 6 cx mov 1 ax imul cx ax sub 1 cx jnz 2 push ax This program calculates 6!, and leaves the answer (720) on the stack. You should also test your program against instructions that have errors: # stack underflow pop ax # illegal operands for move mov [3] [bx] # illegal destination for idiv idiv ax dx (strings can be compared using = and <>) THERE WILL BE TWO MORE PROGRAMS TO TEST YOUR IMPLEMENTATION ON AS AN IN-CLASS ASSIGNMENT. -------------------------------------------------------------------------- -------------------------------------------------------------------------- There are three levels to this assignment: 1. To get a C, you can edit the code in place. 2. To get a B or better, you can't touch my code, but you must reuse it. You have to add your code modularly using the technique illustrated for aluop - by assigning lambda terms to functions that perform new operations while "inheriting" the original operations. Put all your code in a separate file with 'open CSC7B' at the top, then compile with fsharpc yourprogram.fs -r am7b19.dll ... run under mono compiling on native windows will be different (fsc, dotnet or V. Studio) There are three functions that you will need to extend: execute (this is the most important function) transoperand (currently does not recognize memory operands) translate (translates instructions into abstract syntax) executeProg (maybe you need to change this too) For execute, the type definition of 'operation' already include the cases for MOV, JZ and JNZ instructions (we will talk about how to extend a type definition modularly later). You just need to add cases to execute (modularly like it's done in the aluop example) to recognize these new instructions and perform the corresponding operation. Be careful when implmenting JZ and JNZ: study the executeProg function and note that the pc counter is incremented after the execution of each instruction. For transoperand, you just need to translate string "[bx]" into Mem(Reg("bx")), because [bx] is the only valid memory operand. Optionally, you can examine a string s more carefully with rule | s when s.[0]='[' && s.[s.Length-1]=']' && s.Substring(1,2)<>"bx" -> raise (Exception("illegal memory operand")) For translate, You need to recognize arrays of the forms [|"mov"; x; y|], [|"jz"; n|], [|"jnz"; n|], etc. and translate them into abstract instructions such as MOV(Imm(4),Reg("ax")). Use the am7b19.fs source code only as a reference. Do not use it in your code. Instead, download am7b19.dll, and write a new program with the following structure. open System; open CSC7B;; // ... add your code here trace_advice(run);; // add this as the last line, which will run program. // alternatively you can just call run() without tracing. and compile your program with fsc (fsharpc on mono) yourprogram.fs -r am7b19.dll And test it with (mono) yourprogram.exe < test4.7b etc.. The amount of code you need to write for this part of the assignment is about 50 lines. 3. To get an A, you must also study and implement the trace_advice function and how it simulates dynamic scoping to inject new behaviors into exisiting functions. Another program that uses this "aspect-oriented programming" technique was given in Perl (look for program with "subversive ideas"). Apply these techniques to implement additional advice: A. memdump_advice(k,target): this advice should execute target under a new version of executeProg so that the contents of the first k words in RAM are displayed after the program terminates. Use this advice when running the Fibonacci program (test7.7b) * Your advice should work in conjunction with other advice: memdump(16,fun () -> trace_advice(run)) // should run under both advice * Your advice should not permanently alter the behavior of programs: run() // should still run without the effects of any advice * Your advice should work on any target function of type unit -> unit, not just the 'run' function: that is, it must affect any function that calls the functions that you advise. B. input_advice(target): this advice should execute target by modifying executeprog to take as user input the intial values of ax, bx, cx and dx Change the 7b programs test4.7b and test5.7b so that they work for more than just the given values. Determine how to control the precedence (priority) of multiple advice when they're "weaved" together: Explain how input_advice(fun () -> trace_advice(fun () -> memdump(16,run))) is different from memdump(16,(fun () -> trace_advice(fun () -> input_advice(run)))) Which advice takes affect first? Can you find a precise schema for controling which advice will have precedence, and how one advice may override another advice? Write a function 'weave' that takes a list of advice of arguments and compose them in the order specified, returning a new, dynamically constructed advice that can affect the behavior of any target. 4. To get an A and be considered super awesome, you must also implement "peephole optimization": Write a program that optimizes a (operation list) by replacing redundant code of the following forms (given by example): push ax pop bx --> replace with single instruction mov ax bx push ax pop ax --> eliminate altogether mov ax bx mov bx ax --> mov ax bx Challenge: sequences such as push 3 push 4 pop ax pop bx should be optimized into mov 4 ax mov 3 bx Can you optimize arbitrarily long sequences of this form? How would you know when to stop?