Problem Set 3: Memely

To get started,

1. Ask Didit to create a remote psets/ps3 repository for you on github.mit.edu.

2. Clone the repo. Find the git clone command at the top of your Didit assignment page, copy it entirely, paste it into your terminal, and run it.

3. Import into Eclipse. See Problem Set 0 for if you need a refresher on how to create, clone, or import your repository.

Image memes are fun. But they would be even more fun if we could program them. In this problem set, we’ll implement a language that generates image memes.

The meaning of an expression in this language is a generated image, a 2D array of pixels with a specific width and height. All widths and heights in the language are positive integers.

The two primitives of the language are images, represented by filenames:

myroom.jpg

and captions, represented as quoted strings:

"This is my room"

An image filename loads an image from the specified file. Even though operating systems allow a variety of characters in a filename, in this language a filename may consist of letters, digits, periods, or forward slashes /, and may also contain hyphens - and underscores _ as long as they are not the first character in the filename. The image file format may be any format that the Java Image I/O package is capable of reading. If the image in the file has zero width or zero height (which is actually forbidden by most image formats), then behavior is undefined.

A caption produces an image showing the given text as a single line with no word-wrapping. A caption may contain any characters except newlines and double-quotes (though how the font actually displays unusual characters, like emojis, is unspecified). The font, color, and size of the text is unspecified, but must be reasonably readable. (If you choose to use a font other than the default font, make sure all the public tests render correctly on Didit.) The width and height must be positive and big enough to not crop any of the text. Extra margin or padding is permitted but unspecified. The background of a caption should be transparent, so that it can be placed on top of other images if the user so desires.

Two expressions can be glued together side-by-side, e.g.:

A.jpg | B.jpg | C.jpg

produces a horizontal three-panel cartoon strip.

Expressions can be glued together top-to-bottom, e.g.:

1.jpg --- 2.jpg --- 3.jpg

produces a vertical three-panel strip.

Space, tab, carriage return, and newline characters around symbols are irrelevant and ignored, and any string of at least 3 - characters can be used to mean a single --- operator, so this can also be written:

1.jpg
--------
2.jpg
------
3.jpg

Side-by-side gluing has higher precedence than top-to-bottom gluing so:

A1.jpg  |  B1.jpg  |  C1.jpg
-----------------------------
A2.jpg  |  B2.jpg  |  C2.jpg

produces a 6-panel cartoon laid out in 2 rows of 3 images each. Parentheses can be used to group expressions and override precedence, so if the six image files are all the same size, here is another way to write the same layout:

(A1.jpg --- A2.jpg) | (B1.jpg --- B2.jpg) | (C1.jpg --- C2.jpg)

When images of different sizes are glued together side-by-side, the shorter image is centered vertically relative to the taller image, and the resulting combination has the height of the taller image. Similarly, when different-sized images are glued top-to-bottom, the narrower image is centered horizontally relative to the wider image. In both cases, if centering the smaller image requires placing it at a fractional pixel position, then it may be placed instead at an integer position within ±1 pixel. The “empty space” around the smaller image should be transparent.

The language has two more combiner operators that overlay an image onto another image. The caret ^ places its second argument over the top part of its first argument so that the tops of both images are aligned, as in:

img/boromir.jpg ^ "One does not simply"

Similarly, the underscore _ places its second argument over the bottom part of its first argument so that the bottoms are aligned:

img/boromir.jpg _ "walk into Mordor"

The arguments of ^ and _ can be any expression, not just a caption, though these are most often used with captions. For both operators, if the two images have different widths, then the narrower image is centered horizontally relative to the wider image. The resulting image’s width is the maximum of the two image widths, and likewise for height.

Finally, any expression can be explicitly resized using the @ operator:

img/red.jpg @ 300x200

which rescales the image (i.e. stretches or shrinks it) so that its width is 300 pixels and height is 200 pixels. Width and height must be either positive integers, or ?, which means that the corresponding dimension should be a legal width or height that preserves the aspect ratio of the image as closely as possible. For example:

img/boromir.jpg @ 100x?

This expression resizes img/boromir.jpg from its original 550x325 dimensions to 100x59, because the resulting aspect ratio 100/59 ≅ 1.6949 is as close as possible to the original aspect ratio 550/325 ≅ 1.6923. If both width and height are ?, the expression is invalid and should produce a syntax error. The aspect-ratio-preserving ? is particularly useful for captions, for example:

img/boromir.jpg ^ ( "One does not simply" @ 550x? )

This expression resizes the caption to fill the width of boromir.jpg without making the text look stretched or squashed.

The precedence of the operators goes in the order: @ ^ _ | ---. The resize @ operator has highest precedence, applied first. The top-overlay operator ^ has next highest precedence, followed by the bottom-overlay operator _, so that A ^ B _ C means (A ^ B) _ C. Then the side-by-side glue operator | is applied, and finally the top-to-bottom glue operator ---- has lowest precedence. Precedence can be overridden by parentheses.

Note that the characters _ and - can also appear inside filenames. In order to use operators like _ and --- immediately after a filename, the operator must be separated from the filename either by a parenthesis, as in (cat.jpg)_"meow", or by whitespace, as in cat.jpg _ "meow". Without that separation, the _ and - characters are considered part of the filename.

The system has a console user interface where users may input expressions and see their results. When the user enters an expression on the console, that expression becomes the current expression and is echoed back to the user, possibly with reformatting (user input in green):

> img/boromir.jpg ^ "One does not simply" _ "walk into Mordor"
(img/boromir.jpg ^ "One does not simply") _ "walk into Mordor"

> img/tech1.png ---------- img/tech2.png ---------- img/tech3.png
img/tech1.png --- (img/tech2.png --- img/tech3.png)

A command starts with !. The command operates on the current expression, and may also update the current expression. Valid commands:

!size
prints the final size of current expression in the form WxH. This command does not update the current expression.

!hflip
flips the current expression horizontally, so that a left-to-right comic strip now reads in right-to-left order (or vice versa).

!vflip
flips the current expression vertically, so that a top-to-bottom comic strip now reads in bottom-to-top order (or vice versa).

!image
generates the image represented by the current expression and displays it in a window. This command does not update the current expression, and this command can be run on any valid current expression, including the results of !hflip or !vflip.

!quit
exits the program.

Entering an invalid expression prints an error but does not update the current expression. The error should include a human-readable message but is not otherwise specified.

More examples:

> img/tech2.png | img/tech1.png
img/tech2.png|img/tech1.png

> img/tech3.png -|-|- img/tech4.png
unknown expression

> !hflip
img/tech1.png|img/tech2.png

> !size
400x150

> !image

The console UI makes use of four provided method specifications in the code for this problem set:

• Expression.parse()
• Commands.size()
• Commands.flip()
• Commands.image()

These methods are used by Main to provide the user interface described above.

Problem 1: we will create the Expression data type to represent expressions in the program.

Problem 2: we will create the parser that turns a string into an Expression, and implement Expression.parse().

Problems 3-5: we will add new Expression operations for computing the size of an expression, laying out an expression and generating an image from an expression, and implement the corresponding commands Commands.size(), Commands.flip() and Commands.image().

The starting code includes a file Examples.java, with example code showing how to use the Java library to:

• read an image file into memory
• create new images in memory for drawing on
• draw text into an image
• draw an image with a particular position and size
• examine the pixels of an image for unit testing

This is staff-provided code, which means you are free to draw from it without attribution.

Define an immutable, recursive abstract data type to represent expressions as abstract syntax trees.

Your AST should be defined in the provided Expression interface (in Expression.java) and implemented by several concrete variants, one for each kind of expression. Each variant should be defined in its own appropriately-named .java file. You should have separate variant classes for each operator in the language.

Concrete syntax in the input, such as parentheses and whitespace, should not be represented at all in your AST.

It should be legal to create and use an abstract syntax tree containing filenames that do not currently exist in the filesystem. Only operations that actually require the image data (size and image) should try to read the files. Others (like toString, flip, or equals) should not.

For creating your AST type, you may find these examples useful:

• the reading on recursive data types
• the example code for IntegerExpression from class

1.1 Expression

To repeat, your data type must be immutable and recursive. Follow the recipe for creating an ADT:

• Spec. Choose and specify operations. For this part of the problem set, the only operations Expression needs are creators and producers for building up an expression, plus the standard observers toString(), equals(), and hashCode(). We are strengthening the specs for these standard methods; see below.

• Test. Partition and test your operations in ExpressionTest.java, including tests for toString(), equals(), and hashCode(). Note that we will not run your tests on any implementations other than yours.

• Code. Write the rep for your Expression as a data type definition in a comment inside Expression. Implement the variant classes of your data type.

  The variant classes are considered part of the Expression type’s rep, so a single good test suite for Expression covers the variants.

Remember to include a Javadoc comment above every class and every method you write; define abstraction functions and rep invariants, and write checkRep(); and document safety from rep exposure.

1.2 toString()

Define the toString() operation on Expression so it can output itself as a string. This string must be a valid expression as defined above. You have the freedom to decide how to format the output with whitespace and parentheses for readability, but the expression must have the same meaning as an image.

Your toString() implementation must be recursive, and must not use instanceof.

Use the @Override annotation to ensure you are overriding the toString() inherited from Object.

Remember that your tests must obey the spec. If your toString() tests expect a certain formatting of whitespace and parentheses, you must specify this formatting in your spec.

1.3 equals() and hashCode()

Define the equals() and hashCode() operations on your AST to implement structural equality.

Structural equality defines two expressions to be equal if:

1. the expressions contain the same filenames, captions, dimensions (numbers and ?), and operators;
2. those filenames, captions, dimensions, and operators are in the same order, read left-to-right;
3. and they are grouped in the same way.

For example, the AST for a.jpg ^ "title" is not equal to the AST for "title" ^ a.jpg, but it is equal to the ASTs for a.jpg^"title", (a.jpg ^ "title"), and (a.jpg) ^ ("title"). The AST for (A | B) --- (C | D) is not equal to the AST for (A --- C) | (B --- D) even though they both may generate the same 2×2-panel meme.

For n-ary groupings where n is greater than 2:

• Such expressions must be equal to themselves. For example, the ASTs for A | B | C and (A | B | C) must be equal.
• However, whether they are equal or not to different groupings with the same image meaning is not specified, and you should choose an appropriate specification and implementation for your AST. For example, you must determine whether the ASTs for (A | B) | C and A | (B | C) are equal.

Remember: concrete syntax, including parentheses, should not be represented in your AST. Grouping, for example, should be reflected in the AST’s structure.

Be sure that AST instances which are considered equal according to this definition and according to equals() also satisfy observational equality.

Your equals() and hashCode() implementations must be recursive. Only equals() can use instanceof, and hashCode() must not.

Remember to use the @Override annotation.

Commit to Git. Once you’re happy with your solution to this problem for the minimal language, commit, push, and continue on.

Iterate. After completing the problem set with just those features, come back and update your work, starting with the Expression specs.

Now we will create the parser that takes a string and produces an Expression value from it. The entry point for your parser should be Expression.parse().

Examples of valid inputs:

A.jpg | B.jpg --- C.jpg | D.jpg
A.jpg --- B.jpg --- C.jpg
((A _ B)^C)---D
base.jpg _ ("all your base"---"are belong to us")
A@1x2@?x3@4x?

Examples of invalid inputs:

A - B - C	the --- operator must have at least three dashes
A --- --- B	no spaces within the --- operator
|A|B|	the | operator must be binary
"no	unterminated caption
A.jpg_"B"	filenames can have dashes and underscores, so A.jpg_ is parsed as a filename
A.jpg@?x?"	resize operator must specify at least one dimension

Examples of optional inputs (extensions to the language that you may want to design and support):

'caption'	single-quoted captions
"One does not simply"{Helvetica 96pt black}	font face, size, color of text
ghost.jpg * 50%	make image translucent

You may consider the optional inputs invalid, or you may choose to support additional features (like new operators) in the input. However, your system may not produce an output with a new feature unless that feature appeared in its input. This way, a client who knows about your extensions can trigger them, but clients who don’t know won’t encounter them unexpectedly.

2.1 Write a grammar

Write a ParserLib grammar for expressions as described in the overview. A starting ParserLib grammar file can be found in src/memely/Expression.g. This starting grammar recognizes filenames, side-by-side gluing, and @-resizing with numbers (not ?).

For more information on ParserLib, see:

• the reading on parsers
• example code for compiling the parser and processing a parse tree
• Javadoc documentation for ParserLib

2.2 Implement Expression.parse()

Implement Expression.parse() by following the recipe:

• Spec. The spec for this method is given, but you may strengthen it if you want to make it easier to test. Remember that it should be legal to parse an expression containing filenames that do not currently exist in the filesystem, since parsing does not depend on image data from the files.

• Test. Write tests for Expression.parse() and put them in ExpressionTest.java. Note that we will not run your tests on any implementations other than yours.

  Now that you are implementing Expression.parse(), it’s a good idea to review the spec for Expression.toString(), which specifies a testable relationship between parse(), equals(), and toString().

• Code. Implement Expression.parse() so that it calls the parser generated by your ParserLib grammar. The reading on parsers discusses how to call the parser and construct an abstract syntax tree from it, including code examples. The starting code for this problem set includes a skeletal ExpressionParser.java that you can work from.

2.3 Run the console interface

Now that Expression values can be both parsed from strings with parse(), and converted back to strings with toString(), you can try entering expressions into the console interface.

Run Main. In Eclipse, the Console view will allow you to type expressions and see the result. Try some of the expressions from the top of this handout.

Commit to Git. Once you’re happy with your solution to this problem (first for the minimal language, later for the full language), commit and push!

The !size command takes an expression and prints the width and height of the image it would generate in the form WxH. It should follow the size calculation rules described in the overview.

For example, the following are correct size results. (Hover or tap on an input expression to see the sizes of its image files.)

For getting sizes of image files and text captions, you may find the following useful:

• Examples.java, which you can find in the starting code for the problem set
• ImageIO.read() and Font.getStringBounds() from the Java API

3.1. Add an operation to Expression

You should implement size as a method on your Expression datatype, defined recursively. The signature and specification of the method are up to you to design, but it would be wise for your size operation to return a more useful data type than String – such as Dimension, or even better, a similar but immutable type of your own devising.

Follow the recipe:

• Spec. Define your operation in Expression and write a spec.
• Test. Put your tests in ExpressionTest.java. Note that we will not run your tests on any implementations other than yours.
• Code. The implementation must be recursive. It must not use instanceof, nor any equivalent operation you have defined that checks the type of a variant.

For any part of the problem set, if your tests use additional images, add them to the img directory. Do not commit large image files to Git! Keep images small to ensure that Didit can clone and build your repo.

3.2 Implement Commands.size()

In order to connect your size operation to the user interface, and also to the Didit autograder, you need to implement the Commands.size() method.

Keep Commands.size() extremely simple. It should be no more than glue code, calling your size operation and converting the result to a string. If that is the case, then you don’t need to write a separate test suite for it. Your existing tests for your size operation should suffice.

Specifically, the body of Commands.size() should be at most 3 lines long, consisting of at most a couple simple method calls, possibly using local variables, plus a return statement. All of the methods that it calls should be already well-tested, either by your Expression test suite or by Java itself. If this is the case, then you don’t need separate tests for this method.

If your Commands.size() method is more complex than that — for example, with control flow statements like if or while, or arithmetic operations like + or < or Math.max, or recursive calls to itself — then you will need to design a test suite for it, in a file called CommandsTest.java. But you should first discuss your design with an LA or TA, because this is a sign that the size operation you designed for your Expression type is not powerful enough.

• Spec. The spec for this operation is given, but you may strengthen it if you want.
• Test. Keep this operation extremely simple so you don’t have to test it separately.
• Code. Implement size() as simply as possible.

3.3 Run the console interface

We’ve now implemented the !size command in the console interface. Run Main and try some sizes in the Console view.

Commit to Git. Once you’re happy with your solution to this problem (first for the minimal language, later for the full language), commit and push!

The flip operation takes an expression and flips it either horizontally or vertically.

Horizontal flipping can transform a comic strip from left-to-right reading order, the convention for English-language comics, into a right-to-left order like Japanese manga, or vice versa. Vertical flipping similarly transforms top-to-bottom reading order into bottom-to-top order.

Flipping affects the glue operators (side-by-side and top-to-bottom) and the overlay operators (overlay bottom and overlay top). Flipping does not transform individual image files or individual captions. As a result, flipping is not (in general) the same as generating the image and then flipping it in an image-processing program. From a comic strip perspective, flipping can rearrange comic strip panels and move captions, but it doesn’t invert the images in the panels or the text of the captions themselves.

For example, the following are correct flip results:

flip horizontally: img/tech3.png | img/tech4.png
→ img/tech4.png | img/tech3.png

flip horizontally: img/tech1.png | img/tech2.png --- img/tech3.png | img/tech4.png
→ img/tech2.png | img/tech1.png --- img/tech4.png | img/tech3.png

flip vertically: img/tech3.png ^ "TECH SUPPORT" --- img/tech4.png --- img/tech5.png
→ img/tech5.png --- img/tech4.png --- img/tech3.png _ "TECH SUPPORT"

Incorrect flips:

flip horizontally: img/boromir.jpg ^ "ONE DOES NOT SIMPLY" _ "WALK INTO MORDOR"
  incorrect: img/boromir.jpg ^ "YLPMIS TON SEOD ENO" _ "RODROM OTNI KLAW"
  captions and image files do not flip

4.1. Add an operation to Expression

You should implement flip as a method on your Expression datatype, defined recursively. The signature and specification of the method are up to you to design, but it would be wise for your flip operation to return Expression rather than String. Follow the recipe:

• Spec. Define your operation in Expression and write a spec.
• Test. Put your tests in ExpressionTest.java. Note that we will not run your tests on any implementations other than yours.
• Code. The implementation must be recursive. It must not use instanceof, nor any equivalent operation you have defined that checks the type of a variant.

You may find it useful to add more operations to Expression to help you implement the flip operation. Spec/test/code these additional operations using the same recipe, and make them recursive as well where appropriate. Your helper operations should not simply be a variation on using instanceof to test for a variant class.

4.2 Implement Commands.flip()

In order to connect your flip operation to the user interface, we need to implement the Commands.flip() method.

Like Commands.size(), as discussed above, this method should be simple glue code that calls the flip operation of your Expression data type. The body of Commands.flip() should be at most 3 lines long, consisting of at most a couple calls to already well-tested methods, possibly using local variables, plus a return statement. If this is the case, then you don’t need separate tests for this method.

• Spec. The spec for this operation is given, but you may strengthen it if you want.
• Test. Keep this operation extremely simple so you don’t have to test it separately.
• Code. Implement flip() as simply as possible.

4.3 Run the console interface

We’ve now implemented the !hflip and !vflip commands in the console interface. Run Main and try some flips in the Console view.

Commit to Git. Once you’re happy with your solution to this problem (first for the minimal language, later for the full language), commit and push!

The image operation takes an expression and generates an image from it. You may strengthen this spec if you wish.

For example, the following are representative outputs for generated images. Their sizes have been changed for inclusion in this handout: the dimensions of the images shown here do not satisfy the spec.

img/tech1.png|img/tech2.png
→

img/boromir.jpg ^ "ONE DOES NOT SIMPLY"@550x? _ "WALK INTO MORDOR"@550x?
→

img/black.png@600x50 ^ "TECH SUPPORT"@?x50 ---------------------------------- img/tech1.png | img/tech2.png@200x150 | img/tech3.png ---------------------------------- (  img/black.png@200x25 ^ "What my friends think I do"@?x15  | img/black.png@200x25 ^ "What my mom thinks I do"@?x15  | img/black.png@200x25 ^ "What society thinks I do"@?x15   ) ---------------------------------- img/black.png@600x25 ---------------------------------- img/tech4.png | img/tech5.png@200x160 | img/tech6.png ---------------------------------- (  img/black.png@200x25 ^ "What my boss thinks I do"@?x15   | img/black.png@200x25 ^ "What I think I do"@?x15  | img/black.png@200x25 ^ "What I actually do"@?x15       ) ---------------------------------- img/black.png@600x25

→

For generating images, you may find the following useful:

• Examples.java, which you can find in the starting code for the problem set
• BufferedImage.getGraphics(), Graphics.drawImage(), Graphics.drawString()

5.1 Add an operation to Expression

You should implement generation as a method on your Expression datatype, defined recursively. The signature and specification of the method are up to you to design. Follow the recipe:

• Spec. Define your operation in Expression and write a spec.
• Test. Put your tests in ExpressionTest.java. Note that we will not run your tests on any implementations other than yours.
• Code. The implementation must be recursive (perhaps by calling recursive helper methods). It must not use instanceof, nor any equivalent operation you have defined that checks the type of a variant class.

You may find it useful to add more operations to Expression to help you implement the image operation. Spec/test/code them using the same recipe, and make them recursive as well where appropriate. Your helper operations should not simply be a variation on using instanceof to test for a variant class.

Since your image operation produces an image, your tests may need to inspect properties of that image, like its width, height, and possibly some values of its pixels. Examples.java included in the starting code has examples of doing this inspection.

5.2 Commands.image()

In order to connect your image operation to the user interface, we need to implement the Commands.image() method.

Like Commands.size(), as discussed above, this method should be simple glue code that calls the image-generation operation of your Expression data type. The body of Commands.image() should be at most 3 lines long, consisting of at most a couple calls to already well-tested methods, possibly using local variables, plus a return statement. If this is the case, then you don’t need separate tests for this method.

• Spec. The spec for this operation is given, but you may strengthen it if you want.
• Test. Keep this operation extremely simple so you don’t have to test it separately.
• Code. Implement image() as simply as possible.

5.3 Run the console interface

We’ve now implemented the !image command in the console interface. Run Main and try using it in the Console view.

Commit to Git. Once you’re happy with your solution to this problem (first for the minimal language, later for the full language), commit and push!

• Make sure you have documented specifications, in the form of properly-formatted Javadoc comments, for all your types and operations.

• Make sure you have documented abstraction functions and representation invariants, in the form of a comment near the field declarations, for all your implementations.

  With those comments, also say how the type prevents rep exposure. See Documenting the AF, RI, & SRE.

  Make sure all types use checkRep() to check the rep invariant and implement toString() with a useful representation of the abstract value.

• Make sure you have satisfied the Object contract for all types. In particular, you will need to specify, test, and implement equals() and hashCode() for all immutable types.

• Use @Override when you override toString(), equals(), and hashCode(), to gain static checking of the correct signature.

  Also use @Override when a class implements an interface method, to remind readers where they can find the spec.

• Make sure you have a thorough, principled test suite for every type. Note that the Expression type’s variant classes are considered part of its rep, so a single good test suite for Expression covers the variants, too.

Make sure you commit AND push your work to your repository on github.mit.edu. We will use the state of your repository on github.mit.edu as of 10:00pm EDT on the deadline date. When you git push, the continuous build system attempts to compile your code and run the public tests (which are only a subset of the autograder tests). You can always review your build results at didit.csail.mit.edu/6.031/sp20.

Didit feedback is provided on a best-effort basis:

• There is no guarantee that Didit tests will run within any particular timeframe, or at all. If you push code close to the deadline, the large number of submissions will slow the turnaround time before your code is examined.
• If you commit and push right before the deadline, the Didit build does not have to complete in order for that commit to be graded.
• Passing some or all of the public tests on Didit is no guarantee that you will pass the full battery of autograding tests — but failing them is almost sure to mean lost points on the problem set.

Your overall ps3 grade will be computed as approximately:
~35% alpha autograde + ~5% alpha manual grade + ~45% beta autograde + ~15% beta manual grade

The same autograder test cases will be used in both alpha to beta, but their point values will differ. In order to encourage incremental development, alpha autograding will put most of its weight on tests using only filenames, |, and @ with numbers (not ?), and less weight on tests that use the other features of the language (captions, @ with ?, ---, ^, and _). On the beta, autograding will spread its weight across the entire language.

Manual grading of the alpha will examine the specs of your Expression operations, the internal documentation (data type definition, AF, RI, etc.) of your Expression data type, and the implementations of Expression variants. Manual grading of the beta may examine any part, including re-examining ADT implementations, and how you addressed code review feedback.