HDTenEightyP/NetNews huggingface dataset:
From: kff@dentex.tds.kth.se (Karl-Filip Faxen)
Subject: Re: Gabriel benchmarks in a functional language?
Reply-To: kff@dentex.tds.kth.se (Karl-Filip Faxen)
Organization: Royal Institute of Technology, Stockholm, Sweden
Date: Mon, 27 Jul 1992 15:32:05 GMT

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

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

I haven't seen the code for the Gabriel benchmarks, but I can see three
reasons for this result:

(1) The benchmaks throws away their results, since they are just
    benchmarks. This is an old problem with optimizing compilers,
    that they eliminate 'unnecessary' code. It is interresting to
    note that in this sense, any lazy implementation will behave
    like a heavily optimizing implementation of an imperative 
    language. This is often referred to as the 'self optimizing
    property' of lazy evaluation.

    The cure is, of course, to rewrite the benchmarks to do something
    with their result (eg write it to a file).

(2) The code is probably written so that datastructures are built
    and traversed. Now, these may sometimes not be traversed in their
    entirety, with the choice of what parts to traverse or not being
    data dependent. Also, these datastructures may be shared, ie 
    traversed by several different functions. Then lazy evaluation
    guarantees that only the parts that actually are traversed will
    be constructed, and then they will only be constructed once.

    In a strict language, the datastructures in question will always
    be constructed in their entirety and only subsequently be
    traversed. The only way to get the behaviour of the lazy language
    is to merge the producer and consumers of the datastrucure. This
    may be hideously difficult and lead to very messy code, especially
    if there are multiple consumers (sharing), and one wishes to avoid
    recomputation by every consumer. In any case, even if there is only
    one consumer, modularity is greatly compromised.

    Thus laziness allows you to separate the problem of how to build
    the datastructure from the problem of determining how much of it 
    will actually be needed.

(3) Sometimes, the evaluation order of a lazy evaluator is more 
    efficient than that of a strict evaluator, since the lazy evaluator
    might build and traverse a datastructure incrementally using a 
    constant amount of heap space and increasing the locality of the
    computation. This might have been such a case.


Karl-Filip
-----------------------------------------------------------------------
Make the frequent case fast, and the fast case frequent!
Newsgroups: comp.lang.functional
From: dtarditi@CS.CMU.EDU (David Tarditi)
Subject: algorithmic efficiency and lazy languages
Date: Tue, 21 Jul 92 07:35:49 GMT
Organization: School of Computer Science, Carnegie Mellon University
Distribution: comp
Originator: dtarditi@DESERT.FOX.CS.CMU.EDU

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.

As a side note, it is sufficient to base the argument simply on
affecting asymptotic space complexity, since that affects the 
asymptotic time complexity of garbage collection.

It seems hard to argue that referential transparency is more
important to language design than the ability to predict the
algorithmic behavior of one's programs, given the fact that
a vast section of computer science is devoted to the study
of algorithms.

  -- David Tarditi
From: basile@soleil.serma.cea.fr (Basile STARYNKEVITCH)
Newsgroups: comp.lang.functional
Subject: Re: References to Generational garbage collection
Keywords: garbage generational
Date: 22 Jul 92 07:31:14 GMT
Reply-To: basile@soleil.serma.cea.fr (Basile STARYNKEVITCH)
Organization: Commissariat a l Energie Atomique

In article <19376@optima.cs.arizona.edu>, saunders@cs.arizona.edu (Richard T. Saunders) writes:
|> Does anybody know of any (preferably introductory) good places for
|> information of generational garbage collection? 

There are a lot of papers and some book chapters on that subject. Of
course, i don't claim to have a full list (and i am interested by
recent papers on Generational G.C.):


Books (with chapters on G.C.):

"Topics in Advanced Language Implementation"
Peter LEE ed.
MIT Press 1991
ISBN 0-262-12151-4
contains a paper by A.W.APPEL: "Garbage Collection";

"Functionnal Programming"
A.J.FIELD & P.G.HARRISON
Addison Wesley 1988
ISBN 0-201-19249-7
contains a chapter on G.C.


Recent Papers:

A.W.APPEL "A runtime system" 
Lisp & Symbolic Computation 1990, 3, pp343-380

H.G.BAKER
"the Threadmill, real-time Garbage Collection without Motion Sickness"
ACM SIGPLAN Notice vol27 n3 March 92

H.G.BAKER
"CONS should not CONS its Arguments, or a Lazy Alloc is a Smart Alloc"
ACM SIGPLAN Notice vol27 n3  March 92


D.UNGAR & F.JACKSON
"an Adaptative Tenuring Policy for Generation Scavengers"
ACM Transactions on Programming Languages & Systems vol14 n1, Jan 92, pp1-27

C.CHAMBERS, D.UNGAR, E.LEE
"An efficient Implementation of SELF ..."
Lisp & Symbolic Computation 1991, 4, pp243-281 (and also OOPSALA 89?)


and many other papers on parallel generational garbage collection (eg OOPSALA 91....)


Again if someone have other recent references i'm interested (and also
by ftp sites having them).



-- 
Basile STARYNKEVITCH
Commissariat a l Energie Atomique
DRN/DMT/SERMA * C.E. Saclay bat.470 * 91191 GIF/YVETTE CEDEX * France
fax: (33) 1- 69.08.23.81;    phone: (33) 1- 69.08.40.66
email: basile@soleil.serma.cea.fr;  homephone: (33) 1- 46.65.45.53
N.B. Any opinions expressed here are solely mine, and not of my organization.
N.B. Les opinions exprimees ici me sont personnelles et n engagent pas le CEA.
From: ark@alice.att.com (Andrew Koenig)
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Date: 27 Jul 92 14:06:55 GMT
Article-I.D.: alice.23325
Organization: AT&T Bell Laboratories, Liberty Corner NJ

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

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

Hmmm...

I've heard from my friends in the ML community that they're thinking about
introducing a new primitive to make it easier to write lazy programs
in ML, much like delay/force in Scheme.

Now I see discussion of introducing a strictness primitive in Haskell.

The two camps are moving closer together.  Indeed, the question begins
to look like a human-factors one: is it more convenient to use a strict
language where the strictness can be turned off on request or a lazy
language that can be made strict in places?
-- 
				--Andrew Koenig
				  ark@europa.att.com
From: fegaras@freya.cs.umass.edu (Leo Fegaras)
Newsgroups: comp.lang.functional
Subject: Re: Bird-Meertens Formalism
Keywords: Program Derivation, Calculational Approach
Date: 23 Jul 92 16:03:33 GMT
Organization: University of Massachusetts, Amherst


Nico Verwer writes:

>                                                               On the
> other hand, there is not yet a system for automatic reasoning in BMF.

There is an automatic theorem prover based on Fokkinga's paramorphisms.
This work is described in the paper:
L. Fegaras, T. Sheard, and D. Stemple.
"Uniform Traversal Combinators: Definition, Use and Properties"
In eleventh International Conference on Automated Deduction
(CADE-11), Saratoga Springs, New York, June 1992.

Leo Fegaras
From: ajtd@st-andrews.ac.uk (Antony J. T. Davie)
Newsgroups: comp.lang.functional
Subject: garbage collection
Date: 21 Jul 92 15:35:23 GMT
Organization: St. Andrews University, Scotland.

Richard Sauders asks:

>Does anybody know of any (preferably introductory) good places for
>information of generational garbage collection?  I have seen the
>term mentioned in this group numerous times without "truly"
>understanding what it meant.  

Here's one reference:


D. Ungar "Generation Scavenging: A Non-Disruptive High Performance Storage
Reclamation Algorithm" SIGPLAN 19(5) 1984, pp157-167
Newsgroups: comp.lang.functional
From: boehm@parc.xerox.com (Hans Boehm)
Subject: GC complexity (was algorithmic efficiency and lazy languages)
Organization: Xerox PARC
Distribution: comp
Date: 23 Jul 92 21:03:13 GMT

acha@CS.CMU.EDU (Anurag Acharya) writes:
>... 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). 

(I hate to start this thread again, especially since it's irrelevant to
the previous discussion, but ...)
As far as I know, the above statement about mark-sweep collection is
only meaningful and correct if:

1. Allocation and initialization time is not considered,
2. Concurrent or incremental collection is not considered.  (Otherwise it
becomes hard  and pointless to distinguish the collector and the allocator.)
3. The M/S collector is not allowed to defer sweeping to allocation
time, e.g. by using a bit map representation of the free list.
4. The collector does not attempt to maintain the heap size as a fixed
multiple of the amount of live data (otherwise there's no asymptotic
difference between the two).

(1) seems rather arbitrary.  There are great arguments for violating (2)
through (4), and I don't know of any good arguments for not implementing
at least (3) (and (4) under a real OS).

Thus, I think a more informative version of the standard statement
about asymptotic complexity of mark/sweep collection is:

It's possible to implement mark-sweep collection so badly that garbage
collector pause time is proportional to all space available to the
program.

Of course, there are other arguments why mark-sweep collection might
to e.g. copying collection under the right circumstances.  But I think
the asymptotic complexity argument is 95% bogus.

Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...
From: sjv@doc.ic.ac.uk
Newsgroups: comp.lang.functional
Subject: Re: Lazy languages considered questionable
Date: 21 Jul 92 09:33:54 GMT
Organization: Imperial College

In article <1992Jul20.213929.10686@m.cs.uiuc.edu> morrison@dante.cs.uiuc.edu
(Vance Morrison) writes:
>...
>That is the very point I was trying to make.  Namely that when you
>use 'lazy lists' or other structures that work only in lazy languages
>you ARE worrying about order of evaluation.   (Since you have to make
>sure that your program terminates).   Now granted, you have to worry
>about order of evaluation in a strict language too, but since lazy
>data structures are not allowed, this reason can be highly localized
>(that is the termination properties of a piece of code are only 
>very loosely coupled to the inputs to that code).   If infinite 
>structures are allowed, that reasoning is not longer has localized
>(since figuring out the termination properties now depends strongly
>on the input given).  
>...

Please can we have some examples to illustrate these points? 


>The bottom line is that if you REALLY want to abstract order of 
>evaluation away, you have to use a STRONGLY NORMALIZING language
>(they do exist, take type theory for example).   Now order of evaluation
>truely doesn't matter since any evaluation order terminates.  

On the face of it, evaluation order is related more closely to the
Church-Rosser property than to strong normalization.

Steve Vickers.
From: jdr@starflight.Corp.Sun.COM (Jon Roland)
Newsgroups: comp.lang.functional
Subject: Re: Scientific Programs?
Date: 30 Jul 1992 04:24:14 GMT
Organization: Sun Microsystems, Inc.
Distribution: world
Reply-To: jdr@starflight.Corp.Sun.COM
NNTP-Posting-Host: starflight.corp.sun.com

In article 19713@optima.cs.arizona.edu, vin@cs.arizona.edu (Vincent W. Freeh) writes:
>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.
>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.

I don't know if you would consider it "traditional", but you should look at
the Nial language, currently implemented as Q'Nial, available from

  Nial Systems Ltd
  155 Queen St 9th Flr
  Ottawa, Ontario, Canada K2P 5C9
  613/234-4188

It is accompanied by an extensive set of user-contributed libraries of
operations that include what you are seeking. They offer the additional
benefit of being fairly readable by people who do not make their living
by programming, but by persons knowledgeable about the subject domain
after investing a little time to familiarize themselves with the notation.

Considered only as a system of notation, Nial has enormous expressive
power for scientific ideas that stimulates the discovery of further
scientific ideas. The nice thing about this notation system is that you
can also run it on a computer.

---

jdr@starflight.corp.sun.com, starflt@uunet.uu.net
Jon Roland
Starflight Corporation, 1755 E Bayshore Rd #9A,
Redwood City, CA 94063-4142, 415/361-8141
From: skill@qucis.queensu.ca (David Skillicorn)
Subject: Polynomial functors (in categorical datatypes)
Organization: Computing & Information Science, Queen's University
Date: Wed, 22 Jul 1992 16:51:53 GMT


I'm pretty sure that polynomial functors are not what's
really needed to make Malcolm-style datatype constructions
in BMF work. There's a paper from the group at Calgary
(Cockett et al.) from which I gather that strength is
the real property of importance. This can be arranged
in several ways, one of which is to use a polynomial
functor in a CCC. Some people (Bob Walters for one)
would argue that this is the wrong setting, and prefer
distributive categories.

Anyway it seems possible to get the kind of benefits
that the CDT construction gives without needing
the polynomial restriction.

But we're getting a bit far from the centre of this
newsgroup.

The Calgary work can be obtained by ftp from
cpsc.ucalgary.ca in directory pub/charity/PAPERS.

                       -david skillicorn

Newsgroups: comp.lang.functional
From: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Subject: Re: ** LAZY LANGUAGES FASTER?? **
Organization: Computer Science, University of Melbourne, Australia
Date: Wed, 29 Jul 1992 07:56:01 GMT

erik@wsinfo03.win.tue.nl (Erik Poll) writes:

>In lazy languages, an argument is evaluated once for every time that it 
>is used. If the argument is used N times, it will be evaluated N times. 

As everyone has pointed out, lazy evaluation means evaluating each argument
at most once. The correct term for the sort of evaluation strategy you
were describing is "normal-order evaluation" (at least according to my
programming languages textbook).

-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
This .signature VIRUS is a self-referential statement that is true - but 
you will only be able to consistently believe it if you copy it to your own
.signature file!
From: boehm@parc.xerox.com (Hans Boehm)
Newsgroups: comp.lang.functional
Subject: Re: algorithmic efficiency and lazy languages
Date: 23 Jul 92 17:23:29 GMT
Distribution: comp
Organization: Xerox PARC

dat@ukc.ac.uk (D.A.Turner) writes:

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

It seems to me that this is insufficient.  It basically tells us that it's
possible to write accurate profilers.  The real question is:  Are the Tfi
sufficiently simple for real programs that I can understand what's going
on, and use them to drive my algorithm design? 

>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

Hans-J. Boehm
From: dlester@cs.man.ac.uk (David Lester)
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Keywords: This is probably where the article got lost...
Date: 29 Jul 92 09:40:19 GMT
Reply-To: dlester@cs.man.ac.uk (David Lester)
Organization: Department of Computer Science, University of Manchester

In article <1992Jul28.194846.7295@cs.chalmers.se>, augustss@cs.chalmers.se (Lennart Augustsson) writes:
|> 
|> 	-- Lennart
|> 
|> -- 
|> 
|> 	-- Lennart Augustsson
|> [This signature is intentionally left blank.]

Doubtless this article, quoted in its entirety, was generated by an LML
program(mer) that was being too lazy.

---
David Lester, Manchester University, UK.

[ ... but a nice meta-comment anyway, Lennart.]
Newsgroups: comp.lang.functional
From: dmg@maia.mitre.org (David M Goblirsch)
Subject: Re: Scientific Programs?
Organization: Mitre Corporation, McLean, VA
Date: Tue, 28 Jul 1992 20:34:57 GMT


I too am interested in scientific applications of functional languages. In
particular, I have started to prototype my speech recognition algorithms
in Haskell.

Other than the FFT, I have not seen any scientific programming examples
done in the lazy functional languages.  So far, I have written a
spectrogram program in Haskell, and also a program for building a
hierarchical representation of a speech signal using dendrograms.
However, neither of these is quite ready for public consumption yet.

If you are not particularly interested in lazy languages, you should check
the Mathematica Journal or the Mathematica reference book by Stephen
Wolfam.  Mathematica contains a functional sublanguage, and the Journal
contains examples of how to use it to solve scientific problems.  Because
it's intended for mathematics, it doesn't have the nice terse syntax of
Miranda or Haskell; but its "prelude" contains a lot of math oriented
functions in addition to the usual take, drop, etc.

David M. Goblirsch, The MITRE Corporation, McLean VA 22102
dmgob@mitre.org
(703) 883-5450



--

David M. Goblirsch, The MITRE Corporation, McLean VA 22102
dmgob@mitre.org
(703) 883-5450
From: dbh@doc.ic.ac.uk (Denis Howe)
Newsgroups: comp.lang.functional
Subject: Gabriel benchmarks in a functional language?
Date: 23 Jul 92 15:24:42 GMT
Organization: Computing Department, Imperial College, London, UK

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?
Newsgroups: comp.lang.functional
From: dwights@ogicse.cse.ogi.edu (Dwight Spencer)
Newsgroups: comp.lang.functional
Subject: Re: Polynomial functors (in categorical datatypes)
Date: 22 Jul 92 21:05:54 GMT
Article-I.D.: ogicse.40402
Distribution: world
Organization: Oregon Graduate Institute (formerly OGC), Beaverton, OR

Article 1960 of comp.lang.functional:
In article <1992Jul22.165153.737@qucis.queensu.ca>
skill@qucis.queensu.ca (David Skillicorn) writes

 > I'm pretty sure that polynomial functors are not what's
 > really needed to make Malcolm-style datatype constructions
 > in BMF work. There's a paper from the group at Calgary
 > (Cockett et al.) from which I gather that strength is
 > the real property of importance.

At least it seems to be an important starting point if we are to take
categorical programming within the Hagino style seriously.

The "et al." group includes Tom Fukushima who has actually implemented
such a CDT programming language (CHARITY) with initial and final datatypes,
and myself, whose thesis - "Categorical Programming with Functorial
Strength" that expounds on much of the categorical underpinnings of this
language - will be completed within the next month or so. The parallels 
with Malcolm's syntactic calculus are very strong (not a pun) and the
variety of datatypes available to the programmer is quite reasonable
for much practical programming (e.g. database applications).

- Dwight Spencer

  Oregon Graduate Institute --> Trinity College, Hartford, CT
From: ajtd@st-andrews.ac.uk (Antony J. T. Davie)
Newsgroups: comp.lang.functional
Subject: Re: programs that are too lazy
Date: 27 Jul 92 08:30:20 GMT
Organization: St. Andrews University, Scotland.

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.

Tony Davie
From: greg.vigneault@bville.gts.org (Greg Vigneault) 
Newsgroups: comp.lang.modula2
Subject: FST MODULA-2 RUN-TIME
Date: 28 Jul 92 19:19:00 GMT
Distribution: world
Organization: Baudeville BBS - Toronto, Canada 416-283-0114/6059* *v32bis/HST
Reply-To: greg.vigneault@bville.gts.org (Greg Vigneault) 


 Is there anyone here who registered their shareware FST Modula-2
 compiler with Fitted Software Tools, before they disappeared?

 I'm interested in getting the compiler run-time source.

 Greg_

 Jul.28.1992.Toronto.Canada.
 greg.vigneault@bville.gts.org
 gregsv@eastern.com
                                                                                                           
Newsgroups: comp.lang.modula2
From: randy@psg.com (Randy Bush)
Subject: Re: MODULA2 COMPILER FOR DOS
Organization: Pacific Systems Group, Portland Oregon, US
Date: Sat, 25 Jul 1992 22:30:29 GMT

greg.vigneault@bville.gts.org (Greg Vigneault)  writes:
>  The last version of FST Modula-2 was 2.0b, and it's available on
>  many public BBS's.

and ftp.psg.com:~/pub/modula-2/pc/*

There were some libraries and tools distributed iff one registered FST
with Roger, and those are not available for FTP.  Should someone get
Roger's consent to make them publicly available, I will do so.
-- 
randy@psg.com   ...!uunet!m2xenix!randy