[Caml-list] yet another question on lazy lists

[Caml-list] yet another question on lazy lists

[Michael Vanier]

First off, thanks very much to all of you who have helped me understand
lazy evaluation in ocaml.  Now for another question: I get a strange type
error from the following code:

(* "stream" means lazy lists for my purposes. *)
type 'a stream =
    Nil
  | Cons of 'a * 'a stream Lazy.t

let stream_cons x y = Cons (x, lazy y)

let stream_hd s =
  match s with
    Nil -> invalid_arg "stream_hd"
  | Cons (x, y) -> x

let stream_tl s =
  match s with
    Nil -> invalid_arg "stream_tl"
  | Cons (x, y) -> Lazy.force y

let rec stream_map2 proc s1 s2 =
  match (s1, s2) with
    (Cons (x1, y1), Cons (x2, y2)) ->
      Cons ((proc x1 x2), lazy (stream_map2 proc 
                                  (Lazy.force y1) 
                                  (Lazy.force y2)))
  | _ -> invalid_arg "stream_map2"
    
let add_streams s1 s2 =
  stream_map2 (+) s1 s2

(* Generating fibonacci numbers. *)

let rec fibs =
  Cons (0,
        lazy (Cons (1,
                    lazy (add_streams
                            (stream_tl fibs)
                            fibs))))


Thus far, everything works properly.  But when I try to convert the "Cons"
expressions into "stream_cons" function calls, I get a weird type error:


let rec fibs2 =
  stream_cons 0 (stream_cons 1 (add_streams (stream_tl fibs2) fibs2))

# let rec fibs2 =
    stream_cons 0 (stream_cons 1 (add_streams (stream_tl fibs2) fibs2))
    -------------------------------------------------------------------
  ;;
This kind of expression is not allowed as right-hand side of `let rec'


What does this mean?  My best guess is that ocaml sees that you're defining
a value in terms of itself (like e.g. "let rec a = 2 * a") and won't allow
it, but that doesn't explain why the lazy version works.  Does this mean
that my "stream_cons" function is useless?

Thanks in advance,

Mike

-------------------
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] yet another question on lazy lists

[Pierre Weis]

[...]
> # let rec fibs2 =
>     stream_cons 0 (stream_cons 1 (add_streams (stream_tl fibs2) fibs2))
>     -------------------------------------------------------------------
>   ;;
> This kind of expression is not allowed as right-hand side of `let rec'
> 
> What does this mean?  My best guess is that ocaml sees that you're defining
> a value in terms of itself (like e.g. "let rec a = 2 * a") and won't allow
> it, but that doesn't explain why the lazy version works.

It means right-hand side of `let rec' expressions are submitted to
conditions in order to be able to compile the recursively defined
value.

Roughly speaking, you cannot use expressions that contain function
calls, variables, or constants that are not under an explicit
(i.e. syntactic) function abstration or arguments of a construtor
application. Hence, neither let rec x = x nor let rec x = 1 is
allowed. Hence, all recursive definitions of the form let rec f =
function x -> .... are legal.

On the other hand, constructor applications are allowed (since those
are not function calls per se., and recursive values defined with
constructors are easy to compile). For instance,
# let rec x = 1 :: x;;
val x : int list =
  [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   ...]

This explains why replacing a constructor application by a function
call may turn a legal recursive definition into an illegal one. This
also explain why your previous ``lazy'' definition worked.

>  Does this mean
> that my "stream_cons" function is useless?
>
> Thanks in advance,
> 
> Mike

No. It means you cannot always use it in place of a constructor
application. Note that a similar phenomenon occurs for pattern
matching: constructors are mandatory, you cannot subtitute them by
equivalent function calls!

Best regards,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
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] yet another question on lazy lists

[William Lovas]

On Sat, Jul 06, 2002 at 05:26:33PM +0200, Pierre Weis wrote:
> >  Does this mean
> > that my "stream_cons" function is useless?
> >
> > Thanks in advance,
> > 
> > Mike
> 
> No. It means you cannot always use it in place of a constructor
> application. Note that a similar phenomenon occurs for pattern
> matching: constructors are mandatory, you cannot subtitute them by
> equivalent function calls!

Actually, i think stream_cons may be useless, due to OCaml's eager
evaluation strategy.  If you try to delegate the recursion to a function
call, the following happens:

    # let rec constant n = stream_cons n (constant n);;
    val constant : 'a -> 'a stream = <fun>
    # constant 1;;
    Stack overflow during evaluation (looping recursion?).

... but the constructor still works:

    # let rec constant n = Cons (n, lazy (constant n));;
    val constant : 'a -> 'a stream = <fun>
    # constant 1;;
    - : int stream = Cons (1, {contents = Lazy.Delayed <fun>})

The second argument needs to be treated lazily (which it is, explicitly, 
using the Cons constructor call), but stream_cons will never achieve that,
unless i'm missing something.

William

P.S. Michael, why not call your type something like `lazy_list', instead of
`stream'?  The latter conjures up images of stateful Stream.t's, for me at
least.  Just a thought!
-------------------
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] yet another question on lazy lists

[Michael Vanier]

> Date: Sat, 6 Jul 2002 14:22:52 -0400
> From: William Lovas <wlovas@stwing.upenn.edu>
> 
> On Sat, Jul 06, 2002 at 05:26:33PM +0200, Pierre Weis wrote:
> > >  Does this mean
> > > that my "stream_cons" function is useless?
> > >
> > > Thanks in advance,
> > > 
> > > Mike
> > 
> > No. It means you cannot always use it in place of a constructor
> > application. Note that a similar phenomenon occurs for pattern
> > matching: constructors are mandatory, you cannot subtitute them by
> > equivalent function calls!
> 
> Actually, i think stream_cons may be useless, due to OCaml's eager
> evaluation strategy.  If you try to delegate the recursion to a function
> call, the following happens:
> 
>     # let rec constant n = stream_cons n (constant n);;
>     val constant : 'a -> 'a stream = <fun>
>     # constant 1;;
>     Stack overflow during evaluation (looping recursion?).
> 
> ... but the constructor still works:
> 
>     # let rec constant n = Cons (n, lazy (constant n));;
>     val constant : 'a -> 'a stream = <fun>
>     # constant 1;;
>     - : int stream = Cons (1, {contents = Lazy.Delayed <fun>})
> 
> The second argument needs to be treated lazily (which it is, explicitly, 
> using the Cons constructor call), but stream_cons will never achieve that,
> unless i'm missing something.
> 
> William

You're right.  I realized this shortly after sending out the question.
Because of ocaml's eager evaluation, the whole point of 'stream_cons' is
thwarted by writing it as a function, because by definition all the
arguments to the function are evaluated.  I got confused because I was
trying to imitate some scheme code from SICP in ocaml, and there was (what
looked like) a 'stream-cons' function in the SICP code.  It turns out that
'stream-cons' has to be implemented as a macro in scheme (a point glossed
over in SICP).

> 
> P.S. Michael, why not call your type something like `lazy_list', instead of
> `stream'?  The latter conjures up images of stateful Stream.t's, for me at
> least.  Just a thought!

Right again.  This is SICP terminology.  I'll change it if I post any more
questions on this subject to this list.

Thanks for your input (and to Pierre Weis for his explanation of the error
message).

Mike
-------------------
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] yet another question on lazy lists

[John Max Skaller]

>
>
>
>Right again.  This is SICP terminology.  I'll change it if I post any more
>questions on this subject to this list.
>
My understanding is that a list is a finite inductuive type, 
characterised by constructors.
Whereas a stream is like an infinite list, but it is a coinductive type,
characterised by destructors:

    'a list = Empty | Cons of 'a * 'a list
    split ('a stream) -> 'a * 'a stream

As I understand it, the two types are formally dual.
See Charity (if you can find it)  for a language which provides
coinductive types with a natural syntax which makes the duality
syntactically evident.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




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