[ General Information
| Lectures
| Handouts
| Other Resources
| Requirements
]
[ Announcements
]
Course description: This course is an introduction to programming language design and implementation. From the design point of view, we will study language features as tools for expressing what and how to compute. From the implementation point of view, we will discuss compilers as tools for mapping language features onto computer hardware. The course will touch on a wide variety of languages, in different programming paradigms. Rather than dwell on the features of any particular language, we will focus instead on the differences between languages, the reasons for the differences, and the implications of the differences. Students will do programming assignments, mostly in Python, to better understand language features. | Prerequisites: CSE219 and CSE220. | Credits: 3.
Instructor: Annie Liu, liu AT cs DOT sunysb DOT edu, Computer Science 1433, 632-8463. | Office hours: by appointment (send email), or stop by any time I'm around.
TA: Dengpan Zhou, dpzhou AT cs DOT sunysb DOT edu. | Office hours: Friday 12:30-2:30PM, Computer Science 1207.
Lectures: Tue Thu 9:50-11:10AM, in E&SSCI 069.
Textbook: Programming Language Pragmatics by Michael Scott. Second Edition, Morgan Kaufmann Publishers, 2006. This is an excellent recent textbook that covers both language design and implementation.
Grading: Assignments, quizzes, a midterm, and a final, worth 40%, 10%, 20%, and 30%, respectively, of the grade. Extra credit work will be given as appropriate. Partial credit will be given for partial work. Reduced credit for late assignments, 25% off per day.
Course homepage: http://www.cs.sunysb.edu/~liu/cse307/
Lectures
Lecture 1 (01/23/07): Introduction. What, why,
and how of the course, spectrum of programming languages, compilation
and interpretation, programming environments. Reading: Ch.1. Assignment 1.
Lecture 2 (01/25/07): An overview of compilation (after review
and refinement, and Quiz 1). Compiler phases, examples for scanning
and parsing. Reading: Ch.1.6-7.
Lecture 3 (01/30/07): Syntax. Regular expressions,
scanning, deterministic finite automata, from RE to NFA to DFA to
minimum-state DFA. Reading: Ch.2.1-2.
Lecture 4 (02/01/07): Context free-grammars, parsing,
LL/top-down/predictive parsers and FIRST/FOLLOW/PREDICT sets,
LR/bottom-up/shift-reduce parsers. Reading:
Ch.2.3-5.
Lecture 5 (02/06/07): Python. To learn a new language
yourself, first read its tutorial, then browse its library; if you
need to know anything more formally, look up its manual. Reading: Python Tutorial. Assignment 2.
Lecture 6 (02/08/07): Python (after Quiz 2). Key features:
dynamic and higher-level, basic data types and statements, high-level
data types and expressions. Reading: Python
Library.
Lecture 7 (02/13/07): Semantics (after review and
refinement). Semantics analysis motivations, attribute grammars and
attribute evaluation by examples. Reading:
Ch.4.1-3.
Lecture 8 (02/15/07): S-attributed and L-attributed grammars,
action routines, building syntax tree, tree grammars, type checking,
code generation (to finish). Reading:
Ch.4.4-7,14.3.1.
Lecture 9 (02/20/07): Names. Binding times,
object lifetime and static/stack/heap storage management, static
scoping and dynamic scoping. Reading: Ch.3.1-3.
Assignment 3.
Lecture 10 (02/22/07): More scopes and bindings (after review
and refinement, and Quiz 3). Rules for declarations, referencing
environments, aliasing, overloading, polymorphism. Reading: Ch.3.3-8.
Lecture 11 (02/27/07): Python (after more about
names and about evolution of data abstraction mechanisms). Python
review, more basics, classes (to finish). Reading:
Python Tutorial.
Lecture 12 (03/01/07): More Python (guest lecture by Tom
Rothamel). Classes and methods, everything as objects, properties,
reflection, modules, generators. Reading: Python
Tutorial.
Midterm exam (03/06/07): In class. You can prepare one
hand-written personal "crib sheet".
Lecture 14 (03/08/07): Control flow. Expression
evaluation, variables as values vs as references, assignment, side
effects, sequencing, selection. Reading: Ch.6.1-4.
Assignment 4.
Lecture 15 (03/13/07): Lecture 15 (03/13/07): Iteration,
logically-controlled, enumeration-controlled, iterators, recursion,
tail recursion, concurrency and nondeterminacy (to finish). Reading: Ch.6.5-8.
Lecture 16 (03/15/07): Data types. Strong
typing, static vs dynamic typing, type checking, equivalence and
compatibility, ML type inference and polymorphism (to finish). Reading: Ch.7.1-2.
Lecture 17 (03/20/07): Types. Records/structs,
variants/unions, arrays, sets, pointers and recursive types, garbage
collection, C pointers and arrays. Reading:
Ch.7.3-11.
Lecture 18 (03/22/07): Control abstraction and functional
languages. Subroutines, calling sequence, parameter passing
mechanisms, call-by-reference/value/name, exception handling (to
finish). Reading: Ch.8.
Lecture 19 (03/27/07): Functional languages. Functional
programming concepts, Scheme overview, evaluation order, higher-order
functions, lambda calculus (to finish). Reading:
Ch.10.
Lecture 20 (03/29/07): Data abstraction and
object-oriented languages. Evolution of data abstraction,
encapsulation and inheritance, initialization and finalization (to
finish). Reading: Ch.9.1-3. Assignment
5.
Spring break: April 2-6.
Lecture 21 (04/10/07): Dynamic method binding, subtype
polymorphism, implementation of classes, multiple inheritance, summary
of features (to finish). Reading:
Ch.9.4-7.
Lecture 22 (04/12/07): Logic languages. Logic
programs and Prolog, logic programming, database programming,
recursive programming (to finish). Reading: Ch.11.1-2.
Assignment 6.
Lecture 23 (04/17/07): Logic program semantics, implementation,
and efficiency. Goal directed search, unification, negation, cut,
tabling, graph reachability, transitive closure, misc (to finish).
Reading: Ch.11.2-5.
Lecture 24 (04/19/07): Scripting languages.
Common characteristics, problem domains: shell commands, text
processing and report generation, glue, general purpose. (postponed)
Reading: Ch.13.1-2.
Lecture 25 (04/24/07): Extension languages, web scripting,
innovative features: scoping rules, string pattern matching,
high-level data types, object orientation (to finish). Reading: Ch.13.3-5.
Lecture 26 (04/26/07): Concurrency. Process and
thread creation, mutual exclusion vs conditional synchronization,
shared memory, busy wait vs scheduler. (postponed) Reading: Ch.12.1-3. Assignment 7.
Lecture 27 (05/01/07): Scheduler-based synchronization,
semaphores vs monitors vs conditional critical sections, message
passing, no wait vs synchronization vs remote invocation. Reading: Ch.12.3-5
Lecture 28 (05/03/07): Final review. Basic concepts and techniques, sample problems and
solutions.
Final exam (05/15/07): 8:00-10:30AM, in our classroom. You can
prepare two hand-written personal "crib sheets".
Q2: Questionnaire 2
A1: Assignment 1: Comparing languages ---
Reading tables
A2: Assignment 2: Syntax checking ---
Matching patterns
A3: Assignment 3: Semantic analysis ---
Inferring types
A4: Assignment 4: Control abstraction ---
Writing queries
A5: Assignment 5: Object abstraction ---
Organizing everything
A6: Assignment 6: Logic programming ---
Adding power
A7: Assignment 7: Building interfaces ---
Showing off, or Doing something different (Extra credit)
Q1: Quiz 1
Q2: Quiz 2
Q3: Quiz 3
Q4: Quiz 4
Q5: Quiz 5
M1: Preparation for Midterm Exam
M2: Midterm Exam
M3: Solutions to Midterm Exam
F1: Preparation for Final Exam
F2: Final Exam
F3: Solutions to Final Exam
Prof. Michael Scott's course on Programming Language Design and Implementation
CS Undergraduate Computing Lab (The ug server is public.ug.cs.sunysb.edu)
Google Directory for Programming Languages
GNU C/C++ (Documentation): run /usr/local/bin/g++ or /usr/local/bin/c++ on the ug server
Java (Documentation): run /usr/local/bin/javac and /usr/local/bin/java on the ug server
SML/NJ (User's Guide): run /usr/local/bin/sml on the ug server
Python (Documentation: Tutorial, Library Reference, Reference Manual): run /usr/local/bin/python on the ug server
XSB (Programmers' Manual, Libraries etc): run /raid2/h/cse307/xsb/XSB/config/i386-unknown-freebsd4.3/bin/xsb on the ug server
Learn all information on the course homepage. Check the homepage periodically for Announcements. Use Blackboard for additional communications, including in particular assignment handins and discussions.
Attend all lectures and take good notes. I will start promptly on time, if only to be fair to people who come on time. We will start with quizzes from time to time. I will have students form groups to participate in problem solving in the class. We will discuss materials not in the textbook from time to time.
Do all course work. The readings are mainly to help you preview and review the materials discussed in the lectures. The assignments are to provide concrete experiences with the basic concepts and methods covered in the lectures. The quizzes are to help check that you are keeping up with the lectures and the assignments. The exams will be comprehensive.
Ask questions and get help. Ask questions in class, visit the TA during office hours, and visit the professor with any remaining questions. Talk with your classmates, and share ideas (but nothing written or electronic).
Academic honesty: All assignments, quizzes, and exams must be done individually, unless specified otherwise. You may discuss ideas with others and look up references, but you must write up your solutions independently and credit all sources that you used. Any plagiarism or other forms of cheating discovered will have a permanent consequence in your university record.
Disability: If you have a physical, psychological, medical or learning disability that may have an impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133 Humanities, 632-6748/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.