[Haskell] What makes a functional language functional?

[Jeremy Gibbons]

Many arguments have been had about what it means for a language to be  
"functional", so that's probably not a productive line of discussion.  
(ICFP carefully doesn't stipulate language choice for the programming  
contest, for example.)

Both eager and lazy evaluation can be "pure", providing referential  
transparency: all that matters of an expression is its value, and a  
subexpression may be substituted with a different one having the same  
value without changing the meaning of the surrounding context. This  
fails on languages supporting side effects.

Lazy evaluation is necessary, however, in order to treat a function  
definition as a (universally applicable) equation. In Haskell, I can  
define

 > three x = 3

and then infer, for any expression x, that the equation

   three x = 3

holds. With eager evaluation, that's no longer the case: if x denotes  
a non-terminating or error-raising computation, then

   three x /= 3

The equation then requires a side condition:

   three x = 3,  for well-defined x

which complicates equational reasoning, but it doesn't break  
referential transparency.

Jeremy


On 9 Aug 2007, at 10:30, C.M.Brown wrote:

> Hi,
>
> Is lazy evaluation necessary for a functional language to remain
> functional?
>
> The reason I ask is that because it violates beta-reduction, and also
> referential transparency (I think). In haskell, we can transform:
>
> g x + f x
>
> into:
>
> f x + g x
>
> as both f and g do not change the parameter x.
>
> If g always evaluates to a normal form (in both a lazy and a strict  
> world)
>
> g x = x
>
> but f is defined thus:
>
> f x = (\y -> if x /= 0 then x else y/x)
>
> And we apply f to 0 (1/0) then f becomes _|_
>
> therefore:
>
> 0 + _|_ /= _|_ + 0
>
> Or, does this just become:
>
> _|_ = _|_ ?
>
> Or, am I missing something totally obvious?
>
> Regards,
> Chris.
>
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell



Jeremy.Gibbons at comlab.ox.ac.uk
   Oxford University Computing Laboratory,    TEL: +44 1865 283508
   Wolfson Building, Parks Road,              FAX: +44 1865 283531
   Oxford OX1 3QD, UK.
   URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html