sequencing

sequencing

[Jean.Luc.Paillet]

   Quelqu'un pourrait-il m'expliquer pourquoi le sequencement d'une fonction
a` effet de bord, telle que "print_string" par exemple, semble inverse'
quand elle est appliquée sur une liste au moyen d'un iterateur.

Par exemple
   map print_string ["a" ; "b"] ;;   produit

    ba- : unit list = [(); ()]
ce qui implique un parcours de la liste de droite a gauche .
Plus curieux, avec une definition recursive "personnelle" de l'iterateur,
telle que

   let rec monmap f liste      match liste  with [] -> [] |
                     head :: tail -> (f head) :: monmap f (tail) ;;

On pourrait s'attendre ici a ce que  "(f head)" soit evalue avant
l'appel recursif. He bien non,
 on obtient encore

   monmap print_string ["a" ; "b"] ;;
    ba- : unit list = [(); ()]

Quelle est mon erreur d'interpretation ?
Doit-on penser que  (f head) est empile jusqu'a ce que la fonction termine ?

   ?????
**********************************************
££  English version  ££

I don't understand why the sequencing of side effects seems to be inverted,
when using "map" , like for example in the following:

     map print_string ["a" ; "b"] ;;   gives
    ba- : unit list = [(); ()]

it means that the list is scanned from the right to the left

More surprising, with a recursive hand made definition of "map", such as

   let rec monmap f liste      match liste  with [] -> [] |
                     head :: tail -> (f head) :: monmap f (tail) ;;


We also obtain

   monmap print_string ["a" ; "b"] ;;
    ba- : unit list = [(); ()]

We could thing that   "(f head)" is evaluated before the recursive call .

What is my mistake ?
Does the term "(f head)" pushed on the recursion stack until terminating
the recursive calls, before being evaluated ?


   Thanks for an explanation

    Kind regards


        Jean-Luc Paillet

(*
------------------------------------------------------------------------
              Jean-Luc PAILLET
              LIM  (URA 1787)
              CMI -   Universite de Provence
              39 r Joliot Curie
              13453  Marseille  Cedex 13   FRANCE
              Tel:  (33) 04 91 11 36 10
              Fax:  (33) 04 91 11 36 02
              e-mail:  Jean.Luc.Paillet@lim.univ-mrs.fr
                       jluc@gyptis.univ-mrs.fr
--------------------------------------------------------------------------
*)

Re: sequencing

[Francois Pessaux]

>    Quelqu'un pourrait-il m'expliquer pourquoi le sequencement d'une fonction
> a` effet de bord, telle que "print_string" par exemple, semble inverse'
> quand elle est appliquée sur une liste au moyen d'un iterateur.

Il se trouve que l'ordre d'evaluation (droite-gauche ou gauche-droite) n'est
pas specifie pour le compilo Caml. Autrement dit, il ne faut pas compter sur
un ordre particulier pour faire un programme correct. Sur la version de Caml
que tu utilise l'evaluation doit vraissemblablement se faire de droite a
gauche et la fonction map doit etre definie comme :
let rec map f = function
 | [] -> []
 | h :: q -> (f h) :: (map f q) ;;

Pour patcher ca, et ne plus etre dependant de l'ordre d'evaluation, il faut
effectuer explicitement le calcul de f h en premier :
let rec map f = function
    [] -> []
  | h :: q -> let r = f a
               in r :: map f q ;;

C'est d'ailleurs comme ca qu'est codee map en Objective Caml.

-- 
(*                      Francois PESSAUX (Francois.Pessaux@inria.fr) *)
(*                               INRIA Rocquencourt - Projet CRISTAL *)
(*                               (http://pauillac.inria.fr/~pessaux) *)
;;

Re: sequencing

[Jean-Christophe Filliatre]

[-- Attachment #1: Type: text, Size: 1821 bytes --]

Re: sequencing

[Michel Quercia]

Jean.Luc.Paillet@lim.univ-mrs.fr wrote:
> 
>    Quelqu'un pourrait-il m'expliquer pourquoi le sequencement d'une fonction
> a` effet de bord, telle que "print_string" par exemple, semble inverse'
> quand elle est appliquée sur une liste au moyen d'un iterateur.
> 
> Par exemple
>    map print_string ["a" ; "b"] ;;   produit
> 
>     ba- : unit list = [(); ()]
> ce qui implique un parcours de la liste de droite a gauche .
> Plus curieux, avec une definition recursive "personnelle" de l'iterateur,
> telle que
> 
>    let rec monmap f liste =
>      match liste  with [] -> [] |
>                      head :: tail -> (f head) :: monmap f (tail) ;;

Un coup d'oeil a la bibliotheque sur les listes
(/usr/local/lib/caml-light/list.ml) monter que map est a peu pres defini
comme cela.

> 
> On pourrait s'attendre ici a ce que  "(f head)" soit evalue avant
> l'appel recursif. He bien non,

L'ordre d'evaluation de (expr_a) :: (expr_b) n'est pas specifie dans le
manuel de reference. En pratique, il se trouve que expr_b est evalue
d'abord.
Voici une fonction lr_map produisant une application de gauche a droite
:


>       Caml Light version 0.73

#map print_char [`a`; `b`; `c`];;
cba- : unit list = [(); (); ()]
#let rec lr_map f liste = match liste with
| [] -> []
| t::q -> let t' = f(t) in t' :: (lr_map f q)
;;
lr_map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#lr_map print_char [`a`; `b`; `c`];;
abc- : unit list = [(); (); ()]
#

> **********************************************
> ££  English version  ££
> 
> I don't understand why the sequencing of side effects seems to be inverted,
> when using "map" , like for example in the following:
> 
>      map print_string ["a" ; "b"] ;;   gives
>     ba- : unit list = [(); ()]
> 
> it means that the list is scanned from the right to the left
> 
> More surprising, with a recursive hand made definition of "map", such as
> 
>    let rec monmap f liste =
>      match liste  with [] -> [] |
>                      head :: tail -> (f head) :: monmap f (tail) ;;
> 

Look at the list implementation (/usr/local/lib/caml-light/list.ml),
you'll see that map is roughly defined that way.

> 
> We could thing that   "(f head)" is evaluated before the recursive call .
> 

The order of evaluation of (expr_a) :: (expr_b) is unspecified in the
reference manual. Actually, it turns out that expr_b is evaluated first.
Here is a function lr_map going from left to right :


>       Caml Light version 0.73

#map print_char [`a`; `b`; `c`];;
cba- : unit list = [(); (); ()]
#let rec lr_map f liste = match liste with
| [] -> []
| t::q -> let t' = f(t) in t' :: (lr_map f q)
;;
lr_map : ('a -> 'b) -> 'a list -> 'b list = <fun>
#lr_map print_char [`a`; `b`; `c`];;
abc- : unit list = [(); (); ()]
#


-- 
Michel Quercia
Lycee Carnot  16 bd Thiers  21000 Dijon
mailto:quercia@cal.enst.fr

Re: sequencing

[Vincent Poirriez]

Jean.Luc.Paillet@lim.univ-mrs.fr wrote:
> 
>    Quelqu'un pourrait-il m'expliquer pourquoi le sequencement d'une fonction
> a` effet de bord, telle que "print_string" par exemple, semble inverse'

il n'est pas inversé puisqu'il n'est pas spécifié!!!

Le sens naturel, pour nous autres, est l'évaluation de gauche à droite,
ce n'est pas le même dans d'autres cultures et certaines raisons
(efficacité de compilation par exmple) font que certains compilateurs
évaluent de droite à gauche, c'est le cas pour ocaml.

Si vous voulez controler l'ordre d'exécution utilisez l'opérateur
de séquencement ";" ou, ce qui est équivalent pour votre exemple, les
itérateurs "impératifs"
 
Ce qui donne
 Objective Caml version 1.05

# List.iter;; 
- : ('a -> 'b) -> 'a list -> unit = <fun>
# List.iter print_string ["a" ; "b"];;
ab- : unit = ()
# let rec iter f = function
   [] -> ()
  | h::t -> f h; iter f t;;
val iter : ('a -> 'b) -> 'a list -> unit = <fun>
# iter print_string ["a" ; "b"];;
ab- : unit = ()
# 
au lieu de votre code
> quand elle est appliquée sur une liste au moyen d'un iterateur.
> 
> Par exemple
>    map print_string ["a" ; "b"] ;;   produit
> 
>     ba- : unit list = [(); ()]
> ce qui implique un parcours de la liste de droite a gauche .
> Plus curieux, avec une definition recursive "personnelle" de l'iterateur,
> telle que
> 
>    let rec monmap f liste =
>      match liste  with [] -> [] |
>                      head :: tail -> (f head) :: monmap f (tail) ;;
> 
> On pourrait s'attendre ici a ce que  "(f head)" soit evalue avant
> l'appel recursif. He bien non,
>  on obtient encore
> 
>    monmap print_string ["a" ; "b"] ;;
>     ba- : unit list = [(); ()]
> 
> Quelle est mon erreur d'interpretation ?
> Doit-on penser que  (f head) est empile jusqu'a ce que la fonction termine ?
> 
>    ?????
> **********************************************
> ££  English version  ££
> 
> I don't understand why the sequencing of side effects seems to be inverted,
It is not inverted is it is not specified!!!
The natural way, "for us" is to evaluate from left to right
but it is not the same in other cultures and for some
deep reasons (efficiency for example) some compilers evaluate
from right to left, it is the case for ocaml.

If you need to control the order of evaluation you have to use
the operator ";" or, which is simpler for your example,
the predifined "imperatif" iterator:

This leads to 
 Objective Caml version 1.05

# List.iter;; 
- : ('a -> 'b) -> 'a list -> unit = <fun>
# List.iter print_string ["a" ; "b"];;
ab- : unit = ()
# let rec iter f = function
   [] -> ()
  | h::t -> f h; iter f t;;
val iter : ('a -> 'b) -> 'a list -> unit = <fun>
# iter print_string ["a" ; "b"];;
ab- : unit = ()
# 

instead of your code
>


> when using "map" , like for example in the following:
> 
>      map print_string ["a" ; "b"] ;;   gives
>     ba- : unit list = [(); ()]
> 
> it means that the list is scanned from the right to the left
> 
> More surprising, with a recursive hand made definition of "map", such as
> 
>    let rec monmap f liste =
>      match liste  with [] -> [] |
>                      head :: tail -> (f head) :: monmap f (tail) ;;
> 
> We also obtain
> 
>    monmap print_string ["a" ; "b"] ;;
>     ba- : unit list = [(); ()]
> 
> We could thing that   "(f head)" is evaluated before the recursive call .
> 
> What is my mistake ?
> Does the term "(f head)" pushed on the recursion stack until terminating
> the recursive calls, before being evaluated ?
> 
>    Thanks for an explanation
> 
>     Kind regards
> 
>         Jean-Luc Paillet
> 
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