[ This web application uses JavaScript, which is not enabled in your browser - for full functionality, use a browser that supports JavaScript ]

Virtual Machines for Programming Languages

Announcements

  • Mar 27: Adjusted exam schedule (please re^3-check).
  • Mar 26: Adjusted exam schedule (please re-re-check).
  • Mar 25: Adjusted exam schedule (NB: you may now be scheduled 20 minutes earlier, please re-check).
  • Mar 24: Added exam schedule. Note that the indicated timing is approximate.
  • Mar 07: Added exam questions and related information.
  • Mar 07: Added slides from Florian's lecture.
  • Feb 29: Added slides and mini project from Slava's lecture.
  • Feb 22: Added slides and mini project from Kevin's lecture.
  • Feb 17: Corrected the CSOM-without-readline link.
  • Feb 15: Set the topic for Kevin's guest lecture next week.
  • Feb 15: Uploaded slides, CSOM source, added link to paper and mini-project description.
  • Feb 07: Uploaded slides from today's lecture, the third mini-project, and added a couple of relevant links.
  • Feb 01: Uploaded a tar file with all the tests, compiled.
  • Jan 31: Uploaded the 2003 DAIMI Scheme project.
  • Jan 30: Uploaded a Scheme version of the Magritte-style decompiler.
  • Jan 26: Set-up the first mini-project for online handin in CourseAdmin.
  • Jan 25: Uploaded a Scheme version of the first half of the mini-project.
  • Jan 24: Supplemented the first half of the mini-project with a decompiler.
  • Jan 24: Uploaded the first mini project (note: there are two halves)
  • Jan 23: Added a link to dOvs slides including the sketch of a simple bytecode interpreter

Course description

This course focuses on how to design and implement virtual machines for programming languages. We will cover virtual machines for dynamically typed functional languages such as Scheme (as in the course Programming Language), co-routine based imperative languages such as Lua, and object-oriented languages such as Smalltalk. This involves the foundational ideas and touches upon techniques and designs behind some of today's high performance virtual machines. Execution models, adaptive code generation, garbage collection, threading, and sand boxing are all relevant subjects for this course. For the last part of the course, there will be guest lecturers from Google Aarhus, who have a very special expertise in this area.

Link to the official course description

Time and place:

Lectures: Tuesdays 13-16 in Nygaard-184, Finlandsgade 21

Tentative course plan:

LectureTopicCourse MaterialMini project
January 24VM basics (OD)First half:ae.sml and also ea.sml (and now ae.scm and also ea.scm) Second half: The universal machine
January 31The 2003 DAIMI Scheme projectProject03.tgz and Tests.tgz Implement, in C, a virtual machine for DAIMI Scheme
February 7Byte code dispatch techniques, closure representations, and a Lua 5.0 case study (JM) Lua 2.5 dispatch experiment
February 14OO virtual machines, and CSOM/Smalltalk case study (EE) Slides. CSOM source, in case you get compilation errors about readline and cannot install it, here is a variant: CSOM without readline. Self. Self download. The paper An efficient implementation of Self, a dynamically-typed object-oriented language based on prototypes (this is a journal version of the OOPSLA paper: same text, but nicer typography). Mini project: See the description on the last page of the slides. Note that CSOM must be compiled on a 32bit architecture in order to work. If several 32bit development packages are installed it is also possible to use a 64bit platform and cross-compile with options -m32 and -march=i486. For those who get bored, an interesting extension to this project would be to change the lookup_invokable method of VMObject to use binary search and change the lists of invokables to contain also inherited methods such that method lookup need not search superclasses.
February 21JIT compilation (Kevin Millikin, Google)Slides: in pdf and as Google docJIT Compilation for the UM
February 28Garbage Collection (Vyacheslav Egorov, Google)Slides: in pdfMini-project: Change your DAIMI-Scheme VM to use
  • unboxed integers (one bit for tagging should be sufficient, which leaves us with 31-bit numbers), or
  • a generational garbage collector
Measure the impact of your changes.
March 6Inline caching, hidden classes, and the Crankshaft V8 VM (Florian Schneider, Google)Slides: in pdf(None)

Links

Mini projects

The course includes a track of weekly mandatory mini projects.

Exam

The course finishes with an oral exam. Note: only students with approved mini projects can attend the exam.

Examination Requirements (da: Pensum)

The following papers and materials should be studied and used for the exam:

  • The DAIMI Scheme specification, available via links above.
  • The paper The Implementation of Lua 5.0, and the slides on dispatch techniques and closure representations, available above.
  • The paper An efficient implementation of Self, a dynamically-typed object-oriented language based on prototypes, available above.
  • The slides on JIT compilation, on garbage collection, and on inline caching, hidden classes, and the Crankshaft V8 VM, available above.

It is important that you make an effort to connect this (theoretical) material to the practical work in your mini projects, so please look for connections. We cannot expect you to know many thousands of lines of code that you haven't written (e.g., all of CSOM) in detail, but you can select specific parts of the code that you have been working with and explain why they are relevant in connection with a particular exam question. In other words, please find ways to use your practical experience to give more detail and depth to the material from the papers that you choose to focus on for each of the exam questions.

Exam Questions

  1. DAIMI Scheme
  2. Bytecode dispatch techniques (and possibly JIT compilation).
  3. Closure representations (and possibly Lua).
  4. Optimization techniques used in Self (and possibly connections to Smalltalk and CSOM).
  5. Garbage collection (and possibly run-time data structures in a broader perspective).

    In the exam questions, the "possibly" parts indicate related areas that you may or may not wish to include in connection with that particular question. Keep in mind that the exam lasts only 15 minutes, and it is important that you plan for a meaningful selection of topics to cover well, rather than trying to cover everything in a way that inevitably ends up being superficial.

    Concretely, for each exam question you should plan for having a mini-presentation taking about 7-8 minutes, such that you are ready to set the scene at the beginning of the exam, showing that you have chosen a particular approach to the topic and you have something to say about it. We will then gradually change this to an interactive form where we ask questions and enter into discussions with you, based on the topic and the things that you have already said. Note that we may begin to have this discussion already after a few minutes, or it may happen later on, depending on the situation.

    Exam Schedule

    The exam will be on Tuesday March 27, from 9am, in DI-5523.120.

    Here is the list of participants at the exam, with associated approximate timing. Please be there well before the estimated time, and note that we may adjust the ordering along the way if needed in order to ensure progress. We may also decide to take a break around 15.something.

    Approximate timeName
    09.00Janus Nørgaard Tøndering
    09.20Morten Elmvig Bruhn
    09.40Dennis Decker Jensen
    10.00Troels Ugilt Jensen
    10.20Asger Feldthaus
    10.40Jeppe Welling Hansen
    11.00Jørgen Ligaard Sørensen
    11.20Jørgen Fogh
    11.40Frederik Mogensen
    12.40Morten Kragelund Holt
    13.00Jens Johansen
    13.20Mikkel Nielsen
    13.40Nils Asbjørn Joensen
    14.00Søren Bramer Schmidt
    14.20Jacob Hougaard
    14.40Clement Scheelfeldt Skau
    15.00Kasper Føns Sørensen
    15.20Ole Rasmussen
    15.40Kaare Hoff Skovgaard
    16.00Lasse Jesper Garding Espeholt
    16.20Casper Svenning Jensen
    Data on this page is maintained by Jan Midtgaard.