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. Run npm install, then open in Visual Studio Code. See Problem Set 0 for if you need a refresher on how to create, clone, or set up 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 the named image from a library of images stored as files. Even though operating systems allow a variety of characters in a filename, in this language a filename may consist of letters, digits, or periods, 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 web browsers widely support. 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.

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 also 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:

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:

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:

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:

boromir.jpg @ 100x?

This expression resizes 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:

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):

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

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

A command starts with !. The command operates on 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.

!image
generates the image represented by the current expression and displays it in a window. This command does not update the current expression.

!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:

> tech1.png | tech2.png
tech1.png|tech2.png

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

> !size
400x150

> !image

The system also has a web user interface. Users may input an expression and click Generate to see the parsed expression echoed back, the size, and the generated image.

Both user interfaces rely on these three provided function specifications in the code for this problem set:

• parse() from Expression.ts
• size() from commands.ts
• image() from commands.ts

And there are two more required specifications in Expression.ts:

• toString()
• equalValue()

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-4: we will add new Expression operations for computing the size of an expression and generating an image from an expression, and implement the corresponding commands size() and image().

The starting code includes a file examples.ts, with example code showing how to use the Canvas API 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.

And the starting code includes image-library.ts, which provides an API you must use in your implementation:

• createCanvas(..) to get a new Canvas instance
• getImage(..) to get the image data for a filename

This will allow your Expression type to work both in Node.js, for testing and the console user interface, and in the browser, for the web user interface.

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.ts) and implemented by several concrete variants, one for each kind of expression. You should have separate variant classes for each operator in the language, defined at the end of Expression.ts.

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

It must be legal to create and use an abstract syntax tree containing filenames that do not currently exist or have not been added to the image library. Only operations that actually require the image data (size and image) should try to read the image data. Others (like toString or equalValue) 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() and equalValue(). We are strengthening the specs for these standard methods; see below.

• Test. Partition and test your operations in ExpressionTest.ts, including tests for toString() and equalValue(). 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 TypeDoc 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, following the spec/test/code recipe.

The output 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. The required strengthened spec for toString() is already shown in Expression.ts. You can strengthen the spec further if you wish, but it’s not necessary for the spec to be deterministic.

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

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 equalValue()

Define the equalValue() operation on your AST to implement structural equality. The required spec for equalValue() is already shown in Expression.ts. You can strengthen it further if you wish.

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 equalValue() also satisfy observational equality.

Your equalValue() must be recursive, and it should use instanceof to test the variant of the expression it is comparing with: see the added section “Equality” in Recursive Data Types.

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 parse() from Expression.ts.

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. You may not use any of the characters reserved by the required syntax (e.g. -, |, etc.) or the console UI (!) in your additional features.

2.1 Write a grammar

Write a ParserLib grammar for expressions as described in the overview. A starting ParserLib grammar can be found in ExpressionParser.ts. 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
• 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 must be legal to parse an expression containing filenames that do not currently exist or have not been added to the library, since parsing does not depend on image data from the files.

• Test. Write tests for Expression.parse() and put them in ExpressionTest.ts. 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(), equalValue(), 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.ts that you can work from. Keep Expression.parse() itself extremely simple: it should be no more than glue code, calling a function like parseExpression in ExpressionParser.ts that has the implementation.

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 the console interface using npm start. Its prompt 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.ts, which you can find in the starting code for the problem set
• Canvas API

Warning: you must use the image-library.ts API, which provides getImage(..) and createCanvas(..). Do not import or use the canvas or fs modules directly.

3.1. Add an operation to Expression

You should implement size as a method on your Expression type, 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 – perhaps a simple record type of your own devising.

Do not generate images (discussed in Problem 4) in order to compute the size. In fact, there are some expressions whose size you can determine without reading any image data, and you are encouraged to design your operation to produce sizes for such expressions even if, for example, they refer to filenames that are not in the image library.

Follow the recipe:

• Spec. Define your operation in Expression and write a spec.
• Test. Put your tests in ExpressionTest.ts. 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 the size command

In order to connect your size operation to the user interfaces, and also to the Didit autograder, you need to implement the size() function in commands.ts.

Keep size() extremely simple. It should be no more than glue code, calling your size operation and converting the result to a string. If that’s the case, 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 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 TypeScript itself. If this is the case, then you don’t need separate tests for this method.

If your 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 create test/CommandsTest.ts and design a test suite for it. Before you do that, stop! First discuss your design with course staff, 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 npm start and try some sizes at the prompt.

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.

tech1.png|tech2.png
→

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

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

→

For generating images, you may find the following useful:

• examples.ts, which you can find in the starting code for the problem set
• Canvas API

You must use the image-library.ts API, which provides getImage(..) and createCanvas(..). Do not import or use the canvas or fs modules directly.

4.1 Add an operation to Expression

You should implement generation as a method on your Expression type, 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.ts. 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.ts included in the starting code has examples of doing this inspection.

4.2 Implement the image command

In order to connect your image operation to the user interfaces, we need to implement the image() function in commands.ts.

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

4.3 Run the console interface

We’ve now implemented the !image command in the console interface. Run npm start and try using some commands at the prompt.

4.4 Run the web interface

So far we have been running the image meme system in Node.js, by running the console interface and the tests. But the JavaScript that the TypeScript compiler emits can also run in the web browser.

First, start the provided web server using npm run web. This tiny Node.js web server will send the code and the image files to your browser. It does not run the code: all the parsing and image generation will done by your browser’s JavaScript engine.

Then, navigate to localhost:8080 in your browser. Enter an expression, and click Generate to see the results.

When you change your code, you do not need to restart the web server. Of course you do need to recompile your TypeScript into JavaScript (e.g. npm run compile), but once that’s done you can reload the web page to use your updated code.

(If you imported canvas, fs, or other modules directly, your code may not work in the web interface. Make sure you are only using the exports from image-library.ts.)

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 TypeDoc 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 specify, test, and implement equalValue() for all immutable types.

• When a method is specified in an interface and then implemented by a concrete class, use @inheritdoc to point to the interface spec, to indicate the method has the same spec.

• Make sure you have a thorough, principled test suite for every abstract data 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.mit.edu/6.031/sp22.

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.