Exercises to
Principles of Programming Languages and Systems
by
Peter Fritzson,
PELAB - Programming Environment Laboratory
Dept. of Computer and Information Science,
Reporting course results
Hand in all course results in printed paper form.
a) People who hand in completed exercises at the latest Nov 30, 2004,
will have their course results reported in Dec 2004.
b) People who hand in completed exercises later will get their results reported during 2005
c) People who have a very low attendance at lectures may be required to answer a few questions orally.
Please tell whether you would like to do an extra mini-project.
Exercises for the course:
There are two editions of the course book: Louden1993 and Louden2003.
The exercises are now marked for both books,
Louden1993/Louden2003
Lecture 1
Introduction, History, Design Principles, Syntax
First read the chapters!
Chapter 1
Ex 23/1.25 which means Ex Chapter 1, 23 in Lounden1993
or Ex. 1.25 in Louden 2003.
Chapter 2
(Ex Louden1993, 8 - voluntary exercise, if you are specially interested)
Ex 12/2.13
Ex 14/2.14
Chapter 3
Ex 10/3.8
Ex 23/3.21
Chapter 4
Ex 7a/4.11a
Ex 7b/4.11b
Ex 10d/4.14d
In the Exp1 example, add an operator !, representing the factorial function,
update the grammar, and use yacc to regenerate the parser. Try it
on some mini example of your own.
Exp1 is described on page 17 in the RML book. The getting started chapter
is also helpful.
The yacc grammar file for Exp1 can be found in the directory
http://www.ida.liu.se/~petfr/princprog/rml-exp1.
Lecture 2
Basic semantics and type systems
Chapter 5 (7.1)
(In Louden2003: Also Expressions in Chapter 7, section 7.1)
Ex 1/5.1, 9/5.9, 10/5.8
**:
Write ex 9/5.9 in Mathematica with dynamic scope. Answer
the questions related to both static and dynamic scope, and try it. The static
scope version rewritten in Mathematica appears below:
p[] := Module[{
a
},
a = 0; b = 1;
Return[2]
];
print[] := Module[{ },
Print[a,b,p[]];
];
q[] := Module[{
b,p
},
a = 3; b = 4; p = 5;
Print[];
];
a = p[];
q[];
Ex 14/5.14, 15/5.22, 23/5.26, 29/7.1, 30/7.2
** Write your own Mathematica function myand
which
DOES NOT have short circuit evaluation
of and.
Ex 40/ 7.11, 41/ 7.12
Chapter 6
Ex 1/6.1, 3a/??, 7/6.8,
11/6.12, 25/6.22, 35/6.27,
36/??, 47/??
Lecture 3,
Functional programming, control, and parameter
passing
Chapter 7 (Chapter 8 in Louden2003)
First read the whole chapter!
Try Mathematica versions of the loop constructs you find on pages 201-203 in Louden1993 or on pages 276-278 in Louden2003.
x21 (a) Program Jensens device (described on page 219 in Louden1993 or
on page 324 in Louden2003) in Mathematica using call by name, to compute the
scalar produc of two vectors corresponding to array [1..n] of Integer.
Hint: read about call by name, intswap, etc. in Louden1993, pages 217-219, or
in Louden2003, pages 321-324). See lecture notes.
Try it!
x21 (b) Rewrite the sum procedure (on page 219 in Louden1993, on page 324 in Louden2003) in Mathematica using a function parameter for the parameter a to imitate call-by-name.
Study section 7.5.3 (p 231-233) in Louden1993 or section 8.4.3, p 336-339 in
Louden2003.
Write a variation of the Withdraw function in Mathematica, using the Withdraw
already available in the lecture3.nb notebook,
and try it on an account of your own.
Does it use stack allocation? Why or why not?
Chapter 10 (Chapter 11 in Louden2003)
1/11.1 (a) Write Power in functional form in Mathematica.
(b). Write it
in Mathematica in tail-recursive form using an accumulating input parameter.
(Hint: accumulating parameters (p477 in Louden2003) for recursive functions are
normallly input parameters).
(Note, not needed for 1b:
multiple result values can be used instead in Mathematica, e.g.
Call: {x,y} =
twoadd [3,5] makes x 5 and y 7
Definition: twoadd [x_,y_] := {x+2,y+2}
7/ 11.7: Write (a), (b),(c) in Mathematica.
Hint: solve the memoization problem in (c) as described by caching
function values (see Mathematica help master index)
15/11.18. Write a Mathematica list representation for the binary search
tree.
16/11.19. Write an insert procedure in Mathematica for the binary search data
structure.
24/11.26 (b), but in Mathematica.
30/11.32.
34/11.36. Write the sieve of Eratosthenes in a functional way in Mathematica,
with upper bound of largest desired prime
number given.
43/11.45 (a), (b), but use Mathematica to get the results instead of doing
it manually.
(Hint: a third argument {HoldAll} to Function[] in
Mathematica gives normal-order evaluation. See also Help.)
44/11.46. Try this using Mathematica.
Lecture 4
Object oriented programming and Abstract Data
Types
Chapter 9 (Chapter 10 in Louden2003)
3/10.3. Hint: see section 9.8 in Louden1993 or section 10.7.2 in
Louden2003.
4/10.4.
12/10.12.
16/10.15.
45/???
Define a closedfigure class hierarchy similar to the point classes given in
lecture4.nb with subclasses circle and and rectangle, similar to whats defined
in Simula on page 310, but in Mathematica using the Classes package for OO
programming (see lecture4.nb).
Chapter 8 (Chapter 9 in Louden2003)
1/ 9.1 a), b)
2/9.2 a)
Lecture 5
Formal Semantics
Chapter 12 (Chapter 13 in Louden2003)
3/ 13.3. (not 3b)
Add division to the Exp1 example language in the notes (lecture5.nb), both in
the RML natural semantics formalism for Exp1
and in the Mathematica version of Exp1 semantics, which you also should try.
Also compile and run the RML version.
x60.
Add environments and assignment to the Exp1 Mathematica based semantics.
Hint: Read page 470 in the book, and section 2.4 in the RML tutorial.
Try it!
Lecture 6
Versioning and Configuration Management
(article by
x59. Which are the five most important functions in a configuration management
system.
Why are these functions especially important ? Motivate and give examples.
Are there any other functions that you believe are equally important and should
be included?
x61. What are the basic software configuration management concepts? Why have
these concepts
been chosen and not other concepts?
x62. Describe (roughly) the development of some software of your own, or in
your group,
by drawing a version group diagram, including the typical operations.
x63. Describe how you could benefit from and use a software
configuration management tool
in your current research project (possibly together with your colleagues)
where some software development is performed.
Program Development Environments
(article by Dart et al. OH's by Peter F)
x64. Try to find other environments (not mentioned in the article),
belonging to each of the four main groups
of programming environments. Describe properties and motivate why an
environment should belong
to a certain group.
x65. The Mathematica system can be regarded as a structure-oriented and
language-centered environment.
Motivate why, or why not, if you do not agree.
x66. Use the Notation package (found via demo Notebooks in the Mathematica
help browser) to extend
Mathematica with a notation of your choice.
Extra exercise
This exercise can be done by interested students who
then will get an extra point.
Others who do a bigger mini-project of their own choice may also get an
extra point.
Below are some suggestions:
Alt 1. Make a natural semantics specification for the Eva
language described in Frank Pagan's book on programming
language semantics. (Used in the undergraduate Pteori course)
Alt 2a) Make a correct Mathematica implementation of the RML natural
semantics, including Fail.
In the lecture5 notebook examples I cheat in the handling of Fail.
Alt2b) Create an interactive RML environment within notebooks, by
integrating the RML parser parsing text from
a notebook cell, and transforming to executable form of alt2a).
Note: two students could cooperate, one doing 2a) and one 2b).
Something else of your own choice.