COS Independent Work Seminar:
Programs Generating Programs

COS IW09
Fall 2018

General Information:

 Instructor: Aarti Gupta, CS Building 220, 258-8017, aartig at cs dot princeton dot edu
      Office Hours: Mon 4:00-5:00 pm, Tues 3:00-4:00 pm

Teaching Assistant: Zachariah Cohen, zacohen at princeton dot edu

Meeting time and place: Thursday, 11:00 am - 12:20 pm, CS 401

Links: Description, Schedule, Resources, FAQ, Piazza
 

Description:

Do you wish sometimes that programs would just write themselves? Wouldn’t it be great if you could somehow say what a program should do, sketch a program outline, but the rest would get automatically generated? While this is difficult to do for Java and C programs (and COS 126/217/226 programming assignments!), it is quite possible in domain-specific languages for a variety of applications. Indeed, automated synthesis of programs is an active area of research in programming languages and formal verification. Available tools aim at automatically generating programs by filling in holes in a partially-complete program sketch or by using input-output examples, optionally using grammar rules that define the underlying search space of candidate programs.

Participants in the seminar will choose from a range of program synthesis domains and applications, or choose one of their own interest. Examples include automatic parallelization of array-handling programs, obfuscation/de-obfuscation of high-security code, automatic repair of security bugs through bit-twiddling, etc. They will use available synthesis tools (such as Rosette, Sketch), design their own libraries of program sketches, specify the correctness requirements, and experiment with different synthesis strategies to generate a variety of target programs. Those interested in backend techniques can also design and implement new synthesis strategies using SMT (Satisfiability Modulo Theory) solvers that perform the search and verification in these tools.
 

Schedule:

 The schedule may change during the semester. Please check it frequently.
Orange rows are mandatory meetings and obligations for all IW students.
 
Date Topic Notes and References
Sep 13 Introductions and Background Background Papers: [B1] [B2] [B3]
Sep 13 Information meeting for all IW students Andlinger Center, Maeder Hall, Room 002, 4:30-5:30pm
Sep 20 Background and Tools Synthesis Tools: [T1] [T2] [T3]
Sep 27 Tools and Project Ideas
Oct 03 Written project proposals due
Oct 04 Proposal talks
Oct 11 Proposal talks
Oct 18 Progress reports, discussion, and feedback
Oct 22 Submit Checkpoint Form
Oct 25 Progress reports, discussion, and feedback
Nov 01 Fall recess, no class
Nov 08 Status update
Nov 12 Attend "How to Give an IW Talk" 4:30pm, Location: TBD
Nov 15 Status update
Nov 22 Thanksgiving, no class
Nov 27 Attend "How to Write an IW Paper" 4:30pm, Location: TBD
Nov 29 Practice Talks w. Demos
Dec 06 Practice Talks w. Demos
Dec 10-14 Oral Presentations
Jan 08 Written final report due
Jan 09 Submit poster
Jan 10 Poster session for all IW students 9am-4pm, Friend Center, Convocation Room

 

Resources:
 

Frequently Asked Questions: