Re: [Caml-list] type abbreviation is cyclic

Re: [Caml-list] type abbreviation is cyclic

[William Smith]

I was just writing the simplest example of the recursive definition.   I 
didn't know about -recftypes.

The distilled version of the actual case follows

type b = ((tree -> bool) * (b-> tree ->  int)) list

The first function of each pair determines whether the second function 
will be called.   The second function recurses over the subtrees, 
possibly with different b control lists as their first argument.  My 
actual example is more complex because of the details of the tree, but I 
think this is gives the flavor of what I'm trying to do. (snd b) can 
pass different list's into subtrees when it recurses.  

The actual example gets messier because another argument to snd b is a 
function that can use different rules to choose a row (or rows) from b.

It's the recursion that can happen is related to the technique of 
writing recursive functions without using let rec..

let f1 it a1 b2 = ...
let f2 it a1 b2 = ....
let f3 it a1 b2 = ...

let items = [f1; f2; f3]

let x =  f1 items a b...

Till Varoquaux wrote:

Type b doesn't exactly make much sens to me.
While I could easilly define a value of type b (fun x:int _ -> x ) I
really don't see the point. I'm gessing you'r trying to pass a chain
of alternative functions (In which case this seems to be the  wrong
way).
Could you give an exemple (without using Obj.magic) were you'd
actually need such a type.
On 10/24/07, William W Smith <sesquized@sbcglobal.net> wrote:
  

I wonder whether this error is an example of the language being defined more
restrictively than required.  What is the reason that I get these results?

type a  = int -> one -> int and one = Unused | One of a;;
type b = int -> b -> int

type a is accepted while type b is not. (b gives "The type abbreviation b is
cyclic"  However, in the uses that I intended, there won't be any actual
difference between the two.

I'd appreciate an explanation about why there is difference  between a and
b.

Thanks

Bill Smith

Re: [Caml-list] type abbreviation is cyclic

[Dmitri Boulytchev]

    We intensively use -rectypes option. The "pattern" we've found to be
handy is like that:

    type 'a p =
       | Add    of 'a * ' a
       | Sub     of 'a * 'a
       | Neg    of 'a
       | Const of int
    and t = t p (* we need rectypes here *)

    let map f = function
       | Add (x, y) -> Add (f x, f y)
       | Sub  (x, y) -> Sub  (f x, f y)
       | Neg x        -> Neg (f x)
       | Const x     -> Const x

    let rec toString x =
       match map toString x with
       | Add (a, b) -> a ^ " + " ^ b
       | Sub  (a, b) -> a ^ " - " ^ b
       | Neg  a      ->  "-" ^ a
       | Const x    -> string_of_int x

    let rec eval x =
       match map eval x with
       | Add (a, b) -> a + b
       | Sub  (a, b) -> a - b
       | Neg  a      -> -a
       | Const x    -> x

    etc.

    Although this may look useless at a first glance we have some profit
since we bother about
correct applications of function only when writing map. In this very
example it may not be obvious
but when the number of "phantom" parameters grows (type ('expr, 'stmt,
'process, 'handler) something = ...)
the code becomes much more transparent.

    We use -rectypes together with recursive modules in a rather large
project (>30 000 loc) and
all works well.

    Best regards,
    Dmitry Boulytchev,
    St.Petersburg State University.
   

>On Wednesday 24 October 2007 19:09:13 Till Varoquaux wrote:
>  
>
>>...
>>AFAIK -rectypes doesn't break any of the programs working before but
>>if you attend to use it you will probably run in problems with type
>>inference (not polymorphic enough). I would recommend steering clear
>>of it for anything else than toy programs.
>>    
>>
>
>You used to be able to get the OCaml compiler to segfault by using -rectypes 
>inconsistently while compiling. I believe that -rectypes can be useful. For 
>example, the OCaml implementations of the ray tracer benchmark use it to good 
>effect to implement the scene tree without an extra level of indirection. I 
>have never bothered turning it on for any significant projects or during 
>development though, so I can't say with any certainty whether or not it has a 
>practical impact on error messages.
>
>  
>

Re: [Caml-list] type abbreviation is cyclic

[Dmitri Boulytchev]

    Atleast one value of that type exists :)

    let rec x y n = (n (y+1) x) + 1
  

>Type b doesn't exactly make much sens to me.
>While I could easilly define a value of type b (fun x:int _ -> x ) I
>really don't see the point. I'm gessing you'r trying to pass a chain
>of alternative functions (In which case this seems to be the  wrong
>way).
>Could you give an exemple (without using Obj.magic) were you'd
>actually need such a type.
>On 10/24/07, William W Smith <sesquized@sbcglobal.net> wrote:
>  
>
>>I wonder whether this error is an example of the language being defined more
>>restrictively than required.  What is the reason that I get these results?
>>
>>type a  = int -> one -> int and one = Unused | One of a;;
>>type b = int -> b -> int
>>
>>type a is accepted while type b is not. (b gives "The type abbreviation b is
>>cyclic"  However, in the uses that I intended, there won't be any actual
>>difference between the two.
>>
>>I'd appreciate an explanation about why there is difference  between a and
>>b.
>>
>>Thanks
>>
>>Bill Smith
>>
>>_______________________________________________
>>Caml-list mailing list. Subscription management:
>>http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>>Archives: http://caml.inria.fr
>>Beginner's list:
>>http://groups.yahoo.com/group/ocaml_beginners
>>Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>>
>>    
>>
>
>
>  
>

Re: [Caml-list] type abbreviation is cyclic

[Dmitri Boulytchev]

... and you can overcome this restriction with -rectypes option of course :)

    BR
    DB
    SPBSU

> I wonder whether this error is an example of the language being
> defined more restrictively than required.  What is the reason that I
> get these results?
>
> type a  = int -> one -> int and one = Unused | One of a;;
> type b = int -> b -> int
>
> type a is accepted while type b is not. (b gives "The type
> abbreviation b is cyclic"  However, in the uses that I intended, there
> won't be any actual difference between the two.
>
> I'd appreciate an explanation about why there is difference  between a
> and   b.
>
> Thanks
>
> Bill Smith
>
>------------------------------------------------------------------------
>
>_______________________________________________
>Caml-list mailing list. Subscription management:
>http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>Archives: http://caml.inria.fr
>Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>Bug reports: http://caml.inria.fr/bin/caml-bugs
>  
>

Re: [Caml-list] type abbreviation is cyclic

[Dmitri Boulytchev]

    As far as I remember you need atleast one constructor in order to
declare recursive type:

    type b = X of (int -> b -> int)

    BTW, you have that in your first example.

    Best regards,
    Dmitri Boulytchev,
    St.Petersburg State University.

> I wonder whether this error is an example of the language being
> defined more restrictively than required.  What is the reason that I
> get these results?
>
> type a  = int -> one -> int and one = Unused | One of a;;
> type b = int -> b -> int
>
> type a is accepted while type b is not. (b gives "The type
> abbreviation b is cyclic"  However, in the uses that I intended, there
> won't be any actual difference between the two.
>
> I'd appreciate an explanation about why there is difference  between a
> and   b.
>
> Thanks
>
> Bill Smith
>
>------------------------------------------------------------------------
>
>_______________________________________________
>Caml-list mailing list. Subscription management:
>http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>Archives: http://caml.inria.fr
>Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>Bug reports: http://caml.inria.fr/bin/caml-bugs
>  
>

Re: [Caml-list] type abbreviation is cyclic

[Jon Harrop]

On Wednesday 24 October 2007 19:09:13 Till Varoquaux wrote:
> ...
> AFAIK -rectypes doesn't break any of the programs working before but
> if you attend to use it you will probably run in problems with type
> inference (not polymorphic enough). I would recommend steering clear
> of it for anything else than toy programs.

You used to be able to get the OCaml compiler to segfault by using -rectypes 
inconsistently while compiling. I believe that -rectypes can be useful. For 
example, the OCaml implementations of the ray tracer benchmark use it to good 
effect to implement the scene tree without an extra level of indirection. I 
have never bothered turning it on for any significant projects or during 
development though, so I can't say with any certainty whether or not it has a 
practical impact on error messages.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] type abbreviation is cyclic

[Till Varoquaux]

Yes,
This used to be a FAQ entry: unless you pass the -rectypes option to
ocaml you have to pass through a constructor (record variant...) to
break your recursion, this prevents writing empty types such as:
type pb = pb * pb
You can still write infinite recursive definitions :
type a = Succ of a;;
let rec infinity = Succ infinity;;

AFAIK -rectypes doesn't break any of the programs working before but
if you attend to use it you will probably run in problems with type
inference (not polymorphic enough). I would recommend steering clear
of it for anything else than toy programs.
Till
On 10/24/07, Brian Hurt <bhurt@janestcapital.com> wrote:
> William W Smith wrote:
>
> > I wonder whether this error is an example of the language being
> > defined more restrictively than required.  What is the reason that I
> > get these results?
> >
> > type a  = int -> one -> int and one = Unused | One of a;;
> > type b = int -> b -> int
> >
> > type a is accepted while type b is not. (b gives "The type
> > abbreviation b is cyclic"  However, in the uses that I intended, there
> > won't be any actual difference between the two.
> >
> > I'd appreciate an explanation about why there is difference  between a
> > and   b.
>
>
> I *think* this has to do with being able to bottom out data structures.
> I mean, consider the following two (similiar) types:
>
> type a = int * one * int and one = Unused | One of a;;
> type b = int * b * int;;
>
> How do you specify a limited-length member of type b?  You can with a
> just by inserting Unused in the correct location.  But there's no such
> "stopping point" for b.
>
> This makes more sense when you make the linked-list aspect more plain:
>
> type a = int * next and next = EmptyList | Cons of a;;
> type b = int * b;;
>
> Hopefully someone more knowledgeable than I will post an actual
> type-theoretical reason this is so, but this is the pragmatic reason
> I've found.
>
> Brian
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>


-- 
http://till-varoquaux.blogspot.com/

Re: [Caml-list] type abbreviation is cyclic

[Brian Hurt]

William W Smith wrote:

> I wonder whether this error is an example of the language being 
> defined more restrictively than required.  What is the reason that I 
> get these results?
>
> type a  = int -> one -> int and one = Unused | One of a;;
> type b = int -> b -> int
>
> type a is accepted while type b is not. (b gives "The type 
> abbreviation b is cyclic"  However, in the uses that I intended, there 
> won't be any actual difference between the two.
>
> I'd appreciate an explanation about why there is difference  between a 
> and   b.


I *think* this has to do with being able to bottom out data structures.  
I mean, consider the following two (similiar) types:

type a = int * one * int and one = Unused | One of a;;
type b = int * b * int;;

How do you specify a limited-length member of type b?  You can with a 
just by inserting Unused in the correct location.  But there's no such 
"stopping point" for b.

This makes more sense when you make the linked-list aspect more plain:

type a = int * next and next = EmptyList | Cons of a;;
type b = int * b;;

Hopefully someone more knowledgeable than I will post an actual 
type-theoretical reason this is so, but this is the pragmatic reason 
I've found.

Brian

Re: [Caml-list] type abbreviation is cyclic

[Till Varoquaux]

Type b doesn't exactly make much sens to me.
While I could easilly define a value of type b (fun x:int _ -> x ) I
really don't see the point. I'm gessing you'r trying to pass a chain
of alternative functions (In which case this seems to be the  wrong
way).
Could you give an exemple (without using Obj.magic) were you'd
actually need such a type.
On 10/24/07, William W Smith <sesquized@sbcglobal.net> wrote:
> I wonder whether this error is an example of the language being defined more
> restrictively than required.  What is the reason that I get these results?
>
> type a  = int -> one -> int and one = Unused | One of a;;
> type b = int -> b -> int
>
> type a is accepted while type b is not. (b gives "The type abbreviation b is
> cyclic"  However, in the uses that I intended, there won't be any actual
> difference between the two.
>
> I'd appreciate an explanation about why there is difference  between a and
> b.
>
> Thanks
>
> Bill Smith
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>


-- 
http://till-varoquaux.blogspot.com/