* Instruction return
@ 1997-05-31 17:30 Pascal Zimmer
1997-06-02 14:15 ` Pierre Weis
0 siblings, 1 reply; 7+ messages in thread
From: Pascal Zimmer @ 1997-05-31 17:30 UTC (permalink / raw)
To: caml-list
Serait-il possible d'ajouter une instruction return au langage CAML afin
de pouvoir sortir directement d'une boucle, comme c'est le cas en C ? Je
pense qu'une telle instruction ameliorerait beaucoup la lisibilite du
code.
Par exemple, cela permettrait de retourner la valeur d'une fonction au
cours d'une boucle for, alors que pour l'instant on doit utiliser une
boucle while avec un compteur sous forme de pointeur.
Ainsi, une fonction classique de recherche d'une valeur x dans un tableau
non trie v s'ecrit:
let rech x v =
let n = vect_length v in
let i = ref 0 in
while !i < n & v.(!i) <> x do i := !i + 1 done;
not (!i = n);;
Avec une instruction return, on pourrait l'ecrire ainsi:
let rech x v =
let n = vect_length v in
for i=0 to n-1 do
if v.(i) = x then return true
done; false;;
Cette derniere forme sans pointeur pour le compteur i est tout de meme
plus claire !
Bien entendu, le typeur devra verifier que le type renvoye par return est
le meme que celui renvoye par la derniere instruction de la fonction.
Une telle possibilite (renvoi par return ou par la derniere instruction)
est par exemple utilisee par le langage de programmation de MAPLE, sauf
qu'il n'y a aucun controle de type.
J'aimerais donc savoir si une telle instruction est possible ou s'il y a
incompatibilite avec le reste du langage.
[English: Is it possible to add a 'return' instruction to the CAML
language, like in C ?]
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Instruction return
1997-05-31 17:30 Instruction return Pascal Zimmer
@ 1997-06-02 14:15 ` Pierre Weis
1997-06-03 8:37 ` Vincent Poirriez
0 siblings, 1 reply; 7+ messages in thread
From: Pierre Weis @ 1997-06-02 14:15 UTC (permalink / raw)
To: Pascal Zimmer; +Cc: caml-list
> Serait-il possible d'ajouter une instruction return au langage CAML afin
> de pouvoir sortir directement d'une boucle, comme c'est le cas en C ? Je
> pense qu'une telle instruction ameliorerait beaucoup la lisibilite du
> code.
Oui c'est possible et c,a ne pose aucun proble`me pour le reste du langage.
Il faut seulement se persuader que c'est vraiment ne'cessaire.
> Par exemple, cela permettrait de retourner la valeur d'une fonction au
> cours d'une boucle for, alors que pour l'instant on doit utiliser une
> boucle while avec un compteur sous forme de pointeur.
>
> Ainsi, une fonction classique de recherche d'une valeur x dans un tableau
> non trie v s'ecrit:
>
> let rech x v =
> let n = vect_length v in
> let i = ref 0 in
> while !i < n & v.(!i) <> x do i := !i + 1 done;
> not (!i = n);;
>
> Avec une instruction return, on pourrait l'ecrire ainsi:
>
> let rech x v =
> let n = vect_length v in
> for i=0 to n-1 do
> if v.(i) = x then return true
> done; false;;
>
> Cette derniere forme sans pointeur pour le compteur i est tout de meme
> plus claire !
Pour sortir d'une boucle il n'est pas besoin d'une telle instruction:
il suffit d'utiliser le me'canisme d'exceptions du langage; lorsqu'on
veut arre^ter la boucle pre'mature'ment on lance une exception, et
l'on prote`ge la boucle a` l'aide d'un try ... with. Il existe
d'ailleurs une exception spe'cialement pre'de'finie pour ce faire:
l'exception Exit. On e'crit donc d'habitude
let rech x v =
try
let n = vect_length v in
for i=0 to n-1 do
if v.(i) = x then raise Exit
done; false
with Exit -> true;;
Bien su^r cela ne suffit pas pour rendre la valeur d'une fonction au
milieu d'une boucle, sauf a` de'finir une exception spe'cifique a`
chaque fonction, sur le mode`le:
exception Return of bool;;
let rech x v =
try
let n = vect_length v in
for i=0 to n-1 do
if v.(i) = x then raise (Return true)
done; false
with Return b -> b;;
C'est e'videmment un peu lourd (et ca ne marche pas pour les fonctions
polymorphes). C'est pourquoi on pre'fe`re alors conside'rer que la
boucle est trop complexe pour une boucle for ou while et qu'il est
temps d'utiliser des outils adapte's a` e'crire des boucles
arbitrairement complexes, c'est-a`-dire les fonctions re'cursives.
let rech x v =
let rec boucle i =
if i < vect_length v then
if v.(i) = x then true else trouve (i + 1)
else false in
boucle 0;;
ou encore, apre`s un peu de re'e'criture:
let rech x v =
let rec boucle i = i < vect_length v && (v.(i) = x || boucle (i + 1)) in
boucle 0;;
Ce qui est encore plus bref (plus simple?) que la boucle for et posse`de
l'immense avantage d'e^tre comple`tement ge'ne'ral et de ne pas
ne'cessiter d'instruction supple'mentaire.
> Bien entendu, le typeur devra verifier que le type renvoye par return est
> le meme que celui renvoye par la derniere instruction de la fonction.
> Une telle possibilite (renvoi par return ou par la derniere instruction)
> est par exemple utilisee par le langage de programmation de MAPLE, sauf
> qu'il n'y a aucun controle de type.
Il suffit pour cela de typer le corps d'une fonction en e'tendant
l'environnement avec une liaison pour l'identificateur return de type
'a -> 'a; on doit enfin unifier 'a avec le type obtenu pour le corps
de la fonction. La compilation correspond en gros a` ge'ne'rer un
goto. Il n'y a donc pas de re'elle difficulte'.
> J'aimerais donc savoir si une telle instruction est possible ou s'il y a
> incompatibilite avec le reste du langage.
C'est donc possible, et ce n'est pas incompatible, mais est-ce ne'cessaire ?
De surcroi^t, il n'est pas certain que cette construction facilite
vraiment la lecture, dans la mesure ou` la valeur de retour des
fonctions serait alors bien moins facile a` localiser, puisque qu'elle
pourrait apparai^tre n'importe ou` dans le corps de la fonction.
(conside'rez me^me un programme sans boucles:
let f x =
let y = if ... then return 1 else 2 in
if y > x then x + 1 else y;;
(dans certains cas) la valeur de retour de f est obtenue (et rendue)
pendant l'e'valuation de l'expression de'finissant y ...)
Cela dit l'argument est faible, car il est toujours facile d'e'crire
des programmes illisibles, me^me avec les meilleures constructions
possibles dans le langage (comme en Caml :).
Peut-e^tre avez-vous des exemples encore plus convaincants ?
> [English: Is it possible to add a 'return' instruction to the CAML
> language, like in C ?]
Yes it is possible, but is it necessary ?
To escape from loops, use the predefined exception Exit, and enclose
the loop inside a try with:
let rech x v =
try
let n = vect_length v in
for i=0 to n-1 do
if v.(i) = x then raise Exit
done; false
with Exit -> true;;
To return the result of a function from inside a loop, it's a bit more
tricky: you must define first an exception that could carry the result (in
your case a boolean):
exception Return of bool;;
Then you enclose the body of the function within a try with construct:
let rech x v =
try
let n = vect_length v in
for i=0 to n-1 do
if v.(i) = x then raise (Return true)
done; false
with Return b -> b;;
In fact the best way of writing complex loops is via recursive
function definitions:
let rech x v =
let rec boucle i = i < vect_length v && (v.(i) = x || boucle (i + 1)) in
boucle 0;;
This is even shorter than the version with the return construct, and
uses a more general concept that the return construct.
Last, the addition of the return construct could be considered
harmful, since the returned value of functions could now be easily
hidden anywhere in the body of the function.
(consider the following program:
let f x =
let y = if ... then return 1 else 2 in
if y > x then x + 1 else y;;
the returned value of f is computed and returned during the evaluation
of the expression that defines y...)
However this is poor, since it is easy to write bad programs, even if
you have the best constructs in the language (as in Caml :)
Have you other examples that could convince us to adopt the return
construct ?
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Instruction return
1997-06-02 14:15 ` Pierre Weis
@ 1997-06-03 8:37 ` Vincent Poirriez
1997-06-03 10:24 ` Pierre Weis
0 siblings, 1 reply; 7+ messages in thread
From: Vincent Poirriez @ 1997-06-03 8:37 UTC (permalink / raw)
To: Pierre Weis; +Cc: Pascal Zimmer, caml-list
>
> > Serait-il possible d'ajouter une instruction return au langage CAML afin
> > de pouvoir sortir directement d'une boucle,
> ...
Je souscrit a la réponse de Pierre Weis
>C'est pourquoi on pre'fe`re alors conside'rer que la
>boucle est trop complexe pour une boucle for ou while et qu'il est
>temps d'utiliser des outils adapte's a` e'crire des boucles
>arbitrairement complexes, c'est-a`-dire les fonctions re'cursives.
Cependant, j'ai rencontré la situation suivante dans un contexte
où l'efficacité (à l'exécution) est essentielle.
Trouver l'indice du premier élément d'un tableau qui vérifie
un prédicat p, s'il y en a un.
Ce code étant compile avec l'option -unsafe, je ne peux pas
compter sur les test de débordement des primitives Array.get ...
Le choix d'utiliser Array.unsafe_get serait inutile si j'inclus
ce test de débordement dans la condition
du while ou de la fonction récursive ainsi:
let find p a =
let l = Array.length a in
let i = ref 0 in
while !i<l & not( p (Array.unsafe_get a !i) do
incr i
done;
!i
J'ai donc prefere le coût d'un try ... with:
exception Exit_for of int
let find p a =
let l = Array.length a in
try
for i = 0 to l-1 do
if p (Array.unsafe_get a i) then raise Exit_for i
done;
l
with Exit_for i -> i
Si l'on veut sortir d'une boucle for avant sa fin normale, en
admettant que ce soit justifié (while ou fonction récursive exclue)
, la valeur de sortie du compteur suffit.
English short version:
I agree with Pierre Weis:
>In fact the best way of writing complex loops is via recursive
>function definitions:
But, due to runtime efficiency considerations I had to make
the following choice.
I want to find the index of the first item of an array which
verifies a predicat p, if one exists.
It is useless to prefer Array.unsafe_get if I add the test
in the while (or recursive) condition as below:
let find p a =
let l = Array.length a in
let i = ref 0 in
while !i<l & not( p (Array.unsafe_get a !i) do
incr i
done;
!i
I prefer to pay the cost of one try ... with ...
exception Exit_for of int
let find p a =
let l = Array.length a in
try
for i = 0 to l-1 do
if p (Array.unsafe_get a i) then raise Exit_for i
done;
l
with Exit_for i -> i
When I want to exit a loop for before its natural end, when I really
need it, it is sufficient to return the value of the count
when I exit
Vincent Poirriez
--
Tel: (33) {0}3 27 14 13 33 Fax: (33) {0}3 27 14 12 94
mailto:Vincent.Poirriez@univ-valenciennes.fr
http://www.univ-valenciennes.fr/limav/poirriez
ISTV Université de Valenciennes Le Mont Houy BP 311 F59304 Valenciennes
CEDEX
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Instruction return
1997-06-03 8:37 ` Vincent Poirriez
@ 1997-06-03 10:24 ` Pierre Weis
1997-06-03 14:17 ` Vincent Poirriez
0 siblings, 1 reply; 7+ messages in thread
From: Pierre Weis @ 1997-06-03 10:24 UTC (permalink / raw)
To: Vincent Poirriez; +Cc: Pierre.Weis, zimmer, caml-list
> Cependant, j'ai rencontré la situation suivante dans un contexte
> où l'efficacité (à l'exécution) est essentielle.
>
> Trouver l'indice du premier élément d'un tableau qui vérifie
> un prédicat p, s'il y en a un.
>
> Ce code étant compile avec l'option -unsafe, je ne peux pas
> compter sur les test de débordement des primitives Array.get ...
>
> Le choix d'utiliser Array.unsafe_get serait inutile si j'inclus
> ce test de débordement dans la condition
> du while ou de la fonction récursive ainsi:
>
> let find p a =
> let l = Array.length a in
> let i = ref 0 in
> while !i<l & not( p (Array.unsafe_get a !i) do
> incr i
> done;
> !i
>
> J'ai donc prefere le coût d'un try ... with:
>
> exception Exit_for of int
> let find p a =
> let l = Array.length a in
> try
> for i = 0 to l-1 do
> if p (Array.unsafe_get a i) then raise Exit_for i
> done;
> l
> with Exit_for i -> i
[...]
As-tu fait des tests qui prouvent la supe'riorite' d'une version sur
l'autre ?
Comment crois-tu que la boucle for fait le bon nombre de tours puis
s'arre^te ? (En faisant un test a` chaque tour, et pratiquement le
me^me que celui de ta boucle while!).
English short version:
> But, due to runtime efficiency considerations I had to make
> the following choice.
>
> I want to find the index of the first item of an array which
> verifies a predicat p, if one exists.
>
> It is useless to prefer Array.unsafe_get if I add the test
> in the while (or recursive) condition as below:
>
> let find p a =
> let l = Array.length a in
> let i = ref 0 in
> while !i<l & not( p (Array.unsafe_get a !i) do
> incr i
> done;
> !i
>
>
> I prefer to pay the cost of one try ... with ...
>
>
> exception Exit_for of int
> let find p a =
> let l = Array.length a in
> try
> for i = 0 to l-1 do
> if p (Array.unsafe_get a i) then raise Exit_for i
> done;
> l
> with Exit_for i -> i
Have you got some runtime figures that prove that this last version is more
efficient than the others ?
By the way, the for loop implies also a test each time its body is
executed (exactly the same as in your while loop) to decide to
continue or stop the loop...
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Instruction return
1997-06-03 10:24 ` Pierre Weis
@ 1997-06-03 14:17 ` Vincent Poirriez
0 siblings, 0 replies; 7+ messages in thread
From: Vincent Poirriez @ 1997-06-03 14:17 UTC (permalink / raw)
To: Pierre Weis; +Cc: Vincent Poirriez, zimmer, caml-list
Pierre Weis wrote:
>
> > Cependant, j'ai rencontré la situation suivante dans un contexte
> > où l'efficacité (à l'exécution) est essentielle.
> >
> > Trouver l'indice du premier élément d'un tableau qui vérifie
> > un prédicat p, s'il y en a un.
> >
> > Ce code étant compile avec l'option -unsafe, je ne peux pas
> > compter sur les test de débordement des primitives Array.get ...
> >
> > Le choix d'utiliser Array.unsafe_get serait inutile si j'inclus
> > ce test de débordement dans la condition
> > du while ou de la fonction récursive ainsi:
> >
> > let find p a =
> > let l = Array.length a in
> > let i = ref 0 in
> > while !i<l & not( p (Array.unsafe_get a !i) do
> > incr i
> > done;
> > !i
> >
> > J'ai donc prefere le coût d'un try ... with:
> >
> > exception Exit_for of int
> > let find p a =
> > let l = Array.length a in
> > try
> > for i = 0 to l-1 do
> > if p (Array.unsafe_get a i) then raise Exit_for i
> > done;
> > l
> > with Exit_for i -> i
> [...]
>
> As-tu fait des tests qui prouvent la supe'riorite' d'une version sur
> l'autre ?
Je n'avais pas, voila une série de test (cf fin du message)
Est-ce que cela prouve? en tout cas la version
for est toujours plus rapide que la version while
(exactement le code ci-dessus aux erreurs de syntaxe pres)
La difference est marginale, je le reconnait,
je ne suis pas allé voir
dans le code d'implantation du for et while pour expliquer la
difference.
test réalisé sur DEC alpha en ocaml 1.05
deux process executes en concurrence, l'un pour le for, l'autre
pour le while.
Les temps sont stables pour plusieurs executions
>
> Comment crois-tu que la boucle for fait le bon nombre de tours puis
> s'arre^te ? (En faisant un test a` chaque tour, et pratiquement le
> me^me que celui de ta boucle while!).
>
Je reconnais la naïveté, ce n'est pas parce que l'on connait la borne
que l'on est dispensé de tester si on la atteinte!!!
> English short version:
>
> > But, due to runtime efficiency considerations I had to make
> > the following choice.
> >
> > I want to find the index of the first item of an array which
> > verifies a predicat p, if one exists.
> >
> > It is useless to prefer Array.unsafe_get if I add the test
> > in the while (or recursive) condition as below:
> >
> > let find p a =
> > let l = Array.length a in
> > let i = ref 0 in
> > while !i<l & not( p (Array.unsafe_get a !i) do
> > incr i
> > done;
> > !i
> >
> >
> > I prefer to pay the cost of one try ... with ...
> >
> >
> > exception Exit_for of int
> > let find p a =
> > let l = Array.length a in
> > try
> > for i = 0 to l-1 do
> > if p (Array.unsafe_get a i) then raise Exit_for i
> > done;
> > l
> > with Exit_for i -> i
>
> Have you got some runtime figures that prove that this last version is more
> efficient than the others ?
I had not, but it's done now
Does it prove?
These tests were executed on a Dec Alpha with ocaml-1.05
two distinct processes, one for the while version and the other
for the for version (exactly the above code except for syntax mistakes)
times are rather stable for several executions
>
> By the way, the for loop implies also a test each time its body is
> executed (exactly the same as in your while loop) to decide to
> continue or stop the loop...
>
I agree with the naivety of the "for" code, the knowledge of the bound
does not exempted to test if it is reached!!!
I did not
Vincent Poirriez
CPU times (as report by the times function)
an array of int randomly generated between 10 and 10000010
Size of the array : 10000000
first find the first item equal to the length
second (all) find the first negative item
ten instances of the pb
for: 0.183 index: 912770
while : 0.2 index: 912770
for (all): 2.05 index: 10000000
while (all): 2.166 index: 10000000
for: 0.566 index: 2509612
while : 0.583 index: 2509612
for (all): 2.05 index: 10000000
while (all): 2.266 index: 10000000
for: 0.75 index: 3345779
while : 0.783 index: 3345779
for (all): 2.033 index: 10000000
while (all): 2.25 index: 10000000
for: 0.216 index: 1101347
while : 0.266 index: 1101347
for (all): 2.016 index: 10000000
while (all): 2.266 index: 10000000
for: 2.05 index: 9398524
while : 2.2 index: 9398524
for (all): 2.066 index: 10000000
while (all): 2.216 index: 10000000
for: 0.016 index: 36893
while : 0.016 index: 36893
for (all): 2 index: 10000000
while (all): 2.3 index: 10000000
for: 2.166 index: 10000000
while : 2.283 index: 10000000
for (all): 2.05 index: 10000000
while (all): 2.233 index: 10000000
for: 0.6 index: 2881739
while : 0.683 index: 2881739
for (all): 2.116 index: 10000000
while (all): 2.2 index: 10000000
for: 0.5 index: 2243375
while : 0.516 index: 2243375
for (all): 2.016 index: 10000000
while (all): 2.216 index: 10000000
for: 1.766 index: 8282931
while : 2 index: 8282931
for (all): 2.033 index: 10000000
while (all): 2.2 index: 10000000
--
Tel: (33) {0}3 27 14 13 33 Fax: (33) {0}3 27 14 12 94
mailto:Vincent.Poirriez@univ-valenciennes.fr
http://www.univ-valenciennes.fr/limav/poirriez
ISTV Université de Valenciennes Le Mont Houy BP 311 F59304 Valenciennes
CEDEX
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Instruction return
1997-06-02 16:23 Dwight VandenBerghe
@ 1997-06-02 21:41 ` Pierre Weis
0 siblings, 0 replies; 7+ messages in thread
From: Pierre Weis @ 1997-06-02 21:41 UTC (permalink / raw)
To: Dwight VandenBerghe; +Cc: caml-list
> This is one of the two main control problems with functional programming,
> IMHO.
> The solution I use is:
[...]
Dwight's solution uses the a user defined exception Found_it instead of the
predefined exception Exit, with a loop or an iteration functional.
> The other control problem is when you want the equivalent of:
>
> x = foo(a);
> bar();
> return x;
>
> If you try
>
> let x = foo(a) in
> bar();
> x
>
> then bar gets done first, instead of second.
That's not true: the language semantics ensures that foo (a) is
evaluated before the sequence bar (); x. (This is intuitively evident
since the value of x may be required to evaluate the "in" part.)
(Try for instance:
let foo x = print_string "Hello "; print_string x; x;;
let bar () = print_string " world!";;
And then
# let x = foo ("you") in bar(); x;;
Hello you world!- : string = "you")
> i use this instead:
>
> let f x = bar(); x in
> in f (foo a)
This is provably equivalent, although slightly offuscating.
(Theory meets practice in this case, since we get:
# let f x = bar(); x in f (foo "you");;
Hello you world!- : string = "you")
> I haven't found any other serious problems with Caml's logic flow. These
> two just take some getting used to.
Good. Especially if we discarde the second problem :)
Pierre Weis
INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Instruction return
@ 1997-06-02 16:23 Dwight VandenBerghe
1997-06-02 21:41 ` Pierre Weis
0 siblings, 1 reply; 7+ messages in thread
From: Dwight VandenBerghe @ 1997-06-02 16:23 UTC (permalink / raw)
To: Pascal Zimmer, caml-list
(I apologize for no French version)
> let rech x v =
> let n = vect_length v in
> for i=0 to n-1 do
> if v.(i) = x then return true
> done; false;;
This is one of the two main control problems with functional programming,
IMHO.
The solution I use is:
exception Found_it
let rech x v =
try
for i = 0 to pred (vect_length v) do
if v.(i) = x then raise Found_it
done;
false
with Found_it -> true
You don't have to assign vect_length v to n; it is only evaluated once
anyway.
If iter is defined on the type of v, then you can also use
let rech x v =
try
let f x1 = if x1 = x then raise Found_it in
iter f v; false
with Found_it -> true
The other control problem is when you want the equivalent of:
x = foo(a);
bar();
return x;
If you try
let x = foo(a) in
bar();
x
then bar gets done first, instead of second. I use this instead:
let f x = bar(); x in
in f (foo a)
I haven't found any other serious problems with Caml's logic flow. These
two just take some getting used to.
Dwight
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~1997-06-03 15:16 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1997-05-31 17:30 Instruction return Pascal Zimmer
1997-06-02 14:15 ` Pierre Weis
1997-06-03 8:37 ` Vincent Poirriez
1997-06-03 10:24 ` Pierre Weis
1997-06-03 14:17 ` Vincent Poirriez
1997-06-02 16:23 Dwight VandenBerghe
1997-06-02 21:41 ` Pierre Weis
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).