it-ebooks - Functional Programming Lecture Notes (Chicago CS223)

There will be two primary themes:

1. Implementing and analyzing efficient data structures,particularly in the context of functional programming languages.

2. Functional reactive programming (FRP) for interactive programs.

Why? Well, because all of you have seen at least one functionalprogramming language before (Racket in 151 or Haskell in 161, and perhapsStandard ML in 221 or 226x), there's an implicit "Advanced" or "Topics in"that prefixes the "Functional Programming" name of this course.So, we need to choose some topics to study.

There's certainly plenty of interesting and important topics relatedto data structures, some of which you may have seen in other courses.But probably few of you have seen all of the data structures andanalysis techniques we will cover, and fewer still will have spent muchtime with them in the context of a purely functional language.That's one good topic.

Functional reactivity is a neat idea for building interactive programs.It's not really mainstream yet, so probably few of you have spent muchtime with it before. That's makes for another good topic.

And as it happens, I have wanted an excuse to learn more about both of these,so why not make a course out of it? (I am curious, and so can you!)

The vehicle we will use for programming is Elm, an exciting,new-kid-on-the-block language that features FRP at its core and thatcompiles to JavaScript for browser integration.

The core of Elm, on top of which FRP primitives are built,is a small dialect of ML.

No, not that ML. In our world, ML refers to a family offunctional programming languages, developed since the 1970s,which has served as seminal work for decades of programminglanguage design and engineering work.

I like to think of ML as kind of sitting halfway between Racketand Haskell for several reasons.

• Evaluation Strategy.

  Like Racket and pretty much every language you may know besides Haskell,Elm is eager expressions will be evaluated even when theirresulting values are not immediately, or ever, needed elsewhere inthe program.

  Interestingly, however, we will see that lazy evaluationis actually crucial to building efficient data structures in purelyfunctional languages (i.e. without mutable variables).

  To bridge this gap, Elm (and most other ML dialects) do providemechanisms for lazy evaluation on top of the eager semantics.

• Types.

  Unlike Racket but like Haskell, ML has a static type system that rejectsprograms that might possibly (but not necessarily) fail with certainkinds of run-time errors.

  ML type systems feature a bunch of really neat and powerful features such as parametric polymorphism and automatic type inference but generally do not employ mechanisms like Haskell's type classes.

  Note: there is a statically typed dialect of Racket calledTyped Racket. In fact, designing typed dialects of"dynamic" languages like Racket, JavaScript, Python, etc. is anactive area of programming languages research.

• Side Effects.

  Even when functional programming languages do offer imperative(or impure) features such as mutable variables, their use isdiscouraged and typically used in small, local ways.

  Although both ML and Haskell languages do have features thatproduce side effects, their type systems track such features in verydifferent ways. Such effects typically "go outside" an ML type system,whereas in Haskell effects are recorded in types. Functions of typeInt -> String in ML may possibly perform I/O with the user, butin Haskell they cannot. Instead, such functions would have typeIO (Int -> String) in Haskell.

  Although Elm does not offer mutable variables, we will see othermechanisms that it provides which break out of the purely functionalparadigm.

Practical languages that build on an ML core typically have manyadditional features such as objects, modules, threads, exceptions, laziness, andmany forms of syntactic sugar that help with real-world programming.Popular full-fledged ML dialects include Standard ML,OCaml, and F#.Elm, in comparison, is a much smaller ML language with feweradditional features beyond those for FRP.

This course will feature usual things like homeworks, exams, grades,TAs, etc. See the Course Info page for details.

If you like programming and math (in other words, if you likecomputer science), I think you will like this course.

If you like only courses that are super-polished, however, thenperhaps this course is not for you. This is the first time I'mteaching these topics, some of which, like I said, I will be grokkingfor the first time. In addition, although the Elm language, libraries,and tools are really coming along nicely, it is still a smalllanguage with a small (but helpful!) community. As a resultof these factors, there may be times during the course when youwill have to get your hands a bit dirty. That said, I think we'llhave some fun.