Benchmarking Lazy Functional Languages
Kenneth Cheng-Lim Seah
Hi there!
I'd like to poll the net opinion on the relative speeds of current
lazy functional languages with respect to imperative languages (such
as C). Do people think that there is an order of magnitude difference?
Or two or more?
Are there any benchmark papers out there comparing lazy functional
languages with each other (I have a couple) or with imperative
languages.
Thanks in advance!
-- K
--
Kenneth Seah (ks...@cs.utexas.edu|PO Box 8565, Austin, TX 78713-8565|TAY 5.144)
Grad Student, Dept of Computer Sciences, University of Texas at Austin
"Money means nothing 'cause hacks are free..." (Apologies to MK)
Paul Wilson
In article <466ug9$2f...@news-s01.ny.us.ibm.net>,
Dietmar Logoz <lo...@ibm.net> wrote:
>In <45roal$4...@roar.cs.utexas.edu>, ks...@cs.utexas.edu (Kenneth Cheng-Lim Seah) writes:
>>
>> Are there any benchmark papers out there comparing lazy functional
>>languages with each other (I have a couple) or with imperative
>>languages.
>
> Richard P. Gabriel, Performance and Evaluation of Lisp Systems,
> Cambridge MA, MIT Press, 1985
Unfortunately, this book isn't about lazy languages, and many of the
benchmarks in the suite are not functional, i.e., they use side
effects. It's about Lisp, not functional programming.
My impression is that there is essentially zero reliable quantitative
data comparing the efficiency of lazy functional languages to eager
imperative (dysfunctional?) languages. (Tiny benchmarks don't count---I'm
talking about real applications, and source code sizes in at least the
hundreds of lines, preferably many thousands.)
The only remotely "real" study I know of is one comparing languages for
rapid prototyping. It'd be interesting to see one for generating approximately
production-quality code, i.e., you get it to work and also spend a few days
tuning it.
My impression from anecdotal reports is that programs in lazy functional
languages tend to be a factor of five or ten slower than imperative
programs in (say) C or Modula doing the same job. (There are exceptions
where the functional program may run as fast or faster, but on average
they're "several" times slower.)
I'd be interested in knowledgeable peoples' opinions on this. In particular,
I'd be interested in whether it's true that lazy languages tend to be almost
an order of magnitude slower than imperative ones---even with the best
compilers---and if so, why? I myself don't know much about the deep
issues in using and compiling functional languages, so comments are very
welcome.
Some hypotheses (NONE of which I'm defending!) for discussion:
0. You have to have side effects to be able to write a lot of algorithms
efficiently. Most of the costs of lazy functional languages are due
to excessive copying or expensive data structure lookups, where
side effects would allow you to solve the problems with lower
computational complexity, e.g., fast constant time vs. log time
with an obnoxious constant.
1. Lazy languages are intrinsically slow, because no feasible compiler
can eliminate the overheads of laziness. The analyses are just
too hard to be automated, and we're in trouble here.
I'm not sure if this is true, or why. Does laziness defeat conventional
optimizations because control flow is too unpredictable? Would some
slightly clever compilers be able to fix the problems, by being able
to guess the likely control flow? (Based on static heuristics, profiling
and recompilation, dynamic feedback guided incremental recompilation...)
(In some recent discussions it sounded like people didn't really use
laziness that much, in the sense that they usually knew which parts
of their applications relied on laziness and could make that explicit
without too much trouble. This would reduce overheads immediately;
I wonder if it would also have a big effect on code quality once
other aspects of compilers improve significantly---is laziness a
bottleneck to achieving performance that will become progressively
more important?)
2. Compilers for lazy languages are still not mature, because people
have spent too much time on fancy features and not enough of basic
back-end optimization. (e.g., doing closure elimination and lifetime
analysis and type inference and so on, but not getting around to
bread and butter optimizations like data flow and control flow
analysis, register allocation, instruction scheduling, and so on.)
The extreme version of this would be that compiler writers need
to work on their back ends and everything will be fine.
The less extreme version is that the standard compiler stuff is a
little harder to do in this context, but with some work it'll
get integrated with the wonderful front-end parts of the compilers
and functional languages will be competitive.
A variant is that there just aren't enough people working on the
compilers, so the population isn't big enough that you can pick
the best compiler from a very variable bunch and it will be very good.
Another variant is that the appropriate compiler techniques are
different from the traditional ones, and more general (e.g.,
abstract interpretation, partial evaluation). In the short term,
the intractability of such general techniques is a problem, but
once they're tuned with the right heuristics, etc., functional
programming languages will speed up and eventually surpass imperative
languages, because their general niceness provides more opportunities
for automatic analysis and optimization.
3. People haven't learned to program the right ways in functional
languages, because it's really hard. You can code almost any
program efficiently in a functional language, but you have to
know avante-garde tricks to get it to really work well. E.g.,
the judicious use of monads, etc., and it's really hard to know
what the appropriate techniques are.
A more optimistic view is that people are getting to have a better
understanding of these things, and the techniques will soon be
pretty well understood, so that normal programmers will be able
to write efficient programs easily Real Soon Now.
4. Interactions between 3 and compiler issues are the problem---the
idioms people use in functional programming are not very standardized,
and the compilers are not well tuned for the ways people actually
write programs---they solve the "general" problems that can be
tractably solved, but they don't have a well-developed set of
heuristics for solving the particular problems that real programs
present a compiler. (E.g., they don't know anything much about
monads, and the usual compiler optimizations don't get as
much performance out of monadic code as a compiler would if it
exploited monadic idioms---kind of the way that FORTRAN compilers
are really good at big, dumb loops.)
5. It's a little of each of these.
Pessimistic version: using and compiling functional programming
languages (for efficiency) is just too hard, and functional code
will always be behind the curve performance-wise, because the
software engineering (of the code and especially of the compilers
is enormously difficult.
Optimistic version: good progress is being made on all of these
fronts and good performance will come in due course.
Anybody have well-worked out views about this, or failing that, some
reasonable intuitions based on some knowledge and experience? Where
will the big wins be from here? How long will it take?
Paul
--
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wil...@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and Scheme interpreters and compilers available via ftp from
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
Henry Baker
<jes...@cs.indiana.edu> wrote:
> A side note about the laziness issue: I tend to think that it is
> underappreciated, especially with regard to the expressiveness that it
> lends to programs, by the general programming populace. I don't think
> you can fully appreciate its nuances until you have programmed one or
> more large applications in a lazy language. The pedagogical examples
> presented in most programming courses (e.g. streams) give only the
> faintest glimmer of the possibilities, and even then the explicit
> manipulation required negates much of these programming benefits.
> Current popular VHLLs owe much of their popularity due to the fact that
> there is not as great a conceptual leap between programming imperative
> styles in different languages.
We're all ears. How about some concrete examples?? If you've got a catalog
of really good examples of why laziness is important, then this should be
worth a good conference/journal article.
Thanks in advance.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
Matthias Blume
Someone wrote:
>0. You have to have side effects to be able to write a lot of algorithms
>efficiently.
Are you sure about this?
There are some problems for which the best asymptotic complexity is
achieved by algorithms that seem to inherently rely on side-effects.
Union-find with path compression comes to mind. However, there are
some impressive results in the algorithms world that achieve very good
results and sometimes even lower bounds using purely functional
approaches.
--
-Matthias
Graham Matthews
>0. You have to have side effects to be able to write a lot of algorithms
>efficiently.
Are you sure about this? From a parallelising point of view side effects are
a pain in the neck as they interfere with dataflow ordering. Also side effects
may be necessary to get fast code, but that does not mean the languages we
program in need to contain side effect semantics. Take a look at the work the
Sisal group has done. Sisal is a pure applicative language (absolutely no side
effects, not even I/O). Sisal is of course compiled into a language which
contains side effects (C or assembler), but thats a job for the compiler not
the programmer.
graham
--
----------------------------------------------------------
England's not the mythical land of madame george and roses
It's the home of police who kill black boys on mopeds
----------------------------------------------------------
Martin Cracauer
It seems some of the posters in this discussion tend to see
optimization as the production of the shortest sequence of machine
statements.
Let me add that the speed of today's RISC processors depends on
optimal filling of their pipelines and that the performance
discrepancy of the cache compared to main memory gets bigger.
I think some of these points can be took in advance of functional
languages. To make full use of superscalar processors, one needs a
compiler that has a good interface to give it an idea of what
sequences of code will run fast on a given processor.
IMHO, it might be easier to write a good multi-target compiler in a
functional language under these circumstances. An abstract interface
to provide the necessary information for a given CPU type seems to be
easier to implement.
Look at the GNU C compiler. It's optimization in "classical" terms of
elimination of dead code and generating short sequences is good. But
the performance on modern superscalar processors gets worse compared
to the compilers provided by CPU makers. gcc's interface to tell about
optimal instruction sequences isn't really an elegant and powerful
one. Of course, there are few - if any - multi-platform *and*
superscalar-optimizing compilers for C or C++. Functional languages
may be able to provide such a compiler with much less effort.
The other issue, the growing importantness of the CPU cache may be
used to the benefit of languages that can generate code on the fly. A
compiled C program can detect whether it trashes the cache, but can't
really do something about it (maybe switching to an alternate
precompiled piece of code). Languages with on-the-fly code generation
will maybe able to react on such a situation.
Upcoming OS interfaces like "OpenImplementation" from PARC and the GNU
Hurd will provide more feedback on what is going on with the
hardware. You can tell them about your expectation how you will use
memory you're about to allocate, you'll can tune of buffer cache for
your needs etc. You can use these interfaces from languages like C or
C++, but you program cannot in turn react to what is available at a
given time.
I'm not an implementator, just my 2 cents. I though the discussion is
too much on "classic" optimization and maybe chances are missed.
Martin
--
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Martin Cracauer <crac...@wavehh.hanse.de> - BSD User Group Hamburg, Germany
"As far as I'm concerned, if something is so complicated that you can't ex-"
"plain it in 10 seconds, then it's probably not worth knowing anyway"- Calvin
Henry Baker
Mogensen) wrote:
> You may well be able to do without arrays and destructive updating.
> Certainly (unless we have some assumptions about the implemenation),
> we can not in pure functional languages simulate array access/update
> in linear time.
> P.S.
> In the worst case, functional languages have a O(log(N)) penalty over
> imperative languages, as running a RAM can be simulated in O(N*log(N))
> time, where N is the number of operations done by the RAM.
Bzzzzt! Wrong!
If the array in the functional language is being used in an 'essentially'
imperative manner, then the implementation runs at the _same_ speed (O(1))
as the imperative language, and without _any_ fancy compiler optimizations.
This is a different approach from the uniqueness types approach, and has
been used in some Prolog implementations.
See
ftp://ftp.netcom.com/pub/hb/hbaker/ShallowArrays.html (also .ps.Z)
Thomas Charles CONWAY
>Someone wrote:
>>0. You have to have side effects to be able to write a lot of algorithms
>>efficiently.
>
>Are you sure about this? From a parallelising point of view side effects are
>a pain in the neck as they interfere with dataflow ordering. Also side effects
>may be necessary to get fast code, but that does not mean the languages we
>program in need to contain side effect semantics. Take a look at the work the
>Sisal group has done. Sisal is a pure applicative language (absolutely no side
>effects, not even I/O). Sisal is of course compiled into a language which
>contains side effects (C or assembler), but thats a job for the compiler not
>the programmer.
Some data structures (eg arrays and hash tables) are generally too
expensive to use if you can't be sure that imperative update will be
used on them (copying entire arrays all over the place would be really
bad). Languages like Clean and Mercury allow the programmer to specify
as part of the type or in the case of Mercury, part of the mode, that
a structure is unique and may be imperatively updated.
The uniqueness information does not compromise the declarative semantics,
but ensures that all the uses of a structure conform to the rules that
enable imperative update to be used. The fact that the compiler introduces
side effects in the generated code has no effect on the declarative semantics
since the compiler will only do so where it can prove it to be safe.
Thomas
--
Thomas Conway con...@cs.mu.oz.au
AD DEUM ET VINUM obscure incantation for the day: pr#6
Stuart Clayman
>>Someone wrote:
>>>0. You have to have side effects to be able to write a lot of algorithms
>>>efficiently.
>>
>>Are you sure about this? From a parallelising point of view side effects are
>>a pain in the neck as they interfere with dataflow ordering. Also side effects
>>may be necessary to get fast code, but that does not mean the languages we
>>program in need to contain side effect semantics.
>Some data structures (eg arrays and hash tables) are generally too
>expensive to use if you can't be sure that imperative update will be
>used on them (copying entire arrays all over the place would be really
>bad).
You may well be able to do without arrays and destructive updating.
Certainly (unless we have some assumptions about the implemenation),
we can not in pure functional languages simulate array access/update
in linear time. But who says we have to? It is quite conceivable that
most problems can be handled purely functionally with the same
complexity as in imperative languages. Here I look at the complexity
including reading the input and printing the output as text. Hence, I
invalidate algorithms that for a problem of (so-called) size N,
require the input to be given as an already instantiated NxN matrix,
e.g specifying an N-vertex graph by a neighbour matrix.
You can do array and hash table operations quite nicely in functional
languages.
You do need built in arrays, and operations on them to do it
effectively (such as O(1) access), but creating a new array each time
is not that bad. You can have a special heap of array memory (using a
buddy system perhaps) and most machines these days can do block-copies
pretty rapidly, so copying is not much of an issue.
Also, with some analysis techniques it is possible to do update
in-place on the array to avoid the unnecessary copying. To make it
simpler, you can limit this to just once cell at a time.
By having this functionality you can do arrays nearly as effectively
as imperative languages. Note that in serial, imperative languages
arrays and hash tables are only ever accessed or updated one cell at a
time. This means that functional versions of these algorithms using
the above primitives need not be so inefficient.
I looked at all this for my PhD a few years ago. The current problem
is the lag getting this stuff in implemenations, but I think most
recent Haskell systems have this, or are pretty close. (Someone will
correct if I'm wrong).
stuart
Eric Jeschke
:In article <1995Oct24.1...@news.cs.indiana.edu>, "Eric Jeschke"
:<jes...@cs.indiana.edu> wrote:
:Thanks in advance.
[Sorry for the late reply--I don't keep up with this group daily]
OK. Here are a few examples of small things that I have noticed after
coding in a lazy language for a while. My guess is that most readers
of these groups will think: "Oh, I can do that in <insert favorite
strict symbolic language> by using <insert explicit delayed evaluation
trick>. Of course you can; I'm not arguing that. The crux of the point
I was trying to make is that when you combine these and other artifacts
that arise easily and naturally under a lazy language you end up with a
programming style that is distinctly different in character, sometimes
subtly, but definitely noticeable. I agree that this would make an
interesting journal article. Perhaps if I had a few more examples...
A similar argument can be made for other paradigms; e.g. a distinct
programming style develops using a truly object-oriented language as
opposed to coding in an OO style in a non-OO language. However, I don't
know enough about these to make a good analogy here.
Caveat: these examples arise from programming in Daisy, a sort of lazy
counterpart to Scheme. Some of these examples may not apply to other
lazy languages that have quite different attributes (e.g. strong typing).
I have tried to pick only things that are primarily linked to laziness
and not just a functional style. This list is hardly comprehensive;
if you have another good example please jump in and tack it on.
[1] It is routine to de-structure a function argument before knowing
the actual structure passed, because the binding is delayed.
This occurs frequently in mapping functions where in strict languages
you'd test for a nil argument right away before doing anything else.
This results in multiple conditionals, separated by _lets_, where in
a lazy language you generally end up with fewer conditionals--
often one local binding followed by one conditional.
in Scheme
--------------------------
(define foo (lambda (l)
(if (null? l) ...
(let ((x1 (caar l)) (y1 (cadar l))
(x2 (caadr l)) (y2 (cadadr l))) ; did I get these right?
(if (x1 < 0) ...
(let ...
in Daisy
--------------------------
foo = \l.
let:[ [[x1 y1] [x2 y2]] l
if:[ nil?:l ...
neg?:x1 ...
]
]
[ In a pattern-matching language it's even shorter: ]
foo [] = ...
foo [[x1 y1] [x2 y2]] = ...
[2] I often create local bindings to large or (potentially) erroneous
computations before I decide whether to use them. For example, I
might create a binding to the recursion of a function over the tail
of its argument so that I can conveniently refer to it later in
the body in multiple places with a single identifier, rather than
explicitly expressing the same recursion over and over.
[3] Similar idea, different application is "data continuations".
I frequently pass data continuations around between functions--
the data continuation is the result of rest of the computation.
This allows me to avoid costly functional appends and instead
just cons data on to the front of the result.
[4] Prevalent use of streams. Essentially the inverse of [3]--one can
create a binding in the tail of a list to a future computation
which makes expressing streams trivial. Combined with transparent
stream coercion, streams are commonplace in lazy languages and rarely
used in others, except for special "I/O streams".
Note that these are all just subtle variations on the tacit assumption
of laziness.
To respond to Baker's original question, I think that a Scheme that
provides explicit delays and _implicit_ forces provides much of the power
needed to express these kinds of things semi-conveniently in Scheme.
For the curious, what was the motivation for the original question?
How many working Scheme's actually provide implicit "force"s?
--
Eric Jeschke | Indiana University
jes...@cs.indiana.edu | Computer Science Department
John Feo
Array structures with O(1) access are absolutely essential for
performance, parallelism and vectorization. Mathematical and
scientific codes written with data structures other arrays are too slow
to be of any interest to application programmers.
If the functional language has true arrays, array operations, and
does not permit the expression defining an array to reference array
elements, then the compiler can determine the size of most arrays
and preallocate memory, build the array in place and in parallel
(assuming no data dependencies), eliminate almost all unnecessary
copy operations implied by destructive updates, and reclaim storage
on last use.
The Sisal compiler has been doing this since 1987!!! Our array codes
on one processor are just as fast as Fortran codes, and usually faster
than C codes. On multi-processors we win hands down.
Arrays, array operations, destructive updates, garbage collection of
array structure, and performace in a functional language is a done
deal.
Next topic!!!
John
John Sargeant
In article <47sth0$l...@odin.diku.dk>, tor...@diku.dk (Torben AEgidius Mogensen)
writes:
|>
|> In the worst case, functional languages have a O(log(N)) penalty over
|> imperative languages, as running a RAM can be simulated in O(N*log(N))
|> time, where N is the number of operations done by the RAM.
However, the constant is huge. We gave up on this one about 1980.
More interesting question: which algorithms using arrays and destructive
update are/or not amenable to sharing analysis when cast in functional
form? What work is there on this other than the SISAL work?
John
Rod Oldehoeft
> Array structures with O(1) access are absolutely essential for
> performance, parallelism and vectorization. Mathematical and
> scientific codes written with data structures other arrays are too slow
> to be of any interest to application programmers.
Absolutely correct. No implementations with logarithmic factors, or
even constant factors, over simple imperative array access can be
considered as competitive.
> If the functional language has true arrays, array operations, and
> does not permit the expression defining an array to reference array
> elements, then the compiler can determine the size of most arrays
> and preallocate memory, build the array in place and in parallel
> (assuming no data dependencies), eliminate almost all unnecessary
> copy operations implied by destructive updates, and reclaim storage
> on last use.
That is, the current SISAL 1.2 language does not have an array
comprehension or constructor as found in Id, for example; arrays
are the products of iterative or parallel loops. In this context
what John says is true. Further, we know how to add an array
constructor and preserve the truth of the above.
> The Sisal compiler has been doing this since 1987!!! Our array codes
> on one processor are just as fast as Fortran codes, and usually faster
> than C codes. On multi-processors we win hands down.
Well, to pick a nit, statements about many array optimizations have been
true for SISAL since 1989, when Cann's dissertation work was completed.
Plus, there were a couple of years more work by him and others at LLNL
before the performance claims above could be said. It may be in place
(no pun intended), but it was not easy.
One must also acknowledge research done by others in more difficult
functional language contexts, at about the same time.
> Arrays, array operations, destructive updates, garbage collection of
> array structure, and performace in a functional language is a done
> deal.
True, in the context of SISAL 1.2. Not everything we want to do with
arrays while preserving/enhancing high performance is embodied there,
however.
Fergus Henderson
>You may well be able to do without arrays and destructive updating.
Sure, if performance is irrelevant. But usually it is not.
>It is quite conceivable that
>most problems can be handled purely functionally with the same
>complexity as in imperative languages.
Even if this were the case, it would not be sufficient.
>In the worst case, functional languages have a O(log(N)) penalty over
>imperative languages, as running a RAM can be simulated in O(N*log(N))
>time, where N is the number of operations done by the RAM.
Never mind the complexity - what about the constant factors?
For most functional language implementations, the constant factors
are pretty bad compared to conventional languages. Bad enough
to rule them out for many application programs.
--
Fergus Henderson WWW: http://www.cs.mu.oz.au/~fjh
f...@cs.mu.oz.au PGP: finger f...@128.250.37.3
Paul Wilson
>
>>In the worst case, functional languages have a O(log(N)) penalty over
>>imperative languages, as running a RAM can be simulated in O(N*log(N))
>>time, where N is the number of operations done by the RAM.
>
>Never mind the complexity - what about the constant factors?
>For most functional language implementations, the constant factors
>are pretty bad compared to conventional languages. Bad enough
>to rule them out for many application programs.
I've found the discussion of these issues quite interesting, but I still
don't feel that I have the big picture.
From several postings and pieces of email, it seems that the consensus
is that lazy pure FP languages are usually a factor of 2 to 10 slower
than conventional imperative languages.
It also appears that lazy FP programmers often "cheat" in some sense, by
using imperative and side-effecting constructs in crucial parts of
their code. (One of the few concrete examples given was that the
Glasgow Haskell Compiler's type checker was sped up by a factor of
50 by judicious use of side effects.)
What I'm trying to figure out now is whether the factor of 2 to 50 is
a constant factor performance loss (and assumes that log factors have
been eliminated by use of side effects here and there), or whether
it includes log factor losses that typically amount to a small constant.
So my question is this: if you DON'T use side effects and other impure
techniques, do you lose a factor of 2 to 10---or some log factor that
usually amounts to a fator of 10 or 100? (Naturally, depending on what
you're coding, this could be a factor of 1 or 1000 for some programs.)
Naturally, I expect that the evidence is rather anecdotal, but I'm
curious what the informed views on this are. Do most large application
programs have big losses if you don't cheat? Or is the factor of 2 to
10 about right assuming a pure FP style?
If you were advising somebody on the use of FP for real, large systems
(with a variety of components and algorithms), would you tell them
to expect to lose a small constant factor from using a pure style,
or a much larger scalability loss?
And to the degree that people are expected to cheat, how cheating do
they have to be? (e.g., can you usually slap monads around things
very easily and encapsulate the stateful parts, and get code that
performs quite well, or is it a big hassle?)
Seth M. LaForge
>Someone wrote:
>>0. You have to have side effects to be able to write a lot of algorithms
>>efficiently.
>
The one area I've seen in which a non-side-effecting style is
dramatically weaker then a side-effecting one is circular data
structures. There are many areas in which cyclic data structures are
necessary, for instance generation of cyclic graphs in compiler
optimization passes. As far as I know, there is no purely functional
language in which one can implement explicitly circular data
structures. A friend of mine implemented cyclic graphs in ML by using
a lookup table to map from strings to nodes and representing edges as
strings, but this strikes me as using explicit dereferencing to
effectively get side-effects (creating a new table with a different
association for a particular string effectively rebinds all edges to
that node).
Any opinions out there? I have relatively little experience in
functional programming, so I may be wrong on some points. Am I right
that it's impossible to create circular data structures without
side-effects? Do functional programs which need circular data
structures use explicit dereferencing, or use some other method of
getting effectively circular data types, or avoid circular data types
in the first place?
Seth
Graham Matthews
>>Some data structures (eg arrays and hash tables) are generally too
>>expensive to use if you can't be sure that imperative update will be
>>used on them (copying entire arrays all over the place would be really
>>bad).
You should look at the work by the Sisal group. They have arrays in a pure
applicative language and yet they avoid copying arrays by clever compilation
algorithms (they don't avoid all copies, but a lot of them).
Kragen Javier Sittler aka xentrac
Torben AEgidius Mogensen <tor...@diku.dk> wrote:
>hba...@netcom.com (Henry Baker) writes:
>
>>In article <47sth0$l...@odin.diku.dk>, tor...@diku.dk (Torben AEgidius
>
>>If the array in the functional language is being used in an 'essentially'
>>imperative manner, then the implementation runs at the _same_ speed (O(1))
>>as the imperative language, and without _any_ fancy compiler optimizations.
(and he gives a reference, which I read)
>I did say "In the worst case". I'm well aware of several methods that
>implement constant time array access/update. Some use amortized costs,
> . . .
>From a practical point of view, it is not the asymptitic behavior that
>is a problem with functional arrays, it is the constant factors that
>do matter. Here the uniqueness types (or similar) approach ensures
>that arrays can be implemented exactly as in imperative languages,
>with no overhead. Another often used approach is to let updates
>actually destructively update the array, and let earlier "copies"
>refer to this but have lists of the values of updated cells. This
>ensures constant time access if only one copy is actually active (the
>imperative case) while giving correct behaviour for non-linear uses,
>but there is an overhead that makes it about 3-5 times slower than
>imperative array access. The method can be extended to provide
>amortized constant time access and update for arbitrary sharing/access
>patterns. But that increases the overhead even more.
Well, with my small but highly interested brain, I read the paper
Mr. Baker referenced; it appears that you're describing the same
method. (Unless I missed something.)
The paper does mention that there is overhead involved in gc'ing the
'difference' nodes; it doesn't mention how big the overhead is.
(The reference [Baker78a] made me shudder a bit; I think dynamic
scoping is an abomination! Using dynamic scoping and a reasonably
complex APL function, you can redefine the functions the
reasonably-complex function calls to make it do just about anything
you want. Or, more likely, didn't want!)
Peace,
Kragen
--
Peace
Kragen
Dominic Duggan
Paul Wilson <wil...@cs.utexas.edu> wrote:
>
>It also appears that lazy FP programmers often "cheat" in some sense, by
>using imperative and side-effecting constructs in crucial parts of
>their code. (One of the few concrete examples given was that the
>Glasgow Haskell Compiler's type checker was sped up by a factor of
>50 by judicious use of side effects.)
>
substitutions. Using side-effects provided a further 10-fold improvement.
Side-effects were encapsulated using monads to pass around a heap.
--
Spoken: Dominic Duggan Internet: ddu...@uwaterloo.ca
Canada: Dept of Computer Science, University of Waterloo,
Waterloo, Ontario, Canada N2L 3G1
WWW: http://nuada.uwaterloo.ca/dduggan.html
Torben AEgidius Mogensen
>So my question is this: if you DON'T use side effects and other impure
>techniques, do you lose a factor of 2 to 10---or some log factor that
>usually amounts to a fator of 10 or 100? (Naturally, depending on what
>you're coding, this could be a factor of 1 or 1000 for some programs.)
Side effects can be on two levels: the user level and the
implementation level. Well, any implementation of even purely
functional languages obviously uses sideeffects. What makes me bring
this point up is that even state-monads can be argued a side-effecting
implementation of a purely functional idea. However, any person that
sees a program with heavy use of monads will agree that it looks
imperative. So the point is really: what speed-loss (if any) do you
get by programming in purely functional _style_? This adds the
question: can the use of uniqueness types be considered
non-functional? I would say, no, as it is just an annotation that
allows efficient implementation. On the other hand, if you have to use
an unnatural coding style to achieve uniqueness, I would consider that
against the functional style idea.
If you don't consider the style, I believe that you can translate
imperative code to fully functional code with uniqueness types and
implement it with very little (if any) overhead. But that is really
quite uninteresting, as this doesn't make a good argument for
functional programming.
I think a lot of the use of imperative style (e.g. monads) in
functional programs is due to using classical algorithms, which are
imperative in nature. It is a lot easier to re-implement an old
algorithm than it is to think up a new one in functional style. Ooge
de Moor have done good work in finding efficient fully functional
algorithms (in style as well as implementation) to classical problems,
e.g the knapsack problem.
Regarding the type checker in GHC, it would be interesting to
investigate efficient purely functional unification algorithms.
Torben Mogensen (tor...@diku.dk)
Torben AEgidius Mogensen
>On 6 Nov 1995 22:44:29 GMT, Graham Matthews <graham> wrote:
>>Someone wrote:
>>>0. You have to have side effects to be able to write a lot of algorithms
>>>efficiently.
>>
>>Are you sure about this?
>The one area I've seen in which a non-side-effecting style is
>dramatically weaker then a side-effecting one is circular data
>structures. There are many areas in which cyclic data structures are
>necessary, for instance generation of cyclic graphs in compiler
>optimization passes. As far as I know, there is no purely functional
>language in which one can implement explicitly circular data
>structures.
>Any opinions out there? I have relatively little experience in
>functional programming, so I may be wrong on some points. Am I right
>that it's impossible to create circular data structures without
>side-effects?
If you have a _lazy_ functional language, you can easily build a
circular data structure, e.g.
> ones = 1 : ones
which produces a circular list. This generalizes to arbitrary directed
graphs. There are, however, some restrictions to the use of such
graphs. Following edges is O(1), and by some fancy use of evaluation
order you can dynamically add edges (but this disallows testing for
existence of edges), but you can not remove edges. Essentially, the
modifications to the graph must be monotonic, and any non-instantiated
part is bottom, which means that any attempt at accessing/testing
non-instantiated parts will lead to "black holes".
Torben Mogensen (tor...@diku.dk)
Eric Jeschke
:On 6 Nov 1995 22:44:29 GMT, Graham Matthews <graham> wrote:
:>Someone wrote:
:>>0. You have to have side effects to be able to write a lot of algorithms
:>>efficiently.
:>
:>Are you sure about this?
:The one area I've seen in which a non-side-effecting style is
:dramatically weaker then a side-effecting one is circular data
:structures. There are many areas in which cyclic data structures are
:necessary, for instance generation of cyclic graphs in compiler
:optimization passes. As far as I know, there is no purely functional
:language in which one can implement explicitly circular data
:structures. A friend of mine implemented cyclic graphs in ML by using
:a lookup table to map from strings to nodes and representing edges as
:strings, but this strikes me as using explicit dereferencing to
:effectively get side-effects (creating a new table with a different
:association for a particular string effectively rebinds all edges to
:that node).
:Any opinions out there? I have relatively little experience in
:functional programming, so I may be wrong on some points. Am I right
:that it's impossible to create circular data structures without
:side-effects? Do functional programs which need circular data
:structures use explicit dereferencing, or use some other method of
:getting effectively circular data types, or avoid circular data types
:in the first place?
Circular references are trivial in lazy functional languages.
Perhaps I missed something in your post...
Juliusz Chroboczek
examples which need non-strict evaluation of function application, not
only lazy data structures?
J. Chroboczek
Henry Baker
set...@wrath.ugcs.caltech.edu (Seth M. LaForge) wrote:
> The one area I've seen in which a non-side-effecting style is
> dramatically weaker then a side-effecting one is circular data
> structures. There are many areas in which cyclic data structures are
> necessary, for instance generation of cyclic graphs in compiler
> optimization passes.
I'm curious as to how/why this is important in compiler optimization
passes.
---
You can also emulate cyclic structures in a 100% functional way using
Y-combinator techniques. Depending on how your system is implemented --
e.g., Turner's combinator reduction -- I believe that the Y combinator
stuff actually _becomes_ a real circular structure.
---
If you turn off the occur check in Prolog-type languages, you can program
with cyclic structures, and this is very closely related to 'functional'
data structures.
Henry Baker
Javier Sittler aka xentrac) wrote:
> (The reference [Baker78a] made me shudder a bit; I think dynamic
> scoping is an abomination! Using dynamic scoping and a reasonably
> complex APL function, you can redefine the functions the
> reasonably-complex function calls to make it do just about anything
> you want. Or, more likely, didn't want!)
Well, the interesting point of my paper was that this scheme which was
developed for one purpose (dynamic scoping), works for several other
different applications, as well -- e.g., functional array updates,
'state space' techniques for wind-unwind/unwind-protect stuff,
log-before/log-after database logs, etc.
So, even if you don't like dynamic scoping, you may still find the
technique useful for something else.
Lloyd Allison
>On 6 Nov 1995 22:44:29 GMT, Graham Matthews <graham> wrote:
>>Someone wrote:
>>>0. You have to have side effects to be able to write a lot of algorithms
>>>efficiently.
>>
>>Are you sure about this?
>The one area I've seen in which a non-side-effecting style is
>dramatically weaker then a side-effecting one is circular data
>structures. There are many areas in which cyclic data structures are
>necessary, for instance generation of cyclic graphs in compiler
>optimization passes. As far as I know, there is no purely functional
one can easily implement circular structures in non-strict FP,
just lookup circular program in
http://www.cs.monash.edu.au/~lloyd/tildeBIB/
Lloyd
Chris Okasaki
>...are there any well known good examples of functional
>implementations of algorithms which are typically implemented with
>cyclic data structures?
One common use of doubly-linked lists is to support constant-time
catenation for sequential structures. Two mechanisms for achieving the
same goal purely functionally have been proposed within the past year.
See
Haim Kaplan and Robert Tarjan
"Persistent Lists with Catenation via Recursive Slow-Down"
STOC'95, pages 93-102
and
Chris Okasaki
"Amortization, Lazy Evaluation, and Persistence: Lists with Catenation
via Lazy Linking"
FOCS'95, pages 646-654
http://foxnet.cs.cmu.edu/people/cokasaki/papers.html#catenation
Unfortunately, these data structures do not support several other common
uses of doubly-linked lists, such as splicing in or splicing out an element
from the middle of the sequence.
Chris
--
-------------------------------------------------------------------------------
| Chris Okasaki | Life is NOT a zero-sum game! |
| coka...@cs.cmu.edu | http://foxnet.cs.cmu.edu/people/cokasaki/home.html |
-------------------------------------------------------------------------------
Kragen Javier Sittler aka xentrac
Henry Baker <hba...@netcom.com> wrote:
>In article <486an7$g...@thelair.zynet.com>, k...@thelair.zynet.com (Kragen
>Javier Sittler aka xentrac) wrote:
>> (The reference [Baker78a] made me shudder a bit; I think dynamic
>> scoping is an abomination! Using dynamic scoping and a reasonably
>Well, the interesting point of my paper was that this scheme which was
Yes, I know; I was just going off on a wild tangent :)
--
Peace
Kragen
Exjobb - Arjan van Yzendoorn
>:The one area I've seen in which a non-side-effecting style is
>:dramatically weaker then a side-effecting one is circular data
>:structures.
And then Eric replied:
>Circular references are trivial in lazy functional languages.
>Perhaps I missed something in your post...
And this is what I have to say:
It is trivial to make circular references and data structures, but
the problem is UPDATING them. If, for example, you have a tree which
also has a 'reference' to its parent, then inserting a node would require
a complete rebuild of the tree. Here's that example:
-- a node contains its parent, a left subtree, a value and a right subtree
data Tree a = Node (Tree a) (Tree a) a (Tree a)
| Nil
a = Node Nil b 3 c
b = Node a Nil 4 Nil
c = Node a Nil 5 Nil
Now suppose you want to insert a new node (d) as the left child of c. This
would give you a new node c' with the value: Node a d 5 Nil. This means
that a has to be updated, because it stills refers to the 'old' c. In turn
this means that b has to be updated to reflect the fact that his parent
has changed. In short, one insert causes ALL the nodes to be updated.
There are (as far as I know) three ways to solve this:
a) simulate pointers using mutable arrays/vars which are available in
e.g. Gofer, Glasgow Haskell and Clean. In the first two language
you would have to use to IO monad and in the last a unique (and
thus destructively updatable) array.
b) rewrite your algorithm to work without cyclic data structures.
Sometimes rethinking a problem gives you a concise algorithm
which doesn't use them.
c) torture yourself by trying to write it in C. Give up after a
few hours of "segmentation violations" and "bus errors".
Enter a rehabilitation centre for "people who have seen too much
C on one day".
Greetings,
Arjan
Tommy Thorn
| It is trivial to make circular references and data structures, but
| the problem is UPDATING them.
..example deleted
| There are (as far as I know) three ways to solve this:
|
| a) simulate pointers ... in e.g. Gofer, Glasgow Haskell and Clean.
...
| b) rewrite your algorithm to work without cyclic data structures.
...
| c) torture yourself by trying to write it in C.
If you give up on b) the you might as well try a language with
pointer, but why be perverse and turn to C? SML seems to be a far
better alternative that both c) and a).
Talking about b), are there any well known good examples of functional
implementations of algorithms which are typically implemented with
cyclic data structures? The only example that I can think of right
now is register allocation through graph coloring.
Andrew Conway
|> ex-a...@mdstud.chalmers.se (Exjobb - Arjan van Yzendoorn) writes:
|> | It is trivial to make circular references and data structures, but
|> | the problem is UPDATING them.
|>
|> ..example deleted
|>
|> | There are (as far as I know) three ways to solve this:
|> |
|> | a) simulate pointers ... in e.g. Gofer, Glasgow Haskell and Clean.
|> ...
|> | b) rewrite your algorithm to work without cyclic data structures.
|> ...
|> | c) torture yourself by trying to write it in C.
|>
|> If you give up on b) the you might as well try a language with
|> pointer, but why be perverse and turn to C? SML seems to be a far
|> better alternative that both c) and a).
Agreed (though I use CAML rather than SML).
For those who don't know about ML, it is a language with a syntax
and feel very similar to modern functional languages. However, it
is not a "pure" language, and one can use pointers almost explicitly
if one wishes to. This makes it very easy to manipulate circular
data structures, while retaining the syntax and GC of a modern language.
The ability to manipulate circular data structures was my main reason
for choosing CAML.
Andrew.
Dara Gallagher
I don't know what you mean by realistic; but how about
(for pedagogical reasons):
> if_then_else :: bool -> * -> * -> *
> if_then_else True x y = x
> if_then_else False x y = y
> while :: (* -> bool) -> (* -> *) -> (* -> *)
> while c delta s_0 = while c delta (delta s_0), if c(s_0)
> = s_0, otherwise
I always argue that just about all useful languages have at
least one or two lazy constructs. Non-lazy languages either
a) don't allow the user to define lazy functions -- thus
there are two destinct classes of function in such
languages: strict user defined functions and possibly
lazy builtin functions. Obviously (I feel) this is an
undesirable complication in the semantics of the
languages as well as being restrictive; if the builtin
stuff doesn't provide exactly what you want, you can
be stuck.
b) provide kludgy "special forms" or macro preprocessing
to overcome the lack of general laziness. Again
I don't really appreciate these "extra-ordinary"
complications. Things can also get hairy and
unpredictable using these schemes -- for example
the subtle bugs caused by naive use of CPP's
`#define'; in this case you basically have to deal
with two vaguely seperate languages.
The fact that many strict languages are of type b) indicates
that the language designers forsaw "realistic" (i.e. practical)
uses for lazyness. Look at examples of the use of these special
forms or macros being used for non-inlining purposes in such
languages.
> J. Chroboczek
--
_______________________________________________________________
Dara Gallagher. http://www.cs.tcd.ie/www/jgllgher/jgllgher.html
---------------------------------------------------------------
Robert Harper
Mogensen) wrote:
> You have to give up on deleting nodes and edges, though. Also, you
> can't test on the existence of an edge. If it's there, no problem, but
> if it is not yet built, you get a black hole.
>
And yet people persist in pretending that lazy languages are useful and
important.
> Torben Mogensen (tor...@diku.dk)
Robert Harper
--
Robert Harper
Eric Jeschke
: While we're on the subject, could anyone post some realistic
:examples which need non-strict evaluation of function application, not
:only lazy data structures?
AFAIK, the two are interchangable; that is, if you have lazy data
structures you can get non-strict function application and vice versa.
I've been informed that a paper appeared about ten years ago that
delved into the semantic issues in the distinction. This may have
discussed some pathalogical programs that depended on the type of
laziness. I believe the paper is by Cartwright and Donahue, in either
POPL or LFP, about 10 years ago. Sorry I can't be more precise;
this is from secondhand information.
Seth M. LaForge
>In article <slrn4acul2...@wrath.ugcs.caltech.edu>,
>
>> The one area I've seen in which a non-side-effecting style is
>> dramatically weaker then a side-effecting one is circular data
>> necessary, for instance generation of cyclic graphs in compiler
>> optimization passes.
>
>passes.
For optimizers for traditional, imperative languages, for most
optimizations you need a control-flow graph. For instance, the
CFG for the following pseudo-C pseudo-assembly:
a = 0;
loop:
a += 1;
if (a < 10) goto loop;
...
would look like:
--> a = 0; -+-> a += 1; if (a < 10) goto loop; -+-> ...
\-------<---------<----------<------/
This is of course a circular data structure.
Global optimizations then involve post-order searches and such on the
resulting graphs. As far as I can tell, this stuff is impossible
without side-effects or an indirection table.
>You can also emulate cyclic structures in a 100% functional way using
>Y-combinator techniques. Depending on how your system is implemented --
>e.g., Turner's combinator reduction -- I believe that the Y combinator
>stuff actually _becomes_ a real circular structure.
Can you give an example of this? I'm intrigued... Is this reasonable
for real use?
>If you turn off the occur check in Prolog-type languages, you can program
>with cyclic structures, and this is very closely related to 'functional'
>data structures.
I've been meaning to learn a Prolog-derivative, but haven't had time.
CS classes eat way too much time...
Seth
A. Grant
>> a = Node Nil b 3 c
>> b = Node a Nil 4 Nil
>> c = Node a Nil 5 Nil
>I don't see any way to make a circular data structure purely
>functionally in ML, either. let a = ... and b = ... and c = ... in (a,b,c)
>doesn't work, probably for similar reasons as in Scheme.
How about
datatype node = a | b | c | Nil
Parent = fn a => Nil | b => a | c => a
Left = fn a => b | b => Nil | c => Nil
etc.
William D Clinger
set...@liquefy.ugcs.caltech.edu (Seth M. LaForge) writes:
>think of any way to make a circular data structure in the two
>functional languages I know, Scheme and SML....
Neither Scheme nor Standard ML is a purely functional language.
Both let you use side effects to create circular structures, just
as you would in any other imperative language.
>Can you show me the purely functional creation of a circular data
>structure in real code in a real language?
Haskell is just as real a language as Scheme or C. I think LaForge
is really asking for code in a language he happens to have seen before.
See below for Scheme code that illustrates the purely functional
creation of a circular data structure.
Arjan van Yzendoorn <ex-a...@mdstud.chalmers.se> gave an example
showing how to create circular data structures in a non-strict language
such as Haskell. LaForge wrote:
>I still don't see how it is trivial to make a circular data structure
>in a functional language. In most languages if you entered your above
>example, b and c would not be defined when a is defined....
Most languages aren't non-strict. To translate van Yzendoorn's example
into a strict language such as Scheme or Standard ML, you need to add
some explicit lambda expressions and procedures calls:
--------
; Each tree node consists of its parent, a left subtree, a value,
; and a right subtree.
; SICP (Abelson & Sussman) message-passing style.
; Each argument to make-tree is a thunk (a procedure of no arguments).
(define (make-tree parent left value right)
(lambda (message)
(case message
((parent) (parent))
((left) (left))
((right) (right))
((value) (value))
(else (error "Undefined operation on a tree")))))
(define (tree.parent tree) (tree 'parent))
(define (tree.left tree) (tree 'left))
(define (tree.right tree) (tree 'right))
(define (tree.value tree) (tree 'value))
; Example.
(letrec ((a (make-tree (lambda () #f)
(lambda () b)
(lambda () 3)
(lambda () c)))
(b (make-tree (lambda () a)
(lambda () #f)
(lambda () 4)
(lambda () #f)))
(c (make-tree (lambda () a)
(lambda () #f)
(lambda () 5)
(lambda () #f))))
(+ (tree.value (tree.parent b))
(tree.value (tree.left a))
(tree.value (tree.right a))))
--------
In a non-strict language, the explicit lambda expressions and procedure
calls aren't necessary.
th...@drogo.irisa.fr (Tommy Thorn) used the words "lazy" and "eager",
which describe particular evaluation strategies. Roughly speaking, a
"lazy" implementation of a non-strict language never evaluates anything
it doesn't have to, and furthermore it never evaluates anything more than
once.
This is accomplished by "memoizing" the expressions that got translated
into explicit lambda expressions in the Scheme code above. The "delay"
and "force" mechanisms of R4RS Scheme are a crude way to approximate a
lazy implementation.
William D Clinger
rej
In article <slrn4akurm...@liquefy.ugcs.caltech.edu>,
Seth M. LaForge <set...@liquefy.ugcs.caltech.edu> wrote:
>>
>> -- a node contains its parent, a left subtree, a value and a right subtree
>> data Tree a = Node (Tree a) (Tree a) a (Tree a)
>> | Nil
>>
>> b = Node a Nil 4 Nil
>> c = Node a Nil 5 Nil
>
>in a functional language. In most languages if you entered your above
>example, b and c would not be defined when a is defined.
...stuff deleted...
>functional languages I know, Scheme and SML. In Scheme,
>Can you show me the purely functional creation of a circular data
>structure in real code in a real language?
>
>Seth
>
The example you quote is real code in a real language that creates a
circular data structure purely functionally. The language is Haskell (or
gofer, the syntax is the same). Change the type declaration to
tree * ::= Node (tree *) (tree *) * (tree *) | Nil
and you have it in Miranda.
Richard Jones
===============================================================================
Computing Laboratory Room SW107
University of Kent at Canterbury Telephone: 01227 764000 ext.7943
Canterbury, 01227 827943 (direct)
CT2 7NF, U.K. FAX: 01227 762811
===============================================================================
OVLINGER Johan
: As a simple example, how can I implement an ordered list with
: following properties in languages without side-effects?
: * There should be no upper bound on the number of items in the list.
: * All items must be enumerated in O(N) time where N is the number of
: items in the list.
: * Insertion or removal of items to/from the list should be performed
: in constant time.
: In languages such as C, Lisp, etc. we can use doubly-linked list to
: implement the data structure specified above. I don't know how to do
: it in FP language (I'm not an experienced FP programmer; I write
: programs mainly in Lisp and C++). I'd like to hear from gurus.
I don't see (excuse my ignorance if the answer is staring me in the face)
how you can get constant update time for ANY implementation of a linked
list. Admittedly, in a functional language, you pay twice, once to find
the node, once to rebuild the list, (three times, if you count the stack,
for a naive implementation) but the order of complexity is the same.
With fancy algorithms and data structures, you can mimick list behaviour
in a balanced tree for O(log n), but I don't see how to achieve constant
time updates, even WITH destructive update.
The double linked aspect is problematic in FP, as someone has already
pointed out. The whole data strucure becomes 'monolithic' and has to be
copied en-masse unless it can be proved (difficult) that there is only
one reference to it. O(n) is the logical result for ANY update. One
way around this is to emulate a heap and pointers, but this is silly-
we could also just emulate a turing machine in all languages and write
compilers to it from all languages- it's possible, but not attractive.
But then, I'm not a guru.
regards,
johan
James McCartney
wrote:
> With fancy algorithms and data structures, you can mimick list behaviour
> in a balanced tree for O(log n), but I don't see how to achieve constant
> time updates, even WITH destructive update.
you are already pointing to the element you want to change. Then it
IS constant time, you just have 4 pointers to update.
--- james mccartney ja...@astro.as.utexas.edu
Paul E. Bennett
> One
> way around this is to emulate a heap and pointers, but this is silly-
> we could also just emulate a turing machine in all languages and write
> compilers to it from all languages- it's possible, but not attractive.
>
> But then, I'm not a guru.
>
>
I'm not a Guru as far as functional languages go either. My main language is
Forth which I use for just about everything, including hardware simulations. I
follow this group quite a bit as it holds some interest and monitoring it I see
where some of my Formal Methods advocating colleagues are trying to aim. I have
already had one person involved in the dissemination of Haskell and Gofer agree
that Forth is sort of halfway between fully imperative and functional languages.
The above idea of having a Turing Machine emulated in all languages is not a
bad idea. I will still maintain that Turings Machine is a simpler device than
the Von-Neuman architectured machines and it's derivatives. Perhaps you guys
don't have to look too far for such a machine that embodies the basics of a
Turing Machine and these could probably be found in Stack Oriented Computers.
With a Forth planted on top and the functional language of choice layered above
we could be getting somewhere. Perhaps the result could also pass Turing's Test.
--
Paul E. Bennett
(p...@transcontech.co.uk)
Going Forth Safely
Seth M. LaForge
>In this discussion, functional == lazy. Scheme and SML are eager.
>Eager languages have no problem with side effects.
How can you define functional as lazy? My understanding of the matter
is that there are two issues: functional vs. imperative
languages/styles and eager vs. lazy languages/styles. There is
certainly such a thing as a functional eager program, right?
Do other people have different meanings for these words?
>| Can you show me the purely functional creation of a circular data
>| structure in real code in a real language?
>
>Are you implying that Haskell is not a "real" language?
No, I wasn't implying anything. I meant "real language" as opposed to
"pseudocode". If the posted example was Haskell code, my apologies -
I thought it was pseudocode. If it was Haskell code, I'd like to
know.
Seth
Eric Jeschke
:On 16 Nov 1995 16:19:23 +0100, Tommy Thorn <th...@drogo.irisa.fr> wrote:
:>In this discussion, functional == lazy. Scheme and SML are eager.
:>Eager languages have no problem with side effects.
:How can you define functional as lazy? My understanding of the matter
:is that there are two issues: functional vs. imperative
:languages/styles and eager vs. lazy languages/styles. There is
:certainly such a thing as a functional eager program, right?
:Do other people have different meanings for these words?
These buzzwords are so overloaded as to be nearly useless.
Clinger rightly points out that "lazy" and "eager" are implementation
adjectives, while "strict" and "non-strict" are semantic adjectives.
I'm particularly disappointed that the term "eager" is used by some
(erroneously, IMO) as synonymous with "strict". "eager" simply means that
some expressions may be evaluated "eagerly" (I believe the term decended
from the expression "eager-beaver"). Thus, "eager" can imply concurrent
speculative computation, for example. Provided you reclaim
useless speculative computations, YOU CAN HAVE AN EAGER FUNCTIONAL
LANGUAGE THAT IS NON-STRICT.
Similarly, the term "lazy" does not exactly mean "non-strict",
but there is less room for confusion, because all lazy languages (that
I know about, at least) _are_ non-strict (by virtue of laziness).
However, the converse might not be true, depending on how broadly you
cast your definition of "lazy" in implementation terms.
I won't even attempt to detangle "functional" vs. "non-functional" vs.
"imperative".
Oleg Moroz
wrote:
> > You have to give up on deleting nodes and edges, though. Also, you
> > can't test on the existence of an edge. If it's there, no problem, but
> > if it is not yet built, you get a black hole.
> >
>
> And yet people persist in pretending that lazy languages are useful and
> important.
>
That's not the feature of lazy language, that's the feature of the
technique used in the implementation cited. You can implement
those graph algorithms in many different styles, and here's what
lazy languages give you: the possibility of choosing from many
more programming styles and techniques than strict (and impure)
languages EASILY. E.g. you can model many impure (and imperative)
features in lazy functional languages via monads, but when you
want to use lazy evaluation (or preserver referential integrity) in
strict (or imperative) language, you should apply a substantial
amount of work to buld the evaluation model (or constantly watch
whether you are writing only allowed operations on your data).
> Robert Harper
>
Oleg
Seth M. LaForge
>In article <slrn4akurm...@liquefy.ugcs.caltech.edu>
>set...@liquefy.ugcs.caltech.edu (Seth M. LaForge) writes:
>> ...I can't
>>think of any way to make a circular data structure in the two
>>functional languages I know, Scheme and SML....
>
>Neither Scheme nor Standard ML is a purely functional language.
>Both let you use side effects to create circular structures, just
>as you would in any other imperative language.
Sorry for not being explicit, I meant in a functional subset of Scheme
or SML.
>>Can you show me the purely functional creation of a circular data
>>structure in real code in a real language?
>
>Haskell is just as real a language as Scheme or C. I think LaForge
>is really asking for code in a language he happens to have seen before.
Sorry, I didn't realize that it was Haskell code. At the time that I
originally posted, I wasn't thinking about lazy evaluation. I'll
definitely have to check out a lazy language when I have some free
time (not this term, anyway...).
>Most languages aren't non-strict. To translate van Yzendoorn's example
>into a strict language such as Scheme or Standard ML, you need to add
>some explicit lambda expressions and procedures calls:
In this context, what does strict mean? Is this another word for
lazy?
Overall, so far it seems to me that every scheme for creating circular
datastructures in without side-effect involve some type of
indirection, through lazy evaluation, functions, or explicit tables,
lazy evaluation being basically implicit functions.
From a practical rather than theoretical point of view, how do
circular data structures tend to be represented in CPU-intensive
programs in the different categories of functional languages? I'd
guess that the best examples would be compilers, since compilers tend
to need circular data structures of some type, and since most
languages seem to have at least one compiler written in the language.
What techniques tend to win the generality/usability/efficiency/memory
usage tradeoffs? My guess would be that indirection tables and side
effects, where available, probably tend to win out, but I'd like to
hear about counterexamples.
Seth
MAEDA Atusi
MAEDA Atusi (m...@math.keio.ac.jp) wrote:
: As a simple example, how can I implement an ordered list with
: following properties in languages without side-effects?
: * There should be no upper bound on the number of items in the list.
: * All items must be enumerated in O(N) time where N is the number of
: items in the list.
: * Insertion or removal of items to/from the list should be performed
: in constant time.
: In languages such as C, Lisp, etc. we can use doubly-linked list to
: implement the data structure specified above. I don't know how to do
: it in FP language (I'm not an experienced FP programmer; I write
: programs mainly in Lisp and C++). I'd like to hear from gurus.
johan> I don't see (excuse my ignorance if the answer is staring me in the face)
johan> how you can get constant update time for ANY implementation of a linked
johan> list. Admittedly, in a functional language, you pay twice, once to find
johan> the node, once to rebuild the list, (three times, if you count the stack,
johan> for a naive implementation) but the order of complexity is the same.
johan> With fancy algorithms and data structures, you can mimick list behaviour
johan> in a balanced tree for O(log n), but I don't see how to achieve constant
johan> time updates, even WITH destructive update.
Hmmm. You're including time to search node by some index in list, or
by some id for node. I didn't mean that. Sorry for ambiguities.
In C, nodes in graphs or lists are typically identified by pointer to
it. That is, insertion or removal of nodes have prototypes such as:
void insert_node_after(Node* prev, Node* n); /* insert n after prev */
void remove_node(Node*);
and these takes O(1) time each.
You seem to think we *must* perform search before remove/insert nodes,
but it is not true. And this can make essential difference in
complexity. For example, consider linear time algorithm to calculate
Euler path of a graph. There's no need for linear search whatsoever
(if written in C, Lisp, etc.) except for initial step (to find start
node).
johan> The double linked aspect is problematic in FP, as someone has already
johan> pointed out. The whole data strucure becomes 'monolithic' and has to be
johan> copied en-masse unless it can be proved (difficult) that there is only
johan> one reference to it. O(n) is the logical result for ANY update. One
johan> way around this is to emulate a heap and pointers, but this is silly-
johan> we could also just emulate a turing machine in all languages and write
johan> compilers to it from all languages- it's possible, but not attractive.
A person responded me in email and recomended following papers:
"Graph Algorithms in a Lazy Functional Programming Language",
Kashiwagi, Y. and Wise D. S.,
ftp://ftp.cs.indiana.edu/pub/dswise/GraphDoc3.ps.Z
"Lazy Depth-First Search and Linear Graph Algorithms in Haskell",
King, D. J., Launchbury, J.,
ftp://ftp.dcs.glasgow.ac.uk/pub/glasgow-fp/tech-reports/
FP-94-_?_?_lazy-depth-first-search.ps.Z
The first uses recursive equation approach which Torben Mogensen
described in this newsgroup (<48cjf8$p...@odin.diku.dk>).
The latter uses monadic approach using State Thread (which seems to me
equivalent to unique arrays).
And now I vaguely feel that it is possible to remove/insert node in
doubly-linked lists in FP language. We represent path by an array of
size N (N is the size of the graph). Elements of the array is triple
(Node, PrevIndex, NextIndex) where PrevIndex and NextIndex are indices
of previous and next node, respectively. By using indices instead of
pointers we pretend these structures are uniquely referenced so that
we can destructively update them.
Yes, it's not attractive, as you said. It's not flexible in size. It
requires O(N) initialization time (true?). It forces imperative
programming style. But now I think insertion/removal can certainly be
done in constant time in pure FP language.
;;; Keio University
;;; Faculty of Science and Technology
;;; Department of Math
;;; MAEDA Atusi (In Japan we write our family names first.)
;;; m...@math.keio.ac.jp
Dr S B Jones (Staff)
> From: m...@math.keio.ac.jp (MAEDA Atusi)
>
> It is true that you can easily *create* graph structures in lazy
> functional languages but *modifying* them looks hard to me.
>
> <snip>
>
> These can be done in constant time in imperative languages by
> destructive update of pointers.
>
> From: ex-a...@mdstud.chalmers.se (Exjobb - Arjan van Yzendoorn)
>
> It is trivial to make circular references and data structures, but
> the problem is UPDATING them. If, for example, you have a tree which
> also has a 'reference' to its parent, then inserting a node would require
> a complete rebuild of the tree.
>
Hang on. Let's be sure we're comparing like with like.
Imperatively:
In an imperative program, we usually work with the explicit plan
that linked graph structures are single threaded - that is we *intend*
that updates are seen by all who refer to the structure. So updates are
usually efficient for TWO reasons:
o the required destructive update mechanism exists in the language
o the common update is the effect required
If, on the other hand, a `what if' modification were to be made to the
graph for some purpose, and we wished to retain the option to return to an
earlier state of the graph later. Aside from keeping one or more
reversible record of update transactions (yeuch), a natural way to achieve
that is to set up a new pointer to the graph and to ensure that the pointed
to graph is immutable --- and the only way to guarantee this is to make a
(probably expensive) copy!
Now consider the analogous functional situation:
The semantics guarantees us of the immutability of shared values, which is
exactly what we desire and require in functional programming. Where values
become shared (eg `what if' analysis, as above), and one or more sharers
need to update their copies, then the updates are usually expensive,
because they imply copying to protect other sharers' values against change
- as most critical posts so far have taken delight in pointing out (tho' we
can envisage implementation techniques that avoid complete copies). But, in
fact there is no difference here from the imperative case: if you need
immutable shared copies then you are involved in expense.
On the other hand, if, in the functional context, we have a graph
representation that is used *single threadedly* (ie no shared occurrences
arise that must be updated independently) through a program, then there
is no barrier in principle to performing cheap destructive updates to the
structure (if only we can work out the mechanism to do this in practice).
(This is exactly the same argument as is used to justify other destructive
update mechanisms.) Again, there is no difference from the imperative case.
Finally, if we have a functional analogue of an imperative algorithm, then
presumably the graph structures will be used single threadedly *by intent*
so naturally we will fall into the "On the other hand" functional case
above.
Overall: exactly where is this intrinsic difference between imperative and
functional that I have been reading about??
Of course, there remains the question of whether there is, for example, a
general graph representation mechanism for functional programs that allows
constant time destructive updates. Given the availability of true arrays,
and destructive updates for arrays used single threadedly, the graph
representation issue looks as if it should present no problem in principle
(just some "simple coding details" and a neat module to hide the inner
workings). I haven't worked through the details, but I guess that someone
has.
Simon
--
Dr Simon B Jones
Dept of Computing Science
and Mathematics | Email: s...@cs.stir.ac.uk
University of Stirling | URL: http://www.cs.stir.ac.uk/~sbj
Stirling | Tel: (UK) 01786 467434 (Int) +44 1786 467434
SCOTLAND FK9 4LA | Fax: .... 464551 ....... 464551
Randolph Bentson
Eric Jeschke <jes...@cs.indiana.edu> wrote:
>Clinger rightly points out that "lazy" and "eager" are implementation
>adjectives, while "strict" and "non-strict" are semantic adjectives.
>
>I'm particularly disappointed that the term "eager" is used by some
>(erroneously, IMO) as synonymous with "strict". "eager" simply means that
>some expressions may be evaluated "eagerly" (I believe the term decended
>from the expression "eager-beaver"). Thus, "eager" can imply concurrent
>speculative computation, for example. Provided you reclaim
>useless speculative computations, YOU CAN HAVE AN EAGER FUNCTIONAL
>LANGUAGE THAT IS NON-STRICT.
Lazy evaluation is so closely associated with non-strict functions
that it is often thought of as the antonym to strictness. One can
see that this is not so when one looks at parallel evaluation
schemes.
In "Functional implementation of non-strict functional programming
languages" (MIT Press, 1990), Kenneth R. Traub calls non-strict
non-lazy evaluation schemes "lenient". This is slightly different
from non-strict eager as I believe the latter implies evaluation
of terms _will_ take place, whereas the former only says evaluation
of terms _may_ take place. In either case, the evaluations may
be discarded before they are used (or even completed) if they are
unneeded. In any case, non-strict semantics still imply that an
unused term cannot effect a function's value.
Randolph Bentson
ben...@grieg.seaslug.org
Bert Thompson
>set...@liquefy.ugcs.caltech.edu (Seth M. LaForge) writes:
>| > data Tree a = Node (Tree a) (Tree a) a (Tree a)
>| > | Nil
>| >
>| > a = Node Nil b 3 c
>| > b = Node a Nil 4 Nil
>| > c = Node a Nil 5 Nil
>|
>| I still don't see how it is trivial to make a circular data structure
>| in a functional language. In most languages if you entered your above
>| example, b and c would not be defined when a is defined. I can't
>| think of any way to make a circular data structure in the two
>| functional languages I know, Scheme and SML. In Scheme,
>In this discussion, functional == lazy. Scheme and SML are eager.
>Eager languages have no problem with side effects.
``Smells like Red Herring''
Eagerness and side-effects are orthogonal issues. There -are-
lazy languages that support side-effects in a disciplined way (and
others that do in a undisciplined way!).
Have a look at the programming language `Forsythe' by
Reynolds. This is a lazy procedural language inspired
by Algol-60.
For that matter, the Haskell work on state monads solves many of
the problems of maintaining equational semantics with
stateful computations.
I suspect having first-class graph structures rather
than tree-structures (which is what algebraic datatypes really are)
would solve many of the problems. Andrew Tanenbaum invented
a language (Orca?) that does support exactly this. (It's not
functional though.)
Bert
---------------------------------------------------------------------------
Bert Thompson a...@cs.mu.oz.au
---------------------------------------------------------------------------
Fergus Henderson
> I'm joining this discussion late, so if I say something over again,
> sorry in advance. The concept of "imperative style functional programs"
> intrigues me. What exactly do you mean by it?
I mean pure functional programs that thread a global state throughout
the entire computation (or perhaps a small number of states threaded
through large parts of the computation), and which relies heavily on
the implementation being able to implement modifications to that state
(or those states) using destructive update.
> If you refer to
> conciseness, well, then I can see it, because an iterative Sisal loop
> with in-place array updates is probably less concise than the shortest
> recursive formulation you could write.
One of the advantages of functional programming that you lose is
parallelizability.
Conciseness is another advantage that you may lose. Alternatively, you
may choose to keep conciceness by using some syntactic sugar, but in
that case you lose some of the nice properties such as order
independence. Another alternative is the Monad approach - use
higher-order functions and simple infix operators for your syntactic
sugar. In that case, you pay a small program complexity cost as the
types in your program become quite complicated. (These alternatives
are probably quite worthwhile, since conciseness is very important.)
> I also don't
> see how such a loop loses the other advantages of functional
> programming, such as formal analyzability, etc.
If there is a single state threaded through the computation,
formal analysis does become more difficult, because even though
the formal framework is there, the problems you have to solve
with it are less tractable.
(If formal analysis wasn't more difficult for imperative style
functional programs, then formal analysis would be easy for imperative
programs too - just transform them into imperative style functional
programs first - so formal analysis wouldn't be an advantage of
functional programs.)
> Personally, I think
> Sisal is one place where the imperative and functional worlds are being
> squeezed together, and the layer of interface between them is being
> made slim and clean.
I agree. Sisal was one of the projects I was thinking of when I said
"... much work has been and is being done on this". But I don't think Sisal
address all parts of the problem.
--
Fergus Henderson WWW: http://www.cs.mu.oz.au/~fjh
f...@cs.mu.oz.au PGP: finger f...@128.250.37.3
Oleg Moroz
wrote:
>
> Conversely, when programming in a lazy language, I must constantly
> worry about where to put the proper pattern matching or other
> mechanism to force delayed computation so that I don't have to worry
> about space and time problems. Reasoning about intensional properties
> is just as important as reasoning about extensional equivalence.
> Also, I have to worry about where to put the strict annotations, the
> unboxing annotations, etc., all of which destroy the supposed
> advantages of lazy computation (i.e., all-singing, all-dancing
> reasoning about equational properties of my language, which I can't
> prove anyway because of small details like non-termination. See
> Pfenning's previous post on this subject.)
>
Yes, I understand your point here, but I consider this the property of
(most) existing implementations of lazy functional languages, not
languages themselves or lazy computation model. Good compiler or
development system should apply global optimizations to your program
when generating production code and these should include total
strictness analysis etc. Strictness annotations are supposed to guide
today's compilers in this process. Unboxing annotations are analogous
in that they should be used only on low-level (system-level) data
structures such as primitive data types and system calls in standard
library (say, prelude in Haskell). Future systems should infer the
optimal (boxed or unboxed) representations of data types from the
global program analysis.
You can say that's a wonderful dream & nothing more and you'll be
absolutely right from the today's practical point of view - functional
languages' implementations just haven't reached the industrial
strength point - sigh !
Oleg
Richard A. O'Keefe
> And yet people persist in pretending that lazy languages are useful and
> important.
It is possible to have a lazy language with destructive updates.
Existence proof: Clean. (I have a copy running on my Macintosh right now.
Cool. Really cool. I could do with a bit more tutorial on the new IO
system though.) In fact Clean manages to legitimate destructive updates
precisely by virtue of is graph rewriting semantics; it has a non-ad-hoc
definition of when there is a single reference to a value. Uniqueness
annotations on types permit the compiler generate destructive operations.
The Mercury language is a logic programming language with uniqueness
annotations that are enforced by the compiler. Like Clean, it exploits
that to provide simple readable I/O (there is a unique "world" that IO
updates). Like Clean, the intent is to support destructive update, though
in release 0.4 (the latest I have) that's not yet implemented. Control
flow is driven by data flow, but it's not non-strict.
Uniqueness annotations are not a new idea. (A closely related idea is
"compile time reference counting".)
--
"conventional orthography is ... a near optimal system for the
lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
Mark Jones
>Conversely, when programming in a lazy language, I must constantly
>worry about where to put the proper pattern matching or other
>mechanism to force delayed computation so that I don't have to worry
>about space and time problems.
In sharp contrast to your constant worry, I can honestly say that
I rarely give such things *any* consideration when I program in a
lazy language. My performance as a programmer is often much more
important than the performance of the systems on which I execute
my programs; my worries have more to do with the search for clear
and concise ways to solve particular problems.
Concerns about space and time are concerns about optimization, and
I do not dismiss the importance of that. But productivity is often
more important to me, and correctness must surely be the ultimate goal.
>Also, I have to worry about where to put the strict annotations, the
>unboxing annotations, etc., all of which destroy the supposed
>advantages of lazy computation
Again, I do not share your worries; after all, the lazy languages
that I use most of the time *do not even support these features*.
You have doubtless seen these things described in research papers
that present techniques used in particular implementations as a
way to express optimizations or to record the results of program
analysis. And of course, some ideas -- boxing and unboxing, for
example -- are important in the implementation of both strict and
non-strict languages. But such features are rarely included or
used as everyday programming tools.
All the best,
Mark
Michael Froehlich
> > the problem is UPDATING them. If, for example, you have a tree which
> > also has a 'reference' to its parent, then inserting a node would require
> > a complete rebuild of the tree.
> >
> representation that is used *single threadedly* (ie no shared occurrences
> arise that must be updated independently) through a program, then there
> is no barrier in principle to performing cheap destructive updates to the
> structure (if only we can work out the mechanism to do this in practice).
> Of course, there remains the question of whether there is, for example, a
> general graph representation mechanism for functional programs that allows
> constant time destructive updates. Given the availability of true arrays,
> and destructive updates for arrays used single threadedly, the graph
> representation issue looks as if it should present no problem in principle
> (just some "simple coding details" and a neat module to hide the inner
> workings). I haven't worked through the details, but I guess that someone
> has.
Right, in daVinci we're using this approach for many years. daVinci is an
interactive graph visualization system, written in the *pure* and strict
functional language ASpecT (which is translated to C). I can guarantee
that daVinci is efficent, runs like hell and is even much faster than some
compeditors written in imperative languages. :-) More information about
daVinci in WWW: http://www.Informatik.Uni-Bremen.DE/~davinci
Properly used (i.e. single threadedly), ASpecT arrays are as efficient as
imperative ones, because in fact they are C-arrays after the ASpecT
compiler has finished. Of course, when you work with a former version of
an array (i.e. multi threaded use), the the array is copied and you've
lost efficiency. Access to arrays looks like this in ASpecT:
NewArray = (OldArray,Index) := Data.
/* stores data at index (= integer) in an array by
using the (_,_):=_ operator. */
Data = Array!Index.
/* gets the data of an array stored at index by
using the _!_ operator. */
The internal graph data structure of daVinci supports doublely linked
nodes. From a simple point of view, each node has an integer ID which is
the index of the graph array. The value of this array is a node data type
which includes two ID-lists for the parents and childs of a node, among
other things. So destructive updates are done in constant time.
Michael
--
_ _ __ __
| | || | | Dipl.-Inform. Michael Froehlich
| | || | | University of Bremen - FB3 Computer Science
| | ||_ |__| Bremen Institute for Safe and Secure Systems
| | || |\ PO-Box 330440, D-28334 Bremen, Germany
| | || | \ e-mail: m...@Informatik.Uni-Bremen.DE
| | || | \ WWW: http://www.Informatik.Uni-Bremen.DE/~mfr
Dara Gallagher
> Eagerness and side-effects are orthogonal issues. There -are-
> lazy languages that support side-effects in a disciplined way (and
> others that do in a undisciplined way!).
Sure. The problem lies in trying to analyse programs written in such
languages; it is more difficult to see the order of evaluation in a
lazy language. Hence it is difficult to predict the order in which
the side effects will take place (in a lazy side-effecting language).
For example; with a strict language you know that the argument in a
function application will be evaluated before the application is
reduced. Therefore it is trivial to see that in "f(g(x))" the side
effects of g have to take place before those of f; with a lazy
language this may or may not be the case depending on definitions of
f and g. This dependancy is likely to be a source of subtle bugs
and unexpected behaviour.
The combination of lazyness and side effects is not impossible but
seems to give you many of the disadvantages of both approaches with
precious few advantages.
> Have a look at the programming language `Forsythe' by
> Reynolds. This is a lazy procedural language inspired
> by Algol-60.
> For that matter, the Haskell work on state monads solves many of
> the problems of maintaining equational semantics with
> stateful computations.
> I suspect having first-class graph structures rather
> than tree-structures (which is what algebraic datatypes really are)
> would solve many of the problems. Andrew Tanenbaum invented
> a language (Orca?) that does support exactly this. (It's not
> functional though.)
> Bert
> ---------------------------------------------------------------------------
> Bert Thompson a...@cs.mu.oz.au
> ---------------------------------------------------------------------------
Bert THOMPSON
|On Wed, 15 Nov 1995 07:57:05 -0500, r...@cs.cmu.edu (Robert Harper) wrote:
|> And yet people persist in pretending that lazy languages are useful and
|> important.
|It is possible to have a lazy language with destructive updates.
|Existence proof: Clean. (I have a copy running on my Macintosh right now.
|Cool. Really cool. I could do with a bit more tutorial on the new IO
|system though.)
You might want to look at the Clean book:
Functional Programming and Parallel Graph Rewriting,
Plasmeijer and van Eekelen
There're also lots of references at Nijmegen Uni:
http://www.cs.kun.nl/~clean/Clean.Papers.html#i/o
I found this paper to be a good overview :
ftp://ftp.cs.kun.nl/pub/Clean/papers/beauty.ps.Z
Have fun!
Bert.
---------------------------------------------------------------------------
Bert Thompson a...@cs.mu.oz.au
"This sentence is true."
---------------------------------------------------------------------------
[3]- Segmentation fault (core dumped)
C Wright
> > Conversely, when programming in a lazy language,
> > I must constantly>worry about where to put the
> > proper pattern matching or other mechanism to
> > force delayed computation so that I don't have
> > to worry about space and time problems.
>
> In sharp contrast to your constant worry, I can
> honestly say that I rarely give such things *any*
> consideration when I program in a lazy language.
> My performance as a programmer is often much more
> important than the performance of the systems on
> which I execute my programs;
As a commercial programmer I have to worry about
* implementation time
* correctness
* ease of maintenance
* cost of hardware
* efficient execution
(time and space)
* consistency of execution time
* predictability of behaviour
Writing in a lazy functional language gives me about
three out of seven. Writing in C gives me size our of
seven. Guess which I choose.
If my programmes are quick to write, correct and easy
to maintain, but then require virtual memory and take
unpredictable amounts of time to run, I get no money
at all, because I can't meet the specifications. My
code needs to run on small systems in real time.
Suggest to me a language? When will lazy functional
languages be practical in the real world?
Don't get me wrong, I desperately want to use these
theoretically elegant and seductive ideas/languages,
but I need to get paid for my programmes.
Dr C.D. Wright,
personal opinions only.
C Wright
> > There -are- lazy languages that support side-effects
>
> Sure. The problem lies in trying to analyse programs
> written in such languages; it is more difficult to see
> the order of evaluation in a lazy language. Hence it is
> difficult to predict the order in which the side effects
> will take place (in a lazy side-effecting language).
I don't understand this. If the order is important, why
not define a list whose elements in some sense are required
side-effects, in order. Then they can be read off and
effected in the right order. In other words, stream the
required side-effects through a sequencing list, or even
through a poset that expresses the required dependencies.
This is what I do - what have I missed?
Fergus Henderson
>Incidentally, can anyone tell me which existing functional language
>implementations do offer true arrays with destructive update?
I got a few email replies, and did a little bit of research of my own,
and here's what I've come up with. The following table includes
only pure (referentially transparent) functional languages.
The perhaps idiosyncratic headings reflect what I consider to be important.
Destructive update of Guaranteed Natural Compiler
System Arrays Trees Graphs performance style inference
------ ------ ----- ------ ----------- ------- -------
Haskell YES NO NO? YES NO NO
(monads)
Clean YES N.Y.I. NO YES YES YES
(unique types)
SISAL YES NO NO NO YES YES
(optimizer)
ReWrite ? YES NO? YES YES N/A
(linear types [only!])
"N.Y.I." means Not Yet Implemented.
"Haskell" means any of several Haskell implementions.
By "Destructive update of Arrays" I mean that the system provides
an array type which has constant time access and update, for at least
some updates.
By "Destructive update of Trees" I really mean applying destructive update
to user-defined data types.
By "Destructive update of Graphs" I mean that the system provides
a way of creating and destructively updating cyclic data structures,
and also that unreachable nodes are garbage collected. (If it were
not for that caveat, graphs could be implemented using arrays.)
"Guaranteed performance" means that there is a way for the programmer
to be sure that they will get destructive update for a particular data
structure (i.e. the compiler can be made to issue an error or warning
if they write code which would require copying.)
"Natural style" means that the programmer doesn't have to jump
through too many hoops to get destructive update - that the compiler
can perform destructive update for ordinary style code, if it happens
to be single-threaded (though the compiler might need some hints
in the form of special declarations, etc.)
This column is there to emphasize the disadvantages of monads ;-)
"Compiler inference" means that the system is capable of performing
destructive update on code written in a natural style without any help
from the programmer.
I would like to use a system which had a YES in every column. The
system I'm working on at the moment, Mercury, should have a YES under
every column except "Compiler inference" sometime in the not too
distant future.
Destructive update of Guaranteed Natural Compiler
System Arrays Trees Graphs performance style inference
------ ------ ----- ------ ----------- ------- -------
Mercury N.Y.I. N.Y.I. N.Y.I. YES YES NO
(unique modes)
If anyone can fill in any of the question marks in the table above,
or has any entries to add to this list, or any corrections to make,
please let me know.
--
Fergus Henderson WWW: http://www.cs.mu.oz.au/~fjh
f...@cs.mu.oz.au PGP: finger f...@128.250.37.3
I will have little or no net access from Nov 30 until Dec 25.
Please email me a copy of any follow-ups.
CB. Dornan
: In article <48spg0$l...@cantaloupe.srv.cs.cmu.edu> jgmo...@cs.cmu.edu (Greg Morrisett) writes:
: >Conversely, when programming in a lazy language, I must constantly
: >worry about where to put the proper pattern matching or other
: >mechanism to force delayed computation so that I don't have to worry
: >about space and time problems.
: In sharp contrast to your constant worry, I can honestly say that
: I rarely give such things *any* consideration when I program in a
: lazy language. My performance as a programmer is often much more
: important than the performance of the systems on which I execute
: my programs; my worries have more to do with the search for clear
: and concise ways to solve particular problems.
Indeed. My own experience of programming with the various lazy functional
compilers is similar:
* programming in Haskell/Miranda(tm)/LML (and no doubt in Clean) is fun
and rewarding;
* reuse of techniques and code is extensive;
* lazy functional programs scale well, it being possible to construct,
maintain and alter non-trivial programs in ways that could only be
dreamt about in a weakly typed, less declarative programming language
such as C;
* the latest compilers (especially, in my experience, the Glasgow
Haskell Compiler) provide excellent facilities for calling existing C
libraries;
* performance is becoming less and less of a problem, most applications
being quite feasible with one of the Haskell optimising compilers
running on an up-market home computer (i.e., a top-loaded PC running
Linux).
In general I aim to produce a maximally correct program with the least effort
that meets a given performance threshold. Increasingly, lazy functional
compilers allow me to meet the performance criteria without compromising my
confidence in the correctness of the program I am writing or the amount of
effort it takes.
By the way, I found the recent discussion of the merits of lazy functional
programming -- cyclic data structures, etc., -- baffling and difficult to
relate to my own experience of lazy functional programming.
I have to say that I cannot be impressed by ML programmers that claim that they
fail to program Haskell effectively. Programming in a non-strict functional
language requires practice and technique just as programming in Lisp, Standard
ML, Prolog, FP or C. I personally find Prolog difficult to work with because I
find it so hard to leave behind my Haskell baggage; I know many Prolog
programmers that make effective use of Prolog but likewise find Haskell
difficult. Surely the fact that there is a significant and growing research
community that does make effective use of lazy functional programming makes a
more compelling indication of its potential usefulness.
If the aim is really to understand the rationale and motivation for lazy
functional programming then I would recommend one of the standard works on the
topic, particularly the Bird and Wadler textbook and Hughes' `Why Functional
Programming Matters' (references appended). It is hardly feasible to distill
this material in a usenet article.
Cheers,
Chris Dornan dor...@compsci.bristol.ac.uk
Department of Computer Science
University of Bristol +44 117 9289000 x 3676
@BOOK{bird-wadler,
author = "R. Bird and P. Wadler",
title = "Introduction to Functional Programming",
series = "Prentice Hall International Series in Computer Science"
publisher = "Prentice Hall",
year = 1988 }
@INCOLLECTION{hughes,
author = "J. Hughes",
title = "Why Functional Programming Matters",
chapter = 2,
pages = "17-42",
crossref = "rtfp" }
@BOOK{rtfp,
editor = "D. A. Turner",
title = "Research Topics in Functional Programming",
booktitle = "Research Topics in Functional Programming",
series = "UT Year of Programming Series",
publisher = "Addison-Wesley",
Year = 1990 }
Greg Morrisett
CB. Dornan <dor...@cs.bris.ac.uk> wrote:
> * programming in Haskell/Miranda(tm)/LML (and no doubt in Clean) is fun
> and rewarding;
>
> * reuse of techniques and code is extensive;
>
> * lazy functional programs scale well, it being possible to construct,
> maintain and alter non-trivial programs in ways that could only be
> dreamt about in a weakly typed, less declarative programming language
> such as C;
>
> * the latest compilers (especially, in my experience, the Glasgow
> Haskell Compiler) provide excellent facilities for calling existing C
> libraries;
>
> * performance is becoming less and less of a problem, most applications
> being quite feasible with one of the Haskell optimising compilers
> running on an up-market home computer (i.e., a top-loaded PC running
> Linux).
IMHO, all of these good points hold for SML, CAML, Caml Special Light, etc.
So the question remains as to why _lazy_ functional languages are a
win over these languages. In fact, as far as building large systems,
I would claim that languages like SML and CSL have a serious leg up
with their advanced module systems.
>I have to say that I cannot be impressed by ML programmers that claim that they
>fail to program Haskell effectively. Programming in a non-strict functional
>language requires practice and technique just as programming in Lisp, Standard
>ML, Prolog, FP or C. I personally find Prolog difficult to work with because I
>find it so hard to leave behind my Haskell baggage; I know many Prolog
>programmers that make effective use of Prolog but likewise find Haskell
>difficult. Surely the fact that there is a significant and growing research
>community that does make effective use of lazy functional programming makes a
>more compelling indication of its potential usefulness.
Good point. But as I claimed earlier, the reports of problems in
both space and time come from the lazy language literature (i.e.,
check out the "experience" papers in the last couple of FPCA proceedings.)
So, while I may not be able to program in Haskell effectively,
apparently, neither could these people, without resorting to
"strict" annotations and the like.
>If the aim is really to understand the rationale and motivation for lazy
>functional programming then I would recommend one of the standard works on the
>topic, particularly the Bird and Wadler textbook and Hughes' `Why Functional
>Programming Matters' (references appended). It is hardly feasible to distill
>this material in a usenet article.
Having read these references, I can still say that I am baffled
as to why full laziness is considered a virtue.
-Greg
rej
C Wright <cd...@cix.compulink.co.uk> wrote:
>As a commercial programmer I have to worry about
> * implementation time
> * correctness
> * ease of maintenance
> * cost of hardware
> * efficient execution
> (time and space)
> * consistency of execution time
> * predictability of behaviour
>
>Writing in a lazy functional language gives me about
>three out of seven. Writing in C gives me size our of
>seven. Guess which I choose.
But at least writing in a lazy functional language gives correct
output!!
Sorry, couldn't resist.
Bryan O'Sullivan
> Well, it does on the types of systems I have to use,
> precisely because it takes so long to get functional
> programs to run in sufficiently little memory, time
> and predictably. See the next point too.
I find it interesting that all of your responses are simply special
pleading. That you, personally, are willing to go through unusual
contortions in order to get things working as you would wish
demonstrates little of value, other than that such contortions are
possible.
<b
--
Let us pray:
What a Great System.
Please Do Not Crash. b...@eng.sun.com
^G^IP@P6 b...@serpentine.com
Andrew Conway
|> [ Comment about not worrying about space/time from Mark Jones ]
|> As a commercial programmer I have to worry about
|>
|> * implementation time
|> * correctness
|> * ease of maintenance
|> * cost of hardware
|> * efficient execution
|> (time and space)
|> * consistency of execution time
|> * predictability of behaviour
|>
|> [ C gives me most of these; lazy functional languages don't. I
|> would like to use a lazy functional langauge, but it seems wrong
|> pragmatically. ]
I have had the same seven worries (plus the eighth of being able to do
anything if I really want to).
I have found ML to be a very good compromise. It is not lazy,
unfortunately, and in many ways has the same program structure as C
for a given program. However, it has a functional syntax and feel,
making it (in my opinion) much nicer to use.
I use Caml special light (a dialect of ML) and find that it is small
and fast and I can recommend it to people who are finding it hard to
break the C habit.
Notwithstanding that, I sometimes wish it was lazy, and I am avidly
reading this newsgroup waiting for a lazy language that has "YES"
under all of Fergus Henderson's recent survey headings. But in the
mean time ML fits my needs nicely.
Andrew Conway.
David SHERMAN
> Overall, so far it seems to me that every scheme for creating circular
> datastructures in without side-effect involve some type of
> indirection, through lazy evaluation, functions, or explicit tables,
> lazy evaluation being basically implicit functions.
Well, I think we have to be careful about what we call a circular data
structure. Do we mean that the chain of pointers in the run-time heap
has a cycle, or do we mean that the user can't tell that there isn't
one?
I'm not being facetious. In an equational program, when I write
structure[X] = cons[X; structure[X]]
what happens? As far as I can tell by inspecting this structure, it
is circular. Of course the system might not be very clever, and unwind
the structure in the heap, but I have no way of knowing that.
The whole idea is that a circular structure in the heap is just an
efficient way of representing an infinite structure. The user is only
interested in the fact that the semantics is the same (and, I suppose,
that the machine doesn't crash too soon).
Run-time detection of sharing opportunities is, as you note, the usual
way to let the system be clever about such structures. Hashed cons
(Spitzen and Levitt, 1978), directed congruence closure (Chew, 1981),
lazy memo functions (Hughes, 1985), lazy directed congruence closure
(me, 1994), and so on.
But why couldn't a static analysis in the compiler handle the example
above? There might still be what you call an indirection somewhere,
but it seems to me that it wouldn't involve any run-time overhead.
--
djs David J. Sherman (da...@LaBRI.U-Bordeaux.FR)
Laboratoire Bordelais de Recherche en Informatique
...and also the use of double reeds. Now, many composers have written for
double reeds, but P.D.Q. Bach is the only one I know to do so without the
use of oboes and bassoons. --Peter Schickele, /Iphigenia in Brooklyn/
MAEDA Atusi
In article <490sev$5...@goanna.cs.rmit.EDU.AU> o...@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:
ok> On Wed, 15 Nov 1995 07:57:05 -0500, r...@cs.cmu.edu (Robert Harper) wrote:
>> And yet people persist in pretending that lazy languages are useful and
>> important.
ok> It is possible to have a lazy language with destructive updates.
ok> Existence proof: Clean. (I have a copy running on my Macintosh right now.
ok> Cool. Really cool. I could do with a bit more tutorial on the new IO
ok> system though.) In fact Clean manages to legitimate destructive updates
ok> precisely by virtue of is graph rewriting semantics; it has a non-ad-hoc
ok> definition of when there is a single reference to a value. Uniqueness
ok> annotations on types permit the compiler generate destructive operations.
Uniqueness annotations of Clean is surely nice. But there's one
irritating thing. Cyclic data are never referenced uniquely by
definition. You can handle it by using unique arrays and indices
instead of (something like) tuples of form (label, prev, next), but it
is not as a direct solution as desirable.
--mad
C Wright
<49e394$o...@shellx.best.com>
> cd...@cix.compulink.co.uk ("C Wright") writes:
>
> > Well, it does on the types of systems I have to use,
> > precisely because it takes so long to get functional
> > programs to run in sufficiently little memory, time
> > and predictably. See the next point too.
>
> I find it interesting that all of your responses are
> simply special pleading. That you, personally, are
> willing to go through unusual contortions in order to
> get things working as you would wish demonstrates
> little of value, other than that such contortions are
> possible.
I don't actually understand here what you're trying to
say. Let me state my position.
* I program to make money.
* I sell special systems to specific
customers who have particular requirements.
* I would greatly prefer to write in a
functional language.
* No functional languages I know of will run
on hardware that the customer will buy.
My initial response was to the following exchange.
> > Conversely, when programming in a lazy language,
> > I must constantly worry about where to put the
> > proper pattern matching or other mechanism to
> > force delayed computation so that I don't have
> > to worry about space and time problems.
> In sharp contrast to your constant worry, I can
> honestly say that I rarely give such things *any*
> consideration when I program in a lazy language.
I was simply pointing out that _some_ of us in the
real world find his attitude irrelevant.
CB. Dornan
: In article <DIp6y...@uns.bris.ac.uk>,
: CB. Dornan <dor...@cs.bris.ac.uk> wrote:
: But as I claimed earlier, the reports of problems in
: both space and time come from the lazy language literature (i.e.,
: check out the "experience" papers in the last couple of FPCA proceedings.)
: So, while I may not be able to program in Haskell effectively,
: apparently, neither could these people, without resorting to
: "strict" annotations and the like.
Laziness clearly has a cost (though it can avoid redundant computation too)
but, in my experience, it is nothing like the problem that some people claim it
to be. In any case, there is bound to be investigations into further reducing
its cost -- that is how we have arrived at the current happy situation where
lazy functional programming is a practical propostion for a wide variety of
applications. [BTW, I have no problem with `adding strictness' to a
lazy functional program, just as I would be prepared to lift computation out of
loops at key places in a C program.]
Incidentally, it is my impression that there is really not that much difference
between code-improving Standard ML compilers and code-improving Haskell
compilers in terms of the sort of resources required by the programs they
produce -- much less than an order of magnitude for instance.
: Having read these references, I can still say that I am baffled
: as to why full laziness is considered a virtue.
Surely this is the key to this discussion. If you don't buy the basic thesis
then, of course, lazy functional programming is going to make no sense at all.
However, to many people it does make sense and I cannot see how anyone could
reasonably expect to `undo' that through discussion.
Robert Harper
a...@labri.u-bordeaux.fr (Andrew Conway) wrote:
> Notwithstanding that, I sometimes wish it was lazy, and I am avidly
WHY?
>
> Andrew Conway.
RH
--
Robert Harper
Richard A. O'Keefe
>Uniqueness annotations of Clean is surely nice. But there's one
>irritating thing. Cyclic data are never referenced uniquely by
>definition. You can handle it by using unique arrays and indices
>instead of (something like) tuples of form (label, prev, next), but it
>is not as a direct solution as desirable.
I think the thread may be cyclic as well as the data.
Clean and Mercury don't give you a _direct_ representation of cyclic data.
I'm actually happy about that, because I think _directly_ cyclic data are
Evil. I was never happy about the fact that Prolog's unification
algorithm was unsound according to the standard theory of equality, and
I regard the non-standard theory of equality that was developed so that
some Prolog people could pretend the bug was a "feature" called rational
trees as being nearly as bad as the bug it tried to paper over. One of
the things I love about Mercury is that its unification is sound according
to the standard theory of equality.
Large numbers of other people disagree.
Andrew Conway
|> In article <49c26n$j...@serveur.cribx1.u-bordeaux.fr>,
|> a...@labri.u-bordeaux.fr (Andrew Conway) wrote:
|>
|> > Notwithstanding that, I sometimes wish it was lazy, and I am avidly
|>
|> WHY?
"I use eager languages, and I can't see why anyone would want to use
lazy languages" or those saying "I use lazy languages and I like
them."
Well, I use (and like) eager languages, but occasionally I have
constructs that could be done more nicely in a lazy language. For
instance, sometimes I may want to say something like
if condition1 then f(x)
else if condition 2 then 2*f(x)
else 4.3
Now, it would be nice to extract the calculation of f(x) so that
it didn't have to be repeated, but without causing it to be calculated
if not needed. Of course there are 73 ways to do this in an eager
language, but none are _quite_ as nice as with a lazy language.
I realise that this it quite a trivial example; but I have several
times had such situations. Of course, explicit lazy annotations could
be almost as easy to use.
As mentioned lots of times before, lazy lists and similar
datastructures are often very useful and I have had to implement
work-arounds equivalent to them in order to get some algorithms to
work effectively. Again, lazy data structures are easy to do in an
eager language, but they ARE easier to do in a lazy language.
Now comes the big point.
In my view (looking towards the distant future), lazy languages may
well turn out to be implemented VERY well by compilers, which can work
out what should be evaluated eagerly themselves most of the time. In
this situation, there would be no reason not to use a lazy language
unless you wanted side effects (which I often do, but I realise that
most of the time they could be avoided). Looking hopefully into the
future again, I see side effect free languages being reasoned about
much more effectively by compilers, producing better optimisations. I
see this sort of thing starting to happen, and I see lazy languages as
the future. Look at the strictness annotations of Clean and Fergus
Henderson's vision of Mercury for a start to this process.
I view the "strict" constructs of today as similar to "register"
constructs of the past. Sometime the compilers may get good enough to
ignore them and make their own (better) choices.
In the present, however, I still use a very nice eager language (CSL) for most
tasks, as I believe that it is the most appropriate FOR ME at this time.
At the moment, I believe that strictness annotations are too clumsy
and that carrying state around is too unpleasant, but these things are
improving.
Andrew Conway.
Greg Morrisett
Andrew Conway <a...@labri.u-bordeaux.fr> wrote:
>As mentioned lots of times before, lazy lists and similar
>datastructures are often very useful and I have had to implement
>work-arounds equivalent to them in order to get some algorithms to
>work effectively. Again, lazy data structures are easy to do in an
>eager language, but they ARE easier to do in a lazy language.
...just as depth-first backtracking search can be easier in
Prolog. I'm not discounting lazy evaluation as a useful
programming technique. I'm discounting the idea that all
evaluation, indeed the default evaluation strategy, should
be lazy. I'm all for convenient notation to express lazy
computations. But, if I rarely need backtracking search
as an evaluation strategy, and I rarely need lazy evaluation
as an evaluation strategy, then I don't want it to be the
default.
>I view the "strict" constructs of today as similar to "register"
>constructs of the past. Sometime the compilers may get good enough to
>ignore them and make their own (better) choices.
I would buy this if any compiler in the world were looking
towards turning any strict computations into lazy computations.
If we used languages where strict constructs were the default,
then I would view the "delay/force" constructs as similar to "register"
constructs -- the compiler may well ignore the programmer,
perform strictness analysis on the lazy constructs, and decide
that it is more profitable to use a strict construct.
>In my view (looking towards the distant future), lazy languages may
>well turn out to be implemented VERY well by compilers, which can work
>out what should be evaluated eagerly themselves most of the time.
I am very sure that in the short run, lazy languages will be left
in the dust in terms of performance. In part, this is because
every compiler for a lazy language that I'm aware of, translates
the source language to an intermediate form that uses eager
evaluation and makes laziness explicit. Then, an analysis is
performed to detect when it is possible to turn functions and
data structures into strict constructs. Rarely is an analysis
performed to determine whether doing so is profitable -- because
it almost always is. Compilers for strict languages can skip
this whole first step and work on the next set of issues.
In the long run, the only hope that non-strict evaluation has is in
parallelism. I'm actually quite dubious that this will pay off.
Currently, the economics of the situation show that, even for
non-strict languages like Id, the problem is that there is way
too much parallelism at the wrong level of granularity -- it's
not at the instruction level, nor at the task level, but rather
at the procedural level. The overheads of synchronization, task
start up, and task and memory management simply outweight the benefits
right now, and I actually suspect this will hold for quite a long while.
However, I don't discount it entirely.
In contrast, languages with explicit concurrency constructs (e.g.,
CML) hold a decent chance of taking advantage of shared memory
multiprocessors for the next few years, because the level of
granulariy matches the architectures. Languages with data parallelism
constructs (e.g., NESL), will rule at the vector/super-computer level.
So, you might be right -- in the very long term, lazy evaluation
might hold some promise, and we should never forget that. However,
I find it very interesting that languages with task-level and
data-level parallelism map well onto stock hardware as well as
more exotic hardware, while lazy languages, IMHO, map well onto
no existing hardware, be it sequential or parallel. Certainly
this is a good topic for research -- but keep in mind that a lot
of really smart people who worked on dataflow architectures for the
past 20 years are now looking at much more conventional hardware
and programming languages. The promise of "free" parallelism
just never materialized.
All the best,
-Greg
Peter Ludemann
Clean and Mercury don't give you a _direct_ representation of cyclic data.
I'm actually happy about that, because I think _directly_ cyclic data are
Evil. I was never happy about the fact that Prolog's unification
algorithm was unsound according to the standard theory of equality, and
I regard the non-standard theory of equality that was developed so that
some Prolog people could pretend the bug was a "feature" called rational
trees as being nearly as bad as the bug it tried to paper over. One of
the things I love about Mercury is that its unification is sound according
to the standard theory of equality.
Just because something is non-standard doesn't mean it's bad ... in
Physics, the theory of relativity was non-standard for a long time;
and it's not really needed unless you move at near-light speeds or are
in strong gravity fields.
"Rational trees" can be considered the data equivalent of the
fixed-point theorems for recursive programs. That is, if you
define a data structure by:
x = cons(1, x)
then the rational tree theory tells you that the data structure exists
(the standard equality theories don't allow such structures).
I agree with Richard that rational trees don't seem very useful.
I've only seen one use of rational trees, in representing an
interepreter. That is, if we have a program like:
f(x) = if (x > 0) then x * f(x-1) else 1
we can represent it in a straightforward manner by something like:
f1 = function(f, lambda([x], if(gt(x,0), times(x, apply(f1, sub(x,1), 1)))))
and the interpreter for processing this is pretty simple.
However, this representation turns out to be not very useful as soon
as we want to do loop analysis and other clever things with the
program's definition, and we're forced to go back to an indirect
representation of the program's cycles; the interpreter needs only
minor changes to deal with that (for those worried about efficiency,
looking up an indirection can be the same O(1) that pointer following
is, although the constant factor is larger).
--
Peter Ludemann lude...@expernet.com
ExperNet phone: +1.408.327.4339 (+1.415.949.8691)
Systems Architect fax: +1.415.949.1395
KNS Project Leader 3945 Freedom Circle,
Suite 240, Santa Clara CA 95054
CB. Dornan
[...]
: I am very sure that in the short run, lazy languages will be left
: in the dust in terms of performance.
Can we have some data to back this up? I don't doubt that eager languages
generally run faster than lazy languages but `in the dust'?
From the point of view of compiler writers, who typically spend their time
squeezing fractions of a percentage out of the system, the performance
differences between strict and lazy languages are going to look quite large.
However, from the perspective of the application programmer, so much has been
paid to use an eager functional language (instead of Fortran or C) that the
extra cost of a lazy language probably won't be very significant (assuming that
a lazy language is considered desirable, of course).
As compilation techniques improve and languages become more mixed (in the
lazy/eager sense), will it not become increasingly difficult to tell the
difference between lazy and eager languages?
Andrew Conway
jgmo...@cs.cmu.edu (Greg Morrisett) writes:
|> In article <49mnui$f...@serveur.cribx1.u-bordeaux.fr>,
|> Andrew Conway <a...@labri.u-bordeaux.fr> wrote:
|> > [ Lazy evaluation is sometimes slightly more convenient ]
obtained the reply
> [ The slight is very slight ]
Agreed that it is very slight...but my claim is that some time there
will be no or very little overhead, and there will be no reason not to
use lazy languages, and slight reason to do so.
|> >I view the "strict" constructs of today as similar to "register"
|> >constructs of the past. Sometime the compilers may get good enough to
|> >ignore them and make their own (better) choices.
|>
|> I would buy this if any compiler in the world were looking
|> towards turning any strict computations into lazy computations.
One could argue that "dead code elimination" is a step in this
direction. Lazy evaluation is basically dynamic dead code elimination.
|> [ other comments removed. ]
Andrew Conway.
P.S. Future hardware may well include hardware support for garbage
collection and for lazy constructs in the same way that it now
provides support for caches, parallelism and virtual memory. Maybe it
never will...I am not all that good at predicting the future. There
has been little reason to do so in the present as the market wasn't
there. Still, one could have said the same thing about caches,
parallelism and virtual memory in the PC market 20 years ago.
Greg Morrisett
CB. Dornan <dor...@cs.bris.ac.uk> wrote:
>Greg Morrisett (jgmo...@cs.cmu.edu) wrote:
>
>[...]
>
>: I am very sure that in the short run, lazy languages will be left
>: in the dust in terms of performance.
>
>Can we have some data to back this up? I don't doubt that eager languages
>generally run faster than lazy languages but `in the dust'?
Well, recent advances in, for instance, representation analysis
show upwards of a 42% reduction in allocation and a 33% reduction
in running times. (See Shao & Appel's paper in L&FP '95). These
techniques do not apply to lazy languages, because unboxing drags
strictness along with it, if only because you need a "box" to
represent a thunk. See also the recent work of Robert Sansom,
Simon Peyton Jones and others in the Glasgow group along these lines.
Hardly "fractions of percentages".
>As compilation techniques improve and languages become more mixed (in the
>lazy/eager sense), will it not become increasingly difficult to tell the
>difference between lazy and eager languages?
As more languages provide an option, programmers will pick and choose
those constructs that are really needed, instead of having an uneeded
default foisted upon them. Compiler writers will continue to optimize
the cases that really matter and arise in practice. Further,
programmers will cease to use constructs that buy them nothing and
cost them in performance. So, I fully expect to see some uses of lazy
datatypes, but I also fully expect to see compiler writers ignoring
them and concentrating on the real issues.
-Greg
Stephen
Andrew Conway <a...@labri.u-bordeaux.fr> wrote:
>In article <49sqop$7...@cantaloupe.srv.cs.cmu.edu>,
>jgmo...@cs.cmu.edu (Greg Morrisett) writes:
>
>|> In article <49mnui$f...@serveur.cribx1.u-bordeaux.fr>,
>|> Andrew Conway <a...@labri.u-bordeaux.fr> wrote:
>
>
>|> >I view the "strict" constructs of today as similar to "register"
>|> >constructs of the past. Sometime the compilers may get good enough to
>|> >ignore them and make their own (better) choices.
>|>
>|> I would buy this if any compiler in the world were looking
>|> towards turning any strict computations into lazy computations.
>
You have made a very basic mistake here! What we need to realize is that
it is wrong to look at programs written for a strict language, and see where
lazyness might be helpful. (I remember somebody's sarcastic comment a long
time ago that 'lazyness' was devised for the one in ten-thousand situation
where it might improve the running time of a program.)
People who program in strict languages naturally use a style of programming
which _works_ in such a language. There are alternative ways of writing a
functional program which might, as a practical matter, only work in a lazy
language.
One simple example would be a chess playing program. It is possible, in a
lazy programming language, to write a function which describes the entire
tree of possible moves in a chess game. It is also possible to write a
program which will, based on some input (of the opponents moves), will
selectively search the tree to determine the computer's next move.
Thus, you have a chess playing program, but the function which describes
the tree of possible chess moves is distinct from the function that knows
how to respond to the opponent's moves (by selectively searching the game
tree); it is even possible that the game playing component could be a
generic module not written specificaly for chess.
My main point here is that lazy languages allow programs to be written
in different styles compared to strict languages.
- Steve Pipkin
Robert Harper
number of techniques. Lazy languages don't help here (or anywhere).
RH
--
Robert Harper
Greg Morrisett
Eric Jeschke <jes...@cs.indiana.edu> wrote:
>At the cost of tweaking the code to figure out where to put your
>parallel annotations. This is on par with tweaking lazy code with
>strictness annotations. i.e. you do it if you have to for performance
>reasons. Plus synchronization primitives, critical sections, etc.
>(if you have side effects).
But the dataflow people found that they were putting annotations
all over the place to turn all of the "free parallelism" back into
sequential code that would run decently. Same with futures, promises,
let*, etc.
The point is that we've failed so far in our bid to automatically
parallelize sequential code _or_ sequentialize parallel code --
both are hard problems and both are important.
-Greg
Eric Jeschke
:In the long run, the only hope that non-strict evaluation has is in
:parallelism. I'm actually quite dubious that this will pay off.
:Currently, the economics of the situation show that, even for
:non-strict languages like Id, the problem is that there is way
:too much parallelism at the wrong level of granularity -- it's
:not at the instruction level, nor at the task level, but rather
:at the procedural level. The overheads of synchronization, task
:start up, and task and memory management simply outweight the benefits
:right now, and I actually suspect this will hold for quite a long while.
:However, I don't discount it entirely.
Of course this has been the holy grail of functional languages
and I agree that there is a fundamental granularity mismatch on
conventional architectures. In short, we're not there yet.
I think it is important to note, however, that in a lower-level sense,
non-strict evaluation provides automated process management. In the
future, APM may come to be viewed in the same positive light that
automated storage management is today. After all, parallel programming
cruft is as bad (if not worse) than explicit memory management cruft.
:In contrast, languages with explicit concurrency constructs (e.g.,
:CML) hold a decent chance of taking advantage of shared memory
:multiprocessors for the next few years, because the level of
:granulariy matches the architectures. Languages with data parallelism
:constructs (e.g., NESL), will rule at the vector/super-computer level.
At the cost of tweaking the code to figure out where to put your
parallel annotations. This is on par with tweaking lazy code with
strictness annotations. i.e. you do it if you have to for performance
reasons. Plus synchronization primitives, critical sections, etc.
(if you have side effects).
--
Eric Jeschke
jes...@cs.indiana.edu
Robert Harper
(Exjobb - Arjan van Yzendoorn) wrote:
> Suppose I write:
>
> process = filter (>10000)
> . map computeSalary
>
> and I would apply this to a big list; would a strict language
> first compute ALL the salaries and only then filter out the ones
> higher than 10000 ? (and thus use much more memory). This is
> the case in C; I would like to hear if this also holds for (say) ML.
>
No, it would not, provided that you used a stream rather than a list.
RH
--
Robert Harper
CB. Dornan
: >Can we have some data to back this up? I don't doubt that eager languages
: >generally run faster than lazy languages but `in the dust'?
: Well, recent advances in, for instance, representation analysis
: show upwards of a 42% reduction in allocation and a 33% reduction
: in running times. (See Shao & Appel's paper in L&FP '95). These
: techniques do not apply to lazy languages, because unboxing drags
: strictness along with it, if only because you need a "box" to
: represent a thunk. See also the recent work of Robert Sansom,
: Simon Peyton Jones and others in the Glasgow group along these lines.
: Hardly "fractions of percentages".
There have also been recent advances in the compilation of lazy functional
languages involving transformations that may well prove difficult to apply to
SML. I would still be interested in a proper analysis of the overall
performance of (say) SML/NJ and GHC so that a serious comparison can be made
between the compilers.
Exjobb - Arjan van Yzendoorn
Robert Harper wrote:
>You can just as easily write that chess program in, say, ML using any
>number of techniques. Lazy languages don't help here (or anywhere).
I've never used a strict language (apart from C :-) and I would
like to know something about them.
Suppose I write:
process = filter (>10000)
. map computeSalary
and I would apply this to a big list; would a strict language
first compute ALL the salaries and only then filter out the ones
higher than 10000 ? (and thus use much more memory). This is
the case in C; I would like to hear if this also holds for (say) ML.
If so, I don't understand how anybody could say that lazy languages
don't help. I often (read: always) write code like this and I wouldn't
want to think about the enormous 'space leaks' I could get in a strict
language. Merging the two phases (is that what Robert Harper means with
"using any number of techniques"?) would loose modularity and lead to
a low-level programming style.
Please correct me if I'm wrong.
Regards,
Arjan
Shin-Cheng Mu
: In article <4a6cnq$n...@nyheter.chalmers.se>, ex-a...@mdstud.chalmers.se
: (Exjobb - Arjan van Yzendoorn) wrote:
: > process = filter (>10000)
: > . map computeSalary
: > and I would apply this to a big list; would a strict language
: > first compute ALL the salaries and only then filter out the ones
: > higher than 10000 ? (and thus use much more memory). This is
: > the case in C; I would like to hear if this also holds for (say) ML.
I suppose the 'stream' here to be either a non-strict data structure
non-uniformly provided by the strict language, or a home-made
lazy list with which all the tedious details of delayed evalutaion
have to be manupulated by programmer's hand.
--
To iterate is human; to recurse, divine.
,--------------------- ------------- -------- ----- --- -- - -
| Shin-Cheng Mu Computer Information Science, NCTU, Taiwan
| u812...@cc.nctu.edu.tw http://140.113.23.51/~is81033
`----------
Thomas Johnsson
Steve Pipkin wrote:
:: One simple example would be a chess playing program. It is possible, in a
:: tree of possible moves in a chess game. It is also possible to write a
:: program which will, based on some input (of the opponents moves), will
:: selectively search the tree to determine the computer's next move.
to which Bob Harper replied:
: You can just as easily write that chess program in, say, ML using any
: number of techniques. Lazy languages don't help here (or anywhere).
Bob,
I'd be very curious as to how you, as an experienced SML programmer,
would structure this in a strict functional language?
Give us some for-instances please.
-- Thomas
--
Thomas Johnsson
email:john...@cs.chalmers.se www:http://cs.chalmers.se/~johnsson
Dept. of CS, Chalmers University of Technology, S-412 96 Goteborg, Sweden
phone: dept: +46 (0)31 7721088.
Jan Krynicky
r...@cs.cmu.edu says...
>
>In article <4a6cnq$n...@nyheter.chalmers.se>,
ex-a...@mdstud.chalmers.se
>(Exjobb - Arjan van Yzendoorn) wrote:
>
>> Suppose I write:
>>
>> process = filter (>10000)
>> . map computeSalary
>>
>> and I would apply this to a big list; would a strict language
>> first compute ALL the salaries and only then filter out the ones
>> higher than 10000 ? (and thus use much more memory). This is
>> the case in C; I would like to hear if this also holds for (say) ML.
>>
>
>No, it would not, provided that you used a stream rather than a list.
>
And simulate the lazy lists that way ;-)
Jenda
MAEDA Atusi
In article <rwh-071295...@harper-eth.fox.cs.cmu.edu> r...@cs.cmu.edu (Robert Harper) writes:
rwh> In article <4a6cnq$n...@nyheter.chalmers.se>, ex-a...@mdstud.chalmers.se
rwh> (Exjobb - Arjan van Yzendoorn) wrote:
ex-arjan> Suppose I write:
ex-arjan>
ex-arjan> process = filter (>10000)
ex-arjan> . map computeSalary
ex-arjan>
ex-arjan> and I would apply this to a big list; would a strict language
ex-arjan> first compute ALL the salaries and only then filter out the ones
ex-arjan> higher than 10000 ? (and thus use much more memory). This is
ex-arjan> the case in C; I would like to hear if this also holds for (say) ML.
ex-arjan>
rwh> No, it would not, provided that you used a stream rather than a list.
Space requirement tends to be more problematic in lazy languages.
Programs written in lazy languages sometimes require extra spaces
which is not obvious to programmer. (E.g. CAFs, tail-recursive
functions which don't run in bounded space, etc. See Peyton Jones'
book, chapter 23 for details.)
Compiler can remove (some of) these hidden inefficiency via strictness
analysis. Actually, lazy languages rely heavily on strictness
analysis to obtain acceptable (both time- and space-) efficiency.
Most (if not all) compilers' document recommend to write programs so
that compiler can infer its strictness for efficency. But still,
there exists some cases that compiler fails to prove strictness and
needs pragma to be added by hand (that's why forthcoming Haskel 1.3
includes strictness annotation into standard, I believe).
Given all these, and given the fact that we need laziness in only few
cases (and in that cases programmer should know she needs it), I think
"strict evaluation by default, plus optional laziness" is the easier
policy to write program with (at least for now).
--mad