His Category Theory for Programmers book is an excellent introduction to the CT world if you come from a Computer Science background (well ... duh it says it right there in the title) and know very little math.
Highly recommended to give it a try, even if the topic doesn't seem to fit you. This is one of those books that will make you a better programmer regardless of what you do.
Writing interpreters in Haskell (which is what some of the lessons seem to be about) is a great way to learn the language. It naturally motivates recursion, algebraic data types, strong types, higher-order functions and later, when effects such as state and errors are needed, monads arise naturally.
The best part? It takes a ridiculously small amount of code to do all that, maybe around a hundred or less. Languages without ADTs and higher-order functions bend over backwards to recover them[0] via design patterns.
It also introduces you to the expression problem pretty quickly and organically :)
I agree with the comment though. I learned Haskell and how to write an interpreter at the same time by working through the book Crafting Interpreters. It was a great match.
Back when I did my degree, Haskell still wasn't a thing, like it was giving its first steps.
So the choice would be Lisp, Prolog, Caml Light, or the recently released Objective Caml.
The year before I took compilers design project, the TA responsible for it used to disallow them from the implementation language option list, as it would make the assignment too easy.
Agreed! I've been trying to learn haskell for a long time, and this guy writes a json parser live, giving his intuition along the way. It's helped me immensely.
https://www.youtube.com/watch?v=N9RUqGYuGfw
compiler, evaluator constructs should be the bottom of the next set of mainstream languages (possibly being born today by former haskell programmers?) imagine free monad lisp
Also I personally recommend to take a look to this series before diving into his great introductory book about category theory [1]. Seeing the application of the theoretical concepts and deriving the code yourself makes it more approachable for completly begginers from my experience.
The only introductory treatment of Category Theory for non-specialists that I’ve encountered that even competes with it is Spivak’s “Category Theory for the Sciences.” For the curious, Eugenia Cheng’s books for lay audiences are excellent for getting a feel of the power and value of the Category Theoretical approach.
Category Theory is somewhat unique in being a recently developed area of advanced maths that is nevertheless approachable with only modest formal training. Because it maps so well to much of the theory and practice of functional programming, most programmers with even a little interest and familiarity with that will be able to engage with the fundamentals, and Milewski does a masterful job of introducing it to that audience.
My university teaches the intro CS course in Racket (lisp), and I know another that teaches in Haskell. If decades of priority exposure to young programmers is not enough to spur widespread adoption, then I'm not hopeful.
I think intro CS courses in Lisp and Haskell (or other less-than-mainstream languages) hurts the uptake of those languages. The students will confuse the difficulty of the material with the language itself. And there's less material out there to support them, compared to the multitude of Q&As for C or Java or C++. And when later courses move them to other languages (C, Java, C++, etc.) things seem easier so the students reject those earlier languages. In some ways those languages may be easier, but the student is also more experienced.
I doubt I would've taken as well to Lisp if it was my first course, versus used in a couple graduate courses.
When I did my degree, we had ISO Pascal and C++ (proper C++ not C with classes) on the 2nd year (1st was a common year to all engineering degrees),
Followed by abstract logic, Prolog, Caml Light and Smalltalk on the 3rd.
By the 4 year, you would have used Prolog in a couple of parallel assignments that also required it, Lisp via ELisp, as Emacs was the "IDE" for the Prolog and Caml Light assignments and some TAs liked to spend an hour introduction to not using Emacs like Notepad.
UNIX systems programming, distributed computing, data structures and algorithms would make use of C, that by virtue of having already learned C++, no teacher would spend a second with an introduction to C lectures.
Those of us that took language design and compilers, would still delve into proper Lisp, Cobol, Fortran, Algol, Oberon, and a couple of others even less known. The teacher driving this lectures would switch back to Caml Light for several exercises.
Since I ended up graduating as Java came into the scene, the very last year I ended up doing several projects in Java as well, while taking place in the national championship of logic programming.
If anything what frustrated me was coming into the market place and having to deal with C, while having been exposed how much better the things could be. Thankfully using it alongside Tcl made it not so bad, given Tcl's lispy background.
The problem is not the intro courses, the problem are the teachers and the material been given to the students. It isn't a big deal if there aren't many books available, when there are teaching notes (of book like quality) given by the responsible professor, which one can question at any time unlike most book authors.
For me what made the difference weren't the books, rather the teachers I had the luck to meet during my university travel.
I don't think that's the point of having the intro CS course in a functional language. The concepts that you get taught there can also be applied outside of pure functional languages and they teach you a different way to think about programming.
I did my interpreter class in Scheme in university. The main thing it taught me was I never wanted to use scheme (or lisp) and put me off of functional programming for many years.
I re-did the interpreter from that class in C++ and it made insanely more sense to me than the scheme version. I could see where scheme was going and why it was a good fit but just hated it.
That same professor taught our C++ class (while learning it, they had someone quit) the next semester and they had to actually do a do-over he was so bad at C++. To his credit he knew as much half way through the semester (he had students getting ahead of him). He basically nop'd out of C++ like I did out of Scheme. It just didn't fit his brain.
Many people who like scheme and functional languages have an averse reaction to more procedural or OOP languages. It's interesting that people don't grok it can go the other way. But this is HN so I guess I'll explain.
A few things (and for context this was 1996).
With the class I disliked they were trying to teach me a language and a complex concept at the same time. In a 4 month semester, half of it was spent just getting basically proficient in the language. So instead of learning one concept I'm learning 2. We were essentially using scheme to build a interpreter for a simplified scheme. I understand why we were implementing scheme, it's one of the simplest languages to implement and maps well to many concepts in CS. this is actually why the game studio I worked at used it, not that it was the right language, in fact it's caused a lot of trouble and they have a lot of c/python like in the language now
Scheme seemed like a pretty useless language as well. The book for it listed (in the forward) out how amazing it was and showed all the amazing projects done with lisp-like languages. That list started with emacs and then the rest was academic things I'd never heard of, which seemed like a joke. If I recall scheme had some pretty weak language library functions at the time as well. Also at the time I cared about drawing triangles on the screen.
[I will lose points for this but it's my POV] I tend to find people who strongly like functional languages a bit insufferable, especially academics. I tend to learn by getting a real world project done, and I like tools that let you build real world things. I don't care anywhere near as much about form of the solution. . Functional languages seem to gel better with people who care about the beauty of a simple proof. I hate proofs. Also in much of the work I've done, the folks who really pushed for functional languages didn't really understand that most of their coworkers were juts not capable of understanding those languages or thinking that logically. There's a reason (imho) that they're not as popular of languages.
I have written stuff in these languages since then. I did work in the (gp reference) scripting language and on its implementation in the engine. This got me real features (like a mission in an AAA game, and features for my mission designers in the engine). This seemed useful to me.
I spent about 3 months trying to use Clojure to do a highly parallel data processing work. It seemed to map well to the problem. However it was insufferably slow, and with required type hinting was essentially complicated java (lost the benefit). I re-wrote it in C++ in about a week and brought the processing time from 15 minutes to 32 seconds by leveraging the deeper parts of the machine (buffers, disk cache, physical cores) which were not as available inside the abstraction.
So it also comes down to I haven't found a problem that maps well to something like scheme that I need to solve. When I do stuff with interpreters I just grab ANTLR and java/go/c++. This is more maintainable for everyone I work with.
I think some points are unfair. I have physical anger when I use java prior 8, but I do appreciate smalltalk a lot more, it tickles my sense of curiosity, joy.
While I do admit that lisp/scheme/fp seek beauty.. it's also one thing I want in coding. Beautiful code. Not at the expense of practicality.. but still, look at how easy it is to be confused and make a mess trying to write a flatmap like procedure, while in lisp it's so trivial you never even think about it.
Thanks for the honesty and good job on making things fast.
Oh I never said it's fair, just laying it out there for you to take however you wish. It's pretty obvious to me I've got an inherent bias towards functional programming. I see people who love it and are successful with it so it obviously works. I've never had cause to work it out though. Just like I never owned a Sega Saturn nor a X-Box One. It's my personal opinion and thoughts on a language. You don't have to agree with it! In fact I'm very sure you don't. But for every preferential opinion you have, someone else will have a different one.
I once had an discussion with someone who was a huge relational guy who could not understand dynamo (many have this issue). I asked him how to do a global postal address in a relational db. He proceeded to put out a ~5 table layout on the whiteboard from memory. Finished by saying of course there are other situations and you can handle them with X or Y. We went and grabbed a drink and I had him grab get a sde1 and explain that layout to the SDE1. I cut it off after 15 minutes. While it was OBVIOUS to him in his experience, it was in no way simple and the SDE1 (who was just starting multi-table joins) was taking a while to catch up. The sr eng was just used to relational. The model he had on the board was at least 30 years of iteration and best practices, practically it's own microservice. I drew it in dynamo where it's just PK:UserId, and then a bunch of optional columns. SDE1 grokked this right away.
I would love to know what types of apps / code / work you do that you really appreciate in lisp. As I said I'm always looking for a language to solve a problem. What class of applications do you use it for?
For instance I use C++ when I need to be near the metal (game engines, shaders, arduino). We use go at work but Scheme or Clojure might be better for the business logic we do (tho it'd be slower). Always wanted to use Erlang but I never got on the distributed chat program projects (I killed 2 acutally).
The flatten code is very simple. You can probably guess what defun is, but you have to know what is cond, atom, and the symbol nil (and its relation to lists), as well as the mapcan function, not to mention the #' notation that appears on the self-reference to flatten.
cond is a multi-branch conditional test: it has the syntax
The tests are evaluated in sequence. When the first one is encountered that yields true, then the associated code is evaluated. cond then terminates, and yields the value of the last expression that was evaluated.
A catch-all clause, if necessary, is put at the end, where the test expression is just the symbol t. This symbol is Lisp's canonical representation of Boolean true. Though, any object other than nil is true, it is good form to use the t symbol as a Boolean true constant. Such a catch-all clause appears in the flatten implementation's cond.
atom tests whether a value is an atom, which means "not a cons cell". All objects that are not conses are atoms.
Non-empty lists are made of conses: a three element list has three conses. The empty list is made of no conses; it is represented by the symbol nil, which is an atom.
null tests whether a value is the nil object: (null X) is the same thing as (eq nil X).
list is a constructor that makes a list of its argument values.
mapcan projects a each element of a list through a function. The values returned by the function must be lists, and those lists are catenated together. The catenated list is returned by mapcan (destructively, not functionally!) Obviously, mapcan is relevant to implementing flatten.
The #'X notation is a shorhand for (function X). It's a special operator which obtains a function as a value, given its name. It is necessary due to the two-namespace nature of Common Lisp: function bindings are in a separate namespace from variable bindings. If there is a function called X, the (X ...) expression calls the function well enough, but the expression X doesn't retrieve the X function; it refers to an X variable. (function X) refers to the function as a value, and because that is verbose, it has a #'X shorthand.
Note that the flatcan expression recurses on the list elements without regard for whether they are lists or not. For instance, if we flatten (1 2 3), then flatten will get recursively called for 1, 2, and 3. These 1, 2, 3 cases will be detected by the (atom structure) branch of the cond. (1), (2) and (3) will be returned, which get catenated by mapcan to (1 2 3) again.
I think your view’s totally reasonable. In my experience, the benefit of FP is To teach good program design: I’ve observed that functional programming languages encourage good practices that can be practiced in any language. For example: pushing I/O to the leaves of your program, dependency injection, eradicating global state, focus on functional interfaces.
These are patterns that you can do in any language, but functional languages kind of compel you to follow them. Many people first learned these patterns from FP, and carry them over to OOP, which they have to write at work.
I don’t know if there are many problems that are elegantly defined for FP, as you suggest. I think people just get comfortable in their cages. :)
You’re not alone. My brain works in steps, not proofs. If all code looked like Haskell and friends I doubt I’d ever have gotten into it in the first place.
[edit] algos, over proofs, would probably be a better way to put it.
Sure, which is why I edited that “algorithms” is more accurate. When I read proofs I have to go through each step and figure out what every term on either side “does” to something “going through” it to make sense of it. I’d rather have my sandwich-making instructions as instructions than a series of statements about how the sandwich looks at each stage that I have to go back and turn into instructions to actually do anything with it, if that makes sense.
I get that other people don’t have this preference, but I strongly do. Test results indicate I should be incredibly well suited to mathematical work but I feel the way I imagine a dyslexic must when I try to read math or “mathy” programming languages. Give me something more-or-less procedural and I’m totally happy (though I gather I had a much easier time understanding and getting comfortable with recursion than many people do, which seems weird given I find the languages most heavily associated with it almost unreadable).
I did my interpreter/PLT class in OCaml and absolutely loved it. I yearn for things like ADTs and pattern matching in other languages I use now :'(
Another benefit (I guess the primary benefit) was that my interpreter programs written in OCaml ended up looking nearly identical to my proofs/definitions. Doing it imperatively would add a nasty layer of indirection.
If you already knew C++, that's not a particularly useful comparison. Of course you were more comfortable reading and writing code in a language you already knew, than one you were learning.
An equivalent would be a class teaching c++ and writing and interpreter at the same time. And my gut says that would be more complex for unnecessary reasons than the class you took.
I did not already know C++. I did already know Java since we did java for our intro class (101/102) and then the next year we did Compiler theory (240). But the professors who know more than me an entry level student designed this structure.
And I did write that same compiler in c++ and sure it was more lines of code but I understood it better.
I've also worked on a scheme interpreter in C++ that someone wrote in a game engine and it wasn't all that complicated.
There are plenty of programmers who learned languages like Haskell, Scheme, Eiffel etc. as their first languages who are now programming in Java, JavaScript, C# etc.
There are just way more courses/universities that teach or taught Java/Python.
Businesses settle on the lowest common denominator it seems.
Would it not be great if instead of a programming language being handed down to us as if made of stone, it was seen as a particular expression of a set of ideas (some good, some bad), much as music is, that we could relate and respond to in the same spirit?
i think a better analogy would be [programming techniques as "musical ideas", programming languages as instruments]. you can pick an instrument that fits what want to do, or build a new one if you know how :)
This is just my heuristic but Haskell has just 25 keywords. For comparison: C 32, Java 53, C++ 83 and C# 102. What makes Haskell confusing are the 115 GHC language extensions. Each is basically a new concept to learn. Every time i join a new and sufficiently large project, I stumble across an extension that I am not familiar with.
Often extensions make the language easier to understand, by removing arbitrary restrictions that you wouldn't have expected to be there in the first place.
I think that a lot of people find that LYAH makes you feel like you're learning, but have difficulty actually applying/using the concepts. This is compounded by the lack of exercises.
> The material often bores learners and leaves them feeling like they're not "getting" it. This is because they're being "talked at" and demo'd to. They're not engaging with and solving problems.
His Category Theory for Programmers book is an excellent introduction to the CT world if you come from a Computer Science background (well ... duh it says it right there in the title) and know very little math.
Highly recommended to give it a try, even if the topic doesn't seem to fit you. This is one of those books that will make you a better programmer regardless of what you do.