CS 251: Principles of Programming Languages

Instructor: Lyn Turbak, SCI E126
Drop-in hours (SCI E126 or micro-focus):

  • Mon. 11:10am-12:20am, 4-7pm
  • Tue. 1:30-3:45pm
  • Thu. 12-1:30pm, 8-10pm
  • Fri. 2-5pm
Tutors:
  • Sara Burns: drop-ins Wed. 7-9pm in micro-focus
  • Sravanti Tekumalla: drop-ins Thu. 6:15-8:15pm in micro-focus

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

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 Spring 2016, with minor adjustments for reality. A concrete schedule evolves on the course website.

  • Week 1: Big ideas, computability, halting problem, introduction to Racket
  • 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

Originally, two midterm exams and a final exam were planned, but in the end, only a single take-home midterm exam (between PS4 and PS5) was given.

Project

Unlike recent semesters of CS251, there will be no final project. However, it is likely that the final assignment will involve analyzing features of a language that is unfamiliar to you.

Grading

  • 80% assignments
  • 20% midterm exam

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 (typically 5pm Friday). This deadline is strict.

However, there are two exceptions to this rule:

  • An assignment is not considered late until 24 hours after the previous assignment has been returned.

  • You are each allotted five 24-hour lateness coupouns (Ben calls them time-turner passes) to use during the semester. Each coupon 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 lateness coupons for emergencies. A 20%-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. 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 makes extensive use of materials on previous semesters of CS251 at Wellesley taught by
Ben Wood and Randy Shull. It also draws (with permission) on material developed by
Dan Grossman at the University of Washington and Steve Freund at Williams College.