CS 251: Principles of Programming Languages

Instructor: Ben Wood, SCI E128 or microfous, office hours / contact on website
Tutors: Alice and Cecille

  • Tuesday 7pm - 9pm (SCI microfocus)
  • Wednesday 7pm - 9pm (SCI S173)
  • Thursday 7pm - 9pm (SCI microfocus or S173)

Website: https://cs.wellesley.edu/~cs251/

Google Group: We will use the Google Group email list for announcements, course discussion, and help. You are subscribed automatically on registration. Please stay subscribed and check your email.

Class Meetings

Class meetings are Tuesday, Wednesday, Friday 9:50am - 11:00am in SCI E111.

Attendance and active participation is expected at all class meetings. Class time will be spent on a mix of lecture and hands-on activities. Bring a laptop if you can! We will do a good bit of coding in class, both on whiteboards and on screens.

Textbooks

We will not use a traditional textbook for this course. We will refer to a variety of course-specific material and some material freely available online, to be posted or linked on the course website.

Course Description and Goals

Prerequisite: CS 230 or permission of the instructor.

This course introduces principles underlying the design, semantics, and implementation of modern programming languages in major paradigms including function-oriented, imperative, and object-oriented. The course examines: language dimensions including syntax, naming, state, data, control, types, abstraction, modularity, and extensibility; issues in the runtime representation and implementation of programming languages; and the expression and management of parallelism and concurrency. Students explore course topics via programming exercises in several languages, including the development of programming language interpreters. Students will also engage in critical thought exercises analyzing how language design choices impact concerns such as reliability, extensibility, implementation, and performance, and vice versa.

The course will prepare you to:

  • Quickly and effectively learn new programming languages by focusing on key language dimensions.
  • Recognize whether a given programming language is a good fit for a given problem.
  • Reason rigorously about the execution of programs using precisely defined models.
  • Implement a well-specified model correctly by applying lessons from language design to construct a program or define a programming language.

Schedule

Projection for Fall 2015, with minor adjustments for reality. A concrete schedule evolves on the course website.

  • Week 1: Themes, computability, halting problem
  • Weeks 2-3: Building blocks (in Racket: expressions, values, bindings, environments, syntactic sugar, lists, first-class functions, lexical scope, closures, tail recursion)
  • Week 4: Implementation interlude (tail call optimization, immutability, Lisp, GC, interpreters, compilers, programs as data, macros)
  • Weeks 5-8: Types, patterns, and abstraction (in Standard ML: static type-checking and inference, polymorphism, algebraic data types, pattern matching, grammars and ASTs, currying, partial application, modules, abstract data types)
  • Week 9: Implementation interlude (implementing environments, stacks, closures, exceptions, building interpreters)
  • Week 10: Alternative evaluation models (lambda calculus, substitution, parameter passing, delayed evaluation, streams, laziness)
  • Weeks 10-12: Object orientation (in Smalltalk, Java, Scala: substitutivity, subtyping, polymorphism, inheritance, mixins, traits, generic types, dynamic dispatch, multiple dispatch)
  • Week 12: Design tensions (decomposition, classification vs. composition, extensibility, composability, encapsulation) and other models (logic and constraints, DSLs)
  • Weeks 13-14: Parallelism and concurrency, languages for problems, program analysis

Course Work and Grading

Reading

Notes posted on the working schedule on the course website cover much of the same material as lecture. Links to additional resources providing alternative descriptions of concepts will also be posted. You may consult these as needed, before or after the related lectures.

Additional readings (typically classic papers) on programming languages topics will also be assigned. These readings will be accompanied by thought questions in preparation for group discussions in class or for written response as part of assignments.

Assignments

CS 251 will include roughly 10 assignments, comprised of:

  • exercises in reasoning about the execution of small programs to understand precise language semantics;
  • small and medium-scale programming problems illustrating idioms in different programming languages and paradigms;
  • larger programming assignments, such as the implementation of interpreters for small languages of our own design; and
  • written analyses of language designs, their motivating applications, and their suitability to new applications.

Exams

I plan two exams:

  • A take-home exam in the week following Fall Break.
  • An in-class exam in the week of November 16-20 on Tuesday 17 November.

Project

There will be an open-ended final project involving programming and writing. The project will focus on exploring and evaluating the design of a new-to-you programming language. We will discuss the shape of this project in more detail as it gets closer.

Grading

  • 50% assignments
  • 30% exams
  • 15% final project
  • 5% participation, etc.

This course complies with the Wellesley College policy (http://www.wellesley.edu/registrar/grading/gradingpolicyfaq). While that policy asks faculty to hold each 100- and 200-level course with 10 or more students to an average of no higher than 3.33, it does not require faculty to grade on a “curve.” There is no arbitrary limit on the number of A’s, B’s, C’s etc., and every student will be assigned the grade they earn and deserve according to the grading standards of the college.

Late Policy

Assignments are due at the date and time specified. This deadline is strict. You are each allotted a budget of 3 24-hour time-turner passes to use during the semester. Each pass may be redeemed to delay one deadline by exactly 24 hours. (e.g., turning in an assignment 1 hour late or 23.5 hours late both cost exactly one 24-hour pass.) Save your time-turner passes for emergencies. A 25%-per-day penalty is assessed for late work if you have no more passes to redeem. Passes are non-transferable and may not be applied to exams or projects. There is no guarantee about how long we will take to grade late work.

Honor Code and Collaboration

I encourage you to talk with other students about the course and to form study groups.

Unless otherwise instructed, feel free to discuss problems with other students and exchange ideas about how to solve them, but do not collaboratively develop a full solution. You must write (or otherwise implement) your own solution to each problem from scratch. With your solution to each problem, you must explicitly name each person with whom you discussed the problem and strategies to solve it.

On some problems, we may explicitly allow (and recommend) pairs of students to work together to produce a single solution. In this case, similar rules apply: you may discuss high-level strategies and ideas with others, but your solution must be the work of you and your partner only and you must cite your discussion collaborators in your work.

On other problems, we may explicitly disallow any collaboration. These problems must be solved alone, without discussing solution strategies with anyone except the instructors.

You are welcome to consult “external” material beyond the course material for CS 251, but you must cite any sources that contribute to your solution. (You do not need to cite documentation of tools, like compilers or debuggers.)

Exams will give explicit instructions on what sources (if any) are allowed.

Failure to cite collaborators or sources on assignments is a violation of the Honor Code, as is any collaboration or consultation of outside sources where these have been explicitly disallowed.

In general, common sense applies. If you are unsure of the boundaries of acceptable collaboration or use of reference material, please ask your instructor. In this case, it is far better to ask permission than to seek forgiveness.

Accommodations

Please feel free to speak with me about concerns or suggestions about how I can make the course more accessible to you. I will keep our conversations confidential and do my best to help. An anonymous feedback form is available in the Google Group if you would prefer.

Students with disabilities who are taking this course and who need disability-related accommodations are encouraged to work with Jim Wice (781.283.2434 or jwice@wellesley.edu), the Director of Disability Services. Jim’s office is located in the Pforzheimer Learning & Teaching Center on the third floor of Clapp Library. If you have a physical disability or a learning disability, Jim is the person to see to arrange for accommodations. If your learning disability is undocumented or if you are uncertain as to whether you have a disability, Jim can arrange for you to be tested.

Course Feedback

Please share suggestions and comments about the course at any time. Tell me what works well and what does not. I will do my best to address it. An anonymous feedback form is available if you would prefer.

Acknowledgments

This course draws (with permission) on materials from Dan Grossman at the University of Washington, Steve Freund at Williams College, and previous versions of CS 251 at Wellesley by Randy Shull and Lyn Turbak.