[Caml-list] Is arrow programming impossible in ocaml?

[Caml-list] Is arrow programming impossible in ocaml?

[Nick Name]

Hi all, I am trying to work on a project where I need ocaml efficiency 
with rank-2 polymorphism, if I got it correctly (I am not an expert in 
programming language semantics). 

Basically I am trying to reproduce FRAN-like usage of arows as in 

http://haskell.cs.yale.edu/yampa/AFPLectureNotes.pdf

so I have defined my own arrow module etc, but I faced the rank-1 
polymorphism restriction of ocaml. I have cut down my example to:

-
type ('a,'b) t = 'a -> 'b

let rec arr f = f

let a = arr (fun x -> x)
-

and "a" is typed like '_a -> '_a , where I would like it to be typed 'a 
-> 'a.

Does anyone think I have other possibilities in writing that kind of 
higher-order combinator based code, or is it impossible?

thanks

Vincenzo

-------------------
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] Is arrow programming impossible in ocaml?

[Oleg Trott]

On Monday 13 October 2003 07:59 pm, Nick Name wrote:
> Hi all, I am trying to work on a project where I need ocaml efficiency
> with rank-2 polymorphism, if I got it correctly (I am not an expert in
> programming language semantics).
>
> Basically I am trying to reproduce FRAN-like usage of arows as in
>
> http://haskell.cs.yale.edu/yampa/AFPLectureNotes.pdf
>
> so I have defined my own arrow module etc, but I faced the rank-1
> polymorphism restriction of ocaml. I have cut down my example to:
>
> -
> type ('a,'b) t = 'a -> 'b
>
> let rec arr f = f
>
> let a = arr (fun x -> x)
> -
>
> and "a" is typed like '_a -> '_a , where I would like it to be typed 'a
> -> 'a.

I think OCaml 3.07 makes this possible

> Does anyone think I have other possibilities in writing that kind of
> higher-order combinator based code, or is it impossible?
>
> thanks
>
> Vincenzo

-- 
Oleg Trott <oleg_trott@columbia.edu>

-------------------
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] Is arrow programming impossible in ocaml?

[Jacques Garrigue]

From: Oleg Trott <oleg_trott@columbia.edu>
> On Monday 13 October 2003 07:59 pm, Nick Name wrote:
> > Hi all, I am trying to work on a project where I need ocaml efficiency
> > with rank-2 polymorphism, if I got it correctly (I am not an expert in
> > programming language semantics).
> >
> > Basically I am trying to reproduce FRAN-like usage of arows as in
> >
> > http://haskell.cs.yale.edu/yampa/AFPLectureNotes.pdf
> >
> > so I have defined my own arrow module etc, but I faced the rank-1
> > polymorphism restriction of ocaml. I have cut down my example to:

Looking at your example, this doesn't seem to be a problem with rank-2
polymorphism, but just one instance of the value restriction.
(See the FAQ on caml.inria.fr)

> > -
> > type ('a,'b) t = 'a -> 'b
> >
> > let rec arr f = f
> >
> > let a = arr (fun x -> x)
> > -
> >
> > and "a" is typed like '_a -> '_a , where I would like it to be typed 'a
> > -> 'a.
> 
> I think OCaml 3.07 makes this possible

Unfortunately, no. OCaml 3.07 recovers polymorphism only if 'a appears
only in covariant positions, and here it appears in both covariant and
contravariant position.

But as long as you represent arrows by normal functions (as this seems
to be the case in the paper), eta-expanding should solve the problem.

  let a y = arr (fun x -> x) y

Not also that there is no problem if Arr is a constructor:

  type ('a,'b) = Arr of ('a -> 'b)

  let a = Arr (fun x -> x)

Jacques Garrigue

-------------------
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] Is arrow programming impossible in ocaml?

[Nick Name]

Alle 05:02, martedì 14 ottobre 2003, Jacques Garrigue ha scritto:
> But as long as you represent arrows by normal functions (as this
> seems to be the case in the paper), eta-expanding should solve the
> problem.
>

Unfortunately I can't; I am using arrows to hide a function-like 
structure wich is more complex than functions

>   let a y = arr (fun x -> x) y
>
> Not also that there is no problem if Arr is a constructor:

I can't do this in general, either, because I need the (>>>) combinator, 
wich represents (reverse) function composition, so

type ('a,'b) t = Arr of ('a -> 'b) | Seq of ((('a,'c) t) * (('c,'b) t))

where Seq is the composition, is not writeable because I would need to 
make 'c a parameter for t, and then ('a,'c) t would no longer be valid 
etc.

Do anyone see another solution?

Thanks & bye

Vincenzo



-------------------
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] Is arrow programming impossible in ocaml?

[Jacques Garrigue]

From: Nick Name <nick.name@inwind.it>
> Alle 05:02, martedì 14 ottobre 2003, Jacques Garrigue ha scritto:
> > But as long as you represent arrows by normal functions (as this
> > seems to be the case in the paper), eta-expanding should solve the
> > problem.
> >
> 
> Unfortunately I can't; I am using arrows to hide a function-like 
> structure wich is more complex than functions
> 
> >   let a y = arr (fun x -> x) y
> >
> > Not also that there is no problem if Arr is a constructor:
> 
> I can't do this in general, either, because I need the (>>>) combinator, 
> wich represents (reverse) function composition, so
> 
> type ('a,'b) t = Arr of ('a -> 'b) | Seq of ((('a,'c) t) * (('c,'b) t))
> 
> where Seq is the composition, is not writeable because I would need to 
> make 'c a parameter for t, and then ('a,'c) t would no longer be valid 
> etc.
> 
> Do anyone see another solution?

I'm afraid you will have to state in more detail what you want to do.
Or to show some Haskell code.

What you try to do may or may not be possible, but I don't think that
the value restriction is essential to your problem.
In a first step I suppose you could assume that you have no
polymorphic identity, just identity functions at every type.

Jacques
-------------------
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] Is arrow programming impossible in ocaml?

[Nick Name]

Alle 02:22, mercoledì 15 ottobre 2003, Jacques Garrigue ha scritto:
> I'm afraid you will have to state in more detail what you want to do.
> Or to show some Haskell code.

Here it is:

module type ARROW =
sig
  type ('a,'b) t

  val arr : ('a -> 'b) -> ('a,'b) t
  val (>>>) : ('a,'b) t -> ('b,'c) t -> ('a,'c) t
  val (&&&) : ('a,'b) t -> ('a,'c) t -> ('a,('b * 'c)) t
end

module Time : sig

  include ARROW

  val time : ('a,float) t
  val run : (unit,'a) t -> float -> 'a option
  val const : 'a -> ('b,'a) t
end =
struct
  type state = (float * float)

  (* A signal transformer is a function wich takes the current time (and  
     dt) and maybe returns a value, or stops with None *)

  type ('a,'b) t = T of ((state * 'a) -> (('b * ('a,'b) t) option))

  let rec arr f = T (fun (_,x) -> Some (f x,arr f))

  let rec (>>>) (T a1) (T a2) =
    T (fun (s,x) ->
	 match a1 (s,x) with
	     None -> None
	   | Some (r1,n1) ->
	       match a2 (s,r1) with
		   None -> None
		 | Some (r2,n2) ->
		     Some (r2,n1 >>> n2))

  let rec (&&&) (T a1) (T a2) =
    T (fun arg ->
	 match (a1 arg,a2 arg) with
	     ((None,_)|(_,None)) -> None
	   | (Some (r1,n1),Some (r2,n2)) -> Some ((r1,r2),n1 &&& n2))

  let rec time = T (fun ((t,_),_) -> Some (t,time))

  let run (T f) t = 
    match f ((t,0.0),()) with
	None -> None
      | Some (r,_) -> Some r

  let const x = arr (fun _ -> x) 
end

(* now in the toplevel

  # let t = time >>> time;;
  val t : ('_a, float) Var.Time.t = <abstr> *)
 
Well, that '_a is exactly what I wish to avoid; I had this suggestion 
privately (with simplified type declarations):

# type ('a,'b) sf = Arr of ('a * float -> 'b);;
type ('a, 'b) sf = Arr of ('a * float -> 'b)
# let (>>>) f1 f2  = match f1(),f2() with (Arr f1),(Arr f2) -> Arr (fun 
(a,s) -> f2 (f1(a,s),s));;
val ( >>> ) : (unit -> ('a, 'b) sf) -> (unit -> ('b, 'c) sf) -> ('a, 'c) 
sf =
  <fun>
# let time () = Arr (fun (_,t) -> t);;
val time : unit -> ('a, float) sf = <fun>
# let t () = time >>> time;;
val t : unit -> ('a, float) sf = <fun>


and yet I don't know if it's satisfactory, however I realize that this 
is a general problem with caml view of polymorphism, probably driven by 
type-inference decidability issues; in fact I can't write a polymorphic 
compose operator in general, because I will get exactly the same 
problems.

Vincenzo

-------------------
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] Is arrow programming impossible in ocaml?

[Jacques Garrigue]

From: Nick Name <nick.name@inwind.it>

> Here it is:
> 
> module type ARROW =
> sig
>   type ('a,'b) t
> 
>   val arr : ('a -> 'b) -> ('a,'b) t
>   val (>>>) : ('a,'b) t -> ('b,'c) t -> ('a,'c) t
>   val (&&&) : ('a,'b) t -> ('a,'c) t -> ('a,('b * 'c)) t
> end

[...]

> (* now in the toplevel
> 
>   # let t = time >>> time;;
>   val t : ('_a, float) Var.Time.t = <abstr> *)
>  
> Well, that '_a is exactly what I wish to avoid;

I see.

> I had this suggestion privately (with simplified type declarations):
> 
> # type ('a,'b) sf = Arr of ('a * float -> 'b);;
> type ('a, 'b) sf = Arr of ('a * float -> 'b)
> # let (>>>) f1 f2  = match f1(),f2() with (Arr f1),(Arr f2) -> Arr (fun 
> (a,s) -> f2 (f1(a,s),s));;
> val ( >>> ) : (unit -> ('a, 'b) sf) -> (unit -> ('b, 'c) sf) -> ('a, 'c) 
> sf =
>   <fun>
> # let time () = Arr (fun (_,t) -> t);;
> val time : unit -> ('a, float) sf = <fun>
> # let t () = time >>> time;;
> val t : unit -> ('a, float) sf = <fun>
> 
> and yet I don't know if it's satisfactory.

What would be the problem?
This is just about delaying the arrow construction, to make sure that
no side-effect may occur.

> however I realize that this 
> is a general problem with caml view of polymorphism, probably driven by 
> type-inference decidability issues; in fact I can't write a polymorphic 
> compose operator in general, because I will get exactly the same 
> problems.

This has nothing to do with decidability at all!
Again, this is the value restriction, which solves a problem with
soundness in presence of side-effects, and this is a FAQ.

And you can perfectly define a polymorphic compose operator.
  # let compose f g x = f (g x);;
  val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
The only difficulty is that to create polymorphic functions with this
operator you must apply eta-expansion.
  # let swap (x,y) = (y,x);;
  val swap : 'a * 'b -> 'b * 'a = <fun>
  # fun p -> compose swap swap p;;
  - : 'a * 'b -> 'a * 'b = <fun>

By the way, if you are ready to break abstraction (which in your case
doesn't seem essential), you can build a t with the right polymorphic
type:
  # let t = T(fun s -> let T a = time >>> time in a s);;
  val t : ('a, float) Var.Time.t = ...
Not very clean, but you can replace time >>> time by any polymorphic
expression.
It can be made a bit simpler by using a record instead of a sum:
  # let t = {f=fun s -> (time >>> time).f s};;

Jacques Garrigue

-------------------
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] Is arrow programming impossible in ocaml?

[skaller]

On Wed, 2003-10-15 at 12:20, Jacques Garrigue wrote:
> From: Nick Name <nick.name@inwind.it>

> By the way, if you are ready to break abstraction (which in your case
> doesn't seem essential), you can build a t with the right polymorphic
> type:
>   # let t = T(fun s -> let T a = time >>> time in a s);;
>   val t : ('a, float) Var.Time.t = ...
> Not very clean, but you can replace time >>> time by any polymorphic
> expression.

The cleanliness can be had with camlp4 surely?


-------------------
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] Is arrow programming impossible in ocaml?

[skaller]

On Tue, 2003-10-14 at 09:59, Nick Name wrote:
> Hi all, I am trying to work on a project where I need ocaml efficiency 

> type ('a,'b) t = 'a -> 'b
> 
> let rec arr f = f
> 
> let a = arr (fun x -> x)
> -
> 
> and "a" is typed like '_a -> '_a , where I would like it to be typed 'a 
> -> 'a.
> 
> Does anyone think I have other possibilities in writing that kind of 
> higher-order combinator based code, or is it impossible?

It works fine with an annotation:
# type ('a,'b) t = 'a -> 'b
 
  let rec arr f = f
   
  let a = arr   (fun x -> x)
  ;;
type ('a, 'b) t = 'a -> 'b
val arr : 'a -> 'a = <fun>
val a : '_a -> '_a = <fun>
# let a:('a,'a) t = (fun x -> x)
  ;;
val a : ('a, 'a) t = <fun>
# a 1;;
- : int = 1
# a 1.1;;
- : float = 1.1
#


-------------------
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