🚀 go-pugleaf

While looking for data structures to store states of a computation
the following questions arose concerning the garbage collector of
Miranda. 

1) Where is the implementation difference between list comprehensions
and explicit recursive list definitions like the following? In an
environment with heap size set to 10000 cells (this is small, I know),
the lenght of the list defined by a comprehension cannot be evaluated.

    >list 0 = []
    >list n = n : list (n-1)

    Miranda /heap 10000
    heaplimit = 10000 cells
    Miranda /count
    Miranda #[1..50000]
    <<not enough heap space -- task abandoned>>
    ||reductions = 5548, cells claimed = 11094, no of gc's = 3, cpu = 0.32
    Miranda #(list 50000)
    50000
    ||reductions = 400003, cells claimed = 417248, no of gc's = 51, cpu = 7.90
    Miranda


Looking to the garbage collection report (/gc) shows the different
runtime behaviour of both implementations. In the first expression the
number of collected cells drops one or more times but reaches 0 at
some stage. The second implementation is more stable in that sense
that in more runs the number of collected cells is around 9940.

But this leads to the second question.

2) Is the garbage collector non-deterministic or can the following effect
be predicted?
 
Once you evaluate the expressions "#(list 50000)" and "#[0..50000]"
several times you will notice that the evaluation does not succeed all
the times. Could anybody tell me whether and if so how the garbage
collector is related to the operating system to explain this
non-deterministic behaviour.

3) Why does the extension of the heap changes the situation to the
reverse effect?

    Miranda /heap 200000
    heaplimit = 200000 cells
    Miranda #[1..50000]
    50000
    ||reductions = 50004, cells claimed = 117248, no of gc's = 0, cpu = 1.88
    Miranda #(list 50000)

    <<gc after 192248 claims>>

    <<gc after 83646 claims>>

    <<gc after 31371 claims>>

    <<gc after 11763 claims>>

    <<gc after 4413 claims>>
    <<not enough heap space -- task abandoned>>
    ||reductions = 297407, cells claimed = 314644, no of gc's = 4, cpu = 9.08
    Miranda

Setting the heap to 200000 cells causes the successfull termination of
the standard definition whereas the explicit definition causes heap
overflow. 

These runs were executed on SUN-4 with 16 MB and Miranda version 2.014.
Thanks to any hints on this questions.

Heiko

+-----------------------------------------------------------------+
| Heiko Doerr                          Tel.: 030/896 91 106       |
| Institut fuer Informatik             Fax.: 030/896 91 123       |
| Freie Universitaet Berlin            e-mail:                    |
| Nestorstrasse 8-9                      doerr@inf.fu-berlin.de   |
| D-1000 Berlin 31                                                |
+-----------------------------------------------------------------+