HDTenEightyP/NetNews huggingface dataset:
From: david@gdstech.grumman.com (David Nettles)
Subject: ** LAZY LANGUAGES FASTER?? **
Organization: Grumman Data Systems-Woodbury
Date: Fri, 24 Jul 1992 13:48:57 GMT


Are lazy languages faster than eager languages?

My intuition says that a lazy language would be a lot faster than an
eager language simply because the eager language evaluates all of its
arguements regardless of whether they are all needed by the function.

The lazy language, by evaluating only what is necessary, appears to
save time.

****************************************************************************
   David E. Nettles
   Grumman Data Systems             Internet: avid@gdstech.grumman.com
   1000 Woodbury Road                  Phone: (516) 682-8464
   Woodbury, NY 11797                    FAX: (516) 682-8022
   MS D12/237
****************************************************************************
Newsgroups: comp.lang.functional
From: bombadil@diku.dk (Kristian Nielsen)
Subject: Re: Maturing implementations of functional languages (and religion)
Date: Sun, 19 Jul 1992 15:14:18 GMT
Organization: Department of Computer Science, U of Copenhagen

farrell@coral.cs.jcu.edu.au (John Farrell) writes:

>  Certainly, functional languages have some properties which look like they
>will slow the language down no matter what. On the other hand, we can write
>functional and FORTRAN programs which produce exactly the same results on
>exactly the same machine, so why shouldn't they both run in the same time.
>While a functional program is slower than an equivalent procedural program, we
>have to acknowledge that we haven't got the compiler technology right yet.

I think there is another aspect that is often overlooked when lazy
functional programs are deemed slower than en equivalent program in a
more traditional language such as C or Pascal. I often find myself
writing 'better' programs in say Haskell to solve a particular problem
than I would have done otherwise. A very common example of this is the
tendency to have artificial constrains on the size of data structures
used in programs, like the dreaded maximum identifier length in
compilers or 256 character limit on input lines. In functional
languages (eager and lazy alike) the natural use of dynamic data
structures avoids this. Another example more related to laziness would
be a binary tree implementation. In a straitforward implementation in
an eager language the time complexity of m insertions followed by n
lookups would be O((m+n)log(m)). In a lazy implementation the
complexity might be somewhat better, since the insertions are not
taking place until/unless actually needed by the lookup operations.

The point is that a lazy program that is seemingly equivalent to
another (efficient) program may in fact not be quite equivalent. While
using dynamic data structures is probably at least as efficient in C
as in functional languages, I would think that the true equivalent of
the Haskell binary tree would be quite difficult to write as efficient
in C. The code would certainly be an order of magnitude more complex.
Anyway, such subtle differences will make it very difficult for a
compiler to reach the efficiency of todays compilers for traditional
languages, since it would have to outguess the programmer as to
his/her intention. In the binary tree example, a transformation to
strict evaluation would probably seem 'wrong', even though it might be
faster in most cases.

My personal feelings about this is that the lazy formulation is
usually the 'right', or most elegant, way to formulate the solution
(as likely as not steaming from my matematical background), causing me
to delight in the added power of expression provided by these
languages.

	- Kristian.
From: jjl@doc.ic.ac.uk (Junxian J Liu)
Newsgroups: comp.lang.functional
Subject: Re: Questions on converting Miranda code to Haskell
Date: 21 Jul 92 15:58:23 GMT
Organization: Glasgow University Computing Science Dept.
X-Mailer: mail-news 2.0.5


The character '>' appeared at the first column of my original 
message was automatically converted to '|' somehow (I don't know
why). I list the Miranda code here again (leave first coulmn
blank):

 > ns    = map numval (lines (read "data"))

 > n     = # ns

 > sqrts = map sqrt ns

 > sum_sqrts = sum sqrts

 > avg_sqrts = sum_sqrts / n

 > men_sqrts = sum (map minus_avg_sqr sqrts) / n
 >             where
 >             minus_avg_sqr x = (x - avg_sqrts) * (x - avg_sqrts)

 > result  = "number of values = " ++ show n ++ "\n"
 >           ++ "sum_sqrts = " ++ show sum_sqrts ++ "\n"
 >           ++ "avg_sqrts = " ++ show avg_sqrts ++ "\n"
 >           ++ "men_sqrts = " ++ show men_sqrts ++ "\n"

 > main    = [Stdout result]

Sorry about this.

Liu.
-------
Dr J Liu,   Department of Computing, Imperial College, 
            180 Queens Gate, London SW7 2BZ, United Kingdom.
Telephone : (+44 71/071) 589 5111 ext. 5033  Fax : (+44 71/071) 581 8024
Email:      jjl@doc.ic.ac.uk
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.lang.functional
Subject: Re: Typing and Expressiveness
Date: 21 Jul 92 17:25:28 GMT
	<NICKH.92Jul14151920@VOILA.VENARI.CS.CMU.EDU>
	<1992Jul14.205627.25659@eng.umd.edu> <1992Jul15.002311.27895@udel.edu>
	<knight.711224199@cunews> <farrell.711260486@coral.cs.jcu.edu.au>
	<knight.711298049@cunews> <92199
Organization: Department of Computer Science, University of Manchester
In-reply-to: sewardj@cs.man.ac.uk's message of 21 Jul 92 12:29:52 GMT

In article <SEWARDJ.92Jul21132952@r6.cs.man.ac.uk> sewardj@cs.man.ac.uk (Julian Seward (DRL PhD)) writes:

   Or how about: with a statically typed (functional) language,
   the typechecker automatically constructs a proof that the
   program will not fall over with a segmentation fault when run.

I've never had a Scheme program that fell over with a "segmentation
fault" and it certainly isn't statically typed (strong yes, static
no).  I've had some that didn't produce the results I expected, but
then I've had Haskell programs do the same :-)


   So much more convenient than C.

But then isn't almost anything :-)
BTW, C _is_ statically typed, it is just very easy to defeat the type
checker.

bevan
Newsgroups: comp.lang.functional
From: farrell@coral.cs.jcu.edu.au (John Farrell)
Subject: Re: ** LAZY LANGUAGES FASTER?? **
Organization: James Cook University
Date: 28 Jul 92 01:21:37 GMT

In <3737@svin02.info.win.tue.nl> erik@wsinfo03.win.tue.nl (Erik Poll) writes:
>david@gdstech.grumman.com (David Nettles) writes:
>>My intuition says that a lazy language would be a lot faster than an
>>eager language simply because the eager language evaluates all of its
>>arguements regardless of whether they are all needed by the function.

>Lazy evaluation does indeed save time by not evaluating arguments
>that are not needed. However, eager evaluation saves times by never
>evaluating the same argument twice.

  *Non-strict* evaluation saves time by not evaluating arguments which are not
needed. *Lazy* evaluation saves time by evaluating each argument at most once.
Eager evaluation evaluates each argument exactly once.

  It is the mechanism by which lazy evaluation is implemented which slows it
down. The speedup due to not evaluating arguments is often negligible because
mostly people don't write functions which don't use their arguments.

John
From: sewardj@cs.man.ac.uk (Julian Seward (DRL PhD))
Newsgroups: comp.lang.functional
Subject: Re: Typing and Expressiveness
Date: 21 Jul 92 12:29:52 GMT
	<NICKH.92Jul14151920@VOILA.VENARI.CS.CMU.EDU>
	<1992Jul14.205627.25659@eng.umd.edu> <1992Jul15.002311.27895@udel.edu>
	<knight.711224199@cunews> <farrell.711260486@coral.cs.jcu.edu.au>
	<knight.711298049@cunews> <92199
Organization: Department of Computer Science, University of Manchester
In-reply-to: brendan@cs.uq.oz.au's message of 20 Jul 92 06:21:38 GMT


| How's this for an explanation.
| 
| With a statically typed language you not only specify a calculation to
| be performed, but also a consistency check on your program text which
| highlights really stupid mistakes. That is, you are actually writing two
| programs with the one piece of text.

Or how about: with a statically typed (functional) language,
the typechecker automatically constructs a proof that the
program will not fall over with a segmentation fault when run.

So much more convenient than C.
From: S.Courtenage@cs.ucl.ac.uk (Si Courtenage)
Newsgroups: comp.lang.functional
Subject: Re: Maturing implementations of functional languages (and religion)
Date: 21 Jul 92 09:20:39 GMT


 Stuart Clayman writes:
 >Another thing that should be considered is the cost of actually
 >writing algorithms and maintaining them.
 >These are the most money intensive aspects of commercial software.
 >
 >My feeling is that if my lazy, functional and modular program goes 10%
 >slower than the C version, then in itself that seems poor.
 >However if I consider the no. of lines of code, how long it took me to
 >write it correctly, and moreover how long it may take me to debug it
 >in future (in case of errors) then the overall view has to be (my
 >belief here) that the functional version is not too bad, and may even
 >be competitive.
 >Rule n: Consider all the costs over the whole development cycle.
 >

Making the following assumptions, that

   1. execution cost of functional languages is fixed for each program run
   2. the cost advantage of functional languages, such as ease of program
      maintenance and clarity of expression etc. per unit time decrease
      over the program life-cycle,

then if the program was a high-use, long-use program then it would be better
to write the application in an imperative language as the execution cost
disadvantage would outweigh the dvelopment cost advantage. If the program
was a short-use or low-use program then it would be better to write it in a
functional language since the development cost advantage of functional
languages would, on average(?), overcome the execution cost disadvantage.
Hence why functional languages make good tools for prototyping but not for
end-products.

Has there been any research in software engineering/fp into this kind of
tradeoff?

Simon
Newsgroups: comp.lang.functional
From: delacour@waxwing.parc.xerox.com (Vincent Delacour)
Subject: Re: Gabriel benchmarks in a functional language?
Organization: Xerox PARC, Palo Alto, CA
Date: 23 Jul 92 11:00:32


In article <DBH.92Jul23152442@wombat.doc.ic.ac.uk> dbh@doc.ic.ac.uk (Denis Howe) writes:

   Have the Gabriel benchmarks been translated into a functional
   language?  I am thinking of translating them from Scheme to Haskell.
   --
   Denis Howe <dbh@doc.ic.ac.uk>
   Does this question have an answer?


Francis Dupont of INRIA has translated some of the Gabriel benchmarks
in a lazy variant of CAML. He found that, eg, the Boyer test program
was running faster in lazy mode than in eager mode, because most of
the lists it creates do not get used! 

Feel free to consider this a proof that lazyness is superior to
eagerness <8^]. IMO this is at best a proof that benchmarks are often
meaningless.

	Vincent

Newsgroups: comp.lang.functional
From: farrell@coral.cs.jcu.edu.au (John Farrell)
Subject: Re: ** LAZY LANGUAGES FASTER?? **
Organization: James Cook University
Date: 29 Jul 92 01:38:10 GMT

In <1992Jul28.140801.21895@crl.dec.com> nikhil@crl.dec.com (R.S. Nikhil) writes:
>In article <farrell.712286497@coral.cs.jcu.edu.au>, farrell@coral.cs.jcu.edu.au (John Farrell) writes:
>>   *Non-strict* evaluation saves time by not evaluating arguments which are not
>> needed.

>Pardon my nit-picking, but this is not true.  I refer you to my earlier posting
>(last week?) in which I pointed out that evaluators CAN work on unnecessary
>arguments while preserving non-strictness.

  My statement is true if you are implementing non-strict evaluation on a
sequential machine, in which case speculative evaluation can cause
non-termination unless you can prove that the argument being speculatively
evaluated was needed, and at the very least speculatively evaluating an
unneeded argument will waste time. Your nit-picking is pardoned :-).


John
Newsgroups: comp.lang.functional
Newsgroups: comp.lang.functional
Subject: Re: ** LAZY LANGUAGES FASTER?? **
From: brian@comp.vuw.ac.nz (Brian Boutel)
Date: Wed, 29 Jul 1992 04:04:13 GMT
 <farrell.712286497@coral.cs.jcu.edu.au> <1992Jul28.140801.21895@crl.dec.com> <farrell.712373890@coral.cs.jcu.edu.au>
Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand.


In article <farrell.712373890@coral.cs.jcu.edu.au>, farrell@coral.cs.jcu.edu.au (John Farrell) writes:
|> In <1992Jul28.140801.21895@crl.dec.com> nikhil@crl.dec.com (R.S. Nikhil) writes:
|> >In article <farrell.712286497@coral.cs.jcu.edu.au>, farrell@coral.cs.jcu.edu.au (John Farrell) writes:
|> >>   *Non-strict* evaluation saves time by not evaluating arguments which are not
|> >> needed.
|> 
|> >Pardon my nit-picking, but this is not true.  I refer you to my earlier posting
|> >(last week?) in which I pointed out that evaluators CAN work on unnecessary
|> >arguments while preserving non-strictness.
|> 
|>   My statement is true if you are implementing non-strict evaluation on a
|> sequential machine, in which case speculative evaluation can cause
|> non-termination unless you can prove that the argument being speculatively
|> evaluated was needed, and at the very least speculatively evaluating an
|> unneeded argument will waste time. Your nit-picking is pardoned :-).
|> 
|> 
|> John

To pick a further nit, you can, of course, simulate parallel evaluation on a
sequential machine, and so preserve non-strictness while working on unnecessary
arguments.

--brian


-- 
Internet: brian@comp.vuw.ac.nz
Postal: Brian Boutel, Computer Science Dept, Victoria University of Wellington,
        PO Box 600, Wellington, New Zealand
Phone: +64 4 471-5328   Fax: +64 4 495-5232
From: acha@CS.CMU.EDU (Anurag Acharya)
Newsgroups: comp.lang.functional
Subject: Re: algorithmic efficiency and lazy languages
Date: 23 Jul 92 19:52:06 GMT
Article-I.D.: DRAVIDO.ACHA.92Jul23145206
Distribution: comp
Organization: School of Computer Science, Carnegie Mellon University
Originator: acha@DRAVIDO.SOAR.CS.CMU.EDU

In article <501@owl.ukc.ac.uk> dat@ukc.ac.uk (D.A.Turner) writes:
> In article <DTARDITI.92Jul21023549@DESERT.FOX.CS.CMU.EDU> dtarditi@CS.CMU.EDU (David Tarditi) writes:
> >I have always been under the impression that lazy evaluation
> >makes it difficult to determine the time and space efficiency
> >of programs.>
> >If this is true, then it is a strong practical argument against using 
> >lazy evaluation, since asymptotic efficiency is quite important in
> >practice.> An O(n^2) algorithm may be unusable in practice, while
> >an O(n log n) algorithm may do quite nicely.

> I think it is only half true. There  is  no  special  difficulty  in
> reasoning   about  the  *time*  complexity  of  programs  written  in  a
> non-strict  functional  language.   One  can  derive  from  the  program
> equations   for  functions  fi  say,  similar  equations  for  Tfi,  the
> time-to-execute of function fi.  There is quite  a  nice  discussion  of
> this,   with   some   examples,  in  chapter  6  of  Bird  and  Wadler's
> "Introduction to Functional Programming".
>   On the other  hand  reasoning  about  the  *space*  complexity  of  such
> programs seems to be much more difficult.

If it is difficult to determine the space complexity of the programs, I wonder
why is it easy to determine their time complexity ? Allocating and 
initializing space takes time proportional to the space used (in the best
case -- assuming the space is never reused). Explicit freeing 
takes time proportional to the space freed (again in the best case -- not
much compaction needed), garbage collection needs time proportional to the
amount of live data (best case -- mark and sweep needs time proportional
to the all space available to the program). 

anurag
Newsgroups: comp.lang.functional
From: murthy@cs.cornell.edu (Chet Murthy)
Subject: Predicting efficiency from theoretical models (Re: ** LAZY LANGUAGES FASTER?? **)
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Sat, 25 Jul 1992 19:02:52 GMT

david@gdstech.grumman.com (David Nettles) writes:

>Are lazy languages faster than eager languages?

>My intuition says that a lazy language would be a lot faster than an
>eager language simply because the eager language evaluates all of its
>arguements regardless of whether they are all needed by the function.

>The lazy language, by evaluating only what is necessary, appears to
>save time.

This reminded me of something else, which I thought maybe I'd bring
up, which is on a soemewhat related topic.  Anybody thought about the
question of _why_ CBV is more efficient?  I mean, for a theoretician,
there seems to be no really good answer.  But I'd like to be able to
argue for efficiency from purely theoretical grounds, and since I'm
interested in programming-languages research, that means to predict
the efficiency of programming languages.  Of course this depends on
all sorts of things - the quality of the implementation is paramount.
But there ought to be something which theory can say other than the
standard "asymptotic complexity" arguments - after all,

      almost compiler optimization comes down to shaving
      constant factors, eh?

So, anyway, on to CBV versus CBN:

(1) Looking at abstract machines, it seems like CBN should be the
    naturally more efficient evaluation mechanism.

(2) I had this conjecture that maybe it was the "simplicity of the
    standard reduction function" - but here, too, CBN wins - the CBV
    standard reduction sequence definitions are rather more
    complicated than those for CBN.

In the end, it came down for me to something disgustingly applied -
the frequency of expressions which are weak-head-normalizable to
closure-free objects (i.e. which compute to data-values) is very high
in normal programs - so CBV wins because it "represents" them
efficiently - as the values they denote.

In other words, the cost of manipulating "thunks" overwhelms the
savings from not evaluating unneeded arguments.  This seems like an
awfully specious argument, from a theoretical standpoint, and I sure
would like to hear something more firm.

--chet--
From: sewardj@cs.man.ac.uk (Julian Seward (DRL PhD))
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Date: 26 Jul 92 22:26:57 GMT
Organization: Department of Computer Science, University of Manchester
In-reply-to: bevan@cs.man.ac.uk's message of 26 Jul 92 17:44:20 GMT


Steven J Bevan writes:

| This works well, and keeps the usage down to under 2Mb for the input
| that previously ran out of heap.  However, there are a couple of
| things that bother me about this :-
| 
| 1. The extra amount of work that has to be done in "forcing" the store.
|    This bumps up the runtime.

Hmm ... but not by much.

| 2. A simple, one-liner using higher order functions has turned into a
|    10 line tail recursive loop.  Now being a Schemer at heart, I have
|    no particular problem with this, but it does seem to go against the
|    whole idea of "higher order functions are good" which most fp books
|    espouse.

I have a couple of comments on this.  Firstly, the problem
is you are getting 000's of thunks.  The problem is *not*
the use of a higher-order function.  Even if you unfolded the
definition of "foldl" at the parameterisation shown, the program would
behave the same.

Secondly, a few minutes of investigation and a few changed lines
made a massive difference to the usability of the program. 
In my book this is a very small price to pay for the
convenience of a language as expressive as Haskell.  I believe
a few (say five at most) strategically placed hyperstrictnesses (so to speak)
can make a big difference to the space behaviour of programs 
tens of thousands of lines long.  Using a heap-profiling
compiler, it is easy to spot the functions filling the heap up
with thunks.

For this reason, I believe the Haskell committee should
consider the provision of two built-in functions:

   hyperstrict, whnf :: Eq a => a -> b -> b

both of which evaluate their first argument (fully or to whnf)
and return the second.  We can simulate this at the moment using
Haskell 1.2, but it might be more efficient if compilers could
regard these as primitive.

Jules
Newsgroups: comp.lang.functional
From: kff@dentex.tds.kth.se (Karl-Filip Faxen)
Subject: Re: ** LAZY LANGUAGES FASTER?? **
Reply-To: kff@dentex.tds.kth.se (Karl-Filip Faxen)
Organization: Royal Institute of Technology, Stockholm, Sweden
Date: Mon, 27 Jul 1992 13:07:09 GMT

In article <3737@svin02.info.win.tue.nl>, erik@wsinfo03.win.tue.nl (Erik Poll) writes:

|> In lazy languages, an argument is evaluated once for every time that it 
|> is used. 

No, in a lazy implementation (and laziness is an implementation related
concept - the corresponding semantic concept is nonstrictness (as Nikhil
pointed out earlier)) an argument to a function is evaluated *at most once*.
A lazy implementation is required to save the result of evaluation for 
later use. What *has* to be done for each use of the argument (in the
absence of strictness analysis) is a check of whether the argument is or
isn't already evaluated, ie if we should evaluate it or use the saved 
result of an earlier evaluation.

Karl-Filip
---------------------------------------------------------------------
Make the frequent case fast, and the fast case frequent!