CS 251: Principles of Programming Languages

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

  • Mondays 5-7pm
  • Wednesdays 10am-12:30pm
  • Thursdays 7-9pm
  • Fridays 2-5pm

Tutor Drop-ins (start the week of Sep 09)
(see the drop-ins calendar for the most up-to-date info)

  • Tuesdays 7-9pm: Emma Shumadine in SCI E211
  • Wednesdays 4-6pm: Sherry Xu in E101
  • Wednesdays 7-9pm: Ngina Kariuki in E101

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 8:30am - 9:50am in SCI E211.

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! (If you don’t bring a laptop, you can share with someone who does.) 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

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.

Learning Goals

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 and evaluate 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 (17 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)
  • quoted data and tree-shaped data with S-expressions (2)
  • 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 (14 lectures):

  • metaprogramming and language derivations (2)
  • 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)
  • HOFL: environments and closures (1)
  • HOFL: dynamic vs static scope (1)
  • HOFLEC: state and closures: (1)
  • laziness and memoization (1)
  • continuations, non-local exits, and exceptions (1)
  • object-oriented programming (OOP) with closures (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 Feedback

You will submit assigments via Google Docs (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, although grant proposal deadlines on Tue. Oct 02 and Tue. Nov. 14 may delay grading near these deadlines. Why do I think I can to better this semester?

  • My weekly schedule now has lots of hours set aside for grading CS251 work;

  • Last semester I developed some grading assistant software that streamlines the grading of assignments with code.

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.

Sometimes, my grading comments on a pset may indicate that you can redo a problem or a part of a problem. If you redo the problem, please email me when you modify your Google Doc with the revised solution so that I know to regrade it.

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.

Credit/Non is Usually a Bad Idea!

Experience shows that taking CS251 credit/non is generally a bad idea.

  • In order to get credit in a credit/non course, you must get a C grade (73.33 course score or higher), which is significantly higher
    than the D grade (60 course score or higher) required to pass the course.

  • Most students who take the course credit/non do not get a C grade by the end of the semester, and either need to retake the course or need to take an incomplete in the course and earn more points before the beginning of the next semester. For seniors, this can delay the awarding of a diploma. Because many credit/non students who do not get credit by the end of the course would be able to get a D, they tend to regret their decision to take the course credit/non.

At the beginning of the semester, I cannot tell who is signed up to take the course credit/non. So I request that any student wishing to take the course credit/non should meet with me in person during the first two weeks of the semester to discuss this decision.

Lateness Policy

This semester I am adopting a version of Ada Learner’s lateness policy from CS342, which I like a lot. Much of the wording below is Ada’s.

Assignments have two purposes: to help you learn, and to help both of us assess your learning (so that you can learn better, and I can help you learn better). Because assignments play such an important role in your learning, it is very important to me that you do the assignments. As a consequence, I do not deduct points for late assignments, since I find that doing so discourages completing the assignment and gaining its learning-related benefits.

For any and all assignments, you may take a no-questions-asked extension until the end of the second day after the posted deadline. For example, for an assignment due on Fri at 5:30pm, you may submit the assignment by the end of Sunday without needing to do anything else.

If those two extra days are not sufficient for you to complete the assignment, you MUST contact me to let me know. When you contact me, I will ask you to tell me about your plan for completing the assignment, and we will work together to make sure that plan is a reasonable and effective one that supports both your learning and your health and wellbeing.

In some cases, it may make sense to delay certain parts of one assignment and instead focus on the next assginment, so as to keep up better with the current course material.

Even if you are behind on one or more assignments, it is essential that you continue to attend class and try your best to keep up with the new material being presented in class.

The purpose of this policy is to help you balance the requirements of this course with your mental, physical, and emotional health. I recognize that your personal life is important, and my goal with this policy is to help you find the flexibility you need. You are never expected or required to tell me any personal or private details of your life. However, I am always available to listen should you feel that sharing anything will help me support you.

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.

Disabilities and Accommodations

Thanks to Ada Lerner for some of this wording.

My job is to help each and every one of you learn, and part of that is making accommodations for any disabilities you might have. Please feel free to speak with me about concerns or suggestions about how I can make the course more accessible to you. I will never judge you or your disabilities, and I will keep the details of our conversations confidential. If you prefer, you may instead use Lyn’s anonymous feedback form. Though you are welcome to share any details that will help me assist in your learning, you are never required to share any private details of your life with me.

If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, it is also strongly recommended that you contact Disability Services to get a letter outlining your accommodation needs, and submit that letter to me. You should request accommodations as early as possible in the semester, or before the semester begins, since some situations can require significant time for review and accommodation design. If you need immediate accommodations, please arrange to meet with me as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact Disability Services. They can provide assistance including screening and referral for assessments. Disability Services can be reached at disabilityservices@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website www.Wellesley.edu/disability , or by visiting their offices on the 3rd floor of Clapp Library, rooms 316 and 315.

Course Feedback

Please share suggestions and comments about the course at any time. My goal is to make this course the best it can be for covering material about programming languages, so I am always open to suggestions for improving it. Tell me what works well in the course 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.