Programming Languages Homework #2

ECS 140A Programming Languages

Homework #2

This assignment asks you to complete programming tasks using the Go programming
language. This assignment should be worked on individually. Please turn in your solutions
electronically via Kodethon by the due date.
Getting Started
First, download the project ?les from Kodethon. Please see this support page1
for details on
downloading the required project ?les, as well as how to submit your solutions via Kodethon.
Next, go to ?Switch Environments? from your Kodethon dashboard and choose the ?go?
execution environment. Finally, you will need to open the Kodethon Terminal to execute
commands. This can be done by selecting the grid icon in the top bar, selecting ?CDE Shell?,
and then clicking the ?Terminal? button in the upper-right. (NOTE: The CDE Shell behaves
very di?erently from the Terminal. Make sure you're using the Terminal!) Further questions
regarding Kodethon can be directed to the course Piazza forum using the kodethon tag.
The project code includes a simple ?Hello, World!? program written in Go. Before
changing anything, make sure you understand how to build and run this program. You can
?nd the source code for this program in the ?hello/? folder. The ?rst thing you should do is
set the GOPATH2
environment variable so that the Go compiler knows how to traverse your
project. You can do this by using cd in your terminal to navigate down to the homework
directory, then running export GOPATH=$(pwd).
You should work through the ?rst four modules in A Tour of Go3
to familiarize yourself
with the language.
For the ?rst three parts of this project, you will be working with a simple arithmetic
language. This language comes with a parser, turning strings like 1 + x / 3 into abstract
syntax trees (ASTs), and an evaluator, turning ASTs into numbers. You will be analyzing and
transforming these ASTs to make the arithmetic language more useful; part 3 in particular
adds basic support for units of measurement.
For the fourth through sixth parts of this project, you will be working with the AST
of the Go language itself. You may need to traverse these ASTs di?erently; make sure to
familiarize yourself with the documentation for go/ast4
in particular, as well as go/token5
,
1https://support.kodethon.com/d/38-how-to-use-a-course-as-a-student
2https://golang.org/doc/code.html#GOPATH
3https://tour.golang.org/list
4https://golang.org/pkg/go/ast/
5https://golang.org/pkg/go/token/
1
go/format6
, and go/parser7
. This article8 gives a gentle introduction to using these packages.
For several parts of this project, you will need to write tests and ensure 100% test coverage
of your code. You can generate a coverage pro?le using the go test command. For example, to generate a coverage pro?le for the Simplify method in the eval/ package, run go
test eval -run Simplify -coverprofile=Simplify.cov. You can then run
go tool cover -func=Simplify.cov | grep simplify.go to see what the coverage results are. You can graphically see which lines of your code are covered by testing using the go tool cover -html=Simplify.cov command, which opens a new browser
window with the results. (On Kodethon, you may need to download the HTML ?le for local
viewing. Add the ?ag -o Simplify.html to generate an HTML ?le, which you can then
download from Kodethon.) See this post9
for more on coverage testing.
1 Depth (15 points)
For this part, you must implement a Depth method on expr ASTs, as declared in eval/ast.go.
The Depth method should return the maximum number of AST nodes between the root of
the tree and any leaf (literal or variable) in the tree.
Fill in the empty method bodies in eval/depth.go with your implementation. Make
sure it passes the sample tests provided in eval/depth_tests.go.
2 Simplify (15 points)
Sometimes we have an expression where we have values for some of its variables, but not
all of them. Or perhaps there are some obvious evaluations we can do without involving
variables, as in ?x + 5 + 8?, which can be simpli?ed to ?x + 13?. Your task is to write a
Simplify method that ?lls in whichever variables we know and simpli?es the expression.
As another example, ?x + 2 + y? with Env{’x’: 3} will be simpli?ed to ?3 + 2
+ y?. Because of how the provided parser works, the input is interpreted as +(x, +(2,
y)), and this can't be simpli?ed without reassociating the addition operation. Don't worry
about reassociating or rotating the AST ? just make sure the subtrees that you can simplify
directly are simpli?ed.
Your code should perform the following simpli?cations:
• Any Var whose name is in the provided map should be replaced with its value.
• Any unary operator whose operand is a Literal should be replaced with a Literal
representing the result.
• Any binary operator whose operands are both Literals should be replaced with a
Literal representing the result.
6https://golang.org/pkg/go/format/
7https://golang.org/pkg/go/parser/
8https://zupzup.org/go-ast-traversal/
9https://blog.golang.org/cover
2
• Any binary operator performing addition, where one operand is 0, should be reduced.
(0 + X = X = X + 0)
• Any binary operator performing multiplication, where one operand is 1 or 0, should
be reduced. (1 ∗ X = X = X ∗ 1 and 0 ∗ X = 0 = X ∗ 0)
No other simpli?cations should be performed.
Write your Simplify method in eval/simplify.go, and write tests for your code
in eval/simplify_test.go. Ensure that your tests provide 100% coverage of code in
eval/simplify.go.
3 FlattenUnits (20 points)
The supplied Eval cannot compute expressions involving units (measure nodes in the
AST), so your next job is to implement a FlattenUnits method that replaces measure
operations with arithmetic operations. The resulting AST must contain no measure operations. The second result of FlattenUnits must be the unit of the overall expression.
You should support the following basic kinds of quantities, in addition to scalars (unitless
numbers):
• Length: Meter (?m?), kilometer (?km?), mile (?mi?), where 1 km = 1000 m and 1 mi =
1609.344 m;
• Time: Second (?s?), milisecond (?ms?), minute (?min?), where 1 ms = 0.001 s and 1
min = 60 s;
• Mass: Kilogram (?kg?), gram (?g?), pound (?lbs?), where 1 g = 0.001 kg and 1 lbs =
45359237 kg;
• Temperature: Fahrenheit (?F?), Celsius (?C?), Kelvin (?K?), where [C] = [K] − 273.15
and [K] = ([F] + 459.67)5/9
10;
• Volume: liters (?ltr?), gallons (?gal?), where 1 gal = 3.78541 ltr.
Apart from the above basic kinds of quantities, you need to support the following two
derived quantities:
• Speed: Each of the three length units can be combined with any of the three time
units to de?ne a speed unit; for example, meters per sec (?m_p_s?), miles per minute
(?mi_p_min?). There are 9 di?erent speed units.
• Fuel Consumption: Each of the three length units can be combined with any of the
two volume units to de?ne a fuel consumption unit; for example, kilometers per liter
(?km_p_ltr?), miles per gallon (?mi_p_gal?). There are 6 di?erent fuel consumption
units.
10https://en.wikipedia.org/wiki/Conversion_of_units_of_temperature
3
For binary operations, if the left-hand quantity is not a scalar, its unit determines the
unit of the result. For example, ?s(4) + min(5)? should produce an AST without units that,
when evaluated, produces the value ?304? (the number of seconds in 5 minutes, 4 seconds),
and the second return value of FlattenUnits should be "s" (for ?seconds?). On the
other hand, addition and subtraction of incompatible units (e.g. ?s(4) + F(10)?) is illegal,
and should cause a panic11
.
Your code does not need to handle multiplication of quantities with units. If you encounter an input like ?m(5) * s(1)?, you should call the standard function panic() to throw
an exception and fail early. However, your code should still allow multiplication by scalars.
Your code does not need to handle division of quantities with units, except for cases
that construct speed from length and time units, and fuel consumption units from length and
volume units. If you encounter an input like ?m(5) / s(1)?, the result of FlattenUnits
should be (?5?, ?m_p_s?). On the other hand, if you encounter an input such as ?m_p_s(5)
/ s(1)?, you should call the standard function panic() to throw an exception and fail early.
However, your code should still allow division by scalars.
The eval/flatten.go ?le contains a solution for handling length, time, mass, and
temperature units. However, it does not handle volume, speed, and fuel consumption units.
Furthermore, it does not handle division between length and time units to give speed units,
and division between length and voume units to give fuel-consumption units; instead it
calls panic. You can extend the given implementation or write your own from scratch.
Write your FlattenUnits method in eval/flatten.go, and write tests for your code
in eval/flatten_test.go. Ensure that your tests provide 100% coverage of code in
eval/flatten.go.
(We call this ?FlattenUnits? because all of the units in the expression are ??attened?
together, with the only unit left as the second result of the FlattenUnits call.)
4 ComputeBranchFactor (15 points)
For the next three parts, we'll be working with the AST of the Go language itself. As a
warm up, write a ComputeBranchFactor function that takes a Go program as a string,
and for each function in that program, counts the number of branching statements in the
function. ComputeBranchFactor should return a map[string]uint from the name
of the function to the number of branching statements it contains.
?Branching statements? are those where the program has a choice of what to execute next.
These include if and for, as well as some other statements you may not have encountered
before. Statements are named ending in ?Stmt? in the go/ast documentation.
Write your ComputeBranchFactor function in analysis/branches.go, and write
tests for your code in analysis/branches_test.go. Ensure that your tests provide
100% coverage of code in analysis/branches.go.
11https://golang.org/pkg/builtin/#panic
4
5 SimplifyParseAndEval (15 points)
The eval package from the ?rst three tasks includes a ParseAndEval method that can
be used in regular Go code. For this task, you will write a source preprocessor that simpli?es
ParseAndEval calls before the program is run. For instance, a call like eval.ParseAndEval(“2
+ 3”, env) should be rewritten to eval.ParseAndEval(“5”, env).
Write your SimplifyParseAndEval function in analysis/rewrite.go. Make
sure it passes the sample tests provided in analysis/rewrite_tests.go.
The ability to manipulate the AST of a program enables you to do code generation12
.
For instance, the genny13 library allows you to write a data structure once for a ?generic?
element type, and generate instances of that data structure for any other element type.
6 CyclomaticComplexity (20 points)
Cyclomatic complexity14 is a measure of how many distinct basic control ?ow paths there are
within a function, and it is sometimes used as a heuristic for how maintainable a function is.
For this task, you will compute the cyclomatic complexity for each function in a Go program
and output a map[string]uint from the function's name to its cyclomatic complexity.
You probably shouldn't use the ast.Walk method in go/ast for this. ast.Walk does
not give you much control over the order in which AST nodes are visited.
Write your CyclomaticComplexity function in analysis/cyclo.go. Make sure
it passes the sample tests provided in analysis/cyclo_tests.go.
12https://en.wikipedia.org/wiki/Automatic_programming
13https://github.com/cheekybits/genny
14https://en.wikipedia.org/wiki/Cyclomatic_complexity
5