From: mccarrol@remus.rutgers.edu (Mark C. Carroll <MC>)
Newsgroups: alt.lang.ml
Subject: Re: ML neophyte w/ basic type question
Keywords: ml
Date: 15 Dec 92 21:51:18 GMT
Distribution: all
Organization: Rutgers Univ., New Brunswick, N.J.

]I just started learning ML a few days ago and I am
]having trouble figuring out how to predict what the
]type of a function will be reported as. Can someone
]explain how to determine a functions type and how to
]read the type that is reported back?
]

Put very simply, what happens is: the compiler looks at the code, and
looks for anything in the code that can constrain the type of the
function. Then it propogates those constraints, and forms the most
general type that matches them.

The example that you use isn't valid syntax (at least not in SML,
which is the system I use, but I don't remember CAML being that
different in the core language.)

I'll give a couple of quick examples:

	fun fact(x) = x * fact(x-1);

  The most general type of this, before any type constraints are
  considered is:
     a -> b
  That is, a single input argument mapping to a single output value,
  no constraints.

  Looking at this, the compiler first sees that fact must return
  something numeric, and take an argument of the same numeric type.
  It can determine this, because * requires that its arguments be
  numeric, and of the same type. Since the other argument to the *
  is also the argument to the function, they must be the same type.
  So, it can restrain it to "a -> a", where a must be numeric.

  Next, it can tell that the argument must be an integer, because 
  - requires its arguments to be of the same type, and 1 is an
  integer. So, the complete typing is "int -> int".

Now, for a harder one:

fun compose(f,g) = fn (x) => f(g(x));

which returns:
>	val compose = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

Before any analysis, we start with:
	t1 * t2 -> t3
(That is, two argument function returning one value)

We see that f and g both get applied, so they must be functions, and
the result is also a function. So we expand to
	(t1a -> t1b) * (t2a -> t2b) -> (t3a -> t3b)

Now, since f is applied to the output value of g, the output
value of g must have the same type as the input of f:
	(t2b -> t1b) * (t2a -> t2b) -> (t3a -> t3b)

Further, the output value of the entire function is the output from a
call to f, so the result type must have the output type of f as its
output type:
	(t2b -> t1b) * (t2a -> t2b) -> (t3a -> t1b)

And finally, the input value is used as an argument to g, so the 
input value of the result must have the same type as the input
value to g. So:
	(t2b -> t1b) * (t2a -> t2b) -> (t2a -> t1b)

Simplifying names to match the output from my SML compiler:
	(a -> b) * (c -> a) -> (c -> b)

That's the basic idea of what goes on. Try getting a text on ML if you
want to know more. There's a very good tutorial available through the
net on SML. (I forget the location, maybe some other kind soul can
post the location of Robert Harper's "Introduction to Standard ML").

	<MC>
-- 
|| Mark Craig Carroll: <MC>     ||"I live to see my fondest dreams realized,
|| Univ of Delaware, Dept of CIS|| Of living under the sights and sounds of
|| Grad Student/Labstaff Hacker || the gifted, Who gave so much to me"
|| carroll@udel.edu             ||   - _Feed_the_Fire_, Happy Rhodes
Newsgroups: alt.lang.basic