"ocaml_beginners"::[] recursive values and constructor hiding

Shalom.

Some days ago this question was discussed here
("untying the knot" or something like this), but
I can't understand how to do it in my code.
The example is oversimplified, real constructors
and their values are much more complicated.

$ ocaml camlp4r.cma
Objective Caml version 3.09.3
Camlp4 Parsing version 3.09.3
# type gen 'a = [ A of unit -> gen 'a | B of 'a ];
type gen 'a = [ A of unit -> gen 'a | B of 'a ]
# value rec randomgen = A (fun () ->
if Random.bool () then randomgen else B 123);
value randomgen : gen int = A <fun>;

Everything seems good until we'll hide (or make private)
type gen 'a. (I wrapped long lines by hand to make them
visible)

# value make_A f = A f;
value make_A : (unit -> gen 'a) -> gen 'a = <fun>;
# value make_B v = B v;
value make_B : 'a -> gen 'a = <fun>;
# value rec randomgen2 = make_A (fun () ->
if Random.bool () then randomgen2 else make_B 123);
Characters 23-91:
value rec randomgen2 = make_A (fun () ->
^^^^^^^^^^^^^^^^^
if Random.bool () then randomgen2 else make_B 123);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This kind of expression is not allowed as right-hand side
of `let rec'

I perfectly understand _why_ OCaml has such limitation.
I want to know _how_ to make this trick. Speaking
precisely, I want to create a value with constructors like
make_A and make_B so that the value can refer to itself.
In my real code the situation is the same: if I inline
the call of constructor, everything goes ok.
I could let the user create values using constructors,
but it's possible that details of implementation will be
changed in future, and it will break users' code.
I could create fresh values of type gen 'a every time
they are used:

# value rec randomgen3 () = make_A (fun () ->
if Random.bool () then randomgen3 () else make_B 123);
value randomgen3 : unit -> gen int = <fun>;

, but in real code the argument of make_A is complex value
that creates and uses many other values, and its creation on
every use causes slowdown of the program.

How can I create a single self-recursive value using
&quot;constructor function&quot;?

--
WBR,
dmitry mailto: gds-mlsts%40moldavcable.com">gds-mlstsmoldavcable.com

Messages in this topic (1) Reply (via web post) | Start a new topic

.

On Friday 15 December 2006 06:58, dmitry grebeniuk wrote:
&gt; I perfectly understand _why_ OCaml has such limitation.
> I want to know _how_ to make this trick. Speaking
> precisely, I want to create a value with constructors like
> make_A and make_B so that the value can refer to itself.
&gt; In my real code the situation is the same: if I inline
&gt; the call of constructor, everything goes ok.

I think you must inline the constructors, yes.

&gt; I could let the user create values using constructors,
> but it's possible that details of implementation will be
> changed in future, and it will break users' code.

You could use polymorphic variants to have the types inferred. That should
make the code less likely to break in the future as the new types will be
inferred for you.

&gt; , but in real code the argument of make_A is complex value
>; that creates and uses many other values, and its creation on
> every use causes slowdown of the program.

Yes. Note that the fastest way (I think) to untie the knot in my previous
example is by using -rectypes.

> How can I create a single self-recursive value using
>; "constructor function&quot;?

I don't think you can.

What exactly are your recursive values?

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Messages in this topic (2) Reply (via web post) | Start a new topic

.

Shalom, Jon.

&gt;> In my real code the situation is the same: if I inline
>> the call of constructor, everything goes ok.
JH>; I think you must inline the constructors, yes.

Are there any other ways to do it, for example, using
auxiliary functions or something like this?

&gt;> I could let the user create values using constructors,
>> but it's possible that details of implementation will be
>> changed in future, and it will break users' code.
JH&gt; You could use polymorphic variants to have the types
JH&gt; inferred. That should make the code less likely to
JH> break in the future as the new types will be inferred
JH> for you.

I think there's no difference between usual and
polymorphic variants in this, because in my case
changes more probably will occur inside the expressions
under constructors, not in the constructors and not in
the count or types of constructors' arguments.

JH> What exactly are your recursive values?

It will be surprise I'll announce my work in
senior's list when/if it will be ready.
Now I can say that my recursive values contain
values with existential types, and ocaml works
with them as usual ML: with two additional types
with polymorphic fields/values. Not for faint of
heart. This was the main reason that forced me
to actively search solution/workaround for this
problem.

If there will be no good solution, I will make one
module that hides the representation of my type (this
module will be used by programmers who don't want to
go inside the ugly values), and another module that
will give details about my type for those who don't
afraid of dirt and who wants some more effectivity
by cost of additional amount of low-level details
and possibility of breaking their code.

--
WBR,
dmitry mailto: gds-mlsts%40moldavcable.com">gds-mlstsmoldavcable.com

Messages in this topic (3) Reply (via web post) | Start a new topic

.

On Fri, 15 Dec 2006, dmitry grebeniuk wrote:

> Shalom.
&gt;
> Some days ago this question was discussed here
> ("untying the knot" or something like this), but
> I can't understand how to do it in my code.
>; The example is oversimplified, real constructors
> and their values are much more complicated.
>
&gt; $ ocaml camlp4r.cma
> Objective Caml version 3.09.3
&gt; Camlp4 Parsing version 3.09.3
&gt; # type gen 'a = [ A of unit -> gen 'a | B of 'a ];
> type gen 'a = [ A of unit -> gen 'a | B of 'a ]
> # value rec randomgen = A (fun () ->
>; if Random.bool () then randomgen else B 123);
>; value randomgen : gen int = A <fun>;
>
&gt; Everything seems good until we'll hide (or make private)
> type gen 'a. (I wrapped long lines by hand to make them
> visible)
>
> # value make_A f = A f;
> value make_A : (unit -> gen 'a) -> gen 'a = <fun>;
> # value make_B v = B v;
> value make_B : 'a -> gen 'a = <fun>;
> # value rec randomgen2 = make_A (fun () ->
>; if Random.bool () then randomgen2 else make_B 123);
>; Characters 23-91:
&gt; value rec randomgen2 = make_A (fun () ->
>; ^^^^^^^^^^^^^^^^^
&gt; if Random.bool () then randomgen2 else make_B 123);
>; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> This kind of expression is not allowed as right-hand side
> of `let rec'
>
> I perfectly understand _why_ OCaml has such limitation.
> I want to know _how_ to make this trick. Speaking
> precisely, I want to create a value with constructors like
> make_A and make_B so that the value can refer to itself.
&gt; In my real code the situation is the same: if I inline
&gt; the call of constructor, everything goes ok.
> I could let the user create values using constructors,
> but it's possible that details of implementation will be
> changed in future, and it will break users' code.
>; I could create fresh values of type gen 'a every time
> they are used:
>;
> # value rec randomgen3 () = make_A (fun () ->
>; if Random.bool () then randomgen3 () else make_B 123);
>; value randomgen3 : unit -> gen int = <fun>;
>
&gt; , but in real code the argument of make_A is complex value
>; that creates and uses many other values, and its creation on
> every use causes slowdown of the program.
>
> How can I create a single self-recursive value using
>; "constructor function&quot;?

Hi Dmitry,

The following should work for your example. It works only if the
actual call to self occurs after your function f returns:

let rec_value f =
let self_value = ref None in
let self () =
match !self_value with
Some x -> x
| None -> failwith "invalid reference to self" in
let result = f self in
self_value := Some result;
result

Here is how you use it:

let randomgen3 =
rec_value
(fun self ->
make_A (fun () ->
if Random.bool () then self () else make_B 123))

Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Messages in this topic (4) Reply (via web post) | Start a new topic

.

Shalom, Martin.

MJ> The following should work for your example. It works
MJ&gt; only if the actual call to self occurs after your
MJ&gt; function f returns:

Yes, for sane programs this holds true.

Your solution is very nice. Thank you.

When I was thinking about your solution, a slightly
better implementation came into my head. Changing
reference self_value resembles me calculation of suspended
lazy values. I think that use of lazy values will be a bit
faster than calling function "self ()" because the "match
self_value" will be executed once. Anyway, I will check
it before serious using.
The code is:

value lazy_rec_value f =
let self_value = ref None in
let self = Lazy.lazy_from_fun (fun () ->
match self_value.val with
[ None -> failwith "invalid reference to self"
| Some x -> x
]
)
in
let result = f self in do
{ self_value.val := Some result
; result
}
;

and usage:

value randomgen4 = lazy_rec_value
(fun self ->
make_A
(fun () ->
if Random.bool ()
then Lazy.force self
else make_B 123
)
)
;

and... it works!

--
WBR,
dmitry mailto: gds-mlsts%40moldavcable.com">gds-mlstsmoldavcable.com

Messages in this topic (5) Reply (via web post) | Start a new topic

.

On Mon, 18 Dec 2006, dmitry grebeniuk wrote:

> Shalom, Martin.
&gt;
> MJ> The following should work for your example. It works
>; MJ> only if the actual call to self occurs after your
> MJ> function f returns:
>
> Yes, for sane programs this holds true.
>;
> Your solution is very nice. Thank you.
>
> When I was thinking about your solution, a slightly
> better implementation came into my head. Changing
> reference self_value resembles me calculation of suspended
> lazy values. I think that use of lazy values will be a bit
> faster than calling function "self ()" because the "match
> self_value" will be executed once. Anyway, I will check
>; it before serious using.
&gt; The code is:
>
> value lazy_rec_value f =
> let self_value = ref None in
> let self = Lazy.lazy_from_fun (fun () ->
>; match self_value.val with
> [ None -> failwith "invalid reference to self"
> | Some x -> x
> ]
> )
> in
> let result = f self in do
> { self_value.val := Some result
&gt; ; result
&gt; }
> ;

Hi Dmitry,

I think you should write:

...
let self = lazy
(match self_value.val with
[ None -> failwith "invalid reference to self"
| Some x -> x
]
)
in
...

but you could also write just:

let lazy_rec_value f =
let rec self = lazy (f self) in
Lazy.force self

# lazy_rec_value (fun self -> Lazy.force self);;
Exception: Lazy.Undefined.

&gt; and usage:
&gt;
> value randomgen4 = lazy_rec_value
> (fun self ->
>; make_A
&gt; (fun () ->
>; if Random.bool ()
> then Lazy.force self
> else make_B 123
> )
> )
> ;
>
&gt; and... it works!

Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

Messages in this topic (6) Reply (via web post) | Start a new topic

.