A coworker pointed out that the Advanced Functional Programming class at Harvard has a public Wiki. The semester has only just started, but there's already some interesting comments coming from the daily discussions. For example, on the first day, they had a puzzle of trying to figure out a way of writing postscript in haskell. They came up with something that could handle expressions like "psbegin push 2 push 3 add psend". I'm currently trying to one-up them by making something like "rpn [2, 3, add]" work.
On the second day, they read Why Functional Programming Matters, and then everybody in the class had to post a question. Reading a paper all by itself has a much different feel than reading the paper and then a bunch of comments by other people. For example, some people pointed out that the paper ignores issues like space leaks and over abstraction. Responding to the space leak question, the teacher posted a reference to this paper which describes a profiler for haskell that measures both time as well as space. I'm glad to have found this because space leaks have been a source of serious unease for me when trying to use haskell.
I've added their Wiki's RecentChanges to my list of links to check periodically. If you're interested in this kind of thing you might want to check it out as well.
Followups to Advanced Functional Programming:Posted on September 26, 2003 05:28 PM
More languages articles
Is there a problem description somewhere, beyond "do Postscript in Haskell?" The page you linked to just talks about some of the solutions, and I looked around to no avail.
Posted by: Ralph Richard Cook at September 26, 2003 09:33 PMI didn't see a problem description. It's not like MIT's online courseware initiative -- their wiki is just a place for people who take the class to collaborate. Presumably the problem was given orally in class.
After spending a couple hours on the problem, I've decided that it's not possible to one-up the solution that the class came up with. I did, however, learn a couple things about haskell in the attempt.
I had originally hoped to use a type class to allow me to create a list of "operation" objects that could then be applied sequentially. The main idea was going to be based on something like this:
class Op a where
op2func :: a -> [Int] -> [Int]
instance Op Int where
op2func val stack = val:stack
rpn :: (Op a) => [a] -> Int
rpn ops = ...
I was hoping that haskell's type checker would unify on the argument type of the "rpn" function to decide that it should automatically coerce the elements of the list to instances of the type class. But alas, haskell merely told me that I couldn't create a list of heterogenous types (in this case a list of Ints and functions). Apparently it didn't care that all the elements were members of the type class. I should have noticed that I wasn't even able to express this idea in the type of the "rpn" function -- the best I could do was to state that it took a list of a bunch of Ops that are actually all the same type. What bothers me is that I know how type classes are implemented, and so I know that something like this could work. I'm just not sure how to express it.
Anyway, after my first attempt failed, I tried to build on the technique used by the example that the class developed. When I started down this dead end, I thought that "psbegin push 1 push 2 add psend" would be parsed as
(psbegin (push 1 (push 2 (add (psend)))))
In other words, I thought that the operations took a kind of continuation that represented the rest of the computation. But it turns out that it's parsed like this:
(((((psbegin push) 1) push) 2) add) psend)
And the only reason it works is because of currying. To me, this feels like it's merely taking advantage of a quirk of the haskell parser, as opposed to being a real semantic technique. It does, however, take spectacular advantage of haskell's polymorphism features -- it almost feels like dependant types (the return type of psbegin depends on the return type of its argument, which almost feels like it depends on the actual value of its argument).
Even after realizing how haskell parsed the expression, I still hadn't given up. I decided to see if I could still make my type class idea work, by making psbegin return a function that promoted its argument to a function before calling it. This way you could write "psbegin 1" directly, without having to insert a "push" function. It would convert the integer to a function, and then apply that function. But the problem with this idea is that, while it works just fine, there's no way to ever get at the result. After you evaluate the entire expression, you are still left with a function that will convert any argument it receives into a stack operator function, and then call it. Sounds fine, except that the stack operator function is required to have exactly the same static type -- it also has to convert any arguments it receives into a stack function, and then call it. So you're stuck in the land of stack operator functions and you can't get out.
This design is very similar to the design of monads in that I'm lifting values into a special type that I then perform operations on, and that frustrated me for a long time because I knew that you could "un-lift" a monad to turn it back into a regular value. But eventually I realized that monads are values that you apply functions to, while what I had created were functions that you apply values to. And at that point I realized that there really, truly was no way to get out of the stack operator black hole.
At this point, I finally gave up and did a search to see if anybody else had a solution I hadn't considered. I came across this paper which was very interesting, but which basically confirmed my conclusion that it couldn't be done.
You simply have to have an explicit "push" operator in haskell. This, by the way, is a good example of static typing preventing me from solving a problem that would be trivial in a dynamic language (as long as the dynamic language had currying).
Someone wrote a paper on how to do something like printf in Haskell, which strikes me as a similar problem. IIRC they had an infix operator to stitch together the parts of the format, and then did the typeclass thing. But I suppose that would also be covered in the linked paper on embedding postfix, which I can't access the text of.
Stack sublanguages can also be a nice example of macros -- I wrote some macros you use like
(define swap (stack-op (y z) (z y)))
(define under+ (stack-op (x y z) ((+ x z) y)))
The paper with printf in ML-Family languages is Functional Unparsing.
Posted by: Matt at October 20, 2003 05:04 AMI like the stack-op macro :)
As for the printf example, given that the point is the syntax, I think relying on an infix operator is cheating.
Posted by: kim at October 20, 2003 11:29 AMI don't understand how it's cheating. I mean, I have to put all those %foo's for various foo's in regular printf. It's just the dual to C's weak dependent typing (not even really typing - but what else should I call it?).
Posted by: Matt at October 20, 2003 01:31 PMAck, I mangled my comment. What I meant was, it's cheating to use infix operators in order to create a postfix syntax. Please ignore the bit about printf.
Posted by: kim at October 20, 2003 04:26 PMYup, it's cheating. :) But not greatly more than [2, 3, add] is cheating, IMHO, compared to just "2 3 add".
Posted by: Darius at October 21, 2003 11:21 PM