Project 3: Quilt

```{.quilt .code size=512 name=images/swirl} let swirl = (let grate = -cos (x20pi)/2 + 0.5 in grate @ (20(sin(50sqrt(xx + yy))))) in swirl * yellow + (y+1)/2 * blue


In this project, you will create a language which can describe and
produce images like the one above!

Getting started
---------------

- Download the [project skeleton](/csci360/projects/quilt/quilt.zip).  This provides:

    - [`QuiltREPL.hs`](/csci360/projects/quilt/QuiltREPL.hs): a REPL, similar to the one on the calculator project
    - [`Quilt.hs`](/csci360/projects/quilt/Quilt.hs): starter code
    - [`Parsing2.hs`](../code/Parsing2.hs)
    - [`quilt.cabal`](/csci360/projects/quilt/quilt.cabal)
    - [`stack.yaml`](/csci360/projects/quilt/stack.yaml)
    - [`LICENSE`](/csci360/projects/quilt/LICENSE) (feel free to edit this file to add your name)

- While working on your project, to load it into `ghci` (e.g. in
   order to try out a function), you can use the `stack repl` command.

- To compile and run your project, you can use the command `stack run`
  (this should be typed at a terminal/shell prompt, not at a ghci
  prompt).

    - You should get a prompt where you can enter quilt expressions
      and commands.  Currently, it will only generate an image of a
      blue square.

    - Simply exit the program and rerun `stack run` every time
      you want to test changes you have made to `Quilt.hs`.

- If you like, you can also view the source for this project
  description file itself, although it is not necessary: [Quilt.lhs](Quilt.lhs).

The Quilt language: basic examples
----------------------------------

The basic Quilt language has real numbers, booleans, arithmetic
operations, `if`-expressions, names of standard colors, RGB color
expressions, and `quilt` expressions.

The name of a color by itself produces an image consisting entirely of
that color:

```{.quilt .code size=256 name=images/red}
red

Arithmetic can be done on colors, which results in their red, green, and blue channels being operated on componentwise.

```{.quilt .code size=256 name=images/purple} red + blue


Colors can be explicitly constructed by giving a triple of values in
list notation.  Each channel should be a number between 0 and 1;
[0,0,0] represents black and [1,1,1] represents white.

```{.quilt .code size=256 name=images/explicitcolor}
[0.2, 0.8, 0.5]

To make things more interesting, there are special reserved variables x and y which can be used to refer to the position within the image. All the images are centered at the origin, with x and y ranging from $-1$ to $1$. As a simple example, we can use if together with x and y to choose different colors for different parts of the image.

```{.quilt .code size=256 name=images/half} if x < y then red else blue


We can also use `x` and `y` in more continuous ways.  For example,
this image smoothly interpolates between red and blue, using the value
of `x`.

```{.quilt .code size=256 name=images/redblue}
(x+1)/2*red + (1-(x+1)/2)*blue

We can also use x and y inside a color expression, as a more direct way to produce smoothly varying colors.

```{.quilt .code size=256 name=images/colorxy} [(x+1)/2, (y+1)/2, 0.5]


Finally, the `quilt` operator takes four images and arranges them in a
square.

```{.quilt .code size=256 name=images/quilt}
quilt 0.4 yellow red (quilt green orange blue purple)

Notice how the number 0.4 can be used as a color, resulting in the color [0.4, 0.4, 0.4] (a dark gray).

Grammar

More explicitly, the basic Quilt language has the following grammar:

<colorlit> ::= 'red' | 'orange' | 'yellow' | ...
<num>      ::= integer or floating-point
<coord>    ::= 'x' | 'y'
<bool>     ::= 'False' | 'True'

<qexp> ::=
  | <colorlit>
  | <num>
  | <coord>
  | <bool>
  | '[' <qexp> ',' <qexp> ',' <qexp> ']'
  | 'if' <qexp> 'then' <qexp> 'else' <qexp>
  | <uop> <qexp>
  | <qexp> <bop> <qexp>
  | 'quilt' <qexp> <qexp> <qexp> <qexp>

<uop>        ::= '-' | '!'
<bop>        ::= <arith> | <comparison> | <boolean>
<arith>      ::= '+' | '-' | '*' | '/'
<comparison> ::= '<' | '>' | ...
<boolean>    ::= '&&' | '||'

Types

Quilt has three types:

In general, an expression of type X represents a function that assigns a value of that type to every $(x,y)$ coordinate. For example, an expression of type Boolean represents not just a single True or False, but an assignment of True or False to every $(x,y)$ coordinate. For example, x < y has type Boolean, and assigns True to every coordinates where $x$ is less than $y$, and False to the others.

Note that a Color value is just a triple of arbitrary floating-point numbers; it does not necessarily have to be a valid, visible color. For example, [0.2,0.3,-1] is a “color” even though an actual visible color must have three values between 0 and 1.

There is one final twist: numbers are a subtype of colors, that is, a numeric value can be used anywhere that a color is expected. (As we have seen, the number $n$ will be interpreted as the color $[n,n,n]$.) This has some interesting implications. For example:

Some hints for dealing with subtyping in your type checker:

Semantics

The x and y coordinates for an image produced by the Quilt language will both vary from -1 to 1, with the origin (0,0) in the center of the image.

Everything in the quilt language (booleans, numbers, colors) can vary continuously over 2D space. For example, consider the expression x < y: x and y both have type Number, so x < y has type Boolean. However, semantically it does not represent just a single boolean, but rather a function of type Double -> Double -> Bool which attaches a boolean value to every point in 2D space (according to whether the x-coordinate at that point is less than the y-coordinate). If you look again at other examples above, you will see more examples of numbers and colors varying over space.

This means your interpreter should always produce something of the form (Double -> Double -> ...). One could have it produce a Double -> Double -> Value, and define a new type Value which can be either a boolean, a number, or a color. However, since Quilt expressions will be typechecked, you can use the same trick we have used before: just represent everything (booleans, numbers, and colors) as a Color, that is, a list of Double values. So your interpreter will always output a QuiltFun, that is, a Double -> Double -> Color. A boolean can be represented by, say, [0] or [1]; a number n should be represented by the list [n,n,n]. If you have a [Double] but need a boolean or a number, just get the first element of the list. This way, your interpreter does not actually have to worry about issues of subtyping or conversion, and it does not need to do any pattern-matching to figure out what kind of value it has.

What to turn in

Level 1

For Level 1 credit, get the Quilt language as described above working in the context of the provided REPL. The user enters an expression, and is shown a syntax error, a type error, or gets an image.

Level 2

To complete this project to Level 2, in addition to the requirements for Level 1:

Level 3

To complete this project to Level 3, in addition to the requirements for Level 2, you must complete at least three extensions, at least one of which is not in the list below. Feel free to consult with me if you are unsure whether your idea for an extension is feasible or substantive enough.

Suggested extensions