Hello, Here's something I've always wanted to know but have never dared ask until now (it seems so basic). If I have defined a function like this.. f <args> = <blah> <args> it could be re-written.. f = <blah> I had always assumed the internal representation of these 2 definitions would be identical (and should yield identical code), but it appears that isn't so (with ghc at least). So.. Is there a semantic difference between the two? Which form is likely to result in faster code? Thanks -- Adrian Hey
The only semantic difference is in the type checker - the first form is not subject to monomorphism while the latter is unless a type signature is present. There should be no difference at all in the generated code. John
Hi Adrian, | If I have defined a function like this.. | f <args> = <blah> <args> | it could be re-written.. | f = <blah> | | I had always assumed the internal representation of | these 2 definitions would be identical (and should | yield identical code), but it appears that isn't so | (with ghc at least). So.. | | Is there a semantic difference between the two? | Which form is likely to result in faster code? There are several differences: - The first will not be subject to the monomorphism restriction; the second will require an explicit type signature for f to avoid that fate. - The second will compute a value of <blah> at most once, then cache the result for future use. That could make a program run faster, but if the result of <blah> takes a lot of space, then it could result in a space leak. The first might end up repeating the computation of <blah> each time f is called. For example, compare the evaluation of: let f = (+) (sum [1..1000]) in (f 1, f 2) with: let f x = (+) (sum [1..1000]) x in (f 1, f 2) (Hint: run it in Hugs on a slow computer with :set +s to see the difference, or replace 1000 with a bigger number :-) Denotationally, the two expressions are the same. (In other words, they both produce the same value.) But the example above shows an operational difference in some implementation. (As far as I can tell, however, nothing in the language definition either guarantees or prevents such behavior.) - There could be other differences in generated code and operational behavior, even when <blah> is an expression that cannot be further evaluated without an argument. In Hugs, for example, the definition: f = \x y -> (x,y) will be translated into: f = f' -- note the extra indirection here! f' x y = (x,y) A compiler with more brains, of course, could do better, but the Haskell report doesn't specify which behavior you'll get in general. Personally, I'd tend to let considerations other than performance affect my choice. For example, if I'd declared f :: a -> String -> [(a, String)] then I might use a definition like: f x s = [(x, s)] -- two parameters in the type, so two -- parameters in the definition But if the type signature was f :: a -> Parser a and if I'd defined: type Parser a = String -> [(a, String)] then I'd write the definition of f in the form: f x = \s -> [(x, s)] -- f is a function of one argument -- that returns a parser as a result. Just my 2 cents, however, ... All the best, Mark
On Thu, 10 Jan 2002, Mark P Jones wrote:
| If I have defined a function like this.. | f <args> = <blah> <args> | it could be re-written.. | f = <blah> [snip] - The second will compute a value of <blah> at most once, then cache the result for future use. That could make a program run faster, but if the result of <blah> takes a lot of space, then it could result in a space leak. The first might end up repeating the computation of <blah> each time f is called. [snip] Denotationally, the two expressions are the same. (In other words, they both produce the same value.) But the example above shows an operational difference in some implementation. (As far as I can tell, however, nothing in the language definition either guarantees or prevents such behavior.)
Even sillier question: there's no other way of getting the optimization that normCorr' has over normCorr (as always on the understanding it may be a space leak) in Haskell? dotProd xs ys=sum(zipWith (*) xs ys) normCorr :: Floating a => [a] -> [a] -> a normCorr xs ys =(dotProd xs ys)/(sqrt((dotProd xs xs)*(dotProd ys ys))) normCorr' :: Floating a => [a] -> [a] -> a normCorr' xs=let e=sqrt(dotProd xs xs) in \ys->(dotProd xs ys)/(e*(sqrt(dotProd ys ys))) for use in, say, corrWithSimpleSignal = normCorr' [1..100] (this is a contrived example I admit) I sometimes write such things but it doesn't leap out at me on rereading the code later why I've defined e only to have it used (on first glance) only once... ___cheers,_dave_________________________________________________________ www.cs.bris.ac.uk/~tweed/|`...heat generated by its microprocessors will email:tweed@cs.bris.ac.uk|slope upward exponentially, reaching the power work tel:(0117) 954-5250 |density of a nuclear reactor before 2010'-Intel
On Friday 11 January 2002 8:46 am, D. Tweed wrote:
Even sillier question: there's no other way of getting the optimization that normCorr' has over normCorr (as always on the understanding it may be a space leak) in Haskell?
dotProd xs ys=sum(zipWith (*) xs ys)
normCorr :: Floating a => [a] -> [a] -> a normCorr xs ys =(dotProd xs ys)/(sqrt((dotProd xs xs)*(dotProd ys ys)))
normCorr' :: Floating a => [a] -> [a] -> a normCorr' xs=let e=sqrt(dotProd xs xs) in \ys->(dotProd xs ys)/(e*(sqrt(dotProd ys ys)))
for use in, say, corrWithSimpleSignal = normCorr' [1..100] (this is a contrived example I admit)
I sometimes write such things but it doesn't leap out at me on rereading the code later why I've defined e only to have it used (on first glance) only once...
Well, apart from the fact that the compiler needs to know that sqrt (a*b)= (sqrt a)*(sqrt b) :-) I think full laziness should effect the transformation. But, IIRC a while ago Simon Marlow said that with ghc if you have two adjacent lambdas and a free sub-expression which can be lifted outside one but not the other (as in this case) then it won't do the full laziness thing at all. (But don't quote me on that because it's entirely possible I misunderstood:-) Regards -- Adrian Hey
Thanks Mark, On Friday 11 January 2002 7:41 am, Mark P Jones wrote:
Denotationally, the two expressions are the same. (In other words, they both produce the same value.) But the example above shows an operational difference in some implementation. (As far as I can tell, however, nothing in the language definition either guarantees or prevents such behavior.)
Ah, now I see the issue seems to be closeley related to full lazy lambda lifting. Given.. f = \x -> <blah> x where <blah> has no free occurences of x, then I thought the compiler would reduce this immediately to f = <blah> Full lazy lambda lifting would give something like this.. b = <blah> f = \x -> b x But this still requires, the (\x -> b x) to be reduced to b to get.. b = <blah> f = b (and hence f = <blah>) Do (should) Haskell compilers do this, as a general rule? It all seems bit vague to me :-(
Personally, I'd tend to let considerations other than performance affect my choice.
For example, if I'd declared f :: a -> String -> [(a, String)] then I might use a definition like:
f x s = [(x, s)] -- two parameters in the type, so two -- parameters in the definition
But if the type signature was f :: a -> Parser a and if I'd defined:
type Parser a = String -> [(a, String)]
then I'd write the definition of f in the form:
f x = \s -> [(x, s)] -- f is a function of one argument -- that returns a parser as a result.
Funnily enough, it was the issue of parsing which prompted me to ask the question.. I guess most people would write.. myParser = <sexy_combinator_expression> and not.. myParser tokens = (<sexy_combinator_expression>) tokens But I wasn't too sure whether the two forms would give equally efficient code (and if not then which one was 'best'). It seems the answer depends on the compiler implementation and/or the level of optimisation selected. Regards -- Adrian Hey
Hi Adrian, | Ah, now I see the issue seems to be closeley related to | full lazy lambda lifting. That's right ... | Do (should) Haskell compilers do this, as a general rule? | It all seems bit vague to me :-( I don't think they do, and I'm not sure they should because the transformation can, in some circumstances, result in a space leak. It would probably be better to specify this aspect of the language semantics more precisely in the language report but I think there are some open problems with the theory that would need to be addressed first. (e.g., how do you give a semantics for Haskell that reflects expected/required implementation behavior will also being abstract enough in accounting for space usage?) All the best, Mark
participants (4)
-
Adrian Hey -
D. Tweed -
John Peterson -
Mark P Jones