From PLSwiki

Jump to: navigation, search


Advanced Models and Programs, part 2 (SMP2), Spring 2008 (course code: SASP F2008)

This is the course page for Advanced Models and Programs.

Exam date

Thursday June 12th Friday June 13th (4A22)

Hand-in status


Practical and administrative matters

  • Lectures: Monday 9 -12 (Room 2A18), Wednesday 13-15 (Room 2A18).
  • Exercise labs: Wednesday 15-17 (Room 2A52).
  • The course period is 16 weeks half time (15 ects). The course will consist of five blocks, covering different themes, with weekly lectures and exercises; and a substantial four-week group project within one of the themes, resulting in a project report.
  • The weekly exercises must be handed in, and at least 9 of the 11 exercises must be approved to pass the course. You are allowed to work in groups to solve the exercises, but each individual student must write his/her solution up individually and hand it in by him/herself. The project must be done in groups (2-4 persons in each group) and the project report must be presented in an oral exam, where questions may be asked in all themes of the course.



  • The themes of the course are:
    • Dynamic object oriented languages and meta programming
    • Lexing, parsing and compilation: From source code to abstract syntax to stack machine code
    • Real and abstract machines
    • Program generation in Scheme
    • Static Analysis; in particular, Data-Flow Analysis
    • ...
    • ...


Week Date Teacher Topic Materials Assignments
05 Mon 28 Jan Smalltalk Basics Squeak by Example Chap 1-4 Week 1
05 Wed 30 Jan Smalltalk Meta programming Squeak by Example Chap 5,6,12
06 Mon 04 Feb Open applications Open Implementation Design Guidelines
Towards a New Model of Abstraction in the Engineering of Software
06 Wed 06 Feb Exception Handling
Continuations light
Fully Object Oriented Exceptions
Week 2
07 Mon 11 Feb Ruby Selected sections from Programming Ruby -The Pragmatic Programmer's Guide
07 Wed 13 Feb Self and Beta - non-standard object models SELF: The Power of Simplicity
Virtual Classes A powerful mechanism in object-oriented programming
Week 3
08 Mon 18 Feb PS Abstract syntax, interpretation and checking; lexing and parsing Mogensen sections 2.1-2.8 and 3.1-3.6. Sestoft PLC chapters 1-3. Slides
08 Wed 20 Feb PS Compilation and stack machines Coco/R User Manual pages 1-17, 23-29. Sestoft PLC chapters 1-3 and 7.2. Slides Week 4
09 Mon 25 Feb PS Micro-C and pointers Kernighan and Ritchie chapter 5. Sestoft PLC chapters 6-7. Slides
09 Wed 27 Feb PS Bytecode, abstract machines, and real machines Sestoft PLC chapters 10-11. Sestoft: Numeric performance in C, C# and Java. Ecma-335, partition I, section 12.3. Richter, chapter 1. Slides Week 5
10 Mon 03 Mar PS Scheme and multi-stage programs Dybvig sections 2.1-2.7, 6.1. Sestoft PLC chapter 14 Slides
10 Wed 05 Mar LB ML intro + expression evaluation Harper Ch. 2-3-4 Slides Week 6
11 Mon 10 Mar LB ML intro + interpretation + compilation Harper Ch. 5-6-7 Slides
11 Wed 12 Mar LB ML intro: data types and higher-order functions Harper Ch. 9-10-11 Slides

Week 7

12 Mon 17 Mar Easter holiday
12 Wed 19 Mar Easter holiday
13 Mon 24 Mar Easter holiday
13 Wed 26 Mar LB ML vs OO: the expression problem Torgersen ECOOP'04 paper
14 Mon 31 Mar CB 3 hour (interactive) lecture on Introduction: Undecidability, Static Analysis, Data-Flow Analysis, and Control-Flow Graphs Slides Lecture Notes Chapters 1, 2, and 5; i.e., pages 3-6 + 15-17.
14 Wed 02 Apr CB 4 hour (interactive) lecture on "Extraterrestrial Mathematics" (Partial-Orders, Lattices, Monotone Functions, Fixed-Points, ...) and connection to Data-Flow Analysis Slides How to solve recursive equations Lecture Notes Chapter 4; i.e., pages 11-15. Hand-in 9A
15 Mon 07 Apr CB 3 hour (interactive) lecture on Data-flow Analyses in practice; we'll study examples Slides Lecture Notes Chapter 6; pages 17-19 + 28-32.
15 Wed 09 Apr CB WORKSHOP on Data-flow Analysis (no lecture); we'll be making analyses :-) Slides Relations as least fixed points of Inference Systems Lecture Notes Chapter 6; pages 19-32. Hand-in 10B
16 Mon 14 Apr MS intro see [1] for slides
16 Wed 16 Apr MS partial derivative regular expression pattern matching
17 Mon 21 Apr MS 0900-1000: Presentation of project proposals (see below).
17 Wed 23 Apr MS

In weeks 18-21, Mon 30 Apr - Wed 21 May, students work on their project. Projects must be handed in no later than Wednesday 21 May at 1500.

Literature and materials

Course project proposals

  • Proposed by Peter Sestoft:
    • Slides with proposal details
    • Change the MicroC compiler to generate x86 code in the form of input for the NASM assembler.
    • Extend the MicroC compiler to handle more of real C, such as struct types, switch, break, continue, malloc/free.
    • Code duplication discovery in Microsoft Dynamics NAV application code. In collaboration with Microsoft Development Center Copenhagen.
    • Write an interpreter -- in Standard ML, Scheme, Java or C# -- for a substantial subset of the Icon language, or for SETL or another "unusual" language.
    • Performance engineering for a managed platform (JVM, .NET) and modern x86 cpus. Consider either numeric intensive code (matrix multiplication), or object-intensive code such as the C5 collection library. Investigate bottlenecks using profiling, and experiment with alternative implementations and target platforms.
    • Write a generator of specialized serialization/deserialization methods in C# (to XML or Json).
  • Proposed by Lars Birkedal:
    • Study the type inference problem for Mini ML and solve associated problems by paper and pencil (proving selected properties of the type system and the algorithm by induction).
    • Implement the type inference algorithm W for Mini ML.
  • Proposed by Claus Brabrand:
    • Make a Data-Flow Analysis and implement it such that it can analyze (and optimize) programs written in (a subset of) some familiar language (e.g., Java, C#, ...)
    • Slide with proposal
  • Proposed by Andrzej Wasowski:
  • Proposed by Kasper Østerbye:
    • Use of continuations in webservers. We briefly looked at that in the course, but here I suggest to dive in and understand it in detail. And to make an assesment of the performance characteristics of such a solution.
    • Dissect a debugger. We can look at the debugging interface to Java, or dissect the Smalltalk debugger.
    • Build a Java version of the Squeak "find method" (the tool in which you write an example input/output and it suggest methods that give that result).
    • As always, your suggestions are better than mine.

Project rules

Actual projects for May 2008

  • Paul Brønnum: Extension of MicroC compiler [PS]
  • Till Blume, Tijs Slaats, Roland Schlosser: Code duplication discovery in Microsoft Dynamics NAV [PS]
  • Andreas Møller Holst, Ramakrishnananda Karidas: Code duplication discovery in Microsoft Dynamics NAV [PS]
  • Jon Eikholm, Jack Lee: Compiling MicroC to x86 code [PS]
  • {Kevser Andersen, Jørn Schou-Rode, Jeppe Larsen, Dario Pacino}: Having fun with Data-Flow Analyses [CB]
  • {Adrian Sobotta, Andreas Nørgaard, Jonas Hubert, Morten Boysen}: Also having fun with Data-Flow Analyses [CB]
  • Nicolo Perra: Distributed Transactions [MS]


The official course description says:

  "The project report must be presented in an oral exam, where
  questions may be asked in all themes of the course. A single grade
  is given, based on the project and the oral exam."


  "Ekstern censur, [7-trinsskala], B4: Mundtlig eksamen med skriftlige
   arbejder men uden forberedelsestid ved eksamen."

We allow 15+15N minutes for examination of a group consisting of N students. In the examination, 10+7N minutes are spent presenting and discussing the project work, and 8N minutes are spent asking questions in other areas of the course. The latter questions relate to the problems posed in the 11 mandatory exercises. Due to the ridiculous new exam laws, each student will be examined individually in the 8N minutes part - where we might ask supplementary questions about the project as well.


Evaluation (Intended Learning Outcomes)

The course has two parts as detailed under course form below - a regular course followed by a project.

After the course, the students are expected to be able to:

  • describe relevant concepts within the themes of the course,
  • account for the practical applications of the covered constructs, and
  • compare selected techniques and constructions within a single of the course themes.

On the basis of the project, the student are expected to be able to:

  • apply relevant methods and techniques in the chosen project
  • argue for the overall design-decisions in the project, and
  • relate project and theory.


Personal tools