unique abstract types functional?

[Maarten de Mol]

-----Original Message-----
From: Zuurbier, E. - AMSXE <Erik.Zuurbier@KLM.NL>
To: 'clean-list@cs.kun.nl' <clean-list@cs.kun.nl>
Date: Friday, July 02, 1999 3:28 PM
Subject: unique abstract types functional?


>A language is purely functional if the function's result depends only on 
>its explicit input and on nothing else.
>
>I seem to recall that this is expressed along the following lines:
>
>For all x1, x2 and fun: if x1 = x2, then (fun x1) = (fun x2)
>
>Clearly, equality is not the same as the == operator in Clean, as I 
>could give that any definition, including for instance <, which would 
>invalidate the above expression. If x1 and x2 have an abstract type, 
>what does x1 = x2 mean? I cannot determine equality by inspection, as 
>abstract types don't allow that.

You could consider an abstract type only functional *if* it has a 
(hidden) implementation somewhere. You could then easily define equality 
on a theoretical level, by exposing this implementation. This of course 
doesn't work for the *World, but it will work for any user defined 
abstract type. 

>
>So maybe we ought to use pointer equality (if this is not a hilarious 
>caseof mixing up theory and implementation). Then, if I don't trust a 
>given function fun, I could test to see whether its output ever differs. 
>Assume that x has an abstract type and that Initialize is defined to 
>produce a value of the type:
>
>Start
> # x = Initialize 1.234
> = (fun x,fun x,fun x,fun x,fun x,fun x,fun x,fun x)
>
>Now of course, if the outputs are all the same, this does not prove
>anything, but if some differ, fun has clearly been exposed as
>non-functional.
>
>Then assume that the abstract type is also unique. Then I cannot even 
>write this test program! I must conclude that since you cannot express a 
>test program to expose fun to be non-functional, fun must be functional. 
>Is this true?

You cannot write the testprogram in this form. But the problem is not
the uniqueness, but that the unique x is 'coming from nowhere'. If the
value x would be constructed somewhere by a function, then this problem
would not exist:
   F :: *Object
   F = ...

   Start = (fun F, fun F, fun F, fun F...)
This is a legal program. You can rewrite (although it may not be easy)
any program manipulating unique abstract objects to this form.
(correct me if I'm wrong; I don't see the problem here; but then again
it is Friday afternoon ;-))

Again, there is one exception, and it is the *World. There is no way to
construct a world yourself, it is given by magic at startup. (unique 
abstract types that can only be constructed using the *World are 
exceptions as well) Instances of all other types *HAVE* to be constructed
somewhere, and this construction can always be copied.

>
>This e-mail was triggered by the 'world as value' discussion, as *World 
>is a unique abstract type. I must be mixing up very many different 
>levels of theory and implementation. Is there any hope of completely 
>understanding functional programming?

I dunno. As far as programs manipulating the *World are concerned: 
I am pessimistic. But if you leave out the *World, I think we can 
completely understand functional programming (someday at least).

>
>Erik Zuurbier
>
>
>
>
>
>Erik Zuurbier
>Application Architect, 
>KLM, Information Services - AMSXE
>phone: (+ 31) 20 64 96 255 
>e-mail: erik.zuurbier@klm.nl
>

--------------------------------------
Maarten de Mol
University of Nijmegen
--------------------------------------