CSE 501: Implementation of Programming Languages
Winter 2019, WF 10:00am-11:20pm, SIG 230
What you will learn
Programming languages bridge two levels of abstraction: (i) the world of the programmer who uses concepts of his domain, such as graphs or matrices, and (ii) the world of the computer, which prefers abstractions that can be efficiently executed, such as arrays, threads, and remote procedure calls.
We will focus on domain-specific languages (DSLs), such as Halide, Tensorflow, and Rx.
This course will teach you how to design and implement a programming language. We will use advanced frontend methods, such as metaprogramming and staging, and advanced backend methods, such as constraint-based optimization and program synthesis.
We will also learn about program synthesis, its role in implementing and synthesizing DSL and interactive programming such as programming by demonstration.
The primary goal of the course is to an independent project in which students select a problem and develop a language addressing this problem, together with a compiler.
This is a project oriented course that also comes with a substantial foundational material. A lot of material will be learnt in programing homeworks, while some will only be touched on in lectures and sections. The lectures will be interactive.
Grade breakdown (tentative; will be adjusted in response to relative sizes of homeworks and projects):
Syllabus and Lecture materials
Frontend: metaprogramming, staging, partial evaluation, lifting, continuation-passing style, syntactic sugar
Program transformations: instruction selection (the Denali superoptimizer), polyhedral transformations, schema-based transformations (Spiral), auto-differentiation
Intermediate representations and programming models: functional programming for deep nets, dataflow, futures, SSA
Program synthesis: superoptimization, enumeration/dynamic programming, version-space algebra, symbolic, genetic/stochastic, gradient-based gen and test
Code generation: mapping software to hardware, software pipelining, fusion and tiling
Case studies: Halide, Spiral, Denali, Scala LMS
This is a graduate course without sections. Please visit the staff during office hours if you want to clarify anything about the material. We are passionate about the material and will happily answer your questions.
Homeworks and Project Milestones
L1: Motivation and Logistics
L2: Embedding languages in a host language
L3: Technical overview
L4: Student Presentations
L5: Abstraction design
L6: Automatic programming
L7: Parser combinators
L8: Generative programming (paper)
L9: Query engine (paper)
L15: Halide (paper)
L19: Implementing PPLs with Continuations ()
L20: Student Presentations
Course project, homeworks, and calendar
The course project will be divided into five milestones. You will design and implement a small language of your choice. Ideally, this project will be in teams of two or three. Contact us if you want to work on a project individually.
The project milestones may include a homework component which will be completed individually.
There will be no exams. The poster and demo will replace the final exam and will happen on the last day of class.
Blogs and papers:
Staff and Communication