Programming Assignment I

The assignment is due on Jan 28.

The aim of this assignment is two fold.

  1. Development and implementation of a new notation
  2. Comparision of text processing in a conventional language (C) and in a scripting language (awk).

Motivation for the notation

Consider the notion of a function. A function returns a single value. For example, in C, we write 
              y = sin(x);
If multiple values are returned, one needs to use a "procedure". For example, if a single function returns, say, the maximum and minimum of an array, we cannot use the above notation. We should write something like 
              maxmin(inputArray, &max, &min);
The function maxmin returns two values, max and min. By looking at the declaration of procedure, it is not always clear which are the input values and which are the returned values. The declaration of the above procedure looks like 
             void maxmin(float*, float*, float*);
Can you spot the inputs and outputs? (Ada has some synatactic help for this. But you need to look into the declaration closely. For example, the Ada "procedure" get(in string, out number, out number) assigns number to the numeric value of the first 1..last characters of string. So string is the input and the other two are outputs. This is indicated by the keywords in and out.)

As discussed in the class, one of the aims of a programming language is to provide good notation. This project makes you explore one such notation which facilitates functions returning multiple values.

Consider a function which works on an array of reals and returns two real values: mean and variance. Note that the calculations of mean and variance are related and it might be efficient to compute them in a single function. So in addition to providing a good notation, there are efficiency reasons also for a function returning multiple values.

The "new" notation for functions is as follows. We'll call this language D. 

float, float stat(float*);  // declaration

float m, float v stat(float* x) { // function definition

// ... calculations ...

    m = ... ;
    v = ....;
}

int main(void) {
     float mean, var, *x, *y, *z;

// ... some computation ...

     mean = stat(x);  // mean gets the average
     mean, var = stat(y); // mean gets the average and var gets variance
     _, var = stat(z);  // only variance is used, the first value is ignored

// more computation

}
we now have a very good language. The only problem is that we need a compiler! Writing a compiler is not easy and lanuguage D has just one extra feature now. So we can do something simpler. We can write a preprocessor which reads a D program and outputs a C program.

Text processing

The preprocessor reads a D file and prints a C file. What does it do? It looks for function declarations, function defintions, and function calls in the new notation and converts them to valid C constructs. This calls for pattern matching and rewrite capabilities. Text processing can be done in a general purpose language or with a language designed for text processing. You will use two languages, C and Perl/awk, to do text processing and then compare the languages.

The assignment

For the assignment you should write a preprocessor in Perl/awk and C which converts the D programs to C. For this you will be using the pattern matching capabilities of the languages. Your programs should read D program from standard input and print the equivalent C program on the standard output. Please note
  1. You should use nawk as your awk interpreter.
  2. You should use only the standard C string manipulation functions. You should not use regexp functions.

Your code

Your Perl/awk file should be called dpreproc.awk or dpreproc.pl. Your C file should be called dpreproc.c. You will use "bundle" to submit your code. "bundle" looks for files with above names. So make sure that your files are named correctly. Make sure that your code is properly documented.

Your report

In your report you should discuss the following aspects.
  1. Part I: D language feature/notation
    1. other examples/counterexamples which show that this feature is useful/dangerous.
    2. evaluation of this feature in light of "Criteria for language design" (discussed in the class)
    3. other notations for functions returning multiple values
    4. overhead of this feature in terms of (1) learning (2) compilation and runtime support
    5. why this feature is not available in many languages
    6. OTHERS
  2. Part II: Comparison of C and Perl/awk for text processing
    1. Which languages did you know already? Which did you learn?
    2. Which is a natural choice for this task?
    3. What are the features *required* for this task?
    4. What are the sizes of the C and Perl/awk source code? Does the code size indicate anything?
    5. Did your thinking depend on the language you used?
    6. OTHERS

What to submit?

In summary, you should submit
  1. Your code using "bundle". The exact details will be announced later. Please watch the course homepage.
  2. A report of at most 5 (for Part I) + 5 (for Part II) pages. The report should contain the name of the account from which the code was submitted. Please submit the reports to Renata Teixeira at APM 3349D between 6:00 and 7:00 on Jan 28.
  3. Attach a hard copy of code and sample input and output as an Appendix to the report.
  4. A self-evaluation report filled and signed by all the team members.

References

  1. GAWK manual: gawk is slightly different from nawk which you'll be using. You can get a wealth of examples from this page.
  2. nawk manual (man nawk on Unix systems)
  3. Online Perl book
Note that only the team members can collaborate. No other form of collaboration is allowed. All resoures used should be explicitly cited.