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, with a unifying focus on recursion. It combines 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

Additional resources for learning Haskell

Haskell reference


Calendar

Assignment submission form Haskell style guide


Date Topic In-class code Notes
W 19 Jan Intro to Haskell Haskell.hs  
F 21 Jan Lists part 1 part 2 Haskell.hs  
       
M 24 Jan Algebraic data types ADT.hs  
W 26 Jan Thinking functionally; inference rules FunctionalThinking.hs  
F 28 Jan Propositional logic    
       
M 31 Jan Propositional logic, part 2    
W 2 Feb Polymorphism Polymorphism.hs  
F 4 Feb No class (snow)    
       
M 7 Feb List recursion patterns RecursionPatterns.hs  
W 9 Feb Folds RecursionPatterns.hs  
F 11 Feb Currying Currying.hs  
       
M 14 Feb λ calculus: definitions   Lambda calculus (video)
W 16 Feb λ calculus: encoding bool Church.hs  
F 18 Feb λ calculus: encoding bool, nat Nat.hs  
       
W 23 Feb fix and the Y combinator Fix.hs Y combinator (video)
F 25 Feb Simply typed lambda calculus    
       
M 28 Feb The Curry-Howard isomorphism    
W 2 Mar Introduction to Agda Agda workspace  
F 4 Mar More Agda: negation and equality intro.agda  
       
M 7 Mar More Agda: isEven    
W 9 Mar Agda: proving properties of functional programs    
F 11 Mar Agda: equational reasoning eqreasoning.agda  
       
M 14 Mar Review    
W 16 Mar No class    
F 18 Mar STLC in Agda STLC.agda  
       
M 28 Mar Wholemeal programming Wholemeal.hs  
W 30 Mar no class    
F 1 Apr More wholemeal programming Wholemeal.hs  
       
M 4 Apr Type classes TypeClasses.hs  
W 6 Apr Monoids TypeClasses.hs  
F 8 Apr Monoidal trees Tree.hs Monoids and finger trees
       
M 11 Apr Kinds and Functor Kinds.hs Functor.hs  
W 13 Apr More Functor instances Functor.hs  
F 15 Apr Semantic editor combinators Functor.hs  
       
M 18 Apr Introduction to Applicative Applicative.hs  
W 20 Apr More Applicative Applicative.hs  
F 22 Apr Yet More Applicative Applicative.hs  
       
M 25 Apr Making a Haskell app, part 1 guess.tgz  
W 27 Apr Making a Haskell app, part 2 guess2.tgz  
F 29 Apr Making a Haskell app, part 3: hangman hangman.tgz  

Coursework and policies

Specifications grading

This course uses specifications grading. Briefly, this means that grading of individual assignments is on a credit/no-credit basis, with a specification that tells you what you must do in order to get credit. Your final letter grade in the course, in turn, is determined by the below specification that says what you must complete in order to get each letter grade.

Grade Specification
A Complete all modules to level 2
  Complete a final project
   
B Complete all but one modules, at least half to level 2
  Complete a final project
   
C Complete all but two modules to level 1
   
D Complete at least half of the modules to level 1

Due dates policy

Submission policies

Modules

Assignment submission form Haskell style guide


There will be a number of modules corresponding to topics in the course. Each module consists of one or more problem sets, a quiz, and occasionally some other small assignments. Each module can be completed to one of two levels:

Each individual module specifies what you need to do to get Level 1 or Level 2 credit. For example, there may be an extra challenge problem set and/or reading you must complete to get Level 2 credit.

# Module Resources Assigned Due
1 Introduction to Haskell   W 19 Jan W 26 Jan
2 ADTs and proofs Proof.hs W 26 Jan W 2 Feb
3 Polymorphism and recursion patterns   W 9 Feb W 16 Feb
4 Lambda calculus lc.tgz, bool.lc W 16 Feb W 23 Feb
  No module week of 23 Feb      
5 STLC and Curry-Howard STLC.hs, survey W 2 Mar W 9 Mar
6 Agda   M 14 Mar W 30 Mar
7 Wholemeal programming   W 6 Apr W 13 Apr
8 Monoids starter code W 13 Apr W 20 Apr

Quizzes

There will be 12 weekly short quizzes (typically on Wednesdays) testing you on key aspects of the previous week’s problem set.

Quizzes will be graded on a credit/no credit basis, but you can re-take a quiz as many times as you like until getting credit.

The first opportunity to take a given quiz will be in class, in written form (however, you need not take it if you do not feel prepared). To retake a quiz, just schedule a 15-minute meeting slot, being sure to clearly indicate which quiz or quizzes you intend to retake.

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. A final project is required to get an A or B in the course.

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 Monday, April 18th 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.

Checkpoint meetings

During the week of April 25–29, your group must schedule a meeting with me to discuss your progress, ask questions, etc. (of course I am happy to meet with you at other times as well.)

Presentations

During the afternoon on Friday, May 6, you will give a 15–20 minute presentation on 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

To get credit for your project, you must meet the following criteria:

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!