[ 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. | Official description.
Instructor: Annie Liu, liu@cs.sunysb.edu, Computer Science 1433, 632-8463. | Office hours: Tue 9:50-11:20AM, Fri 3:30-5:00PM, by appointment (send email), or stop by any time I'm around.
TA: Yury Puzis, ypuzis@cs.sunysb.edu, yury.puzis@gmail.com. | Office hours: Tue 12:50-14:10PM, Wed 8:20-10:00AM, Computer Science 2110.
Lectures: Tue Thu 11:20AM-12:40PM, in CS 2311.
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/29/09): An overview of compilation (after Quiz
1). Compiler phases, examples for scanning and parsing. Reading: Ch.1.6-7.
Lecture 3 (02/03/09): 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/05/09): Context free-grammars, parsing,
LL/top-down/predictive parsers and FIRST/FOLLOW/PREDICT sets,
LR/bottom-up/shift-reduce parsers (to finish). Reading:
Ch.2.3-5.
Lecture 5 (02/10/09): Python (after finishing
parsing). Key features: dynamic and higher-level, basic data types,
statements, defining functions. Reading: Python
Tutorial. Assignment 2.
Lecture 6 (02/12/09): Python (after Quiz 2). High-level data
types and operations, comprehension, basics of classes and objects.
Reading: Python Library.
Lecture 7 (02/17/09): Semantics. Static
semantics analysis motivations, attribute grammars and attribute
evaluation by examples. Reading:
Ch.4.1-3.
Lecture 8 (02/19/09): 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/24/09): Names (after finishing
semantics). Binding times, object lifetime and static/stack/heap
storage management, static scoping and dynamic scoping (to finish).
Reading: Ch.3.1-3. Assignment 3.
Lecture 10 (02/26/09): More scopes and bindings. Declaration
order, referencing environment, aliasing, overloading,
ad-hoc/subtype/parametric polymorphism, evolution of abstractions.
Reading: Ch.3.3-8.
Lecture 11 (03/03/09): Python (after Quiz 3).
More basics and uniformity, more classes and methods, everything as
objects, reflection, generators. Reading: Python
Tutorial.
Lecture 12 (03/05/09): Midterm review. Studying methods for
describing and implementing language syntax and semantics, studying
language features and comparing languages. Reading:
Handout M1.
Midterm exam (03/10/09): In class. You can prepare one
hand-written personal "crib sheet".
Lecture 14 (03/12/09): Control flow. Expression
evaluation, variables as values vs as references, assignment, side
effects, sequencing, selection (to finish). Reading:
Ch.6.1-4. Assignment 4.
Lecture 15 (03/17/09): Iteration, logically-controlled,
enumeration-controlled, iterators, recursion, tail recursion,
concurrency and nondeterminacy. Reading:
Ch.6.5-8.
Lecture 16 (03/19/09): Data types (after Quiz 4).
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/24/09): Types (next time). Records/structs,
variants/unions, arrays, sets, pointers and recursive types, garbage
collection, C pointers and arrays. Reading:
Ch.7.3-11.
Lecture 18 (03/26/09): Control abstraction and functional
languages. Subroutines, calling sequence, parameter passing
mechanisms, call-by-reference/value/name, exception handling. Reading: Ch.8.
Lecture 19 (03/31/09): Functional languages. Functional
programming concepts, Scheme overview, evaluation order, higher-order
functions, lambda calculus (to finish). Reading:
Ch.10.
Lecture 20 (04/02/09): Data abstraction and
object-oriented languages (after Quiz 5). Evolution of
abstractions, encapsulation, inheritance, initialization and
finalization (to finish). Reading: Ch.9.1-3.
Assignment 5.
Spring break: April 6-10.
Lecture 21 (04/14/09): Dynamic method binding, subtype
polymorphism, implementation of classes, multiple inheritance, summary
of features. Reading: Ch.9.4-7.
Lecture 22 (04/16/09): Logic languages (after
Quiz 6, bonus). Logic programs and Prolog, logic programming,
database programming, recursive programming. Reading: Ch.11.1-2. Assignment 6.
Lecture 23 (04/21/09): Logic program semantics, implementation,
and efficiency. Goal directed search, unification, negation, cut,
tabling, graph reachability, transitive closure, misc. Reading: Ch.11.2-5.
Lecture 24 (04/23/09): Scripting languages.
Common characteristics, problem domains: shell commands, text
processing and report generation, glue, general purpose.
Reading: Ch.13.1-2.
Lecture 25 (04/28/09): Extension languages, web scripting,
innovative features: scoping rules, string pattern matching,
high-level data types, object orientation. Reading:
Ch.13.3-5.
Lecture 26 (04/30/09): Concurrency. Process and
thread, shared memory vs message passing, race condition and
synchronization, mutual exclusion vs conditional synchronization, busy
wait vs scheduler, languages and features. Reading:
Ch.12. Assignment 7.
Lecture 27 (05/05/09): Final review. Review of topics covered
and emphasis, basic concepts and techniques, sample problems and
solutions. Reading: Handout F1.
Lecture 28 (05/07/09): Final review. Complete solutions to
sample problems. (Presented by Yury, our TA.)
Final exam (05/14/09): 11:00AM-1:30PM, in our classroom. You
can prepare two hand-written personal "crib sheets".
QQ: Questionnaire 2
A1: Assignment 1: Comparing languages ---
Reading facts
A2: Assignment 2: Syntax analysis ---
Parsing rules
A3: Assignment 3: Semantic analysis ---
Analyzing names
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 extras ---
Showing off (Extra credit)
Q1: Quiz 1
Q2: Quiz 2
Q3: Quiz 3
Q4: Quiz 4
Q5: Quiz 5
Q6: Quiz 6
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
Google Directory for Programming Languages
CS Undergraduate Computing Lab (The ug server is public.ug.cs.sunysb.edu)
GNU C/C++ (Documentation): run /usr/bin/g++ or /usr/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, Standard Library, Language Reference): 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 every student participate in solving problems and presenting solutions in 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. For more comprehensive information on academic integrity, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/
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.