CS45600: Programming Languages

Class Monday, Wednesday, Friday 1:30-2:20pm, Lawson B134
Instructor Roopsha Samanta
Instructor office hours Monday, Wedneday 2:30-3:30pm (or by appointment), LWSN 2116L
TA Sudharshan Viswanathan
TA office hours Tuesday, Friday 10:00-11:00am, HAAS G050
Online forum Piazza (sign up here)
Prerequisites CS35200 (may be taken concurrently)
Textbooks Required:
Norman Ramsey, Programming Languages: Build, Prove and Compare, draft manuscript, December 2016
Jeffrey D. Ullman, Elements of ML Programming (ML97 edition) , Prentice Hall, Englewood Cliffs/NJ, 1998
Lots of useful references
CS45600 is a course about the principles of programming languages and their application. The emphasis is on ideas and techniques relevant to practitioners, but includes theoretical foundations crucial for deeper understanding: abstract syntax, formal semantics, type systems, and lambda calculus. Work in the course involves exploring programming languages and features both as a user (by writing programs in those languages), as a language designer (by implementing interpreters for those languages), and as a scholar (by proving mathematical properties of them). Case studies will cover languages from the functional, logic, and object-oriented families that go beyond the simple imperative paradigm. Example languages may include Standard ML, Smalltalk, Scheme, and Prolog.

To succeed in this course and the field of programming languages, you will combine code and math. You must be comfortable with recursion and with basic mathematical ideas and notations for sets, functions, etc. Good programming skills are essential - you must have previous experience programming in imperative languages like C, C++, or Java.

Note: CS 45600 does not cover implementation of conventional, imperative programming languages, which are covered in CS 35200 (Compilers).

  • Abstract syntax and operational semantics
  • Functional programming with lists and recursion
  • First-class and higher-order functions; continuations
  • Functional programming with algebraic data types and static types (in ML)
  • Type systems and parametric polymorphism
  • ML type inference
  • Lambda calculus; small-step semantics
  • Object-orientation and inheritance
  • ML module system

Acknowledgement: This course and the website are heavily based on Norman Ramsey's COMP 105 at Tufts University. The course materials are derived from those graciously provided by Norman Ramsey, Kathleen Fisher and Tony Hosking.
Note: This syllabus and schedule is tentative and may change without notice at any time. The topics-by-date and additional readings will be provided as we go along.

The course will closely follow these Lecture notes.

Week Date Topic Reading
Week 1Unit 1: Introduction, imperative core, ASTs & environmentsChap 1 (upto and including Sec 1.4)


Jan-9 Course introduction, recursion



Jan-11 An imperative core, abstract syntax, environments



Unit 2: Operational semantics, metatheory Chap 1



Inference rules, evaluation



Week 2 Jan-16 No class: MLK day



Jan-18 Derivations and metatheory (Lecture by Sudharshan)



Jan-20 No class: instructor travel


HW1 due
Week 3 Jan-23 Review: Units 1 and 2



Unit 3: Scheme: Recursive programming with lists Chap 2 (upto Sec. 2.6, then Sec. 2.11 and Sec. 2.13)


Jan-25 S-expressions, cons, and its algebraic laws



Jan-27 Programming with recursion and lists using case analysis



Week 4 Jan-30 Cost of cons, append and reverse, the method of accumulating parameters



Unit 4: Scheme II: First-class and higher-order functions, continuation passing Chap 2


Feb-1 The let family, introduction to lambda, and functions as values



Feb-3 Using lambda to create escaping functions


HW2 due
Week 5 Feb-6 Higher-order functions on lists


Feb-8 Tail calls and continuations



Feb-10 Operational semantics of uScheme



Week 6 Unit 5: Introduction to ML


Feb-13 Introduction, algebraic data types



Feb-15 Introduction and elimination, working with types



Feb-17 More types, more ML


HW3 due
Week 7 Unit 6: Type systems Chap 6


Feb-20 Type systems: basics



Feb-22 No class



Feb-24 Type checking: basics



Week 8 Feb-27 Midterm review



Mar-1 Monomorphic type checking



Mar-3 Polymorphic type checking HW4 due
Week 9 Mar-6 Midterm


Mar-8 Polymorphism wrapup



Mar-10 Midterm exam review



Week 10 Spring break
Week 11 Unit 7: ML type Inference Chap 7


Mar-20 Type inference overview



Mar-22 Hindley-Milner types



Mar-24 Type inference using explicit constraints


HW5 due
Week 12 Mar-27 Inferring polytypes



Mar-29 Constraint-solving



Unit 8: Lambda calculus

Mar-31 Overview, Church encodings, beta reduction



Week 13 Apr-3 Reduction strategies, normal form



Apr-5 Recursion equations, fixed points



Unit 9: Smalltalk: Object-oriented programming Chap 11


Apr-7 Object-orientation and Smalltalk overview


HW6 due
Week 14 Apr-10 Smalltalk protocols, hierarchies, inheritance



Apr-12 Special session: Prof. Zach Tatlock



Apr-14 Collections, subtyping


Week 15 Unit 10: Standard ML Modules


Apr-17 Introduction to modules, structures, signatures



Apr-19 Functors, abstract types



Unit 11: Prolog: Logic Programming



Apr-21 Overview


HW7 due (optional)
Week 16 Apr-24 Semantics



Apr-26 Review





Week 17 May-3 Final exam (LWSN B148)



Most work for this course involves programming assignments. These assignments are significantly challenging, but most of them are also fairly small: many solutions take 10 to 40 lines of code. Many of the assignments will use software that comes with the text by Ramsey.

The course will also have two exams: a midterm and a final.

Homework grades
Your homework grades will be based on a judgement of the quality of your work and your mastery of the material. Grades are assigned on the same scale used by the National Science Foundation:
  • Excellent work is outstanding in all respects. To be ranked excellent, the work must truly excel; that is, it must exceed expectations in some way.
    (By definition, it is not possible for the entire class to excel. The normal top grade is Very Good, and students who consistently produce Very Good work earn A's. Grades of Excellent are awarded only in cases of true distinction.)

    Excellent documentation will address exactly the key issues, and degree of detail will be exactly appropriate.

    Excellent code will be very well thought out and implemented. Excellent code will show mastery of new language features and idioms. On the rare larger assignments, Excellent code will show evidence of thorough attention to abstraction and modularity. Excellent code will be so simple that it obviously has no faults. Instructors will see no obvious ways to make excellent code shorter or simpler. Layout will be consistent and will make good use of scarce vertical space. Excellent code will be of such high quality that the course staff would be happy to maintain it.

  • Very Good work is of high quality in nearly all respects. An assignment that does everything asked for, and does it well, will earn a grade of Very Good.

    Very good documentation will address most key issues, with a good amount of detail.

    Very Good code will show correct, idiomatic use of new language features. On the rare larger assignments, Very Good code will show that some attention will have been paid to abstraction and modularity, although one or two opportunities may have been overlooked. Very Good code will contain well chosen names for functions and their parameters, so that it is easy to guess what functions do. Instructors may see one or two ways to make Very Good code shorter or simpler. Layout will be consistent and will make good use of scarce vertical space. Small errors may be evident from reading the code.

  • Good work demonstrates quality and significant learning.

    Good documentation will cover some key issues, but significant issues may have been overlooked or may have been covered with insufficient detail. Vague generalities may appear where precise specifics are expected.

    In Good code, documentation may not be up to expectations: there may be too much or too little. Individual functions will be well organized and readable. Most names will be well chosen, but their may be some exceptions. On the rare larger assignments, opportunities for abstraction and modularity will probably have been overlooked. Good code will get the job done, but possibly in a way that could be shorter or simpler. Layout may be inconsistent in a few places. Errors may be evident from reading the code, but instructors will believe that code could be made correct with only modest changes.

  • Fair work is lacking in one or more aspects; key issues need to be addressed. “Fair” is the lowest satisfactory grade.

    Fair documentation will show evidence of effort, but the degree of coverage and detail will be significantly short of what the course staff believe is needed to foster success.

    Fair code will contain significant faults. Instructors may not be able to figure out what all functions do. Layout may be inconsistent or waste scarce vertical space (e.g., every other line may be blank). Fair code may show evidence of a 'clone and modify' approach to program construction. Names may be poorly chosen. Possibly a Fair program could be replaced by code half its size. Given Fair code, instructors may believe major changes would be required to make the code correct, or instructors may be unable to understand why the code might be correct.

  • Poor work shows little evidence of effort or has other serious deficiencies. “Poor” is an unsatisfactory grade.

    Poor documentation may fail to address key issues or may address them perfunctorily.

    Poor code may be undocumented or inappropriately documented (e.g., overcommented). Poor code will often be lengthy out of all proportion to the problem being solved. Poor code may be laid out on the page in a way that is hard to read. Poor code often shows evidence of its history: extra copies of functions, unused logic left lying around, old code commented out, and so on. Poor code may be so complex that it has no obvious faults.

  • No Credit will be received for work not turned in, for parts that are incomplete, or for work that is non-functional or appears to bear no relation to the problems assigned.

    You will receive No Credit for work that you cannot explain.

    No Credit will be received for work that is deemed to be plagiarized. Submitted code may be examined for potential plagiarism using automated heuristics. Plagiarism is a form of academic fraud, which is unacceptable. If academic fraud is suspected, appropriate steps will be taken. Submitting someone else's work as your own is likely to lead to suspension or expulsion.

Examinations and examination grades
An examination should test not only your mastery of familiar material but also your ability to apply your knowledge to unfamiliar situations. To do well on my exams, you must
  • Remember the material
  • Understand the material
  • Apply your understanding to new problems

When you take an exam, expect not to know all the answers.

Each exam consists of multiple problems; you may be expected to read and write code. Each problem is worth a certain number of points; the number depends on how hard I think the problem is and how long it takes to complete the problem. Most problems are in multiple parts of varying difficulty:
  • There is usually a basic part that is not too difficult and is worth a few points.
  • There is a middle part that is quite difficult and is worth most of the points.
  • There is often a ``stretch part'' that is meant to extend your reach and is worth a couple of points.
It is very rare for an answer to earn all points available on a problem.

Every exam is unique, but on average, if you earn two-thirds of the available points, your grade will probably be Good or Very Good.

Course grades
Your course grade is based on my judgment of the quality of your work and the degree of mastery you demonstrate. My judgment is influenced by your written work, by your class participation, and by your examination scores, but heavy consideration is given to written work, as indicated by the following approximate system of weights:
Class participation5%
Instructor office-hour visit5%
Homework assignments60%
Midterm exam10%
Final exam 20%
This weighting may be adjusted at the discretion of the instructor.

When determining final course grades, we consider the total picture including not only all of your work but any grading tendencies I have observed during the term. My goal is the final course grades should reflect a consistent standard, consistently applied.

In a typical class, a consistent record of Very Good homework, together with commensurate examination grades, will lead to a course grade in the A range. If a significant portion of work is rated Excellent, a grade of A+ is possible. Work rated Good corresponds to a wide range of passing grades centered roughly around B. Work rated Fair will lead to low but satisfactory course grades; if a significant fraction of your work is Poor, you can expect an unsatisfactory grade (D or F).

Detailed information all students must know

CS Basics. You must grasp basic algorithms, data structures, and good programming practice.

Unix. You must understand the basics of files, directories, creating and editing files, printing, compiling and loading programs, and using make. You will be much, much happier if you also can write a simple shell script (sh) and use Awk and grep effectively. Kernighan and Pike cover these topics at the appropriate level.

Theory/Discrete Math. You must be comfortable with basic discrete mathematics and you must be able to prove theorems, especially by induction. We assume that you have taken Discrete Math. If you have not, you must produce some other evidence that you can reason precisely about computational objects. You should be able to write an informal mathematical proof. For example, you should be able to prove that a sort function returns the same set of elements that it was passed. You should be comfortable using basic mathematical formulas with “forall” and “exists” quantifiers, i.e., the propositional and predicate calculi. You should know basic set theory, e.g., the mathematical definition of functions as sets of ordered pairs. You should be comfortable reading and writing formal mathematical notation, or at least not run screaming from the room when it appears.

Programming. You should have substantial programming experience. Those without such experience will have difficulty keeping up with the homework. Proficiency in C is needed for a few homework assignments; if you have a strong background in C++, some details will be different, but your background should be sufficient. Your programming experience should include work with dynamically allocated data structures and with recursive functions. You should be very comfortable writing recursive functions in the language of your choice, as well as proving that such functions terminate. You should have implemented some of the basic data structures and algorithms used in computer science, like stacks, queues, lists, tables, search trees, standard sorts (quick, insertion, merge, heap), topological sort, and graph algorithms. These topics are well covered in other courses. Prior exposure to exhaustive search (backtracking) will also be helpful.

Some students spend many, many hours thrashing out homework assignments. This course uses unusual programming paradigms, and the techniques you are accustomed to may not be much help. Although this material is not a formal prerequisite for this course, you will be happier if you have a nodding acquaintance with formal methods, including the following intellectual tools:
  • Loop invariants and termination conditions as they apply to imperative programs.
  • Contracts for functions, including preconditions and postconditions.
  • Termination conditions for recursive functions. When writing recursive functions, try to develop your understanding of the deep connections between recursion and loops; the ideas of invariants and termination conditions apply in both cases.
  • Representation invariants and abstraction functions for abstract data types.
You can brush up on this material by looking at the article by Bentley on the reading list. Chapter 4 of Liskov and Guttag has a nice tutorial on reasoning about data, which you will find helpful in several assignments.

Good Work Habits. The most important prerequisites for this course cannot be taught. To do well in this or any other course that involves programming, develop these habits:
  • Think carefully about a problem before you begin to write code.
  • When having difficulty writing code, stand up, walk away from your computer, and think about the difficulty. Enlist the black/white-board as your ally.
  • Never be satisfied with a “working program,” but strive for the simplest, clearest, most elegant implementation.
If you have these habits, the other prerequisites are almost irrelevant. If you don't, you can expect to have trouble no matter what your background.

Interactions are Expected
Engineering is not a solitary profession. To maximize your chances of success in 456 and beyond, the class includes some interactive experiences.
  • Faculty interaction. Part of your job as a student is to get to know some of the faculty. To help you with this part of your education, up to five minutes of office-hour visits count as part of your course grade. Each minute you spend in conversation during office hours will earn one percent of your overall course grade, up to a possible total of five percent. To earn your five percent, you must come to office hours by the end of February. While you may find it helpful to talk about homework, class, engineering, or Purdue overall, any mutually agreeable topic of conversation is acceptable.
  • Pair programming. Much of the programming in 456 is about your own individual understanding of new language features and new ideas, and you will tackle this sort of programming on your own. But sometimes you will have the opportunity to build something more substantial. And in the real world, substantial artifacts are seldom built by individuals working alone. CS 456 will therefore provide you with some opportunity to practice pair programming. You will have the opportunity to practice pair programming on selected problems throughout the term. No single pair may work together on more than three assignments. If you need help finding a partner, advertise on Piazza.

Spontaneous interactions may be welcome or unwelcome depending on the interaction:
  • A particularly useful form of interaction is the question asked in class. Questions are always welcome; if you have a question, chances are other people in class have a similar question. Ask it!
  • A particularly pernicious form of interaction is the telephone call. During class, please put your cell phone on vibrate. If you must take a call, please leave the classroom and do not return until you have finished your call.

Class participation
A portion of your grade is based on your participation in class. This phrase encompasses a variety of activities, all with the same purpose: to earn high grades for class participation, you must show that you are actively engaged in managing your own learning, developing new skills, and developing new ways of programming and problem-solving. You can be engaged in a variety of ways:
  • Participating in the online course evaluations (both mid-term and end-of-term)
  • Asking appropriate questions in class
  • Answering questions when called on in class
  • Asking appropriate questions on Piazza
  • Answering questions well on Piazza
  • Organizing study groups
  • Interacting professionally with programming partners and course staff
  • Working out ideas with course staff
  • Helping other students understand the material (but not doing the work for them)

Nobody has to do all of these things; you can earn top grades for class participation by doing just a few things well. In particular, nobody is required to speak in class, but everybody should be prepared to answer questions if called upon. What questions are appropriate? Any question about programming languages. However, it may not be appropriate to insist that every question be tracked to its lair and dispatched. Professional interactions with other students and with course staff are the same as those which are expected in any workplace. It is also professional for you to recognize that a member of the course staff may be present but not actually available to talk about 456.

Homework is critical
In this class, you will learn most of the material on your own as you complete the homework assignments. The importance of homework is reflected in the weight it is assigned in the course grade. Most homework for this course involves short programming assignments. Many of them will be based on the text by Ramsey. There will be also be some larger programming assignments. There will be some theory homework, involving more proving and less programming.

As in most classes (exceptions, you know who you are), it helps to start the homework early. But in 456, starting early will produce unusually good benefits. Many students find if they start early, even if they don't appear to make much progress, a solution will “come to them” while they are doing something else.

Another reason to start early is that if you get stuck, early help is a lot better than late help.

If you complete and understand all the homework assignments, you are almost certain to do well on the exams and earn a high grade. If you miss assignments or don't really understand the homework, it will be difficult for you to earn a satisfactory grade. Extensive details about grades are available online.

Format of homework
Your written work must carry your name, and it must be neat and well organized. We suggest that you prepare your theory homework using LaTeX. We also recommend the mathpartir package. You can download it directly or install it as a Debian package. You can also find out about many other useful LaTeX packages from the LaTeX Companion. There is a second edition, but the link is to the first edition because it's almost as useful and a lot cheaper. If you can't use a computer for your written work, write it by hand and scan it. Any work that cannot easily be read will receive No Credit.

Clear English expression is required; grammar and spelling count. The same requirements apply to exams.

Every assignment should include a README file that describes the work. This description must
  • Identify you by name
  • Identify what aspects of the work have been correctly implemented and what have not.
  • Identify anyone with whom you have collaborated or discussed the assignment.
  • Say approximately how many hours you have spent completing the assignment.

Extra Credit
Many homework assignments will offer opportunities to earn extra credit. Extra credit applies to adjust final letter grades. For example, if your grade average falls in the borderline between A- and B+, the instructor will assign you the higher grade at my discretion if you have done extra-credit work. Extra credit may also be mentioned in letters of recommendation.

Extra credit is just that: extra. It is possible to earn an A without doing any extra credit.

Readability of programming assignments
A solution to a problem is of little value if that solution cannot be understood and modified by others. For that reason, your code will be graded on your explanation of what you are doing, its conformance to coding standards, and your results. This page explains our coding-style expectations in detail.

Programming is a creative process. Individuals must reach their own understanding of problems and discover paths to their solutions. During this time, discussions with friends and colleagues are encouraged—you will do much better in the course, and in your studies, if you find people with whom you regularly discuss problems. But those discussions should take place in English, not in code. If you start communicating in code, you've broken the rules.

When you reach the coding stage, therefore, group discussions are no longer appropriate. Each program, unless explicitly assigned as a pair problem, must be entirely your own work.

Do not, under any circumstances, permit any other student to see any part of your program, and do not permit yourself to see any part of another student's program. In particular, you may not test or debug another student's code, nor may you have another student test or debug your code. (If you can't get code to work, consult a teaching assistent or the instructor.) Using another's code in any form or writing code for use by another violates the University's academic regulations.

Do not, under any circumstances, post a public question to Piazza that contains any part of your code. Private questions directed to the instructors are OK.

Use of the library
You may look in the library (including the Internet, etc.) for ideas on how to solve homework problems, just as you may discuss problems with your classmates. Library sources must be acknowledged when you submit your homework, even if you find little or nothing useful.

Some students rely heavily on the library. Although this is permitted within the letter of the rules, it is better to grapple without heavy reliance on the library. Doing homework is the best way for you to learn. While library skills are important in our profession, the homework in this course develops other skills that are even more important. Remember, you will not have the library with you when you write your exams or go on job interviews!

Wikipedia considered harmful
Wikipedia merits special warning. Wikipedia is a terrible source of information on programming languages. Many of the entries are just plain wrong, and Wikipedia's rules make it nearly impossible for experts to correct bad articles.

Late policy
Homework that is submitted electronically (most homework) will typically be due at 11:59 pm on a Friday. An automatic extension of ten minutes is available at no cost to you. If you plan on submitting your work at midnight, you will have nine minutes for last-minute changes.

Homework is expected to be submitted on time. However, we recognize that the college life occasionally interferes with on-time submission. If you have difficulty getting homework in on time, you have two options:

  • For ordinary difficulties, each student is automatically issued four (4) extension tokens. By spending an extension token, you can get an automatic 24-hour extension on all deadlines associated with a single assignment. Expenditure of extension tokens is governed by these rules:
    • When expending an extension token, you must notify the course staff by email. We must receive this notification before the assignment is due. (Notification ensures that we don't post solutions before all homework is in.)
    • At most ONE extension token may be expended on any single assignment.
    • When you are out of tokens, late homework will no longer be accepted. It will be returned ungraded, and you will receive No Credit for the work.

  • If a serious illness affects your ability to complete homework on time, your first step is to report the illness to us. We will make suitable arrangements.
  • For extraordinary difficulties, such as bereavement, family emergencies, or other extraordinary unpleasant events, your first step should be to make contact with us. You must take this step before the assignment is due. We will make special arrangements that are suited to your circumstances.

Solutions to homeworks will not be released until the last assignment is turned in or until the 24-hour deadline has passed. Students turning homework in on time may have solutions sent to them by sending a request to the course staff.

If we have made a mistake in grading a homework assignment, you have seven days after the return of the assignment to call the mistake to the attention of your TA or instructor. In such cases, we will reassess the entire assignment and assign a new grade. The new grade may be higher or lower than the original grade.

Computer software
The class will be run using Linux, as installed on the departmental servers and in the laboratories in Lawson. For remote access use data.cs.purdue.edu or sslabXX.cs.purdue.edu (for some value of XX starting with 01. The software from the book will be installed on these machines, but you can also grab the software and compile it yourself; try
                  git clone data.cs.purdue.edu:/homes/cs456/book-code

Stupid software tricks
The Linux servers have the wonderful rlwrap program, which is extremely handy for interacting with our interpreters. Try typing, e.g., rlwrap impcore, and you will be able to get an interactive editing loop with the impcore interpreter.
HW 1: Assignment for Unit 1: Introduction, imperative core, ASTs & environments. Due Friday, January 20.

HW 2: Assignment for Unit 2: Operational semantics, metatheory. Due Friday, February 3.

HW 3: Assignment for Unit 3: Scheme: Recursive programming with lists. Due Friday, February 17.

HW 4: Assignment for Unit 4: Scheme II: First-class and higher-order functions, continuation passing. Due Friday, March 3.

HW 5: Assignment for Unit 5: Introduction to ML. Due Friday, March 24.

HW 6: Assignment for Unit 6: Type systems. Due Friday, April 7.

HW 7: Assignment for Unit 7: ML type inference (OPTIONAL). Due Saturday, April 22.