CS4215 - Programming Language Implementation

Brief Description

This module provides the students with theoretical knowledge and practical skill in the implementation of programming languages. It discusses implementation aspects of fundamental programming paradigms (imperative, functional and object-oriented), and of basic programming language concepts such as binding, scope, parameter-passing mechanisms and types. It introduces the language processing techniques of interpretation and compilation and virtual machines. The lectures are accompanied by lab sessions which will focus on language processing tools, and take the student through a sequence of programming language implementations. This modules also covers automatic memory management, dynamic linking and just-in-time compilation, as features of modern execution systems.

Module Calendar

Topics

  1. Programming language processing tools and introduction to compilers (2 lecture hours)
  2. ePL: An Expression language (2 hours)
  3. simPL: A simple functional language (6 hours)
  4. rePL: Records for Functional Programming (2 hours)
  5. imPL: A Simple Imperative Language (3 hours)
  6. oPL: A Simple Object-oriented Language (3 hours)
  7. cPL: A Simple Concurrent Language (3 hours)
  8. Memory management, garbage collection (3 hours)
  9. Implementation of type systems (1 hours)

Course Material

The course material (notes, slides, software) is accessible in the following table.

Lecture Date Subject Slides Notes Additional Material
01 13/1 Language Processing, Induction Slides in color,
Slides in b/w,
 Notes 01 For the mathematics behind T-diagrams, take a look at the original paper: J. Earley and H. Sturgis. A formalism for translator interactions. Communications of the ACM, 13:607-617, 1970.

Programming languages are ubiquitous in the world of IT. To illustrate this point, a description is given what languages were used to produce the slides for lecture 01.

02 20/1 ePL: An Overture Slides in color,
Slides in b/w
webcast 		Notes 02 -
03 24/1 simPL: Language, Dynamic and Static Semantics and their Implementation Slides in color,
Slides in b/w,
webcast not available due to technical problems 		Notes 03 -
04 3/2 Typing + Denotational Semantics for simPL = A Realistic Interpreter Slides in color,
Slides in b/w,
webcast 		Notes 04 -
05 10/2 A Virtual Machine for simPL Slides in color,
Slides in b/w,
webcast 		Notes 05 -
06 17/2 Memory Management Slides in color,
Slides in b/w,
webcast 		Notes 06 To understand how Cheney's algorithm interacts with the virtual machine, take a look at the Flash animation created by a previous student Pham Thanh Phong.

For a detailed look at the workings of Cheney's algorithm, look at an animation created by Bryan Scappini.

07 2/3 rePL I Slides in color,
Slides in b/w, webcast 		Notes 07 -
08 9/3 rePL II Slides in color,
Slides in b/w, webcast 		see Notes 07 -
09 16/3 imPL Slides in color,
Slides in b/w, webcast 		Notes 09 -
10 23/3 oPL Slides in color,
Slides in b/w, webcast 		Notes 10 -
11 30/3 cPL Slides in color,
Slides in b/w,
webcast not available due to technical problems 		Notes 11 -
13 13/3 Challenge presentation and summary Mark & Sweep by Chen Weiguang,
Type Inference by Romain Edelmann,
webcast 1 webcast 2 		no notes, but a white board written by the lecturer, picture taken by Heng Low Wee -

Lab Tasks and Self-Assessments

week Lab tasks and self-assessments are distributed online on this web site. The course comes with weekly lab sessions that cover the practical aspects of the course material. Attendance of the lab session is required for this module.

rr
Self-assessment Self-assessment solution Lab task Date handed out Time due Lab task solution Additional Material
Self-assessment 1 - - - - - -
- - Lab task Week 2 20/1 26/1, 23:59pm; submit the files ePLdynamic\Evaluator.java and eVM\VM.java in the IVLE workbin "Lab Tasks Week 2" Lab task Week 2 Solution -
- - Lab task Week 3 31/1 3/2, 23:59pm; submit the file simPL\Application.java in the IVLE workbin "Lab Tasks Week 3" Lab task Week 3 Solution -
- - Lab task Week 4 3/2 9/2, 23:59pm; submit the files in the IVLE workbin "Lab Tasks Week 4" Lab task Week 4 Solution -
- - Lab task Week 5 10/2 16/2, 23:59pm; submit the files in the IVLE workbin "Lab Tasks Week 5" Lab task Week 5 Solution -
- - Lab task Week 6 19/2 1/3, 23:59pm; submit the files in the IVLE workbin "Lab Tasks Week 6" Lab task Week 6 Solution Slides shown in Lab Week 7 in color and B/W for printing
- - Lab task Week 8 12/3 17/3, 23:59pm; submit the files in the IVLE workbin "Lab Tasks Week 8" Lab task Week 8 Solution Slides shown in Lab Week 9 in color and B/W for printing
- - Lab task Week 9 19/3 24/3, 23:59pm; submit the file in the IVLE workbin "Lab Tasks Week 9" Lab task Week 9 Solution (including optional parts)
Lab task Week 9 Solution for testing student programs 		-
- - Lab task Week 10 27/3 31/3, 23:59pm; submit the file in the IVLE workbin "Lab Tasks Week 10" Lab task Week 10 Solution -
- - Lab task Week 11 28/3 7/4, 23:59pm; submit the file in the IVLE workbin "Lab Tasks Week 11" Lab task Week 11 Solution -

Challenges

Students who are interested in challenge projects indicate their interest via email to the lecturer by 13/3, 12noon. The lecturer will provide project support and management assistance. After project completion, the submission will be assessed by the tutor and lecturer. Sufficient achievement leads to issuing of an Assignment Voucher, which the qualifying student can use at the end of the semester to replace any module assignment score by full score.

Date handed out Challenge Time Due Additional Material Selected Submissions
9/3 Just-in-time compilation of simPL 30/3, 23:59 - -
9/3 Machine code verification 30/3, 23:59 - -
9/3 Compiling simPL to x86 machine code /3, 23:59 - -
9/3 Mark-and-Sweep Garbage Collection for simPL 30/3, 23:59 - -
9/3 Reference Counting Memory Management for simPL 30/3, 23:59 - -

Other Course Information

Mounting Information
Elective module for students in the programme Bachelor of Computing (Honours) in Computer Science, and for a Master of Computing (coursework).
Prerequisites
Pass CS2104 (or CS3212)
Instructor
Martin Henz, short: MH, consultation: Whenever you want to see me, please propose a meeting time by email to .
Assessment
Tutors
Lectures
13 sessions, 2 hrs/wk, time: Monday 4 - 6 pm, place: COM1, 212.
first lecture: 10/1/2011, see module calendar and official NUS Academic Calendar
Lab Sessions
11 lab sessions, 2 hr/wk.
Venue: COM1, B11
first sessions:
Textbook
There is no textbook. The notes provided for each lecture make up the course material. Books for additional reading will be recommended from time to time.
Assignments
One assignment will usually be given out each week on this course page. Assignments are handed out on Thursdays and they are due as announced, usually one week after hand-out. Assignment scores make up 20% of the overall marks.
Discussion group
IVLE discussion forums are set up for CS4215. There is a topic in the main forum for every chapter of the course notes, as well as forums for anonymous feedback and discussing administrative matters such as exams.
Announcements
Announcements are distributed using the IVLE Announcement feature.
Webcast of Lectures
The lectures are available as IVLE Webcast.
Midterm Exam
The midterm was held as a multiple-choice (MCQ) open book exam, on 2/3, at 10:00am in COM1/212.

The topics covered by the midterm included Lectures 1 through 6, including Chapter 9 Memory Management. The midterm did not cover Section 8.12 (notes_05.pdf) on Tail Recursion.

See midterm questions and answers. See also sample midterm questions and solutions for practice, and another one for additional practice.

Final Examination
May 3, 2011, morning

The final exam will be a two-hour open book exam.

To practice, you may want to look at last year's exam with solution.

Martin Henz