Skip to content

50.054 Compiler Design and Program Analysis Course Handout

This page will be updated regularly. Sync up often.

Course Description

This course aims to introduce a new programming paradigm to the learners, Functional programming and the suite of advanced language features and design patterns for software design and development. By building on top of these techniques, the course curates the process of designing a modern compiler, through syntax analysis, intermediate presentation construction, semantic analysis and code generation. More specifically the course focuses on the application of program analysis in areas of program optimization and software security analysis.

Module Learning Outcomes

By the end of this module, students are able to

  1. Implement software solutions using functional programming language and applying design patterns
  2. Define the essential components in a program compilation pipeline
  3. Design a compiler for an imperative programming language
  4. Optimise the generated machine codes by applying program analysis techniques
  5. Detect bugs and security flaws in software by applying program analysis techniques

Measurable Outcomes

  1. Develop a parser for an imperative programming language with assignment, if-else and loop (AKA the source language) using Functional Programming
  2. Implement a type checker for the source language
  3. Develop a static analyser to eliminate dead codes
  4. Implement the register allocation algorithm in the target code generation module
  5. Develop a static analyser to identify potential security flaws in the source language

Topics

  1. Functional Programming : Expression, Function, Conditional
  2. Functional Programming : List, Algebraic data type and Pattern Matching
  3. Functional Programming : Type class
  4. Functional Programming : Generic and Functor
  5. Functional Programming : Applicative and Monad
  6. Syntax analysis: Lexing
  7. Syntax analysis: Parsing (LL, LR, SLR)
  8. Syntax analysis: Parser Combinator
  9. Intermediate Representation: Pseudo-Assembly
  10. Intermediate Representation: SSA
  11. Semantic analysis: Dynamic Semantics
  12. Semantic analysis: Type checking
  13. Semantic analysis: Type Inference
  14. Semantic analysis: Sign analysis
  15. Semantic analysis: Liveness analysis
  16. Code Gen: Instruction selection
  17. Code Gen: Register allocation
  18. Memory Management

Resource

The main resources are lecture slides, tutorial sessions, and online documentations. There are no official textbooks. But the following are useful for reference and deeper understanding of some topics.

  1. Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman
  2. Modern Compiler Implementation in ML by Andrew W. Appel
  3. Types and Programming Languages by Benjamin C. Pierce
  4. Static Program Analysis by Anders Møller and Michael I. Schwartzbach
  5. Learn you a Haskell for Great Good! - https://learnyouahaskell.com/

Instructors

  • Kenny Lu (kenny_lu@sutd.edu.sg)
    • Office Hour: Wednesday 3:00-4:30pm (please send email to arrange)

Communication

If you have course/assignment/project related questions, please post it on the dedicated MS teams channel.

Assessment

  • Mid-term 10%
  • Project 35%
  • Homework 20%
  • Final 30%
  • Class Participation 5%

Things you need to prepare

  • If you are using Windows 10 or Windows 11, please install ubuntu subsystems
  • If you are using Linux, it should be perfect.
  • If you are using Mac, please install homebrew.
  • Install Haskell tools
    1. (For Windows WSL2 and Ubuntu only) sudo apt install build-essential libgmp-dev
    2. Install ghcup >= 0.1.30.0 https://www.haskell.org/ghcup/
    3. Install ghc == 9.6.6 (via the ghcup tui command)
    4. Install cabal >= 3.10.3.0 (via the ghcup tui command)
    5. install hls >= 2.7.0.0 (via the ghcup tui command)
    6. Install stack >= 2.15.5 (via the ghcup tui command)
  • IDE: It's your choice, but VSCode works fine.
    1. if you are using VSCode with Windows and Ubuntu WSL2, it is recommended to install the "Remote development" extension by (microsoft.com).
    2. if you are using VSCode, it is recommended to install the "Haskell" extension (by Haskell).
  • You should try test your setup by attempting Homework 1 on your own.

Schedule

Schedule

Project

Project Template

The aim of the project is to apply the techniques and concepts taught in this module to develop a simple compiler for the SIMP language.

You may work as a team (up to max 3 members). Please register your team here.

  • Lab 1 (10%, Deadline - 17 Nov 2024 23:59)
  • Lab 2 (10%, Deadline - 1 Dec 2024 23:59)
  • Lab 3 (15%, Deadline - 15 Dec 2024 23:59)

Submission Policy and Plagiarism

  1. You will do the assignment/project on your own (own teams) and will not copy paste solutions from someone else.
  2. You will not post any solutions related to this course to a private/public repository that is accessible by the public/others.
  3. Students are allowed to have a private repository for their assignment which no one can access.
  4. For projects, students can only invite their partners as collaborators to a private repository.
  5. Failing to follow the Code of Honour will result in failing the course and/or being submitted to the University Disciplinary Committee. The consequences apply to both the person who shares their work and the person who copies the work.

Make Up and Alternative Assessment

Make ups for Final exam will be administered when there is an official Leave of Absence from OSA. There will be only one make up. There will be no make-up if students miss the make up test.