[clean-list] Why functional programming matters more
Marco Kesseler
m.kesseler@aia-itp.com
Wed, 12 Dec 2001 10:31:54 +0100
This is a multi-part message in MIME format.
------=_NextPart_000_0005_01C182F8.37E5EC80
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
RE: [clean-list] Why functional programming matters moreHi Erik,
----- Original Message -----=20
From: Erik Zuurbier=20
To: 'clean-list@cs.kun.nl'=20
Sent: Wednesday, December 12, 2001 9:13 AM
Subject: RE: [clean-list] Why functional programming matters more
I find John Hughes' algorithms also beautiful because they display =
plenty of opportunities for deterministic parallellism. An experimental =
Clean-version once supported that with {P} and {I} annotations =
(respectively Parallel and Interleaved reduction). It had its own =
(rudimentary?) load balancing scheme.
If I remember correctly (it's been a long time since I read John Hughes' =
paper), pruning just consisted of not accessing certain parts of the =
result tree that were lazily produced. Hence only the parts that were =
actually passed on by the pruning function would get evaluated. The =
whole point of the pruning step was that the algorithm automatically =
became less demanding, without having to change anything to the =
computing part.
Lazy evaluation is essential here. Adding speculative parallellism =
changes all that, and - if my memory serves me right -John's paper did =
not say anything about how it would affect his algorithm.=20
Still, I think one could add (bounded) speculative parallel evalution to =
the computation, without considering the - possibly manual - pruning =
step. So, I do not understand why this would lead to a particular =
sequential reduction order (except for the pruning step, that is).
regards,
Marco
----------------------------------------------------------------------
Aia Software B.V. Phone: +31 24 371 02 30
PO Box 38025 Fax: +31 24 371 02 31
6503 AA Nijmegen URL: http://www.aia-itp.com
The Netherlands
----------------------------------------------------------------------
This E-mail and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they
are adressed. If you have received this E-mail in error please notify
the postmaster (postmaster@aia-itp.com). The authenticity of this
message cannot, at this moment, be guaranteed by ourselves. For this
reason no legal rights may be granted should the contents differ to
the original sent message. The Aia log-file of sent messages is deemed
to be the sole, true transcript of communication unless the contrary,
other than the received message, can be proven.
----------------------------------------------------------------------
------=_NextPart_000_0005_01C182F8.37E5EC80
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>RE: [clean-list] Why functional programming matters =
more</TITLE>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 5.50.4134.600" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Hi Erik,</FONT></DIV>
<BLOCKQUOTE dir=3Dltr=20
style=3D"PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; =
BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<DIV style=3D"FONT: 10pt arial">----- Original Message ----- </DIV>
<DIV=20
style=3D"BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: =
black"><B>From:</B>=20
<A title=3DEZuurbier@Abz.nl href=3D"mailto:EZuurbier@Abz.nl">Erik =
Zuurbier</A>=20
</DIV>
<DIV style=3D"FONT: 10pt arial"><B>To:</B> <A =
title=3Dclean-list@cs.kun.nl=20
href=3D"mailto:'clean-list@cs.kun.nl'">'clean-list@cs.kun.nl'</A> =
</DIV>
<DIV style=3D"FONT: 10pt arial"><B>Sent:</B> Wednesday, December 12, =
2001 9:13=20
AM</DIV>
<DIV style=3D"FONT: 10pt arial"><B>Subject:</B> RE: [clean-list] Why =
functional=20
programming matters more</DIV>
<P><FONT face=3DArial size=3D2>I find John Hughes' algorithms also =
beautiful=20
because they display plenty</FONT><FONT face=3DArial size=3D2></FONT> =
<FONT=20
face=3DArial size=3D2>of opportunities for deterministic parallellism. =
An=20
experimental</FONT><FONT face=3DArial size=3D2></FONT> <FONT =
face=3DArial=20
size=3D2>Clean-version once supported that with {P} and {I}=20
annotations</FONT><FONT face=3DArial size=3D2></FONT> <FONT =
face=3DArial=20
size=3D2>(respectively Parallel and Interleaved reduction). It had=20
its</FONT><FONT face=3DArial size=3D2> own</FONT> <FONT face=3DArial=20
size=3D2>(rudimentary?) load balancing scheme.</FONT></P></BLOCKQUOTE>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>If I remember correctly (it's =
been a long=20
time since I read John Hughes' paper), pruning just consisted of not =
accessing=20
certain parts of the result tree that were lazily produced. Hence only =
the parts=20
that were actually passed on by the pruning function would get =
evaluated. The=20
whole point of the pruning step was that the algorithm automatically =
became less=20
demanding, without having to change anything to the computing =
part.</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Lazy evaluation is essential =
here. Adding=20
speculative parallellism changes all that, and - if my memory serves me =
right=20
-John's paper did not say anything about how it would affect his =
algorithm.=20
</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Still, I think one could add =
(bounded)=20
speculative parallel evalution to the computation, without considering =
the -=20
possibly manual - pruning step. So, I do not understand why this would =
lead to a=20
particular sequential reduction order (except for the pruning step, that =
is).</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>regards,</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>Marco</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV dir=3Dltr><FONT face=3DArial=20
size=3D2>----------------------------------------------------------------=
------<BR>Aia=20
Software=20
B.V. &nb=
sp; =20
Phone: +31 24 371 02 30<BR>PO Box=20
38025 &n=
bsp; &nb=
sp; =20
Fax: +31 24 371 02 31<BR>6503 AA=20
Nijmegen  =
; =
=20
URL: </FONT><A href=3D"http://www.aia-itp.com"><FONT =
face=3DArial=20
size=3D2>http://www.aia-itp.com</FONT></A><BR><FONT face=3DArial =
size=3D2>The=20
Netherlands<BR>----------------------------------------------------------=
------------<BR>This=20
E-mail and any files transmitted with it are confidential =
and<BR>intended solely=20
for the use of the individual or entity to whom they<BR>are adressed. If =
you=20
have received this E-mail in error please notify<BR>the postmaster =
(</FONT><A=20
href=3D"mailto:postmaster@aia-itp.com"><FONT face=3DArial=20
size=3D2>postmaster@aia-itp.com</FONT></A><FONT face=3DArial size=3D2>). =
The=20
authenticity of this<BR>message cannot, at this moment, be guaranteed by =
ourselves. For this<BR>reason no legal rights may be granted should the =
contents=20
differ to<BR>the original sent message. The Aia log-file of sent =
messages is=20
deemed<BR>to be the sole, true transcript of communication unless the=20
contrary,<BR>other than the received message, can be=20
proven.<BR>--------------------------------------------------------------=
--------</FONT></DIV></BODY></HTML>
------=_NextPart_000_0005_01C182F8.37E5EC80--