What makes a functional language functional?
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.
Chris, I'm not sure what exactly your question is as you are mixing up several concepts. However, you start with:
In haskell, we can transform:
g x + f x
into:
f x + g x
Here you assume that the function + is commutative. Although this is probably true for all numeric types in all Haskell implementations, neither functional languages in general nor the Haskell report guarantee commutativity of +. So this assumption is dangerous.
0 + _|_ /= _|_ + 0
Or, does this just become:
_|_ = _|_ ?
The Haskell report probably does not say so explicitly, but in general primitive functions like + are strict in all arguments and hence 0 + _|_ = _|_ = _|_ + 0. Ciao, Olaf
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Jeremy.Gibbons@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
Hi Jeremy, Thanks for this very informative answer! This has certainly helped to clear up a number of points. Thanks, Chris.
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Jeremy.Gibbons@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
participants (3)
-
C.M.Brown -
Jeremy Gibbons -
Olaf Chitil