Weekly Note 7, DM18, Spring 2007
Lecture February 27
Background material: Appel Chapters 7, 8, 9.
In this course, we have a slightly different focus from that in
the textbook. As a consequence, we will take a simpler and more direct
approach to code generation. Thus, it is recommended that you
merely skim over the material in the book and read later
to the extent that you need the material.
Exercises March 9
-
Consider code generation templates for the following constructions:
-
for-loops (Pascal style):
for i:=7 to 42 do SOMETHING
.
-
for-loops (C style).
-
loops with break/continue, i.e., the loop is as a starting point infinte,
break exits the loop and continue starts from the beginning. For both
break and continue, this is independent of where in the loop code
you are.
-
switch (C) and case (Pascal) constructions.
-
records.
-
arrays.
-
multi-dimensionel arrays; this is different from arrays of arrays.
You must find a layout such that you can efficiently compute
the address of A[i,j,k], for instance. Thus, it must be different
from following three pointers as you would logically do if you used
A[i][j][k].
-
conditional expressions in C style: ( exp ? exp : exp ).
-
What is the semantics of
i:= 7; for i:=i+1 to i+2 do {i:=i+3; print i}
according to your template above, i.e., what is printed?
What are the reasonable behaviors?
-
Are there efficiency reasons to restrict switch/case expressions
to be simple types and only use values from a small domain?
-
Some programming languages offer lists with random access
(
A[i]
), append (A.append(42)
), and insert
(A.insert(pos,val)
) which inserts val
in between the positions pos
and pos+1
.
Can this be implemented efficiently?
-
Consider constructions which are typically allocated in the heap,
e.g., Tigris arrays or C structs.
How can they give rise to (enormous) vaste of space?
How is it possible in principle to check if allocated space
is still used and thereby "collect" unused space for reuse?
Last modified: Tue Feb 20 10:59:35 CET 2007
Kim Skak Larsen
(kslarsen@imada.sdu.dk)