Concepts of Programming Language Design — Assignment An abstract machine for MinHs
-
Each of these parts is explained in detail below.The front end of the interpreter (lexer, parser, type checker) is provided for you, along with the implementation of the evaluate and evalE functions (found in the file Evaluator.hs). The function evaluate requires a program as argument, and returns an object of type Value, and evalE takes an expression as argument. You will need to extend the set of constructors for Value, but not the implementation for evaluate and evalE. The return value of evaluate is used to check the correctness of your assignment.
The types of the functions msInFinalState, msGetValue and msStep are provided and may not be changed. The definition of the type MachineState is currently empty, and you have to find a suitable definition modelling the different states of the machine. The control stack and the environment are part of the machine state. For the environment, you can use the predefined type VEnv, but you have to define your own data type to model the control stack.Apart from Evaluator.hs, no other files can be modified!
The function msStep performs one single evaluation step in the E-machine, with an explicit control stack and environment, and may not be recursive. The function evalE acts as driver and calls msStep on the machine state until it ends up in a final state. Given a closed expression e, then passing the expression to evalE should result in the value as specified by the big step semantics given in Section 2.
You can assume the typechecker has done its job and will only give you correct programs to evaluate. The type checker will, in general, rule out invalid programs, so the abstract machine does not have to consider them.
The dynamic (big step) semantics of MinHs is given in Section 2, and you should use this as a specification for the behaviour of your abstract machine for the core tasks. That is, iff an expression e under the environment Γ evaluates to a value v according to the big step semantics, then it should evaluate, under the same environment and an intially empty control stack, to the same value v and an empty control stack in a finite number of steps in your E-machine implementation. For the subset of the language we discussed in the lecture, you can directly use the E-machine rules. For the remaining language constructs, you still need to find the corresponding rules. For the advanced tasks, you have to come up with the formal sematics from the informal description yourself.
1 Task1
This is the core part of the assignment. You are to implement an abstract machine for MinHs. The following expressions must be handled:
• variables. v,u
• integer constants. 1,2,..
• boolean constants. True,False
• some primitive arithmetic and boolean operations. +,*,<,<=,.. • constructors for lists. Nil, Cons
• destructors for lists. head, tail
• inspectors for lists. null
• function application. f x
• ifethene1 elsee2
• let x :: τx = e1; y :: τy = e2; ... in e2
• recfun f :: (τ1 -> τ2) x = e expressionsThese cases are explained in detail below. The abstract syntax defining these syntactic entities is in Syntax.hs. You should understand the data type Exp and Bind well.
The big step semantics of a higher-order abstract syntax representation of MinHs is given is this document. Your task is to design a corresponding E-machine semantics (that is, with explicit control stack and environment, not substitution!) and implement it in Haskell.
If a runtime error occurs, which is possible, abort the execution and use Haskell’s error ::
String -> a function to emit a suitable error message (the error code returned by error is non-
zero, which is what will be checked for – the actual error message is not important). You do not
need to model an error state in the machine.
1.1 Program structure
A program in MinHs may evaluate to either an integer, a list of integers, or a boolean, depending on the type assigned to the main function. The main function must always be defined; furthermore, for this task, main is always the only top-level binding. For example:
main :: Int = 1 + 2;
or
main :: Bool = let x :: Int = 1;
in if x + ((recfun f :: (Int -> Int) y = y * y) 2) == 0 then True
else False;
1.2 Variables, Literals and Constants
MinHs is a spartan language. We only have to consider 4 types:
Int Bool t1 -> t2 [Int]
The only literals you will encounter are integers. The only non-literal constructors are True and False for the Bool type, and Nil and Cons for the [Int] type.
1.3 Function application
MinHs is, by virtue of its Haskell implementation, a non-strict language. An argument to a function is only evaluated when needed — when the function tries to inspect its value. This does not add a great deal of complexity to your implementation — it will occur naturally as you will be writing the abstract machine in Haskell, which is also a non-strict language.
The result of a function application may in turn be a function.
1.4 Primitive operations
You need to implement the following primitive operations:
+ :: Int -> Int -> Int - :: Int -> Int -> Int * :: Int -> Int -> Int / :: Int -> Int -> Int
negate :: Int -> Int
> :: Int -> Int -> Bool >= :: Int -> Int -> Bool < :: Int -> Int -> Bool <= :: Int -> Int -> Bool
咨询 Alpha 小助手，获取更多课业帮助