CSE526 (Spring 2021)
Principles of Programming Languages

General Information | Schedule | Resources | Requirements

General Information

Course description: This course is for students interested in programming language concepts and design, with emphasis on abstraction mechanisms. Topics include language semantics, programming paradigms, as well as analysis and optimization methods. Such study enables deeper understanding, better usage, and more efficient implementations. | Prerequisites: CSE307, CSE304, or equivalent; or undergraduate discrete math (predicate logic, sets, functions, relations) plus good experience using two or more programming languages. | Credits: 3.

Instructor: Annie Liu | Office: New CS 237 | Phone: 631-632-8463 | Email: liu@cs.stonybrook.edu | Office hours: Mon 12:40-1 PM, 2:20-3 PM, Thu 4:20-5 PM, Fri 12:20-1 PM, 2:20-2:40 PM, or email for an appointment.

Lectures: Mon Fri 1-2:20 PM. For students who registered for the hybrid section: NCS 120 is the teaching lab; you are required to attend in person for lectures in March.

Textbook: There is no required textbook for this course; best relevant book chapters, lecture notes, and/or slides will be given under resources as the course proceeds.

Grading: Lecture critiques: 2% | In-class exercises: 8% | Assignments: 20% | Quizzes: 20% | Project: 25% | Final exam: 25% | No late submission will receive credit.

Course homepage: http://www.cs.sunysb.edu/~liu/cse526/

Schedule

 
14 Weeks total

Unit 1. Overview and language processing

 1. Language overview---what, why, and how:
	data/control/module abstraction, formal semantics, interpreter/compiler

 2. Syntax and semantics---language processing:
	grammar rules, syntax-directed rules, concrete/abstract representations

Unit 2. Imperative languages and formal semantics

 3. Imperative languages, formal semantics:
	expressions/commands, operational semantics, big/small steps, induction

 4. Denotational semantics, axiomatic semantics:
	semantic functions, correctness assertions and proof rules, proofs

 5. Project plan and design, and quiz 1

Unit 3. Database languages and efficient implementation

 6. Database languages---sets and relations, queries:
	set comprehension, aggregation, quantification
    	     
 7. Efficient implementation: generating iteration,
	optimization by incrementalization, data structure selection

Unit 4. Functional languages and type inference

 8. Functional languages---recursive functions, higher-order, 
	call by value/name, eager/lazy, static/dynamic scoping, lambda calculus

 9. Types and type inference: principal types, type constraints, unification,
	Curry-Howard isomorphism, polymorphic type inference

 10. Project implementation and testing, and quiz 2

Unit 5. Logic languages and reasoning

 11. Logic languages---rules, search: Datalog, Prolog,
	logic/relational/recursive programming, Answer set programming

 12. Puzzles and AI---knowledge representation and reasoning:
	Russell's paradox, negation in cycles, efficient implementation

Unit 6. Object-oriented languages and distributed programming

 13. Object-oriented languages: encapsulation, inheritance, 
	evolution of abstraction, design patterns

 14. Concurrent and distributed languages: shared-memory/message-passing,
  	synchronous/asynchronous, history queries

(possibly moving Unit 6 to be before Unit 4)

Resources

Google Classroom for this course, for students in the course

References:

Programming Language Pragmatics by Michael Scott. Morgan Kaufmann Publishers. 3rd edition 2009 or 4th edition, 2015. This is an excellent textbook that covers both programming language design and implementation.

The Formal Semantics of Programming Languages by Glynn Winskel, The MIT Press, 1993. This is an excellent book that covers programming language semantics.

Programming languages and tools at https://hyperpolyglot.org/, with commonly used features in a side-by-side format, and with explanations by examples.

Readings:

Python | Python Documentation (read Tutorial, browse Library Reference, and when needed look up Language Reference and rest)

Undergraduate Programming Languages background, Chapter 1 of Scott

Undergraduate Discrete Math background, Chapter 1 of Winskel

Requirements

Follow all information in the Google Classroom for this course.

Attend all lectures and take good notes. This is the most efficient way to learn the course materials, because we will both distill and elaborate written materials and discuss important related materials. We will start promptly on time. We will have every student participate in solving problems and presenting solutions in class.

Do all course work. The readings are to help you preview and review the materials discussed in the lectures. The assignments and project are to provide concrete experiences with the basic concepts and methods covered in the lectures. The exercises and quizzes are to help check that you are keeping up with the lectures and the assignments. The exams will be comprehensive.

If you have any questions, ask. Ask questions in class, in office hours, and in the Q&A forum. Talk with your classmates, and share ideas, but not solutions to assignments.

Your work:

Your handins should include the following information at the top: your name, student id, course number, assignment number, and due date, and should be submitted in a neat and organized fashion.

Your programming solutions should always be submitted with a README.txt file explaining where things are, what you did and found for the assignment (that is not described in the assignment handout), and how to run and test your code. This file is worth a non-trivial portion of the grade.

Your approach to solving problems is as important as your final solutions; you need to show how you arrived at your solutions and include appropriate explanations. Always include good explanations in your README file and good comments in your code.

Your homework and project submissions must be your own work. You are not permitted to share, borrow, or even look at another student's work while completing your own homework. Likewise, copying material from any source other than what is specified by the instructor will constitute cheating. 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 evidence that answers have been copied, shared, or transmitted in any way, including the use of answers downloaded from the Internet or written by others previously, will be regarded as evidence of academic dishonesty. The College of Engineering and Applied Sciences (CEAS) regards academic dishonesty as a very serious matter and provides for substantial penalties in such cases, such as receiving an 'F' grade and/or expulsion from the University. Those involved in academically dishonest behavior will be prosecuted to the fullest extent permitted by the University and College laws. For more information, you can obtain a copy of the CEAS guidelines on academic dishonesty from the CEAS office.

Submission issues:

Neither extensions nor late submissions will be approved under normal circumstances. If some sort of emergency or other circumstances truly beyond your control prevent you from submitting your assignment on time, supply the instructor with suitable documentation and notification prior to the assignment deadline. The instructor will also refer you to the Dean of Students for follow-up consultation.

Students are urged to plan ahead to avoid problems such as computer failures at the last minute. If your assignment is incomplete before it is due, turn in whatever you have. You are advised to budget your time wisely and to start working on an assignment the day it is posted.

Grading issues:

The final grade you receive in this class will reflect, as far as possible, the extent to which you have mastered the concepts and their applications. How much someone needs a grade, or how close they are to the next higher grade, will have no effect on grade. As the instructor, I want everyone to do well in this course, and will make every reasonable effort to help you understand the material taught. However, the grades provided at the end of the semester are final, except for rare situations involving grading errors. They will not be altered for other reasons, so please do not ask me to do so.

If you feel your grade was assigned incorrectly, please meet with the person (instructor or TA) responsible for the grading. Please arrange a re-grading within one week of receiving the graded work; later requests will not be entertained.

To promote consistency of grading, issues about work graded by a TA should be addressed first to the TA and then, if the issues are not resolved, to the instructor.

Source for items below: https://www.stonybrook.edu/commcms/provost/faculty/handbook/academic_policies/syllabus_statement.php

Academic Integrity: Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/commcms/academic_integrity/

Student Accessibility Support Center: If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, Stony Brook Union Suite 107, (631) 632-6748, or at sasc@stonybrook.edu. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.

Critical Incident Management: Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Student Conduct and Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.

From the College of Engineering and Applied Sciences:

All students must follow Stony Brook, local, state and Centers for Disease Control and Prevention (CDC) guidelines to reduce the risk of transmission of COVID.

Final note (thanks Professor Shyam Sharma for sharing this): College is more than the sum of the courses you take, or the numbers on your transcript; here you also build relationships with professors and advisors, academic staff and classmates. If you anticipate requesting me (and this is true with any professor) to write recommendation letters for internship, job application, scholarship/fellowship, or graduate school, then it is wise to demonstrate your best commitment to studies in this course. If I've observed you as the kind of student college professors want to rave about, I will rave about you in my letters. I respect in students a genuine interest in learning and intellectual honesty in engaging with complex ideas, regularity and punctuality in class, hard work and collegiality with peers and instructor, significant progress and resilience during the semester, a willingness to go beyond "requirements", and so on. In a way, it starts with treating a required course like this with curiosity and interest, as a good learning opportunity, taking full advantage of the course and my support. When I don't have much to say---or include clear, strong, and positive details---I ask students to find another recommender who knows their strengths better. I add this note on the syllabus because students in the past have said that they "wish" they'd known about the idea early on.

Annie Liu