Date |
Topic |
Materials |
Notes |
Overview. Why take cs164? |
|
|
8/26 |
Section 1: HTML, DOM, JavaScript, Regular Expressions and Greasemonkey |
|
|
8/27 |
Lecture 1: Why take CS164? Examples of small languages designed by mortals. History and trends in programming languages. Factors driving design of new languages. |
pdf ppt
|
Google Calculator,
jQuery,
Max/MSP,
The Guitar Zeros,
rfig
|
String processing |
|
|
9/1, 9/3 |
Lecture 2: These are preliminary slides on string processing languages (regular expressions, compilations to NFA, expressivity of regular expressions and regexes, backtracking vs NFA, testing primality with regexes). Once we cover the last topic (regular expressions vs regex on the search problem), these slides will be updated to reflect our discussions during the lectures. |
ppt pdf |
|
9/2 |
Project 1: Meta-programming with JavaScript and Regular Expressions using Greasemonkey
|
|
due Thu Sep 10, noon |
9/2 |
Section 2:Regular expressions, NFAs, and DFAs |
|
|
9/8 |
HW1: Find a bug in the Eclipse command line processing language. Understand why NFAs can be much faster than backtracking regex engines. |
Solutions |
|
Designing a small language (Unit Calculator) |
|
|
9/8, 9/10 |
Lecture 3: Design and development of the unit calculator. Expressions, concrete vs abstract syntax, recursive descent interpreter, types of values, type representation, unit conversion, ....
Section 3 (9/9): developed SI units, non-SI units, and canonization.
|
ppt pdf
snapshots of code we developed
|
|
Building a parser |
|
|
9/16,9/17 |
Section: On why regular expressions are sometimes not powerful enough, for example to parse a regular expression (that contains parentheses) and expose its hierarchical structure. To work around the limitations of regular expressions, we wrapped them in a recursive procedure, and that gave us our first parser. This is a top-down parser. The code is here.
|
code |
|
9/17 |
Lecture: Grammars, their languages, their strings, their derivations. And ambiguity. Plus syntax-directed translation. |
pdf |
|
9/24,9/25 |
Section: Disambiguating a grammar by rewriting it into a grammar that accepts same strings but allows only one parse tree per string. We did this on the famous dangling else problem. Syntax directed translation of regular expressions. Using the parser generator that you will develop in project 2, we translated them back to the original string, to an AST, to a graphviz file that displays the AST and to the graph that shows Ken Thomspon's compilation of regular expressions to NFAs. Code for all variants is included. |
notes with links to code |
|
9/22 |
Lecture: top-down parsing |
|
|
9/24 |
Lecture: Bottom up parsing: growing the parse tree from the string. A suitable representation for this reduction process. CYK parser and its inefficiencies. Earley parser: allow only reductions that may end up in a tree. Disambiguation with parser directives. |
pdf |
|
9/29 |
Project 2 - Grammar Parser |
|
|
9/30,10/1 |
Section: Earley parsing. We worked through some examples and developed some extra parts of the algorithm. The uploaded notes walk through the examples and contain lots of pictures. |
notes |
|
Building control abstractions |
|
|
10/1 |
Lecture. Function as an abstraction, first-class functions, scoping, higher-order functions, control abstractions. Coroutines (Sections 9.1 and 9.3). |
snapshot of slides from lecture |
|
10/07,10/08 |
Section: Started writing a parser for a language like the one presented in lecture. We began supporting simple arithmetic, then added variables, then added functions. We used lambdas so that we could treat functions like other variables. |
grammar, interpreter, wrapper, sample input |
|
10/14,10/15 |
Section: Scoping and coroutines. We talked a bit dynamic vs. lexical scoping and how to implement the latter. We then worked through an example of using coroutines to implement a regular expression matcher. |
notes |
|
Midterm 1 |
|
|
10/20 |
Sample exams: Unfortunately, solutions to other exams existed only in hardcopy. I encourage students to work out the solutions and post them as comments on this page.
|
|
|
10/20 |
Midterm 1: Exam. Solutions. |
|
|
Data Abstractions |
|
|
10/27,29 |
Lecture 1. Objects; implementation with closures and hashes. Modules. Operator overloading.
Lecture 2: Objects and prototypes; implementation with metatables. Prototype-based inheritance.
we also spent quite a bit of useful time brainstorming on how to design the base language that would be sufficient for desugaring S -> E.ID = E and E -> E.ID .
|
Lecture 1 (pdf)
Lecture 2 (pdf)
Further notes
|
|
10/28,10/29 |
Section: Project 3 preparation. We reviewed how our bytecode interpreter works and discussed how to implement advanced features like coroutines. |
|
|
11/04,11/05 |
Section: Inheritance and the visitor pattern. We first reviewed inheritance and the difference between static and dynamic dispatch. We then motivated and developed the visitor pattern. We showed how and why it is different in Java and Python, discussing the difference between overriding and overloading along the way. Finally, we briefly discussed multiple dispatch and pattern matching. |
notes |
|
Small Languages (Final Project)
|
|
|
11/3 |
Lecture: Discussion of problem domains where a small language can help. Implementation of small languages (internal vs. external Domain-Specific Language).
|
|
|
11/5 |
Protovis: Guest Lecture by Jeff Heer (Stanford) |
slides open title.html |
|
11/5,10 |
Lecture: Three build Languages. |
make
rake
memoize
|
|
11/11 |
HW3 (final project proposal): pick a problem and develop an initial design of your final project language |
due 11/20 |
|
11/10 |
Lecture: implementing languages with method chaining |
|
|
11/12 |
Section: Project 3 milestone 2 preparation. We discussed how to implement inheritance and Python-164 interoperability. |
notes |
|
11/12 |
Compiling Max: Guest Lecture by David Zicarelli (Cycling 73) |
|
|
11/18,11/19 |
Section: Method chaining. We developed method chaining as a technique for building ASTs without writing a grammar. |
notes |
|
Static Types |
|
|
11/19 |
Lecture: static types, dynamic types, name analysis, type checking |
|
|
11/24 |
Lecture: static types for object-oriented programs; type safety; the invariant maintained by safety checks; the need for dynamic checks; static typing for arrays. |
notes |
|
11/25 |
Section: We discussed the need for dynamic type checks for arrays in Java. We saw how the absence of such checks could lead to security vulnerabilities. Finally, we saw that even a perfectly correct language and implementation could still be vulnerable to such attacks. |
notes |
|
Second midterm exam |
|
|
|
Sample exams: Focusing on practical language design, after the first midterm, we have covered much less material than in previous years. Hence few previous exams are appliacable this semester.
- fa07.final: Ignore all but question 2
- fa07.2 (
ignore focus on Problem 2)
- sp07 (ignore Part 1 of Problem 4);
Study lecture notes and section notes.
The lecture on tuesday will be a review lecture, as will be the discussions on Wed and Thursday.
Topics for the exam.
|
|
|
12/3 |
Midterm 2: Exam. Solutions. |
|
|
Comments (0)
You don't have permission to comment on this page.