Re: how is polymorphism used?

[Neel Krishnaswami <address@hidden>]

Alan Bawden writes:
> From: Ken Shan <ken@digitas.harvard.edu>
> >
> > ...  I have more than once found bugs in my code because the type
> > inferred by the compiler for a function is more or less general than
> > what I expected or intended....
> 
> It's clear that this is a possibility, but I don't recall any cases
> from my own experience where the system inferred a more general type
> than I had in mind, and where this was a symptom of a bug rather
> than merely being unanticipated generality.  I'd be interested in
> seeing a really compelling example.

I see this all the time. Here's an example from a parser I am
writing. It's a recursive-descent parser, but I make use of many
parser combinators to help ensure that the syntax for the language is
uniform -- whenever there are parallel constructions in the language,
I pull them out into a combinator so that there won't never be subtle
variations in what is legal syntax in different contexts. Ocaml's type
inference has helped me find many bugs in my combinators.

One of the more common combinators is the combinator for bracketed,
delimited, sequences -- eg, "[1, 2, 3]" or "{e1; e2; e3;}". The type
signature for this is

val sequence :
  ('a Stream.t -> 'b) ->
  left:  ('a -> bool) ->
  sep:   ('a -> bool) -> 
  right: ('a -> bool) ->
    ('a Stream.t -> 'b list)

The first argument is a parser -- a function that takes a stream of
some token type 'a, and returns a value of type 'b. Then you need to
supply three functions that can tell whether a token is the left
delimiter, the separator, or the right delimiter. Then you get a new
parser as the result, which yields a list of parse values (each of the
elements in the sequence).

When I wrote my first version, I got the following inferred type:

val sequence :
  ('a Stream.t -> 'b) ->
  left:  ('c -> bool) ->  (*                                   *)
  sep:   ('d -> bool) ->  (* Notice the token type is 'c,'d,'e *)
  right: ('e -> bool) ->  (*                                   *)
    ('a Stream.t -> 'b list)

I could tell immediately from the types that the delimiter token test
functions were never getting called, which is why the type inference
system was able to give them a polymorphic type. So I went online, and
asked around until someone was able to explain to me that I was using
the wrong syntax in the parser code -- I had not properly understood
the documentation.


-- 
Neel Krishnaswami
neelk@alum.mit.edu