HW#1 --- last modified September 09 2021 23:15:22.

Solution set.

Due date: Sep 20

Files to be submitted:
  Hw1.zip

Purpose: To learn about the history of each of the computational paradigms we will consider this semester. To gain experience with a procedural programming language, C. To learn about the steps in the compilation process, as well as the GNU compiler tools.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO1 (Course Learning Outcome 1) -- Recognize the history of programming languages.

CLO2 -- Discuss and distinguish the procedural, object-oriented, functional, and logic programming paradigms.

CLO3 -- Explain the roles of interpreters, compilers, and virtual machines.

Description:

This assignment consists of two parts, a written exercises and a coding part. I want you to put answers to the exercises below in a file Hw1.pdf which should be included in the Hw1.zip file you submit. Please remember the maximum upload size is 10Mb, so if your PDF contains images make sure to scale/compress them. I.e., BMP bad (uncompressed), jpg, png, etc good (compressed).

1. For each of the following programming languages: (a) FORTRAN, (b) LISP, (c) COBOL, (b) Simula, (d) CLU, (e) Smalltalk answer the following: What year did it first appear? Who were the creators of the language? What was an important new feature of the language? Give an example of the syntax of this feature.
2. Do exercise Sec 1.8 1.1 out of the book.
3. Do exercise Sec 2.6 2.1 out of the book.

For the coding part of the assignment, first you will create a typedef struct called Expression for holding expressions, and a function which can evaluate expressions built using your struct. This struct will have three components a Data typedef union type, and two pointers to Expression's leftArgument and rightArgument. The Data union type contains either an Operation typedef enum or a char pointer. An Operation enum can be one of CONS, FIRST, or REST. Expression's can be used to represent things like:

FIRST(REST(CONS("a", CONS( "b", "c"))))

This would evaluate to the string "b". Here CONS is intended to mean concatenate, REST is intended to return all characters from a string except the first, and FIRST is intended to return the first character of a string. For edge cases, FIRST applied to a NULL pointer returns NULL, REST on a NULL pointer or a single char returns NULL, CONS returns the other argument if either argument is NULL. Each of CONS, FIRST, and REST is assumed to take two arguments, but in the case of FIRST, and REST the second argument is ignored and so could be set to NULL. A Data struct using a char pointer as for an Expression still can be thought of as having two arguments, but in this case both are ignored.

Put the definitions of Expression, Data, Operation in the header file expressions.h . Create three files test1.h, test2.h, test3.h, each should have one Expression tree in it (a global variable declaration Expression tree = ...; ) built out of Expression's and making use of each of the three operations and string literals.

You should have a file evaluator.c which contains a function of prototype:

char* eval(Expression E);

which recursively calculates the string (as a char*) of the supplied expression. Use malloc for appropriate memory allocations.

Finally, you will create a program driver.c which has the main() function. You should have a Makefile with targets test1, test2, test3, all, and clean. The test1, test2, test3 targets, test the evaluation of the given test1.h, test2.h, test3.h expression tree, all makes each of test1, test2, and test3, clean gets rid of any intermediary files. The grader will switch into your Hw1 folder after unzipping Hw1.zip, and delete any executables. Then the grader will type:

make test1

to run the first test1. Similarly, for each of the other tests. Next,

./test1

will be typed. This should cause the main function in driver.c to be called. As make test1 was used, test1.h should have been included into driver.c (similarly, if make test2 was called test2.h should have been included, etc). The function main should call eval(tree) and then write the output to the file output.txt .

The next requirement for this project is that each of the make targets test1, test2, test3 depends on sub-targets for each of the stages of the compilation phase test1. By default, if you type "gcc myfile.c" it runs the preprocessor, compiles this, and then links the result. Instead, you should have targets like: preprocesstest1 which uses gcc's -E flag to output the result of just the preprocessor; compiletest1 which uses the -S flag to compile the result to assembly; assembletest1, which uses the as command to produce object code; and linktest1 which uses ld to link the objects code together. So that you have actually looked at what each phase outputs, after you are done your project above type, "make compiletest1", copy the file evaluator.s to experiment.s. Find where in the assembly that FIRST of expressions is computed. Make a file first.s where you have copy and pasted this part of the assembly code for the grader to look and at the top of the file say what line it came from in experiment.s.