Overview

Although you will probably never need to implement your own full-blown programming language from scratch, thinking in terms of language design is a powerful problem solving technique. In this hands-on course you will develop programming language design and implementation skills through a number of examples, using the Haskell programming languages. Topics to be covered include parsing, type checking, interpreters, abstraction, compositionality, and embedded domain-specific languages. As a final project, each student creates and implements a domain-specific language of their own design.

Learning Goals

Upon completing this course, you will be able to:

• Use structured data, polymorphism, and higher-order functions to write programs in a functional style.
• Discuss and apply tools of elegant language design such as types, compositionality, and abstraction.
• Identify and discuss the components of a language implementation pipeline, such as parsing, type checking, desugaring, compiling, and interpreting.
• Implement a parser, type checker, and interpreter for a functional language based on the simply typed lambda calculus.
• Implement a parser, type checker, and interpreter for an imperative language with assignment, conditional, and iteration statements.
• Design and implement simple domain-specific languages for various domains.

Resources

Haskell

ghcup

Swarm

• For editing Haskell code, I recommend using Visual Studio Code, which has excellent Haskell support. But if you have a different favorite editor, it will probably work with Haskell just fine.

Calendar

Date	Lectures and Modules	Notes
W 22 Jan	Module 0: Introduction to CSCI 360
	Module 1: Introduction to Haskell
F 24 Jan	Haskell in context	CSCI student survey due
M 27 Jan	Module 2: Algebraic data types and pattern-matching	Grading contract due
		Modules 0 and 1 due
W 29 Jan	Algebraic data types and pattern-matching
F 31 Jan	Algebraic data types in context
M 3 Feb	Module 3: Polymorphism and lists	Module 2 due
W 5 Feb	Polymorphism and lists	Swarm tutorials 1-9 (through “Build”) due
F 7 Feb	Polymorphism and lists in context	Project 1 assigned
M 10 Feb	Module 4: Syntax and semantics	Module 3 due
W 12 Feb	Syntax and semantics	Swarm tutorials 10-14 (“Bind notation” through “Define”) due
F 14 Feb	Programming language pipeline
M 17 Feb	No class (Mid-winter break)
T 18 Feb		Module 4 due
W 19 Feb	Module 5: Pretty-printing and parsing	Swarm tutorials 15-18 (“Lambda” through “Conditionals”) due
F 21 Feb	Operator precedence
M 24 Feb	Module 6: Parser combinatorics	Module 5 due
W 26 Feb	Parser combinators	Contract evaluation due
F 28 Feb	Parser combinators	Project 1 due
M 3 Mar	Module 7: Variables	Module 6 due
		Project 2 assigned
W 5 Mar	Variables	Swarm tutorials 19-20 (“First Steps” and “Farming”) due
F 7 Mar	Variables
M 10 Mar	Module 8: Dealing with errors	Module 7 due
W 12 Mar	Dealing with errors
F 14 Mar	Arith with functions
M 17 Mar	Module 9: Dynamic type checking	Module 8 due
W 19 Mar	Dynamic type checking
F 21 Mar	Type systems	Project 2 due
M 24 Mar	No class (Spring break)
W 26 Mar	No class (Spring break)
F 28 Mar	No class (Spring break)
M 31 Mar	Project 3 introduction	Project 3 assigned
	Module 10: Static type checking
W 2 Apr	Static type checking	Module 9 due
F 4 Apr	Static type checking for functions	Contract evaluation due
M 7 Apr	Module 11: IMP	Module 10 due
W 9 Apr	IMP
F 11 Apr	Extending IMP
M 14 Apr	Module 12: Quilt EDSL	Module 11 due
W 16 Apr	Quilt EDSL
F 18 Apr	EDSL examples	Project 3 due
		Final project assigned
M 21 Apr	Module 13: Quilt Deep EDSL	Module 12 due
W 23 Apr	Quilt Deep EDSL	Final project proposal due
F 25 Apr	TBD
M 28 Apr	Programming language history
W 30 Apr	TBD
F 2 May	Module + Project workshop
Th 8 May	Final project presentations

Grading

Grading contracts

In this course, you determine your own final grade: you will prepare and submit for my approval a grading contract explaining your chosen final grade and what you will do to achieve it. You will then earn your chosen final grade by fulfilling the agreed-upon contract.

This may be different than what you are used to. Professor Cathy Davidson of CUNY perfectly sums up the reasons for doing things this way:

The advantage of contract grading is that you, the student, decide how much work you wish to do this semester; if you complete that work on time and satisfactorily, you will receive the grade for which you contracted. This means planning ahead, thinking about all of your obligations and responsibilities this semester and also determining what grade you want or need in this course. The advantage of contract grading to the professor is no whining, no special pleading, on the student’s part. If you complete the work you contracted for, you get the grade. Done. I respect the student who only needs a C, who has other obligations that preclude doing all of the requirements to earn an A in the course, and who contracts for the C and carries out the contract perfectly.

Required components of a grading contract

There is no specific format required for a grading contract, but it must have the following components:

• Your desired course grade. You may choose to contract for an A, B, or C (if you’re wondering about D’s and F’s, see below). Note that your grading contract should not explain the reasons for your choice. I will not judge you because of your choice, and you do not need to justify it: there are as many different valid reasons for choosing to work toward a particular final grade as there are students. If you do wish to explain to me the reasons for your choice—which you are in no way required to do—you may do so in an email, a personal conversation, etc., but it should not go in your contract.

• A description of the work and requirements you will complete, in checklist format. It doesn’t have to be super detailed, but you do have to explicitly include everything. For example, you can’t just say “I will complete all the assignments listed in the syllabus”; you must actually list them. This is so that you and I both know that you are explicitly aware of the requirements, and to help you keep track of what you have completed and what you have yet to complete. You also have some choice in terms of which assignments you complete, so you must record your choice in the contract.

  Note that at the beginning of the semester you may not have a very good idea about this. For example, if you need to complete ten modules, it’s not reasonable to insist that you know which specific modules you plan to complete. However, you can refine your contract over the course of the semester. You just have to put something to start; for example, a reasonable default would be to plan to complete the first ten modules assigned.

Example grading contract

For example, a grading contract might look like this:

My desired course grade in Programming Languages is a C. To achieve this grade, I will complete the following:

• CSCI student info survey
• Grading contract
  • Submit grading contract
  • Grading contract evaluation 1
  • Grading contract evaluation 2
• Modules (8)
  • Module 0
  • Module 1
  • Module 2
  • Module 3
  • Module 4
  • Module 5
  • Module 9
  • Module 10
• Projects
  • Project 1 (Level 2)
  • Project 2 (Level 1)
  • Project 3 (Level 1)
• Swarm scenarios (60%)

Grading contract submission

You must turn in an initial proposed grading contract by the start of class on Monday, January 27. After the initial submission, I may require some revisions before I approve your contract.

Contract evaluation and adjustment

Two times during the semester (Wednesday, February 26 and Friday, April 4) you are required to reflect on your progress in the course and complete an evaluation of your work, comparing it against what you agreed to in your grading contract. Your evaluation should:

1. Contain a copy of your original grading contract, with items you have completed checked off.

2. Revise your grading contract with more specific details as appropriate, for example, regarding which modules and projects you intend to complete.

3. Include a 1-2 paragraph reflection, which answers questions such as the following:

   • What have you done well?
   • What have you learned?
   • What could you do to improve your learning?
   • What could I (the instructor) do to improve your learning?
   • Are there ways in which you have not lived up to the requirements of your contract, and if so, what steps are you taking, or will you take, to rectify that?

Your evaluation is also an opportunity to request an adjustment to your contract in either direction. If you find that you will be unable to meet the obligations of your contract, you may request to move to the next lowest grade and its requirements. Contrariwise, if you find that you’ve been performing above the obligations of your contract, you may request to fulfill the requirements for the next higher grade.

Note, however, that you don’t have to wait for an evaluation to adjust your contract. If your life has really gone off the rails (or if, say, you are finding the class easier and more enjoyable than you thought!) just come and talk to me about adjusting your contract.

A, B, and C grades

• To earn an A in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Complete at least 12 modules.
  • Earn at least 10 project points.
  • Complete all 25 assigned Swarm scenarios.
• Or, to earn a B in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Complete at least 10 modules.
  • Earn at least 7 project points.
  • Complete at least 20 Swarm scenarios.
• Or, to earn a C in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Complete at least 8 modules.
  • Earn at least 4 project points.
  • Complete at least 15 Swarm scenarios.

D and F grades

[Adapted from Cathy Davidson.] You cannot intentionally contract for a grade of D (and certainly not for an F). However, I reserve the right to award a grade of D or F to anyone who fails to meet their contractual obligations in a systematic way. A “D” grade denotes some minimal fulfilling of the contract; an “F” denotes absence of enough satisfactory work, as contracted, to warrant passing of the course. Both a “D” and “F” denote a breakdown of the contractual relationship.

Modules

Much of your learning in the course will take place through modules which will be started during class time in teams of 2 or 3. Each module will guide you through a learning process on a particular topic. Modules not completed during class time should be completed with your group outside of class. Completed modules will generally be due by the end of the day on the first Monday after the module was assigned.

Submitted modules will be graded on a credit/no credit basis. Modules not receiving credit may be revised and resubmitted for 1 token per group member.

A submitted module will either receive credit or no credit based on whether it is complete and correct. Submitted modules will receive a credit/no credit grade and feedback within two business days of submission.

Projects

There will be four projects available to complete throughout the semester. These projects will give you a chance to demonstrate and apply the things you have learned through the modules.

• Unlike modules, projects must be completed individually. Since this is the one and only opportunity for you to demonstrate individual mastery of the material, academic integrity should be taken especially seriously.

• Each project will have three levels (Level 1, 2, 3) to which it can be completed, with each level building on the previous level. Generally speaking:
  • A Level 1 project is a “bare bones” project containing a satisfactory implementation of the core ideas.
  • A Level 2 project is a more complete and polished implementation, with some extra features.
  • A Level 3 project stretches beyond the basic requirements of the project into one or more advanced topics or features.

• The levels earned on all projects are added to yield total project points. For example, if you complete one project to Level 1 and two other projects to Level 2, you have earned 5 project points.

• Each project will be evaluated via specifications (a set of criteria) for each level. Projects meeting all the criteria for a given level will receive credit for that level; projects that do not meet all the criteria will not receive credit for that level.

Swarm

Some weeks, you will be assigned Swarm scenarios to complete. See the Swarm github repo for instructions on building Swarm from source.

For each scenario or scenarios completed, you should submit:

• A .sw file containing your code for the challenge, if appropriate

• A screenshot showing the relevant scenarios completed, like this:

  

Tokens do not need to be spent to turn in Swarm scenarios late.

Creating Swarm challenge scenarios

Take a look at the scenario authoring guide for help on creating your own scenarios.

Tokens, late submissions, and resubmissions

Each student starts the semester with five virtual tokens which they can spend however they wish. Tokens are non-transferable.

• 2 tokens may be spent to turn in any assignment late.
  • All assignments must be submitted at the latest by Friday, May 9 at 5pm.
• 1 token may be spent to submit a revised homework assignment or project at any time.
• Note that group members must spend two tokens each to turn in a late module, or 1 token each to turn in a revised module.
  • If one group member does not have enough tokens, don’t let it stop you from submitting a late or revised module: that group member will simply not be eligible to get credit for the module until they obtain sufficient tokens.

Conversely, additional tokens may be earned in the following ways:

• Scheduling and attending an office hours meeting with Dr. Yorgey earns 1 token per student (thus, attending an office hours meeting as a group earns one token for each group member).
• Creating a Swarm challenge scenario that gets merged to the main branch earns 5 tokens. (Note, the process of review and revision may take a while, so do not try to do this at the last minute!)
• Creating an educational video for the course earns 4 tokens.
  • Videos should be around 2-4 minutes long and cover a single topic.
  • The audience for videos should be other students in the course (or students in a future offering of the course).
  • Feel free to be creative in how you record the video and what kinds of visual aids you use. For example, you might record yourself writing on a whiteboard, or on a piece of paper; or you could record your screen while you type, or draw; you could create some slides or animations to display.
  • With your permission, and appropriate attribution, videos you create will be posted to the course website.

Expectations

Although you and I play different roles in the course, we both have your learning as a common goal. There are things I expect from you as a student in the course, but there are also things you can expect of me as the course instructor and facilitator.

If I am not fulfilling my responsibilities outlined below, you are welcome (and encouraged!) to call me out, perhaps via the anonymous feedback form. I will also initiate a conversation if you are not fulfilling yours. However, none of us will meet all of the expectations perfectly—me included!—so it’s also important that we have grace and patience with one another.

Attendance

Attendance in this class is expected, though not required as part of your grade. I appreciate you letting me know when you will need to miss class. Also, if you have been working in a group and need to miss class, it is courteous to let me and your group members know so that we can reassign groups if necessary.

Academic integrity

Hendrix College is committed to high standards of honesty and fairness in academic pursuits. Such standards are central to the process of intellectual inquiry, the development of character, and the preservation of the integrity of the community. Please familiarize yourself with the statement of Academic Integrity.

You should also familiarize yourself with the Computer Science-specific Academic Integrity Policy.

Disabilities

If you have a documented disability or some other reason that you cannot meet the above expectations, and/or your learning would be best served by a modification to the usual course policies, I would be happy to work with you—please get in touch (via Teams or email)! The course policies are just a means to an end; I don’t care about the policies per se but I do care about you and your learning.

It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Students should contact Julie Brown in the Office of Academic Success (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student seeking accommodation in relation to a recognized disability should inform the instructor at the beginning of the course.

Diversity and Inclusion

Hendrix College values a diverse learning environment as outlined in the College’s Statement on Diversity. All members of this community are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the community. If you believe you have been the subject of discrimination please contact the Dean of Students Office (Donna Eddleman, eddleman@hendrix.edu, 501-450-1230 ) or the Title IX Coordinator (Jennifer Fulbright, fulbright@hendrix.edu, 501-505-2901). If you have ideas for improving the inclusivity of the classroom experience please feel free to contact me. For more information on Hendrix non-discrimination policies, visit hendrix.edu/nondiscrimination.

Mental and Physical Health

Hendrix recognizes that many students face mental and/or physical health challenges. If your health status will impact attendance or assignments, please communicate with me as soon as possible. If you would like to implement academic accommodations, contact Julie Brown in the office of Academic Success (brownj@hendrix.edu). To maintain optimal health, please make use of free campus resources like the Hendrix Medical Clinic or Counseling Services (501.450.1448). Your health is important, and I care more about your health and well-being than I do about this class!