break and continue for OCaml

break and continue for OCaml

[Sanghyeon Seo]

I have the first cut of patch to implement break and continue inside
for and while loops for OCaml.

http://sparcs.kaist.ac.kr/~tinuviel/devel/ocaml/

Patch is against OCaml 3.10.2. All the meat is in bytecomp/bytegen.ml.
Currently bytecode only. I am working on natvie code and error
handling when break is used outside loop etc but I thought "releasing
early" could be useful.

What do you think?

-- 
Seo Sanghyeon

Re: [Caml-list] break and continue for OCaml

[Luc Maranget]

> I have the first cut of patch to implement break and continue inside
> for and while loops for OCaml.
> 
> http://sparcs.kaist.ac.kr/~tinuviel/devel/ocaml/
> 
> Patch is against OCaml 3.10.2. All the meat is in bytecomp/bytegen.ml.
> Currently bytecode only. I am working on natvie code and error
> handling when break is used outside loop etc but I thought "releasing
> early" could be useful.
> 
> What do you think?


I think that you can implement break/continue without altering
the lambda-code (file bytecomp/lambda.mli) by using the existing
'static exception' mechanism :

...
| Lstaticraise of (int * lambda list)
| Lstaticcatch of lambda * (int * Ident.t list) * lambda
...

with the following pretty printing convention (cf. option -dlambda)

 (exit i) stands for 'Lstaticraise (i,[])'
 (catch e1 with (i) e2) stands for 'Lstaticcatch (e1,(i,[]),e2)'


Then you have for instance
while e1 do e2 done ->

(catch
  (while (e1) (catch  e2 with (icont) ())
with (ibreak) ())

In the loop body e2, break is compiled into (exit ibreak)
and coninue into (exit icont).


It is a bit complicated, but then you get native code compilation for
free.

--
Luc
PS> I make no statement on whether break/continue
    should be added to ocaml!

    But..

      1. Exceptions are already here and they express more flexible
         control flow modifications.

      2. Adding keywords is something that is not easily accepted,
         because it breaks existing code.

Re: [Caml-list] break and continue for OCaml

[Jean-Christophe Filliâtre]

Sanghyeon Seo wrote:
> I have the first cut of patch to implement break and continue inside
> for and while loops for OCaml.
> 
> http://sparcs.kaist.ac.kr/~tinuviel/devel/ocaml/
> 
> Patch is against OCaml 3.10.2. All the meat is in bytecomp/bytegen.ml.
> Currently bytecode only. I am working on natvie code and error
> handling when break is used outside loop etc but I thought "releasing
> early" could be useful.
> 
> What do you think?

A comment on typing break and continue: If I read your patch correctly,
you're giving type "unit" to both expressions "break" and "continue". I
was rather expecting type 'a instead, as for "raise exn". It could be
useful in situations like this

	while ... do
	  let x = ... [if ... then break else ...] ... in
	  ...
	done

Said otherwise, break and continue can be simply encoded with exceptions

	try
	  while ... do
            try
 	      .... loop body where break is raise Break ...
	      .... and continue is raise Continue ...
	    with Continue ->
              ()
	  done
	with Break ->
	  ()

and thus should be typed the same way.

-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/

RE: [Caml-list] break and continue for OCaml

[David Allsopp]

Is there therefore any reasonable performance gain over implementing
break/continue as a camlp4 extension rather than as a compiler patch?


David


Jean-Christophe Filliâtre wrote:
> Sanghyeon Seo wrote:
> > I have the first cut of patch to implement break and continue inside
> > for and while loops for OCaml.
> > 
> > http://sparcs.kaist.ac.kr/~tinuviel/devel/ocaml/
> > 
> > Patch is against OCaml 3.10.2. All the meat is in bytecomp/bytegen.ml.
> > Currently bytecode only. I am working on natvie code and error
> > handling when break is used outside loop etc but I thought "releasing
> > early" could be useful.
> > 
> > What do you think?
>
> A comment on typing break and continue: If I read your patch correctly,
> you're giving type "unit" to both expressions "break" and "continue". I
> was rather expecting type 'a instead, as for "raise exn". It could be
> useful in situations like this
>
>	while ... do
>	  let x = ... [if ... then break else ...] ... in
>	  ...
>	done
>
> Said otherwise, break and continue can be simply encoded with exceptions
>
>	try
>	  while ... do
>             try
>  	      .... loop body where break is raise Break ...
>	      .... and continue is raise Continue ...
>	    with Continue ->
>               ()
>	  done
>	with Break ->
>	  ()
>
> and thus should be typed the same way.
>
> -- 
> Jean-Christophe Filliâtre
> http://www.lri.fr/~filliatr/

Re: [Caml-list] break and continue for OCaml

[Richard Jones]

On Thu, Apr 10, 2008 at 04:12:49PM +0200, David Allsopp wrote:
> Is there therefore any reasonable performance gain over implementing
> break/continue as a camlp4 extension rather than as a compiler patch?

The posted patch turns the break/continue into jump instructions
(well, jump bytecodes), which should be moderately faster than pushing
an exception stack frame / unwinding the stack.

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] break and continue for OCaml

[Richard Jones]

On Thu, Apr 10, 2008 at 10:59:16AM +0900, Sanghyeon Seo wrote:
> What do you think?

When you've done that, how about a type-safe return statement?  It
should immediately return from the inner-most function, allowing one
to return a value.

Here's a usage scenario (modified from Extlib, it would be even
shorter with 'break'):

  (* Find the index of string 'sub' within 'str' *)
  let find str sub =
    let sublen = String.length sub in
    if sublen = 0 then return 0;

    let len = String.length str in
    for i = 0 to len-sublen do
      let j = ref 0 in
      while String.unsafe_get str (i + !j) = String.unsafe_get sub !j do
        incr j;
        if !j = sublen then return i
      done;
    done;
    raise Not_found

Rich.

-- 
Richard Jones
Red Hat

Re: [Caml-list] break and continue for OCaml

[Martin Jambon]

On Thu, 10 Apr 2008, Richard Jones wrote:

> On Thu, Apr 10, 2008 at 10:59:16AM +0900, Sanghyeon Seo wrote:
>> What do you think?
>
> When you've done that, how about a type-safe return statement?  It
> should immediately return from the inner-most function, allowing one
> to return a value.
>
> Here's a usage scenario (modified from Extlib, it would be even
> shorter with 'break'):
>
>  (* Find the index of string 'sub' within 'str' *)
>  let find str sub =
>    let sublen = String.length sub in
>    if sublen = 0 then return 0;
>
>    let len = String.length str in
>    for i = 0 to len-sublen do
>      let j = ref 0 in
>      while String.unsafe_get str (i + !j) = String.unsafe_get sub !j do
>        incr j;
>        if !j = sublen then return i
>      done;
>    done;
>    raise Not_found

I'm OK with the intent, but what should happen in such cases:

module A =
struct
   let a = break
   let b = continue
   let c = return true
   let d = lazy (return 123)
   let e () = Lazy.force d
end



Martin

--
http://wink.com/profile/mjambon
http://mjambon.com

Re: [Caml-list] break and continue for OCaml

[Richard Jones]

On Thu, Apr 10, 2008 at 04:05:45PM +0200, Martin Jambon wrote:
> I'm OK with the intent, but what should happen in such cases:
> 
> module A =
> struct
>   let a = break
>   let b = continue
>   let c = return true

Assuming we can tell if we're inside a function[1] then 'c' would be
an error.

>   let d = lazy (return 123)

  let d () = lazy (return 123)

is an interesting case because in theory the behaviour could end up
looking like a continuation.  However if you consider 'lazy' to be a
kind of shorthand for 'fun () -> ...' then the answer is more obvious;
this is just the same as:

  let d () = lazy 123

>   let e () = Lazy.force d

and the outcome of 'e ()' is then also obvious.

Rich.

[1] .. and not being an expert on the internals of the compiler I
don't really know if this assumption is true.

-- 
Richard Jones
Red Hat

Re: [Caml-list] break and continue for OCaml

[Michael Wohlwend]

Am Donnerstag, 10. April 2008 16:05:45 schrieb Martin Jambon:

> I'm OK with the intent, but what should happen in such cases:
>
> module A =
> struct
>    let a = break
>    let b = continue

I think break and continue should be restricted to inside of loops, which 
isn't hard to do.

 Michael

Re: [Caml-list] break and continue for OCaml

[Martin Jambon]

On Thu, 10 Apr 2008, Michael Wohlwend wrote:

> Am Donnerstag, 10. April 2008 16:05:45 schrieb Martin Jambon:
>
>> I'm OK with the intent, but what should happen in such cases:
>>
>> module A =
>> struct
>>    let a = break
>>    let b = continue
>
> I think break and continue should be restricted to inside of loops, which
> isn't hard to do.

I would not say this until I have done it myself :-)


Martin

--
http://wink.com/profile/mjambon
http://mjambon.com

Re: [Caml-list] break and continue for OCaml

[Michael Wohlwend]

Am Donnerstag, 10. April 2008 16:35:30 schrieben Sie:

> > I think break and continue should be restricted to inside of loops, which
> > isn't hard to do.
>
> I would not say this until I have done it myself :-)
>

yes sure, I did it :-) allthough not for a functional language

 Michael

Re: [Caml-list] break and continue for OCaml

[Florian Weimer]

* Martin Jambon:

> I'm OK with the intent, but what should happen in such cases:
>
> module A =
> struct
>   let a = break
>   let b = continue
>   let c = return true
>   let d = lazy (return 123)
>   let e () = Lazy.force d
> end

I think break/continue/return should be syntactic constructs (perhaps
using pseudo-keywords), so that "let a = break" is as legal as say,
"let a = end".

Re: [Caml-list] break and continue for OCaml

[Eric Cooper]

On Thu, Apr 10, 2008 at 10:59:16AM +0900, Sanghyeon Seo wrote:
> I have the first cut of patch to implement break and continue inside
> for and while loops for OCaml.
> ...
> What do you think?

Yuck.

It adds more imperative baggage to the language, going against its
"mostly functional" style.  And it doesn't add any expressive power,
since you can easily use exceptions, or bool refs as in Pascal, to
achieve the same effect.

The syntax and semantics would become more much complicated and
irregular.  As others have pointed out, it's not even clear what a lot
of cases should mean.

If you want richer control structures, continuations and call/cc would
be much more in the functional spirit.

-- 
Eric Cooper             e c c @ c m u . e d u

Re: [Caml-list] break and continue for OCaml

[Micha]

On Thursday 10 April 2008 22:35:36 Eric Cooper wrote:
> It adds more imperative baggage to the language,

good thing. OCaml advertises the imperative paradigm it supports, so it should 
support it right.

> going against its 
> "mostly functional" style.  And it doesn't add any expressive power,
> since you can easily use exceptions, or bool refs as in Pascal, to
> achieve the same effect.

I'm interessted in the cleanest way to solve a problem, whether it's 
functional or imperative or oo in the end doesn't matter. And replacing a 
simple thing with myriads of exception code and workarounds is not my 
unterstanding of "easily useable".
But that discussion is academic, nothing will evolve here,

 Michael

Re: [Caml-list] break and continue for OCaml

[Andrew I. Schein]

[-- Attachment #1: Type: text/plain, Size: 909 bytes --]

I took the exception approach in a camlp4 macro: pa_breakcont

http://code.google.com/p/ocaml-break-continue/

There are timings before/after on the wiki section of that page that
demonstrate the overhead.

Also, pa_breakcont changes rather than adds to the grammar increasing
likelihood of conflict with other extensions.

Hopefully, Sanghyeon can fix both of these drawbacks with his approach.

-Andy



> On Thu, Apr 10, 2008 at 04:12:49PM +0200, David Allsopp wrote:
> > Is there therefore any reasonable performance gain over implementing
> > break/continue as a camlp4 extension rather than as a compiler patch?
>
> The posted patch turns the break/continue into jump instructions
> (well, jump bytecodes), which should be moderately faster than pushing
> an exception stack frame / unwinding the stack.
>
> Rich.
>
> --
> Richard Jones
> Red Hat
>
>



-- 
Andrew I. Schein


web: www.andrewschein.com

[-- Attachment #2: Type: text/html, Size: 1329 bytes --]