Hobby-hacking Eric

2007-07-15

monomorphism and the unintentional fib

The monomorphism restriction is a simple problem with a scary name.

I think I've run into the first instance where I have actually been able to identify something as being the monomorphism restriction in action (*). The good news is that if you don't understand what the restriction is, this might be your chance. The bad news is that many Haskell newbies might have been hurt in the process, because it involves an unintentional fib that I told in near the beginning of the Haskell wikibook.

(*) I'd appreciate it if somebody could fact-check me on this.

circles and half-truths

High school Geometry. We've got a circle of radius 25 and we want to know its circumference (2 * pi * r). Now let's see what happens when we type it into GHCi

Prelude> let r = 25
Prelude> 2 * pi * r

<interactive>:1:4:
No instance for (Floating Integer)
arising from use of `pi' at :1:4-5
Possible fix: add an instance declaration for (Floating Integer)
In the second argument of `(*)', namely `pi'
In the first argument of `(*)', namely `2 * pi'
In the expression: (2 * pi) * r


Oops! At this point, the reader runs into types for the very first time. This morning, I realised to my horror that I might have given a very wrong explanation of the problem to the gentle Haskell newbie. I said

The main problem is that Haskell doesn't let you multiply Integers with real numbers. We'll explain why later, but for now, you can get around the issue by using a Double for r so that the pieces fit together:

Prelude> let r = 25.0
Prelude> 2 * pi * r
157.07963267948966


Which is true, but is only sort of a half-truth. The problem with my explanation is that it lets the reader walk away with the mistaken belief that numbers without a decimal point, such as 25, can only be integers, when really they can be any Num a. It's as if somebody had taught OCaml too recently and forgotten that haskell /= ocaml! (Coughs discretely)

A concrete example of why it's important to get this right can be found further down the chapter. Here, I want to show that we can use variables within other variables. So here's what I have the reader type in area = pi * 5^2:
Prelude> let area = pi * 5^2

And here everything works... except...


Except if you are a sharp-eyed reader, you remember from above that I had just said that types prevent you from multiplying integers with reals and I had unintentionally implied that numbers like 5 are integers. So if you are a sharp-eyed reader, you look at that thing and you say to yourself, "HUH? That shouldn't work! You can't multiply an integer with a real!"

monomorphism, like polymorphism without the poly

The real problem is not that we had set r to an integer. By right r = 25 should give us any Num a => a; however, since we do not give it a type signature, r gets restricted to being an Integer. In fact, the example of 2 * pi * r would have worked if (a) we had given r a polymorphic type signature or (b) we had run GHC with its 'no monomorphism restriction' extension.

polymorphic type signature

Here we add an explicit type signature to r. Everything works:
Prelude> let  r :: Num a => a; r = 25
Prelude> 2 * pi * r
157.07963267948966
(Thanks to shachaf on #haskell for reminding me that we can use {}/; syntax and showing me how to apply it to write type signatures)

-fno-monomorphism-restriction

And if you don't like type signatures, here's what it looks like running without the monomorphism restriction:
dewdrop /tmp % ghci -fno-monomorphism-restriction
___ ___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98.
/ /_\\/ __ / /___| | http://www.haskell.org/ghc/
\____/\/ /_/\____/|_| Type :? for help.

Loading package base ... linking ... done.
Prelude> let r = 25
Prelude> 2 * pi * r
157.07963267948966
No surprises.

helping the newbies

Clearly, my explanation needs to be fixed. I just need to figure out the right way to do it though. I really don't want to get too technical (the reader doesn't even know about types yet!), but I'll need to avoid lying to the reader. It's already bitten two users, and it took me one of my readers typing in this text for me to figure out what had happened:
You might be thinking that this won't work--isn't 5 an integer, and therefore 5^2 also an integer? And didn't we just get an error trying to multiply pi by an integer?. What's going on is that when you "let r = 25", the "r" you get is more restricted than using the literal string "25" or 5^2. Try :t r and :t 5^2 and see the difference

I'm not entirely satisfied with this attempt (sorry), and want to deal with the situation more gracefully. Just don't know how to go about it yet.

knowing, Knowing and poly/mono


Oh a word about the scary name 'monomorphism restriction'. I find it curious that I should have found that name scary for so long. I mean, for the longest time, I've told myself that I liked 'polymorphism' right? So how difficult would it have been to do a little etymology and notice that 'monomorphism' sounds exactly like 'polymorphism', except that you replace the 'poly-' (many) by 'mono-' (one). By the right, the two words have equivalent scariness! But for some reason, my brain somehow refused to recognise the fact. Instead, it associated one word with warm fuzzies and the other word with huh-does-not-compute.

Otherwise, one thing I found interesting about this is how you can simultaneously (a) hold a piece of knowledge and (b) not apply it consistently. For example, when I had written that module, I knew that numbers could be any Num a (and that you could do fun things making up crazy implementations of Num), yet at the same time as I was using this knowledge (I told myself 'true, but let's not talk about that now, no point confusing the newbies'), I can completely failed to apply that knowledge, because I went back and reflexively treated 25 as an Integer, probably due to all that freshman OCaml teaching. You know something, but you don't Know it.


5 comments:

Anonymous said...

it me might useful for the reader to notice than

let r () = 25
2 * pi * r ()

works.

Tristram Brelstaff said...

2*pi*25 also works.

I think the moral that you can draw from this is:

"Explicit is better than implicit."

(The Zen of Python by Tim Peters).

kowey said...

Thanks for the comments. I'll note that this is for an introductory text trying to present what a variable is. So part of the point was to show the user how to say things like "let r = 25". As for "r ()", well that's probably going to be a bit non-obvious for the new reader.

Cale Gibbard said...

For quite some time (before I actually had a close look at what the MR was), I had expected "monomorphism" to mean exactly what it usually means in mathematics: an injective homomorphism f, or more generally, one which has the property that for any g1 and g2, if f . g1 = f . g2 then g1 = g2.

So it is a particularly unfortunate piece of terminology, seeing as it can initially confuse those with both a mathematical and computer science background. On the other hand, it's the only sensible thing to refer to the opposite of polymorphism.

Matthew Cox said...

Well, the monomorphism restriction is really about preventing a let-bound name from having a polymorphic type. Maybe we should go back in time and call it the apolymorphism restriction?

As for the wikibook, maybe the best thing to do would be to not lie to the user. Say something like:

This failed because of a subtle rule of Haskell that's actually designed to protect you. Because Haskell is a strongly typed language, and because it's designed to make that strong typing transparent to programmers, it's possible for a lexical value such as 25 to have multiple possible values (one for each possible type.) For now, you can remember that the "monomorphism restriction" only lets there be a single type, and thus a single value, for a let binding. This keeps the language from duplicating values (wasting space on large values) and computations (wasting time on long computations) behind your back. If you really want to allow this duplication to occur, you'll need to supply a polymorphic type signature.