Homework #2 Solution

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 page 1 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 dierently 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 Go 3 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 dierently; make sure to familiarize yourself with the documentation for go/ast 4 in particular, as well as go/token 5,







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 prole using the go test command. For exam-ple, to generate a coverage prole 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 cov-erage results are. You can graphically see which lines of your code are covered by testing us-ing 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 post 9 for more on coverage testing.







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.







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 simplied to x + 13. Your task is to write a




Simplify method that lls in whichever variables we know and simplies the expression. As another example, x + 2 + y with Env{’x’: 3} will be simplied to 3 + 2 + y. Because of how the provided parser works, the input is interpreted as +(x, +(2, y)), and this can't be simplied 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 simplied.

Your code should perform the following simplications:




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 simplications 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.







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 oper-ations. 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=910;




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 dene a speed unit; for example, meters per sec (m_p_s), miles per minute (mi_p_min). There are 9 dierent speed units.




Fuel Consumption: Each of the three length units can be combined with any of the two volume units to dene a fuel consumption unit; for example, kilometers per liter (km_p_ltr), miles per gallon (mi_p_gal). There are 6 dierent 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 en-counter 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.)







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
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 simplies 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 generation 12. 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.







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