Scala代写: 这是一个基础的scala代写任务
COMP 302 Programming Languages and Paradigms
Assignment 4
This assignment focuses on building an evaluator for the WML language within Scala. Your code must run without error or modification using Scala 2.12.
Note that you must follow the given naming, input, and output requirements precisely. All code should be well-commented, in a professional style, with appropriate variables names, indenting (uses spaces and avoid tabs), etc.The onus is on you to ensure your code is clear and readable. Marks will be very generously deducted for bad style, lack of clarity, or failing to follow the required instructions.
Your code should endeavour to follow a pure functional programming style. In particular, and unless specifically stated otherwise, all data types must beimmutable, anddata may not be modified once assigned or bound. Note that this means you may not usevardeclarations,whileordo-loops,ArrayBuffersor other mutable structures, nor may you reassignArrayelement values after creation.
This assignment focuses on typing and exploring WML as a functional language. You can use your own evaluator or the one provided as a solution to assignment 3. You do not need need to provide your evaluator code, but should assume any WML code you write in this assignment will be tested with the official assignment 3 solution.
- We can try to encode-calculus in WML. To do so, though, well need a data structure of some form. You already know that closures can be used to encapsulate data and control access, so that is what we will use. Using-calculus syntax, we can basic data aggregation with just functions by formingpairsof data. The term PAIR= xyf.fxyconstructs a pair ofxandy, returning a function which accepts a function that will operate on the pair of elements. We can then access the first part of the pair with the term HEAD= p.p(xy.x), which accepts a PAIR construction, and passes in a function that retrieves the first half of the pair. Similarly, the second part of the pair can be retrieved with the term TAIL= p.p(xy.y). To understand it better, it may be helpful to verify for yourself thatHEAD (PAIR a b)evaluates toa, and TAIL (PAIR a b)evaluates tob.
(a) Based on the-calculus definitions, define similarpair,head, andtailfunctions in WML. Verify 5
that{{head|{{pair|A|B}}}}==A, that{{tail|{{pair|A|B}}}}==B, and that it
continues to work for deeper nesting; e.g.,
{{head|{{tail|{{pair|A|{{pair|C|D}}}}}}}}==C.
(b) Use your pair construction to encode-terms in WML. Define constructor functions for building 5
WML-encoded-terms astaggedpairseach term is a pair with head (string tag) representing
what the tail holds, either avar,app, orabs. The tail then contains the actual datathe actual
variable name, or the two terms involved in an application, or the abstraction var and body.
- Define a functionvarwhich encodes a base variablevas a pair. Thus the invocation{{var|x}} represents the-termx. To simplify extractingvfrom your encoding, also define a functionvnamewhich receives an encoded variable and returns the actual variable. Verify{{vname|{{var|x}}}}==x.
- Define a functionappwhich encodes an applicationM N. Given previously WML-encoded termsMandN, the invocation{{app|M|N}}thus represents the-term(M N).
To simplify extracting the components, also define functionsapp1andapp2which returnM
andNfrom anappconstruction respectively.
- Define a functionabswhich encodes an abstractionx.M. Given a base variablexand a pre- viously WML-encoded termM, the invocation{{abs|x|M}}represents the-term(x.M). To simplify extracting the components, also define functionsparamandbodywhich return xandMfrom anabsconstruction respectively. (c) With the above in place, you can define arbitrary-terms in WML. But it is not the nicest syntax. 5 Define a WML functionpprintthat receives a WML-encoded-term and evaluates into the corresponding, nicely formatted-term using standard-calculus syntax. Thus, {{pprint|{{abs|x|{{app|{{var|x}}|{{var|y}}}}}}}}==(x.(x y)) You may write lambda x instead of x if you prefer. Whitespace is not significant (we will stick to single-character variables). (d) Define a WMLsubstitutefunction that works on your encoding. This function does the bulk 5 of work in-reduction,^1 substituting a term for all free instances of a given variable within another term. Yoursubstitutefunction should accept three parameters,M,v, andN, whereMandNare WML-encodings of-terms, andvis a base variable. It should return a WML-encoding of M[v7 N], replacing all free instances ofvinMwithN.
Submit a fileq1.wmlwith your code, using plain text to indicate each section. Format each function on
a new line for readability (blank lines will be ignored in testing).
- Suppose we have a restricted language, where data may be either a non-pointer, or a pointer (reference) to a non-pointer, or a pointer to a pointer to a non-pointer, etc. We could define a simple formal type-system for our data modeling the levels of pointer indirection with the following inductive type definition, ::=|! whereindicates a non-pointer type (or a pointer to nothing), and !means a pointer to something of type. Comparison operations still need a boolean type, so our full type system consists of {bool}, although we will only allow actual data to be declared types in. To manipulate pointers, the & and * operators are used for referencing (making a pointer of) and deref- erencing (removing one pointer level from) variables, and are applied in a right-associative fashion. For example, ifvis a non-pointer (i.e.,v:) then we may type the expression&&v:! !, and the expres- sion&&v: !. Consider now a program in this language, as below:
let x=&y in
let z=&x in
let w=*z in
if (w==x) then
let r=*&y in r
else
let r=**z; in r
(a) Come up with a formal set of rules for typing all the code constructs used in the above code. 5
(b) With the initial assumption thaty:, what is the type of the above code? Give a formal proof using 10
your rules to prove your typing is correct.
(^1) It does not address inadvertent capture.
Submit a pdf document, q2.pdf, with all fonts embedded, clearly identifying your rules, and showing the
full type proof. You may break the proof up into sub-proofs to better fit it on a page, but the structure
must be clear.
A handwritten (scanned into pdf) proof is ok, provided your writing is very clear.
What to hand in
Submit your assignment toMyCourses. Note that clock accuracy varies, and late assignments will not be accepted without a medical note:do not wait until the last minute. Assignments must be submitted on the due datebefore 6pm.
This assignment is worth 10% of your final grade. 35