HW#1 --- last modified February 28 2019 22:25:23..
Solution set.
Due date: Feb 16
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:
LO1 -- Have a basic knowledge of the history of programming languages.
LO2 -- Have a basic knowledge of the procedural, object-oriented, functional, and logic programming paradigms.
LO3 -- Understand the roles of interpreters, compilers, and virtual machines.
Specification:
For this assignment, you will submit all your files in the ZIP file Hw1.zip.
In this file make sure to have a file readme.txt which lists each group member
that participated in this project. There are two parts of this assignment:
a written part and a coding/experiment part. The written part should be in
a file history.txt in your ZIP file. For the written part of the
assignment, I want you to write a couple of paragraphs on the history of each
of the following programming language features: (a) regular expressions,
(b) iterators/generators, (c) object inheritance, (d) garbage collection.
For each try to find the earliest language which directly supported
the feature, find a modern language which supports the feature, and discuss
how the feature has evolved between the two languages. Make sure to properly
reference your sources, and if possible actually try to check out a book
or two rather than just rely on the internet.
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 a Operation typedef enum or an int. An Operation enum
can be one of MULT, ADD, CURR_POWER, or POWER. The idea is Expression's
can be used to represent things like:
74*(4+5)
where MULT is used to handle *, ADD is used to handle +, and exponents
like 74 are handled using POWER. Numbers are represented by
expressions where the leftArgument and rightArgument are both null and Data
is being used to contain an int. CURR_POWER is used to raise an int to
whatever is the value of the global int variable curr_pow, its right argument
is null.
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 four operations.
You should have a file evaluator.c which contains a function of prototype:
int eval(Expression E);
which calculates the int value of the supplied expression. This file should
also contain a recursive function of prototype:
int power(int x, int y);
for computing powers. 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. (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 some_number
will be typed. some_number might be 2, 3, etc. This should cause
the main function in driver.c to be called. curr_pow should be set to
some_number, 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 the addition of expressions is done and change that
operation to a multiplication. Assemble and link the result. Leave experiment.s in your zip
for the grader to look at. The point here is just to make you look at the kind of code (mod converting
to bits, dealing with symbols, and linking) that your computer really runs on. You don't
need to understand much assembly to do this (imul is the instruction for multliplication).
For the last part of this assignment, I want you to test out the gdb debugger. Use the
script command (type "man script" to find out how it works), to create a file debug.log
of your experiments. Have a make target test1simple (you don't need to do this for test2 or test3)
which rather than split the compilation of test1 into the steps above does just runs
gcc on the necessary source files with the -g (debug) flag. Then type "gdb test1simple", list
the program, set a breakpoint, run the program, use "step" at least once, use "next" at least once,
"print" the value of a variable, "clear" a breakpoint, and quit.
Point Breakdown
history.txt (1pt/feature) |
4 pts
|
Departmental C++ coding guidelines for your C program followed |
1pt
|
expressions.h follows spec above |
1pt
|
Functions eval and power work |
1pt
|
make test1,test2,test3 and running the result works, and the
file output.txt contains the correct value for the given expression. |
1pt
|
experiment.s as described |
1/2pt
|
Each of target's test1, test2, test3 is split into subtargets as
described above |
1/2pt
|
debug.log has the debug experiments described above |
1pt
|
Total | 10pts |
|