Project 2: Types and parameter passing mechanisms

Goals of the project

This project will give you implementation experience in the following areas:

• Parameter passing mechanisms
• Types and type checking

In addition, this project will give you experience in using the following concepts:

• Nested scoping
• Objects and method invocations
• Opaque types

You will use the Modula-3 programming language for this project.

Introduction

The Modula-3 programming language supports two parameter passing modes: by value and by reference but it does not support parameter passing by name.  In this project we will write a preprocessor that takes a program written in a subset of Modula-3 plus some new syntax for parameter passing by name and rewrites it into a legal Modula-3 program that uses parameter passing by name.

Recall from the class notes that parameter passing by name works by passing a thunk instead of the argument.  In C++ like syntax, to implement parameter passing by name you would have to rewrite:

main() {
  int i;
  f(i);
}

as

main() {
  int i;
  int *i_thunk() {
    return &i;
  }
  f(i_thunk);
}

Also the body of "f" needs to be suitably modified so that every time it wants the value of its parameter, it invokes the thunk that is passed in instead of the parameter.  For example,

void f(int x) {
  x = x + 1;
}

would be rewritten as

void f(int * (*x_thunk())) {
  *x_thunk() = *x_thunk() + 1;
}

Note that the parameter to "f" is not "x" as before but a function that takes no arguments and returns a pointer to an integer.

My solution to this project has these phases:

• Parse the input and build an abstract syntax tree (I'm already providing you with this)
• Walk over the abstract syntax tree and resolve references.  Modula-3 allows forward references and thus, we need to build the AST first before we go to resolve the references.  Resolving references simply involves doing a lookup in the enclosing symbol tables while observing static scoping. (I'm already providing you with this)
• Walk over the abstract syntax tree and output the rewritten program.  Whenever I encounter a parameter that is passed by name, I output a thunk and pass the thunk instead.  Whenever I encounter a use of a parameter that was passed by name, I output a call to the corresponding thunk (whose name is simply the name of the parameter followed by _thunk).

My solution to the code you have to write makes up about 300 lines (including all declarations and blank lines between declarations).  However, in order to do this assignment, you will need to understand my code at some level and get a good understanding of Modula-3.  The two parts of Stage 0 will give you a good understanding of the code and a working knowledge of Modula-3.

Background: Modula-3

For a full definition of Modula-3 see the Modula-3 language definition.  Also, this tutorial (maintained by Francisco Reyes and Blair MacIntyre) may also be helpful to you;  amongst other things it shows you how to write a simple, small and self-contained program.  I recommend that you start with the tutorial and work through the examples there and use the language definition as a reference.  The language reference is compact (50 pages) but quite terse and does not have many examples.  The tutorial has several examples.  In addition, we will be giving you additional examples in recitation and class.

Modula-3 is not dissimilar to Java; as a matter of fact, some people jokingly call Java "Modula-3 in C++ syntax".  For example, Modula-3 has procedures just like  C++.  In the rest of this section, I'll describe some of the features of Modula-3 that are different from corresponding features in Java.

Procedures in Modula-3 versus C/C++

int f(char c) {
  if (ch == 'a') return 1 else return 0;
}

in C/C++ is similar to:

PROCEDURE f(c: CHAR): INTEGER =
  BEGIN
    IF ch = 'a' THEN RETURN 1; ELSE RETURN 0; END;
  END f;

Note that the "=" operator in Modula-3 is a test for equality and not an assignment as in C/C++/Java; ":=" is the assignment operator in Modula-3.

Objects in Modula-3 versus C++/Java

Modula-3 also supports objects, inheritance, and exceptions but they have a different syntax than Java.  The tutorial does not contain examples of objects but the language definition, of course, describes how they work.  I'll give a simple example here;  you will see more examples in class, recitation, and in the code I give you as part of the project.

Let's consider a simple class hierarchy in Java:

class T {
  int i;
  void m1();
};

class S extends T {
  int j;
  void m1();
 void m2();
};

void S::m1() {... }
void S::m2() {...}

In this hierarchy, class S inherits from class T and provides its own implementation for method m1.  In addition, it introduces a new method, m2.  An equivalent hierarchy in Modula-3 would be:

TYPE T = OBJECT
   i: INTEGER;
METHODS
   m1();
END;

TYPE S = T OBJECT
  j: INTEGER;
 METHODS
  m2() := mym2;
 OVERRIDES
   m1 := mym1;
  END;

PROCEDURE mym1(this: S) =
  BEGIN ... END mym1;

PROCEDURE mym2(this: S) =
   BEGIN ... END mym2;

There are two big differences between the Modula-3 and Java code: (i) In a modula-3 class overrides and new methods are delimited by OVERRIDES and METHODS respectively; (ii) In Modula-3 one needs to declare the "this" explicitly as the first argument of the method.  In Java (and C++), this is implicit.

Note that this is not intended as a complete or definitive description but just as examples.  You should refer to the tutorial and language definition for more information.

Using the Modula-3 system

The directions here apply to the linux machines in the undergraduate lab (which include  em, en, oh, pee, queue, are, es, tee, you, vee, doubleu, ecks, why, zee).

• To you use the Modula-3 system, you need to add /tools/cs/pm3/bin in your path.
• Each Modula-3 program has a "src" directory which must have a m3makefile.  m3makefile is like a Makefile except that it is more declarative: one simply needs to list the modules and interfaces in the m3makefile and not how to bould them and the dependencies between them.  I've already provided you with the m3makefiles so you probably do not need to do anything with them.  The SRC Modula-3 web page has lots of information on using Modula-3 and m3makefiles.  Also, I've put an entire program along with the m3makefile in ~csci3155/m3-example.  I recommend starting your exploration of Modula-3 with that example.
• To build a Modula-3 program, type m3build in the directory that contains the src directory.  This will compile the program and put the binaries in a directory LINUXLIBC6.  For this project, you can run the program by typing  LINUXLIBC6/m3byname at the shell prompt.

The Modula-3 distribution comes with a debugger m3gdb that works exactly the same as gdb.  I find it very handy for debugging programs.

Stages of the project

• Stage 0a, Due March 6th (15 points)
• Stage 0b (25 points)
• Stage 1 (25 points)
• Discussion (10 points)
• Stage 2 (25 points)

Resources

The SRC Modula-3 web page contains a wealth of information on how to use the Modula-3 compiler.  It also contains a link to an "alphabetical index" of all libraries that come standard with Modula-3.  You will note that I use several of these standard libraries for input/output, lists, etc. in my code.  Here are some libraries I recommend you look at; I've found them useful in my solution:

• Rd, Wr, Stdio: useful for input and output
• Scan, Fmt: useful for converting between different types (e.g., text and integer).  Note that the Rd and Wr libraries can only read and write text, so if you want to print anything other than text, you need to first convert it to text.  Scan and Fmt provide useful functionality for that.
• List and Table: these are generic modules (templates) that you can instantiate to get lists and tables.  Search my code for examples of both.

Note that m3makefiles have a special syntax for instantiating generic libraries (templates in C++ lingo).  For examplle, if you want to have a list of ParseNode, simply add this like to the m3makefile:
list(ParseNode, ParseNode)
This will automatically instantiate the template for a list and create a new interface and moule called ParseNodeList.i3 and ParseNodeList.m3 for you to use.  ParseNodeList.i3 has a type called "T" in it which is the type of the list.  You can use this list by importing ParseNodeList in your program.