COMP3000: Tips for assignment 3ApproachFor the assignment, all you will need to do is: understand and use the SEC instructions (you do not need to use IClosure and IPopEnvbecause those have been done for you in genMkClosure) use gen, genall, genMkClosure use translateExpression recursively manipulate and construct Exp expressions when dealing with LET and definitions add some helper functions as required think recursivelytranslateExpressionHopefully you have a reasonable idea of what translateExpression does based on the week 10 and11 classes. The SEC machine is a stack machine – every operation (e.g. +) expects to get its operandfrom the stack and put its result back to the stack. If we have an expression:3 + 4then we would want instructions:IInt(3), IInt(4), IAdd()Remember that the job of the translation phase (which is what the assignment is about) is to convertour expressions into machines instructions. The execution phase is done automatically (you don’thave to do anything) once all instructions for the whole HasLang program have been produced.When the above instructions are executed:IInt(3) pushes 3 onto stack stack: 3IInt(4) pushes 4 onto stack stack: 3, 4IAdd() pops the top two values on the stack (3, 4),adds them and pushes the result onto the stack stack: 7But, in general, an addition can have complicated operands:( … ) + ( … )The code in translateExpression for this:case PlusExp (l, r) =>genall (translateExpression (l))genall (translateExpression (r))gen (IAdd ())handles this recursively: the first translateExpression line generates all the instructions needed to push the result ofthe left operand onto the stack (which may involve many pushes and pops and otheroperations but which all resolve down to a single result) the second translateExpression line generates all the instructions needed to push the resultof the right operand onto the stack then the IAdd() instructionThe recursion makes this easy, but remember that translateExpression is producing a list ofinstructions (genall and gen are adding to that list of instructions). So, everything needs to be donein the correct order. For example, there is no point generating the IAdd() instruction if theinstructions producing its operand don’t appear first.Think recursivelyIn more than one place in the assignment you will need to rely on recursion to build up a sequenceof things (LETs, IFs, …). For example, suppose we wanted to convert:List(3, 1, 4, 1, 5, 9)intoPlusExp(IntExp(3),PlusExp(IntExp(1),PlusExp(IntExp(4),PlusExp(IntExp(1),PlusExp(IntExp(5), IntExp(9))))))[Note: you will not need to do anything like this with PlusExp in the assignment.]If our recursive function is foo and it takes a list of numbers as its parameter then we can see thatthe recursive step is going to be:PlusExp(IntExp(a number), foo(list of rest of numbers))So (assuming initial list always has at least one number in it):def foo(s:List[Int]):Exp = s match{case Nil => IntExp(0) // won’t happen; keeps compiler happycase List(a) => IntExp(a) // end of listcase h :: t => PlusExp(IntExp(h), foo(t))}Note that a vector can also be deconstructed in a similar way into a head (h) and tail (t):case h +: t => …ClosuresAs we have discussed previously, a closure contains: a function an environment (i.e. a collection of name-value bindings)Wherever we need a function of any form, we will make a closure. A closure is made by supplying aparameter name (can have only one) and a list of instructions; and the supplied functiongenMkClosure that will do it for you. The environment is bound to the closure when the closure isdefined. You don’t have to worry about the environment – it is taken care of automatically by theSEC machinery. (You will never need to use the IClosure or IPopEnv instructions – genMkClosuredoes those for you.)A closure is then just treated like a function. Consider this example:letb :: Int = 4;f :: Int -> Int = letb :: Int = 3;g :: Int -> Int = x :: Int -> x + binginf 10In the environment that g is defined in, b has the value 3. g’s function value is assigned to f. In f’senvironment, b has the value 4. Will f 10 produce 13 or 14?The lambda expression that is g’s value is a closure because it includes the environment around it,including b having the value 3. This closure is passed to f, including that environment. So f 10produces 13.Stack machineRemember that this is a stack machine. You have seen this in the Reverse Polish exercise in an earlyclass and it is also in the week 10 and 11 classes. The idea is to push values onto the stack and everyinstruction takes its parameters from the stack and places its result on the stack. E.g. 3 + 4 * 5becomes:IInt(3), IInt(4), IInt(5), IMul(), IAdd()IfExpThere is a fairly obvious SEC instruction to handle this.AppExpFor application expression (function call), there is a fairly obvious instruction for this; but beforeusing that, we need to check if the function is head, tail or length, e.g.head [3, 5, 7]If it is, then the corresponding SEC instruction needs to be used, e.g.(instructions to get list onto stack), IHead()For the general application expression (i.e. not head, tail , length), it is just as easy to do as PlusExp.ListExpIf we have IntExp(someValue) then (as can be seen in Translator.scala) the SEC machine has thecorresponding instruction IInt(someValue) to push that value onto the stack. Same for BoolExp(.)and IBool(.).But what about if we have ListExp? There is no corresponding instruction that will push a list ontothe stack. But ListExp is different from IntExp. IntExp will just have an integer value as its parameter:case class IntExp (n : Int) extends ExpFor example, IntExp(7); and IInt expects an integer value as its parameter; so IInt(7).ListExp is not like that:case class ListExp (exps : Vector[Exp]) extends ExpEvery element in the list (Vector) will need to be converted to instructions. That still leaves thequestion of how to build a list. What SEC machine instructions can be used to construct a list?What instructions are needed to create the following lists:[][5][3, 5][4 + 2, 28 / 7] (including instructions for the arithmetic)LetExpOverviewFor those of you who struggle with the transformation of a LET with multiple definitions, there willbe some tests with LETs with single definitions.There are three transformations that will need to be applied to LETs or the definitions in them: convert a LET with multiple definitions into cascading LETs where each LET has a singledefinition convert a multi-line pattern function into a definition with a value that is a lambdaexpression convert a LET with a single definition (that is not a multi-line function) into an applicationexpression using a lambda expressionEach of these transformations can be done as independent steps by deconstructing the LET ordefinition into an equivalent expression. Only when the transformations have all been done can thefinal expression be transformed into instructions (using translateExpression).LET with single definitionLet’s start with a LET with a single definition. There are three kinds of definitions, as seen by theseexamples: x :: Int = 3 + 4 * 5a variable with a simple valueinc :: Int -> Int = a :: Int -> a + 1a variable with a function valuefac :: Int -> Intfac 0 = 1.fac n = n * fac (n – 1)a function using patterns The first two kinds just collapse into (using x for any variable name and ? for the type):x :: ? = expwhere exp is any expression including a lambda expression.We can distinguish between this type of definition and the multi-line pattern-based definition bylooking at the structure of the definition. A Defn contains lines: Vector[FunLine]. For the first type ofdefinition, the vector will have only one item and that FunLine will have: ident of “” lines will be an empty vector exp will be the simple expressionIn that case, the LET now looks like:letx :: ? = expinbodyand the spec indicates that instead of translating the existing LET expression, you should constructthis alternate expression:(x :: ? -> body) (exp) [AppExp(LamExp(…), …)]and translate this expression instead. (You can use UnknownType() for the type.) Remember thattranslateExpression is recursive.For example:letj :: Int = 4inj + 2This gets transformed to:(j :: ? -> j + 2) (4)For our understanding, we can see how this would be evaluated. It is just an application expression,i.e. a function call, where the function is the first bracketed expression and the function’s parametervalue is the second bracketed expression:(j :: ? -> j + 2) (4)= (j + 2) [substitute j = 4]= 4 + 2= 6If instead you have a multi-line function using patterns then the patterns need to be dealt with. Let’sconsider a very simple example using the wildcard pattern:letf :: Int -> Intf _ = 7inf 3f is a simple function that will always return 7. We need to transfer this multi-line definition into adefinition of a variable that has a lambda function as its value. We want the definition to look like:f :: ? = x :: ? -> expAnd we will always use x as the lambda parameter because it is specified in the spec. This is so thattest cases will work.Our function is very simple, so we can see that the definition becomes:f :: ? = x :: ? -> 7(We don’t care about the type, so can use UnknownType() for the “?”.)And the LET becomes:letf :: ? = x :: ? -> 7inf 3The transformation of the LET proceeds as before:(f :: ? -> f 3) (x :: ? -> 7)It looks like we are getting overwhelmed by lambda expressions, but this is just an applicationexpression. The function is the first bracketed expression and its parameter value is the secondbracketed expression. The function is a lambda expression with parameter f. We can evaluate thisexpression (just for understanding – our program doesn’t need to handle evaluation). The functionhas parameter f; so we can evaluate the body of the function if we substitute f’s value wherever fappears:(f :: ? -> f 3) (x :: ? -> 7)= f 3 [substitute f = x :: ? -> 7]= (x :: ? -> 7) 3= 7 [substitute x = 3]= 7Multi-line pattern functions: factorialNow consider the factorial example:letfac :: Int -> Intfac 0 = 1.fac n = n * fac (n – 1)infac 4The first pattern line of fac needs to be transformed into (remembering that our multi-line patternfunction parameter name must always by x): if(x == 0) then 1 else …[always put the x first in the conditionto keep the test cases happy] Note that the IF must have an ELSE because the IF/THEN/ELSE expression must always produce avalue.The second pattern line is trickier. Our function parameter is the mandated x but our patternmatching variable name is n; and the right hand side of the line uses n, not x. As explained in thespec, this line becomes:(n :: ? -> n * fac (n – 1)) xSo fac gets transformed to:fac :: ? = x :: ? -> if(x == 0) then 1else (n :: ? -> n * fac (n – 1)) xThe LET is now like:letfac :: ? = x :: ? -> if(x == 0) then 1else (n :: ? -> n * fac (n – 1)) xinfac 4And, as before, this gets transformed to:(fac :: ? -> fac 4) (x :: ? ->if(x == 0) then 1else (n :: ? -> n * fac (n – 1)) x)Cons patternWhen we have a cons pattern, we can assume that our function parameter x is a list. The compilerwould have checked all that (except our compiler is not complete and does not check types but wewill still assume the types are correct).If we have a cons pattern such as 4 : t, then this pattern is looking for a list that has 4 as its head. Wecan write a condition that tests the head but first we need to establish that the list has at least oneelement. So our condition would look like (remembering that the function’s parameter is x):if length x >= 1 and head x == 4 then (handle right-hand sideof the pattern line)else(handle next pattern line)But there is a problem here – there is no AND operation in our expression syntax or in the SECinstructions. This can be overcome by thinking a bit about short-circuit evaluation. We want toevaluate the condition:length x >= 1 and head x == 4This condition can be evaluated to produce a Boolean result as:if length x >= 1then head x == 4 // value is: head x == 4else false // or: falseSo the original IF becomes:ifif length x >= 1then head x == 4else falsethen (handle right-hand side of the pattern line)else(handle next pattern line)If there were more than two comparisons in the condition then a cascading IF would be required.For example:cond1 and cond2 and … and condkwould become:if cond1then if cond2then if cond3then ……if cond(k-1)then condkelse false…else falseelse falseelse falseThis could be hard-coded in your program or it could be generated recursively in the style of therecursive section at the start of this document.In 4: t, the t would be handled in the same way as the n in the factorial example. It would get itsvalue from tail x.For a cons pattern with two identifiers (e.g. h : t), it would be necessary to create two lambdaexpressions (like for n in factorial), with one inside the other (because a lambda expression for haveonly one parameter).As an aside, how would you write one-parameter lambda expressions in Scala to add two numbers?((x:Int) => ((y:Int) => x + y)) (3) (5) // produces 8NOTE: the cons pattern tests will be restricted to a single cons with any of the following: _ literal value (an integer or true or false) an identifierIt will not contain any form of list (including []).E.g.: 4:_ 3:b _:d a:bList patternThe list pattern is not hugely different from the way cons is done. For example, the pattern:[_, 4]would require an applicability test of:if length x == 2 and head (tail x) == 4 then …LETs with multiple definitionsLETs with more than one definition require the LET to be transformed; e.g.letx :: ? = exp_x;y :: ? = exp_y;z :: ? = exp_zinbodybecomes:letx :: ? = exp_xin lety :: ? = exp_y;z :: ? = exp_zinbodyand the process is repeated on the new inner LET. This can be done at the same time astransforming each LET into an application expression as previously described; and a recursiveapproach like that described at the start of this document will work well. In the big match intranslatorExpression, it may help to have two cases to handle the deconstruction of the vector ofdefinitions LetExp:…case LetExp (Vector(), exp) =>genall(translateExpression(exp))case LetExp (Defn(IdnDef(name, _), lines) +: defs, exp) =>…Suggested stepsThe overall suggested order is:1. IfExp2. AppExp3. ListExp4. LetExpTo do LetExp:1. for now, ignore multi-line pattern functions – stick to simple definitions2. if you are comfortable transforming a LetExp with multiple definitions into cascading LetExpsthen do that now; otherwise leave it to the end (or not at all – still plenty of marks available)3. work out (spec + tips) how to transform a LetExp with one (simple) definition into a lambdaexpression; see test case for: “translate let x :: Int = 3 in x + 4” (see ExecTests.scala)4. (consider handling LetExp with multiple (simple) definitions now)5. read about patterns (spec + tips) and see if you can handle this test case: “SIMPLEPATTERNS: translate foo 3 = 2″6. try the following pattern test cases (no lists)7. do the cons pattern8. do the list pattern: empty list, list of length 1, 2, 39. handle LetExp with multiple definitions28 Oct 21
