|
| = |
|
| ∈ |
| |||
| ⊂ |
|
| = |
|
| = |
|
\(
, \)
special characters make it possible to include parentheses in expressions in a way that does not cause them to interpreted as regular expression grouping symbols;\s
matches a single whitespace character;[0-9]
matches a single numeric digit;[a-z]
matches a single lowercase letter;[A-Z]
matches a single uppercase letter;[a-zA-Z]
matches a single letter;[a-zA-Z0-9]
matches a single alphanumeric character.re
module provides functionality for automatically checking whether a string matches a particular regular expression. In order to check whether a string exactly matches a regular expression, it is necessary to wrap the regular expression in parentheses and then add special markers to ensure that the regular expression matches from the beginning of the string to the end of the string.
None
is returned.
| = |
|
| = |
|
| = |
|
| ||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
|
| ::= |
| |||
| |
| ||||
⋮ | |||||
| |
|
| = |
|
| ::= |
|
| = |
|
| = |
|
| ::= |
| |||
| |
|
| = |
|
| = |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
| = |
|
| ||||||
| |||||||||
| |||||||||
| |||||||||
| |||||||||
|
| = |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
|
| = |
|
| ::= |
| |||
| |
| ||||
| ::= |
| |||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
| ::= |
| |||
| |
|
| ::= |
| |||
| |
|
character string (concrete syntax) |
⇒ | lexer/ tokenizer |
⇒ | token sequence |
⇒ | parser | ⇒ | parse tree (abstract syntax) |
character string (concrete syntax) |
⇒ |
parser |
⇒ | parse tree (abstract syntax) |
| ::= |
| |||
| |
|
| ::= |
| |||
| |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
|
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, ...)
.
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
hw1/hw1.py
. Please follow the gsubmit directions.
hw1-tests.py
. You should be able to place it in the same directory as hw1.py
and run it. Feel free to modify or extend it as you see fit.
tokenize()
that takes two arguments: a list of terminals and a concrete syntax character string to tokenize. It should build a regular expression, use that regular expression to convert the second string into a token sequence (represented in Python as a list of strings), and then return that token sequence. You should not assume the tokens will always be separated by spaces in the concrete syntax.
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:
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
"Forward"
, "Reverse"
, "LeftTurn"
, "RightTurn"
, or "Stop"
. An example input and output are provided below.
Note that the output below omits the token list. It is fine if your implementation of directions()
returns an empty token list along with the parse tree.
json
module. Your implementation does not need to format its results in this way and can produce it in the above format.
#
character):
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| ::= |
| |||
| ::= |
|
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"
, "LessThan"
, or "GreaterThan"
), 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.
| ::= |
| |||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
| ::= |
| |||
| ::= |
|
&&
corresponds to and
, ||
corresponds to or
, ==
corresponds to equal
, <
corresponds to less than
, >
corresponds to greater than
, +
corresponds to plus
, and *
corresponds to mult
).
| ::= |
|
[Name-of-Inference-Rule] |
|
[Example] |
|
[Algorithm-Case] |
|
[Algorithm-Case] |
|
expressions (abstract syntax) |
⇒ | evaluation algorithm |
⇒ | values (abstract syntax) |
| ::= |
| |||
| ::= |
|
[True] |
|
[False] |
|
[Not-True] |
|
[Not-False] |
|
[And-True-True] |
|
[And-True-False] |
|
[And-False-True] |
|
[And-False-False] |
|
[Or-True-True] |
|
[Or-True-False] |
|
[Or-False-True] |
|
[Or-False-False] |
|
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
| |||
| = |
|
[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) |
| ::= |
| |||
| ::= |
| |||
| ::= |
|
[Statement-Print] |
|
[Statement-End] |
|
[Formula-True] |
|
[Formula-False] |
|
[Formula-Not] |
|
[Formula-And] |
|
[Formula-Or] |
|
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 pre-order traversal of the syntax tree.
|
⇒ | execution algorithm |
⇒ | output (record of side effects) |
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
|
[Statement-Assign] |
|
[Statement-Print] |
|
[Statement-End] |
|
[Formula-True] |
|
[Formula-False] |
|
[Formula-Not] |
|
[Formula-And] |
|
[Formula-Or] |
|
[Formula-Variable] |
|
vnot
, vand
, and vor
are the same as those in a previous example.
|
⇒ | execution algorithm |
⇒ |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
⋮ |
[Statement-Assign] |
|
[Statement-Print] |
|
[Statement-Repeat-Twice] |
|
[Statement-End] |
|
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.
program (abstract syntax) |
⇒ |
|
⇒ | output and/or value(s) |
character string (concrete syntax) |
⇒ |
interpreter |
⇒ | output and/or value(s) |
hw2/parse.py
and hw2/interpret.py
. Please follow the gsubmit directions and remember to put your files in the hw2
directory.
hw2-tests.py
. Feel free to modify or extend it as you see fit.
parse.py
. You may 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. The functions should return a string or integer, respectively, without wrapping the result in a dictionary. If the first token in the token sequence supplied to a function does not correspond to the production, the function should return None
.
| ::= |
| |||
| ::= |
|
formula()
that can parse token sequences that conform to the following production. You may need to perform left-recursion elimination on a production before you can implement a working parser. You should use the abstract syntax tree node labels "Xor"
, "Not"
, "Parens"
, "Variable"
, "True"
, and "False"
. If the token sequence is not in the language defined by the production, the function should return None
(this will be tested, and is necessary to receive full credit).
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
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 parse tree. However, you may need to perform left-recursion elimination on a production before you can implement a working parser. You should use the abstract syntax tree node labels "Plus"
, "Mult"
, "Log"
, "Parens"
, "Variable"
, and "Number"
. If the token sequence is not in the language defined by the production, the function should return None
(this will be tested, and is necessary to receive full credit).
| ::= |
| |||
| |
| ||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
program()
that can parse token sequences that conform to the following production. You may want to implement a helper parser function expression()
. You should use the abstract syntax tree node labels "Print"
, "Assign"
, "If"
, "While"
, and "End"
. 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"
. If the token sequence is not in the language defined by the production, the function should return None
(this will be tested, and is necessary to receive full credit).
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| | |||||
| ::= |
| |||
| |
| ||||
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.[Term-Number] |
|
[Term-Variable] |
|
[Term-Parens] |
|
[Term-Log] |
|
[Term-Plus] |
|
[Term-Mult] |
|
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 (let ⊕ represent the logical exclusive or operation, which can be implemented with the Python built-in relational operator !=
).[Formula-True] |
|
[Formula-False] |
|
[Formula-Variable] |
|
[Formula-Parens] |
|
[Formula-Not] |
|
[Formula-Xor] |
|
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. Note that end ; corresponds to the empty token sequence and is used as a placeholder to make the notation unambiguous.[Statement-Print] |
|
[Statement-Assign] |
|
[Statement-If-False] |
|
[Statement-If-True] |
|
[Statement-While-False] |
|
[Statement-While-True] |
|
[Statement-End] |
|
interpret()
that takes a single string as its argument. The function should tokenize the string and parse it to generate a parse tree. If parsing fails, it should return None
; otherwise, it should execute the parse tree to obtain an output. It should then return the output. Your implementation only needs to interpret entire programs; you do not need to interpret stand-alone terms or formulas.execProgram()
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 (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 | ||
high-level program | ||
compiler | ||
machine program | ||
machine languauge | ||
|
user A
|
user B
|
|||||||||
high-level program |
high-level program |
high-level program |
high-level 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.
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| | |||||
| ::= |
|
call printProc;
statement, or to the point corresponding to the second call printProc;
statement?
call printProc;
are compiled into machine code that stores the index of the current instruction at each call point at a particular memory location (in this example, suppose it is memory address 7
). Then, the block of machine code into which the procedure body is compiled can always consult the same memory location to determine to which point it should pass control back after the machine code for the procedure body finishes executing. Because control should not go back to the goto instruction but beyond it, it may be necessary to increment the value representing the program location before using the jump instruction. We provide machine language pseudocode below that does just that.
7
, making it impossible to determine the program location to which control must return after the outermost procedure body finishes. To address this, it is possible to have the machine language program maintain a stack starting at memory location 7
that will keep track of all the program locations to which control must return after each nested procedure call finishes. We do so in the machine language pseudocode below.
hw3/parse.py
(there is no need to modify this file);hw3/interpret.py
;hw3/machine.py
;hw3/compile.py
.hw3
directory.
hw3-tests.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/interpret.py
. The abstract syntax for the language is presented below:
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| | |||||
[Term-Variable] |
|
[Formula-Variable] |
|
[Formula-Or-Short] |
|
[Formula-Or] |
|
[Formula-And-Short] |
|
[Formula-And] |
|
[Statement-Assign] |
|
[Statement-Procedure] |
|
[Statement-Call] |
|
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:
hw3/compile.py
. The source language of the compiler will be the language for which you implemented an interpreter in Problem #1. The target language will be the machine language with which you worked in Problem #2.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 |
i
corresponds to memory address 123
).
{'Mult':[{'Number':[3]}, {'Number':[4]}]}
can be evaluated in a finite amount of time, and then replace it with the value to which it evaluates. The overall tree would then look as follows.
[Stmt-For] |
|
[Exp-Comprehension] |
|
high-level source language abstract syntax |
⇒ ⇐ |
loop unrolling |
⇓ | ||
SSA conversion | ||
⇓ | ||
IR in SSA form | ⇒ ⇐ |
constant folding |
⇓ | ||
compilation | ||
⇓ | ||
low-level IR | ⇒ ⇐ |
register allocation |
⇓ | ||
instruction selection |
||
⇓ | ||
low-level target machine language abstract syntax |
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.) |
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
|
| ::= |
| |||
| |
|
[Formula-True] |
|
[Formula-False] |
|
[Formula-Not] |
|
[Formula-And] |
|
[Formula-Or] |
|
[Term-Number] |
|
[Term-Plus] |
|
| ::= |
| |||
| | |||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| |
| ||||
| |
|
[Statement-Assign] |
|
[Statement-End] |
|
[Variable] |
|
[Formula-True] |
|
[Formula-False] |
|
[Formula-Not] |
|
[Formula-And] |
|
[Formula-Or] |
|
[Term-Number] |
|
[Term-Plus] |
|
[Term-Mult] |
|
| ::= |
| |||
| |
| ||||
| | |||||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| |
| ||||
| |
|
[Statement-Assign] |
|
[Statement-Function] |
|
[Statement-End] |
|
[Term-Variable] |
|
[Term-Number] |
|
[Term-Plus] |
|
[Term-Apply] |
|
| ::= |
| |||
| |
| ||||
| | |||||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| |
| ||||
| |
| ||||
| ::= |
| |||
| |
| ||||
[Statement-Assign] |
|
[Statement-Function] |
|
[Statement-End] |
|
[Term-Variable] |
|
[Term-Number] |
|
[Term-Concat] |
|
[Term-Apply] |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| | |||||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
|
[Expression-Number] |
|
[Expression-Mult] |
|
[Statement-Print] |
|
[Statement-For] |
|
[Statement-Procedure] |
|
[Statement-Call] |
|
[Statement-End] |
|
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| | |||||
| ::= |
| |||
| |
| ||||
| |
| ||||
| ::= |
| |||
| ::= |
| |||
| ::= |
| |||
| ::= |
|
[Duration-Minutes] |
|
[Duration-Hours] |
|
[Duration-Days] |
|
[Statement-Reserve] |
|
[Statement-For] |
|
[Statement-Procedure] |
|
[Statement-Call] |
|
[Statement-End] |
|
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 | meta-support (monads) |
meta-support (functions) |
no support | full support | full support | extensive | yes | some (IO monads) |
|
SQL | some support (insertion/ deletion; sequences of statements in versions like MS-SQL) |
some support (procedures in versions like MS-SQL) |
no support | full support (definition of schemas and tables; ability to evaluate queries over tables) |
some support (custom map and aggregation procedures in MS-SQL) |
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/Term.hs
.hw4
directory.
hw4-tests.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:[Declaration-Function-First] |
|
[Declaration-Function-More] |
|
[Declaration-End] |
|
| ::= |
| |||
| |
| ||||
| |
|
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 [Expression-Apply] requires using a unification algorithm to obtain a substitution σ that unifies p and v1.[Expression-Constructor-Args] |
|
[Expression-Constructor-No-Args] |
|
[Expression-Number] |
|
[Expression-Variable] |
|
[Expression-Plus] |
|
[Expression-Apply] |
|
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.twigs :: Tree -> Integer
that returns an integer representing the total number of Twig
values in the input tree.
branches :: Tree -> Integer
that returns an integer representing the total number of branches 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 0
, while trees consisting of a Twig
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 and no twigs.hw4/Term.hs
.
Implement the evaluate :: Term -> Integer
function so that it evaluates abstract syntax trees of the type Term
to obtain values (i.e., integers).
| ::= |
| |||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
| |
| ||||
⋮ | |||||
| |
| ||||
| |
| ||||
| |
| ||||
⋮ | |||||
[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
:
user()
and owns()
either as tables in a database (with each declaration for the function acting as a row in the table) or as logical predicates.
file()
and user()
must take place when the program is running. We can make the code more efficient by instead declaring distinct types. Since type checking is performed only at compile time in Haskell, this will still ensure that there are no type errors, but it will be more efficient because fewer function invocations will occur when the program is running.
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, space-separated parameters in the definition of g
.
g
to arguments one at a time, as before.
f
of type Integer -> Integer
and returns a function f'
that is its reflection across the x-axis (i.e., for all x
, f(x)
= -f'(x)
).
(Integer -> Integer) -> (Integer -> Integer)
because ->
is right-associative. This makes it more obvious that reflect
takes a function of type Integer -> Integer
as an input and returns a function of type Integer -> Integer
as an output.
f
of type Integer -> Integer
and returns an integer approximation of its definite integral starting at x = 0.
f
of type Double -> Integer
and returns an approximation of its definite integral starting at x = 0 for a given precision.
f
of type Double -> Double
and returns an approximation of its derivative.
0
, 1
, 2
, and so on) and built-in 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 right-most Function
synonym with its definition:
->
type operator is right-associative; this means we can remove the right-most 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:
&;lt-
can be any pattern. If a pattern appears on the left-hand side of &;lt-
, then each element in the list on the right-hand side will be checked against the pattern. Only those elements that unify with the pattern will be considered, and for each of them, the subsequent conditions in the comprehension, as well as the body of the comprehension, will be evaluated.
example
. The second expression builds a list containing the right subtrees that are not leaves. The last expression builds a list of subtree pairs for each non-leaf tree.
()
for each matching entry and then checking the length of the list resulting from the comprehension, or by comparing it to the empty list.
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.
len
for computing lengths of lists of integers.
Bool
values because the type [Integer]
does not unify with the type [Bool]
. We could write an alternative type to address this.
len
on lists of type [Bool]
, but we can no longer use it on lists of type [Integer]
. Notice that the only thing that has changed is the type of the function; the body is the same in both cases. Haskell allows us to take advantage of this by employing a type variable.
len
function to a list containing any type of element. This is because the type variable a
unifies with any other type (including Bool
and Integer
), so the input type [a]
will unify with both [Integer]
and [Bool]
, as well as types such as [String -> String]
(a list of functions that take String
inputs and return String
outputs).
len
is a function that can be applied to different input types, but has only a single definition that works for all input types, it is an example of parametric polymorphism.
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
.
Ord a
constraint on the element type a
in case we want to compare them (e.g., if we are using a binary search tree implementation of sets).
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.
hw5
directory.
hw5-tests.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/Database.hs
.Database
already contains data type definitions below for representing the syntax of the embedded language.
[Command]
) such as the following example.
select :: [Command] -> User -> Table -> Column -> Maybe [Integer]
that takes four arguments: a list of commands describing the current state of the database, the user evaluating the query, the table on which the query is being evaluated, and the name of the column the user wants to select. Hint: use list comprehensions with pattern matching.Just
constructor). If the user or table do not exist, or if the specified user does not have permission to query the specified table, the function should return Nothing
.
aggregate :: [Command] -> User -> Table -> Column -> Operator -> Maybe Integer
that takes five arguments: a list of commands describing the current state of the database, the user evaluating the query, the table on which the query is being evaluated, the name of the column to aggregate, and an operator (of type Integer -> Integer -> Integer
) to use when aggregating the values in the specified column. Hint: use foldr
.Just
constructor). If the user or table do not exist, or if the specified user does not have permission to query the specified table, the function should return Nothing
.
validate :: [Command] -> Bool
that checks that every command in the list refers to a table that has already been created and a user that has already been added earlier in the list of commands. If every command is valid, it should return True
; otherwise, it should return False
. Hint: write a helper function and call it on a reversed list of commands, then check each command against the rest of the list.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 built-in 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 built-in 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.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
.
| = |
|
|
| = |
|
| = |
|
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 |
gsubmit
. This section reproduces and extends some of the instructions already made available by the BU Computer Science Department.csa
machines maintained by the CS Dept. You will need to physically visit the undergraduate computing lab located at 730 Commonwealth Avenue, on the third floor in room 302.csa
home directory. If you are using Windows, you will also need an SSH client (such as PuTTY).
local device
|
your csa2 /csa3 home directory |
your gsubmit directory for CS 320 |
csa2
or csa3
using an SCP or SSH client and create a directory for your submission in your CS account home directory. Note that in the examples below %>
represents a terminal prompt, which may look different on your system.
local device
|
your csa2 /csa3 home directory
|
your gsubmit directory for CS 320 |
csa2
or csa3
using an SCP client and copy your completed file(s) into that directory.
local device
|
⇒ |
your csa2 /csa3 home directory
|
your gsubmit directory for CS 320 |
csa2
or csa3
using an SSH client and run the gsubmit
commands to copy the files from your CS account home directory to the gsubmit
directories to which the course staff has access.
local device
|
⇒ |
your csa2 /csa3 home directory
|
⇒ |
your gsubmit directory for CS 320
|
csa2/csa3
..py
. For example, suppose the following is contained within a file called example.py
:
python3
, python3.2
, python3.3
, etc. depending on the Python installation you're using). Note that in the examples below %>
represents a terminal prompt, which may look different on your system.
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 single-character 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]
).example()
is defined as follows:
*
-operator, the scatter operator, or the splat operator) involves providing a list to the function, preceded by the *
symbol; the arguments will be drawn from the elements in the list.
**
-operator) involves providing a dictionary to the function, preceded by the **
symbol; each named paramter in the function definition will be looked up in the dictionary, and the value associated with that dictionary key will be used as the argument passed to that parameter.
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 unbounded-size 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
.