CSCI 365
Functional Programming

Time

MWF 8:10pm - 9:00am (A1)

Location

MC Reynolds 317

Instructor

Dr. Brent Yorgey
yorgey@hendrix.edu
(501) 450-1377
Office Hours

Image by Chor Ip, CC-BY-SA-2.0

Overview

Functional programming takes as its central organizing principle the idea of evaluating expressions rather than executing instructions. It supports programming at a high level of abstraction and carefully controlling side effects, which are critical given the ever-increasing sophistication of software systems. This course explores functional programming in depth, combining practical programming experience in Haskell with a deep exploration of the underlying theory. Covered topics include algebraic data types and pattern matching, static type systems, recursion and induction, folds, lambda calculus, laziness, functors, and monads. A few weeks will also be spent learning about computer-checked formal proofs using the dependently typed functional language/proof assistant Agda.

Learning Goals

Upon completing this course, you will be able to:


Resources


Calendar

Assignment submission form Haskell style guide


Date Topic Code Reading & Links Due
W 17 Jan No class (snow)      
F 19 Jan Rewriting systems stream pdf   Verse Language Reference Grading contract
        CSCI student info survey
         
M 22 Jan Substitution; Haskell types and functions stream pdf HaskellIntro.hs CFP Chapters 1 & 2  
W 24 Jan Functions youtube HaskellIntro.hs CFP Chapters 2 & 3  
F 26 Jan More functions, tuples, recursion stream HaskellIntro.hs   PS 1: Rewriting
         
M 29 Jan Algebraic data types and pattern matching stream ADT.hs    
W 31 Jan Algebraic data types and polymorphism stream ADT.hs    
    Polymorphism.hs    
F 2 Feb Polymorphism stream Polymorphism.hs   PS 2: Functions & Haskell
         
M 5 Feb Lists and list comprehensions stream Lists.hs CFP Chapters 5 & 6  
W 7 Feb Standard list functions stream Lists.hs CFP Chapters 6 & 7  
F 9 Feb More list functions stream Lists.hs   PS 3: ADTs and polymorphism
         
M 12 Feb Higher-order functions and recursion patterns stream RecursionPatterns.hs CFP Chapter 10  
W 14 Feb More recursion patterns, foldr stream RecursionPatterns.hs CFP Chapters 10 & 11  
F 16 Feb Wholemeal programming stream Wholemeal.hs CFP Chapter 11 PS 4: Lists
         
M 19 Feb No class (Mid-winter break)      
W 21 Feb I/O stream SideEffects.py    
    IO.hs    
Th 22 Feb       Grading contract evaluation I
F 23 Feb More I/O stream IO.hs   PS 5: Higher-Order Functions and Recursion Patterns
         
M 26 Feb Case expressions & currying stream Case.hs    
    Currying.hs    
W 28 Feb Type classes stream TypeClasses.hs    
F 1 Mar Semigroups & monoids stream Monoids.hs   PS 6: I/O
         
M 4 Mar More monoids, newtypes stream Monoids.hs   Project 1
W 6 Mar No class (Dr. Yorgey sick)      
F 8 Mar No class (Dr. Yorgey sick)      
         
M 11 Mar Kinds & functors stream Kinds.hs    
    Functor.hs    
W 13 Mar Functors stream Functor.hs   PS 7: Type classes and monoids
F 15 Mar Laziness stream Laziness.hs    
         
M 18 Mar Spring break      
         
M 25 Mar Applicative stream Applicative.hs    
W 27 Mar More Applicative stream Applicative.hs    
F 29 Mar Applicative examples stream Applicative.hs    
         
M 1 Apr Scanner stream Scanner.hs    
W 3 Apr Introduction to Monads stream Scanner.hs    
    Monad.hs    
    MonadInstances.hs    
Th 4 Apr       Grading contract evaluation II
F 5 Apr Monads stream Monad.hs   PS 8: Applicative
         
M 8 Apr No class (solar eclipse)      
T 9 Apr       Final project proposal
W 10 Apr Lambda calculus stream pdf      
F 12 Apr More lambda calculus stream LambdaCalc.hs    
    nat.lc    
    lc.tgz    
S 13 Apr       PS 9: Monad
         
M 15 Apr Introduction to Agda stream intro.agda    
W 17 Apr More Agda, Curry-Howard Isomorphism stream agda intro.agda    
F 19 Apr Agda, proving properties of addition stream intro.agda   PS 10: Lambda calculus
         
M 22 Apr Agda, proving properties of programs stream programs.agda    
W 24 Apr Simply typed lambda calculus, encoding type systems in Agda stream agda pdf LambdaCalc.agda    
F 26 Apr Encoding STLC in Agda stream agda LambdaCalc.agda    
         
F 3 May Final project presentations (2-5pm)     Final project

Grading

Grading contracts

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:

Example grading contract

For example, a grading contract might look like this:

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

Grading contract submission

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

Contract evaluation and adjustment

Two times during the semester (Thursday, February 22 and Thursday, 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 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 a lower 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 a 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

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 (typically, I would want to see at least 5 projects complete). 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.


Coursework and policies

Problem sets

12 weekly problem sets will be assigned, with a mix of coding and written exercises. Problem sets will generally be assigned and due each Friday. Coding exercises must be submitted in .hs or .lhs format; written exercises must be submitted as a .pdf.

Assignment submission form
# Topic Assigned Due
1 Rewriting and substitution F 19 Jan F 26 Jan
2 Functions & Haskell F 26 Jan F 2 Feb
3 ADTs & Polymorphism F 2 Feb F 9 Feb
4 Lists F 9 Feb F 16 Feb
5 HOFs & Recursion Patterns F 16 Feb F 23 Feb
6 I/O F 23 Feb F 1 Mar
7 Type classes and monoids S 2 Mar W 13 Mar
  dickens-editor.tgz    
8 Applicative F 29 Mar F 5 Apr
  AParser.hs, SExpr.hs    
9 Monad S 6 Apr S 13 Apr
  risk.tgz    
10 Lambda calculus F 12 Apr F 19 Apr
  lc.tgz    

Projects

In addition to problem sets, there will be two larger coding projects in the course.

Each project will be worth up to 3 points, depending on the level to which it is completed. Each project will have a specification explaining what you must do to complete the project to each level. Generally speaking, level 1 denotes a minimal completion of the basic learning objectives for the project, level 2 denotes a fuller completion of the learning objectives, and level 3 requires some extra depth.

Projects may be completed individually, or in groups of up to 3. However, note that in order to get an A or B in the course, you must complete at least one project individually.

Project Assigned Due
Project 1: Game M 12 Feb M 4 Mar
Final project M 1 Apr F 3 May

Tokens

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

Conversely, additional tokens may be earned at any time:

Final project

Overview/important dates

You may complete a final project which extends or ties together some of the things we have learned over the course of the semester.

Important dates:

Format

You may work by yourself, or in groups of up to three students. Groups of five are right out.

You have quite a bit of latitude in what sort of project you choose to complete (subject to approval, of course). Possible types of projects include (but are not limited to):

Your project should somehow go beyond what we have covered in class, that is, completing the project should require you to learn something new.

Project proposal

You must submit a project proposal by Tuesday, April 9th explaining what you intend to do. The proposal should be about 1 page, and must clearly explain:

I will provide feedback on your proposal to ensure that your project is at an appropriate level of difficulty.

Presentations

During the afternoon on Friday, May 3, you will give a short presentation of your project. The presentation could take many forms depending on the type of project. For example, it could just be a demo, if you primarily produced some sort of artifact; it could be a presentation with slides or a chalkboard talk explaining something.

Since giving a good presentation is not really a learning goal of this course, there is no particular specification or set of criteria that a presentation must meet. However, here are some suggestions for giving a good presentation:

Final submission

You may submit your project in one of two ways:

Specification

I will provide feedback on final projects that do not meet the specifications, allowing you an opportunity to address the issues and turn in a revised project.

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.

What I expect from you What you can expect from me
Communication
  • Check your email and Teams for occasional course announcements.
  • Let me know via email or Teams message if you will need to miss class for some reason.
  • Let me know as soon as possible if you feel you are struggling, would like extra help, or have something going on that will affect your engagement in the course or your ability to fulfill your responsibilities.
  • Clearly communicate expectations, assignment details and dates, and grading standards.
  • Return grades and feedback on submitted work within two weekdays of submission.
  • Respond to emails within 24 hours.
Preparation
  • Come prepared to fully engage in class meetings, with distractions minimized, to the best of your ability.
  • Spend time outside of class actively practicing unfamiliar or shaky concepts or skills (not just reading over notes).
  • Have a concrete plan for how we will spend each class meeting, prepared to lead you through the plan.
Engagement
  • Make myself available to meet outside of class, and give you my full attention during a meeting.
  • Be committed to your learning, open to feedback and willing to respond in substantive ways to your suggestions or concerns.

Attendance

Attendance in this class is not required as part of your grade. However, I do expect you to attend and appreciate knowing in advance if you will need to miss class.

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 Dean Mike Leblanc at leblanc@hendrix.edu or 501-450-1222 or the Title IX Coordinator Allison Vetter at titleix@hendrix.eduor 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!