I love the "reimplement the standard library" approach to learning a programming language.
When I learned C and Unix, the instructor had us reimplement libs like string.h and stdio.h, command line tools like date, ls and cut and then build tools like make.
C is a language I'd like to see make a reappearance in CS curricula. It's great that most programmers today don't have to deal with memory management and pointers, but I think a CS degree should leave the student with a basic grasp of the full stack of programming paradigms.
I think a nice approach would be to start off with a high-level, functional language like Haskell or Scheme, and then move down the ladder of abstraction in subsequent courses, culminating in a hardcore C (or maybe even assembly) course.
This is exactly what my school did. The first CS class was in Scheme, based on SICP. The next one was about data structures and based on Java. The last one was about computer architecture and used C followed by MIPS followed by designing a simple CPU with logic gates.
Overall, it's a pretty good system. The middle Java class was completely worthless and a big waste of time though; in hindsight, I should have skipped it. Also, while we learned a bunch of cool things in the SICP class, every single other class except for programming languages/compilers completely ignored it. Most retaught some of the same concepts, but poorly.
Also, apart from SICP, there aren't any undergraduate classes doing functional programming! What's up with that?
At least at my university, there's plenty of C and C++--even in places where it blatantly doesn't fit, like the other version of the compilers class. And far, far too much Python. And too little functional programming. Ah well, c'est la vie.
I would love a compilers course taught in ML (maybe OCaml?), and it's a possibility, but not before I graduate :(.
Where are you studying? My undergrad (City College of New York) was mostly C++/Java with the exception of the PL course, which used Scheme. We also had an elective that taught x86 assembly.
I also had to find Haskell on my own, but I think it worked out reasonably well in the end. The type theory/semantics class did use a bit of OCaml, but it took a while to get to it.
Also, I should add that--largely due to my own preferences--I've taken a disproportionate number of classes that do not really focus on programming at all. The aforementioned type theory/semantics course only had a token amount of programming, and three other CS classes had no programming at all. They were also some of the coolest and most fun. (After all, I can do programming on my well enough; theory is a bit harder.)
I graduated from the University of Chicago, and they have a handful of undergrad classes using functional languages. The intro comp sci courses were using Haskell for the honors class, and Racket for the non-honors version when I took it. The compilers course there is taught using ML, though the fact that UChicago has several faculty who work on the development and maintenance of Standard ML may have something to do with this.
The C Programming Language takes a similar approach to exposition, and I think that's one of the reasons it's considered such a classic. It was certainly eye-opening for me when I first read it.
While I've heard good things about LYAH, I personally found its approach to be too wordy with too many not-illustrative-enough examples for each concept, and ultimately confusing. I felt like I gained a much better understanding from 2 hours spent reading "Learn Haskell Fast And Hard"(1) which is more concise, pragmatic, and presents a better logical build up of explanation and examples.
Manipulating lists is a solved problem in functional programming IMO, but I struggle to define good higher-order tree operations. Complex operators compose very poorly, and have too many options. So instead I write many simple operators, most of which I don't use frequently enough to remember that they exist at all. Or, I just give up and use recursion.
Is there any chance of you ever doing your compilers class on Coursera or just posting videos of the lectures online somewhere? Your blog posts are great, I'd love to be able to see the lectures as well.
Well, trees are recursive. Sometimes the cost bugs me, so I implement the tree as a list of lists ( each level in tree is its own list) ... this brings costs down but the code looks nasty and lot more bookkeeping under the hood.
If anything, I've fallen in love with recursion all over again...it is so bloody natural
Maps and folds, at the very least, generalize to trees fairly naturally. They also behave essentially the same way as for lists.
If you want more versatile functions, you could look at the famous "Bananas, Envelopes, Lenses and Barbed Wire" paper which introduces a bunch of recursion schemes that apply to trees as well as lists and other structures. These have Greek names you might have heard like "catamorphism" (a generalized fold).
Even if you don't end up using the functions, it's a good read. Might be a bit dense though, but it's not that bad or terribly heavy on math.
One really cool thing is that you do not you do not need to stick to lists. Many of these functions naturally generalize to other data types.
The simplest is map. It turns out that there are a ton of types that you can map a function over, and many of them are extremely useful. There are obvious examples like trees and arrays, but they don't even have to be containers. In Haskell, we call any type with a map function that behaves like the standard list function a functor. This is all a functor is--pretty simple.
The next interesting example is fold. We can also fold over non-list structures. In this case, the structures are usually containers like trees and arrays.In Haskell, this is what the Foldable class represents.
You can also think of zipping--in a very abstract sense of applying a multi-argument function to a bunch of structures--as generalized by applicative functors. However, lists by default form an applicative functor with pairwise application rather than zipping; there is a wrapper called ZipList that does a normal zip. Applicative functors also come up very often, not just for container types.
All these generalizations let you take all the powerful list functions you're familiar with and use them in new contexts. They also let you write more polymorphic code.
Interestingly, you can also generalize these functions in a different way--instead of taking a different structure, take a different function. This is where monads come in: you can generalize these functions over monads. In Haskell, the generalized versions are named by a trailing M: foldM, mapM and so on.
At a high level, this lets you customize how functions get applied. So you can have a fold that maintains internal state, propagates errors or even computes the result non-deterministically. The exact behavior is specified very declaratively by your choice of monad.
And, of course, as with any good abstractions, you can combine these. Particularly, you can take a foldable and use a bunch of the monadic functions on it. So you might end up using a non-deterministic fold on a tree. Just by itself, this seems exotic and hard to grasp. However, since it was built up step-by-step from familiar abstractions, it's actually easier to understand. Each step along the way is relatively simple and intuitive; you just have to put them together.
Now, what are the benefits to all this? The main one is that it gives your code more structure. A map a fold always behaves the same way for a given type where a for-loop could be doing anything. This makes it easier to read because you know the structure of the computation just from its name. It also makes the code easier to write since all the iteration logic is hidden away; you only have to write the function dealing with one "step"which means you cannot accidentally mess up how the steps are combined (no more off-by-one errors) and you can't accidentally couple the computation itself with the iteration logic. They're guaranteed to be separate because one is encapsulated into the higher-order function.
In many ways this parallels the transition from goto to structured programming.
Another advantage is that it lets you write more generic, more polymorphic code. This sort of code is easier to write because the types are more restrictive. There are simply less ways to mess up. Also, naturally, the code is more general, letting you reuse it in more places.
But it's not necessary to use these operations with functions at all; they were mostly invented and refined in the array programming space like APL. Just in a functional language you have all those nice lambdas to help out and can keep your language simple.
I haven't actually learned monads yet, but am I correct that the end of this article leaves readers a hair's breadth away from an introduction to monads (and without another round of distracting analogies)?
And that reminds me, lately I have been kicking around a suspicion that, given the right example, it wouldn't be hard to understand how to use call/cc to implement a lazy function in Scheme--perhaps one that returns a lazy list of the natural numbers.
As a step in that direction, I managed to construct the following example, which I hope is pretty clear.
; Return anon function returning its argument's value at n: _(n).
(define (at n) (lambda (s) (s n)))
; The curried (schönfinkeled) function t(m, n) = 2m+n: (t m) returns anon function 2m+_.
(define (t m) (lambda (n) (+ (* 2 m) n)))
; Example of using these "at" and "t" together.
(define (f n m) ((at n) (t m))) (display (f 5 3)) (newline); 11
(display (f 3 5)) (newline) ; 13
; Write an equivalent function inside-out using call/cc!
(define (g n m) ((t m) (call/cc (at n)))) (display (g 5 3)) (newline) ; 11
25 comments
[ 1.8 ms ] story [ 52.2 ms ] threadWhen I learned C and Unix, the instructor had us reimplement libs like string.h and stdio.h, command line tools like date, ls and cut and then build tools like make.
It made me a much better C programmer.
I think a nice approach would be to start off with a high-level, functional language like Haskell or Scheme, and then move down the ladder of abstraction in subsequent courses, culminating in a hardcore C (or maybe even assembly) course.
Overall, it's a pretty good system. The middle Java class was completely worthless and a big waste of time though; in hindsight, I should have skipped it. Also, while we learned a bunch of cool things in the SICP class, every single other class except for programming languages/compilers completely ignored it. Most retaught some of the same concepts, but poorly.
Also, apart from SICP, there aren't any undergraduate classes doing functional programming! What's up with that?
At least at my university, there's plenty of C and C++--even in places where it blatantly doesn't fit, like the other version of the compilers class. And far, far too much Python. And too little functional programming. Ah well, c'est la vie.
I would love a compilers course taught in ML (maybe OCaml?), and it's a possibility, but not before I graduate :(.
I had to discover and learn Haskell on my own :)
I also had to find Haskell on my own, but I think it worked out reasonably well in the end. The type theory/semantics class did use a bit of OCaml, but it took a while to get to it.
Also, I should add that--largely due to my own preferences--I've taken a disproportionate number of classes that do not really focus on programming at all. The aforementioned type theory/semantics course only had a token amount of programming, and three other CS classes had no programming at all. They were also some of the coolest and most fun. (After all, I can do programming on my well enough; theory is a bit harder.)
1.) http://yannesposito.com/Scratch/en/blog/Haskell-the-Hard-Way...
That's a major topic in my compilers class, and I'll likely write a post on that as well.
In the meantime, I recommend you check out "Scrap Your Boilerplate" in Haskell.
I don't know if my teaching style would translate well to Coursera or Udacity.
My classes tend to be very interactive. Assuming I recorded in front of a live class, some of that would come across.
But, it would lose some of the spontaneity that comes from sitting in the class and being able to interject.
I do post my (unanimated) lecture slides online as pdfs.
Well, trees are recursive. Sometimes the cost bugs me, so I implement the tree as a list of lists ( each level in tree is its own list) ... this brings costs down but the code looks nasty and lot more bookkeeping under the hood. If anything, I've fallen in love with recursion all over again...it is so bloody natural
If you want more versatile functions, you could look at the famous "Bananas, Envelopes, Lenses and Barbed Wire" paper which introduces a bunch of recursion schemes that apply to trees as well as lists and other structures. These have Greek names you might have heard like "catamorphism" (a generalized fold).
Even if you don't end up using the functions, it's a good read. Might be a bit dense though, but it's not that bad or terribly heavy on math.
The simplest is map. It turns out that there are a ton of types that you can map a function over, and many of them are extremely useful. There are obvious examples like trees and arrays, but they don't even have to be containers. In Haskell, we call any type with a map function that behaves like the standard list function a functor. This is all a functor is--pretty simple.
The next interesting example is fold. We can also fold over non-list structures. In this case, the structures are usually containers like trees and arrays.In Haskell, this is what the Foldable class represents.
You can also think of zipping--in a very abstract sense of applying a multi-argument function to a bunch of structures--as generalized by applicative functors. However, lists by default form an applicative functor with pairwise application rather than zipping; there is a wrapper called ZipList that does a normal zip. Applicative functors also come up very often, not just for container types.
All these generalizations let you take all the powerful list functions you're familiar with and use them in new contexts. They also let you write more polymorphic code.
Interestingly, you can also generalize these functions in a different way--instead of taking a different structure, take a different function. This is where monads come in: you can generalize these functions over monads. In Haskell, the generalized versions are named by a trailing M: foldM, mapM and so on.
At a high level, this lets you customize how functions get applied. So you can have a fold that maintains internal state, propagates errors or even computes the result non-deterministically. The exact behavior is specified very declaratively by your choice of monad.
And, of course, as with any good abstractions, you can combine these. Particularly, you can take a foldable and use a bunch of the monadic functions on it. So you might end up using a non-deterministic fold on a tree. Just by itself, this seems exotic and hard to grasp. However, since it was built up step-by-step from familiar abstractions, it's actually easier to understand. Each step along the way is relatively simple and intuitive; you just have to put them together.
Now, what are the benefits to all this? The main one is that it gives your code more structure. A map a fold always behaves the same way for a given type where a for-loop could be doing anything. This makes it easier to read because you know the structure of the computation just from its name. It also makes the code easier to write since all the iteration logic is hidden away; you only have to write the function dealing with one "step"which means you cannot accidentally mess up how the steps are combined (no more off-by-one errors) and you can't accidentally couple the computation itself with the iteration logic. They're guaranteed to be separate because one is encapsulated into the higher-order function.
In many ways this parallels the transition from goto to structured programming.
Another advantage is that it lets you write more generic, more polymorphic code. This sort of code is easier to write because the types are more restrictive. There are simply less ways to mess up. Also, naturally, the code is more general, letting you reuse it in more places.
This is imho the most important bit an imperative programmer needs to learn and understand functional.
And that reminds me, lately I have been kicking around a suspicion that, given the right example, it wouldn't be hard to understand how to use call/cc to implement a lazy function in Scheme--perhaps one that returns a lazy list of the natural numbers.
As a step in that direction, I managed to construct the following example, which I hope is pretty clear.
; Return anon function returning its argument's value at n: _(n).
(define (at n) (lambda (s) (s n)))
; The curried (schönfinkeled) function t(m, n) = 2m+n: (t m) returns anon function 2m+_.
(define (t m) (lambda (n) (+ (* 2 m) n)))
; Example of using these "at" and "t" together.
(define (f n m) ((at n) (t m))) (display (f 5 3)) (newline); 11
(display (f 3 5)) (newline) ; 13
; Write an equivalent function inside-out using call/cc!
(define (g n m) ((t m) (call/cc (at n)))) (display (g 5 3)) (newline) ; 11
(display (g 3 5)) (newline) ; 13
In fact, monads were secretly used throughout the article in the form of the comprehension notation (which desugars to the List monad).
There's also a tight connection between continuation-passing style, continuations and monads.
More on that in a future post...