Macquarie UniversityDepartment of Computing COMP3000 Programming Languages 2021 Assignment Three HasLang Translation and Execution Due: see submission pageWorth: 15% of unit assessment Marks breakdown: Code: 90%Your unit tests: 10% Submit a notice of disruption via ask.mq.edu.au if you are unable to submit on time for medical or other legitimate reasons. Late penalty without proper justification: 20% of the full marks for the assessment per day or part thereof late. Overview This assignment asks you to develop a translator for the HasLang programming language. The translator will target a simple abstract machine called the SEC machine. An implementation of this machine is provided, so once your translator is working you will be able to run HasLang programs. To limit the complexity of the assignment, the non-function data types that can be handled are: BoolInt[Int], i.e. list of Int You will not be implementing tuples or other kinds of lists. As well, multi-line functions will be restricted to having one parameter. You will build on the parsing and tree construction done in Assignment 2. Semantic analysis has not been included which means that there will be no type checking. If you make a program that would not type check then you may get Scala errors at run time. Building this translator will give you insight into the way that source language features correspond to target language features. It will show you how abstract machines can be used to provide a run-time system for languages. You will also gain specific experience with how HasLang is compiled and executed, which is similar in many respects to the implementation of full general-purpose functional programming languages. Once you have completed this assignment you will have a working implementation of HasLang. The SEC machine The “SEC” in the name SEC machine stands for Stack, Environment and Code. The interpreter that implements our SEC machine can be found in the file SECMachine.scala. Note: you don’t need to understand the inner workings of the SEC machine. The stack, environment and code components form the state of the SEC machine. The name is somewhat confusing because the environment component of the state is a stack as well. We will refer to the operand stack and the environment stack to make it clear which one we are referring to. The operand stack of the machine is used to keep track of values that are being operated on by instructions. In this respect, the SEC machine is similar to the stack machine which we used in the classes in Weeks 10 and 11. When execution begins the operand stack is empty. The operand stack can contain machine values. There are three types of value: integers, Booleans, lists of integers, and closures. The last of these is used to represent functions and will be explained more below. The environment stack of the machine is used to keep track of bindings of names to values. For example, when a function is called the value passed to the function will be bound to the name of the function argument. When the body of the function refers to the name we will look it up in the current environment to get its value. The environment stack is initialised to contain a single environment that is empty and at any time the topmost environment on the stack defines the bindings that are accessible to the running code. In our implementation an environment is a map from names to machine values. The code component of the machine state is the sequence of SEC machine instructions that is being executed. When a program begins executing, the code component is initialised to the code sequence that comprises the compiled program. At each step of the execution the machine interpreter will look at the first instruction in the code sequence and decide what to do based on what that instruction is. In each case the instruction will update the machine state in some way. Execution will then continue with the next instruction in the sequence. SEC machine instructions The SEC machine instructions are defined in the file SECTree.scala. There are the following instruction types: Push value instructions (IBool, IInt and INil): Push a single given Boolean or integer value or Nil onto the operand stack.Push variable instruction (IVar): Push the value of a given variable onto the operand stack. This variable must be bound in the current environment, otherwise the machine halts with an unknown variable error.Arithmetic instructions: (IAdd, IDiv, IMul and ISub): Pop two integers off the operand stack, perform the given operation on them and push the result onto the operand stack. The first value popped will be the right operand of the operation and the second value popped will be the left operand. The machine will halt if the top of the operand stack does not contain two integer values. If the instruction is IDiv the machine will halt with an error if the right operand is zero.List instructions: (ICons, IHead, ITail and ILength): IHead, ITail and ILength pop a list off the operand stack and put the result onto the operand stack. ICons pops a list/Nil and an integer off the operand stack, conses them and pushes the result onto the operand stack. The first value popped will be the right operand of the operation (the list/Nil) and the second value popped will be the left operand (the integer). The machine will halt if the top of the operand stack does not contain these two types of values, or if IHead or ITail is applied to Nil.Equality instruction: (IEqual): Pop two values off the operand stack, compare them for equality and push the result of the comparison as a Boolean onto the operand stack. The machine will halt if the top of the operand stack does not contain two values that are either both integers or both Booleans or both lists.Less than instruction: (ILess): Pop two values off the operand stack, compare them for equality and push the result of the comparison as a Boolean onto the operand stack. The first value popped will be the right operand of the operation and the second value popped will be the left operand. The machine will halt if the top of the operand stack does not contain two integer values.Print instruction: (IPrint): Pop a value off the operand stack and print it. The machine will halt if there is no value on the operand stack.Branch instruction: (IBranch): The instruction contains two code sequences (also called frames in the code). Pop a Boolean value from the operand stack. If the popped value is true continue execution with the first code sequence from the instruction; otherwise continue with the second code sequence. The machine will halt if the top of the operand stack does not contain a Boolean value.Closure instruction: (IClosure): The instruction contains an argument name, and a sequence of instructions that constitute the body of a function. Push a closure value onto the operand stack that represents this function. The closure will contain the argument name, body and the current environment (top of the environment stack). The environment value is therefore captured so that it can be used later when the function is called. The machine will halt if the environment stack is empty since in that case there will be no environment to capture.Call instruction: (ICall): Pop a value from the operand stack; this value will be the argument to the call. Then pop a closure value from the operand stack; this will be the function that is called. Continue execution in the body of the closure with the closure’s argument bound to the argument value. The machine will halt if the value or the closure are not present on the operand stack.Pop environment instruction: (IPopEnv): Pop the current environment from the environment stack and discard it. The machine will halt if the environment stack is empty. Note that in normal operation of the SEC machine we would not expect to trigger any of the error conditions. The code that we generate for the machine must be constructed so that none of the error conditions can occur. For example, if we generate an IAdd instruction then we must previously generate code to push its two integer operands onto the operand stack. Note that a closure is a function together with an environment of variable bindings that were captured from the enclosing environment at the point that the closure was created. It can be used like a function that has one parameter. Translating HasLang to the SEC machine This section describes how the constructs from the HasLang language should be translated to SEC machine instructions. The top-level expression in a program should translate into the code that evaluates the expression, followed by a print instruction.Boolean expressions, integer expressions and applied occurrences of identifiers should translate into pushes of the relevant values.Arithmetic operations, equality and less-then comparisons should translate into the code for their operands, followed by the relevant machine operation.Cons operation (:) should translate into the code for its operands, followed by the cons machine instruction.An IF expression should translate into code to evaluate the condition followed by a branch instruction containing the code for the THEN and ELSE expressions of the IF expression.An application expression of the form:head expression; ortail expression; orlength expression should translate the argument expression, followed by the corresponding list instruction. An application expression (excluding those above) should translate into the translation of the left-hand side function-valued expression, followed by the translation of the right-hand side argument expression, followed by a call instruction.Because of Haskell’s functional approach, a let with multiple definitions gets transformed into a series of cascading lets with a single definition in each. A program like:let x :: Int = 5; y :: Int = xin y will get transformed into the following: let x :: Int = 5 in let y :: Int = x in y A let consisting of a single definition and a body is translated as if it was an application of an anonymous function. (? is being used to represent whatever the type is.)let x :: ? = expin body The body will contain (zero or more) occurrences of x; so we can think of body as the body of a function whose parameter name is x; and this function will be evaluated with the value exp. In other words, the body is packaged in a closure x :: ? -> body which takes the value exp as an argument. This closure is called, passing the expression that defines the value as the argument. The let translates to this application expression: (x :: ? -> body) (exp) If there are other definitions after the first definition then they are collected together with the let body and translated as a new (smaller) let. For example: let x :: ? = exp_x; y :: ? = exp_y; z :: ? = exp_z in body translates as if it were let x :: ? = exp_x in let y :: ? = exp_y; z :: ? = exp_z in body And the same transformation is applied to the inner let. This continues until the last inner let contains only one definition. This is necessary because the only way a binding can be created in the SEC machine is by calling a closure; each definition becomes part of its own let which gets converted into a closure. Multi-line functions are covered in the next section. Multi-line functions and patterns In the previous section, all definitions in a let were of the form x :: ? = exp which could include functions if they are written as a lambda expression on the right-hand side (where exp is). For example, the factorial function could be written as: fact :: Int -> Int = n :: Int -> if(n == 0) then 1 else n * fact (n – 1) Clearly multi-line functions are not like this; e.g. factorial again: fac :: Int -> Int fac 0 = 1. fac n = n * fac (n – 1) This needs to be converted into a lambda expression like above. The first line of fac supplies the information for: fac :: Int -> Int = … The second and third lines of fac will supply the information needed to build a lambda expression for the right-hand side of the line above. In general, the lines after the first line will look like (assuming the function is called foo and the function always has exactly one argument): foo pat1 = exp1. foo pat2 = exp2. … Each of these pattern lines corresponds to a condition and transformation of the function’s input parameter. Since we will be working with the function’s input parameter, we need to give it a name. For this assignment the parameter name will always be x for any multi-line function. This means that will can fill in a bit more detail with the partial line above: fac :: Int -> Int = x :: ? -> … When constructing a lambda expression, the type of the parameter needs to be specified; but since there is no type checking, it will always be specified as UnknownType(). Back to the pattern lines. They can be thought of like: if something to do with pat1 is true then do something with exp1 else if something to do with pat2 is true then do something with exp2 else … and this is the whole body of the lambda expression – a series of cascading IFs. Patterns Before we go further with the handling of patterns, here is the list of patterns that need to be handled for this assignment: _truefalsean integeran identifier, representing a variable to be instantiated by the matchan (integer) list of length 0 to 3 containing _ or integer or identifier; e.g. [], [4, y], [3, _, 5]a cons (e.g. h:t) containing:left part: _ or integer or identifierright part: _ or identifier or list of integers (but not a list containing patterns) If there is a line like: foo 3 = exp then the translation of this will be like: if x == 3 then exp If there is a line like: foo _ = exp then _ will always match, so there is no need for a condition and exp is unconditionally executed. The translation will be like: exp If there is a line like: foo n = exp then n will always match, getting instantiated with x’s value. So there is no condition and exp is unconditionally executed; except there is an issue – exp will have n occurring in it (zero or more times), not x. We need to evaluate exp but substituting x’s value wherever n occurs. So the translation will require a new lambda expression around exp and applied to x; it will be like: (n :: ? -> exp) x All the other patterns are based on similar ideas although the list-related patterns will require some list operations on x. Note that multiple identifiers in a pattern will require multiple lambda expressions for them. If the pattern is only _ or an identifier then, because these will always match, there will be no following ELSE and any further function lines will be ignored. (If our compiler was smart enough then having following lines in this situation would cause an error to be reported by the compiler.) Otherwise, there will always be an ELSE (we will not try to analyse the sequence of patterns to determine if they provide complete coverage). That means that often we will have a dangling ELSE at the bottom. We will take care of this by returning an arbitrary 999 in that case as a feeble way of flagging an error (incomplete coverage of the patterns). (Obviously a “real” compiler wouldn’t do this; it would give a compilation error or at least a runtime error; but here it is just to keep things simple (since there is no simple way to report a runtime error); and it also makes the testing easier.) For example: foo pat1 = exp1. foo pat2 = exp2. foo _ = exp3. foo pat4 = exp4 becomes: if something to do with pat1 is true then do something with exp1 else if something to do with pat2 is true then do something with exp2 else exp3 And (assuming pat3 is not _ or an identifier): foo pat1 = exp1. foo pat2 = exp2. foo pat3 = exp3 becomes: if something to do with pat1 is true then do something with exp1 else if something to do with pat2 is true then do something with exp2 else if something to do with pat3 is true then do something with exp3 else 999 Translation Example As a simple example of translation, consider this HasLang program: 3 * (12 / 4) This program would be translated into the followed SEC machine code: IInt(3), IInt(12), IInt(4), IDiv(), IMul(), IPrint() As a more complex translation example, consider the HasLang program found in test/function.hal in the skeleton: let x :: Int = 100; inc :: Int -> Int = a :: Int -> a + 1 in inc x This program should print 101 when executed. Here is the SEC machine code that is the translation of this program. The comments in the code are there to assist your understanding; they are not part of the code. IClosure ( // Closure “x -> ((inc -> inc x) (a -> a + 1))” “x”, List ( IClosure ( // Closure “inc -> inc x” “inc”, List ( IVar (“inc”), IVar (“x”), ICall (), // inc x IPopEnv ())), IClosure ( // Closure “a -> a + 1” “a”, List ( IVar (“a”), IInt (1), IAdd (), IPopEnv ())), ICall (), // (inc -> inc x) (a -> a + 1) IPopEnv ())), IInt(100), // Push 100 ICall(), // (x -> ((inc -> inc x) (a => a + 1))) 100 IPrint() // Print the value of the expression What you have to do You have to write, document and test a Scala translator for the HasLang language, according to the description above. You are strongly advised to complete portions of the assignment before moving onto the next one, rather than trying to code the whole solution in one go. A skeleton sbt project for the assignment has been provided. The translation module is very similar to those used in the practical exercises, particularly for Weeks 10 and 11. For this assignment you should not have to modify any parts of the implementation except the translator (Translator.scala) and the related tests (ExecTests.scala). Some of the translation and associated testing code is given to get you started; you must provide the rest, particularly the implementations of the actual translation of HasLang constructs into SEC machine instructions (look for FIXME in the code for some places where new code has to go). Running the translator and testing it The skeleton for this assignment is designed to be run from within sbt. For example, to compile your project and run it on the file test/function.hal you use the command run test/function.hal Assuming your code compiles and runs, this will print any errors that have been found in the program contained within the file. If no errors are detected, the HasLang program will be passed to the translator to produce SEC machine code. Then the SEC code will passed to the SEC interpreter for execution. You should see the result values of the top-level printed out. For example, once you have written your translator, if you compile and run the function program, you should see the number 101 printed out. The project is also set up to do automatic testing. See the file ExecTests.scala that provide some useful definitions for translation and execution testing, and some tests that we have written for you. Note that the tests we provide are not sufficient to test all of your code. You must augment them with other tests. You can run the tests using the test command in sbt. This command will build the project and then run each test in turn, comparing the output produced by your program with the expected output. Any deviations will be reported as test failures. What you must hand in and how A zip file containing only: Translator.scalaExecTests.scala Your submission should include all of the tests that you have used to make sure that your program is working correctly. Note that just testing one or two simple cases is not enough for many marks. You should test as comprehensively as you can. Submit your code electronically as a single zip file called ass3.zip using the appropriate submission link on the COMP3000 iLearn website by the due date and time. DO NOT SUBMIT YOUR ASSIGNMENT IN ANY OTHER FORMAT THAN ZIP containing two .scala files. Use of any other format slows down the marking and may result in a mark deduction. Marking The assignment will be assessed according to the assessment standards for the unit learning outcomes. Your code will be assessed, with respect to the assignment description, for correctness – tested against a large suite of test cases beyond what was supplied Marking will also assess the adequacy of your testing – this will be 10% of the marks for the assignment. As there are many possible pattern combinations, it is sufficient to have some good representative test cases rather than every possibility. Tony Sloane, Matt Roberts, Kym Haines Last modified: 28 Oct 2021Copyright (c) 2021 by Macquarie University. All rights reserved.
