HDTenEightyP/NetNews huggingface dataset:
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Date: 27 Jul 92 10:22:46 GMT
	<SEWARDJ.92Jul26232657@r6.cs.man.ac.uk>
Organization: Department of Computer Science, University of Manchester
In-reply-to: sewardj@cs.man.ac.uk's message of 26 Jul 92 22:26:57 GMT

In article <SEWARDJ.92Jul26232657@r6.cs.man.ac.uk> sewardj@cs.man.ac.uk (Julian Seward (DRL PhD)) writes:
   | 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.

How can we know this?  All I committed myself to was that the runtime
increased.  I can't say by how much, as without forcing the store it
is either slower or doesn't fit in the available heap.  However,
intiution tells me that doing repeated full equality tests on 7 AVL
trees containing 10,000+ elements each cannot be a cheap operation :-)


   | 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.

Ah, but I never said it was.  All I pointed out was that a solution to
the problem involved removing the HOF and replacing with an explicit
loop.  If I hadn't have been a HOF in the first place, the solution
whouldn't have seemed such a drastic change.


   Even if you unfolded the definition of "foldl" at the
   parameterisation shown, the program would behave the same.

Actually it runs out of heap quicker than the foldl version.  I guess
foldl isn't being optimised by the compiler.


   ..., 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.

Doesn't this move us back into the realms of separate annotations.  I
thought many people don't like as there is too much opportunity for
the user to make a mistake i.e. "hyperstricting" everthing in sight in
the hope of efficiency.  Alternately couldn't you argue that as most
of the time you want strict evaluation, you'd be better off with a
language were that was the default and annotating it with "lazy" at
appropriate points? For example, I have a much better feel for where I'd
want a strict version to be lazy than I do about where I'd want a lazy
version to be strict.  Is this the mark of a novice lazy programmer?

That notwithstanding, if the above proposal means I can remove the
loop and replace it with one hyperstrict/whnf call in the
read_ASCII_Store definition, then I'm all for it (but then what do I
know :-)

bevan
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: ** LAZY LANGUAGES FASTER?? **
Date: 28 Jul 92 20:01:01 GMT
	<farrell.712286497@coral.cs.jcu.edu.au>
Reply-To: tmb@idiap.ch
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
In-reply-to: farrell@coral.cs.jcu.edu.au's message of 28 Jul 92 01:21:37 GMT

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. *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.

I think there are two views towards strict evaluation in a purely
functional framework:

 (1) it constrains the program, letting the compiler generate
     better code (a constant factor speedup)

 (2) it affects the semantics of functions in the presence of
     errors and non-termination

Mostly what I care about is (1). I care about (2) only when I am
debugging. Therefore, for debugging, I want strict evaluation.  For
using my code, I want the most efficient evaluation possible.
Usually, I suspect that will be strict evaluation, but on parallel
machines, it could be something else.

Altogether, it therefore seems prudent to write programs so that they
depend as little as possible on whether the language is strict, eager,
non-strict, or lazy. But if it came down to a choice, I'd suspect that
eager evaluation is a practical necessity for many applications, and
languages should provide it at least in some form.

					Thomas.
Newsgroups: comp.lang.functional
From: greg@crl.dec.com (Greg Morrisett/Maurice Herlihy)
Subject: Tech Report
Keywords: Standard ML, multiprocessor
Organization: Carnegie Mellon Univ.
Date: Thu, 30 Jul 1992 16:44:23 GMT

We would like to announce the availability of the following technical
report.  Directions for obtaining the report via anonymous ftp appear
at the end of this message.  Note that the report has been published
jointly as Carnegie Mellon Technical Report CMU-CS-92-155 and
Princeton Technical Report 376-92.


                 A Portable Multiprocessor Interface
                                for
                     Standard ML of New Jersey

        J. Gregory Morrisett                 Andrew Tolmach
        jgmorris@cs.cmu.edu               apt@cs.princeton.edu


                             ABSTRACT

  We have designed a portable interface between shared-memory multiprocessors
  and Standard ML of New Jersey. The interface is based on the conventional
  kernel thread model and provides facilities that can be used to implement 
  user-level thread packages.  The interface supports experimentation with 
  different thread scheduling policies and synchronization constructs.  It 
  has been ported to three different multiprocessors and used to construct
  a general purpose, user-level thread package.  In this paper, we discuss 
  the interface and its implementation and performance, with emphasis on the 
  Silicon Graphics 4D/380S multiprocessor. 


   DIRECTIONS FOR ANONYMOUS FTP:
   1) Ftp to reports.adm.cs.cmu.edu (128.2.218.42) as "anonymous".

   2) At the password prompt, send your Username@site 
      (you must include the "@" or the login will fail)
  
   3) Then "cd 1992"  (the directory for 1992 technical reports)

   4) set file type to binary: "binary"

   5) get CMU-CS-92-155.ps

   6) When you have finished getting the file, simply "quit."

Greg Morrisett
Andrew Tolmach
From: ajtd@st-andrews.ac.uk (Antony J. T. Davie)
Newsgroups: comp.lang.functional
Subject: Execution costs
Date: 22 Jul 92 09:35:24 GMT
Organization: St. Andrews University, Scotland.

Simon Courtenage writes:

>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.

The first assumption is not realistic in persistent situations. One of the
whole points about laziness is that things should get evaluated at most once.
If this principle is extended so that values persist after a functional
program has been run and so that evaluation work done on these values is not
lost, then running a new program which accesses these values will NOT
incur the fixed cost mentioned in the assumption. The cost of reusing such
values will be virtually zero --- and reuse is one of the major planks on
which software engineering rests.

My colleague Dave McNally (forthcoming thesis) and I have been working on
such persistent systems [1,2] and their power really adds a new dimension
to lazy evaluation, making its beneficial effects felt after particular
programs have terminated.

[1] D.J. McNally, A.J.T. Davie "Two Models for Integrating Persistence and
Lazy Functional Languages"  SIGPLAN 26, No. 5, May 1991 and University
of St.Andrews Dept. of Math and Comp Sci research report CS/91/1 

[2] A.J.T. Davie, D.J. McNally "PCASE --- A Persistent Lazy Version of an
SECD Machine" University of St.Andrews Dept. of Math and Comp Sci research
report CS/92/7
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.lang.functional
Subject: programs that are too lazy
Date: 26 Jul 92 17:44:20 GMT
Organization: Department of Computer Science, University of Manchester

I've defended lazy* evaluation in a previous message, now I have
question that may give some ammunition to the strict* camp.

Consider the following Haskell fragment which reads lines data from a
file into the "store" :-

  read_ASCII_Store st file fail succ = readFile file fail (succ . store)
    where
      store = (foldl (flip process_line) st) . (map words) . lines

where "process_line" has the form :-

  process_line :: [String] -> Store -> Store

This works fine.  It is nice and lazy i.e. if you invoke it, it does
not do anything until you actually try to access some of the values of
"store".  However, there is a price to pay for this.  When the input
file is reasonably large, this creates a large amounts of "thunks"
when reading in the data, in fact the "thunks" dominate the
proceedings and cause much more heap to be used than should be
necessary.  (It runs out of space in a 5Mb for an "interesting" input
file)

This appears to be well known problem (a number of people here have
had similar problems anyway), and the suggested solution is to "force"
the store at regular intervals so that it fully evaluates itself.
This results in the following code, where 100 is the number of lines
to read between "forcing" :-

    store xs = store_loop 0 st (lines xs)
    store_loop n st []    =
      if (st == st)           -- force the store
      then st
      else error "the FORCE is not with us"
    store_loop n st stuff =
      let st' = process_line (words (head stuff)) st
      in if (n `mod` 100 == 0)
         then if (st' == st') -- force the store
              then store_loop (n+1) st' (tail stuff)
              else error "the FORCE was not with us"
         else store_loop (n+1) st' (tail stuff)

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.

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.

So, I'm asking the net at large for advice.  Does anybody know of any
other methods of keeping the heap usage low and that do better in
answering 1&2?  Something using continuations or monads maybe?

bevan

* apologies for the imprecise terminology, I hope you all know what I
  mean anyway.
From: dat@ukc.ac.uk (D.A.Turner)
Newsgroups: comp.lang.functional
Subject: Re: algorithmic efficiency and lazy languages
Date: 24 Jul 92 14:36:27 GMT
Reply-To: dat@ukc.ac.uk (D.A.Turner)
Distribution: comp
Organization: Computing Lab, University of Kent at Canterbury, UK.

In a previous posting I wrote:
> 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.

To which boehm@parc.xerox.com (Hans Boehm) writes:
>It seems to me that this is insufficient.  It basically tells us that it's
>possible to write accurate profilers.

Sorry, I should have been more explicit.

I meant that you  could  often  *solve*  the  equations  (making  enough
simplifying  assumptions,  as  one  always does in asymptotic complexity
analysis) to arrive at a formula for the asymptotic complexity  of  each
function  of  interest.   As  mentioned,  see  chapter 6 of B+W for some
examples.

	-------------------

To add a further note on why space complexity is much less tractable -
it is RESIDENCY we are interested in, typically, rather than just the
number of times `cons' gets called, which is clearly related to the
time analysis, as has already been commented.

David Turner
From: augustss@cs.chalmers.se (Lennart Augustsson)
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Keywords: n
	whnf : : (WHNFable a) => a -> b -> b
Date: 28 Jul 92 19:48:46 GMT
Organization: Chalmers University of Technology


	-- Lennart

-- 

	-- Lennart Augustsson
[This signature is intentionally left blank.]
From: augustss@cs.chalmers.se (Lennart Augustsson)
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Keywords: n
Date: 29 Jul 92 16:49:19 GMT
Organization: Chalmers University of Technology


Sorry about my last posting, the mailer mangled it.
In article <1992Jul27.083020.6061@st-andrews.ac.uk> ajtd@st-andrews.ac.uk (Antony J. T. Davie) writes:
>Julian Seward writes
>>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.
>
>Whether or not one agrees with the provision of these fns., why restrict
>them to Eq types? Certainly one can only easily simulate them if they
>operate on equality types, but that's no reason to restrict primitive
>versions of them so.
>
There should be some suitable restriction on the values that allow
whnf.  E.g.
	whnf :: (WHNFable a) => a -> b -> b
The function with type a->b->b that evaluates its first argument
and return the second is not definable within lambda calculus.
Having it enables you to distinguish between BOT and \x.BOT,
which are usually regarded as equal.  (whnf BOT 0 --> BOT, but
whnf (\x.BOT) 0 --> 0)

	-- Lennart

-- 

	-- Lennart Augustsson
[This signature is intentionally left blank.]
Newsgroups: comp.lang.functional
From: lindgren@sics.se (Thomas Lindgren)
Subject: Re: A simple and common example of the usefulness of lazy evaluation.
Organization: Swedish Institute of Computer Science, Kista
	<DELACOUR.92Jul16110219@waxwing.parc.xerox.com>
Date: Thu, 23 Jul 1992 15:54:34 GMT

In article <DELACOUR.92Jul16110219@waxwing.parc.xerox.com> delacour@waxwing.parc.xerox.com (Vincent Delacour) writes:

>	   2- Another issues that has been raised is that of efficiency.
>   Despite the belief expressed by some that "Laziness is theoretically
>   more efficient even." (J. Farrel), I don't see how you can avoid
>   running "at the speed of the continental drift" as will from now on be
>   remembered as "Turner's confession", unless he denies vigorously
>   having said so.

It should be noted that the Miranda implementation is notoriously slow
and based on interpretive techniques. Indeed, even back in 1987, the
Chalmers LML implementation ran 100 times faster than Miranda on a
number of benchmarks (quicksort, 8 queens, that kind of thing)
[Augustsson's thesis]. So perhaps Miranda shouldn't be taken as a
representative example of such implementations. I would guess
that lazy languages are perhaps 10 times slower than imperative
ones on the average (feel free to correct me), with a smaller
factor on some benchmarks. (E.g., procedures that use
arithmetic are usually compiled well today, as I understand it.)
I would expect this factor to decrease with time, as the issues of
compilation are better understood (the basis of much of the work in
the area was laid in the mid-80:s, which isn't all that far-off).

As has been mentioned previously by Peyton Jones, there are good books
out on the subject of outrunning the continental drift.

>	   V. Delacour

			Thomas

--
--------------------------------------------------------------------------
Thomas Lindgren				thomasl@meryl.csd.uu.se
Computing Science Dept.,		Thomas.Lindgren@csd.uu.se
Uppsala University			lindgren@sics.se

	"I can call procedures in the vasty kernel."
	"Why so can I, or so can any program. But will you
	 return when you do call them?"
-----------------------------\\\\-----------------------------------------
From: nikhil@crl.dec.com (R.S. Nikhil)
Newsgroups: comp.lang.functional
Subject: Re: ** LAZY LANGUAGES FASTER?? **
Date: 28 Jul 92 14:08:01 GMT
Organization: DEC Cambridge Research Lab

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.

Rishiyur Nikhil (nikhil@crl.dec.com)
Newsgroups: comp.lang.functional
From: knight@mrco.carleton.ca (Alan Knight)
Subject: Re: Maturing implementations of functional languages (and religion)
Reply-To: knight@mrco.carleton.ca (Alan Knight)
Organization: Carleton University
Date: Wed, 29 Jul 1992 21:13:13 GMT

In <1992Jul19.151418.16386@odin.diku.dk> bombadil@diku.dk (Kristian Nielsen) writes:

>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

IMHO this is due to ease of using dynamic data structures, and not
anything to do with functional languages as such, let alone laziness.
I don't think that languages like LISP,Smalltalk, or even APL suffer
very much from artificial size constraints.

>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.

I can't see this being very beneficial. As soon as I search for a key
which is not in the tree, I need to do all pending insertions. As soon
as I search for a key which has recently been added I need to do most
pending insertions. If I support deletions or change of keys, these
will also require pending insertions to be done.  Further, I am
postponing a great deal of work that will probably need to be done
anyway. If I do many insertions, the next query may take a very long
time.

The biggest potential benefit of this might arise in a parallel
implementation, where insertions can be evaluted in the background.
Even here, I suspect that additional code would be needed to preserve
ordering, at least between queries and insertions.

I am not arguing for or against lazy evaluation, but I think these are
poor examples. 

-- 
 Alan Knight  knight@mrco.carleton.ca  +1 613 788 2600x5783   Join
 Dept. of Mechanical and Aerospace Engineering                the
 Carleton University, Ottawa, Ontario, Canada, K1S 5B6        LPF
From: vin@cs.arizona.edu (Vincent W. Freeh)
Newsgroups: comp.lang.functional
Subject: Scientific Programs?
Date: 28 Jul 92 16:23:37 GMT
Organization: U of Arizona, CS Dept, Tucson

I am interested in using functional languages to solve
scientific problems.  Some of the problem I am curious about
are:  Jacobi Iteration, SOR, adaptive quadrature, FFT, to name a few.

In my investigation I have only found real world scientific problems,
such as the above, solved in the functional language SISAL.  
Because of SISAL's for-all and for-initial constructs, mapping from an
imperative algorithm for the FFT to SISAL is relatively straight-forward (one 
of the goals of the SISAL project).  However, I have not seen any examples
of these types of problems solved in a ``traditional''
functional language--i.e. using recursion and/or pattern matching.

I am wondering if this is because 
	a) no one has tried it, or 
	b) I haven't looked in the right places, or
     	c) it cannot be done, or
	d) none of the above.

I am hoping the answer is b.  But I can live with a.  
Please inform me if you have solved any of the above or
similar problems using a ``traditional'' functional language.

Thanks,
Vince.
From: dat@ukc.ac.uk (D.A.Turner)
Newsgroups: comp.lang.functional
Subject: Re: algorithmic efficiency and lazy languages
Date: 23 Jul 92 15:36:00 GMT
Reply-To: dat@ukc.ac.uk (D.A.Turner)
Distribution: comp
Organization: Computing Lab, University of Kent at Canterbury, UK.

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.

David Turner
Newsgroups: comp.lang.functional