On Wed, 19 Jan 2005, Jan-Willem Maessen wrote:

On Jan 18, 2005, at 11:36 PM, mgross@dorsai.org wrote:

...

On Tue, 18 Jan 2005, Satnam Singh wrote:

...

I'm trying to find out about existing work on implicit parallel functional programming. I see that the Glasgow Haskell compiler has a parallel mode which can be used with PVM and there is interesting work with pH at MIT. Does anyone know of any other work on implicitly parallelizing functional programs for fine grain parallel execution?

The emergence of multi-core processors makes me think that we should look at implicit parallel functional programming in a new light.

At Brooklyn College, we are working on a version of Parallel Haskell that does not require PVM. Instead, we use Internet protocols and the Mosix patches to Linux.

But what about Haskell for closely-coupled shared-memory multiprocessors? These are the machines Satnam is talking about. For a multipcore processor with shared caches, message passing is actively bad for performance; you *want* to share memory to prevent cache conflicts. A first step would be to simply get GHC's RTS to work in multiple threads (harder than it looks, as the Simons have attested in the past).

The same approach we use will work for closely coupled multiprocessors, although we will increase overhead slightly with message passing. The trick here is to assure that the number of Haskell processes running on a given processor is no greater than the number of processors, since moving messages between virtual hosts on the loopback network is a low-overhead operation. If it is larger, then we begin to introduce overhead from process switching. There are, of course, still problems at the lowest optimization levels, such as cache optimization. Since we do not yet trust our system at the higher levels, we are ignoring the lower level problems for the time being. Murray Gross Brooklyn College

I have to say I disagree... I feel Haskell is highly suited to implicit parallel execution... The key to "implicit" parallelisation is that it is implicit - not explicit, so the programmer should feel like they are programming a sequential language. If we can assume little memory access penalties for threads running on other CPUs (shared cache model), it seems to be a matter of putting locks on the right structures, and allowing any worker-thread to take the next function ready to run from the scheduler. Keean. Clemens Grelck wrote:

Satnam Singh wrote:

...

I'm trying to find out about existing work on implicit parallel functional programming. I see that the Glasgow Haskell compiler has a parallel mode which can be used with PVM and there is interesting work with pH at MIT. Does anyone know of any other work on implicitly parallelizing functional programs for fine grain parallel execution?

The emergence of multi-core processors makes me think that we should look at implicit parallel functional programming in a new light.

This is perhaps not the kind of language you are looking for, but SAC (Single Assignment C) is a functional array language, which supports among others truly implicit parallelization.

See http://wwww.sac-home.org/ for more information.

Clemens

Having donned my flame-resistant suit, I am going to venture that I think the differences of opinion in the posts copied below are in large part the result of people talking about different things at the same time. First, there is a claim that functional languages facilitate parallel execution, which is undeniably true if the implementation is something like that of Haskell (no assignment statements mean no memory contention, etc.). Then there is the claim that it is difficult (if not impossible) to analyze a piece of code and parallelize it optimally automatically, which is a point that was conceded long ago. Third, there is the issue of whether "reasonable" parallelization can be obtained, and the answer to this problem is that it has been done before, and it can be done again. The open question is whether or not the parallelization thus achieved is sufficiently "good" in some sense. This, I submit, appears to be an open question at present, which is a statement I'd really like to find is wrong. Then there is the issue of optimality of algorithms. Which is always a bugbear, because different quality criteria change things wildly (y'know, n-square sorts are frequently used in real-world programs . . . <g>). And when it comes to dealing with parallel execution on a multiprocessor machine (as opposed to a cluster), this raises significant questions about performance constraints resulting from hardware design and implementation. Any answer to the problems here depends on the hardware that is being used and cannot be general. I suggest, then, that if this thread is to be continued, contributors should be careful to specify the particular hardware and software environments they are talking about, and be specific about such things as quality criteria. Murray Gross On Thu, 20 Jan 2005, Ben Lippmeier wrote:

I thought the "lazy functional languages are great for implicit parallelism" thing died out some time ago - at least as far as running the programs on conventional hardware is concerned.

Designing an algorithm that breaks apart a "sequential" lazy program into parallel chunks of the appropriate size is **HARD** (with double asterixes). The time and space behavior of a lazy program is complex enough for the _programmer_ to reason about, let alone an automated analysis - which has no knowledge of what the program is actually trying to do.

I think a more likely approach lies in the direction of the so called "parallel strategies". If you haven't already, I would strongly suggest reading: Algorithm + Strategy = Parallelism, 1998, PW Trinder, et al. You can get this paper from Simon Peyton Jones's homepage.

Also, at the end of Hans Wolfgang-Loidl's thesis he develops a granularity analysis for a Haskell subset - one of the first steps in any kind of implicit parallelism. It's a pretty good effort, but at the end of it all it still relies on a pre-existing table of information about recursive functions. I think that these kind of analyses tend suffer from uncomputability problems more than most.

If you've still got your heart set on implicit parallelism, then there's a (very slow) simulator you might want to poke around with. I wrote it based around Clem Baker-Finch's "Abstract machine for parallel lazy evaluation", which supports fully speculative implicit parallelism.

There's a link to it on my homepage at http://cs.anu.edu.au/people/Ben.Lippmeier

Keean Schupke wrote:

...

I have to say I disagree... I feel Haskell is highly suited to implicit parallel execution... The key to "implicit" parallelisation is that it is implicit - not explicit, so the programmer should feel like they are programming a sequential language. If we can assume little memory access penalties for threads running on other CPUs (shared cache model), it seems to be a matter of putting locks on the right structures, and allowing any worker-thread to take the next function ready to run from the scheduler.

Keean.

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

Bjorn Lisper wrote:

A guess is that the first generation will support a shared memory model much like SMP:s of today (shared main memory with on-chip cache(s), or some other kind of local memory (-ies)). Here, I think implicit parallelism in functional languages can be a win in some situations. This is provided spawning of parallel threads is cheap and local memory can be efficiently utilized (so control of granularity is no problem, and dynamic parallelism is cheap). Cheap threads is likely to be true, efficient use of local memory is a question mark.

You only need one thread per CPU-core, so the spawning threads cost is a red-herring. Just like GHC schedules haskell-threads from a single OS-thread.

However, some obstacles:

Laziness, if used strictly (sorry) gets in the way for parallelism. Waiting to spawn a parallel thread until we surely know it's result is needed, if it is anyway needed 99% of the time, is not an optimal strategy. I think optimistic evaluation strategies a la Robert Ennals can be helpful here. But designing them to work for new parallel architectures may be non-trivial. I think there can be material for PhD theses here.

I suggest speculative execution, as used by current CPUs to take advantage of multiple microcode execution units. If the a CPU has spare capacity, functions whose results might be needed are run. As soon as you know a result is not needed the thread can be killed, and the time used for something else. A lot of work has already been done on hardware superscalar-architectures, and a lot of this should be applicable to the software case.

If the program implements an inherently sequential algorithm then parallelism won't help anyway. The use of lists often leads to sequential algorithms: a prime example is list folds, which all translate the linear spine structure of a list into a sequential dependence graph of the resulting computation. Folds over tree-like structures are better in this regard. The FP community will have a problem with legacy code using inherently sequential computations over lists. There has been quite some research on how to parallellize list computations (skeletons, program transformations using BMF,...). However, they typically rely on knowing the length of the list. In a lazy language it is common that lists are evaluated dynamically, and then it's hard to use these techniques efficiently. Again, speculation may help.

But in the worst case its just a sequential computation, so any gain from parallelism is still a gain... also the dependant part of a loop is often separate from an independant part... For example consider a list of strings, and taking the length of each string. The next iteration does not have to wait for the length to be computed, it can start the next length computation as soon as the pointer for the next list cell has been dereferenced.

In the long run, as hardware dimensions shrink even more and communication becomes relatively even more expensive, it is likely that we will have some kind of on-chip massively parallel, mesh-connected distributed memory machine. This will most likely favor static parallelization techniques, which means only for certain classes of functional programs an automatic approach with implicit parallelism will work well.

The next generation of CPUs seem to be using a shared cache architecture, so overheads are extreemely small... Erm, by static I assume you mean programmer specified parallelism. I would tend to think of static parallelization as something that takes place at compile time (and would still count as implicit). Keean.

Bjorn Lisper wrote:

It depends on what you compare with. Multicore CPU:s will probably have cores that are simpler than current processor cores, which means you will want to have some parallelism. Cf. a superscalar processor, which really in a sense is a parallel machine but where you add some complex control hardware to make it emulate a sequential machine. Running a multicore CPU on a single core at a time corresponds to running a superscalar machine where you use none of the superscalarity. Or, running a pipelined CPU (another form of parallelism) without utilizing any of the pipelining. This is not what you want.

Well, intel have 2 core now, 4 core soon. AMD have 2 core now... IBM have 8 core Power5... These are full spec superscalar cores. When I am thinking about exploiting parallelism, I am thinking about 2/4 cpu (4/8 with hyperthreading) Intel boxes, maybe 8/16 cpu AMD Opteron boxes, or 8 way Power5 boxes.

Sure you can get some overlap, which can be quite big if the task to perform per list element is big, but a dependence graph with O(n) nodes will still have O(n) depth => at maximum constant speedup.

A constant speedup per CPU. Imagine a loop: loop [] = 0 loop (a:b) = length a + loop b we can run as many "length" calculations in parallel as we have CPUs. (Here length may take a significant time as a could be long)

I'm not talking about the next generation but further ahead. Maybe these architectures will have some kind of on-chip shared cache, who knows, but that memory will then still be much more expensive to access than the memory in a local core. So you will want to use the core-local memory all the time, and only communicate between processor cores which are quite close on the chip.

One step at a time, are you suggesting we fail to take advantage of architectures that are on the horizon, because things may be different in the far future...

No, I mean automatic techniques to detect the parallelism statically (and schedule and allocate work statically), which only will work well for restricted classes of programs.

Well this is how I imagine things happening as well. As do as much static analysis as you can at compile time. You end up with a lot of dependancies resolved, but a few will be unknown until runtime (due to IO for example)... These remaining few are the ones that you might want to try speculative execution on... If you have the spare CPU cycles (and the machine would otherwise be idle). Keean.

I'd like to add another meaning to running things in a distributed way, i.e., scalability. Implicit parallelism should help the application to scale itself automatically with the increase of the number of nodes in the cluster. Yes, today we have two-processors on a core, and uni-processor speed bump is unlikely to overshadow the effort of parallelism like it did 20 years ago. But we are also beginning to see applications requiring thousands of machines to run. The so called grid computing maybe a just another buzzword, but the reality is that grand applications just won't scale on today's two-processor core, and explicit parallelism often requires a prior knowledge on how to split the program, which is hardly scalable except some simple cases. Recent examples? World of Warcraft. Blizzard is already having trouble to manage the load across thousands of their servers, until the stage that they are forced to stop shipping new games to store. It's in the news yesterday. Regards, Paul On Wed, Jan 19, 2005 at 11:16:12PM -0500, mgross@dorsai.org wrote:

Having donned my flame-resistant suit, I am going to venture that I think the differences of opinion in the posts copied below are in large part the result of people talking about different things at the same time.

First, there is a claim that functional languages facilitate parallel execution, which is undeniably true if the implementation is something like that of Haskell (no assignment statements mean no memory contention, etc.).

Then there is the claim that it is difficult (if not impossible) to analyze a piece of code and parallelize it optimally automatically, which is a point that was conceded long ago.

Third, there is the issue of whether "reasonable" parallelization can be obtained, and the answer to this problem is that it has been done before, and it can be done again. The open question is whether or not the parallelization thus achieved is sufficiently "good" in some sense. This, I submit, appears to be an open question at present, which is a statement I'd really like to find is wrong.

Then there is the issue of optimality of algorithms. Which is always a bugbear, because different quality criteria change things wildly (y'know, n-square sorts are frequently used in real-world programs . . . <g>). And when it comes to dealing with parallel execution on a multiprocessor machine (as opposed to a cluster), this raises significant questions about performance constraints resulting from hardware design and implementation. Any answer to the problems here depends on the hardware that is being used and cannot be general.

I suggest, then, that if this thread is to be continued, contributors should be careful to specify the particular hardware and software environments they are talking about, and be specific about such things as quality criteria.

Murray Gross

On Thu, 20 Jan 2005, Ben Lippmeier wrote:

...

I thought the "lazy functional languages are great for implicit parallelism" thing died out some time ago - at least as far as running the programs on conventional hardware is concerned.

Designing an algorithm that breaks apart a "sequential" lazy program into parallel chunks of the appropriate size is **HARD** (with double asterixes). The time and space behavior of a lazy program is complex enough for the _programmer_ to reason about, let alone an automated analysis - which has no knowledge of what the program is actually trying to do.

I think a more likely approach lies in the direction of the so called "parallel strategies". If you haven't already, I would strongly suggest reading: Algorithm + Strategy = Parallelism, 1998, PW Trinder, et al. You can get this paper from Simon Peyton Jones's homepage.

Also, at the end of Hans Wolfgang-Loidl's thesis he develops a granularity analysis for a Haskell subset - one of the first steps in any kind of implicit parallelism. It's a pretty good effort, but at the end of it all it still relies on a pre-existing table of information about recursive functions. I think that these kind of analyses tend suffer from uncomputability problems more than most.

If you've still got your heart set on implicit parallelism, then there's a (very slow) simulator you might want to poke around with. I wrote it based around Clem Baker-Finch's "Abstract machine for parallel lazy evaluation", which supports fully speculative implicit parallelism.

There's a link to it on my homepage at http://cs.anu.edu.au/people/Ben.Lippmeier

Keean Schupke wrote:

...

I have to say I disagree... I feel Haskell is highly suited to implicit parallel execution... The key to "implicit" parallelisation is that it is implicit - not explicit, so the programmer should feel like they are programming a sequential language. If we can assume little memory access penalties for threads running on other CPUs (shared cache model), it seems to be a matter of putting locks on the right structures, and allowing any worker-thread to take the next function ready to run from the scheduler.

Keean.

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

paul@theV.net wrote:

...

Yes, today we have two-processors on a core, and uni-processor speed bump is unlikely to overshadow the effort of parallelism like it did 20 years ago. But we are also beginning to see applications requiring thousands of machines to run. The so called grid computing maybe a just another buzzword, but the reality is that grand applications just won't scale on today's two-processor core, and explicit parallelism often requires a prior knowledge on how to split the program, which is hardly scalable except some simple cases.

Re: the grid buzzword

Grid computing, as seen by organisations like the GGF and mainstream toolkits such as Globus, is not about parallelisation, but instead simply about access to shared resources. That is, they're interested in providing tools and standards for remote, shared access to software services, data and hardware (and providing useful features like security, authorisation, authentication, monitoring and reliability). Of course peer-to-peer compute systems are more about parallelisation, but they tend to be mostly commercial/proprietary rather than standardised at the moment.

The Grid will be more like an enhanced version of the current web. But Haskell could get involved there too, especially if styles such as web programming with continuations prove useful in future generations of web services architectures.

At Heriot Watt University, we are working on a version of Glasgow Parallel Haskell that uses Globus Toolkit as a midle-ware and MPICH-G2 for communication. We experiment this version with serious of experiments over three clusters which located in three different places, Edinburgh (UK), Galashiels (UK), and Munich (Germany). There is a paper of the new implementation and a serious of experiments on IFL04 draft proceeding. Abyd

Amanda

-- Amanda Clare http://users.aber.ac.uk/afc/ Dept. of Computer Science, University of Wales, Aberystwyth, SY23 3DB _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

Ben Lippmeier wrote:

I thought the "lazy functional languages are great for implicit parallelism" thing died out some time ago - at least as far as running the programs on conventional hardware is concerned.

Designing an algorithm that breaks apart a "sequential" lazy program into parallel chunks of the appropriate size is **HARD** (with double asterixes). The time and space behavior of a lazy program is complex enough for the _programmer_ to reason about, let alone an automated analysis - which has no knowledge of what the program is actually trying to do.

I guess this is true, but only if you are trying to find the optimal solution (or prooveably optimal solution)... There must me many ad-hoc solutions with reasonable performance. Perhaps a good first step would be a solution bounded in the worst case by the sequential execution time (IE the multi-CPU version would be no slower than the single CPU version, excluding the locking overhead). If something were to win on 2/4/8 cpu machines most of the time I think it would be useful. Keean.

Lennart Augustsson and Thomas Johnsson got some encouraging results fifteen years ago with their nu-G-machine. They compiled Lazy ML for a shared memory multiprocessor, and benchmarked against the sequential LML compiler, the precursor of hbc and at that time the best compiler for a lazy functional language. They observed speed-ups of at least 20% even with only two processors, and with four the speed-ups were in the range 2-3.3x. The idea was to use "sparks" to start parallel computations, which were ignored, and thus cheap, unless a processor was actually available. OK, then benchmarks were tiny (n-queens), and the LML compiler had higher overheads for ordinary computation than GHC, but still, it's an encouraging result for exploiting multi-core machines. Here's the reference:

@inproceedings{99386, author = {Lennart Augustsson and Thomas Johnsson}, title = {Parallel graph reduction with the (v , G)-machine}, booktitle = {FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture}, year = {1989}, isbn = {0-89791-328-0}, pages = {202--213}, location = {Imperial College, London, United Kingdom}, doi = {http://doi.acm.org/10.1145/99370.99386}, publisher = {ACM Press}, }

John

...

I thought the "lazy functional languages are great for implicit parallelism" thing died out some time ago - at least as far as running the programs on conventional hardware is concerned.

Designing an algorithm that breaks apart a "sequential" lazy program into parallel chunks of the appropriate size is **HARD** (with double asterixes). The time and space behavior of a lazy program is complex enough for the _programmer_ to reason about, let alone an automated analysis - which has no knowledge of what the program is actually trying to do.

I think a more likely approach lies in the direction of the so called "parallel strategies". If you haven't already, I would strongly suggest reading: Algorithm + Strategy = Parallelism, 1998, PW Trinder, et al. You can get this paper from Simon Peyton Jones's homepage.

Also, at the end of Hans Wolfgang-Loidl's thesis he develops a granularity analysis for a Haskell subset - one of the first steps in any kind of implicit parallelism. It's a pretty good effort, but at the end of it all it still relies on a pre-existing table of information about recursive functions. I think that these kind of analyses tend suffer from uncomputability problems more than most.

If you've still got your heart set on implicit parallelism, then there's a (very slow) simulator you might want to poke around with. I wrote it based around Clem Baker-Finch's "Abstract machine for parallel lazy evaluation", which supports fully speculative implicit parallelism.

There's a link to it on my homepage at http://cs.anu.edu.au/people/Ben.Lippmeier

Keean Schupke wrote:

...

I have to say I disagree... I feel Haskell is highly suited to implicit parallel execution... The key to "implicit" parallelisation is that it is implicit - not explicit, so the programmer should feel like they are programming a sequential language. If we can assume little memory access penalties for threads running on other CPUs (shared cache model), it seems to be a matter of putting locks on the right structures, and allowing any worker-thread to take the next function ready to run from the scheduler. Keean.

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

Hi, The classical Hamming problem have the following solution in Haskell : *** BEGIN SNAP -- hamming.hs -- Merges two infinite lists merge :: (Ord a) => [a] -> [a] -> [a] merge (x:xs)(y:ys) | x == y = x : merge xs ys | x < y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys -- Lazily produce the hamming sequence hamming :: [Integer] hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming)) *** END SNAP I just love these algorithms that run after their tail (they make my brain melt) but I don't know how is it that they are efficient. Here, the hamming recursively calls itself three times. For this algorithm to be efficient, the Haskell system, somehow, has to "remember" the already generated sequence THROUGH RECURSION (i.e. not only intermediate "local" results) otherwise it would end up regenerating the beginning of the sequence over and over again. Obviously, Haskell does remember what had already been generated THROUGH RECURSION since executing the program with GHCI runs quite smoothly and responsively. That Haskell manages to do that is for me "magnifique". But I need to know (if only a little) about how it achieves this in order to know what I, as a lambda programmer, can do, and how to compute the Big-Oh complexity of the algorithm. Thank you, Francis Girard FRANCE

It doesn't have to be a top level definition, it works anyway. -- Lennart Bruno Abdon wrote:

'hamming', in your code, is a top-level definition. When used three times inside its own definition, it's the same variable being used three times. You don't recompute a variable value in order to reuse it.

As an example, if you do

foo :: [Integer] foo = [1,2,3] + [4,5]

bar = foo ++ foo ++ foo

the concatenation used to produce foo will not be done three times in order to calculate the value of bar. That would be true for any function would foo be defined upon, not only concatenation.

Bruno Abdon

On Mon, 24 Jan 2005 10:38:35 +0100, Francis Girard <francis.girard@free.fr> wrote:

...

Hi,

The classical Hamming problem have the following solution in Haskell :

*** BEGIN SNAP -- hamming.hs

-- Merges two infinite lists merge :: (Ord a) => [a] -> [a] -> [a] merge (x:xs)(y:ys) | x == y = x : merge xs ys | x < y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys

-- Lazily produce the hamming sequence hamming :: [Integer] hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming)) *** END SNAP

I just love these algorithms that run after their tail (they make my brain melt) but I don't know how is it that they are efficient.

Here, the hamming recursively calls itself three times. For this algorithm to be efficient, the Haskell system, somehow, has to "remember" the already generated sequence THROUGH RECURSION (i.e. not only intermediate "local" results) otherwise it would end up regenerating the beginning of the sequence over and over again.

Obviously, Haskell does remember what had already been generated THROUGH RECURSION since executing the program with GHCI runs quite smoothly and responsively.

That Haskell manages to do that is for me "magnifique". But I need to know (if only a little) about how it achieves this in order to know what I, as a lambda programmer, can do, and how to compute the Big-Oh complexity of the algorithm.

Thank you,

Francis Girard FRANCE

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

Thank you, I understand the point. But I can't help thinking that the distinction between "being" a list of integers and "being" a function that "returns" a list of integers (without arguments) is not always clear in FP ... since there is not really such a thing as returning a value in declarative programming, neither in mathematical thinking. Thank you Francis Girard FRANCE Le lundi 24 Janvier 2005 18:11, Graham Klyne a écrit :

Notice that 'hamming' *is* a list of integers, not a function to produce them:

hamming :: [Integer]

Thus, the "magic" here is that you can define this list as a value, without having to actually evaluate any element until it's needed, either by direct reference from another function, or indirectly by the recursive definition to obtain a value directly required. But once evaluated, the deferred evaluation is replaced by the resulting value.

This is the power of lazy evaluation. Even fixed values (as opposed to function calls) aren't evaluated until they're needed.

#g --

At 10:38 24/01/05 +0100, Francis Girard wrote:

...

Hi,

The classical Hamming problem have the following solution in Haskell :

*** BEGIN SNAP -- hamming.hs

-- Merges two infinite lists merge :: (Ord a) => [a] -> [a] -> [a] merge (x:xs)(y:ys)

| x == y = x : merge xs ys | x < y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys

-- Lazily produce the hamming sequence hamming :: [Integer] hamming = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming)) *** END SNAP

I just love these algorithms that run after their tail (they make my brain melt) but I don't know how is it that they are efficient.

Here, the hamming recursively calls itself three times. For this algorithm to be efficient, the Haskell system, somehow, has to "remember" the already generated sequence THROUGH RECURSION (i.e. not only intermediate "local" results) otherwise it would end up regenerating the beginning of the sequence over and over again.

Obviously, Haskell does remember what had already been generated THROUGH RECURSION since executing the program with GHCI runs quite smoothly and responsively.

That Haskell manages to do that is for me "magnifique". But I need to know (if only a little) about how it achieves this in order to know what I, as a lambda programmer, can do, and how to compute the Big-Oh complexity of the algorithm.

Thank you,

Francis Girard FRANCE

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell

Francis Girard <francis.girard@free.fr> writes:

But I can't help thinking that the distinction between "being" a list of integers and "being" a function that "returns" a list of integers (without arguments) is not always clear in FP ... since there is not really such a thing as returning a value in declarative programming, neither in mathematical thinking.

Please correct me if I'm wrong, but I can recall that this distinction is made by hamming::[Integer] having no arguments, so it gets memoized within its scope. Being a CAF (top level constant applicative form) only means it can't go out of scope so has no chance of recomputation at all. Am I right? -- Feri.