Explorations with PAL and STUPID

Summary: In today's lab, you will primarily explore PAL, the pseduo-assembly language that I've written as an intermediate language for your compilers. You will also explore some aspects of STUPID, a simple higher-level language that you can compile to PAL.

Contents:

• Preliminaries
• Background: PAL
• PAL Exercises
  • PAL Exercise 1: PAL Basics
  • PAL Exercise 2: A Sum Program
  • PAL Exercise 3: Your Own PAL Program
• Background: STUPID
• STUPID Exercises
  • STUPID Exercise 1: Input, Output, and Expressions
  • STUPID Exercise 2: Conditionals
  • STUPID Exercise 3: Conditionals, Revisited

Preliminaries

Collaboration: Feel free to work on this lab in pairs or trios.

Turning It In: Save your answers in a plain text file and email it to me.

Grading: I expect that you will gain more from doing this lab than from me grading this lab. I may simply scan through your answers to see if you had any particularly valuable insights.

Preparation:

1. Make a copy of today's files with

cvs -d  /home/rebelsky/Web/Courses/CS362/2004S/CVS checkout Lab02

You will find that you now have a directory called Lab02.

2. Update your CLASSPATH to include /home/rebelsky/Web/Courses/CS362/2004S/Examples/. Here's one command that works (and that you might want to add to your .bashrc).

export CLASSPATH=".:/home/rebelsky/Web/Courses/CS362/2004S/Examples/"

Reference:

You can view all of the PAL source code at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Examples/rebelsky/pal/

For now, you need not read the STUPID source code.

Background: PAL

PAL, the pseudo-assembly language, is a set of Java classes intended to provide a simple assembly-language-like intermediate code. PAL consists of a model of a computer, Computer, a number of Variable subclasses that hold values, and a number of Instruction implementations that represent instructions.

The Computer class provides four key methods.

• The constuctor, Computer(int memsize), which builds a computer whose memeory holds memsize non-code values.
• setCode(InstructionSequence code), which sets the program code for the machine.
• dump(java.io.PrintWriter out), which prints the program to the selected destination.
• run(boolean trace), which runs the program (starting at instruction 0). If trace is true, it also prints out each instruction as it executes it.

Each Variable subclass provides four key procedures:

• iget(Computer hal) gets the integer associated with the variable.
• fget(Computer hal) gets the float associated with the variable. (PAL is untyped, so each container can store either kind of value.)
• iset(Computer hal, int newval) tells the variable to store a new integer value.
• fset(Computer hal, int newval) tells the variable to store a new float value.

There are many kinds of variables.

• IConstant variables store integer constants. Once created, they cannot change. (Yes, I know that means I shouldn't call them variables. Deal with it.)
• Register variables refer to the key registers. You cannot create new registers. Instead, you must use the built-in registers, Register.sp, Register.fp, and Register.pc.
• Temporary variables are temporary locations. You can think of them as an infinite number of registers.
• MemLoc variables are positions in memory. Each has an index (which can be any kind of container) which specifies where in memory the location resides.
• Label objects are also treated as variables because it simplifies the implementation.

Instructions provide one key method,

• execute(Computer hal), which executes the given instruction on that particular computer.

As you may have noted, a number of the methods take Computer objects as parameters. I've made that choice so that they can access or modify the state of the computer.

PAL provides an ever-growing set of instructions which you can identify by looking at the source code.

Note that the InstructionSequence instruction is a special instruction designed for building trees of instructions, as you would create while traversing a parse tree.

PAL Exercises

PAL Exercise 1: PAL Basics

a. Scan through TestPAL.java. See if you can determine what it does.

b. Compile and run TestPAL.java. Observe its output.

c. Why was the program able to use FWrite on input (temporary 0)? What was the output?

d. Turn off program tracing by setting the parameter to hal.run to false. Run the program again.

e. Update TestPAL.java to count down from 5 to 1 (instead of up from 1 to 10).

PAL Exercise 2: A Sum Program

a. Scan through SumPAL.java. As you can see, the program repeatedly reads values and shoves them on the stack. When 0 is entered, it repeatedly pops values off of the stack and adds them to the counter.

b. Run the program and enter three non-zero values followed by zero. Does it do what you expect?

c. Add an instruction to print the stack pointer at each step and rerun the program with three non-zero values. Does it do what you expect? When you're done observing the stack pointer, you can either keep or remove the line to print the stack pointer.

d. Run the program and enter seven non-zero values followed by zero. What does it do? WHy?

e. Run the program and enter five non-zero values followed by zero. What does it do? Why?

f. Run the program and enter four non-zero values followed by zero. What does it do? Why?

PAL Exercise 3: Your Own PAL Program

Write a PAL program that reads three numbers, initial, step, and final, and counts (by printing results) from initial to final using increments of step.

Background: STUPID

STUPID is a fairly minimal subset/variant of Pascal. It permits no function or procedure declarations. It supports only integer, real, and Boolean variables (although you can write strings). Conditionals always require both parts. STUPID is intended primarily as a platform for examples of compilation steps.

In this portion of the lab, you will explore how SIMPLE parses and translates some simple programs.

STUPID Exercises

STUPID Exercise 1: Input, Output, and Expressions

a. Look at sample.stupid. What do you expect it to do?

b. How would you describe the structure of the program?

c. What PAL instructions would you expect it to generate?

d. You can generate a parse tree, generate PAL instructions, and execute the PAL using the following command. Do so, and interact with the program.

java stupid.Stupid sample.stupid

e. How did the parse tree compare to what you expected? What were the key differences?

f. How did the PAL code compare to what you expected? What were the key differences?

STUPID Exercise 2: Conditionals

a. Look at testif.stupid. What do you expect it to do?

b. How would you describe the structure of the program?

c. What PAL instructions would you expect it to generate?

d. You can generate a parse tree, generate PAL instructions, and execute the PAL using the following command. Do so, and interact with the program.

java stupid.Stupid sample.stupid

e. How did the parse tree compare to what you expected? What were the key differences?

f. How did the PAL code compare to what you expected? What were the key differences?

STUPID Exercise 3: Conditionals, Revisited

a. What do you expect to happen to the code generated by testif.stupid if you replace

  if (x) then

by

  if (true) then

b. Check your answer experimentally.

c. What do your results suggest?