Lazy evaluation from "Why Functional programming matters"
Hi All, I was going through the paper's "lazy evaluation" section where the square root example is given. It occurred to me that one could implement it in a modular way with just higher order functions (without the need for lazy evaluation that is). function f (within, eps, next, a0){ while(true){ a1=next(a0); if(within(a0,a1,eps)return a0; a0=a1; } } Is this not the case? -- Regards, Kashyap
Hi,
Let us try to rewrite the code in a more java-esque syntax:
It translates to something like the below generic method. Correct?
static <T> T function(IBoundsCheck<T> within, Delta<T> eps, Iterator<T>
iterator, T initValue){
T currVal = initVal;
while(iterator.hasNext()){
T nextVal = iterator.next();
if(within.verify(delta, eps, currVal, nextVal))
return currVal;
currVal = nextVal
}
}
I have not tested it but I think this is a fair translation of the code.
(For instance, by using an appropriate implementation of IBoundsCheck, I
will be able to implement the 'relativeSqrt' functionality of the example).
But this IS still a lazy evaluation. By passing an iterator instead of a
list as the third argument of the static method, I achieved 'laziness'.
In the example, the laziness is in the way we are iterating over the
sequence of values [a0,f(a0), f(f(a0)),...] and so on and not on when the
runtime evaluates appropriate values.
Just that having to write,
(repeat (next N) a0)
is (take 1000 (repeat 1)) times more intuitive and convenient than having to
implement the Iterator for T or implementing a true-while loop.
/Hemanth K
On Tue, Oct 5, 2010 at 4:50 PM, C K Kashyap
Hi All,
I was going through the paper's "lazy evaluation" section where the square root example is given. It occurred to me that one could implement it in a modular way with just higher order functions (without the need for lazy evaluation that is).
function f (within, eps, next, a0){ while(true){ a1=next(a0); if(within(a0,a1,eps)return a0; a0=a1; } }
Is this not the case?
-- Regards, Kashyap _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hi, Let us try to rewrite the code in a more java-esque syntax: It translates to something like the below generic method. Correct? static <T> T function(IBoundsCheck<T> within, Delta<T> eps, Iterator<T> iterator, T initValue){ T currVal = initVal; while(iterator.hasNext()){ T nextVal = iterator.next(); if(within.verify(delta, eps, currVal, nextVal)) return currVal; currVal = nextVal } }
I have not tested it but I think this is a fair translation of the code. (For instance, by using an appropriate implementation of IBoundsCheck, I will be able to implement the 'relativeSqrt' functionality of the example). But this IS still a lazy evaluation. By passing an iterator instead of a list as the third argument of the static method, I achieved 'laziness'. In the example, the laziness is in the way we are iterating over the sequence of values [a0,f(a0), f(f(a0)),...] and so on and not on when the runtime evaluates appropriate values. Just that having to write, (repeat (next N) a0) is (take 1000 (repeat 1)) times more intuitive and convenient than having to implement the Iterator for T or implementing a true-while loop.
I see ... I think I understand now. hmmm ... I am little disappointed though - does that mean that "all the laziness" cool stuffs can actually be done using iterators(generators)? As in, but for the inconvenient syntax, you can do it all in - say java? -- Regards, Kashyap
On Tue, Oct 05, 2010 at 07:37:32PM +0530, C K Kashyap wrote:
Hi, Let us try to rewrite the code in a more java-esque syntax: It translates to something like the below generic method. Correct? static <T> T function(IBoundsCheck<T> within, Delta<T> eps, Iterator<T> iterator, T initValue){ T currVal = initVal; while(iterator.hasNext()){ T nextVal = iterator.next(); if(within.verify(delta, eps, currVal, nextVal)) return currVal; currVal = nextVal } }
I have not tested it but I think this is a fair translation of the code. (For instance, by using an appropriate implementation of IBoundsCheck, I will be able to implement the 'relativeSqrt' functionality of the example). But this IS still a lazy evaluation. By passing an iterator instead of a list as the third argument of the static method, I achieved 'laziness'. In the example, the laziness is in the way we are iterating over the sequence of values [a0,f(a0), f(f(a0)),...] and so on and not on when the runtime evaluates appropriate values. Just that having to write, (repeat (next N) a0) is (take 1000 (repeat 1)) times more intuitive and convenient than having to implement the Iterator for T or implementing a true-while loop.
I see ... I think I understand now. hmmm ... I am little disappointed though - does that mean that "all the laziness" cool stuffs can actually be done using iterators(generators)? As in, but for the inconvenient syntax, you can do it all in - say java?
You can do anything in any Turing-complete language, but for the inconvenient syntax. So what? -Brent
I see ... I think I understand now. hmmm ... I am little disappointed though - does that mean that "all the laziness" cool stuffs can actually be done using iterators(generators)? As in, but for the inconvenient syntax, you can do it all in - say java?
Yes. It would slightly easier in, say, C# or C++. I think 'D' achieves its implementation of the 'lazy' keyword using a similar approach. But I did not understand why you are disappointed ?
Yes. It would slightly easier in, say, C# or C++. I think 'D' achieves its implementation of the 'lazy' keyword using a similar approach. But I did not understand why you are disappointed ?
The disappointment was not on a serious note ... the thing is, I constantly run into discussions about "why fp" with my colleagues - in a few of such discussions, I had mentioned that Haskell is the only well known language with lazy evaluation (IIRC, I read it somewhere or heard it in one of the videos) And I had built up this impression that laziness distinguished Haskell by a huge margin ... but it seems that is not the case. Hence the disappointment. -- Regards, Kashyap
C K Kashyap
Yes. It would slightly easier in, say, C# or C++. I think 'D' achieves its implementation of the 'lazy' keyword using a similar approach. But I did not understand why you are disappointed ?
The disappointment was not on a serious note ... the thing is, I constantly run into discussions about "why fp" with my colleagues - in a few of such discussions, I had mentioned that Haskell is the only well known language with lazy evaluation (IIRC, I read it somewhere or heard it in one of the videos)
And I had built up this impression that laziness distinguished Haskell by a huge margin ... but it seems that is not the case. Hence the disappointment.
Don't be disappointed. There are some things, which are extremely elegant to express with laziness: isPrime :: Integral a => a -> Bool isPrime n = all (\x -> mod n x /= 0) . takeWhile (\x -> x*x <= n) $ primes primes :: Integral a => [a] primes = 2 : filter isPrime [3..] These two definitions use each other in a way, which is very difficult to express without lazy evaluation. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/
Don't be to disappointed. One can always kinda fake lazy evaluation
using mutable cells.
But not that elegantly. In the example given above, all being used is
iterators as streams... this can also be expressed using lazy lists,
true. But one big difference between e.g. lazy lists and iterators is,
that lazy values are (operationally) replaced by their result wheres
values generated from iterators and streams are not.
For example one can use Iterators and chain them together in Java, to
achieve more or less the same space and runtime-efficiency found by
Stream-fusion in haskell (the Java JIT can abstract loads away, once
the iterators are build together). But If you need to access the
iterator's values more then once, you have to either force the full
iterator into a list or rerun/reevaluate the iterator every time you
need a value.
Lazy lists are nice, but haskell's laziness is not about lazy lists
only. For example lazy evaluation also matters when creating
"elegant" Embedded DSLs... have you ever tried to build a more complex
EDSL without laziness and macros?
On 5 Okt., 16:52, C K Kashyap
Yes. It would slightly easier in, say, C# or C++. I think 'D' achieves its implementation of the 'lazy' keyword using a similar approach. But I did not understand why you are disappointed ?
The disappointment was not on a serious note ... the thing is, I constantly run into discussions about "why fp" with my colleagues - in a few of such discussions, I had mentioned that Haskell is the only well known language with lazy evaluation (IIRC, I read it somewhere or heard it in one of the videos)
And I had built up this impression that laziness distinguished Haskell by a huge margin ... but it seems that is not the case. Hence the disappointment.
-- Regards, Kashyap _______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe
On Tue, Oct 5, 2010 at 9:19 PM, steffen
Don't be to disappointed. One can always kinda fake lazy evaluation using mutable cells. But not that elegantly. In the example given above, all being used is iterators as streams... this can also be expressed using lazy lists, true. But one big difference between e.g. lazy lists and iterators is, that lazy values are (operationally) replaced by their result wheres values generated from iterators and streams are not.
For example one can use Iterators and chain them together in Java, to achieve more or less the same space and runtime-efficiency found by Stream-fusion in haskell (the Java JIT can abstract loads away, once the iterators are build together). But If you need to access the iterator's values more then once, you have to either force the full iterator into a list or rerun/reevaluate the iterator every time you need a value.
Lazy lists are nice, but haskell's laziness is not about lazy lists only. For example lazy evaluation also matters when creating "elegant" Embedded DSLs... have you ever tried to build a more complex EDSL without laziness and macros?
Thanks Ertugrul for the nice primes example. Steffen, Thanks for the explanation. Is there some literature around other lazy entities from the imperative side. I'm currently trying to get my Makefile EDSL to work - not sure, if that could turn complex. My ultimate aim it to write an EDSL for x86 - as in, describe a micro-kernel in haskell, compiling and running which would generate C code ( not sure if it's even possible - but I am really hopeful). Could you send me a sample on how I could use the reader monad for my Makefile EDSL. Regards, Kashyap
On 06/10/10 11:00, C K Kashyap wrote:
My ultimate aim it to write an EDSL for x86 - as in, describe a micro-kernel in haskell, compiling and running which would generate C code ( not sure if it's even possible - but I am really hopeful).
Have you seen Potential (http://intoverflow.wordpress.com/2010/05/21/announcing-potential-x86-64-asse... Quote: "The language’s goal is to provide a solid foundation for the development of a useful (multi-tasked, multi-processor, etc) microkernel" Which sounds like it's exactly what you want. Also, see Harpy (http://uebb.cs.tu-berlin.de/harpy/). Thanks, Neil.
Have you seen Potential (http://intoverflow.wordpress.com/2010/05/21/announcing-potential-x86-64-asse... Quote:
"The language’s goal is to provide a solid foundation for the development of a useful (multi-tasked, multi-processor, etc) microkernel"
Which sounds like it's exactly what you want. Also, see Harpy (http://uebb.cs.tu-berlin.de/harpy/).
Thank you very very much Neil for pointing me to Potential. I'll take a look at it. -- Regards, Kashyap
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 10/5/10 10:52 , C K Kashyap wrote:
And I had built up this impression that laziness distinguished Haskell by a huge margin ... but it seems that is not the case. Hence the disappointment.
Haskell is lazy-by-default and designed around lazy evaluation, whereas most other languages are strict by default, designed around strictness, and make you do extra work to get laziness which you then may lose rather easily. Sometimes it's as easy as using an iterator, other times it means passing around closures and invoking them at just the right time. - -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.10 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkyrVcgACgkQIn7hlCsL25W5tQCeMoY6XCcDLKFh3tbwdrliQSqd grcAnjCGqxBwRsEoI2pG3+ZgA4biSDAw =kgwK -----END PGP SIGNATURE-----
participants (7)
-
Brandon S Allbery KF8NH -
Brent Yorgey -
C K Kashyap -
Ertugrul Soeylemez -
Hemanth Kapila -
Neil Brown -
steffen