Principles of Programming Languages
198:314, Spring 2023
Announcements
- There will be a review session / office hour on Tuesday, May 2, from
11:00am to 12:30pm in CoRE 101.
- Deadline extension for the third programming
project: Tuesday, May 2
- The third programming project has been posted.
- The Seventh homework is now available.
Course Description
This course covers topics in programming languages and compilers such
as parsing techniques with error handling;
attribute grammars and their use in syntax-directed translation; type
systems; models of programming language
semantics (i.e., operational semantics through closure interpreters );
data abstraction; functional, logical, and object-oriented paradigms;
intermediate representations of programs; parallel programming
models; automatic parallelization and vectorization; quantum
computing
Staff
- Ulrich (Uli) Kremer
(uli@cs.rutgers.edu)
Office: CoRE 318
Office hours: CoRE 305 (not my office!), Friday 2:20pm - 4:00pm
- Chun Lau - TA (larryl@cs.rutgers.edu)
Office: CoRE 305
Office hours: Thursday 1:00pm - 3:00pm
- Xinyu Zhang - TA (xz653@scarletmail.rutgers.edu)
Office: CoRE 305
Office hours: Tuesday, 10am - noon
- Zining Fan - TA (zf140@scarletmail.rutgers.edu)
Office: CoRE 305
Office hours: Wednesday, 10:00am - noon
- Abhilash Kolluri - Grader (ak2048@cs.rutgers.edu)
Lectures and Recitations
Lecture Hill 114, 12:10pm - 1:30pm, Tuesday/Friday
- TA Section: 01 - Xinyu
Recitation: SEC-202, Tuesday 7:45pm - 8:40pm
- TA Section: 02 - Chun
Recitation: SEC-203, Tuesday 5:55pm - 6:50pm
- TA Section: 03 - Xinyu
Recitation: SEC-205, Tuesday 4:05pm - 5:00pm
- TA Section: 04 - Chun
Recitation: SEC-205, Tuesday 2:15pm - 3:10pm
Textbooks
- Michael L. Scott (required):
Programming Language Pragmatics, 4th Edition
Publisher: Morgan Kaufmann (Elsevier), printed book ISBN:
9780124104099, eBook ISBN 9780124104778
- Aho, Lam, Sethi, Ullman (ALSU) (New Dragon Book) (suggested):
Compilers: Principles, Techniques, and Tools 2/E (2007)
Publisher: Addison-Wesley, ISBN10: 0321486811, ISBN13: 9780321486813
Note: The Old Dragon Book is also fine.
Aho, Sethi, Ullman (ASU)
Compilers: Principles, Techniques, and Tools (Edition 1986)
Publisher: Addison-Wesley, ISBN10: 0201100886, ISBN13: 9780201100884
Academic Integrity
This course requires that every student adheres to the
Academic Integrity Policy. DO NOT
CHEAT ! If you have any questions whether a particular
activity is considered cheating, talk to the instructor.
You have to make sure that all your project files are read protected.
If you don't know how to do this in Linux, ask your TA. Leaving a
project file unprotected and thereby visible to your fellow students
is considered cheating.
If you need an extension to a project or homework, let the instructor
know as early as possible.
Homework and Project Questions
Please post questions regarding homeworks and projects using
Rutgers's Piazza
system .
DO NOT send homework or project
questions directly to a TA or me. THANKS!
If you have questions of
a more personal nature, please email the instructor with a subject
line starting with cs314: .
You should read the canvas/piazza 314 site at least every other day!
We use Canvas to submit homeworks and publish your grades.
Exams
There will be two midterms and one final exam (common
hours). Please let the instructor as early as
possible if you have a final exam conflict.
Lectures
- January 17, 2023 ---
Lecture 1
Course overview and introduction, a simple rewrite system.
Reading: Scott: Chapter 1
- January 20, 2023 ---
Lecture 2
Syntax vs. semantics, compiler front-end, scanner, lexical analysis,
regular expressions.
Reading: Scott: Chapter 2.1 - 2.2; ALSU: 3.1 - 3.3
- January 24, 2023 ---
Lecture 3
More on regular expressions, table-driven scanners, scanner generators
Reading: Scott: Chapter 2.1 - 2.2 (skip 2.3.3); ALSU: 3.1 - 3.3
- January 27, 2023 ---
Lecture 4
Syntax analysis (parsing), context-free grammars, BNF,
derivations (leftmost, rightmost), parse tree, ambiguity
Reading: Scott: Chapter 2.1 - 2.5 (skip 2.3.3); ALSU: 4.1 - 4.4
- January 31, 2023 ---
Lecture 5
Ambiguity, resolving ambiguity, expression grammars
Reading: Scott: Chapter 2.1 - 2.5 (skip 2.3.3); ALSU: 4.1 - 4.4
- February 3, 2023 ---
Lecture 6
Abstract syntax tree (AST), regular vs. context-free languages, LL(1)
parsing example
Reading: Scott: Chapter 2.3 - 2.5 (skip 2.3.3); ALSU: 4.1 - 4.4
- February 7, 2023 ---
Lecture 7
LL(1) parsing, FIRST and FOLLOW sets
Reading: Scott: Chapter 2.3 - 2.5 (skip 2.3.3); ALSU: 4.1 - 4.4
- February 10, 2023 ---
Lecture 8
More on LL(1) parsing, FIRST and FOLLOW sets examples, parse table, parser skeleton
Reading: Scott: Chapter 2.3 - 2.5 (skip 2.3.3); ALSU: 4.1 -
4.4
- February 14, 2023 ---
Lecture 9
Recursive descent parsing, syntax-directed translation examples
Reading: Scott: Chapter 2.3 - 2.5 (skip 2.3.3); ALSU: 4.1 -
4.4
Scott: Chapter 3.1 - 3.4; ALSU 7.1 - 7.3
ILOC -
an Intermediate Language for Optimizing Compilers: Overview and
its simulator
- February 17, 2023 ---
Lecture 10
More syntax-directed translation examples
Reading: Scott: Chapter 2.3 - 2.5 (skip 2.3.3); ALSU: 4.1 -
4.4
ILOC -
an Intermediate Language for Optimizing Compilers: Overview and
its simulator
- February 21, 2023 ---
Lecture 11
More on project 1; Introduction to imperative programming (C)
Reading: Scott: Chapter 3.1 - 3.2; ALSU 7.1 - 7.3
- February 24, 2023 --- Midterm 1
in class, closed notes, closed book
- February 28, 2023 ---
Lecture 12
C runtime environment, compiling and debugging C programs, pointers, singly-linked list
example, stack and heap, dynamic memory allocation, malloc, free,
things that can go wrong.
Reading: Scott: Chapter 3.1 - 3.2; ALSU 7.1 - 7.3
An introduction to
programming in C can be found through this link. There is an online textbook and a
discussion of gdb and valgrind.
- March 3, 2023 ---
Lecture 13
Dynamic memory allocation, malloc, free, things that can go wrong,
Reading: Scott: Chapter 3.1 - 3.4, 8.1 - 8.5; 9.1 - 9.2 ALSU 7.1 - 7.3
An introduction to
programming in C can be found through this link. There is an online textbook and a
discussion of gdb and valgrind.
- March 7, 2023 ---
Lecture 14
Static and dynamic scoping, procedure activation record, runtime
environments
Reading: Scott: Chapter 3.1 - 3.4, 8.1 - 8.5; 9.1 - 9.2 ALSU 7.1 - 7.3
An introduction to
programming in C can be found through this link. There is an online textbook and a
discussion of gdb and valgrind.
- March 10, 2023 ---
Lecture 15
Dead code elimination; More on runtime environments, access and control links, parameter passing
Reading: Scott: Chapter 3.1 - 3.4, 8.1 - 8.5; 9.1 - 9.2 ALSU 7.1 - 7.3
An introduction to
programming in C can be found through this link. There is an online textbook and a
discussion of gdb and valgrind.
- March 11 - March 19, 2023 --- Spring Recess
- March 21, 2023 ---
Lecture 16
Purely functional languages, introduction to Scheme (racket, drracket),
S-expressions, Read-Eval_print loop, basic functions, recursive
programs
Reading: Scott: Chapter 10.1 - 10.3
The Scheme Programming
Language by R.Kent Dybvik, Fourth Edition, 2009
- March 24, 2023 ---
Lecture 17
More recursive programming, higher-order functions
Reading: Scott: Chapter 10.1 - 10.3
The Scheme Programming
Language by R.Kent Dybvik, Fourth Edition, 2009
- March 28, 2023 ---
Lecture 18
More recursive programming, map and reduce
Reading: Scott: Chapter 10.1 - 10.3
The Scheme Programming
Language by R.Kent Dybvik, Fourth Edition, 2009
- March 31, 2023 ---
Lecture 19
Constructs let, let*, letrec; lambda calculus, beta and alpha
reductions, capture-free substitution, programming with lambda
calculus, the Y combinator
Reading: Scott: Chapter 10.1 - 10.3
The Scheme Programming
Language by R.Kent Dybvik, Fourth Edition, 2009
- April 4, 2023 ---
Lecture 20
More on lambda calculus;
Introduction to data and task parallelism, different levels of parallelism.
Reading: Scott: Chapter 12.1 - 12.2
- April 7, 2023 ---
Lecture 21
Data dependencies, parallelization vs. vectorization, openMP, statement-level dependence graph
Reading: Scott: Chapter 12.1 - 12.2
OpenMP
tutorial, Blaise Barney, Lawrence Livermore National Laboratory
- April 14, 2023 --- Midterm 2
in class, closed notes, closed book
- April 18, 2023 ---
Lecture 22
Data dependencies analysis, iteration spaces, dependence direction and
distance,
OpenMP and third project, loop transformations, simple
vectorization algorithm
Reading: Scott: Chapter 12.1 - 12.2
OpenMP
tutorial, Blaise Barney, Lawrence Livermore National Laboratory
Practical
Dependence Testing (PLDI'91), Gina Goff, Ken Kennedy, and
Chau-Wen Tseng.
- April 21, 2023 ---
Lecture 23
Data dependencies analysis, OpenMP and third project, loop
transformations, simple vectorization algorithm
Reading: Scott: Chapter 12.1 - 12.2
OpenMP
tutorial, Blaise Barney, Lawrence Livermore National Laboratory
Practical
Dependence Testing (PLDI'91), Gina Goff, Ken Kennedy, and
Chau-Wen Tseng.
- April 25, 2023 ---
Lecture 24-A ,
Lecture 24-B
Review simple vectorization algorithm; quantum computing, mathematical
foundation, tensor product, CNOT gate
- April 28, 2023 ---
Lecture 25
Quantum computing, Hadamard gate, superpositioning, Deutsch oracle, entanglement
- May 1, 2023 --- last day of classes
- May 4, 2023 --- Final
1:00pm - 2:10pm, our regular lecture room, closed notes, closed book
Homeworks
Please write your section number on your homework.
Electronic submission of PDF files only.
Sample solutions will be made available on our canvas site.
- Homework 1
New due date: Thursday, February 2, 2023
- Homework 2
New due date: Thursday, February 16, 2023
- Homework 3
Due date: Tuesday, February 21, 2023
no deadline extension possible
- Homework 4
New due date: Wednesday, March 29, 2023
- Homework 5
New due date: Wednesday, April 5, 2023
- Homework 6
Due date: Tuesday, April 25, 2023
- Homework 7
Due date: Monday, May 1, 2023
Projects
You will need an
ilab account
since all projects will require code to run on the ilab machines. You
should know how to create and edit files in the Linux environment. All
projects have to compile and compile on the ilab machines. It is your
responsibility to make sure that your code works correctly on the
ilab machines.
Code that does not compile and/or run on the ilab cluster will not receive any credit.
Late submission policy: 20% penalty for every 24
hour period after the submission deadline. This means, no credit for
projects submitted more than 4 days (4x24hours) late.