[Caml-list] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Caml-list] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Nuutti Kotivuori]

I am wondering, does OCaml provide any variant of being able to
bypass the normal function call and return discipline?

More or less generic implementations of this can be seen in for
example Python's yield instruction, Lisp's call-cc or call with
current continuation, or C's setjmp/longjmp.

And if not, what are the chances of something like that seeing the
light of day in the future? Are there any fundamental problems in
OCaml that would make the implementation of such a thing exceedingly
difficult?

Just curiosity at this point.

-- Naked

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Oleg Trott]

On Tuesday 16 December 2003 08:13 am, Nuutti Kotivuori wrote:
> I am wondering, does OCaml provide any variant of being able to
> bypass the normal function call and return discipline?
>
> More or less generic implementations of this can be seen in for
> example Python's yield instruction, Lisp's call-cc or call with
> current continuation, or C's setjmp/longjmp.

call/cc is Scheme, Common Lisp has "throw" instead, and ML has "raise".

> And if not, what are the chances of something like that seeing the
> light of day in the future? Are there any fundamental problems in
> OCaml that would make the implementation of such a thing exceedingly
> difficult?
>
> Just curiosity at this point.


-- 
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Nuutti Kotivuori]

I've lumped together a bunch of answers to not spam the list too much.

Oleg Trott wrote:
> call/cc is Scheme, Common Lisp has "throw" instead, and ML has
> "raise".

Thanks for the reply, but I was aware that OCaml has exceptions.

Seth J. Fogarty wrote:
> Um.... does lisp have call/cc, I thought that was only scheme? But
> in any case, look at exceptions. They provide a very similar control
> flow arrangement to continuations (although they are weaker).

Thanks.

Ville-Pertti Keinonen wrote:
> There are many different things you could be referring to, some of
> which OCaml does have (exceptions), some of which it doesn't
> (coroutines, first-class continuations, generators etc.).

Well, indeed it was the three latter examples you gave that I was
looking for.

> First-class, capturable continuations are one of the things I often
> wish OCaml had, but implementing them efficiently would require
> significant changes to the execution model.
>
> SML/NJ has efficient first-class continuations, so it's clearly
> possible, even in the presence of native compilation and exceptions.

That's nice to know! Yes, I'd wish for capturable continuations as
well - but living without them is certainly possible.

Brian Hurt wrote:
> By my measurements, Ocaml's exceptions are faster than C's
> setjmp/longjmp.  Ocaml doesn't provide first-class continuations,
> but most of the things people actually do with call-cc can be done
> in other ways in Ocaml.  I don't know what Python's yield
> instruction does.

Ah yes, I should have been more specific. I was looking for things
that are possible with first-class continuations - but also something
weaker, as Python's yield.

> What do you want to do?

Well, what I was looking for is a way to suspend the execution of
something, and come back to it later. Exceptions provide me a way from
getting out of odd places, but not a way back in those odd places.

Python's yield is just a limited form of suspending executing
something, and continuing it later.

-- Naked

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Ville-Pertti Keinonen]

On Dec 16, 2003, at 3:13 PM, Nuutti Kotivuori wrote:

> I am wondering, does OCaml provide any variant of being able to
> bypass the normal function call and return discipline?

There are many different things you could be referring to, some of 
which OCaml does have (exceptions), some of which it doesn't 
(coroutines, first-class continuations, generators etc.).

> And if not, what are the chances of something like that seeing the
> light of day in the future? Are there any fundamental problems in
> OCaml that would make the implementation of such a thing exceedingly
> difficult?

First-class, capturable continuations are one of the things I often 
wish OCaml had, but implementing them efficiently would require 
significant changes to the execution model.

SML/NJ has efficient first-class continuations, so it's clearly 
possible, even in the presence of native compilation and exceptions.

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Kenneth Knowles]

SML/NJ is a continuation-passing style compiler, so they are trivial.  It is
"possible, even in the presence of native compilation exceptions," but in a
traditiional call stack compilation it requires some sort of stack copying,
making them extremely inefficient.  (in SML/NJ every program is slower, while
continuations have almost no penalty)

There may be new tricks for avoiding copying of the whole stack, but I wouldn't
hold your breath for continuations in ocaml.

-Kenn

On Tue, Dec 16, 2003 at 03:48:11PM +0200, Ville-Pertti Keinonen wrote:
> 
> On Dec 16, 2003, at 3:13 PM, Nuutti Kotivuori wrote:
> 
> >I am wondering, does OCaml provide any variant of being able to
> >bypass the normal function call and return discipline?
> 
> There are many different things you could be referring to, some of 
> which OCaml does have (exceptions), some of which it doesn't 
> (coroutines, first-class continuations, generators etc.).
> 
> >And if not, what are the chances of something like that seeing the
> >light of day in the future? Are there any fundamental problems in
> >OCaml that would make the implementation of such a thing exceedingly
> >difficult?
> 
> First-class, capturable continuations are one of the things I often 
> wish OCaml had, but implementing them efficiently would require 
> significant changes to the execution model.
> 
> SML/NJ has efficient first-class continuations, so it's clearly 
> possible, even in the presence of native compilation and exceptions.
> 
> -------------------
> 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

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Richard Jones]

Perhaps I'm being stupid here, but isn't it possible to get a similar
effect (some would say a more comprehensible effect) by writing your
own OCaml bindings for the makecontext/setcontext/getcontext family of
functions?

Granted this would not be portable beyond Linux and Solaris, but who
cares too much about that?

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://freshmeat.net/users/rwmj
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
MOD_CAML lets you run type-safe Objective CAML programs inside the Apache
webserver. http://www.merjis.com/developers/mod_caml/

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Ville-Pertti Keinonen]

On Dec 16, 2003, at 6:45 PM, Richard Jones wrote:

> Perhaps I'm being stupid here, but isn't it possible to get a similar
> effect (some would say a more comprehensible effect) by writing your
> own OCaml bindings for the makecontext/setcontext/getcontext family of
> functions?

They are unsafe and rather limited.  If you'd be willing to go to the 
trouble to make them safe, you might as well implement continuations 
which are more capable anyhow.

> Granted this would not be portable beyond Linux and Solaris, but who
> cares too much about that?

Lots of people.

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Brian Hurt]

On Tue, 16 Dec 2003, Nuutti Kotivuori wrote:

> I am wondering, does OCaml provide any variant of being able to
> bypass the normal function call and return discipline?
> 
> More or less generic implementations of this can be seen in for
> example Python's yield instruction, Lisp's call-cc or call with
> current continuation, or C's setjmp/longjmp.

By my measurements, Ocaml's exceptions are faster than C's setjmp/longjmp.  
Ocaml doesn't provide first-class continuations, but most of the things 
people actually do with call-cc can be done in other ways in Ocaml.  I 
don't know what Python's yield instruction does.

> 
> And if not, what are the chances of something like that seeing the
> light of day in the future? Are there any fundamental problems in
> OCaml that would make the implementation of such a thing exceedingly
> difficult?

What do you want to do?

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Dustin Sallings]

On Dec 16, 2003, at 10:42, Brian Hurt wrote:

> By my measurements, Ocaml's exceptions are faster than C's 
> setjmp/longjmp.
> Ocaml doesn't provide first-class continuations, but most of the things
> people actually do with call-cc can be done in other ways in Ocaml.  I
> don't know what Python's yield instruction does.

Simple example:

from __future__ import generators

def number(max):
     for i in range(max):
         if(i % 2 == 0):
             yield i, "Even"
         else:
             yield i, "Odd"

for n in number(10):
     print n

	The output of this example is as follows:

(0, 'Even')
(1, 'Odd')
(2, 'Even')
(3, 'Odd')
(4, 'Even')
(5, 'Odd')
(6, 'Even')
(7, 'Odd')
(8, 'Even')
(9, 'Odd')

	It's basically a special case of an upward continuation (or is it 
downward? I'm bad with terminology).  I think you can get pretty close 
to this behavior with streams, but it's still not as easy as a return 
statement that has a resume type thing.

-- 
Dustin Sallings

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[ijtrotts]

On Tuesday 16 December 2003 10:10, Dustin Sallings wrote:
> On Dec 16, 2003, at 10:42, Brian Hurt wrote:
> > By my measurements, Ocaml's exceptions are faster than C's
> > setjmp/longjmp.
> > Ocaml doesn't provide first-class continuations, but most of the things
> > people actually do with call-cc can be done in other ways in Ocaml.  I
> > don't know what Python's yield instruction does.
>
> Simple example:
>
> from __future__ import generators
>
> def number(max):
>      for i in range(max):
>          if(i % 2 == 0):
>              yield i, "Even"
>          else:
>              yield i, "Odd"
>
> for n in number(10):
>      print n
>
> 	The output of this example is as follows:
>
> (0, 'Even')
> (1, 'Odd')
> (2, 'Even')
> (3, 'Odd')
> (4, 'Even')
> (5, 'Odd')
> (6, 'Even')
> (7, 'Odd')
> (8, 'Even')
> (9, 'Odd')
>
> 	It's basically a special case of an upward continuation (or is it
> downward? I'm bad with terminology).  I think you can get pretty close
> to this behavior with streams, but it's still not as easy as a return
> statement that has a resume type thing.
  
Why not do this:

# let rec number() =
   let i=ref(-1) in fun() ->
    incr i; 
    !i, if !i mod 2 = 0 then "Even" else "Odd";;
val number : unit -> unit -> int * string = <fun>
# let n=number();;
val n : unit -> int * string = <fun>
# Array.init 10 (fun _ -> n());;
- : (int * string) array =
[|(0, "Even"); (1, "Odd"); (2, "Even"); (3, "Odd"); (4, "Even"); (5, "Odd");
  (6, "Even"); (7, "Odd"); (8, "Even"); (9, "Odd")|]

?

Issac


-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Dustin Sallings]

On Dec 16, 2003, at 22:30, ijtrotts@ucdavis.edu wrote:

> Why not do this:
>
> # let rec number() =
>    let i=ref(-1) in fun() ->
>     incr i;
>     !i, if !i mod 2 = 0 then "Even" else "Odd";;
> val number : unit -> unit -> int * string = <fun>
> # let n=number();;
> val n : unit -> int * string = <fun>
> # Array.init 10 (fun _ -> n());;
> - : (int * string) array =
> [|(0, "Even"); (1, "Odd"); (2, "Even"); (3, "Odd"); (4, "Even"); (5, 
> "Odd");
>   (6, "Even"); (7, "Odd"); (8, "Even"); (9, "Odd")|]
>
> ?
>
> Issac

	That's nice.  Given this type of construct and raise, is there 
anything you can do with a continuation that would really be missed?  
(I'm showing my ignorance of the value of call/cc)

--
SPY                      My girlfriend asked me which one I like better.
pub  1024/3CAE01D5 1994/11/03 Dustin Sallings <dustin@spy.net>
|    Key fingerprint =  87 02 57 08 02 D0 DA D6  C8 0F 3E 65 51 98 D8 BE
L_______________________ I hope the answer won't upset her. ____________

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Falk Hueffner]

ijtrotts@ucdavis.edu writes:

> Why not do this:
> 
> # let rec number() =
>    let i=ref(-1) in fun() ->
>     incr i; 
>     !i, if !i mod 2 = 0 then "Even" else "Odd";;
> val number : unit -> unit -> int * string = <fun>
> # let n=number();;
> val n : unit -> int * string = <fun>
> # Array.init 10 (fun _ -> n());;
> - : (int * string) array =
> [|(0, "Even"); (1, "Odd"); (2, "Even"); (3, "Odd"); (4, "Even"); (5, "Odd");
>   (6, "Even"); (7, "Odd"); (8, "Even"); (9, "Odd")|]

This only works for simple examples. Try for example writing a
function which successively yields all possible moves for a chess
board. The "yield" operator really helps there.

-- 
	Falk

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Pierre Weis]

[...]
> This only works for simple examples. Try for example writing a
> function which successively yields all possible moves for a chess
> board. The "yield" operator really helps there.

Very interesting: please give us the code corresponding to this
example, in order for us to realize how the full power of the "yield"
operator helps to solve this problem.

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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Falk Hueffner]

Pierre Weis <pierre.weis@inria.fr> writes:

> [...]
> > This only works for simple examples. Try for example writing a
> > function which successively yields all possible moves for a chess
> > board. The "yield" operator really helps there.
> 
> Very interesting: please give us the code corresponding to this
> example, in order for us to realize how the full power of the "yield"
> operator helps to solve this problem.

I don't really know Python well (nor chess)... it would probably look
similar to:

def moves(board):
  for x in range(0, 8):
    for y in range(0, 8):
      if board.at(x, y) == PAWN:
        yield Move(x, y, x + 1)
      elif board.at(x, y) == ROOK:
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
          n = 0
          while is_on_board(x + n*dx, y + n*dy):
            yield Move(x, y, x + n*dx, y + n*dy)
            n += 1
      ...

-- 
	Falk

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[David Brown]

On Wed, Dec 17, 2003 at 08:14:21PM +0100, Pierre Weis wrote:
> [...]
> > This only works for simple examples. Try for example writing a
> > function which successively yields all possible moves for a chess
> > board. The "yield" operator really helps there.
> 
> Very interesting: please give us the code corresponding to this
> example, in order for us to realize how the full power of the "yield"
> operator helps to solve this problem.

Perhaps this isn't the best example, since the problem is so large.

The icon language has been around with a similar operator for quite a
while.  It is very useful for prolog-type backtracking, since the code
can be written fairly naturally.

However, this construct is fairly easy to implement in regular OCaml.

The following works, but requires -rectypes to compile:

  open Printf
   
  type 'a thump = 'a * (unit -> 'a thump)
   
  (* Return the numbers a through b and stop. *)
  let through a b () : int thump =
    let rec loop num () =
      if num > b then raise End_of_file;
      num, loop (num + 1) in
    loop a ()
    
  (* Sample to show the results. *)
  let show () =
    let rec loop op =
      let num, op = op () in
      printf "%d," num;
      loop op in
    try loop (through 1 10)
    with End_of_file ->
      printf "\n"
    
  let () = show ()

With a bit more work, you can write it without needing the rectypes.  If
the construct is needed, perhaps it could be done in ocamlp4.  It would
probably have to rewrite the iterative constructs recursively, though.

Dave

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Nicolas Cannasse]

> [...]
> > This only works for simple examples. Try for example writing a
> > function which successively yields all possible moves for a chess
> > board. The "yield" operator really helps there.
>
> Very interesting: please give us the code corresponding to this
> example, in order for us to realize how the full power of the "yield"
> operator helps to solve this problem.
>
> Pierre Weis
>

One simple sample is tree walking :
"if there was yield in ocaml"

type 'a tree =
    |  Node of 'a tree list
    |  Leaf of 'a

let rec iterator = function
    | Node l -> List.iter iterator l
    | Leaf x -> yield x

Doing it using a closure is more difficult, since we need to reproduce the
stack using a data structure. That goes of course for all recursive data
structures.

Nicolas Cannasse

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[David Brown]

On Thu, Dec 18, 2003 at 10:14:19AM +0900, Nicolas Cannasse wrote:

> type 'a tree =
>     |  Node of 'a tree list
>     |  Leaf of 'a
> 
> let rec iterator = function
>     | Node l -> List.iter iterator l
>     | Leaf x -> yield x
> 
> Doing it using a closure is more difficult, since we need to reproduce the
> stack using a data structure. That goes of course for all recursive data
> structures.

Ocaml does help us a bit by sort of having lazy functionality.  Remember
that lazy (expr) is roughly equivalent to (fun () -> expr), and is
equivalent in the case where Lazy.force is only called once.  The
closures are very capable of representing the recursive structure, right
in the closures them selves.

What makes this a little complicated is that your definitions make calls
to things like List.iter, which are not defined for lazy lists.  The
first thing to do, is rewrite your function to just return a list of the
results.  This could be done directly in Haskell, and the lazy
evaluation would give you exactly what you want.

  let rec iterator = function
    | Node l -> List.flatten (List.map iterator l)
    | Leaf x -> [x]

To make this lazy, we need to define our own lazy list type.  This is a
lot cleaner than the implicit closures I posted previously, since the
conversion to lazy form is fairly straightforward.  The thing that makes
this tricky is that we are mixing lazy with regular lists.  First, let's
rewrite the needed list functions (flatten, map, and append)
appropriately for the combination of regular and lazy lists we are
using.

  let rec lazy_map f = function
    | [] -> Nil
    | a::l ->
        let r = f a in
        Pair (r, lazy (lazy_map f l))

  let rec lazy_append l r = match l with
    | Nil -> r
    | Pair (a, ar) ->
        Pair (a, lazy (lazy_append (Lazy.force ar) r))

  let rec lazy_flatten = function
    | Nil -> Nil
    | Pair (l, r) ->
        lazy_append l (lazy_flatten (Lazy.force r))

Now we can directly rewrite your above iterator in a lazy fashion:

  let rec lazy_iterator = function
    | Node l -> lazy_flatten (lazy_map lazy_iterator l)
    | Leaf x -> Pair (x, lazy (Nil))

The following code shows that it indeed works:

  let rec force_iter f = function
    | Nil -> ()
    | Pair (a, l) ->
        f a;
        force_iter f (Lazy.force l)

  let showb () =
    let flat = lazy_iterator sample_tree in
    force_iter (fun x -> printf "%d," x) flat;
    printf "\n"

  let () = showb ()

Coming up with some good lazy data structures (lists are often enough)
and possibly some ocamlp4 grammar to make them as easy to use as regular
lists would be sufficient for this kind of problem.

A good exercise would be to rewrite all of this using a
continuation-passing style.

Dave

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Brian Hurt]

On Thu, 18 Dec 2003, Nicolas Cannasse wrote:

> > [...]
> > > This only works for simple examples. Try for example writing a
> > > function which successively yields all possible moves for a chess
> > > board. The "yield" operator really helps there.
> >
> > Very interesting: please give us the code corresponding to this
> > example, in order for us to realize how the full power of the "yield"
> > operator helps to solve this problem.
> >
> > Pierre Weis
> >
> 
> One simple sample is tree walking :

[snip example of a usefull yield]

> Doing it using a closure is more difficult, since we need to reproduce the
> stack using a data structure. That goes of course for all recursive data
> structures.
> 

Stupid question: would it be possible/usefull to have the yielding 
function run as a seperate thread of execution, in a produce/consumer sort 
of way?

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[David Brown]

On Thu, Dec 18, 2003 at 01:05:20AM -0600, Brian Hurt wrote:

> > Doing it using a closure is more difficult, since we need to reproduce the
> > stack using a data structure. That goes of course for all recursive data
> > structures.
> > 
> 
> Stupid question: would it be possible/usefull to have the yielding 
> function run as a seperate thread of execution, in a produce/consumer sort 
> of way?

Yes.  But if the computation per context switch is low a large portion
of the CPU will be spent doing the context switches.

Dave

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[brogoff]

On Thu, 18 Dec 2003, Nicolas Cannasse wrote:
> > [...]
> > > This only works for simple examples. Try for example writing a
> > > function which successively yields all possible moves for a chess
> > > board. The "yield" operator really helps there.
> >
> > Very interesting: please give us the code corresponding to this
> > example, in order for us to realize how the full power of the "yield"
> > operator helps to solve this problem.
> >
> > Pierre Weis
> >
>
> One simple sample is tree walking :
> "if there was yield in ocaml"
>
> type 'a tree =
>     |  Node of 'a tree list
>     |  Leaf of 'a
>
> let rec iterator = function
>     | Node l -> List.iter iterator l
>     | Leaf x -> yield x

I think this problem is relatively easily handled by the simple home made
lazy lists I described before, available even in SML or Lisp.

The canonical problem of this class is the "same fringe" problem for trees,
where you'd like to compare the tree fringe but not have to build the entire
fringe and do all of the comparisons, but just walk the tree and bail after the
first inequality. I've appended the code of a simple polymorphic generator
module, and two different tree representations to test samefringe on. I believe
that the code is not much longer than the equivalent Sather code, if we take for
granted that the generator code is part of the library.

If this kind of stuff interests you, I suggest you also check out "zippers", and
the paper called "That About Wraps It Up" on using Y in ML programming. The
first, because the notion of "whole + context" is a useful one for traversing
and manipulating data structures in a functional style, the second because you
would like to know about simulating coroutines with first class functions.

Of course, OCaml also has support for laziness with both Lazy (an lazy) as well
as streams which offer other approaches, but I think the simple stuff buys you a
lot of what iterators do.

-- Brian

module Generator =
  struct
     type  'a t = Nil | Cons of 'a * (unit -> 'a t)

     (* Equality of two generators *)

     let rec eq lz1 lz2 =
       match (lz1,lz2) with
         Nil, Nil -> true
       | Cons (v1,f1), Cons (v2,f2) -> (v1 = v2) && eq (f1()) (f2())
       | _ -> false

     exception Empty

     let make_nil () = Nil

     let make x = Cons (x, make_nil)

    (* Combines two generators *)

     let rec concat f g =
       match f () with
         Nil -> g ()
       | Cons(x,h) -> Cons(x, fun () -> concat h g)

    (* Return the first item of the generator paired with the rest *)

     let yield : 'a t -> 'a * 'a t = function
         Nil -> raise Empty
       | Cons(x,h) -> x, (h ())
  end;;

module Tree =
  struct

    (* A generic binary tree data type
    *)
    type 'a t = Leaf of 'a | Node of 'a t list

    let make_leaf x = Leaf x
    let make l = Node l

    let rec fringe = function
        Leaf(x) -> Generator.make x
      | Node[] -> Generator.Nil
      | Node(x::xs) ->
          Generator.concat (fun () -> fringe x) (fun () -> fringe (Node xs))

    let samefringe t1 t2 = Generator.eq (fringe t1) (fringe t2)
  end;;

module BinaryTree =
  struct

    (* A generic binary tree data type
    *)
    type 'a t = Leaf of 'a | Node of 'a t * 'a t

    let make_leaf x = Leaf x
    let make l r = Node(l,r)

    let rec fringe = function
        (Leaf x) -> Generator.make x
      | (Node(l,r)) ->
          Generator.concat (fun () -> fringe l) (fun () -> fringe r);;

    let samefringe t1 t2 = Generator.eq (fringe t1) (fringe t2)
  end;;


-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[brogoff]

On 17 Dec 2003, Falk Hueffner wrote:
> ijtrotts@ucdavis.edu writes:
>
> > Why not do this:
> >
> > # let rec number() =
> >    let i=ref(-1) in fun() ->
> >     incr i;
> >     !i, if !i mod 2 = 0 then "Even" else "Odd";;
> > val number : unit -> unit -> int * string = <fun>
> > # let n=number();;
> > val n : unit -> int * string = <fun>
> > # Array.init 10 (fun _ -> n());;
> > - : (int * string) array =
> > [|(0, "Even"); (1, "Odd"); (2, "Even"); (3, "Odd"); (4, "Even"); (5, "Odd");
> >   (6, "Even"); (7, "Odd"); (8, "Even"); (9, "Odd")|]
>
> This only works for simple examples. Try for example writing a
> function which successively yields all possible moves for a chess
> board. The "yield" operator really helps there.

While I think yield is pretty cool, having used in Sather, which got in from CLU
I believe,you can simulate this control flow and more using higher order
functions. Sticking with the simple example, but ditching the array and rolling
my own streams with core ML yields (ha!)

type  'a generator = Nil | Cons of 'a * (unit -> 'a generator);;

let rec odd_even i j =
  if i > j then
    Nil
  else
    Cons(i, (fun () -> odd_even (succ i) j));;

let rec print_upto n = function
    Nil -> ()
  | Cons(i, f) ->
      if i <= n then
	let s = if i mod 2 = 0 then "EVEN" else "ODD" in
        (Printf.printf "(%i, %s)\n" i s;
          print_upto n (f()))
      else
        ();;

which has similar semantics to the Python yield, except that the generator is
not consumed during the traversal. It should be obvious how to encode that
behavior by modifying print_upto to return the remaining generator.

In any case, programming this kind of thing in ML is pretty easy, so I don't
think we need an extension to the language for yield. callcc is more powerful,
but I don't like the possibility that making callcc fast penalizes code which
doesn't use it. We have exceptions and threads already.

-- Brian


-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[skaller]

On Thu, 2003-12-18 at 06:42, brogoff@speakeasy.net wrote:
> On 17 Dec 2003, Falk Hueffner wrote:

> In any case, programming this kind of thing in ML is pretty easy, so I don't
> think we need an extension to the language for yield. callcc is more powerful,
> but I don't like the possibility that making callcc fast penalizes code which
> doesn't use it. We have exceptions and threads already.

Felix provides the converse of yield -- read.
yield returns a value, saving the current position.
Read yields *expecting* a value, saving the current
position.

I'd sure like to know how to do that in (Oca)ML easily
(without using threads).

In particular, take some aritrary program that
reads a structured file 

	read stuff .. do something
	read stuff do something
	if condition
		read stuff ..
	else
		read ...

	for loop .. subroutine calls


and do that in ML 'easily'... I don't think
the transformation is all that easy to do by
hand. 

(Felix does this transformation mechanically,
so I have an idea what is required, the details
are trivial .. the amount of transforming
is quite laborious though .. and possibly
unreadble .. )



-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Nuutti Kotivuori]

I'm answering to all of this with a single reply.

ijtrotts@ucdavis.edu wrote:

[...]

> Why not do this:

[...]

Falk Hueffner wrote:
> This only works for simple examples. Try for example writing a
> function which successively yields all possible moves for a chess
> board. The "yield" operator really helps there.

Pierre Weis wrote:
> Very interesting: please give us the code corresponding to this
> example, in order for us to realize how the full power of the
> "yield" operator helps to solve this problem.

David Brown wrote:
> The icon language has been around with a similar operator for quite
> a while.  It is very useful for prolog-type backtracking, since the
> code can be written fairly naturally.
>
> However, this construct is fairly easy to implement in regular
> OCaml.

brogoff@speakeasy.net wrote:
> While I think yield is pretty cool, having used in Sather, which got
> in from CLU I believe,you can simulate this control flow and more
> using higher order functions. Sticking with the simple example, but
> ditching the array and rolling my own streams with core ML yields
> (ha!)

[...]

> In any case, programming this kind of thing in ML is pretty easy, so
> I don't think we need an extension to the language for yield. callcc
> is more powerful, but I don't like the possibility that making
> callcc fast penalizes code which doesn't use it. We have exceptions
> and threads already.

I guess the main point about all this is that there are situations
where having first-class continuations, or being able to yield, leads
to code that is more natural.

OCaml is a nice language with plenty of choices for using streams,
higher order functions, threads and the like to achieve the same
effect, so there certainly is no burning need for the features.

I found a nice paper on the usage of call/cc, that explains
coroutines, re-entry and multitasking implemented with that. It's
here:

  http://lambda.weblogs.com/discuss/msgReader$3056

A personal example of what I am thinking of would be to have a long
function which does a lot of stuff, but requires some external input
at times - and it would be nice if the system would just suspend the
evaluation until that input comes available.

Now I can think of several ways to do this.

I could just split the function into several parts, and have them get
a state as a parameter that's returned from the previous function and
given to the next - and the state holds all the context required for
it. Or have an object do the same thing.

I could have it all in one function, but have the function return
closures for the rest of the code, with the wanted input being the
parameter of. That is, simply nesting the functions - then the state
is carried in the local environment of the functions.

I could have it as a separate thread, blocking on input from an event
channel, and that channel would be fed the external inputs when they
become available.

And a whole bunch of more things - but the most natural way would be
just write it all in one function, straight through, with a call that
could be used for fetching the inputs when they become
available. Going for the separate thread model makes the resulting
code look just the same, since it would be a blocking call only, and
this would look like a blocking call - but the thread produces a whole
lot of other issues.

Now, I can do this with call/cc - and I can do it with yield, albeit
clumsily - and I can do it with setjmp/longjmp. Hence my question.

For my part, my curiosity is fulfilled - I will just work around the
issues. If someone is implementing something allowing this into OCaml,
my curiosity rises again :)

Thanks for all the replies, they were very helpful.
-- Naked

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Kevin S. Millikin]

On Tuesday, December 16, 2003 9:42 AM, Kenneth Knowles 
[SMTP:kknowles@uclink.berkeley.edu] wrote:

> SML/NJ is a continuation-passing style compiler, so they are trivial.
> It is "possible, even in the presence of native compilation
> exceptions," but in a traditiional call stack compilation it requires
> some sort of stack copying, making them extremely inefficient.  (in
> SML/NJ every program is slower, while continuations have almost no
> penalty)

> There may be new tricks for avoiding copying of the whole stack, but 
I
> wouldn't hold your breath for continuations in ocaml.

You don't *have* to copy the stack on continuation capture, just mark 
the point where the continuation was captured and seal it off.  You do 
have to copy stack frames (but not the whole stack)---on continuation 
restore or upon stack segment underflow.

Programs that use continuations are (for the most part) the ones that 
pay the price, and they pay that (bounded) price upon continuation 
invocation or returning past a captured continuation.

For details on these new tricks, you can read Hieb, Dybvig, and 
Bruggeman's 1990 PLDI paper.

----
Kevin S. Millikin           Architecture Technology Corporation
Research Scientist          Specialists in Computer Architecture
(952)829-5864 x162          http://www.atcorp.com

-------------------
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] Python's yield, Lisp's call-cc or C's setjmp/longjmp in OCaml

[Ker Lutyn]

How about:

type 'a cont = Cont of ('a -> 'a cont)

let apply c x = match c with Cont f -> f x

let rec iterator c = function
  | Node l -> List.fold_left iterator c l
  | Leaf x -> apply c x

On Thu, Dec 18, 2003 at 10:14:19AM +0900, Nicolas Cannasse wrote:
>
> type 'a tree =
>     |  Node of 'a tree list
>     |  Leaf of 'a
> 
> let rec iterator = function
>     | Node l -> List.iter iterator l
>     | Leaf x -> yield x
> 
> Doing it using a closure is more difficult, since we need to reproduce the
> stack using a data structure. That goes of course for all recursive data
> structures.



__________________________________
Do you Yahoo!?
New Yahoo! Photos - easier uploading and sharing.
http://photos.yahoo.com/

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