This is the home page for Computer Science 652, Graduate Programming Languages, at the University of San Francisco. This course is all about implementing programming languages.
Spring 2011: 2:15pm - 3:20pm MWF in COWELL 312
Last day of class: Wednesday May 11, 2011
Midterm exam: March 11, 2011
2nd midterm exam: Wednesday May 11, 2011
Materials for this class assume ANTLR v3.3 and StringTemplate 3.2.1 or above
Textbook is Language ImplementationPatterns (LIP):
You'll also find The Definitive ANTLR Reference (TDAR) useful.
No laptops are allowed in my lectures ('cept mine)
Because programming languages are at the core of writing software, programmers should have a thorough understanding of how languages are designed, implemented, and manipulated. This course concerns itself specifically with the implementation and translation of computer languages, leaving an in-depth study of language design to another course. Students will learn the formalisms behind computer languages, but the focus will be on developing the ability to build languages and their translators.
This class can be challenging conceptually. Some of the language formalisms take a while to sink in. Well, actually you have one major hurdle to get over and then it's easy--abstraction in the sense of recursion, meta-language, programs that generate other programs (or even themselves), etc... If you get a headache when you try to figure out how the first C compiler could have been written in C, you might invest in a big bottle of aspirin.
Students are required to build projects in Java unless specified otherwise. You should have a good understanding of data structures, algorithms, and recursion. Prior experience with language implementation is helpful, but not required. You will be expected to write a lot of code this semester, culminating in a complete programming language implementation.
Two graduate classes is considered full-time at USF and, hence, you can expect this class to require about 20 hours/week of class time and homework/development time. You should start early on every project. Note that there is no such thing as a late project. Late projects get a 0 grade as I will be handing out the solutions the day projects are due.
By the end of this course, you will have implemented a complete programming language. The lecture flow will lead you through all of the formalisms and techniques you'll need and we'll closely follow the chapter sequence in the textbook for the first part of the semester. For the Spring 2011 semester, we're going to build a bytecode compiler and interpreter for SmallTalk. The main tasks are:
- parser and AST constructor
- bytecode generator
- bytecode interpreter
- SmallTalk primitives and runtime support
After the first stage, you will all start from my solution for the subsequent stages. This will show you what a proper implementation looks like and prevents a single bad stage from killing your chances of success on the remaining stages.
Student Learning Outcomes
At the end of this course, you will
- be familiar with the evolution of programming languages
- be able to build NFA, DFA, and related state machines
- understand the nature and structure of language
- be able to build symbol tables and intermediate representations
- be able to build lexers and parsers by hand and via ANTLR
- be able to describe how object-oriented languages implement inheritance, polymorphism, encapsulation, and data-hiding
- be very comfortable with grammars and parsing
- know how to build source to source translators
- be able to build a programming language to bytecode compiler
- be able to implement a bytecode interpreter
In short, you will be able to intelligently discuss the implementation and translation of programming languages and will have built a nontrivial programming language.
- The evolution of programming languages
- The difference between compilers and interpreters
- Chapter 2: The nature of computer languages (TDAR)
- Chapter 1: Language applications cracked open (LIP)
- Grammars, languages, derivations, parsing
- regular vs context-free languages
- DFA/NFA, lookahead for predictive parsers
- Basic parsing patterns
- Resources: LL Parsing and recursive descent design pattern, 11.1-11.4 from ANTLR reference
- Grammar to Recursive-Descent Parser Mapping
- Recursive-descent Lexer
- Canonical LL(1) Recursive-Descent Parser
- LL(k) Recursive-Descent Parser
- Advanced parsing patterns
- ANTLR introduction: Chapter 3 from ANTLR reference
- Ambiguities and Nondeterminisms: Section 11.5 from ANTLR reference
- Using semantic and syntactic predicates: Chapter 12 from ANTLR reference (required reading: Chapters 13, 14 from ANTLR reference)
- gUnit - Grammar Unit Testing
- Building Intermediate Form Trees
- Walking and Rewriting Trees
- Tracking and Identifying Program Symbols
- Managing Symbol Tables for Data Aggregates
- Enforcing Static Typing Rules
Translation and generation
- Translating Computer Languages; syntax directed, rule-based, model driven
- Generating DSLs with Templates
- Building High-Level Interpreters
- Building Bytecode Interpreters; stack, register
- PostScript case study
- Memory allocation and garbage collection
- Implementing Polymorphism
Lexer for XML 2% Due Jan 31, 2011
Build a lexer for XML that separates tags from text.
Parsing Graphviz DOT files the hard way 4% Due Feb 7
Build a lexer and parser by hand that checks DOT files for correct syntactic structure.
Calculator using ANTLR 3% Due Feb 14
Build ASTs 3% Due Feb 21
Symbol table for statically-typed language 5% Due Feb 28
PostScript interpreter 3% Due Mar 7
SmallTalk grammar and AST construction 10% Due March 30
SmallTalk bytecode compiler 15% Due April 20
SmallTalk interpreter 20% Due May 11
There are no late projects and incomplete features do not count.
All projects will be graded and must run under UNIX. Projects will be graded interactively and may require students to meet with the instructor outside class.
All projects must be submitted in SVN. For example, here is how I would create my cs652 directory:
You might find these svn notes useful. Projects will be placed in subdirectories of cs652 wherever you place it on your disk. E.g., you need to create the following directories:
See the individual project descriptions for more information about what files must be present to submit a project.
There will be two written exams. The midterm exam is on March 11, 2011.
Your grade will be computed according to the following relationship:
15% Exam 1
15% Exam 2
5% Class participation
20% Weekly projects
45% Smalltalk projects
I consider an "A" grade to be above and beyond what most students have achieved. A "B" grade is an average grade or what you could call "competence" in a business setting. A "C" grade means that you either did not or could not achieve competence. An "F" grade implies you did very little work or had great difficulty with the class compared to other students.
Warning: you lose 10% of your grade if you do not provide a jar file that I can run exactly as I specified in various projects. common mistakes are: jar has wrong name, upper or lowercase difference, missing class files, improperly named Java classes. To communicate effectively, programmers must be incredibly precise. in order to work with other programmers, you must be able to spell, provide the right jar files, and know the difference between upper and lower case. shockingly, lots of students get this wrong.
Unless you are sick or have a family emergency, I will not change deadlines for projects nor exam times. For example, I will not give you a special final exam just because you want to fly home early. Consult the university academic calendar before making travel plans.
Attendance is part of your grade. Even if you know this subject well, I will be providing a number of anecdotes from industry and other goodies during my lectures. Anything I say in class is fair game for an exam
Tardiness. Please be on time. It's very disruptive for you to come in late and you could miss vital information.
Academic honesty. You must abide by the copyright laws of the United States and academic honesty policies of USF. If told you may for a particular project, use any code from the net that you find as long as it does not violate the software's license. You may not borrow code from other current or previous students. All suspicious activity will be investigated and, if warranted, passed to the Dean of Sciences for action.
Twitter. You must all follow @cs652 for news, hints, etc...
- smalltalk cheat sheet
- Squeak by example
- Lots of free smalltalk books
- Smalltalk-80: The Language and its Implementation
- A little Smalltalk
- Tim Budd's Java implementation of "a Little Smalltalk"
- "Simple" smalltalk implementations
- Overview of GNU Smalltalk syntax
- Paper describing GNU Smalltalk implementation
- Dan Ingalls on the History of Smalltalk and the Lively Kernel