CS 251: Principles of Programming Languages

Instructor: Lyn Turbak, SCI E126
Drop-in hours: (see the drop-ins calendar for the most up-to-date info):

  • Mondays 5-8pm (SCI E126)
  • Tuesdays 2:50-4pm (SCI E126, CS111 due date)
  • Wednesdays TBA (SCI E126)
  • Thursdays 8-10pm (8:30 on Thu Feb 01) (SCI E111)
  • Fridays 2:30-5:30pm (SCI E111)

Tutor Drop-in:
(see the drop-ins calendar for the most up-to-date info)

  • Tuesdays 8-10pm: Jane Abernathy (in micro Focus)
  • Wednesdays 8-10pm: Hope Anderson (in micro Focus)

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 - 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.

Textbook/Reading

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 from the course schedule.

The most important resource in this course are the lecture slides, which serve as the main notes for the course. We will not necessarily cover all slides in lecture, but you are responsible for understanding the content of all slides.

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:

  • Leverage powerful programming language features — such as first-class functions, recursion over tree-shaped data, sum-of-product datatypes, and pattern matching — in languages that support them.
  • Quickly and effectively learn new programming languages by focusing on key language dimensions.
  • Identify the model of computation underlying a programming langauge and 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.
  • Understand and get practical some experience with key aspects of metaprogramming (programs that manipulate programs), including interpretation, compilation, and boostrapping.
  • 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.5)
  • Racket expresssions and declarations, big-step and small step semantics (1.5)
  • 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 (2)
  • iteration by tail recursion (2)
  • tree-shaped data with S-expressions (1)
  • PostFix and intro to metaprogramming (2)

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

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

Metaprogramming and PL dimensions (15 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)
  • digression: a rule-based simplification language (1)
  • Valex: dynamic typechecking and desugaring (1)
  • HOFL: 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)
  • asynchronous programming, JavaScript promises (1)
  • domain specific languages (DSLs) (1)

Course Work and Grading

Reading

Since the lectures slides are the main notes for the class, you are expected to study them carefully. I will strive tto post these at least one day before lecture, so that you have a chance to at least skim them before lecture. You should read them again after lecture.

There is a Readings/Reference page with links to some notes and reference materials for some of the topics in the course. You are encourage to consult these additional materials, most of which were written/collected by Ben Wood.

Additional readings (typically classic papers) on programming languages topics will sometimes 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, most 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 2018, the policy for extra credit is that up to 100 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.

Assignment Submission

All assignment submission will be electronic.

  • In PS1, you will create a CS251 Google Folder shared with me and the tutors that will contain your pset writeups for the rest of the semester.

  • As described in PS1, in each pset, you will create a Google Doc for that pset that contains written answers and/or code for each problem. I will grade a pset by commenting on your Google Doc.

  • For all problems that involve writing code, you will submit the code to a drop folder on cs.wellesley.edu following instructions on individual psets.

Assignments Solutions

Assignment solutions will be provided in hardcopy form only (not online) that are handed out in class. Only solutions to regular (not solo) problems will be provided. Please see me if you have any questions about the solo problems.

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.

Grading Feebdack

You will submit assigments via GoogleDocs (for problem writeups) and a drop folder (for executable code). I will provide feedback on your work (including numerical grades) using the GoogleDocs comment feature, so make sure that this feature is enabled.

In recent semesters, I have not provided pset feedback in a timely fashion, and I know that this is unacceptable.This semester, I will be making a special effort to grade all work within one week of submission.

An assignment is considered graded when I post a comment containing a numerical grade for the solo and regular parts at the top of the assignment.

Course Grade

Your course grade will be determined by the following weighting

  • 50% solo problems
  • 50% 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 5:30pm Friday).

However, there are several exceptions to this rule:

  • For assignments due on Friday, there will be a grace period until the end of Saturday, during which the assignment will not be considered late. There will be no lateness penalty for work submitted on a Sat. (Having to work on a Friday night or Saturday is penalty enough!)

    This exception does not apply to psets due on weekdays other than Friday.

  • Everyone is allotted fifteen 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 coupon.) For example, submitting a pset with a Friday deadline the following Sunday (1 day after the Saturday grace period) requires 1 lateness coupon; submitting it on a Monday requires 2 lateness coupons; etc.

    Coupons are virtual, not physical. I will keep track of them when you turn in an assignment late.

    Coupons are also non-transferable.

    Save your lateness coupons for emergencies. A 10%-per-day penalty is assessed for late work if you have no more coupons to redeem.

  • Spring Break does not count as time toward the course in terms of lateness coupons or penalties.

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

  • Sometimes there are exceptional circumstances that make it difficult or impossible for you to follow the normal pset schedule. Please consult with me about any such situations.

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.

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 me. 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.) In some parts, it also draws (with permission) on material developed by Dan Grossman at the University of Washington and Steve Freund at Williams College.