CSE 4510/CSE5400: Special Topics -- Functional Programming (Fall 2017)

General info

Instructor

Ryan Stansifer

Office hours

Check my WWW page for upto date information; you are welcome to send me e-mail.

Lectures

Class meets from 3:30pm to 4:45 Tuesday and Thursday in LNK 255.

Overview

This is a course about programming in functional languages. We will focus on the Haskell programming language. Since there is little exposure to functional languages in the usual curriculum, it is impossible to effectively compare programming in a functional language with programming in an imperative language. In this course we attempt to provide the opportunity to program significant programs in Haskell.

Functional languages are important because they are easier to understand and reason about. They have an important impact on the design of all new programming languages. Imperative languages are based on the needs of the computing machinery, functional languages are closer to the way humans think.

Prerequisites

Students are expected to know how to program in an imperative language like Java, Ada or Pascal, and to know about algorithms and data structures. Such material is taught in CSE 1001, 1002, 2010 in the undergraduate curriculum.

Resources

Some books on Haskell are:

O'Sullivan et al. Bryan O'Sullivan, John Goerzen, and Don Stewart.
Real World Haskell.
Sebastopol, California: O'Reilly Meida, 2008.
ISBN: 978-0-596-51498-3
book cover
Hutton Graham Hutton.
Programming in Haskell.
Cambridge University Press, 2007
ISBN-13 9780521871723
book cover
Okasaki Chris Okasaki.
Purely Functional Data Structures.
Cambridge University Press, 1999
ISBN 0-52166350-4
book cover
Reade Chris Reade.
Elements of Functional Programming.
Addison Wesley, 1989
ISBN 0-201-12915-9
book cover
Michaelson Greg J. Michaelson.
An Introduction to Functional Programming Through Lambda Calculus.
Addison Wesley, 1988
ISBN 0-201-17812-5

A freely-distributed version [400kb, pdf, 241 pages].

For information about Haskell:

For each student the numeric scores for the assignments and exams are recorded. If you have any question about your standing in the class, or if some score has been recorded wrong, please contact me.

It goes without saying that students are expected to take the final exam at the scheduled time during finals week. Also, anyone representing someone else's work as their own, will receive an F for the class. Please keep in mind the CS honor code. If you receive ideas, code, or help from any source, be sure to give proper credit and acknowledgment.

Please note, that copies of some work (homework, projects, exams, etc) for undergraduate classes may be kept on file. This is done for two purposes. For review by ABET, for the purposes of maintaining the accreditation of the CS program, and to detect plagiarism.

Assignments

  1. Read Can Programming Be Liberated from the von Neumann Style?, Backus' Turing award lecture.
  2. Read "Why Functional Programming Matters" by Hughs and the preface to Real World Haskell. Hughes & Sheeran, "Why Functional Programming Matters" At q. v. and Sebastian Funk, "Why Functional Programming Doesn't Matter" q. v. Turn in a 200 word answer to that question in a plain text, say why.txt with reasonable line breaks (60-80 characters); due midnight, Fri, 25 Aug 2017. submit
  3. Read Mathematical Preliminaries by Jean Gallier.
  4. Read Post system handout and also Post system and Propositional Logic. Post systems; exercises 1,2,3,7,9; due Fri, 1 Sep 2017. Additional exercise, call it 'X': Give a Post canonical system for strings with correctly balanced and matched brackets of three types: {[()]}. submit   You may work together on this assignment. Text (txt) files, PDF, or clear images of paper may be submitted electronically.
  5. Learn Haskell, e.g., “Learn You a Haskell for Great Good!”
  6. Grid, due midnight, Fri, 22 Sep 2017
  7. Do the five logic exercises; due Fri, 22 Sep 2017. submit   You may work together on this assignment. Note that one question must be submitted by e-mail.
  8. Additional questions: 6. Haskell data type for general Post systesm. 7. Haskell data type for propositional expressions constructed from two symbols (P and Q) and two binary operators (And and OR). 8. Prove that the set of logical operators And and OR are not truth functionally complete by showing not all 16 truth tables are expressible.
  9. Wave, due midnight, Fri, 29 Sep 2017. submit
  10. Triangle Game; due Friday, 6 Oct 2017. submit
  11. Watch Lambda Calculus by Graham Hutton.
  12. Read Lambda Calculus chapter by Fernandez.
  13. Read Lambda Calculus tutorial by Rojas; exercises 1,2,3,4,5,6,7,8,9,10; due Fri, 20 Oct 2017 submit
  14. Use a tree data structure of your own design to solve Spatial Structures. Due Fri, 3 Nov 2017. You may work in groups. submit
  15. Use a tree data structure of your own design to solve Frequent Values. Due Fri, 17 Nov 2017. You may work in groups. submit
  16. Read Unification Theory. [Too much!]
  17. Read Hindley-Milner in blog by Diehl with Haskell code.
  18. Homework on types. submit
    1. Add type rule for fix.
    2. Add tuples to the langauge and the type rule for them
    3. Encode in Haskell \ x -> (x+x, x=True). Derive, if possible, a typing for it.
    4. Encode in Haskell let f = \ x -> x in (f 3, f true). Derive, if possible, a typing for it.
    5. Encode in Haskell \ g -> let f = g in (f 3, f True). Derive, if possible, a typing for it.
  19. Project Treasure submit
  20. Write an elegant Haskell solution for Gold Leaf. submit
  21. Mosaics; due Friday, 29 Oct 2017. submit
  22. Red-Black Trees
  23. Read Finger Trees by Hinze.
  24. Read The Curse of the Excluded Middle, by Erik Meijer
  25. Read OCaml for the Masses by Minksy.
  26. OCAML at Jane Street
  27. Read Max Subsequence Sum in Haskell.
  28. Read "Lazy Depth-First Search ..." by King and Launchbury.
  29. Sinking Islands submit
  30. Weirich's ICFP 2014 presentation on dependent types and red-black trees. Weirich's talk on .
  31. Baby Blocks, submit
  32. Cow Pinball, dynamic programming submit
  33. Extra Ombrophobic Bovines

Links

Turing Grammar Post

Important Notices

Title IX

What is Title IX?

Title IX of the Educational Amendments Act of 1972 is the federal law prohibiting discrimination based on sex under any education program and/or activity operated by an institution receiving and/or benefiting from federal financial assistance. Behaviors that can be considered “sexual discrimination” include sexual assault, sexual harassment, stalking, relationship abuse (dating violence and domestic violence), sexual misconduct, and gender discrimination. You are encouraged to report these behaviors.

Reporting

Florida Tech can better support students in trouble if we know about what is happening. Reporting also helps us to identify patterns that might arise — for example, if more than one complainant reports having been assaulted or harassed by the same individual. Florida Tech is committed to providing a safe and positive learning experience. To report a violation of sexual misconduct or gender discrimination, please contact Security at 321-674-8111. * Please note that as your professor, I am required to report any incidences to Security or to the Title IX Coordinator (321-674-8700). For confidential reporting, please contact CAPS at 321-674-8050.

Syllabus

"Spookey effects" of lazy evaluation.
minima k xs = take k (sort xs)
From Real World Haskell.

"Evoluation of a Haskell Programmer" List comprehension

quicksort  []    = []
quicksort (s:xs) =
  quicksort[x|x<-xs,x<s]++[s]++quicksort[x|x<-xs,x>=s]