CSCE 590: Topics in Information Technology: Functional Programming (Fall 2021)

Syllabus (pdf, 2021-08-17)

Office Hours are on Monday from 1430-1730.

Useful Links for Reference materials:

  • Graham Hutton. Programming in Haskell. Cambridge University Press, Second Edition, 2017 (required text, referred to as [H]). Supplementary materials from the author, including an errata list, are available.
    1. Here is the direct link for Chapter 11 ("The Countdown Problem") lecture.
    2. Here is the direct link for the countdown program code, in literate Haskell format.
  • The secondary textbook is: Richard Bird. Thinking Functionally with Haskell, Cambridge University Press, 2015 (referred to as [TFWH]). It can be accessed with university credential here (https://pascal-usc.primo.exlibrisgroup.com/permalink/01PASCAL_USCCOL/1volnn1/alma991025950382505618). Supplementary materials from the author, including an errata list, are available.
  • A third recommended book on Haskell, which is useful as a reference, is: Bryan O'Sullivan, John Goertzen, and Don Stewart. Real World Haskell, O'Reilly, 2009 (referred to as [RWH]). This book can be accessed freely here (http://book.realworldhaskell.org/).
  • This rather difficult book has examples of good advanced functional programs. Each chapter solves a problem with a functional program. Richard Bird. Pearls of Functional Algorithm Design. Cambridge University Press, 2010. This book can be accessed freely (but not downloaded in full) here (https://pascal-usc.primo.exlibrisgroup.com/permalink/01PASCAL_USCCOL/1oceqbt/alma9911169484905611).
  • Lecture Log

    Lecture Notes
    Notes for Ch.15 [H] with additional slides on Section 16.7 on Strict Application (pptx)
    Notes for Ch.16 [H] (pptx)
    Programming Paradigms (pptx)

    Homework, Tests, and Programs

  • Important Addition to the Statements on Plagiarism and Academic Honesty (2020-08-25, modified 2020-09-05): Notwithstanding other provisions in the syllabus, you are allowed to consult and use the solutions in Appendix A ("Selected Solutions") [H] and answers in [TFWH] when working on your assignments. You are also allowed to use the supplementary material provided at http://www.cs.ox.ac.uk/publications/books/functional/.
  • Points per assignment.
  • See the lecture log for assignments not listed below.
  • Note concerning exercise 11.2 [H], part of HW11:
    The code for exercise 11.2 [H] needs System.Random. This had to be installed, because it is no longer in the default distribution. I could not install System.Random using cabal. I could, however, run the program using stack. Here are two ways I could do it, where ">" is the PowerShell prompt, and the file with the program is ex11p2_2016.hs First way:
    > stack ghci --package random
    in PowerShell (Windows Terminal); ghci starts
    Load program in ghci with :l ex11p2_2016.
    Second way:
    > stack install random
    > stack ghci
    Load program in ghci with :l ex11p2_2016.
  • HW6, based on a video lecture by John Backus,

    Haskell Information

    Some useful links:
    In this class, we write dates according to ISO Standard 8601.
    Brian Hayes. "The Semicolon Wars." _American Scientist_, July-August 2006, pp.299-303. Local copy, pdf.
    "An Introduction to Formal Semantics", Ch. 9 from: Carlo Ghezzi and Mehdi Jazayeri. Programming Language Concepts, 2nd. ed. Wiley, 1987. Some notes on denotational semantics. Example of denotational semantics for a program with a while loop.
    Philip Wadler, "Monads for Functional Programming" (pdf, local copy; bibliographical details at the bottom of the first page). Chapter 5 (especially starting with section 5.2) mirrors the presentation in Chapter 8 [H]. The beginning of Section 5.4 specifies the unit and * operations needed to define a monad. The discussion at the beginning of Section 5.12 explains that these operations have the monad properties, and therefore the parsers of Chapter 8 [H] are monads: "The empty parser and sequencing correspond directly to unit and *, and the monads laws reflect that sequencing is associative and has the empty parser as a unit. The failing parser and alternation correspond to zero and (XOR), which satisfy laws reflecting that alternation is associative and has the failing parser as a unit, and that sequencing distributes through alternation."
    Philip Wadler, "Propositions as Types" (video, September 25-26, 2015). Related paper: Philip Wadler. "Propositions as Types." Communications of the ACM, 58, 12, 75-84 (December 2015). ( Long version from author's website (pdf))
    Functional Programming in the Real World.
    Repository of Code for: Cristina Videira Lopez. Exercises in Programming Style. CRC Press, 2014.
    Parnas D.L. (December 1972). "On the Criteria To Be Used in Decomposing Systems into Modules" (PDF). Comm ACM 15 (12): 1053-1058 (local copy).
    Derek Partridge and Yorick Wilks. "Does AI Have a Methodology Different from Software Engineering?" Technical Report MCCS-86-53 (1986), Computing Research Laboratory, University of New Mexico (local copy).
    Computer Language History web site by Eric Levenez
    The Ariane 5 launch disaster.
    Local copy of: Adrion, W.A., M.A. Branstad, and J.C. Cherniavsky. "Validation, Verification and Testing of Computer Software." ACM Computing Surveys, 14, 2 (June 1982), pp.159--192.
    Local copy of: Rajlich, V., N. Wilde, M. Buckellew. and H. Page. ``Software Cultures and Evolution.'' _Computer_, 34, 9 (September 2001), pp.24--28.
    C.A.R. Hoare. "Retrospective: An Axiomatic Basis for Computer Programming." _Communications of the ACM_, 52, 10 (October 2009), pp.30-32.
    C.A.R. Hoare. "An Axiomatic Basis for Computer Programming. _Communications of the ACM_, 12, 10 (October 1969), 576-580.
    John McCarthy. "A Micromanual for LISP---Not The Whole Truth." ACM SIGPLAN Notices, Vol. 13, Issue 8 (August 1978), Pages 215-216 (local copy)
    The Simplesem interpreter
    : unzip, and follow the instructions in readme.txt. This is a Java implementation that seems robust and will run in Windows.
    Carter Bays's FP interpreter
    John Backus. "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs." Communications of the ACM, 21, 8 (August 1978), 613-641
    John Backus: Function Level Programming and the FL Language: a 1987 lecture on FP by John Backus.
    Boyko Bantchev's List of Interviews with Programming Language Creators from Computerworld's series "The A-Z of Programming Languages (pdf)
    A to Z of Programming Languages Index
    J.W. Backus. "The 701 Speedcoding System." Journal of the ACM, 1, 1, pp.4-6, 1954 (local copy).
    A site with a short program written in many languages, not including FP.
    A site with another short program written in several languages..
    Examples of APL code
    John McCarthy, developer of LISP, wins the Franklin Medal
    John McCarthy's Obituary from the _New York Times_, 2011-10-25 (local copy).
    Dennis Ritchie's Obituary from the _New York Times_, 2011-10-13 (local copy).
    Alain Colmerauer's obituary from _CACM_, 2017-05-22
    Joe Armstrong. "Erlang." Communications of the ACM, Vol. 53 No. 9 (September 2010), Pages 68-75.. This article describes the notion of dynamic code upgrade.
    Pascal Rigaux's Diagrams of Programming Language History.
    Eric Levenez's Genealogy of Programming Languages.