| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Lectures, Sections and Projects

Page history last edited by Joel Galenson 14 years, 3 months ago

CS164 Fall 2009

 

To make these slides more useful to you, send questions and suggestions for revisions to the staff.  Or better yet, add them as comments at the bottom of this page. To add a comment, you need to log in to this web site.  For that, you need to create an account but you don't need any special permission from the course staff.

 

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 parsinggrowing 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: ExamSolutions.    
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 2ExamSolutions.    

 

Upcoming Topics:

 

  • Google Calculator and Beyond: expressions, dynamic typing, simple lazy evaluation, variables, functions, extending a language, structure of the interpreter.
  • Parsing: grammars, ambiguity, and how to write a compiler in 60 minutes.
  • Dynamically typed languages: closures, iterators, coroutines, etc.
  • Objects: inheritance, prototypes, and mixins.
  • Static typing and static analysis
  • Compilation
  • Rolling your own languages
  • Garbage collection 

 

Comments (0)

You don't have permission to comment on this page.