15-150: Principles of Functional Programming

I found the regular expression package as a first thing to make in SML waaay too complex. You already need to have a good understanding of the elements of SML syntax to understand how it works. This is definitely not for SML beginners. I recommend "Elements of ML Programming" by Jeffrey D. Ullman for people starting to learn SML. It too has some corners, that are less great for not so mathematically inclined people, but you will definitely learn the language and have exercises.

That's how I felt when I discovered FP after more than two decades writing procedural and OO code. It felt like I'd found a secret room where all the reasoning was kept.

Do you if any of the course material is available online or as a MOOC?

Partial template source of the slides is available at https://github.com/jacobneu/150lectureNotes (For the uninitiated, it's a Beamer theme, compiled with LaTeX)

Some assembly required; use the instructions from https://github.com/jacobneu/alleycat as inspiration, use the scripts (e.g. startLecture) and Makefile in /crucible

Unfortunately, it does not. These lectures are "mine", in the sense that I developed all of them myself, but the homeworks and lab exercises are the combined efforts of generations of TAs and instructors from the past. It wouldn't be right for me to give them away. (they are also reused from time to time, so there are academic integrity concerns with that also)

If you get to around lecture 9, a classic example I always tell people to start with is a calculator!

For instance, here's the SML code for it:

``` datatype exp =

    Num of int

  | Plus of exp * exp

  | Minus of exp * exp

  | Times of exp * exp

  | Div of exp * exp

Implement the function `eval : exp -> int`, which evaluates the expression as best as it can. Assume no division by zero.

Extra credit: Can you implement `eval' : exp -> int option`, that returns `SOME n` if the expression evaluates, and `NONE` if it divides by zero?

Not exactly exercises, but there's https://smlhelp.github.io/book/docs/ which supports the course and explains each of the concepts as well as library documentation at the official class site, http://www.cs.cmu.edu/~15150/resources.html

It looks like their current workflow keeps exams and homeworks off the internet effectively, but there's a 6-year-old codebase at https://github.com/zhengguan/15150-1 with 10-year-old homeworks and such.

Rewriting standard list functions (map, fold, sum, etc.) is a good entry-level exercise.

A λ-calculus interpreter can be used as an intermediate level exercise. It is in particularly valuable in the context of solidifying one's understanding of functional programming.

You can also use "standard" textbooks, such as the SICP [0], and perform the exercises using the language of your choice, instead of Scheme/LISP.

[0]: https://mitp-content-server.mit.edu/books/content/sectbyfn/b...

making up your exercises is part of that fun journey of creating your own toolbox of functional programming in your language of choice!

If you're fairly new to FP I really recommend working through https://htdp.org.

The value of purely functional programming languages, as opposed to functional programming languages like lisps, is that you get referential transparency, which means that when you define `a = b`, you know that you can always replace any instance of `a` with `b` and get the same answer. This is a very natural property in mathematics (algebraic rewritings are basically just this property writ large) and so it helps to draw nice parallels between the familiar notation of functions from mathematics and the "new" and "confusing" notion of functions in functional programming and other declarative languages.

As other posters have said, strong typing is also a nice property for lots of reasons, most notably it gives a platform to talk about ad-hoc and parametric polymorphism.

(I lecture on Functional Programming at the University of Warwick, where we use Haskell.)

"Lisp" is pretty broad. Whilst it was inspired by Lambda Calculus (the core of most FP languages), a lot of Lisp code is quite imperative (loops, mutable variables, control flow separate from data flow (e.g. exceptions/errors), etc.).

Scheme (and its dialects/descendants) tend to stick to a more functional style (although they also like to do stack-gymnastics with continuations, etc.). Many courses are based around Lisp.

One of the main features of the ML family is static typing, with algebraic datatypes, pattern-matching, etc. (i.e. the stuff that new languages like to call "modern", because they first saw it in Swift or something). That gives a useful mathematical perspective on code ("denotational semantics", i.e. giving meaning to what's written; as opposed to the common "operational semantics" of what it made my laptop do), and having type checking and inference makes it easier to do generic and higher-order programming (dynamic languages make that trivial in-the-small, but can make large systems painful to implement/debug/maintain/understand). This course seems to take such abstraction seriously, since it covers modules and functors too (which are another big feature of the ML family).

NOTE: In ML, the words "functor" and "applicative functor" tend to mean something very different (generic, interface-based programming) to their use in similar languages like Haskell (mapping functions over data, and sequencing actions together)

It is statically typed, there's a lot of depth to that side of things (Curry-Howard isomorphism)

My opinion: marketing. In my experience, if I tell someone „look here is Lisp“ they turn off and roll the eyes with a „ohh that DEAD origramming language“. If I instead say „look this new state of the art language called ML“ I get full attention and respect.

Why would they use a Lisp dialect instead of Standard ML? It looks ugly, it looks different from math, and different concepts have the same syntax. Standard ML looks nice, it looks like math, and different concepts have different syntax.

There's a few things which go into this (hi, I'm the instructor!).

One such reason is historical. Standard ML is a research language, and a significant amount of work on it was done by professors at Carnegie Mellon, who developed the curriculum for this course.

Even setting that aside though, I fully agree with the choice to teach it in SML. For transparency, I work professionally in OCaml, so I am not unfamiliar with it, and I enjoy it quite a bit. That being said, I think that the approach taken by CMU is best summarized as the fact that languages are ephemeral, and the concepts are what matters. We don't teach programming languages, we teach concepts -- so even if SML is not widely used, the tradeoff for having students have a simpler, less distracting, and better learning experience is well worth it.

OCaml has its own intricacies that make things difficult. For instance, you can go down a lot of rabbit holes with `dune` and `utop` and `ocamlc` and `ocamlopt` and all of these things, versus SML/NJ's simple interactive REPL. Another thing is that the language is just generally more "bloated" -- you can teach modules, but then what if a student starts running into first-class modules, recursive modules, or even beyond that, GADTs and classes and objects?

(as an aside, this is my primary reason for why I would not want to teach an introductory course in Haskell. To do anything, you suddenly need to understand the concept of type classes and lazy evaluation, and that's simply too much. I don't know much about the other languages.)

I think teaching is as much enabling students to succeed as it is to prevent them from shooting themselves in the foot. For an anecdote, there is an `Option.valOf` function (of type `'a option -> 'a`), which essentially is just a bad function that should be avoided where possible. Every semester, without fail, even though we never tell students that function exists, students are smart enough to use Google, and will use it anyways, ultimately harming themselves.

I think that same mentality applies to programming language choice, here. Keep it simple, keep it neat, and make sure that the students see what is necessary for their education, and not have to spend mental energy thinking about much more.

because SML is awesome, isn't going to change and is simple. you can learn the syntax in an afternoon, and really focus on learning FP semantics.

Many graph algorithms are designed for imperative programming. It's safe to say that functional graph programming is still in its infancy. Alga[0], a system for algebraic graphs only came out in 2017. And efficient algorithms for graphs may yet to be discovered (even something as simple as reversing a list that's both efficient and elegant only came out in 1986!)

That said, as a beginner in functional programming, it would probably be good enough if you just focus on directly translating imperative graph algorithms to functional programming. You simply solve the problem by programming at a slightly lower level of abstraction.

[0]: https://dl.acm.org/authorize?N46678 or preprint at https://github.com/snowleopard/alga-paper/releases/download/...

My Scala friends heavily rely on discord, e.g. the one mentioned here: https://typelevel.org/blog/2021/05/05/discord-migration.html

It is language based community but they do have vibrant discussion on learning and theories.

tbh if I were in a class taught by someone who had JUST finished their bachelor's degree, I'd take a lot of it with a grain of salt

> I do wish functional programming were more taught

My first CS bachelor's semester in Germany in 2017 taught functional programming using Haskell (as well as C and NASM assembly in another course on computer architecture).

OOP using Java and Python was only introduced in the second semester.

> Regardless I think it's important that students get exposed to more than just Python, which seems to increasingly be the only thing students come out knowing.

In my B.Sc. studies I used C, C++, Haskel, Assembly, Java, Python, and Swift.

This is Haskell-specific, it sounds like. I agree, the IO monad is really quite inconvenient sometimes.

I work in OCaml, which is also a functional language, but prints can be added in single lines. I address this point in Lecture 19 (Imperative Programming), actually, but my perspective is -- we invented immutability and purity to serve us, but we need not be fanatically beholden to it. In my opinion, I think Haskell goes in that direction, when every usage of IO now needs the IO monad to get involved.

A little mutability is OK. Functional programming is about the avoidance of side effects, more than simply forbidding it.

In Haskell you have a lot of options to type your functions in a more granular way. Consider the type class MonadIO, which lets you specify that your function works on any monad that can do side effects, not just IO specifically:

    -- Before
    captureAudioDuration :: DeviceID -> DiffTime -> IO WaveData
    -- After
    captureAudioDuration' :: MonadIO m => DeviceID -> DiffTime -> m WaveData

    class Monad m => MonadLog m where
        log :: String -> m ()
    -- In IO, just log to stdout.
    -- Other implementations might be a state/writer monad
    -- or a library/application-specific monad for business logic.
    instance MonadLog IO where
        log msg = putStrLn ("log: " ++ msg)
    -- Before: Bad, doesn't actually do any IO but logging
    findShortestPath :: Node -> Node -> Graph -> IO [Node]
    -- After: Better, type signature gives us more details on what's happening.
    -- We can still use this in an IO context because IO has a MonadLog instance.
    -- However, trying to capture audio in this function using either
    -- of the functions above will lead to a type error.
    findShortestPath' :: MonadLog m => Node -> Node -> Graph -> m [Node]

Just let all your functions live in IO then. You'll still come out ahead.

Or do an unsafePerformIO.

Or use trace (where someone else has done the unsafePerformIO for you).

Or use a Writer.

Or introduce some logging capability (Logger m =>) onto your code.

Or take a look at all the man-hours that have been spent on trying to perfect logging: https://hackage.haskell.org/packages/tag/logging

> Sometimes I just want to do something silly, like adding a log somewhere.

In Haskell, you can use Debug.Trace for just that purpose, when you don't want to change the type of your function.

You might benefit from a more pragmatic functional language. Erlang is broadly functional, but you can output from anywhere if you want to. It's probably one of the least pure functional languages out there, but it's super handy.

> If I choose to add said side effect, now all my functions are marked with an io signature

You got the wrong idea. You're supposed to write FP in a way where the side effect is highly layered and segregated away from pure code. IO are singularities within your chains of pure function compositions. As soon as you hit a singularity you have to break out of it as soon as possible.

The main idea is the meat. Keep your bread tiny and keep it very very separate from the meat.

The pattern is called Imperative Shell, functional core. Think of your IO as two pieces of bread in a sandwich and your pure code is the meat that connects the read to the write.

The game you're playing with haskell is to avoid letting the IO monad pollute any of your logic as much as possible.

Anyway that being said in applications where IO is all over the place... this pattern becomes largely ineffective. You basically have more bread than meat.

Others have mentioned having the same problem with this issue. One post I particularly like about the subject is this one on function colouring (how lagnuages with async/await syntax have a similar "infection"; this is a response to the original post on function colouring and not the original post). https://www.tedinski.com/2018/11/13/function-coloring.html

From my limited knowledge of FP languages it is expected that pure code in fact doesn't evaluate anything until a monad forces it to evaluate.

You would then need a monad to evaluate the things you're attempting to log. And at that point you have a monad, so you can log as usual?

That’s like saying the problem with rulers is that the real world doesn’t have straight lines.

Or the problem with cleaning your room is that in the real world entropy only ever increases.

on the contrary, i think FP (Haskell at least) gives you more & better tools to represent and wrangle side effects

Programming runs along the back of mathematics. A field famous for spending centuries wasting time on silly games until those same silly games end up being the foundation on which modern society functions.

Even if LLMs completely remove the need for programming (a rather big IF), this is not time wasted.

Functional programming is a perfect pairing with AI-generated code because the type systems are generally more expressive than non-functional languages, which means the compilers can catch all sorts of errors.

As my mother used to say, we'll see...