9 ECTS credits
255 h study time

Offer 1 with catalog number 1000441BNR for all students in the 2nd semester at a (B) Bachelor - advanced level.

Semester
2nd semester
Enrollment based on exam contract
Impossible
Grading method
Grading (scale from 0 to 20)
Can retake in second session
Yes
Enrollment Requirements
Students who want to enroll for this course, must have passed or be enrolled for “Structure of Computer Programs I”.
Taught in
Dutch
Faculty
Faculty of Sciences and Bioengineering Sciences
Department
Computer Science
Educational team
Coen De Roover (course titular)
Activities and contact hours

39 contact hours Lecture
39 contact hours Seminar, Exercises or Practicals
Course Content
This course is an introduction to the implementation of programming languages using several evaluators and a compiler. Content-wise, the course corresponds to the second part of the seminal book "Structure and Interpretation of Computer Programs" by Abelson and Sussman. 
 
We start from an evaluator for the high-level language Scheme, implemented in Scheme. This implementation offers a precise, executable definition of the environment model discussed in the course "Structure of Computer Programs 1". Through several variations on this evaluator, we discuss the choices in the design (e.g., normal-order evaluation for the arguments to a procedure call) and in the implementation (e.g., separating the syntactic analysis from the evaluation of expressions) of programming languages. We conclude this chapter with an evaluator for a so-called "logic" programming language that no longer uses the lambda-calculus as engine, but concepts from predicate logic.
 
We then shift our focus from these high-level languages, to a more primitive language that is akin to assembly. We implement an evaluator for this language, and study programs in this language with attention to the differences between subroutines and procedures. Next, we implement a method of automatic memory management (i.e., stop-and-copy garbage collection) as well as a new evaluator for Scheme in this primitive language. We use this evaluator to illustrate the role of stacks in the implementation of procedure calls, and to explain how tail recursive procedures can give rise to iterative processes. We conclude with a compiler from Scheme programs to equivalent programs in this primitive languages.
 
Contents
 
1. Interpretation
  • Meta-circular evaluators for higher-order procedural languages
  • Separating evaluation from syntactic analysis as an optimisation  
  • Lexical versus dynamic scoping, applicative versus normal-order evaluation
  • Evaluators for logic languages: unification and resolution
2. Compilation
  • Evaluators for assembly languages: registers, subroutines, stack
  • Explicit-control evaluators in assembly language for higher-order procedural languages
  • Automated memory management (stop-and-copy garbage collection)
  • Compilation from procedural languages to assembly languages
 
Course material
Digital course material (Recommended) : Slides uit de hoorcolleges, opgaven en oplossingen voor de oefeningen uit de werkcolleges
Handbook (Required) : Structure and Interpretation of Computer Programs, Harold Abelson and Gerald Jay Sussman with Julie Sussman, 2de, MIT Press, 9780262510875, 1996
Additional info

  

 

Learning Outcomes

General competencies

The goal of this course is to familiarise students with notions of computer hardware; to emphasise the role of programming languages in this context; to investigate the architecture of interpreters, both meta-circular ones as ones expressed in basic register machine code; simulation of register machines; architecture of computer memory and management thereof; compilation of programs to register machine code, including some basic optimisation techniques.
 
The corresponding learning results are:
 
w.r.t. knowledge:
  • the student can explain how Scheme programs are executed using the implementation of the meta-circular evaluator discussed in the course
  • the student can illustrate the discussed variants on this input language using both example programs and extracts from the evaluators 
  • the student can situate the control over the evaluation of subexpressions inn the discussed evaluators
  • the student can situate the syntactic analysis of expressions in the discussed evaluators and the discussed compiler
  • the student can sketch the state of the memory before and after the invocation of the discussed stop-and-copy garbage collection algorithm
  • the student can illustrate the concept of tail recursion optimisation using extracts from the discussed evaluator for Scheme in register machine language
  • the student can illustrate the concept of tail recursion optimisation using extracts from the discussed compiler from Scheme to register machine language
w.r.t. applying knowledge:
  • the student can, given a register machine program, predict the usage of the registers and the stack
  • the student can, given an extension to one of the discussed evaluators, reconstruct the corresponding variant on the input language
  • the student can, given code produced by the compiler from Scheme to register machine language, reconstruct the corresponding source program
w.r.t. analysing:
  • the student can recognise variants on the discussed implementation techniques in the evaluators and compilers for similar languages 
w.r.t. evaluating:
  • the student can, for a given variant on the input language Scheme, evaluate the strengths and weaknesses of the discussed implementation techniques
w.r.t. creating:
  • the student can implement basic variants on and extensions to the input language Scheme in the discussed evaluators 
  • the student can implement basic algorithms in the discussed register machine language
  • the student can implement basic list-manipulation algorithms in the discussed logic programming language 
 

Grading

The final grade is composed based on the following categories:
Written Exam determines 100% of the final mark.

Within the Written Exam category, the following assignments need to be completed:

  • Exam with a relative weight of 1 which comprises 100% of the final mark.

    Note: The exam consists of a mandatory written part and an optional oral part.

Additional info regarding evaluation
The exam consists of a mandatory written part and an optional oral part.
If a student chooses to participate in the optional oral part of the exam, the grades for the written part and for the oral part of the exam will be weighted as follows:
- 80% written part
- 20% oral part
Otherwise, the student receives the grade for the written part as end result for this course.
 
During the written part of the exam, the student is allowed to consult the following material in published, printed, or handwritten form: the book for this course, the slides from the lectures, the student's own lecture notes, the student's own solutions to the exercises from the practical sessions.
 

 

Allowed unsatisfactory mark
The supplementary Teaching and Examination Regulations of your faculty stipulate whether an allowed unsatisfactory mark for this programme unit is permitted.

Academic context

This offer is part of the following study plans:
Bachelor of Computer Science: Default track (only offered in Dutch)