Homework 5: Pic2PS, Part 2

Overview

This week, we will implement a larger subset of the pic language. We will build on last week’s implementation to add arithmetic operations and imperative features such as assignments and loops.

Background: Extending a language

When we extend the implementation for an existing language, we usually perform the following steps:

  1. Design the concrete syntax. Decide which additional features we want programmers to have, and design the syntax for those features.

    In this assignment, the new concrete pic syntax for is provided for you.

  2. Design the abstract syntax. Create and / or extend the data structure (e.g., the Abstract Syntax Tree—AST) that we will use to represent the structure of a program.

    In this assignment, you will design the extensions to the AST.

  3. Extend the parser. Connect the concrete syntax to the abstract syntax, by extending the parser, to accept the new features from the concrete syntax and create the corresponding values in the abstract syntax.

    In this assignment, you will extend an implementation of a parser that uses parser combinators.

  4. Extend the evaluator. Connect the abstract syntax to the semantics of the program, by defining what it means to evaluate each of the new kinds of things in the AST.

    In this assignment, you will extend the evaluator from last week, which takes an AST as input and produces PostScript code (in strings) as output.

You don’t need to do these steps in this order. For example, once you’ve done the first two steps, you can do the last two in either order. (Note, however, that some of the provided evaluator tests depend on a working parser.) You can also extend the language one feature at a time, e.g., add assignments to the AST, then extend the parser and evaluator to support assignments.

Collaboration

If you worked with a partner in Assignment 4, you can work with the same person (as long as you haven’t worked together four times already). As always, you can also work on your own or with someone else.

Materials

Use the assignment workflow and the link provided on Piazza to get access to this week’s files.

A Partial Implementation

In your repository directory, you will find the following files:

  • PicAST.hs defines the abstract syntax for our language. We will modify this file to add more pieces of the abstract syntax.

  • ParserBase.hs and ParserCombinators.hs contain parsing code from this week’s lab, with a few modifications. The ParserCombinators module contains a parsing function rword for parsing reserved words: rword foo will match foo by itself but not match food. These functions do not parse reserved words in pic, but you can use them to write a parser that does. You shouldn’t modify these files, but they contain useful helper functions for writing your parser.

  • PicParser.hs defines the parser for our concrete syntax, using parser combinators. We will modify this file to extend the parser.

  • PicEvaluation.hs defines the evaluator, which turns an AST into lines of PostScript code. We will modify this file to extend the evaluator.

  • test/ contains some test code. Note that ExprEvalSpec.hs and NewElemsSpec.hs won’t compile until after you’ve completed part of the assignment. You can add more tests if you would like.

Building on last week’s code

The remaining files in the repository also contribute to a full solution for Assignment 4. You may use your own code from Assignment 4 (with attribution, if you worked with someone else), or you may use all or part of the provided code, with attribution. If you do not use the provided code, note that there have been changes and additions in PicEvaluation.hs and PicAST.hs (e.g., to add starter code for environments, and for directions with optional expressions).

Style and Elegance (10%)

As with last week, your code should be reasonably well-commented. Ten percent of your grade will be based on clarity (e.g., well-documented with comments, good variable names, and generally easy to understand how your code works) and elegance (e.g., factoring out common code rather than duplicating sections of code).

Your task: Write useful comments and use good names for variables and functions, as you write your code. To make your code elegant, you may need a few iterations of writing—it’s often difficult to write elegant code on the first try. Instead, focus on writing correct, readable code. Then, focus on making it elegant (perhaps by enlisting help from a grutor or professor).

A New Concrete Syntax

A grammar for our larger version of pic appears in Figure 1. The new pic grammar includes floating-point numbers, expressions, assignment to variables, for loops, curly-brace–delimited blocks ({ … }), and optional lengths for direction specifications.

elements: element elements
  ε
   
element: shape attributes ;
  direction ;
  { elements }
  var = exp ;
  for var = exp to exp by exp do { elements }
   
shape: box
  circle
  line
  move
  arrow
   
attributes: string attributes
  direction optexp attributes
  ε
   
direction: left
  right
  up
  down
   
optexp: exp
  ε
   
exp: number
  var
  ( exp )
  exp + exp
  exp - exp
  exp * exp
  exp / exp
Figure 1: Grammar for concrete pic syntax.

Extend the Abstract Syntax (5%)

The abstract syntax in PicAST.hs has been updated from the previous assignment, to add an Expr type and optional expressions to directions, as well as elements enclosed in curly braces. What’s missing is the representation for assignment statements and for loops.

Your task: Extend the abstract syntax, to represent assignment and for loops. Remember, abstract syntax (a) should contain only the minimal information required to reconstruct the input, and (b) should not let us represent things that are not in the concrete syntax (for example, there should not be a way for us to represent the non-expression for circle; to 6 by 2 do { arrow; }).

Extend the Parser (40%)

Your task: Extend the PicParser module to correctly handle the concrete syntax for pic (shown in Figure 1) and to generate the appropriate abstract syntax.

The auto-generated documentation for our parser-combinator library may be helpful: https://www.cs.hmc.edu/cs131/pc-doc/ParserCombinators.html Look here for useful parsers and combinators that you can build on.

Important Notes

The grammar is vague or ambiguous in several details:

  • It does not say what a valid var is. The pic language specification only says “variable names begin with a lower case letter”, but nothing else. So, it seems reasonable to fill in the rest by drawing on the conventions of languages like Python, Java or C++. In particular, you must assume that reserved words (e.g., do, move, box) are not allowed as variable names. The provided ident parser can help, but is not sufficient by itself.

  • The grammar doesn’t explicitly show operator precedence, but the usual rules apply (e.g., multiplication groups more tightly than addition, and both are left-associative). You can look at SimpleExpr.hs from the lab to see how one can handle arithmetic expressions. You can even take code wholesale from that file, so long as you include proper attribution.

  • The grammar doesn’t say what a number is, but the intent is that any reasonable floating point number is valid, including numbers like 42, 2.71828, 5.3e-29, 6e29, 1.234e+56. The provided double parser suffices.

Testing

  • The files test4.pic and test5.pic may be helpful as specific examples of programs in the new grammar.
  • It’s helpful to test as you go: Start with the simplest part of the grammar, implement the parser for it, and test that piece before moving on to something more complex.
  • When you’ve finished, all the tests in test/ParserSpec.hs should pass.
  • You can, of course, write your own tests!

Add Environments to the Evaluator (10%)

New code near the top of PicEvaluation.hs defines a type Env for environments using Haskell’s Data.Map (mapping variable names to real numbers), plus functions and helpful definitions such as picLookup and initialEnv.

Your task: Get the evaluator ready to use environments. As part of this work, we will prepare the translator to follow the official pic implementation by using pic variables boxwid and boxht when drawing boxes (and similarly for other shapes), instead of using fixed constants in the Haskell code.

We can accomplish this task in three main steps:

  1. Modify the State type so that it includes an environment.

    Update the rest of the file so that the code once again compiles and runs. Because element functions return the State, every element function must return an environment (the given environment, updated with any assignments that occurred). None of the shape elements inherited from Assignment 4 change the values of variables, so these cases can all just return the given environment unchanged.

  2. Remove all uses of the fixed constants boxwid through arrowht, replacing them with run-time lookups in the environment of the current state.

  3. Delete the Haskell definitions of constants boxwid through arrowht and make sure your code still compiles.

If you do these these steps, your code compiles, the program outputs the same results, and all the tests compile—you’re done with this part!

Add Expressions to the Evaluator (15%)

Your task: Extend the evaluator to support expression evaluation.

  1. Finish the given eval function, so that it correctly evaluates expressions. Use the given environment to find values of the variables.

  2. Extend the evaluator to handle direction attributes that specify lengths. Recall that if we say arrow right (x+1), we expect a right-pointing arrow that is x+1 inches long instead of (not “in addition to”!) the default linewid inches long.

Testing

  • When you have finished, all the tests in test/ExprEvalSpec.hs should pass.
  • You can, of course, write your own tests!

Add Assignment, Blocks, & for Loops to the Evaluator (20%)

Your task: Extend the evaluator to support imperative statements: assignments, curly-brace–delimited sequences, and for loops. There are more details below about implementing these features.

Assignment

An assignment should not cause doElem to change the position or direction, nor should it generate PostScript commands. It should cause doElem to return an updated environment in which the specified variable has a new value. Verify that, for example, using assignment to change the value of the variable circlerad in a test file causes the sizes of your circles to change.

Blocks

In pic, a sequence of elements surrounded by curly braces generates code as usual, but after the block is finished the current position and direction are restored to the values they had when the sequence was started.

This behavior can be implemented easily by having doElem for blocks return the position and direction it was given originally rather than any values computed during the translation of this block.

Warning: The environment is not restored afterwards; curly braces do not undo assignments to variables.

Loops

The statement for v = exp1 to exp2 by exp3 do { ...elements... } sets v to exp1, and then, while the value of v is less than or equal to that of exp2, repeatedly: draws the given elements and increments v by the value of exp3.

The position, direction, and environment computed at the end of each iteration is used for the beginning of the next iteration. The returned PostScript will be the concatenation of the code created by all the iterations of the loop.

Warning: Although the body of a for loop is syntactically required to be bounded by curly braces, this concrete syntax is misleading: the position and direction are not automatically reset once the loop body ends. If you really do want the position and direction to be reset after every iteration, the loop body must be inside yet another pair of curly braces. The provided tests try to distinguish these two cases (a regular for loop and a for loop whose body is a block).

Testing

When you’ve finished, all the tests in test/NewElemsSpec.hs should pass.

Where to go from here

If you are interested in extending pic even more, some ideas are below. If you implement these ideas, do not to submit them to Gradescope (otherwise the autograder will be confused). You can instead work on a copy of your code or on a separate branch that you don’t submit to Gradescope.

More pic features

The pic user manual describes:

  • An if statement (see page 16)

  • Relational operators for numeric expressions (see page 16)

  • A small collection of standard functions (see page 11)

Extend the concrete and abstract syntax to support these features, and extend your support for statements and expression evaluation to correctly interpret them.