Published using Google Docs
Web Page for CSE501 wi19
Updated automatically every 5 minutes

     

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 and its applications in compilation and programming by demonstration.

The primary goal of the course is for students to design an independent project. They select a problem and develop a language addressing this problem, together with a compiler for the language.  

Course format

This is a project oriented course that also comes with a substantial foundational material. A lot of material will be learnt in programming 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):

Homeworks

Final project

Participation

20%

60%

20%

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

Sections

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

  • HW1: Describe a DSL in a one-minute slide (handout). Due: Jan 11, 9:55am.
  • Milestone 1: instructions are in the shared slide deck
  • Milestone 2: handout, useful reading: Programming Paradigms, When and How to Develop DSLs
  • Milestone 3: the interpreter and samples of AST, IR, generated code.
  • Milestone 4: the encoding of your verification or synthesis in Z3py or scalaZ3.  Due Thursday 3/7.
  • Milestone 5: handout, Friday 3/15, classroom presentations including a demo.
  • Report: handout, Wed 3/20
     

Lectures

L1: Motivation and Logistics 

L2: Embedding languages in a host language

  • Student 1-minute presentations on a DSL.
  • Embedding DSLs into a host language.
  • Slides: pdf, sources for Logic DSL: link

L3: Technical overview

  • Technologies covered in 501.
  • How to leverage them in student projects.

L4: Student Presentations

  • Student present proposals for their DSL designs.

L5: Abstraction design

  • How to design domain abstractions. "Discovering" regexes.
  • Review of grammars.
  • The recursive descent parser.
  • How to hide the plumbing of this parser (continued in L7).

L6: Automatic programming

  • Verification, synthesis, partial evaluation.
  • From a checker to a synthesizer for free.
  • From an interpreter to a compiler for free.

L7: Parser combinators

  • Reading: a chapter on combinator parsing

L8: Generative programming (paper)

  • Semiquoting.
  • Partial evaluation.
  • Staging.

L9: Query engine (paper)

  • Query interpreter (push-style)
  • Staging the interpreter

L14: The Lift Language (Michel Steuwer) (paper, slides)

  • Generating Performance Portable Code using Rewrite Rules

L15: Halide (paper)

  • Separating the specification and the schedule

L18: Probabilistic Programming Languages (paper, slides)

  • Generating Performance Portable Code using Rewrite Rules

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.

Week

Mon

Tue

Wed

Thu

Fri

1


Jan 9
L1: Overview

11  HW1 due
L2: Embed...

2


Jan 16
L3

Jan 18
Milestone 1

HW2 shared slide deck

3

Jan 23

L5 (.pdf)

L5 (.pptx)


Jan 24

L6 (.pdf)
L6 (.pptx)

4

Jan 30
L7 (.pdf)
L7 (.pptx)

Feb 1
Semiquoting, partial evaluation, staging. Paper, slides L8 (pdf), (pptx)

Milestone 2 due

5


Feb 6

Query engine with LMS. Paper, disc. slides: L9 (pdf), (pptx)

Feb 8

6

Feb 13

Feb 15

SAT SMT by example

7


Feb 20

Feb 22
Milestone 3 due

8

Feb 27

March 1

Milestone 4

9

March 6

March 8

Milestone 4 due.

10

March 13

March 15
Demos!

Exams

There will be no exams. The poster and demo will replace the final exam and will happen on the last day of class.

Recommended Resources

Books:

  • Programming in Scala, Third Edition (1st edition is online)
  • DSLs, by Fowler and Parsons
  • [check later for more books]

Courses:

  • Stanford course on DSLs (cs448h)

Blogs and papers:

Staff and Communication

  • Instructor: Ras Bodik, OH by appointment (in Gates 243)
  • TA: Tam Minh Dang, OH: 3:30pm - 4:30pm, Tuesday (in Gates 152)