
 = 

 ∈ 
 
 ⊂ 

 = 

 = 

 = 

 = 

 = 

 ::= 
 
 
 
⋮  
 

 = 

 ::= 

 = 

 = 

 ::= 
 
 

 = 

 = 

 ::= 
 
 
 
 
 
 
 
 

 = 

 = 

 ::= 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 

 = 

 ::= 
 
 
 
 ::= 
 
 
 
 ::= 

 ::= 

 ::= 

character string (concrete syntax) 
⇒  lexer/ tokenizer 
⇒  token sequence 
⇒  parser  ⇒  parse tree (abstract syntax) 
character string (concrete syntax) 
⇒ 
parser 
⇒  parse tree (abstract syntax) 
 ::= 

 ::= 

a1.py
. Please follow the gsubmit directions.
a1tests.py
. You should be able to place it in the same directory as a1.py
and run it. Feel free to modify or extend it as you see fit.
tokenize()
that takes two arguments: a regular expression string and a character string to tokenize. It should then use the regular expression to convert the second string into a token sequence (represented in Python as a list of strings) and return it.
directions()
that takes a token sequence (represented in Python as a list of strings) and parses that token sequence into a parse tree according to the following grammar definition:
 ::= 
 
 
 
 
 
 
 
 

"Up"
, "Down"
, "Left"
, "Right"
, or "Stop"
. An example input and output are provided below.
Note that the output below omits the token list because it was generated using the json
module. It is fine if your implementation of directions
returns an empty token list along with the parse tree.
analyse()
that takes a grammar definition in the above format as its one argument. The function should return a single string (letter case must match):
"Predictive"
if the grammar can be parsed with a predictive recursive descent parsing algorithm;
"Backtracking"
if the grammar can be parsed with a backtracking recursive descent parsing algorithm;
"Neither"
if the grammar fall into neither of the above categories.
d
, you can use [key for key in d]
; to get the list of keys in a list of dictionaries, you can use [key for d in ds for key in d]
; and to check whether a string x
is in a list or set X
, you can use x in X
.
 ::= 
 
 
 
 
 
 
 
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ::= 
 
 
 
 
 
 
 
 
 
 ::= 
 
 ::= 

program()
, formula()
, term()
, variable()
, and number()
. Each function corresponds to one of the productions. Below is an implementation of number()
:
Your algorithm must parse all programs in this programming language correctly. However, it need not return useful error messages if the input provided does not conform to the grammar definition.
variable()
that takes a single token string as an argument and, if the token sequence conforms to the grammar definition, returns a tuple containing two values: an instance of the abstract syntax (i.e., parse tree) with the root node label "Variable"
, and the remaining, unparsed suffix of the input token sequence.term()
that takes a single token string as an argument and, if the token sequence conforms to the grammar definition, returns a tuple containing two values: an instance of the abstract syntax (i.e., parse tree) with an appropriate root node label ("Plus"
, "Mult"
, "Log"
, "Variable"
, or "Number"
), and the remaining, unparsed suffix of the input token sequence.
formula()
that takes a single token string as an argument and, if the token sequence conforms to the grammar definition, returns a tuple containing two values: an instance of the abstract syntax (i.e., parse tree) with an appropriate root node label ("True"
, "False"
, "Not"
, "And"
, "Or"
, "Equal"
, or "Less"
), and the remaining, unparsed suffix of the input token sequence.program()
that takes a single token string as an argument and, if the token sequence conforms to the grammar definition, returns a tuple containing two values: an instance of the abstract syntax (i.e., parse tree) with an appropriate root node label ("Print"
, "Assign"
, or "End"
), and the remaining, unparsed suffix of the input token sequence.complete()
that takes a single string as an argument. If the input string conforms to the grammar of the programming language, the function should return a parse tree corresponding to that input string.
 ::= 
 
 
 
 
 
 
 
 ::= 
 
 
 
 
 
 
 
 
 
 ::= 
 
 
 
 ::= 
 
 ::= 

assign
... :=
corresponds to :=
, ==
corresponds to equal
, <
corresponds to less
, +
corresponds to plus
, and *
corresponds to mult
).
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ::= 
 
 
 
 
 
 

condition()
function with a generic parser for base cases that contain an arbitrary number of terminals in each sequence.
Any call to condition(...)
can then be replaced with a call to parseBaseCases(seqsCondition, ...)
.
 ::= 
 
 
 
 
 
 
 
 
 
 

 ::= 
 
 
 
 
 
 ::= 
 
 
 
 
 
 
 
 ::= 

[NameofInferenceRule] 

[Example] 

[AlgorithmCase] 

[AlgorithmCase] 

expressions (abstract syntax) 
⇒  evaluation algorithm 
⇒  values (abstract syntax) 
 ::= 
 
 ::= 

[True] 

[False] 

[NotTrue] 

[NotFalse] 

[AndTrueTrue] 

[AndTrueFalse] 

[AndFalseTrue] 

[AndFalseFalse] 

[OrTrueTrue] 

[OrTrueFalse] 

[OrFalseTrue] 

[OrFalseFalse] 

 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 

[True] 

[False] 

[Not] 

[And] 

[Or] 

vnot
, vand
, and vor
correspond to ¬, ∧, and ∨, respectively, in the operational semantics.
statement sequence (abstract syntax) 
⇒  execution algorithm 
⇒  output (record of side effects) 
 ::= 
 
 ::= 
 
 ::= 

[StatementPrint] 

[StatementEnd] 

[FormulaTrue] 

[FormulaFalse] 

[FormulaNot] 

[FormulaAnd] 

[FormulaOr] 

evaluate()
from a previous example.
print()
function and turn this into an interpreter that uses the Python runtime system directly to interpret the program. However, we must be careful about where we put the call to print()
: it must be invoked in a way that conforms to a preorder traversal of the syntax tree.

⇒  execution algorithm 
⇒  output (record of side effects) 
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 

[StatementAssign] 

[StatementPrint] 

[StatementEnd] 

[FormulaTrue] 

[FormulaFalse] 

[FormulaNot] 

[FormulaAnd] 

[FormulaOr] 

[FormulaVariable] 

vnot
, vand
, and vor
are the same as those in a previous example.

⇒  execution algorithm 
⇒ 

 ::= 
 
 
 
 
 
 
 
⋮ 
[StatementAssign] 

[StatementPrint] 

[StatementRepeatTwice] 

[StatementEnd] 

evaluate()
is the same as the one in a previous example, while the implementation of execute()
from that example must be modified so that it also returns an updated version of the environment data structure.
hw2/parse.py
and hw2/interpret.py
. Please follow the gsubmit directions and remember to put your files in the hw2
directory.
a2tests.py
. Feel free to modify or extend it as you see fit.
parse.py
. You should adapt the techniques and/or code from Assignment #1 where appropriate to complete this problem. Recall that all parsers take a sequence of tokens (and possibly a flag) as their input, and return a tuple containing a parse tree and a sequence of remaining tokens.variable()
and number()
that can parse token sequences that conform to the following two productions:
 ::= 
 
 ::= 

formula()
that can parse token sequences that conform to the following production. You may need to perform left factoring on a production before you can implement a working parser. Note that the or operator is omitted intentionally to avoid dealing with issues related to leftassociativity. When parsing the choice "( formula )", you should simply return the parse tree that is obtained from the recursive call corresponding to formula.
 ::= 
 
 
 
 
 
 
 
 
 
 
 
term()
that can parse token sequences that conform to the following productions. These productions ensure that the traditional order of operations for addition and multiplication is preserved in a parser tree. However, you may need to perform left factoring on a production before you can implement a working parser. When parsing the choice "( term )", you should simply return the parse tree that is obtained from the recursive call corresponding to term.
 ::= 
 
 
 
 ::= 
 
 
 
 
 
 
 
 

program()
that can parse token sequences that conform to the following production. Note that the last choice in the production defining program is meaningful: it means that an empty token sequence is a valid program. The parse tree corresponding to an empty program should be 'End'
.
 ::= 
 
 
 
 
 
 
 
  
 ::= 
 
 
 
interpret.py
. Your interpreter must conform to the operational semantics for this language, as presented in each of the problem parts below.evalTerm(env, t)
that takes an environment env
and a parse tree t
as its two arguments. The function should return the value that corresponds to the evaluation of the parse tree t
, as determined by the operational semantics below.[TermNumber] 

[TermVariable] 

[TermLog] 

[TermPlus] 

[TermMult] 

evalFormula(env, f)
that takes an environment env
and a parse tree f
as its two arguments. The function should return the value that corresponds to the evaluation of the parse tree f
, as determined by the operational semantics below.[FormulaTrue] 

[FormulaFalse] 

[FormulaVariable] 

[FormulaNot] 

[FormulaAnd] 

execProgram(env, s)
that takes an environment env
and a parse tree s
as its two arguments. The function should return a tuple containing the output (represented as a list of values) and an updated environment that represent the result of the execution of the program s
as determined by the operational semantics below.[StatementPrint] 

[StatementAssign] 

[StatementIfFalse] 

[StatementIfTrue] 

[StatementWhileFalse] 

[StatementWhileTrue] 

[StatementEnd] 

interpret()
that takes a single string as its argument. The function should tokenize the string, parse it to generate a parse tree, and then execute it to obtain an output. It should then return the output. Your implementation only needs to interpret entire programs; you do not need to interpret standalone terms or formulas.evalFormula()
to use "shortcircuiting" when evaluating the and
operator: if the lefthand subtree evaluates to 'False'
, then do not evaluate the right subtree at all.evalProgram()
not to evaluate the expression in an assignment statement if the variable being assigned never appears in the rest of the program. You may want to implement a helper function that checks if a variable appears in a parse tree corresponding to a program.program (abstract syntax) 
⇒ 

⇒  output and/or value(s) 
character string (concrete syntax) 
⇒ 
interpreter 
⇒  output and/or value(s) 
program (e.g., input/configuration, instructions, etc.) 
computing device (e.g., difference engine, modern CPU, quantum computer, etc.) 
physical laws (mechanics, electricity, chemistry, biology, quantum mechanics, etc.) 
memory


central processing unit (CPU) 
machine program  
machine languauge  

FORTRAN program  
FORTRAN compiler  
machine program  
machine languauge  

application  
highlevel program  
compiler  
machine program  
machine languauge  

user A

user B


highlevel program 
highlevel program 
highlevel program 
highlevel program 

compiler  
machine program 
machine program 
machine program 
machine program 

machine languauge  
operating system  

application  application  application  application 
operating system  
hardware 
app.  app.  
web app. platform  
browser  app.  app.  
API  API  OS  OS  
web service  web service  virtual machine  virtual machine  
dist. platform  web server  virtualization layer  
controller  controller  OS  host operating system  
node  node  node  node  node  node  node  node  server  hardware (web/cloud server) 
source language abstract syntax 
⇒  compiler  ⇒  target language abstract syntax 
source language concrete syntax 
libraries  
⇓  ⇓  
parser  linker  ⇒  target language concrete syntax 

⇓  ⇑  
source language abstract syntax 
⇒  compilation algorithm 
⇒  target language abstract syntax 
source language abstract syntax 
⇒  comp. alg. A 
⇒  IR #1 
⇒  comp. alg. B 
⇒  IR #2 
⇒  comp. alg. C 
⇒  target language abstract syntax 
 ::= 
 
  
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 

 ::= 
 
  
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 

copy()
function below can be viewed as a macro that generates a specific machine language program.
increment()
that takes a single argument, a memory address, and generates a machine program that increments the value at the address specified memory address. We could then implement the following macro, which will set an entire region of memory to a particular constant.
setAllToInRegion()
on specific inputs generates a machine language program for a particular region.
 ::= 

compileFormula()
that takes as its input the parse tree, and a variable heap
that represents the highest address in memory that contains a computed value (in our case, 1
can represent true and 0
can represent false). The function returns a list of machine language instructions that computes that value, as well as the memory address where that value would be stored if anyone actually executed (or simulated) the machine language program.
 ::= 
 
 
 
 
 
 
 
  
 ::= 

hw3/parse.py
(there is no need to modify this file);hw3/interpret.py
;hw3/machine.py
;hw3/compile.py
.hw3
directory.
a3tests.py
. You should be able to place it in the same directory with the other assignment files and run it. Feel free to modify or extend it as you see fit.
/hw3/solutions
.
hw3/interpret.py
. The abstract syntax for the language is presented below:
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 
 
 
 
 
 
 
 
 
 
 
 
  
[TermVariable] 

[FormulaVariable] 

[FormulaOr] 

[StatementAssign] 

[StatementProcedure] 

[StatementCall] 

evalTerm(env, t)
that takes an environment env
and a parse tree t
as its two arguments. The function should return the value that corresponds to the evaluation of the parse tree t
, as determined by the operational semantics.evalFormula(env, f)
that takes an environment env
and a parse tree f
as its two arguments. The function should return the value that corresponds to the evaluation of the parse tree t
, as determined by the operational semantics.execProgram(env, s)
that takes an environment env
and a parse tree s
as its two arguments. The function should return a tuple containing an updated environment and the output (represented as a list of values) that represent the result of the execution of the program s
as determined by the operational semantics.hw3/machine.py
already contains a simulator for the machine language with which you will be working; the machine language is defined in detail in a previous example in the lecture notes.
Although any correct implementation is acceptable, it is suggested that you follow the conventions below:
1
, for the stack;7
to store the memory address of the top of the stack;8
and higher for the heap (i.e., results of computations).hw3/machine.py
.increment(addr)
that takes a single integer argument addr
. The function should return a list of instructions (in which each instruction is represented as a string in the list). These instructions should correspond to a machine language program that increments by 1
the integer stored in the memory location addr
and cleans up any memory addresses it used in the process by setting them back to 0
.decrement(addr)
that takes a single integer argument addr
. The function should return a sequence of instructions (represented as a Python list of strings). These instructions should correspond to a machine language program that decrements by 1
the integer stored in the memory location addr
and cleans up any memory addresses it used in the process by setting them back to 0
.call(name)
that takes a single argument: name
is a string corresponding to the name of a procedure. The function should return a sequence of instructions that performs the following operations:
name
supplied;procedure(name, body)
that takes two arguments: name
is a string corresponding to the name of a procedure, and body
is a sequence of machine language instructions (represented as a Python list of strings). The function should return a sequence of instructions that includes:
compileTerm(env, t, heap)
that takes three arguments: env
is a mapping from variables to memory addresses, t
is a term parse tree, and heap
is the memory address of the current top of the heap. The function should return a tuple (insts, addr, heap)
in which insts
is a sequence of machine language instructions (represented as a Python list of strings) that perform the computation represented by the parse tree, addr
is the address of the result, and heap
is an integer representing the memory of the top of the heap after the computation is performed.compileFormula(env, f, heap)
. The requirements for this function are the same as those for compileTerm(env, t, heap)
, except that it must handle formula parse trees.compileProgram(env, s, heap)
that takes three arguments: env
is a mapping from variables to memory addresses, s
is a program parse tree, and heap
is the memory address of the current top of the heap. The function should return a tuple (env, insts, heap)
in which env
is an updated environment, insts
is a sequence of machine language instructions (represented as a Python list of strings) that perform the computation represented by the parse tree, and heap
is an integer representing the memory of the top of the heap after the computation is performed.compile(s)
that takes a single string s
that is a concrete syntax representation of a program in the source programming language and returns its compiled form: a sequence of instructions in the target machine language.source language abstract syntax 
⇒ ⇐ 
optimization algorithm #1 
⇓  
compilation algorithm A 

⇓  
intermediate representation (IR) #1 
⇒ ⇐ 
optimization algorithm #2 
⇓  
compilation algoritm B 

⇓  
intermediate representation (IR) #2 
⇒ ⇐ 
optimization algorithm #3 
⇓  
compilation algorithm C 

⇓  
target language abstract syntax 
⇒ ⇐ 
optimization algorithm #4 
source language abstract syntax 
⇒  compilation algorithm 
⇒  target language abstract syntax 
⇓  ⇓  
source language operational semantics (interpreter) 
target language operational semantics (simulator) 

⇓  ⇓  
source language abstract syntax for values/outputs 
⇒  simple conversion algorithm for values/outputs 
⇒  target language abstract syntax for values/outputs 
 = 

 ::= 

source language concrete syntax 
target language abstract syntax 

⇓  ⇑  
parser  ⇒  source language abstract syntax 
⇒  static analysis algorithms 
⇒  abstract syntax or IR 
⇒  compilation algorithms 
⇓  ⇓  
syntax errors 
other errors (unbound variables, type errors, etc.) 
 ::= 
 
 
 
 
 
 
 
 

 ::= 
 
 

[FormulaTrue] 

[FormulaFalse] 

[FormulaNot] 

[FormulaAnd] 

[FormulaOr] 

[TermNumber] 

[TermPlus] 

 ::= 
 
  
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 
 
 
 
 

[StatementAssign] 

[StatementEnd] 

[Variable] 

[FormulaTrue] 

[FormulaFalse] 

[FormulaNot] 

[FormulaAnd] 

[FormulaOr] 

[TermNumber] 

[TermPlus] 

[TermMult] 

 ::= 
 
 
 
  
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 
 
 
 
 

[StatementAssign] 

[StatementFunction] 

[StatementEnd] 

[TermVariable] 

[TermNumber] 

[TermPlus] 

[TermApply] 

 ::= 
 
 
 
  
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 
 
 
 
 
 
 ::= 
 
 
 
[StatementAssign] 

[StatementFunction] 

[StatementEnd] 

[TermVariable] 

[TermNumber] 

[TermConcat] 

[TermApply] 

 ::= 
 
 
 
 
 
 
 
  
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 

[ExpressionNumber] 

[ExpressionMult] 

[StatementPrint] 

[StatementFor] 

[StatementProcedure] 

[StatementCall] 

[StatementEnd] 

 ::= 
 
 
 
 
 
 
 
  
 ::= 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 

[DurationMinutes] 

[DurationHours] 

[DurationDays] 

[StatementReserve] 

[StatementFor] 

[StatementProcedure] 

[StatementCall] 

[StatementEnd] 

imperative  procedural  object oriented 
declarative  functional  static type checking 
garbage collection 
side effects 

machine languages 
some support (indexed memory, branching) 
no support  no support  no support  no support  none  no  yes  
FORTRAN (initial release) 
full support  no support  no support  no support  no support  very limited 
no  yes  
C  full support  full support  no support  no support  some support (function pointers) 
very limited 
no  yes  
C++  full support  full support  full support  class declarations, some type checking 
function pointers and some extensions (e.g., STL) 
limited  no  yes  
Java  full support  full support  full support  type system, class declarations, abstract classes, interfaces, type checking, and type inference 
generics, interfaces, objects as wrappers, anonymous classes 
extensive  yes  yes  
PHP  full support  full support  full support  no support  some support  none  yes (≥ 5.3) 
yes  
Python  full support  full support  full support  no support  full support  none  yes  yes  
JavaScript  full support  full support  full support  no support  full support  none  yes  yes  
Haskell  metasupport (monads) 
metasupport (functions) 
no support  full support  full support  extensive  yes  some (IO monads) 

SQL  some support (insertion/ deletion; sequences of statements in versions like MSSQL) 
some support (procedures in versions like MSSQL) 
no support  full support (definition of schemas and tables; ability to evaluate queries over tables) 
some support (custom map and aggregation procedures in MSSQL) 
some  yes  some  
Amazon Web Services APIs 
some support  no support  no support  some support  some support  none  n/a  yes 
 ::= 
 
 ::= 

 = 

 = 

 = 

 = 

 = 

 ≠ 

 ::= 
 
 ::= 

 = 

 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
 = 
 
==
operator), and Haskell supports the automatic derivation of this algorithm for any data type (using the deriving Eq
directive).
Tree
algebraic data type. However, in order to actually display instances of the data type, it is necessary to ask the Haskell interpreter to derive a definition of a show
function automatically from the definition of the algebraic data type (something that is done implicitly in, for example, Python). Haskell requires that this be requested explicitly because it also allows users to define their own variants of such functions.
_
) in patterns makes it possible to write even more concise definitions.
==
. To have the Haskell interpreter or compiler derive it automatically, you can use deriving Eq
. These can be combined with other deriving
directives, such as in the example below.
hw4/parse.py
(there is no need to modify this file);hw4/interpret.py
;hw4/Tree.hs
.hw4
directory.
a4tests.py
. You should be able to place it in the same directory with the other assignment files and run it. Feel free to modify or extend it as you see fit.
hw4/interpret.py
.subst(s, a)
that takes two arguments: a substitution s
(represented as a Python dictionary), and an abstract syntax tree a
. The function should return a new abstract syntax tree in which every variable in the tree that is in the domain of s
has been substituted according to the substitution s
. You may assume that variables are always represented using a subtree of the form {"Variable":[ ... ]}
, as in all previous examples and assignments.unify(a, b)
that takes two arguments: two syntax trees a
and b
. The function should return the smallest substitution s
that satisfies the following equation:
hw4/interpret.py
. The abstract syntax for the language is presented below; a complete parser that parses the concrete syntax for this language into the abstract syntax below can be found in hw4/parse.py
. Notice that in the concrete syntax, constructor names always begin with an uppercase letter, while variable names always begin with a lowercase letter.
 ::= 
 
  
 ::= 
 
 
 
 
 
 
 
 
 
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 

build(m, d)
that takes a finite map m
(i.e., a Python dictionary mapping names to lists of (pattern, expression) tuples) and a declaration parse tree d
. The function should return the finite map m
that represents the module definition that is assembled according to the operational semantics presented below:[DeclarationFunctionFirst] 

[DeclarationFunctionMore] 

[DeclarationEnd] 

 ::= 
 
 
 
 

evaluate(m, env, e)
that takes a module m
, an environment env
, and an expression abstract syntax tree e
as its three arguments. The function should return the value that corresponds to the evaluation of the abstract syntax tree e
, as determined by the operational semantics presented below. Note that the [ExpressionApply] requires using a unification algorithm to obtain a substitution σ that unifies p and v_{1}.[ExpressionConstructorArgs] 

[ExpressionConstructorNoArgs] 

[ExpressionNumber] 

[ExpressionVariable] 

[ExpressionPlus] 

[ExpressionApply] 

build()
and evaluate()
are implemented, you can use the interact()
function in hw4/interpret.py
to query modules.hw4/Tree.hs
. You will be working with the following data type definition, which has already been included in the file:
Tree
in Tree.hs
so that the functions (==)
and show
are automatically generated for this data type.leaves :: Tree > Integer
that returns an integer representing the total number of leaves in the input tree.
nodes :: Tree > Integer
that returns an integer representing the total number of nodes in the input tree.
height :: Tree > Integer
that returns an integer representing the height of the input tree. Trees consisting of a Leaf
are defined to have height 1
.
perfect :: Tree > Bool
that returns True
if the input tree is perfect and False
otherwise.
degenerate :: Tree > Bool
that returns True
if the tree supplied is degenerate, and False
otherwise.
infinite :: Tree
that has no leaves.
 ::= 
 
 
 
 
 
 
 
 
 
 
 
 
 
⋮  
 
 
 
 
 
 
⋮  
[Integer]
.
Tree
data type that we have already seen. If we were to define our own algebraic data type for lists in Haskell, for example, we could do so as follows (the terms "nil" and "cons" are commonly used in the functional language community for the empty list and for the list node constructor, respectively):
[]
, and the list node constructor is the operator (:)
, which can also be written as an infix operator :
. The following three syntaxes are equivalent, and evaluate to the same list [1,2,3]
:
String
; strings in Haskell are just lists of characters:
GameStrategyAlgorithm
is equivalent to the type [[(Integer, Integer)]] > String
(i.e., the type for functions that take lists of lists of integer pairs and return a string):
1
in every position:
(:)
list node constructor:
n
elements of a list (note that this function is already included in the Prelude
).
take
.
addInfiniteLists
function to add two infinite lists. Suppose we have the following definitions:
3
:
g
is a function that takes an integer as an argument. It then throws this argument away and returns the function f
. Its type reflects this. Thus, the result of evaluating an expression such as g(4)
is a function of type Integer > Integer
, and this function can be applied to another argument.
g
that can be partially applied to only some of its arguments, but that still uses all of its arguments? We can do so by listing multiple, spaceseparated parameters in the definition of g
.
g
to arguments one at a time, as before.
0
, 1
, 2
, and so on) and builtin operators (such as +
, *
, and so on).
Meters
.
Meters
to strings.
$
syntax to easily write down abstract syntax trees.
parseTree
will yield the actual algebraic data type instance (i.e., a parse tree).
if ... then ... else ...
for writing conditional expressions:
if ... then ... else ...
syntax (or function, as we have seen above) can be useful in certain situations.
String
and a value (e.g., an Integer
). For example:
lookup
. However, since it returns a result that is wrapped in a Maybe
constructor, we can unwrap it using, e.g.:
Red
has the lowest frequency and Blue
has the highest frequency, we can define an ordering on all instances of this data type by making the Color
type a member of the Ord
type class. Note that we could use wildcards (_
) to make the definition more concise.
<
, <=
, >
, and >=
to compare colors, as well as library functions such as max :: Color > Color > Color
, min :: Color > Color > Color
, maximum :: [Color] > Color
, and minimum :: [Color] > Color
.
compose
?
compose
; let's substitute one the rightmost Function
synonym with its definition:
>
type operator is rightassociative; this means we can remove the rightmost set of parentheses without changing the meaning of the type:
compose
: it takes two Function
arguments, and one Integer
argument:
(.)
. So we could also have defined compose
as follows:
X
or O
somewhere on the board. We can model this using a function that, given a move, transforms one board into another board. We use a list comprehension that updates only the cell with the corresponding position.
X
and O
players take alternating turns.
Board
), and can have any number of child trees (including zero).
nextMoves
takes a Board
and a Cell
(to indicate which player is taking a turn), and uses a list comprehension to choose only the board cells that are empty. For each empty cell, it adds a new board state to the list in which that position is filled with the specified player's symbol.
win :: Cell > Board > Bool
that checks if a given board is already a win for a particular player. We can then add an Ord
instance to compare boards from player X
's perspective: a board is "greater" (or "better") than another board if either the board is a win for X
, or the other board is a loss for O
.
<
, <=
, >
, and >=
to compare boards, as well as library functions such as max :: Board > Board > Board
and maximum :: [Board] > Board
to choose the "best" boards.
hw5
directory.
a5tests.hs
. You should be able to place it in the same directory with the other assignment files and load it. Feel free to modify or extend it as you see fit.
hw5/Interpreter.hs
.eval :: ([(String, Value)], Exp) > Value
that takes two arguments: an environment data structure of type [(String, Value)]
and an expression abstract syntax tree of type Exp
. It should return the value that is the result of evaluating the expression abstract syntax tree according to the following operational semantics:[ExpValue] 

[ExpVariable] 

[ExpPlus] 

[ExpNot] 

[ExpAnd] 

[ExpOr] 

exec :: ([(String, Value)], Stmt) > Output
that takes two arguments: an environment data structure of type [(String, Value)]
and a statement abstract syntax tree of type Stmt
. It should return the output that is the result of executing the statement abstract syntax tree according to the following operational semantics:[StatementAssign] 

[StatementPrint] 

[StatementEnd] 

Exp
by using the builtin Haskell infix operator +
instead of the constructor Plus
, and by using numeric literals such as 123
instead of Number 123
.hw5/Allocation.hs
.
Alloc
:
Graph
data type:
graph :: Alloc > [Item] > Graph
that takes a starting allocation and a list of items, and returns the full graph of all possible state space traversals available to an algorithm given the list of items. An example is provided below (spacing has been adjusted for legibility):
alloc :: Graph > Alloc
that makes it easy to retrieve the allocation within the root node of a particular graph of type Graph
.
a :: Alloc
is better than another allocation b :: Alloc
if the difference between the two bin totals in a
is less than the difference between the two bin totals in b
. Add an instance declaration for the Alloc
type so that it is possible to use the builtin Haskell infix operators <
and <=
to compare two allocations according to their differences. You may use the Haskell library function abs :: Integer > Integer
to compute the absolute value of an integer. If you're getting a stack overflow when testing <
, make sure you also define <=
explicitly.
g :: Graph
is better than another graph g' :: Graph
if the difference between the two bin totals in the root node of g
is less than the difference between the two bin totals in the root node of g'
. Add an instance declaration for the Graph
type so that it is possible to use the builtin Haskell infix operator <
to compare two graphs.
final :: Graph > [Alloc]
that returns an aggregate list of the allocations within all the leaf nodes of the supplied state space graph.depth :: Integer > Graph > [Alloc]
that returns the allocations within the state space graph nodes that are at depth exactly n
within the state space graph (the root node is at depth 0
).hw5/Allocation.hs
.
greedy :: Strategy
that takes a graph as an input. It should choose and return the better child of the two children of the root of the graph.patient :: Integer > Strategy
that takes an integer argument n
and a graph as its two inputs, and chooses and returns the best descendant of the supplied graph that can be found at depth n
(an allocation is best if it is better than all others at that depth). If n
is 0
, the function should simply return the graph supplied to it as an input.optimal :: Strategy
that takes a state space graph, and returns the leaf node in the state space graph that has the best allocation. Hint: you can define this function in two lines; look carefully over the functions already available to you, and think recursively.metaCompose :: Strategy > Strategy > Strategy
that takes two strategies as arguments. It should apply the first strategy to obtain a new subgraph, and then it should apply the second strategy to that subgraph and return the result.
metaRepeat :: Integer > Strategy > Strategy
that repeats a given strategy a specified number of times. Your definition of metaRepeat
should take an Integer
and a Graph
argument. If the integer is 0
, it should simply return the graph unchanged. If the integer is positive, it should apply the strategy the specified number of times to the graph and then return the result.metaGreedy :: Strategy > Strategy > Strategy
that takes two strategies as its inputs. It should apply the two strategies to its input graph and should return the better of the two results that it obtains.impatient
is superior to patient
, and one way in which it is inferior.fit :: Graph > [Strategy] > Strategy
that takes a graph and a list of strategies as inputs; this metastrategy should choose the strategy in the list of strategies that has the best performance on the given graph, and return it. Hint: define a way to compare strategies and use minimumBy
.Set
data structure for holding sets of Integer
values that has an underlying list implementation.
Type > Type
, and so on).
Set
data structure for holding sets of values of any type a
.
Set
data structure for holding sets of values of any type a
that has a corresponding size :: Set a > Int
function.
<
operator by making the type Set a
(for any possible a
) a member of the Ord
type class.
a
must be in the Eq
type class. This is because the definition of Set a
contains a deriving Eq
clause, which means that a type Set a
can only be used in a module if the parameter type a
is a member of the Eq
type class (otherwise, Haskell would not be able to compare two sets for equality using the automatically derived definition of (==)
generated by the deriving Eq
clause).
Integer
lists that does nothing.
(:)
and []
) in the input list with a binary operator and a base case (in this case, (+)
and 0
). This way, the fold
function now computes the sum of the elements in the list.
(:)
, so it must be of type Integer > Integer > Integer
, and a replacement for []
, which must be of type Integer
.
fold
implementation to define many common functions on lists of integers.
(:)
and []
) is called foldr
.
foldr
function can be used to implement many of the usual library functions one might find useful when working with lists, and this is what is done in the Haskell libraries. Below are some examples (some of these are simplified versions of what is actually found in the libraries).
1
to every element in an Integer
list. For example, we want to achieve the following using a call to foldr
:
1
to its first argument, then builds the list node:
foldr
:
addOneThenCons
:
foldr
:
consIfPositive
:
(Name, Age)
:
Name
entries in the table; this query amounts to a map operation:
Age
range; this query amounts to a filter operation:
Age
fields of all the entries; this query amounts to fold operation (it is often called an aggregation operation):
map
, filter
, foldr
, and λ abstractions instead of list comprehensions (the Haskell compiler simply converts list comprehensions into some combination of these during compilation):
map
, filter
, reduce
(similar to Haskell's foldr
), and lambda abstractions:
li
elements and updates the text content of each to indicate the item number corresponding to that element. Notice that the .text()
function takes a function as an argument (the function supplied as an argument takes an index as an input and returns a string):
.each()
function.
hw6
directory.
a6tests.hs
. You should be able to place it in the same directory with the other assignment files and load it. Feel free to modify or extend it as you see fit.
hw6/Tree.hs
.leaves :: Tree a > Integer
that takes a tree and returns the total number of leaves in the tree. An Empty
tree contains no leaves.
insert :: a > Tree a > Tree a
that takes an argument of any type a
and another argument of type Tree a
and inserts the new item of type a
into the tree so that the height of the resulting tree is minimized. In other words, the definition should be recursive:
fold :: (a > a > a) > Tree a > a
that takes a function of type a > a > a
and a tree of type Tree a
, and performs a fold over the tree using the function of type a > a > a
in order to return a single result of type a
. You may assume that the input tree is always nonempty.
hw6/Metaql.hs
. The abstract syntaxes for statements, expressions, and types for this programming language are defined below.
 ::= 
 
 ::= 
 
 ::= 

[ExpInteger] 

[ExpString] 

[ExpPlus] 

[ExpConc] 

[StmtPrint] 

[StmtEnd] 

instance Num Exp
declaration so that it is possible to use (*) :: Exp > Exp > Exp
to build abstract syntax trees representing string concatenation operations.
tyExp :: Exp > Maybe Type
that takes an Exp
abstrax syntax tree and, if it conforms to the type inference rules, returns its type (wrapped using the Just
constructor). If the expression has no valid type according to the type inference rules, tyExp
should return Nothing
.tyStmt :: Stmt > Maybe Type
that takes a Stmt
abstrax syntax tree and, if it conforms to the type inference rules, returns its type (wrapped using the Just
constructor). If the statement has no valid type according to the type inference rules, tyStmt
should return Nothing
.flat :: Exp > [Exp]
that takes an Exp
abstract syntax tree and returns a list that contains all the leaf nodes (i.e., integers and strings) in the original tree (in the order obtained via an inorder traversal of the tree).size :: Exp > Int
that takes an Exp
abstract syntax tree and returns the number of leaf nodes (i.e., integers and strings) in the tree.hw6/Metaql.hs
.
You should not evaluate the expressions for this problem. The number of nodes and leaves in the abstract syntax tree must remain the same after refactoring has occurred. Solutions that do not conform to this requirement will receive no credit.refactorInt :: Exp > Exp
that takes an Exp
abstrax syntax tree as its argument. If the tree has Metaql type TyInt
, the function should take advantage of the associative and commutative properties of addition by returning a tree with an equivalent meaning (i.e., the result of evaluating the tree should not change) that is of the least possible height. If the tree is not of Metaql type TyInt
, no changes should be made. Hint: flatten the tree, use foldr
and insert
to build a tree of type Tree Exp
, and then use fold
over the tree to rebuild the expression using the binary operator that corresponds to the tree's original type.refactorStr :: Exp > Exp
that takes an Exp
abstrax syntax tree as its argument. If the tree has Metaql type TyStr
, the function should take advantage of the associative property of string concatenation by returning a degenerate tree with an equivalent meaning (i.e., the result of evaluating the tree should not change) in which only rightassociative concatenation occurs. If the tree is not of Metaql type TyStr
, no changes should be made. Hint: flatten the tree and use foldr
together with other standard list functions to rebuild the tree.refactor :: Stmt > Stmt
that refactors all the Exp
subtrees so that all subtrees of Metaql type TyInt
have the minimum height possible, and so that all subtrees of Metaql type TyStr
only contain rightassociated applications of concatenation.hw6/Compile.hs
. The abstract syntaxes for statements in Protoql are defined below; the file hw6/Protoql.hs
contains a Haskell implementation of an abstract syntax data structure for Protoql.
 ::= 
 
 ::= 
 
 
 
 
 
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 
 
 ::= 

[Input] 

[QueryLeft] 

[QueryRight] 

[Output] 

compExp :: [InLabel] > OutLabel > Exp > [Query]
that takes a list of unused input labels, a target output label, and an Exp
abstract syntax tree. The function should return a list of Protoql queries that corresponds to a valid Protoql program that computes the result of the expression:
Exp
tree is a base case, emit an appropriate Input() Protoql instruction and specify its destination using the OutLabel
argument;Exp
tree is a binary operator, obtain the Protoql instructions for each subtree (use size
together with take
and drop
to ensure that the input label lists for the two recursive calls do not overlap), then return a list containing all the instructions for the two subtrees, and one additional Query() instruction corresponding to the binary operation that must be performed.compStmt :: [InLabel] > Stmt > [Query]
that takes a list of unused input labels, and a Metaql Stmt
abstract syntax tree. The function should return a list of Protoql queries that corresponds to a valid Protoql program that computes the results of all the Print statements in the Metaql Stmt
tree. Each result should be sent to a new Output() query with its own unique input label.compile :: Stmt > Maybe Program
that takes a Metaql Stmt
abstrax syntax tree, ensures that the tree conforms to the Metaql type inference rules, and if so, optimizes the tree, and compiles it into a valid Protoql program. If the Stmt
tree does not conform to the type system, the function should not attempt to optimize or compile the tree; it should return Nothing
.time :: Stmt > Maybe Integer
that takes a Metaql Stmt
abstrax syntax tree and computes the minimum running time in seconds of the fastest valid Protoql program into which it can be compiled (i.e., running the Protoql program should yield a correct result under all circumstances).
servers :: [Exp] > Integer
that computes the minimum number of servers that is required to run all the queries in the input list in parallel in the fastest time possible (as determined by a correct implementation of time
).
maximum
and/or minimum
, foldr
, zip
, sum
, and other list functions to implement a very concise solution.reassign :: [Query] > [Query]
that updates the server entries in all the queries with new server names so that the running time of the query under the new semantics will conform to the output of time
. You may assume the servers 0.protoql.org
, 1.protoql.org
, 2.protoql.org
, and so on are all available.height :: Graph > Integer
that computes the height of a Graph
.
width :: Graph > Integer
that computes the width of a Graph
.
 = 


 = 

 = 

AN
can never be unified with the constructor N
, there is no substitution that can be applied to both sides of the original equation to make both sides equivalent.
"cat"
is the subject?
N
leaf constructor can only occur at the botton of a NounPhrase
tree. In other words, the pattern would need to look something like the following:

 ::= 
 
 
 
 

 ::= 
 
 
 
 ::= 
 
 

 ::= 
 
 ::= 
 



input file 
loop unroller 
machine instruction sequences 

⇓  ⇑ ⇓  ⇑  
parser  ⇒  abstract syntax trees 
⇒  type checker 
⇒  abstract syntax trees 
⇒  compiler 
⇓  ⇓  
error messages 
error messages 
exhaustive case generator 

⇓  
abstract syntax trees 

⇓  ⇓  
interpreter  compiler  ⇒  machine instruction sequences 

⇓  ⇓  
outputs  outputs  ⇐  simulator  
⇓  ⇓  
output comparison function 
csa2/csa3
.True
and False
.and
, or
, and not
.+
, *
, 
, and /
. The infix operator //
represents integer division, and the infix operators **
represents exponentiation. Negative integers are prefixed with the negation operator 
.==
, !=
, <
, >
, <=
, >=
are available.int()
function can convert a string that looks like an integer into an integer.'
or "
characters. Strings can be treated as lists of singlecharacter strings. Another way to look at this is that there is no distinction between a character and a string: all characters are just strings of length 1. Multiline strings can be delimited using """
or '''
(i.e., three quotation mark characters at the beginning and end of the string literal).''
or ""
.+
.len()
returns the length of a string.s[i]
). These characters are also strings themselves.[
and ]
, with the individual list entries separated by commas. Lists cannot be members of sets.[]
.+
.len()
returns the length of a list.a[i]
).in
relational operator.(
and )
, with entries separated by commas. The main distinction between lists and tuples is that tuples are hashable (i.e., they can be members of sets).()
.x
is denoted using (x, )
.+
.list()
function.tuple()
function.len()
returns the length of a tuple.t[i]
).in
relational operator.set()
..union()
and .intersect
correspond to the standard set operations.set()
function.list()
or list()
function, respectively.len()
returns the size of a set.in
relational operator.frozenset()
function.
{}
.list(d.keys())
.list(d.values())
.len()
returns the number of entries in the dictionary.d[key]
).for
clause. This will filter which combinations are actually used to add a value to the resulting list.
type()
can be used to determine the type of a value. Below, we provide examples of how to check whether a given expression has one of the common Python types:
if
, else
, and/or elif
), an iteration construct (i.e., a for
or while
loop), a return
statement, or a break
or continue
statement.def
keyword, followed by the name of the function or procedure, and then by one or more arguments (delimited by parentheses and separated by commas).
else
). The body of each branch is an indented sequence of statements.
if
). The body is executed over and over until the expression in the condition evaluates to False
, or a break
statement is encountered.
csa2/csa3
.Example.hs
should contain the Example
module definition). The module body consists of a series of declarations, which can appear in any order; the only exception is that if there are multiple declarations for a function, they must all be grouped together.
True
and False
.&&
, 
, and not
.if ... then ... else ...
is also available (similar to Python's ... if ... else ...
and C/C++/Java's ternary operator ... ? ... : ...
.Int
and an unboundedsize type Integer
.+
, *
, 
, /
, and ^
. The Prelude
function div
represents integer division. The Prelude
functions min
and max
make it possible to compute the minimum and maximum of two integers, respectively, and the function minimum
and maximum
make it possible to compute the minimum and maximum of a list of integers. Negative integers are prefixed with the negation operator 
.==
, /=
(not equal), <
, >
, <=
, >=
are available."
characters (individual characters are always delimited using '
). Strings can be treated as lists of characters.""
.++
.Prelude
function length
returns the length of a string.[
and ]
, with the individual list entries separated by commas.[]
.:
.++
.Prelude
function length
returns the length of a list.Prelude
function elem
(note that this relies on the ==
operation being defined on the type of the elements in the list).(
and )
, with entries separated by commas.()
.(e)
is equivalent to e
for any Haskell expression e
.