CS 4700 Programming Languages Assignment 1

Assignment 1 - Amok PostScript
CS 4700 - Programming Languages
Utah State University


Home
Calendar
Homework
Lectures
Handouts
Syllabus
Resources
People
Print

Overview

Weight: The homework will count 7% of your final grade.
Due Date (extended) Tuesday Sep. 20, 23:59 MDT
This assignment is a gentle introduction to the agony and ecstasy of PostScript programming.

It is to be your individual work. The problems are simple--you could probably do them in your sleep in C, and the whole assignment is considerably less than 100 lines of code (even being generous with line breaks!). However, remember that you have to do them in an alien language using alien tools and there is little debugging support.

Also, it is very important to test the code that you turn in. Every semester several people lose points because they make what they intend as a simple editorial change at the last minute, turn it in without testing, and it turns out to be broken.

Getting Started

There are two things to download for this assignment. First, is the PostScript interpreter. You can download the PostScript interpreter, GhostScript, at http://www.cs.wisc.edu/~ghost/. A PostScript viewer called GSview is also available and useful; it uses GhostScript. Downloads for both MS Windows and Linux are available. Follow the Resources link off the course web page to web sites that discuss Postscript programming.

The second thing to download is the starter code. You can either download the Windows version (zipped), ps.zip or the Linux version (tarred, gzipped) ps.tar.gz.

Turning in your work

Important: follow these directions exactly concerning file and directory names, file formats, etc. All code should be developed in the ps directory. The directory will have four files: question.ps, fibonacci.ps, squares.ps, and fractal.ps. Each file should contain only the required definition(s). For example, in question.ps, please put the definition of the ? operator, but *do not* include calls to that operator such as

   2 {1} {4} ?

The reason is that I will automatically test your programs by using our own calls, something like the following (on Unix)

   cat question.ps testQuestion.ps | gs

Turnin

Each problem solution should be placed in a separate file within that directory, e.g., question.ps. When you are done and certain that everything is working correctly, create a zipped or tarred, gzipped copy of the ps directory. Turnin in the (zipped) directory using the turnin page. Please upload the file ps.zip or ps.tar.gz. You may turnin your assignment as many times as you like.

Grading

The assignment will be graded for good programming style (indentation and appropriate comments), as well as clean compilation and execution.

The assignment will also be graded to ensure that each operator leaves the stacks and the drawing environment in the same state as when the operator was called (though operands will be popped from the stack). In other words, the operator should not leave extra values on the stack and should restore the graphics environment to that when the operator was called if the environment was changed.

question.ps -- 10%

This program should go into the file question.ps. Define an operator, ?, that mimics the ? conditional expression operator in C++. In C++, the conditional expression operator behaves as follows:

   expr1 ? expr2 : expr3

results in the evaluation of expr2 if expr1 is non-zero and the evaluation of expr3 otherwise. As a reminder, in C++, the operator can be used as follows.

   z = (a > b) ? a : b;  /* this implements z = max(a,b) */

In PostScript the ? operator will need three values on the stack where the first value is an integer, and the second and third values are code (you do not have to error check the types of the values on the stack).

   op1 op2 op3 ?

It evaluates as follows: if op1 is non-zero evaluate op2 otherwise evaluate op3. So, for example

   2 {(ok)} {(zero)} ?         % (ok) will be pushed onto the stack
   0 {(ok)} {(zero)} ?         % (zero) will be pushed onto the stack
  -1 {1} {0} ?                 % 1 pushed onto the stack
  1 {2 3 add} {5 4 add} ?      % 5 pushed onto the stack
  0 {2 3 add} {5 4 add} ?      % 9 pushed onto the stack

HINT: You will find the ifelse (and possibly the roll) operator to be useful.

fibonacci.ps -- 20%

Put this solution into the file fibonacci.ps. The fibonacci number function is recursively defined as follows.

     fibonacci(x) =
           0                                if x == 0
           1                                if x == 1
           fibonacci(x-1) + fibonacci(x-2)  otherwise

Define a recursive fibonacci function in PostScript. The implementation of fibonacci must be done as a recursive function, not a loop. This operator has one operand and one result so the stack must contain the same number of elements before and after the operation. Here are some examples.

   0 fibonacci   % pushes 0 on the stack
   1 fibonacci   % pushes 1 on the stack
   2 fibonacci   % pushes 1 on the stack
   3 fibonacci   % pushes 2 on the stack
   4 fibonacci   % pushes 3 on the stack
   5 fibonacci   % pushes 5 on the stack
   6 fibonacci   % pushes 8 on the stack
   7 fibonacci   % pushes 13 on the stack
   11 fibonacci  % pushes 89 on the stack

squares.ps -- 30%

This program should go into the file squares.ps. Write a PostScript definition for a function, squares, that takes an operand from the stack (call it n) and produces a line of n alternating light and dark squares. You should choose the size of the squares so that they are big enough to see easily and at least 10 squares fit across the page. I don't care about the precise gray levels as long as the individual squares are identifiable. For example

  4 squares

would look like
pretty picture

and

  8 squares

would look like
pretty picture

It is important that squares does not change the graphics environment of the calling function (so think about using gsave and grestore). This function has one operand and no results so after execution the stack will contain one fewer element than it started with.

fractal.ps -- 40%

EXTRA CREDIT: The three prettiest fractals (as adjudged by me) will recieve 10% extra credit (I'll use your calls in testFractal.ps). You may use color in your fractal.

This program should go into the file fractal.ps. Fractal is a term coined by Benoit Mandelbrot to describe geometric objects that are highly irregular and fail to fit into traditional geometry. They typically exhibit self-similarity, which means that a fractal has a structure, which at any scale, is an image of the overall structure. Recursive procedures are often used to draw fractals, with the same image drawn during every recursive call, but at an increasingly finer scale, often rotated and translated (HINT: use the PostScript coordinate transformation operations: translate, rotate, and scale). Assume that the dimension of a fractal is the level of recursion used in drawing the fractal (i.e., one level of recursion is a one-dimensional fractal, two levels is a two-dimensional fractal, etc.).

Your task is to define a fractal operator, fractal that draws the star fractal. i.e., 4 fractal, where 4 is the dimension. To get you started, here is what a basic star fractal, based on drawing a star with vertical lines at each recursive call, looks like at several dimensions. Note that you can fill in the star using a fill command (assuming the star is a path). For dimension 1 (called as 1 fractal ).

Or as a filled star.

pretty picture

For dimension 2 (called as 2 fractal ).

pretty picture

For dimension 4 (called as 4 fractal ). The star can be filled or unfilled as you like.

pretty picture

You don't have to make it look like these stars, as long as the star is drawn recursively as a fractal.