Course Overview

Q: What will we study in this course?

There will be two primary themes:

Implementing and analyzing efficient data structures, particularly in the context of functional programming languages.
Functional programming for interactive web applications.

Why? Well, because all of you have seen at least one functional programming language before (Racket in 151 or Haskell in 161, and perhaps Standard 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 related to data structures, some of which you may have seen in other courses. But probably few of you have seen all of the data structures and analysis techniques we will cover, and fewer still will have spent much time with them in the context of a purely functional language. That's one good topic.

And it turns out there's a new, exciting, functional programming language that makes it easy to write reliable code that compiles to JavaScript and runs in the browser. It's not quite mainstream yet, but it's a great example of how functional programming can be useful in the real world. That makes for another good topic.

Q: What language will we use?

The vehicle we will use for programming is Elm, an exciting, new-kid-on-the-block language that features typed, functional programming with mechanisms for event handling that makes writing interactive web applications sane. I sometimes describe Elm as a small dialect of ML.

Machine Learning... huh?

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

I like to think of ML as kind of sitting halfway between Racket and 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 their resulting values are not immediately, or ever, needed elsewhere in the program.

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

To bridge this gap, most ML dialects provide mechanisms for lazy evaluation on top of the eager semantics. (Elm does not.)

Types

Unlike Racket but like Haskell, ML has a static type system that rejects programs that might possibly (but not necessarily) fail with certain kinds 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 called Typed Racket. In fact, designing typed dialects of "dynamic" languages like Racket, JavaScript, Python, etc. is an active area of programming languages research.

Side Effects

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

Of course both ML languages and Haskell have features that produce side effects, but their type systems track such features in very different ways. Such effects typically "go outside" an ML type system, whereas in Haskell effects are recorded in types. For example, in ML the types of functions for performing I/O might look like:

printLine : String -> ()
readLine  : () -> String

But these very same function types are used also to describe many functions that perform no I/O at all! Instead, in Haskell, these functions might described something like:

printLine : String -> IO ()
readLine  : () -> IO String
readLine  : IO String

The type "IO T" says that the given expression has type T and the evaluation of the expression may (or may not) perform some I/O. So, in addition to data structure invariants and the input-output behavior of functions, types like these explicitly track the I/O effect — and others (such as exceptions, and reading and writing to mutable variables) — within the type system.

The primary effect of an Elm program is to render an interactive web application. As we'll see, the type

main : Program Flags Model Msg

of such an application explicitly tracks the kinds of interactions it may have (e.g. the messages Msg that may be produced) with the surrounding JavaScript and browser environment.

What makes Elm a "small" dialect?

Practical languages that build on an ML core typically have many additional features — such as objects, modules, threads, exceptions, laziness, and many forms of syntactic sugar — that help with real-world programming. Popular full-fledged ML dialects include Standard ML, OCaml, F#, and Reason ML. In comparison to these languages, Elm is, by design, much smaller but provides an effect system at its core that does great for event-based programming.

Q: What else should I know?

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

cs223