Implicit Parameters

Chris Angus [email protected]
Mon, 4 Feb 2002 10:39:04 -0000


This message is in MIME format. Since your mail reader does not understand
this format, some or all of this message may not be legible.

------_=_NextPart_001_01C1AD68.2AB6ED80
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

I'm obviously missing something here.

I dont understand what monomorphism has to do with=20
the given example as the implicit parameter would be=20
the same type [a] for some type a in each case.

If we made the parameter explicit then=20
removing the type definition would not cause this=20
problem. Are implicit parameters not simply made explict
by the compiler?



-----Original Message-----
From: John Hughes [mailto:[email protected]]
Sent: 04 February 2002 10:26
To: [email protected]; [email protected]
Subject: Re: Implicit Parameters



	Suppose I have the following function definition:

	  app :: (?ys :: [a]) =3D> [a] -> [a]
	  app xs =3D
	    case ?ys of
	      []      -> xs
	      (y:ys') -> y : (app xs with ?ys =3D ys')

	This function appends its argument to its implicit argument,
	by recursively changing the implicit argument. For example:

	  Hugs> app [1,2] with ?ys =3D [3,4]
	  [3,4,1,2]

	So far so good! Now, since Haskell has type inference, we
	can leave out the type signature:

	  -- app :: (?ys :: [a]) =3D> [a] -> [a]
	  app xs =3D
	    case ?ys of
	      []      -> xs
	      (y:ys') -> y : (app xs with ?ys =3D ys')

	Let us check if it still works again:

	  Hugs> app [1,2] with ?ys =3D [3,4]
	  [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,{Interrupted!}

	And, stunningly, it doesn't! Why doesn't this work?

	That is because type inference assumes that the body of
	`app' is monomorphic, i.e. has no context in its type.
	Therefore, the recursive call to app where ?ys is changed,
	had no effect at all.

	It works with the type signature there, because in order to
	implement type checking (note: not type inference) with
	polymorphic recursion demands to use the stated type in
	checking the body of the function.

	Mark Shields, Simon Peyton-Jones, and I, and also J=F6rgen
	Gustavsson have been discussing several modest solutions to
	this (we believe it is not needed to do full type inference
	that can deal with polymorphic recursion to solve this
	problem).

Not so fast! Proposing a "solution" means this is regarded as a =
"problem"!
But
what is to say that the first behaviour is "right" in any general =
sense?

The important thing is that the language semantics is clear, and this =
is a
semantic question.  The static semantics of Haskell *is* clear: =
recursive
calls are monomorphic unless a type signature is given; this is the =
basis
for
understanding the behaviour above. When implicit parameters are used, =
it's
very important to be aware whether a binding is monomorphic or not =
(can't
resist plugging :=3D again!). Will your "solution" make understanding =
when a
binding is monomorphic simpler? If not, it could be worse than the =
"problem"
-- and the fact that it makes this one example behave as you want is no
justification.

John

_______________________________________________
Haskell mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell

------_=_NextPart_001_01C1AD68.2AB6ED80
Content-Type: text/html;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
5.5.2653.12">
<TITLE>RE: Implicit Parameters</TITLE>
</HEAD>
<BODY>

<P><FONT SIZE=3D2>I'm obviously missing something here.</FONT>
</P>

<P><FONT SIZE=3D2>I dont understand what monomorphism has to do with =
</FONT>
<BR><FONT SIZE=3D2>the given example as the implicit parameter would be =
</FONT>
<BR><FONT SIZE=3D2>the same type [a] for some type a in each =
case.</FONT>
</P>

<P><FONT SIZE=3D2>If we made the parameter explicit then </FONT>
<BR><FONT SIZE=3D2>removing the type definition would not cause this =
</FONT>
<BR><FONT SIZE=3D2>problem. Are implicit parameters not simply made =
explict</FONT>
<BR><FONT SIZE=3D2>by the compiler?</FONT>
</P>
<BR>
<BR>

<P><FONT SIZE=3D2>-----Original Message-----</FONT>
<BR><FONT SIZE=3D2>From: John Hughes [<A =
HREF=3D"mailto:[email protected]">mailto:[email protected]</A>]</FON=
T>
<BR><FONT SIZE=3D2>Sent: 04 February 2002 10:26</FONT>
<BR><FONT SIZE=3D2>To: [email protected]; [email protected]</FONT>
<BR><FONT SIZE=3D2>Subject: Re: Implicit Parameters</FONT>
</P>
<BR>
<BR>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>Suppose I =
have the following function definition:</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; app =
:: (?ys :: [a]) =3D&gt; [a] -&gt; [a]</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; =
app xs =3D</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>&nbsp;&nbsp;&nbsp; case ?ys of</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =
[]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -&gt; xs</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (y:ys') -&gt; y : (app xs with =
?ys =3D ys')</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>This =
function appends its argument to its implicit argument,</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>by =
recursively changing the implicit argument. For example:</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; =
Hugs&gt; app [1,2] with ?ys =3D [3,4]</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; =
[3,4,1,2]</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>So far so =
good! Now, since Haskell has type inference, we</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>can leave =
out the type signature:</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; -- =
app :: (?ys :: [a]) =3D&gt; [a] -&gt; [a]</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; =
app xs =3D</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>&nbsp;&nbsp;&nbsp; case ?ys of</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; =
[]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -&gt; xs</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (y:ys') -&gt; y : (app xs with =
?ys =3D ys')</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>Let us =
check if it still works again:</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; =
Hugs&gt; app [1,2] with ?ys =3D [3,4]</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>&nbsp; =
[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,{Interrupted!}</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>And, =
stunningly, it doesn't! Why doesn't this work?</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>That is =
because type inference assumes that the body of</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>`app' is =
monomorphic, i.e. has no context in its type.</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>Therefore, the recursive call to app where ?ys is =
changed,</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>had no =
effect at all.</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>It works =
with the type signature there, because in order to</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>implement =
type checking (note: not type inference) with</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>polymorphic recursion demands to use the stated type in</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>checking =
the body of the function.</FONT>
</P>

<P>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>Mark =
Shields, Simon Peyton-Jones, and I, and also J=F6rgen</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>Gustavsson have been discussing several modest solutions =
to</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>this (we =
believe it is not needed to do full type inference</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=3D2>that can =
deal with polymorphic recursion to solve this</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT =
SIZE=3D2>problem).</FONT>
</P>

<P><FONT SIZE=3D2>Not so fast! Proposing a &quot;solution&quot; means =
this is regarded as a &quot;problem&quot;! But</FONT>
<BR><FONT SIZE=3D2>what is to say that the first behaviour is =
&quot;right&quot; in any general sense?</FONT>
</P>

<P><FONT SIZE=3D2>The important thing is that the language semantics is =
clear, and this is a</FONT>
<BR><FONT SIZE=3D2>semantic question.&nbsp; The static semantics of =
Haskell *is* clear: recursive</FONT>
<BR><FONT SIZE=3D2>calls are monomorphic unless a type signature is =
given; this is the basis for</FONT>
<BR><FONT SIZE=3D2>understanding the behaviour above. When implicit =
parameters are used, it's</FONT>
<BR><FONT SIZE=3D2>very important to be aware whether a binding is =
monomorphic or not (can't</FONT>
<BR><FONT SIZE=3D2>resist plugging :=3D again!). Will your =
&quot;solution&quot; make understanding when a</FONT>
<BR><FONT SIZE=3D2>binding is monomorphic simpler? If not, it could be =
worse than the &quot;problem&quot;</FONT>
<BR><FONT SIZE=3D2>-- and the fact that it makes this one example =
behave as you want is no</FONT>
<BR><FONT SIZE=3D2>justification.</FONT>
</P>

<P><FONT SIZE=3D2>John</FONT>
</P>

<P><FONT =
SIZE=3D2>_______________________________________________</FONT>
<BR><FONT SIZE=3D2>Haskell mailing list</FONT>
<BR><FONT SIZE=3D2>[email protected]</FONT>
<BR><FONT SIZE=3D2><A =
HREF=3D"http://www.haskell.org/mailman/listinfo/haskell" =
TARGET=3D"_blank">http://www.haskell.org/mailman/listinfo/haskell</A></F=
ONT>
</P>

</BODY>
</HTML>
------_=_NextPart_001_01C1AD68.2AB6ED80--