Re: [Caml-list] compact.c

Re: [Caml-list] compact.c

[Damien Doligez]

>From: Julie Farago <farago@eecs.harvard.edu>
>
>Is there a paper on the compaction code (compact.c) of the garbage
>collector (in byterun/)? Even though the documentation in this file is
>really exceptional, I am a little confused by how the inversion of
>pointers is used to compact the heap. Is there an algorithm I should
>lookup?

There is no paper on compact.c itself, but the algorithm is not
original.  If I remember correctly, it is from this paper:

F. Lockwood Morris, A time- and space-efficient garbage compaction
algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978

The only tricky part is the double inversion of pointers to infix
headers.  If you really need it, I'll write up a short description and
put it on my web page.

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Rule based language [was: productivity improvement]

[Alessandro Baretta]

Oleg wrote:
> On Thursday 18 July 2002 09:25 pm, Alessandro Baretta wrote:
> 
> [...]
> 
> 
>>Ah! Wait a minute. I have another toy project I could
>>propose to you: an interpreter for rule based language, à la
>>CLIPS. 197 lines of code in ocaml, including comments. This
>>is probably the kind of compelling example you are looking
>>for. I coded it in 24 h, including time for sleep, nutrition
>>and general self care.
>>
>>Let me know if you are interested.
> 
> 
> Sure, if it's really compelling, and if I won't have to guess the language 
> specifications.
> 
> Thanks
> Oleg
> 

Here is the specification of the language:

<program> -> <ruleset> <dataset> <goals>

<ruleset> -> ruleset: <rules>
<rules>   -> <rule> <rules> | <epsilon>
<rule>    -> <rule_name> is <preconditions> =>
                  <postconditions>;
<rule_name> -> <token>
<preconditions> -> <conditions>
<postconditions> -> <conditions>
<conditions>    -> <datum> | <datum> and <conditions>
<datum>   -> <token>

<dataset> -> data_set: <data_list>
<data_list> -> <datum>; <data_list> | <epsilon>

<goals>  -> goals: <goal_list>
<goal_list> -> <goal> <goal_list> | <epsilon>
<goal>   -> <simple>? <goal_name> is <conditions>;
<simple> -> simple
<epsilon> ->

I hope this grammar is complete. I cannot find the original 
specifications for this language.

The interpreter takes a program written in the language 
specified above and for each goal it attempts to find a 
sequence of rule activations that lead to the conditions of 
goal being present contemporarily in the dataset. Since 
preconditions are removed from the dataset upon rule 
activation, the logic determined by this language is non 
monotonous, and backtracking is required to solve the 
problem. Goals marked simple are tested with out 
backtracking: the first rule whose preconditions are 
verified is activated at each step.

Goals are all verified from the initial dataset--that is, 
execution order or goals does not matter.

Here's a thirty second test case I cooked up. We'll want 
something more complete and complex for verification and 
benchmarking.
<rules.program>
--------------------------------------------------------
ruleset:

1 is x => y;
2 is x and pippo => z;

dataset:

foo
x;

goals:

foo is x;
simple x is foo;
simple sz is z;

--------------------------------------------------------
The following is the output the interpreter is supposed to 
generate.

[alex@athlon ocaml]$ ./rules < rules.program
Goal pippo: found
Goal x: found
Goal sz: not found
Goal z: found


Code on and have fun!

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] compact.c

[Julie Farago]

Hello,

Is there a paper on the compaction code (compact.c) of the garbage
collector (in byterun/)? Even though the documentation in this file is
really exceptional, I am a little confused by how the inversion of
pointers is used to compact the heap. Is there an algorithm I should
lookup?

Thanks a lot!
-Julie

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners