Exercises to
Principles of Programming Languages and Systems

Peter Fritzson,

PELAB - Programming Environment Laboratory
Dept. of Computer and Information Science,
Linköping University, Sweden

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,

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

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 = 0;  b = 1;

print[] := Module[{ },

q[] := Module[{
  a = 3;  b = 4;  p = 5;

a = p[];

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.


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.




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.

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 Tichy, OH's by Peter F)

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.