CS 251: Principles of Programming Languages

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

  • Mon. 2:45-5pm
  • Wed. 4-6pm
  • Thu. 11:15am-1:15pm
  • Fri. 2-5pm

Tutor Drop-ins:

  • Wed 8-10pm (E111): Angela Wu
  • Thu 6:30-8:30pm (outside Lyn's office and E111): Meera Hejmadi
  • Thu 8:15-10:15pm (E111): MR Ngo

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 Monday, Wednesday, Thursday 9:50am - 11am 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

Here is the tentative schedule for topics this semester.

Racket and Functional Programming (16 lectures):

  • Intro (1)
  • Racket expresssions and declarations, big-step and small step semantics (2)
  • lambda and the substitution model (2)
  • lists and list recursion (2)
  • local binding (let), contours, and scope (1)
  • first-class functions (1)
  • higher-order list operations; map, filter, foldr (1)
  • compositional programming (1)
  • iteration by tail recursion (2)
  • tree-shaped data with S-expressions (1)
  • PostFix and intro to metaprogramming (2)

Standard ML: Programming with Type Reconstruction: (7 lectures):

  • intro to SML (1.5)
  • lists in SML (1.5)
  • sum-of-product (SOP) datatypes (2)
  • modules and abstract data types (ADTs) (2)

Metaprogramming and PL dimensions (16 lectures):

  • metaprogramming and language derivations (1)
  • PostFix and Sexp in SML (1)
  • Intex: an expression-based language (1)
  • Intex to PostFix translator (1)
  • Bindex: local naming (1)
  • extending Bindex (1)
  • Valex: dynamic typechecking and desugaring (1)
  • environments and closures (1)
  • HOFL: dynamic vs static scope (1)
  • HOFLEC: state and closures: (1)
  • Object-oriented programming (OOP) with closures (1)
  • laziness and memoization (1)
  • parameter passing (1)
  • continuations (1)
  • non-local exits and exceptions (1)
  • asynchronous programming, JavaScript promises (1)

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 typically-weekly problem sets, 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.
  • written analyses of papers related to evaluating and designing programming languages.

Additionally, many problem sets will include a special solo problem on which you can receive no help from anyone else. Solo problems will cover older material from previous problem sets. They effectively serve as a weekly mini-exam.

Many problem sets will also include one or more extra credit problems. These are fun and challenging problems for which you can earn extra points in the course. Because they tend to be very challenging, you should not attempt these until you have finished the regular problems on a problem set. Unlike other problem set problems, extra credit problems have no deadline; you can submit them at any point during the semester.

In Spring 2017, the policy for extra credit is that up to 120 extra credit points can be added to the regular (non-solo) problem portion of your grade. Although extra credit problems are intended to be done in addition to regular problems, this policy allows you to choose to replace certain regular problems by extra credit problems. But be careful: the extra credit problems are typically more challening than the regular ones.

Exams

There will be no exams this semester. However, as noted above, many problem sets will include a solo problem that is effectively a mini-exam problem. This has the feature of spreading exam-like problems over the semester rather than concentrating them on particular days or weeks.

Project

Unlike some recent semesters of CS251, there will be no final project in the course. However, one of the later problem sets may involve analyzing features of a language that is unfamiliar to you.

Grading

Your course grade will be determined by the following weighting

  • 40% solo problems
  • 60% regular (non-solo) problems

Based on the above weighting, grades will be allocated according to the following boundaries

  • 95%: A
  • 90%: A-
  • 86.67%: B+
  • 83.33%: B
  • 80%: B-
  • 76.67%: C+
  • 73.33%: C
  • 70%: C-
  • 60%: D
  • less than 60%: F

I give these details just to tell how I grade, not to foster a preoccupation about grades. I encourage students to think of grades like Monopoly money; sure, it’s nice to get lots of money in a game of Monopoly, but it doesn’t have a big impact on the rest of your life. Focus on learning rather than grades.

This course will comply 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.

Lateness Policy

Assignments are due at the date and time specified (typically 6pm Friday).

However, there are four exceptions to this rule:

  • For assignments due on Fri, there will be a 24-hour grace period until Sat. during which the assignment will not be considered late. E.g., for an assignment due at 6pm on Fri., there will be no lateness penalty until 6pm on Sat. (Having to work on a Saturday is penalty enough!)

  • An assignment is not considered late until 24 hours after your previous assignment has been graded. But this semester I will strive very hard to grade all assignments in a timely fashion.

  • Everyone is allotted ten 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 10%-per-day penalty is assessed for late work if you have no more passes to redeem. Passes are non-transferable. There is no guarantee about how long it will take to grade late work.

  • Deadlines do not apply to extra credit problems. You can submit these at any time during the semester.

Honor Code and Collaboration

I encourage you to talk with other students about the course and to form study groups. The basic rule of collaboration in this class is that you can talk with anyone about how to solve any problem but you can’t take away anything (notes, programs, etc.) from such a discussion and must write up all programs and solutions completely on your own. This is essentially Yoshi Kohno’s Gilligan’s Island Rule, whose purpose is to ensure that you truly understand everything you write up. You must also explicitly list your collaborators on every problem, and give explicit credit to individuals that had key insights into the solution of a problem (Kohno’s Freedom of Information Rule).

Except for problems designated solo, 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.

Except for problems designated solo, 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.)

On solo problems, all collaboration and consulting of external materials is disallowed. These problems must be solved alone, without discussing solution strategies with anyone else, including the instructor and tutor(s). You may ask the instructor for clarifications but not for hints.

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. If you prefer, you may instead use Lyn’s anonymous feedback form.

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.

If you prefer, you can provide feedback anonymously by using Lyn’s anonymous feedback form.

Acknowledgments

This course makes extensive use of materials from previous semesters of CS251 at Wellesley taught by Ben Wood and Randy Shull (some of which themselves were influenced by earlier versions of CS251 taught by me.) It also draws (with permission) on material developed by Dan Grossman at the University of Washington and Steve Freund at Williams College.