CSCI 365
Functional Programming

Time

MWF 1:10pm - 2:00pm (A6)

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 functions 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

Installing Agda


Calendar

Starting March 4, lectures are available as videos on YouTube.

Date Topic In-class code Notes
W 22 Jan Intro to Haskell HaskellIntro.hs Info Survey, HW 1 assigned
F 24 Jan Guards and lists HaskellIntro.hs  
M 27 Jan Algebraic data types ADTs.hs  
W 29 Jan Propositional logic   HW 2 assigned
F 31 Jan Propositional logic    
M 3 Feb Polymorphism Poly.hs Read CPM Chapters 1–3
W 5 Feb Recursion patterns on lists RecursionPatterns.lhs, PDF  
F 7 Feb Folds MoreRecursionPatterns.hs  
M 10 Feb Fold examples; currying Currying.hs  
W 12 Feb foldNat; induction NatFold.hs  
F 14 Feb induction    
W 19 Feb λ calculus: definitions   Lambda calculus (video)
F 21 Feb λ calculus: encoding bool, nat LambdaCalc.hs, inclass.lc  
M 24 Feb fix Fix.hs  
W 26 Feb Y-combinator ycombinator.lc Y combinator (video)
F 28 Feb STLC and Curry-Howard   Propositions as Types (video)
M 2 Mar Introduction to Agda AgdaIntro.agda Read CPM Chapters 4–6
W 4 Mar More Agda: negation and equality AgdaIntro.agda  
F 6 Mar Agda: iseven, totality, and Curry-Howard AgdaIntro.agda  
M 9 Mar Agda: proving programs correct AgdaIntro.agda  
W 11 Mar Agda: equational reasoning Flatten.agda  
W 18 Mar Agda: with clauses, filter Filter.agda  
F 20 Mar Induction is a dependent fold FoldsInduction.agda  
M 30 Mar Intro to online learning (shared Google doc)    
W 1 Apr Type classes, example (Listable) TypeClasses.hs  
F 3 Apr Kinds, Functor Kinds.hs, Functor.hs  

Coursework

Participation: 100 points

Successful participation in the course means:

Problem sets: 400 points

Problem set submission (codepost.io)


# Name Resources Assigned Due
0 Read the syllabus & fill out Student Info Survey   W 22 Jan F 24 Jan
1 Intro to Haskell   W 22 Jan W 29 Jan
2 ADTs and proofs Proof.hs W 29 Jan W 5 Feb
3 Polymorphism and recursion patterns   W 5 Feb W 12 Feb
4 Idiomatic Haskell and Induction   W 12 Feb W 19 Feb
5 Lambda Calculus λ-calculus shell W 19 Feb W 26 Feb
6 STLC and Curry-Howard STLC.hs W 26 Feb W 4 Mar
7 No HW   W 4 Mar  
8 Agda See Agda installation instructions above W 11 Mar W 1 Apr
9 Type classes ExprT.hs, Parser.hs, StackVM.hs W 1 Apr W 8 Apr

Problem sets will be assigned weekly and due on Wednesday before the start of class. Each problem set will be worth 40 points and will typically have both a written component and a programming component. They will be challenging: you should expect to spend time working on them throughout the week; waiting until the night before a problem set is due is very unlikely to go well.

Problem sets may be completed individually or in groups of up to 3. You may pick your own groups (though I am happy to serve the role of matchmaker if you need help finding a group).

Assignments must be turned in electronically via codepost.io, as one or more .hs, .lhs, and/or .agda files. Written components of the assignment should simply be included as comments.

Each student has three late days to spend throughout the semester as they wish. Simply inform me any time prior to the due date for an assignment that you wish to use a late day; you may then turn in the assignment up to 24 hours late with no penalty. Multiple late days may be used on the same assignment. There are no partial late days; turning in an assignment 2 hours late or 20 hours late will both use 1 late day.

Partners working on an assignment together must each use a late day in order to turn in the assignment up to 24 hours late. Late days are non-transferable.

Quizzes: 240 points

# Date Topic
1 Mon, 3 Feb Haskell basics, list processing
2 Fri, 7 Feb Algebraic data types
3 Mon, 24 Feb Folds
4 Fri, 28 Feb λ calculus
5 Fri, 6 Mar STLC and Curry-Howard

There will be 12 weekly short quizzes (typically on Fridays) testing you on key aspects of the previous week’s problem set. However, note that despite being short, these quizzes will constitute a significant fraction of your final grade (about 25%). Each quiz will be worth 20 points.

Grading of the quizzes will be mastery-based: you can re-take a quiz as many times as you like; each time you retake a quiz the new grade replaces the previous grade. The first iteration of a given quiz will be in class, in written form. 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: 260 points

Overview/important dates

You will complete a final project which will extend or tie 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 explaining what you intend to do. The proposal should be about 1 page, and should clearly explain:

Checkpoint meetings

During the week of April 27–May 1, your group must schedule a 30-minute 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

In the afternoon on Friday, May 8, 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.

Final submission

You may submit your project in one of two ways:

Grading

Grading will be as follows:

Grading Scale

Final grades in the course will be determined on the basis of total points accured, according to the following schedule:

Points Grade
900-1000 A
800-899 B
700-799 C
600-699 D
0-599 F

Commitments

It is my ultimate goal for this course, and my teaching, to develop your academic skills, advance your learning of math and computer science concepts, and support the liberal arts in general. To do so will require commitments from myself and from you toward meeting this goal.

Active Participation

I will be prepared and on time for class each day, ready to use class time to help you understand the course material. I will respectfully listen to, understand, and answer questions asked in class.

You are expected to attend class and actively participate in discussions every day, answering questions, asking questions, presenting material, etc. Your participation will be respectful of your classmates, both of their opinions and of their current point in their educational journey, as we each approach the material with different backgrounds and contexts.

Communication

I will clearly communicate expectations, assignment details and dates, and grading standards. I will respond to emails within 24 hours (including weekends).

You are expected to check your email for occasional course announcements, and to let me know via email if you will need to miss class for some reason.

You should 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.

Constructive Feedback

I will provide graded feedback on assignments (problem sets and quizzes) within one week. I will be available for appointments outside of class and will give you my full attention during meetings. I will be open to feedback and willing to respond in substantive ways to your suggestions or concerns.

You are encouraged to provide constructive comments for improving this course for furthering your learning throughout the semester. You are welcome to submit anonymous feedback at any time. There will also be an opportunity for anonymous course feedback at the end of the term, in which I hope you all participate. Through your feedback I can improve this course and others for future students.

Academic Integrity

I will abide by the above syllabus and grade your work fairly.

As stated in the Hendrix Academic Integrity Policy, all students have agreed to adhere to the following principles:

  • All students have an equal right to their opinions and to receive constructive criticism.
  • Students should positively engage the course material and encourage their classmates to do the same.
  • No students should gain an unfair advantage or violate their peers' commitment to honest work and genuine effort. It follows that any work that a student submits for class will be that student's own work. The amount of cooperation undertaken with other students, the consistency and accuracy of work, and the test-taking procedure should adhere to those guidelines that the instructor provides.
  • Members of the Hendrix community value and uphold academic integrity because we recognize that scholarly pursuits are aimed at increasing the shared body of knowledge and that the full disclosure of sources is the most effective way to ensure accountability to both ourselves and our colleagues.

Learning Accomodation

I will make this classroom an open and inclusive environment, accommodating many different learning styles and perspectives.

Any student seeking accommodation in relation to a recognized disability should inform me at the beginning of the course. 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.

Physical and Mental Health

I am willing to work with you individually when life goes off the rails.

Coursework and college in general can become stressful and overwhelming, and your wellness can be impacted when you least expect it. You should participate in self-care and preventative measures, and be willing to find support when you need it.

  • The Office of Counseling Services welcomes all students to see a counselor in a private and safe environment regardless of their reasons for making an appointment. Counseling services are available to all Hendrix students at no cost.
  • Student Health Services provides free healthcare to Hendrix students. Services are provided by an Advanced Practice Registered Nurse (APRN) in collaboration with a local physician.

The Offices of Counseling Services and Student Health Services are located in the white house behind the Mills Center for Social Sciences at 1541 Washington Avenue.