Benchmarking Lazy Functional Languages

25 views
Skip to first unread message

Kenneth Cheng-Lim Seah

unread,
Oct 15, 1995, 3:00:00 AM10/15/95
to

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

unread,
Oct 22, 1995, 3:00:00 AM10/22/95
to

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.
>
>maybe the following is of interest for you:
> 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

unread,
Oct 25, 1995, 3:00:00 AM10/25/95
to
In article <1995Oct24.1...@news.cs.indiana.edu>, "Eric Jeschke"
<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

unread,
Nov 6, 1995, 3:00:00 AM11/6/95
to
In article <47m34d$5...@manuel.anu.edu.au> Graham Matthews <graham> writes:

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

unread,
Nov 6, 1995, 3:00:00 AM11/6/95
to
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.

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

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to

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

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
In article <47sth0$l...@odin.diku.dk>, tor...@diku.dk (Torben AEgidius
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

unread,
Nov 9, 1995, 3:00:00 AM11/9/95
to
Graham Matthews <graham> writes:

>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

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
In article <47sth0$l...@odin.diku.dk> tor...@diku.dk (Torben AEgidius Mogensen) writes:

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

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
hba...@netcom.com (Henry Baker) writes:

: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

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to
Please excuse the flame but ....

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

unread,
Nov 10, 1995, 3:00:00 AM11/10/95
to

In article <47sth0$l...@odin.diku.dk>, tor...@diku.dk (Torben AEgidius Mogensen)
writes:
|>
|> 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.

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

unread,
Nov 11, 1995, 3:00:00 AM11/11/95
to
John Feo (f...@llnl.gov) wrote:

> 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

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
tor...@diku.dk (Torben AEgidius Mogensen) writes:

>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

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
In article <953170...@mulga.cs.mu.OZ.AU>,

Fergus Henderson <f...@munta.cs.mu.OZ.AU> wrote:
>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.
>
>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

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
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?

Seth


Graham Matthews

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
con...@cs.mu.OZ.AU (Thomas Charles CONWAY) writes:
>>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

unread,
Nov 12, 1995, 3:00:00 AM11/12/95
to
In article <47ve2l$5...@odin.diku.dk>,
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
>>Mogensen) wrote:
>
>>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

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to
In article <485mia$3...@boogie.cs.utexas.edu>,

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.)
>
In fairness, there was a 5-fold improvement from the use of non-idempotent
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

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to
wil...@cs.utexas.edu (Paul Wilson) writes:

>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

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to
set...@wrath.ugcs.caltech.edu (Seth M. LaForge) writes:

>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

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to
set...@wrath.ugcs.caltech.edu (Seth M. LaForge) writes:

: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

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to 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?

J. Chroboczek

Henry Baker

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to
In article <slrn4acul2...@wrath.ugcs.caltech.edu>,

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

unread,
Nov 13, 1995, 3:00:00 AM11/13/95
to
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
> 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

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
set...@wrath.ugcs.caltech.edu (Seth M. LaForge) writes:

>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

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
Tommy Thorn <th...@goldmund.irisa.fr> wrote:
>...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

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
In article <hbaker-1311...@10.0.2.15>,

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

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
Graham 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.

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

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
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).

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

unread,
Nov 14, 1995, 3:00:00 AM11/14/95
to
In article <wlf7n13...@goldmund.irisa.fr>, th...@goldmund.irisa.fr (Tommy Thorn) writes:
|> 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

unread,
Nov 15, 1995, 3:00:00 AM11/15/95
to

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

unread,
Nov 15, 1995, 3:00:00 AM11/15/95
to
In article <48cjf8$p...@odin.diku.dk>, tor...@diku.dk (Torben AEgidius
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

unread,
Nov 15, 1995, 3:00:00 AM11/15/95
to
j...@dm.unibo.it (Juliusz Chroboczek) writes:

: 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

unread,
Nov 16, 1995, 3:00:00 AM11/16/95
to
On Mon, 13 Nov 1995 08:12:18 GMT, Henry Baker <hba...@netcom.com> wrote:
>In article <slrn4acul2...@wrath.ugcs.caltech.edu>,
>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.

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

unread,
Nov 16, 1995, 3:00:00 AM11/16/95
to
In article <slrn4akurm...@liquefy.ugcs.caltech.edu> set...@liquefy.ugcs.caltech.edu (Seth M. LaForge) writes:
>> 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

unread,
Nov 16, 1995, 3:00:00 AM11/16/95
to
> ...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.

>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

unread,
Nov 17, 1995, 3:00:00 AM11/17/95
to

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


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

unread,
Nov 18, 1995, 3:00:00 AM11/18/95
to
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.

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

unread,
Nov 18, 1995, 3:00:00 AM11/18/95
to
In article <48kuoc$1...@rc1.vub.ac.be>, v911...@vub.ac.be (OVLINGER Johan)
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.

I think they mean you can update a linked list in constant time if
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

unread,
Nov 19, 1995, 3:00:00 AM11/19/95
to
In article <48kuoc$1...@rc1.vub.ac.be> v911...@vub.ac.be "OVLINGER Johan" writes:

> 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

unread,
Nov 19, 1995, 3:00:00 AM11/19/95
to
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?

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

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
set...@mince.ugcs.caltech.edu (Seth M. LaForge) writes:

: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

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
On Wed, 15 Nov 1995 07:57:05 -0500, r...@cs.cmu.edu (Robert Harper)
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

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
On 16 Nov 1995 18:28:47 GMT, William D Clinger <wi...@ccs.neu.edu> wrote:
>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

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
>>>>> "johan" == OVLINGER Johan <v911...@vub.ac.be> writes:

In article <48kuoc$1...@rc1.vub.ac.be> v911...@vub.ac.be (OVLINGER Johan) writes:

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)

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
Various people wrote:

> 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

unread,
Nov 20, 1995, 3:00:00 AM11/20/95
to
In article <1995112021...@piano.cs.indiana.edu>,

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

unread,
Nov 21, 1995, 3:00:00 AM11/21/95
to
th...@drogo.irisa.fr (Tommy Thorn) writes:

>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

unread,
Nov 21, 1995, 3:00:00 AM11/21/95
to
Thomas M. DeBoni <deb...@llnl.gov> writes:

> 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

unread,
Nov 22, 1995, 3:00:00 AM11/22/95
to
On 21 Nov 1995 14:59:12 GMT, jgmo...@cs.cmu.edu (Greg Morrisett)
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

unread,
Nov 23, 1995, 3:00:00 AM11/23/95
to
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.) 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

unread,
Nov 23, 1995, 3:00:00 AM11/23/95
to
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.

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

unread,
Nov 23, 1995, 3:00:00 AM11/23/95
to daVinci
Dr S B Jones (Staff) wrote:
> > From: m...@math.keio.ac.jp (MAEDA Atusi)
> > 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.
> >
> [...] 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).
> [...]

> 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

unread,
Nov 24, 1995, 3:00:00 AM11/24/95
to
a...@aqua.civag.unimelb.EDU.AU (Bert Thompson) writes:
> 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

unread,
Nov 25, 1995, 3:00:00 AM11/25/95
to
o...@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:

|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

unread,
Nov 25, 1995, 3:00:00 AM11/25/95
to
m...@cs.nott.ac.uk (Mark Jones) writes

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

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

unread,
Nov 25, 1995, 3:00:00 AM11/25/95
to
> > Eagerness and side-effects are orthogonal issues.
> > There -are- lazy languages that support side-effects
> > in a disciplined way (and others that do in an
> > 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).

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

unread,