Do I really want to be using a language where memoize is a PhD-level topic?

http://groups.google.com/group/clojure/msg/c2a9e8d27a1fff3f

by signa11 • 16 years ago

128 75 16 years ago

groups.google.com

greenlblue3• 16 years ago

This argument comes up against haskell over and over again and I think it is because it has some merit. Type level hackery and monad wizardry are great but it just feels like a whole bunch of smart people showing off about how clever they can be with avoiding state and pushing it all into some high level categorical constructs.

masklinn4• 16 years ago

> This argument comes up against haskell over and over again and I think it is because it has some merit.

Yes and no. As with many other things, there's a tradeoff between Haskell's purity and referential transparency and side-effecting constructs such as storing stuff in a local cache, which is what memoization does. You can't litter printfs or cache calls throughout your pure functions either, "for some reason". It makes sense that's it's a pain to do in a (non-IO/state) haskell function, because those are very much about mixing side-effects into the code.

A better solution would probably be to integrate memoization at the runtime level, with some compiler hints maybe. That way it becomes an implementation detail not an imperative side-effect, and the world is pure again.

Anyway yeah, if you can't bear with Haskell's constraints you can just use something else, such as MLs (in order not to give up static type safety). Whoop the fucking do.

klodolph7• 16 years ago

You can litter printfs in your code, you'll just get a lot of hate if you do it in library code that you share. It's fine when debugging to write a "debug printf" function using "unsafePerformIO". Yes, it mixes side effects into pure code, but that's fine for debugging purposes.

    -- totally OK! go ahead! it won't crash or anything!
    debugPrint :: String -> a -> a
    debugPrint s x = unsafePerformIO (putStrLn s >> return x)

You could also implement a memoization function using "unsafePerformIO". No, you won't get a visit from the FP purity police for doing so, it's perfectly fine. Why? Using "unsafePerformIO" in a function does NOT mean that that function is impure. It merely means that the compiler will not inform you whether the function is pure or impure -- the compiler's safety checks are bypassed when you use the function.

Here's how I'd type the memoize function:

    memoize :: Ord a => (a -> b) -> IO (a -> b)

Notice how it gives you a pure function out. No need to do stuff at the runtime level, or write compiler hints. It just works. If you want to memoize some nasty function:

    -- Totally fine! Unless nastyFunction is polymorphic...
    nastyFunction :: Paper -> PublishedBook
    nastyFunctionMemoized = unsafePerformIO (memoize nastyFunction)

If you're new to Haskell, don't write memoize yourself if you want a version that works with polymorphic functions as that requires some more advanced techniques. Most people who need a memoized function don't need a polymorphic one though.

yason3• 16 years ago

I've criticized Haskell many times, and being criticized many times of that.

You see, I would love to love Haskell but in practice the language just always turns out to be an overly intellectual exercise. Real world programs need to manage state, preferably in a very controlled way, but the bottom line is that they need to do that in some obvious and easy way.

It doesn't help if you explain me that you really don't need to explicitly store state anywhere, that you can just use monads to carry it over from computation to computation. Monads are an interesting abstraction per se but I don't want to use such heavy-weight artillery to make a mere assignment, to write a pointer to memory. I want my language to put some effort in protecting myself from the hazards of unintended concurrency but when I want to do it, the language must obey.

That said, Clojure is just perfect. For now, Clojure is my Blub.

klodolph7• 16 years ago

It sounds like Haskell just isn't your style, but you're saying that Haskell is bad for "real-world" programming. And it sounds like you've never really used Haskell seriously (just a guess, most Haskellers I've met get over their monad fixation within a few months, yet you describe them as "artillery"). If you like Clojure so much, why not go champion that instead of complaining about Haskell?

Besides, if you use "how easy is it to implement 'memoize'" as a benchmark then you'll always end up choosing a Lisp.

loup-vaillant2• 16 years ago

You never want "to make a mere assignment", nor "to write a pointer to memory". These are not problems you want solved, they are parts of a possible solution.

Haskell don't need assignments nor memory writes. It solves problems (including state management) differently. You may not like that, but don't say that not using some specific low-level feature is bad by itself.

jrockway8• 16 years ago

The description you give of "type-level hackery" and "monad wizardry" leads me to believe that you don't really understand what's going on. This is dangerous, because you are expecting these things to be complicated, but they are actually so simple that you've probably already invented them in your own computer programs. The Haskell community merely gives names to ideas you already know about.

This isn't "smart people showing off about how clever they can be", it's people giving names to things that they use everyday.

The problem people have with monads is that the word "Monad" does not describe something they're used to dealing with. A computer programmer is used to concrete things like lists, trees, functions, compilers; things you could hold in your hand (or at least draw on a whiteboard), poke at, and observe.

Monads can't be understood in this way, because they are not anything concrete; "Monad" is a word to describe concrete things that, individually, are all very different. It's like explaining the concept of "Green" to someone by showing them an apple, a tennis ball, and some grass clippings. They will never understand "Green", because you can't understand what Green is by seeing three examples of them. Green is a color, not some sort of weird tennis-ball-apple-grass-clipping hybrid.

Monads are the same way. List is a Monad. Reader is a Monad. State is a Monad. But when you look at these things and try to generalize, you might not see the parts that are the same, because the parts that are the same that make them all monads are hard to see.

I think the hard part is that you hear about what defines a monad ("return" and "bind" or "return", "fmap", and "join"), and don't see how some dual or triple like that helps you write computer programs. Each set of functions is so different from the other sets that the fact that they are all called "return" and "bind" doesn't seem to matter. And that's exactly right; at some level, it doesn't matter.

You use a List as a monad to combine computations that return multiple values, and you use Cont to write your programs in a continuation-passing style. Very different. Nothing similar at all, really. On the concrete level.

The similarity does matter at a higher level, though; noticing similarities means you can write parts of your program in advance, and just tweak those parts for each specific case.

An example is liftM2; it abstracts away the tedium of using a calling a two-arg function with monad-like semantics. If there were no similarities between List and Maybe, you'd have to write something like this:

   liftList2 f xs ys = concat $ (\x ->
                                 concat $ (\y -> [f x y])
                                          `map` ys)
                                 `map` xs

   -- this doesn't compile; I want to use more descriptive words than the Data.Maybe API does :)
   liftMaybe2 f x y = if has x then extract x -> \x'
                          if has y then extract y -> \y'
                                           makeMaybe f x' y'
                          else Nothing
                      else Nothing

(Here's how to use the functions, in case you aren't sure:

   liftList2 (,) [1,2] [3,4]      ==> [(1,3),(1,4),(2,3),(2,4)]
   liftList2 (,) [] [1..infinity] ==> []

   liftMaybe2 (,) (Just 10) (Just 20)     ==> Just (10, 20)
   liftMaybe2 (,) Nothing (Just "oh hai") ==> Nothing

These seem very similar. There is the same sort of nesting in both structures, we seem to be saying the same thing twice in both functions. We seem to be applying functions to values "inside" each of these things.

Maybe we can abstract those things away somehow, and make the two functions look a little more similar:

    newList x = [x]
    fmapList xs f = f `map` xs --
    joinList xs = concat xs

    liftList2 f xs ys = joinList $ fmapList xs $ \x ->
                        joinList $ fmapList ys $ \y ->
                        newList $ f x y
    -- hey, the code looks nicer already!

    newMaybe x = Just x
    fmapMaybe Nothing _ = Nothing
    fmapMaybe (Just x) f = Just $ f x
    joinMaybe Nothing = Nothing
    joinMaybe (Just x) = x

    liftMaybe2 f x y = joinMaybe $ fmapMaybe x $ \x' ->
                       joinMaybe $ fmapMaybe y $ \y' ->
                       newMaybe $ f x' y'

Now that we've given List and Maybe some common terminology, it's very hard not to see how these lift2 functions are nearly identical. We just need to do some refactoring, and then we can use the same definition for both!

    class Monad m where
        new :: a -> m a
        fmap :: m a -> (a -> b) -> m b
        join :: m (m a) -> m a

    instance Monad [] where -- haskell98 spells List as []
        new  = newList
        fmap = fmapList
        join = joinList

    instance Monad Maybe where
        new  = newMaybe
        fmap = fmapMaybe
        join = joinMaybe

    liftM2 f x y = join $ fmap x $ \x' ->
                   join $ fmap y $ \y' ->
                   new $ f x' y'

And there you go, that's what a Monad is. It's just refactoring, so we have less code to maintain! That's what any programmer would do, not just super-smart PhDs. You do the same thing every day!

skybrian• 16 years ago

Agreed that abstraction is itself the problem - very abstract things are more difficult to understand than concrete things, because there's nothing to grab onto.

I know you're trying, but you're going to lose the beginner as soon as you get to the code example - it's just too terse and foreign. Remember that people who don't know monads also don't understand Haskell very well, so they need to know your intentions before trying to read the code. You have to explain this in English.

First you'd have to explain what the comma function does (creates a pair), what liftList2 does (takes the cartesian product and applies an operator to each pair - oops, that assumes the reader knows what cartesian product means!) and what the liftMaybe2 does (applies a binary operator if both arguments are not null - er, I mean Nothing).

In Java all these methods would have JavaDoc, so you have some clue what the author intends before reading the code. I think readable Haskell would probably need five times as many lines of comments as actual code since so many functions are one-liners.

It's much like math: if you really want to explain things so a beginner will get it, you need half a page of text and maybe some diagrams per equation.

Personally I like this Monad tutorial. We can at least say that a Monad is more like a macro syntax than like a data structure and people will get the vague idea: http://kawagner.blogspot.com/2007/02/understanding-monads-fo...

greenlblue3• 16 years ago

I have a degree in mathematics so don't try to explain to me what abstract is. I'm no stranger to chasing diagrams and figuring out if something is a natural transformation. The problem is that haskell overlays all this heavy duty math on top of state computations and hopes that by throwing enough examples at the reader, kinda like you did, the reader will figure out that "return", "join", etc. are very special kinds of natural transformations. The fact remains that you are using categorical constructs to program and to me this is just a horrible idea because it confounds a whole bunch of ideas and is basically using a hammer to kill a fly. Just because every concept in programming can be coerced into being a monad doesn't mean it should and that's exactly what haskell does and don't even get me started on arrows. Semantic distinctions between concepts in programming are a good thing because they show beginners boundaries and allow them to apply the concept and gain mastery. There is such a thing as too much abstraction when you are trying to be practical because after all everything in mathematics is basically some kind of category but when you are integrating a function you are not thinking of limits and colimits. Haskell doesn't have many semantic distinctions between it's underlying concepts. Everything is a function, a type or a type constructor and that's it. Sure it's theoretically very beautiful but it's not very practical. There is no way a language with such constructs is going to gain any kind of followers other than people who already have a PhD and eat natural transformations for breakfast.

WorkerBee• 16 years ago

topic is a dud link - it takes me to a login page.

plinkplonk5• 16 years ago

here it is so you don't have to log in.

On Mon, Jul 19, 2010 at 4:34 PM, Jared <tri...@gmail.com> wrote: > I am curious; for the people with Haskell experience why did you decide to use Clojure? I am asking this because Haskell and Clojure seem to solve similar types of problems. When would you want to use Haskell instead of Clojure and visa-versa?

[Mark Engelberg replies]

I think stateful things are too hard to do in Haskell, and they are an important part of most real-world programs. Clojure's blend of persistent data structures with a variety of reference-type objects that can contain them feels much more pragmatic to me. Also, I'm just happier working in a dynamically-typed language.

As a side note, years ago, I wanted to write something in Haskell that worked like Clojure's memoize (which is implemented in a half-dozen or so lines of code in Clojure's core), and asked about it on the Haskell mailing list. I was pointed to a PhD dissertation on the topic of how to write memoize in Haskell. All I could think was,

"Do I really want to be using a language where memoize is a PhD-level topic?" "

jacquesm• 16 years ago

It may that Haskell will never be a mainstream language, but concepts from Haskell will find their way in to other languages, and that's good enough.

Not every language has to be a mainstream web-centric enterprise level application oriented (buzzwords enough like that ?) success in order to be successful by some other measure. Haskell has always been research oriented (avoid success at all cost), and if that's the goal then that's fine.

ekidd• 16 years ago

Not as my _only_ programming language, no. But in general, why not? I value programming languages for what they can teach me. Haskell does make state slightly difficult. (If you need it, just use the IO monad, already. It doesn't bite.) But Haskell makes certain other things easy, things which are extraordinarily difficult in almost any other programming language.

For most of my professional life, I've been paid to program in Common Lisp, Scheme, Dylan, etc. Macros, to me, are an ordinary and natural part of programming. But after a while, macros become boring: 99% of them are just a thin syntactic wrapper over something I already know.

In Haskell, you don't build higher-order abstractions using macros. Instead, you build your higher-order abstractions using math. And math is almost entirely stateless, lazy and functional. You are forced to think in terms of combinators, abstract algebras, algebraic optimizations, and, yes, category theory. Category theory is the closest link between the lambda calculus and mathematical logic, for example, allowing you to transform some very exotic programming paradigms into actual code.

So, yes, Haskell is hard, and it's an ongoing research project. You will spend a lot of time reading papers. (And frankly, you don't want to maintain somebody else's code if you haven't read the same papers.) But some of those papers and theses have blown my mind more in a single weekend than some entire years of hacking in Lisp.

Haskell is not the most practical language I know. (State is not the biggest problem for me, but rather the lack of subtyping.) But Haskell is the language I'd be saddest to forget, and the language which has stretched my mind the most.

jakevoytko• 16 years ago

There is a vast gulf between learning and using.

The original poster obviously enjoys learning new things: he posts on the Clojure mailing list, and hints that he has learned bits and pieces of Haskell. That places him early in the adoption curve. But when you want a language to get things done (one you can "use"), work from a comfort zone - start with a steady base, and branch out to unfamiliar topics. Some people are comfortable finding and reading academic papers as part of their workflow, and others aren't. That's their preference.

Other parts of your time should be spent the opposite way: start at the unfamiliar, and make it familiar. But it's not pragmatic to always work like this.

fogus• 16 years ago

There is (has always been?) an interesting formula for writing academic C.S. papers: define the most constrained environment imaginable and then do mundane things in it. Haskell is a very beautiful language in a very pure sense and it is the perfect garden for C.S. papers. Likewise, it's an incredibly fertile garden for language features and programming techniques. Is it hard? In some ways perhaps, but to me Javascript's notion of logical truthiness is extremely difficult to hold in my head. It's all relative I suppose.

WilliamLP• 16 years ago

> Javascript's notion of logical truthiness is extremely difficult to hold in my head.

So it isn't intuitive to you that an empty object and array should both evaluate to true, but neither are equal to true, the empty array is equal to false, and the empty object is neither equal to true _or_ false?

donw• 16 years ago

I've heard of duck-typing, and static-typing, but this is the first time I've heard of Schrödinger-typing...

gtani2• 16 years ago

Yeah, Appendix A Crockford's "Good Parts" (could be Appendix B, I can't remember. The book's so small I can't find it.

sesqu• 16 years ago

  > Boolean([])
  true
  > []==false
  true
  > [] == ![]
  true

How the hell does that work? Aren't all non-booleans implicitly cast?

edit: rephrased

klodolph7• 16 years ago

A couple years back I read a blog post with someone complaining about how hard it was to implement the traditional Lisp "map" / "mapcar" function. Specifically, one that took N lists and a single function with N arguments. The author was totally right, too. I could implement this generalized "map" function in Haskell, but it required defining an extra type class which is a little extreme.

Of course, the real problem is that people who are new to Haskell expect to sit down and solve problems in the same way they've been solving problems all along. This author was used to the "map" function from Lisp, and wasn't thinking about whether it was necessary, or whether Haskell had a different way of doing things.

Here's what the "mapN" function does:

    > mapN (+1) [1,2]
    [2,3]
    > mapN (+) [1,2] [5,8]
    [6,10]

The reason that we don't want to use "mapN" in Haskell is because of the following problem:

    > mapN (+) [1,2]
    ???

The result is either "[Int] -> [Int]" or "[Int -> Int]", with no clue as to which is correct. This is why Haskell has "zipWith", "zipWith3", ... Not as pedantry, but because the alternative is ambiguous. (You can use Control.Applicative + ZipList, but that's a tad verbose).

My conclusion is that Haskell's differences are what throw people off -- programmers have to relearn how to do things they thought they had figured out for good years ago. (In this case, "everything is curried" means "varargs requires type classes"). It's FINE if you don't want to learn to do things differently and I won't think less of you, I respect your choices for what you do with your precious free time, and I understand that you might want stuff just to work now without learning anything, just please stop stereotyping the Haskellers as a bunch of ivory tower PhDs. I'm not even done with my Bachelor's.

llimllib• 16 years ago

If you want to suggest that the main problem is people "trying to solve problems in the same way they've been solving problems all along", then you should have an answer for how you implement memoization "the haskell way".

If not, your "conclusion that Haskell's differences are what throw people off" is incorrect.

I don't think the author of the email is "stereotyping the Haskellers as a bunch of ivory tower PhDs", he's relating a story that's actually true of finding out that a basic technique he wanted to implement was most easily implemented by following the technique in a PhD thesis.

astine• 16 years ago

Now, I could be very wrong, but it is my understanding that Lazy Evaluation will provide the main benefits of memoization, without any action on the part of the programmer.

johngunderman• 16 years ago

I had this discussion once, and was presented with the following options:

Ideally, lazy evaluation will automatically memoize all your computations. Haskell's 'thunk' system does this in part. However, doing full memoization on most functions will result in huge memory bloat. Which brings us to the essential trade off of memory vs. cpu time. By default, GHC will conserve memory and memoize only when it is obvious that you want values cached. If you want memoization, there are a few things you can do.

1) Add 'let' clauses to your function bodies. GHC will automatically memoize these.

2) Add certain compiler flags for automatic memoization (I don't know what these are, but I know they exist)

3) do it "semi-manually" by generating closures.

I'm sure there are other options, but these three are relatively simple to implement without even needing a memoize function (Though I'm sure one can be written).

loup-vaillant2• 16 years ago

"PhD" may be a scary, Haskell's theses are not. Most academic paper I've read about it are quite readable (I don't have a PhD). The only serious prerequisite for a competent programmer is an introductory course on ML or Haskell.

skm3• 16 years ago

Actually, arrays in Haskell are automatically memoized and lazily evaluated. So in most practical situations you get memoization for free.

For example, imagine you need to calculate a function f(n) for various values of n (let's say for n ranging from 0 to N). You simply define an array memo_f such that memo_f!n = f(n). ('!' is the array selection operator in Haskell).

Because Haskell evaluates lazily (i.e. not until it absolutely has to), it simply stores a link to the definition of the function for each array element. But once a particular array element is used, that link is replaced by the calculated answer.

I'll post some actual code to demonstrate this in a minute, just in case anyone's interested.

skm3• 16 years ago

Haskell code: (explanation below)

    import Data.Array
    
    f :: Integer -> Integer
    f n = sum [0..n]
    
    largeNumber = round 2e6 :: Integer
    
    memo_f :: Array Integer Integer
    memo_f = listArray (0,largeNumber) [ (f n) | n <- [0..largeNumber] ] 
    
    
    main = do
        putStrLn (show (memo_f!largeNumber))     -- slow
        putStrLn (show (memo_f!(largeNumber-1))) -- slow
        putStrLn (show (memo_f!(largeNumber)))   -- fast
        putStrLn (show (memo_f!(largeNumber-1))) -- fast
        putStrLn (show (memo_f!(largeNumber-2))) -- slow
        putStrLn (show (memo_f!(largeNumber-3))) -- slow
        putStrLn (show (memo_f!(largeNumber)))   -- fast
        putStrLn (show (memo_f!(largeNumber-2))) -- fast
        putStrLn (show (memo_f!(largeNumber-4))) -- slow
        putStrLn (show (memo_f!(largeNumber-5))) -- slow

When I run this, I see nothing for about 3 seconds (that's the time spent setting up the array). Then the numbers commented '-- slow' take about 1/3 second to print, while the numbers commented '--fast' print instantaneously, because they were calculated previously. (I'm on a recent macbook air, in case anyone's curious about the timings). Obviously to calculate the entire array of values would take far too long (like a week or so).

yaroslavvb• 16 years ago

Well, that looks easy...so why are people saying that writing memoization in Haskell is PhD-thesis level task?

bpyne2• 16 years ago

I'd like to look at a different facet of the issue. My employer mostly implements COTS; our vendors drive our technology choices. The vendors of our two most critical systems decided on JVM based languages - Java and Groovy - so we're moving in their direction.

Java is new to most of my department. Currently people use C, SQL, and PL/SQL. I started with Java in 1998: it's not very exciting for me anymore. I'd like to use languages with greater abstraction capabilities. Despite being a really attractive language, Clojure is a tough sell because of its Lisp-like syntax: being a JVM-based language I can probably still get it in house for small apps.

Haskell, however, is non-JVM and has unique features by comparison with Java. This combination make it impossible to make an argument for despite all the goodness that it has. Unfortunately for me, it's relegated to the category of a language I'll play with periodically and someday hopefully use in industry.

cageface• 16 years ago

Have you looked at Scala? It's sort of like a Haskell for the JVM. It's very easy to integrate Scala into a Java project and to gradually learn Scala if you have a Java background.

bpyne2• 16 years ago

Thanks for the reply.

Yes I have. I didn't want to mention it in my original response to avoid taking the topic away from Haskell and Clojure.

dons• 16 years ago

Long and detailed discussion, including original participants, on Reddit, http://www.reddit.com/r/programming/comments/crgxs/do_i_real...

My take away:

* The Haskell culture is to take questions seriously * In doing so, the literature will be cited where appropriate * Some people get turned off by research papers

In this case, the guy asked a fairly profound question, and received a long, friendly answer, which included references to the literature.

Also, it plays on a stereotype, hence all the upvotes.

swannodette2• 16 years ago

Rich Hickey about this thread from the ML -

  Everyone, please refrain from language wars. Haskell is a tremendously
  ambitious and inspiring language, for which I have the highest
  respect. There is zero point in bashing it (or its users) in this
  forum.

jrockway8• 16 years ago

But Haskell users picked the wrong religion! God won't like us anymore if we don't bash all other languages!

(And is it really "bash" when you accuse the users of being too smart?)

Do I really want to be using a language where memoize is a PhD-level topic?

Related Stories