11 ms·

15-150: Principles of Functional Programming

448 points by brandonspark 3y ago

deleted 3y ago
[deleted]
freedomben 3y ago
I do wish functional programming were more taught. we're getting to a point where I almost think OOP should be taught briefly and the rest of the focus on C/C++ for low level stuff (OS, data structures, some algorithms), and something functional or pseudo-functional for high level stuff. Most of the newer codebases in startups now require functional concepts to understand what's happening. For example, try writing modern JS without understanding .map, .reduce, et al, and function passing, etc. 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.
- Mandelmus 3y ago
  > 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.
  - freedomben 3y ago
    There are definitely some good schools out there that expose students to a broad field. For anybody who is a student and looking, this is somethign I would strongly recommend considering.
  - randmeerkat 3y ago
    > 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). Also worth mentioning that since this was in Germany not only was it a great education, but there’s no crippling student debt either.
  - RamblingCTO 3y ago
    Same here. Had Scala in my first year. Clojure and Racket later. On top of that I had C, ASM, Java, Python and R (had a focus on machine learning). So I got plenty of education in that department.
- deleted 3y ago
  [deleted]
  - deleted 3y ago
    [deleted]
PennRobotics 3y ago
Standard ML (sml / smlnj) The instructor is clear, energetic, has a decent flow in the first lecture e.g. emphasizes the important points with vigor and repetition, switches media every 10 or 15 minutes, has a conversation with students. Slides are relatively noise-free and are informative; terms to know are highlighted. I haven't watched a full functional programming lecture series yet, but I'd gladly audit this one. As a "new" instructor (as in, not a TA anymore) he's got a bit of teaching talent. I hope he keeps a tight feedback loop and improves every year and continues publishing material.
- deleted 3y ago
  [deleted]
andrewl 3y ago
This looks valuable. And it is from the summer of 2023, so quite current.
ajbt200128 3y ago
Of note, CMU produces a bunch of functional programming research, including a whole homotopy type theory department, so this is a quality source.
- deleted 3y ago
  [deleted]
frankbreetz 3y ago
Does this include exercises? I didn't see any and I always find that the most useful part of learning.
- fredgrott 3y ago
  making up your exercises is part of that fun journey of creating your own toolbox of functional programming in your language of choice!
- PennRobotics 3y ago
  Not exactly exercises, but there's https://smlhelp.github.io/book/docs/ 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 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 https://github.com/zhengguan/15150-1 with 10-year-old homeworks and such.
- brandonspark 3y ago
  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)
  - brandonspark 3y ago
    (but I have thought of developing my own exercises independently to go with the lectures, to post on my website. This is generally a lot of work, though, so this might take some time, depending on how much people would benefit from it.)
    - bombcar 3y ago
      Could be a classic kickstarter campaign style thing.
c-c-c-c-c 3y ago
Wow, he went from taking his bachelor to lecturing. I always dreamt of that when going through my degree and encountering courses that needed a thorough rework.
- shortrounddev2 3y ago
  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
  - medstrom 3y ago
    If you expect perfect factual accuracy from your teachers, yeah. On the flip side, they don't have the curse of knowledge yet i.e. it's still fresh in their mind what was difficult in the beginning, so they can probably explain very well. Just keep in mind who's teaching you, and it's just like if a co-student teaches you. And if you feel you have to take what you hear with a grain of salt, that's probably good for your learning too.
    - shortrounddev2 3y ago
      I just mean in terms of experience. If you deviate from textbook accuracy and go into providing practical advice for real-life scenarios, someone with only a bachelor's and no work history is someone who can only give you canned anecdotes from others. Looking at his resume, it looks like he's had some internships so he has a bit of experience, and that's probably worth something
      - gtchuang 3y ago
        His main day job is as a SWE doing program analysis, so I'm pretty sure he's got the credentials to talk about real-life scenarios.
        shortrounddev2 3y ago
        Yeah idk anything about the guy
narinxas 3y ago
just in time for nobody to really care about programming because LLMs are so good at translation and all computer code and programing are a subfield of linguistics...
- interiorchurch 3y ago
  As my mother used to say, we'll see...
- Verdex 3y ago
  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.
  - deleted 3y ago
    [deleted]
- shepherdjerred 3y ago
  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.
agomez314 3y ago
Great resource! Forgive my ignorance but why do so many modern functional programming courses use Standard ML instead of a Lisp dialect? Is it because of its built-in type-checking, or is it just how it's always been taught?
- f1shy 3y ago
  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.
  - ajbt200128 3y ago
    No, it's definitely not because of marketing. SML is more of a dead language than most lisps. SML is used because it has a strong type checker, which is much more conducive to learning, and just having resilient programs in general.
  - deleted 3y ago
    [deleted]
- vmchale 3y ago
  It is statically typed, there's a lot of depth to that side of things (Curry-Howard isomorphism)
- johnday 3y ago
  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.)
systems 3y ago
on the choice of language to teach the course why sml i think there are a lot of nicer choice OCaml , its basically sml only more popular and used more in real life Haskell , again more popular , and used more in real life Idris , newer and said to be more progressive F# , a more practical choice and similar to sml a lisp , well if you want to focus on the functional part and less on the types part
- deleted 3y ago
  [deleted]
- brandonspark 3y ago
  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.
frozenlettuce 3y ago
My complaint with FP: Sometimes I just want to do something silly, like adding a log somewhere. If I choose to add said side effect, now all my functions are marked with an io signature (so there might be _other_, nastier side effects hiding there as well - mainly an issue if you have multiple people contributing to the same project). If I don't add the side effect, and choose to refactor multiple layers of code, I will need to make all my functions return multiple values and later fold over all the accumulated strings and... life is too short for that. The principles really resonate with me, but maybe we are limited by the current tooling, because the development experience is quite clunky in its current stage.
- deleted 3y ago
  [deleted]
- brandonspark 3y ago
  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.
  - frozenlettuce 3y ago
    yeah, I've been trying to get this mindset as well - even though sometimes I feel that I'm "cheating" :)
- mrkeen 3y ago
  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 https://hackage.haskell.org/packages/tag/logging
imslavko 3y ago
Slightly off-topic but what's a good forum to seek help on FP practices outside of the courses like this online? Every winter break I get back into trying to learn more FP (in Haskell) and in the past several years I have been practicing algo problems (codeforces, advent of code, leetcode). I always get stuck on more advanced graph algorithms where you traverse a and modify a graph, not a tree structure - it gets particularly tricky to work on circular data structures (I learned about "tying the knot" but it's incredibly challenging for me) and usually the runtime perf is sub-par both asymptotically and empirically.
- deleted 3y ago
  [deleted]
- low_tech_punk 3y ago
  My Scala friends heavily rely on discord, e.g. the one mentioned here: https://typelevel.org/blog/2021/05/05/discord-migration.html 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.
- kccqzy 3y ago
  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 https://dl.acm.org/authorize?N46678 or preprint at https://github.com/snowleopard/alga-paper/releases/download/icfp-submission-archived/alga.pdf https://github.com/snowleopard/alga-paper/releases/download/...
  - philsnow 3y ago
    I don't know if [0] would be any help, it doesn't talk about graphs in particular but does talk about functional-focused approaches to data structures. This note[1] on the wikipedia page for the book says it better than I could: > [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style. [0] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf [1] https://en.wikipedia.org/wiki/Purely_functional_data_structure#Using_purely_functional_data_structures https://en.wikipedia.org/wiki/Purely_functional_data_structu...
zubairq 3y ago
Watching it now
aroman 3y ago
150 was one of my favorite courses at CMU; each homework really made me feel like I unlocked a new level of reasoning with code.
- louthy 3y ago
  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.
  - adamddev1 3y ago
    Yes! I love this description!
- 3abiton 3y ago
  Do you if any of the course material is available online or as a MOOC?
  - rashkov 3y ago
    Have a look at this similar course: https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages I enjoyed it quite a bit and the lecturer is fantastic. It also uses SML and teaches similar material, though maybe not as in depth since this is just the first section of a three-part semester long course.
low_tech_punk 3y ago
God send!! The FP learning resource is quite sparse on the internet. I’ve been looking for structured material like this for a while.
- adamddev1 3y ago
  If you're fairly new to FP I really recommend working through https://htdp.org https://htdp.org.
Koshkin 3y ago
It seems that the fundamental problem with the functional paradigm (in its pure form) is that the real world - including the architecture of the computer that is used to run the programs on - is full of side effects, i.e. is essentially "imperative," and with this impedance between them the idea creates more problems than it solves.
- deleted 3y ago
  [deleted]
- whateveracct 3y ago
  on the contrary, i think FP (Haskell at least) gives you more & better tools to represent and wrangle side effects
  - kccqzy 3y ago
    Exactly. These languages come up with more and more strategies and abstractions (from monads to modern effect systems) to help you manage your side effects well. It then raises the level of abstraction in your programs to become simpler and more concise.
- deleted 3y ago
  [deleted]
- epgui 3y ago
  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.
  - kccqzy 3y ago
    Any time an HN comment uses the phrase "fundamental problem" chances are the problem is not only not fundamental, but also rather fun to solve for the right kind of people.
airstrike 3y ago
Hey Brandon, thanks for posting this. Off-topic but maybe consider serving up thumbnails on that page instead of the full-size pngs https://brandonspark.github.io/prologue/lecture01.png https://brandonspark.github.io/prologue/lecture01.png
- deleted 3y ago
  [deleted]
  - deleted 3y ago
    [deleted]
vermilingua 3y ago
Content aside, what gorgeous slides. I wish any of my lecturers had the same eye for presentation.
- PennRobotics 3y ago
  Partial template source of the slides is available at https://github.com/jacobneu/150lectureNotes 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 https://github.com/jacobneu/alleycat as inspiration, use the scripts (e.g. startLecture) and Makefile in /crucible
gsuuon 3y ago
This looks cool! Just a note, it looks like the youtube playlist is in reverse order: https://www.youtube.com/watch?v=DSGXB9G5dxk&list=PLsydD1kw8jng2t2G8USQNLz0faYZetPnH&pp=iAQB https://www.youtube.com/watch?v=DSGXB9G5dxk&list=PLsydD1kw8j...
- deleted 3y ago
  [deleted]
jstrieb 3y ago
I loved 150 when I took it, and program in SML from time to time to this day. Bob Harper (a CMU professor with a focus on PL theory) also has a really good SML reference that is closer to a textbook than lecture notes. http://www.cs.cmu.edu/~rwh/isml/book.pdf http://www.cs.cmu.edu/~rwh/isml/book.pdf
- zelphirkalt 3y ago
  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.
  - jstrieb 3y ago
    This is valid criticism, and I agree. The regular expression example is not made easier by his use of non-standard regex syntax. I have not read Dr. Harper's book cover to cover; I treat it as a reference. For that, it is quite useful. The same criticism of his SML book could also be made of his Practical Foundations for Programming Languages book. It's a massive, dense tome that is probably great for other professors to use as the basis for a course, but (in my opinion) serves as a mediocre introduction if you have never seen the material before. https://www.cs.cmu.edu/~rwh/pfpl.html https://www.cs.cmu.edu/~rwh/pfpl.html
esafak 3y ago
Pretty good for a new grad!
hohohmm 3y ago
Use to be called 15-212. TA-ed it for 1 semester. That's when I really understood programming.
asicsp 3y ago
See also: https://functionalcs.github.io/curriculum/#orge441e24 https://functionalcs.github.io/curriculum/#orge441e24
valenterry 3y ago
No word on where the concept originally comes from? (in the text/description) Should have at least differentiated between "functional programming" and "pure functional programming" IMHO.
endgame 3y ago
The lecture on CPS made things "click" for me in a way that they hadn't before. Thank you.

448 points by brandonspark 3y ago

deleted 3y ago

[deleted]

I do wish functional programming were more taught. we're getting to a point where I almost think OOP should be taught briefly and the rest of the focus on C/C++ for low level stuff (OS, data structures, some algorithms), and something functional or pseudo-functional for high level stuff. Most of the newer codebases in startups now require functional concepts to understand what's happening. For example, try writing modern JS without understanding .map, .reduce, et al, and function passing, etc. 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.

Mandelmus 3y ago
> 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.
- freedomben 3y ago
  There are definitely some good schools out there that expose students to a broad field. For anybody who is a student and looking, this is somethign I would strongly recommend considering.
- randmeerkat 3y ago
  > 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). Also worth mentioning that since this was in Germany not only was it a great education, but there’s no crippling student debt either.
- RamblingCTO 3y ago
  Same here. Had Scala in my first year. Clojure and Racket later. On top of that I had C, ASM, Java, Python and R (had a focus on machine learning). So I got plenty of education in that department.
deleted 3y ago
[deleted]
- deleted 3y ago
  [deleted]

PennRobotics 3y ago

Standard ML (sml / smlnj) The instructor is clear, energetic, has a decent flow in the first lecture e.g. emphasizes the important points with vigor and repetition, switches media every 10 or 15 minutes, has a conversation with students. Slides are relatively noise-free and are informative; terms to know are highlighted. I haven't watched a full functional programming lecture series yet, but I'd gladly audit this one. As a "new" instructor (as in, not a TA anymore) he's got a bit of teaching talent. I hope he keeps a tight feedback loop and improves every year and continues publishing material.

deleted 3y ago
[deleted]

andrewl 3y ago

This looks valuable. And it is from the summer of 2023, so quite current.

ajbt200128 3y ago

Of note, CMU produces a bunch of functional programming research, including a whole homotopy type theory department, so this is a quality source.

deleted 3y ago
[deleted]

frankbreetz 3y ago

Does this include exercises? I didn't see any and I always find that the most useful part of learning.

fredgrott 3y ago
making up your exercises is part of that fun journey of creating your own toolbox of functional programming in your language of choice!
PennRobotics 3y ago
Not exactly exercises, but there's https://smlhelp.github.io/book/docs/ 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 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 https://github.com/zhengguan/15150-1 with 10-year-old homeworks and such.
brandonspark 3y ago
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)
- brandonspark 3y ago
  (but I have thought of developing my own exercises independently to go with the lectures, to post on my website. This is generally a lot of work, though, so this might take some time, depending on how much people would benefit from it.)
  - bombcar 3y ago
    Could be a classic kickstarter campaign style thing.

c-c-c-c-c 3y ago

Wow, he went from taking his bachelor to lecturing. I always dreamt of that when going through my degree and encountering courses that needed a thorough rework.

shortrounddev2 3y ago
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
- medstrom 3y ago
  If you expect perfect factual accuracy from your teachers, yeah. On the flip side, they don't have the curse of knowledge yet i.e. it's still fresh in their mind what was difficult in the beginning, so they can probably explain very well. Just keep in mind who's teaching you, and it's just like if a co-student teaches you. And if you feel you have to take what you hear with a grain of salt, that's probably good for your learning too.
  - shortrounddev2 3y ago
    I just mean in terms of experience. If you deviate from textbook accuracy and go into providing practical advice for real-life scenarios, someone with only a bachelor's and no work history is someone who can only give you canned anecdotes from others. Looking at his resume, it looks like he's had some internships so he has a bit of experience, and that's probably worth something
    - gtchuang 3y ago
      His main day job is as a SWE doing program analysis, so I'm pretty sure he's got the credentials to talk about real-life scenarios.
      - shortrounddev2 3y ago
        Yeah idk anything about the guy

narinxas 3y ago

just in time for nobody to really care about programming because LLMs are so good at translation and all computer code and programing are a subfield of linguistics...

interiorchurch 3y ago
As my mother used to say, we'll see...
Verdex 3y ago
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.
- deleted 3y ago
  [deleted]
shepherdjerred 3y ago
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.

agomez314 3y ago

Great resource! Forgive my ignorance but why do so many modern functional programming courses use Standard ML instead of a Lisp dialect? Is it because of its built-in type-checking, or is it just how it's always been taught?

f1shy 3y ago
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.
- ajbt200128 3y ago
  No, it's definitely not because of marketing. SML is more of a dead language than most lisps. SML is used because it has a strong type checker, which is much more conducive to learning, and just having resilient programs in general.
- deleted 3y ago
  [deleted]
vmchale 3y ago
It is statically typed, there's a lot of depth to that side of things (Curry-Howard isomorphism)
johnday 3y ago
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.)

systems 3y ago

on the choice of language to teach the course why sml i think there are a lot of nicer choice OCaml , its basically sml only more popular and used more in real life Haskell , again more popular , and used more in real life Idris , newer and said to be more progressive F# , a more practical choice and similar to sml a lisp , well if you want to focus on the functional part and less on the types part

deleted 3y ago
[deleted]
brandonspark 3y ago
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.

frozenlettuce 3y ago

My complaint with FP: Sometimes I just want to do something silly, like adding a log somewhere. If I choose to add said side effect, now all my functions are marked with an io signature (so there might be _other_, nastier side effects hiding there as well - mainly an issue if you have multiple people contributing to the same project). If I don't add the side effect, and choose to refactor multiple layers of code, I will need to make all my functions return multiple values and later fold over all the accumulated strings and... life is too short for that. The principles really resonate with me, but maybe we are limited by the current tooling, because the development experience is quite clunky in its current stage.

deleted 3y ago
[deleted]
brandonspark 3y ago
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.
- frozenlettuce 3y ago
  yeah, I've been trying to get this mindset as well - even though sometimes I feel that I'm "cheating" :)
mrkeen 3y ago
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 https://hackage.haskell.org/packages/tag/logging

imslavko 3y ago

Slightly off-topic but what's a good forum to seek help on FP practices outside of the courses like this online? Every winter break I get back into trying to learn more FP (in Haskell) and in the past several years I have been practicing algo problems (codeforces, advent of code, leetcode). I always get stuck on more advanced graph algorithms where you traverse a and modify a graph, not a tree structure - it gets particularly tricky to work on circular data structures (I learned about "tying the knot" but it's incredibly challenging for me) and usually the runtime perf is sub-par both asymptotically and empirically.

deleted 3y ago
[deleted]
low_tech_punk 3y ago
My Scala friends heavily rely on discord, e.g. the one mentioned here: https://typelevel.org/blog/2021/05/05/discord-migration.html 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.
kccqzy 3y ago
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 https://dl.acm.org/authorize?N46678 or preprint at https://github.com/snowleopard/alga-paper/releases/download/icfp-submission-archived/alga.pdf https://github.com/snowleopard/alga-paper/releases/download/...
- philsnow 3y ago
  I don't know if [0] would be any help, it doesn't talk about graphs in particular but does talk about functional-focused approaches to data structures. This note[1] on the wikipedia page for the book says it better than I could: > [...] consider a function that accepts a mutable list, removes the first element from the list, and returns that element. In a purely functional setting, removing an element from the list produces a new and shorter list, but does not update the original one. In order to be useful, therefore, a purely functional version of this function is likely to have to return the new list along with the removed element. In the most general case, a program converted in this way must return the "state" or "store" of the program as an additional result from every function call. Such a program is said to be written in store-passing style. [0] https://www.cs.cmu.edu/~rwh/students/okasaki.pdf https://www.cs.cmu.edu/~rwh/students/okasaki.pdf [1] https://en.wikipedia.org/wiki/Purely_functional_data_structure#Using_purely_functional_data_structures https://en.wikipedia.org/wiki/Purely_functional_data_structu...

zubairq 3y ago

Watching it now

aroman 3y ago

150 was one of my favorite courses at CMU; each homework really made me feel like I unlocked a new level of reasoning with code.

louthy 3y ago
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.
- adamddev1 3y ago
  Yes! I love this description!
3abiton 3y ago
Do you if any of the course material is available online or as a MOOC?
- rashkov 3y ago
  Have a look at this similar course: https://www.coursera.org/learn/programming-languages https://www.coursera.org/learn/programming-languages I enjoyed it quite a bit and the lecturer is fantastic. It also uses SML and teaches similar material, though maybe not as in depth since this is just the first section of a three-part semester long course.

low_tech_punk 3y ago

God send!! The FP learning resource is quite sparse on the internet. I’ve been looking for structured material like this for a while.

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

Koshkin 3y ago

It seems that the fundamental problem with the functional paradigm (in its pure form) is that the real world - including the architecture of the computer that is used to run the programs on - is full of side effects, i.e. is essentially "imperative," and with this impedance between them the idea creates more problems than it solves.

deleted 3y ago
[deleted]
whateveracct 3y ago
on the contrary, i think FP (Haskell at least) gives you more & better tools to represent and wrangle side effects
- kccqzy 3y ago
  Exactly. These languages come up with more and more strategies and abstractions (from monads to modern effect systems) to help you manage your side effects well. It then raises the level of abstraction in your programs to become simpler and more concise.
deleted 3y ago
[deleted]
epgui 3y ago
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.
- kccqzy 3y ago
  Any time an HN comment uses the phrase "fundamental problem" chances are the problem is not only not fundamental, but also rather fun to solve for the right kind of people.

airstrike 3y ago

Hey Brandon, thanks for posting this. Off-topic but maybe consider serving up thumbnails on that page instead of the full-size pngs https://brandonspark.github.io/prologue/lecture01.png https://brandonspark.github.io/prologue/lecture01.png

deleted 3y ago
[deleted]
- deleted 3y ago
  [deleted]

vermilingua 3y ago

Content aside, what gorgeous slides. I wish any of my lecturers had the same eye for presentation.

PennRobotics 3y ago
Partial template source of the slides is available at https://github.com/jacobneu/150lectureNotes 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 https://github.com/jacobneu/alleycat as inspiration, use the scripts (e.g. startLecture) and Makefile in /crucible

gsuuon 3y ago

This looks cool! Just a note, it looks like the youtube playlist is in reverse order: https://www.youtube.com/watch?v=DSGXB9G5dxk&list=PLsydD1kw8jng2t2G8USQNLz0faYZetPnH&pp=iAQB https://www.youtube.com/watch?v=DSGXB9G5dxk&list=PLsydD1kw8j...

deleted 3y ago
[deleted]

jstrieb 3y ago

I loved 150 when I took it, and program in SML from time to time to this day. Bob Harper (a CMU professor with a focus on PL theory) also has a really good SML reference that is closer to a textbook than lecture notes. http://www.cs.cmu.edu/~rwh/isml/book.pdf http://www.cs.cmu.edu/~rwh/isml/book.pdf

zelphirkalt 3y ago
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.
- jstrieb 3y ago
  This is valid criticism, and I agree. The regular expression example is not made easier by his use of non-standard regex syntax. I have not read Dr. Harper's book cover to cover; I treat it as a reference. For that, it is quite useful. The same criticism of his SML book could also be made of his Practical Foundations for Programming Languages book. It's a massive, dense tome that is probably great for other professors to use as the basis for a course, but (in my opinion) serves as a mediocre introduction if you have never seen the material before. https://www.cs.cmu.edu/~rwh/pfpl.html https://www.cs.cmu.edu/~rwh/pfpl.html

esafak 3y ago

Pretty good for a new grad!

hohohmm 3y ago

Use to be called 15-212. TA-ed it for 1 semester. That's when I really understood programming.

asicsp 3y ago

See also: https://functionalcs.github.io/curriculum/#orge441e24 https://functionalcs.github.io/curriculum/#orge441e24

valenterry 3y ago

No word on where the concept originally comes from? (in the text/description) Should have at least differentiated between "functional programming" and "pure functional programming" IMHO.

endgame 3y ago

The lecture on CPS made things "click" for me in a way that they hadn't before. Thank you.