Journal Un décalage de 64 bits, ça vous inspire comment ?

Posté par Blackknight (site web personnel, Mastodon) le 14 mai 2017 à 17:18. Licence CC By‑SA.

Étiquettes :

mai

2017

Salut à tous,
après l'excellent journal d'Anaseto sur le fameux "1+3a", un pote à moi, prof de maths à L'INSA de Rouen, m'a demandé de faire ce petit journal après une "découverte" faite par ses étudiants.
Ceux-ci écrivant des tests unitaires en Free Pascal sont tombés sur un comportement non documenté qui nous a amené à nous poser la question du "comment ksa fait sur les autres langages" :)

Le problème

Le problème vient de l'opérateur de décalage de bits à droite.
Si je prend un entier initialisé à 1, le décalage d'un bit vers la droite retourne 0. Si l'on décale de 2 bits, on s'attend à avoir 0… Et c'est toujours le cas.
Par contre, le code suivant ne retourne pas 0

program beBitwise;
var
a, b: integer;

begin
   a := 1;
   b := a >> 64; (* la, on s'attend normalement à obtenir un 0 *)
   writeln('Valeur de b ', b );
end.

Le code retourne 1 à savoir a.

Si l'on remplace 64 par 63 ou 65, on obtient bien 0.
Bien sûr, sur une machine 32 bits, on obtient le même comportement avec un décalage de 32 bits.

Si le comportement peut s'expliquer, le fait que le compilateur ne prévienne pas du risque et qu'aucune documentation ne le spécifie est un poil gênant.

Résultat, les étudiants sont en train de remplir un rapport de bug pour Free Pascal, ne serait-ce que pour que le comportement soit documenté quelque part.

Et chez les autres ?

En C/C++

#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
  unsigned long long a = 1;
  unsigned long long b = a << 64;
  cout << "b vaut " << b << endl;
}

Au moins, le compilateur GCC nous prévient du problème en affichant le warning si on travaille en statique
shift.cpp: In function ‘int main(int, char**)’: shift.cpp:8:31: warning: left shift count >= width of type [-Wshift-count-overflow] unsigned long long b = a << 64;Dans le cas où c'est l'utilisateur qui rentrerait le décalage à l'exécution, il n'y aurait aucun message… Logique !

En Java

public class Shift
{
    public static void main(String[] args)
    {
    int a = 1;

    System.out.println("Resultat : " + (a >> 64));
    }
}

Même punition et surtout pas de warning.

En Ada

Vous n'y couperez pas, je vais forcément donner un exemple en Ada

with Interfaces; use Interfaces;
with Ada.Text_Io; use Ada.Text_Io;

Procedure Shift is
begin
   Put_Line("Resultat " & Unsigned_64'Image(Shift_Right(Unsigned_64(1), 64))); 
end Shift;

Là, pas de message d'erreur ni de warning mais au final pas d'erreur non plus, le résultat est bien 0.

En OCAML

Il s'agit juste d'une ligne de commande dans l'interpréteur:

# open Int64;;
# shift_right one 64;;
- : int64 = 1L
#

J'avoue que je ne m'attendais pas à ce résultat mais OCAML retourne lui aussi 1 en lieu et place de 0.

En Python

>>> 1 >> 64
0

Ce qui est normal pour un langage typé canard ;)

Que disent les docs ?

Le reproche que l'on peut faire à Free Pascal, c'est justement de ne rien dire quant à ce fonctionnement.
Par contre, si l'on prend OCAML, la documentation du module Int64 précise que le comportement est non spécifié.
val shift_right : int64 -> int -> int64 Int64.shift_right x y shifts x to the right by y bits. This is an arithmetic shift: the sign bit of x is replicated and inserted in the vacated bits. The result is unspecified if y < 0 or y >= 64.

Si on prend les deux langages normalisés, à savoir C++ et Ada, la documentation est claire.
Pour C++, dans le draft de la prochaine norme, page 126, le comportement est implementation defined.

Pour Ada, il n'y a aucune restriction et la norme ne fournit donc que les exigences d'implémentation.

Voilà pour les langages que j'ai eu envie d'explorer.
Et vous, votre langage préféré, il fait quoi ?

# petit complément

Posté par snowball (site web personnel) le 14 mai 2017 à 18:04. Évalué à 8. Dernière modification le 14 mai 2017 à 18:08.
Salut !

Bon comme je suis cité dans ton journal je me dois de réagir :)

D'abord merci pour avoir partagé cette remarque ici.
Petit complément concernant le premier test que tu as écrit en Pascal (compilé avec fpc).
La doc de fpc ne dit rien sur la taille d'une variable déclarée de type integer (ça peut être 16 ou 32 bits).

Par exemple
```
var u : integer;
begin
  u := 1;
  write (u >> 32);
end.
```
le résultat est 1 aussi (et 0 si on décale de 16 ce qui montre que u a été déclaré comme un entier sur 32 bits).

Et si on écrit
```
var u : QWord; // u entier sur 64 bits
begin
  u := 1;
  write (u >> 32);
end.
```
alors le résultat est bien 0.

Tout ça pour dire que quand on commence à faire ce genre de manip, le type "integer" est à proscrire (comportement imprévisible). D'ailleurs je dirais que le type "integer" en Pascal est à éviter en général (on ne sait pas trop ce qu'on manipule).
http://wiki.freepascal.org/Variables_and_Data_Types
- [^] # Re: petit complément
  
  Posté par Blackknight (site web personnel, Mastodon) le 14 mai 2017 à 18:29. Évalué à 4.
  Et si on écrit
```
var u : QWord; // u entier sur 64 bits
begin
  u := 1;
  write (u >> 32);
end.
```
  alors le résultat est bien 0.
  
  Certes mais on retombe sur le même problème en décalant de 64 bits :)
  
  En tout cas, merci pour les précisions sur les types
  - [^] # Re: petit complément
    
    Posté par snowball (site web personnel) le 14 mai 2017 à 18:55. Évalué à 3.
    
    Tout à fait. Ça ne règle effectivement pas le "problème".
    C'était pour dire que même avec 32 dans ton exemple plutôt que 64 ça fait la même chose (puisque le type integer occupe 32 bits sur ta machine 64 bits).
    
    Au passage, Fpc ne dit pas grand chose sur le comportement des opérations de décalage mais côté Delphi c'est plus précis:
    
    The shr keyword performs a bitwise shift right of an Integer. The number is shifted Bits to the right. If Bits is greater than the size of the number type, the Bits value is Mod'ed by the number type size (minimum 32) before the shift.
    
    http://www.delphibasics.co.uk/RTL.asp?Name=shr
- [^] # Re: petit complément
  
  Posté par Pierre le 15 mai 2017 à 09:02. Évalué à -1.
  
  D'ailleurs je dirais que le type "integer" en Pascal est à éviter en général (on ne sait pas trop ce qu'on manipule).
  
  C'est surtout Pascal qu'il faut eviter. Serieusement. Enseigner le Pascal en 2017…
  
  :o)
  - [^] # Re: petit complément
    
    Posté par Marotte ⛧ le 15 mai 2017 à 14:24. Évalué à 6.
    
    Pourquoi ?
  - [^] # Re: petit complément
    
    Posté par snowball (site web personnel) le 15 mai 2017 à 19:28. Évalué à 3.
    
    Les gens qui ont décidé, pour l'école, d'enseigner avec Pascal le début de la programmation procédurale compilée, n'ont pas hésité longtemps (et ils sont loin d'être incompétents).
    
    Perso, je milite pour que, comme à l'INSA Toulouse, on enseigne l'Ada mais avec Pascal j'ai tout ce qu'il me faut pour faire passer ce qu'ils ont à apprendre à leur niveau (et même plus que nécessaire). Par contre Ada nécessite une formation des collègues et une remise à plat de tous les supports (un travail assez énorme). Je ne vois pas quel autre langage il serait intéressant de montrer aux jeunes élèves ingénieurs en première année dans le cadre de la programmation procédure compilée.
    
    Je précise que, bien évidemment, tous les élèves ingénieurs font dans leurs deux premières années, du C et du Python dans les projets Math de l'école, puis font un peu de tout en 3ème, 4ème et 5ème année s'ils suivent le département d'Info.
    - [^] # Re: petit complément
      
      Posté par Pierre le 15 mai 2017 à 21:01. Évalué à -3.
      
      Trolls de coté,
      
      Pascal, Ada, ocaml, c'est l'approche matheuse, algorithmique, universitaire de l'informatique.
      Avec ce bagage, les élèves qui ne prendront pas la filière info auront peu de chance d'utiliser leur competence plus tard.
      
      En enseignant le python, en ne gardant que le paradigme procedural, si vous voulez. L'élève ingénieur pourra réutiliser cette competence pour automatiser ces taches d'ingénieurs, et ne pas se reposer seulement sur ces collègues programmeurs.
      - [^] # Re: petit complément
        
        Posté par Blackknight (site web personnel, Mastodon) le 15 mai 2017 à 21:48. Évalué à 2.
        
        L'élève ingénieur pourra réutiliser cette competence pour automatiser ces taches d'ingénieurs, et ne pas se reposer seulement sur ces collègues programmeurs.
        
        Heu, dans mon ancien boulot, les ingénieurs non informaticiens, c'était plutôt macros Excel mais pas franchement Python.
        Et puis franchement, de mon côté, c'est pas mes cours de chimie de première année de prépa qui me permettrait de faire quoique ce soit. En clair, c'est juste pour la culture, un peu comme apprendre l'algorithmie avec Pascal.
      - [^] # Re: petit complément
        
        Posté par gaaaaaAab le 15 mai 2017 à 22:23. Évalué à 5.
        
        Ta remarque n'est pas sans mérite, mais je ne pense pas qu'elle se tranche aussi définitivement que ce que tu sembles penser.
        
        C'est une grande question de l'éducation. Enseigner des outils directement utilisables professionnellement, ou utiliser des outils moins directement utilisables, mais plus pédagogiques, pour aboutir à une meilleure compréhension de la matière.
        
        En prépa et école d'ingé d'info (au passage, programmeur et ingénieur, c'est pas incompatible), j'ai fait un peu de programmation fonctionnel (ocaml et lisp). Jusqu'à présent, je ne m'en suis pas servi professionnellement, mais je suis content d'y avoir été exposé pendant mes études.
        
        En enseignant le python, en ne gardant que le paradigme procédural, si vous voulez.
        
        J'imagine que c'était un exemple vite fait d'une piste que t'as pas trop creusé. Je relève juste parce que ça me parait être une mauvaise idée d'enseigner le Python en se restreignant au paradigme procédural. Ça ferait des très mauvais développeurs Python.
      - [^] # Re: petit complément
        
        Posté par snowball (site web personnel) le 15 mai 2017 à 22:31. Évalué à 5.
        
        Ils apprennent aussi du Python (pour projet math et projet info) en première et deuxième année. Ils font aussi du C dans certains projets. Certains font du java (parce qu'ils en ont envie ou que ça répond à une problématique pour un projet). Ceux qui en 3ème année feront de l'info toucheront à tout. Aucun ancien élève ingénieur que j'ai pu croiser par la suite ne m'a fait remonter qu'enseigner le Pascal en première et deuxième année était une annerie.
        
        Le Pascal est choisi comme premier langage dans le cadre de la programmation procédurale compilée.
        
        Ils apprennent un langage compilé en première année car certains d'entre eux seront amenés à développer des drivers, à gérer des problèmes numériques un peu touchy (impliquant une compréhension fine de la représentation des entiers et des flottants en machine). Rien de tel qu'un langage compilé pour cela (exemple: utiliser un record conditionnel en Pascal avec un champ entier sur 64 bits et un champ double sur 64 bits est une astuce (qui n'existe pas en Python) et qui permet d'inspecter bit à bit le contenu d'un double représenté abec la norme IEEE754.
        
        Ce n'est pas qu'une approche universitaire déconnectée du réel comme tu le sous entends mais ça répond à un besoin de compétences bien concret.
        
        [^] # Re: petit complément
        
        Posté par Nicolas Boulay (site web personnel) le 08 juin 2017 à 09:18. Évalué à 2.
        
        Qu'apporte le Pascal de plus que le C ?
        
        "La première sécurité est la liberté"
# Coquille

Posté par Blackknight (site web personnel, Mastodon) le 14 mai 2017 à 18:46. Évalué à 2.

J'ai oublié un mot !!

qui nous a amené à nous poser la question du "comment ksa fait sur les autres langages" :)

Pfff, on a beau se relire trois fois quand le cerveau veut pas voir, y a rien à faire :D
- [^] # Re: Coquille
  
  Posté par patrick_g (site web personnel) le 14 mai 2017 à 23:31. Évalué à 3.
  
  Corrigé.
# php

Posté par bunam le 14 mai 2017 à 18:48. Évalué à 4.
en ligne d commande :
```
php -r "echo 1 >> 64 ;"
1
```
- [^] # Re: php
  
  Posté par Faya le 14 mai 2017 à 23:12. Évalué à 6.
  
  La doc PHP prévient : https://secure.php.net/manual/fr/language.operators.bitwise.php
  
  Avertissement
  
  Décaler des entiers par des valeurs supérieures ou égales à la taille maximum des entiers supportés par le système peut induire un comportement non prévu. En d'autres mots, ne décallez(sic) pas plus de 31 bits sur un système 32 bits, ou plus de 63 bits sur un système 64 bits.
# Rust

Posté par Pinaraf le 14 mai 2017 à 19:04. Évalué à 10.
En rust ça compile pas :
```
error: bitshift exceeds the type's number of bits, #[deny(exceeding_bitshifts)] on by default
 --> src/main.rs:3:9
  |
3 |     a = a >> 64;
  |         ^^^^^^^

error: aborting due to previous error
```
- [^] # Re: Rust
  
  Posté par Dring le 19 mai 2017 à 21:33. Évalué à 2.
  
  Ah, cool. Dans le précédent journal, j'étais déçu par Rust, mais là c'est de la balle.
- [^] # Re: Rust
  
  Posté par barmic le 20 mai 2017 à 22:51. Évalué à 3.
  
  Mais s'agit d'il d'une véritable garantie ou est-ce que c'est une vérification opportuniste ?
  Que fait il s'il y est impossible de déterminer la valeur du décalage à la compilation ?
  
  Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
# Quelques autres

Posté par anaseto (site web personnel) le 14 mai 2017 à 19:05. Évalué à 6.
```
$ awk 'BEGIN{print(rshift(1,64))}'
1
$ perl -E 'say 1 >> 64'
0
$ tclsh8.6
% expr {1 >> 64}
0
$ cat main.go
package main

import "fmt"

func main() {
        fmt.Println(1 >> 64)
}
$ go run main.go
0
```
rust se démarque un peu : il n'en veut pas.
```
$ cat main.rs
fn main() {
    println!("{}", 1 >> 64);
}
$ rustc main.rs
error: bitshift exceeds the type's number of bits, #[deny(exceeding_bitshifts)] on by default
 --> main.rs:2:20
  |
2 |     println!("{}", 1 >> 64);
  |                    ^^^^^^^

error: aborting due to previous error
```
Et si on lui passe un nombre non constant qu'il peut pas prévoir, on a un crash.
```
$ cat main.rs
use std::env;

fn main() {
    let args: Vec<_> = env::args().collect();
    let n: i64 = args[1].parse().unwrap();
    println!("{}", 1 as i64 >> n);
}
$ rustc main.rs
$ ./main 64
thread 'main' panicked at 'attempt to shift right with overflow', main.rs:6
note: Run with `RUST_BACKTRACE=1` for a backtrace.
```
- [^] # Re: Quelques autres
  
  Posté par Blackknight (site web personnel, Mastodon) le 14 mai 2017 à 19:20. Évalué à 2.
  
  rust se démarque un peu : il n'en veut pas.
  
  Je me doutais un peu de ça quand j'ai regardé les specs de shr
  
  Et si on lui passe un nombre non constant qu'il peut pas prévoir, on a un crash.
  
  Voilà qui est sauvage !!
  - [^] # Re: Quelques autres
    
    Posté par Marc Quinton le 14 mai 2017 à 20:59. Évalué à 3.
    ruby :
```
marc@gigabyte:~$ irb
irb(main):001:0> 1>>64
=> 0
```
  - [^] # Re: Quelques autres
    
    Posté par lockidor le 15 mai 2017 à 02:10. Évalué à 3.
    
    Voilà qui est sauvage !!
    
    C'est dû au .unwrap(), qui s'applique sur un type algébrique contenant soit une valeur, soit une erreur, et qui renvoi la valeur s'il n'y a pas d'erreur et crash sinon.
    
    Dans un vrai programme bien propre, il faudrait vérifier qu'on a bien une valeur avant de s'en servir et le crash n'arriverait pas.
    - [^] # Re: Quelques autres
      
      Posté par anaseto (site web personnel) le 15 mai 2017 à 09:02. Évalué à 7.
      
      En fait non, ce n'est pas dû au .unwrap() (64 parse bien), mais bien à l'overflow, comme le précise le message d'erreur.
      - [^] # Re: Quelques autres
        
        Posté par anaseto (site web personnel) le 15 mai 2017 à 09:11. Évalué à 5.
        
        J'ai par contre maintenant une explication : ça n'arrive uniquement avec le build par défaut, qui est prévu pour débugger. Si on active les optimisations, on obtient 1 sans erreurs.
      - [^] # Re: Quelques autres
        
        Posté par lockidor le 16 mai 2017 à 02:18. Évalué à 1.
        
        Au temps pour moi ; je ne sais pas ce que j'ai lu quand j'ai écrit mon commentaire, mais pas ce qui était écrit en tout cas…
- [^] # Re: Quelques autres
  
  Posté par . le 15 mai 2017 à 07:56. Évalué à 2.
  
  Tiens, chez moi
  $ perl -E 'say 1 >> 64'
  me retourne 1 avec perl 5.20 et 0 avec perl 5.24.
  - [^] # Re: Quelques autres
    
    Posté par kantien le 15 mai 2017 à 08:19. Évalué à 6.
    Comme pour les autres, c'est dans la doc :
    Shifting by the number of bits in a native integer (or more) is zero, except when the "overshift" is right shifting a negative value under use integer , in which case the result is -1 (arithmetic shift).
    
    Until now negative shifting and overshifting have been undefined because they have relied on whatever the C implementation happens to do. For example, for the overshift a common C behavior is "modulo shift":
    
    1 >> 64 == 1 >> (64 % 64) == 1 >> 0 == 1 # Common C behavior. # And the same for <<, while Perl now produces 0 for both.
    
    Now these behaviors are well-defined under Perl, regardless of what the underlying C implementation does.
    Jusqu'à la 5.2, Perl se reposait sur l'implémentation en C et le comportement était indéfini; depuis la 5.4, le comportement est bien défini.
    
    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
- [^] # Re: Quelques autres
  
  Posté par reno le 15 mai 2017 à 14:42. Évalué à 2.
  
  Je suis surpris, c'est le cas aussi en mode 'release', je m'attendais à ce que ça soit le cas uniquement en mode debug.
# Primitive en C pour OCaml

Posté par kantien le 14 mai 2017 à 19:09. Évalué à 6.
En regardant le fichier d'implémentation et l'interface du module Int64, on tombe sur :
```
external shift_right : int64 -> int -> int64 = "%int64_asr"
external shift_right_logical : int64 -> int -> int64 = "%int64_lsr"
```
ce qui signifie que les fonctions sont des primitives codées en C (je n'ai pas trouvé le code C correspondant). Je suppose que la première doit correspondre à un décalage arithmétique et la seconde à un décalage logique. Ne connaissant pas la norme du C, mais elle doit rejoindre celle du C++ là-dessus, si c'est implementation defined alors le comportement des fonctions OCaml dépend du compilateur C utilisé et donc il paraît normal que le comportement soit non spécifié.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
- [^] # Re: Primitive en C pour OCaml
  
  Posté par Blackknight (site web personnel, Mastodon) le 14 mai 2017 à 19:17. Évalué à 2.
  Effectivement, tout s'explique.
  Je suppose que les fonctions asr et lsr sont du même acabit puisque
```
# 1 asr 64;;
- : int = 1
#
```
  Merci bien pour l'explication, je me doutais que je te verrai dans les parages avec mon exemple Ocaml :)
  - [^] # Re: Primitive en C pour OCaml
    
    Posté par kantien le 15 mai 2017 à 08:37. Évalué à 4.
    Je suppose que les fonctions asr et lsr sont du même acabit
    
    Tu supposes bien, elles sont définies dans le module Pervasives :
```
external ( lsl ) : int -> int -> int = "%lslint"
external ( lsr ) : int -> int -> int = "%lsrint"
external ( asr ) : int -> int -> int = "%asrint"
```
    et la doc précise bien que le comportement est non spécifié :
```
val (lsl) : int -> int -> int
  n lsl m shifts n to the left by m bits. The result is unspecified if m < 0 or m >= bitsize, where bitsize is 32 on a 32-bit platform and 64 on a 64-bit platform.

val (lsr) : int -> int -> int
  n lsr m shifts n to the right by m bits. This is a logical shift: zeroes are inserted regardless of the sign of n. The result is unspecified if m < 0 or m >= bitsize.

val (asr) : int -> int -> int
  n asr m shifts n to the right by m bits. This is an arithmetic shift: the sign bit of n is replicated. The result is unspecified if m < 0 or m >= bitsize.
```
    Reste la question : pourquoi avoir suivi le comportement du C au lieu de définir le résultat proprement ? Je n'en ai aucune idée.
    
    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
- [^] # Re: Primitive en C pour OCaml
  
  Posté par Def le 15 mai 2017 à 12:19. Évalué à 9.
  
  Quand une primitive commence par "%" elle n'est pas implémentée en C mais doit être gérée par le "backend". On peut voir la traduction dans la représentation intermédiaire ici: translcore.ml#L293.
  
  Pour le backend bytecode (interpréteur), la compilaton se fera vers un opcode dédié pour les entiers taggés (bytegen.ml#L344), et une fonction C externe pour les autres types entiers (bytegen.ml#L420) de la forme:
  caml_{nativeint,int32,int64}_shift_{left,right,right_unsigned} (bytegen.ml#L312).
  
  Pour les backend natifs, la procédure est un peu plus longue. D'abord quelques optimisations (constant folding dans closure.ml puis unboxing dans cmmgen.ml. Après ces passes, on a encore un langage indépendant de la plateforme ciblée, CMM et les opérations sont maintenant nommées Clsl, Clsr et Casr (cmm.mli#L115).
  
  Les étapes suivantes vont traduire la primitive vers la ou les instructions appropriées de l'architecture cible: abstraite par Mach.Iasr, implémentée directement par les émetteurs de code (voir Iasr dans arm, arm64, une abstraction de plus pour
  amd64 et i386).
  
  Et ça peut expliquer pourquoi une sémantique sous-spécifiée a été choisie (mais je spécule) : les shifts sont traduits vers du code très efficace, mais leurs sémantiques côté machine change selon les plateformes. X86 masque les 5 ou 6 derniers bits avant, et donc ça se comporte comme une fonction périodique, ARM sature. Le choix d'OCaml est donc un comportement avec une spécification suffisante mais minimale, et proche de la plateforme pour (le code généré est "prédictible" et efficace). L'utilisateur a toujours la possibilité d'implémenter des fonctions plus fortement spécifiées, le coût ne devrait pas être prohibitif.
  - [^] # Re: Primitive en C pour OCaml
    
    Posté par kantien le 15 mai 2017 à 15:49. Évalué à 4.
    Merci beaucoup pour toutes ces précisions, je comprends mieux ce qui se passe (ainsi que l'organisation interne du compilateur).
    
    Et ça peut expliquer pourquoi une sémantique sous-spécifiée a été choisie (mais je spécule) : les shifts sont traduits vers du code très efficace, mais leurs sémantiques côté machine change selon les plateformes.
    
    En spéculant aussi, j'en arrive à la même conclusion. D'appelant en appelé, on finit toujours par appeler en toute fin une instruction machine : autant prendre le plus dénominateur commun des architectures. Cela permet d'avoir le code le plus efficace sur toute les architectures, et si l'appelant veut une spécification plus large, il la code lui même, ce n'est pas bien compliqué.
```
let rec ( << ) m n = 
 if n < 0 then m >> (~- n)
 else if n >= 64 then Int64.minus_one
 else Int64.shift_left m n
and ( >> ) m n =
  if n < 0 then m << (~- n)
  else if n >= 64 then Int64.zero
  else Int64.shift_right m n;;
val ( << ) : int64 -> int -> int64 = <fun>
val ( >> ) : int64 -> int -> int64 = <fun>

1L >> 63;;
- : int64 = 0L

1L >> 64;;
- : int64 = 0L

1L >> (-64);;
- : int64 = -1L

1L >> (-63);;
- : int64 = -9223372036854775808L
```
    Je pense que ce doit être aussi la raison pour laquelle en C ou C++ le comportement n'est pas spécifié. Ce sont des instructions très bas niveau, cela permet d'avoir l'instruction la plus efficace sur chaque architecture et il est de la responsabilité de l'appelant de vérifier que le second paramètre se trouve bien dans les bornes où la fonction fait sens sans ambiguïté. Dans des langages haut niveau, on peut même se demander si le choix de la structure de données est le plus adapter au problème si l'on se retrouve à devoir gérer des cas en dehors des bornes « naturelles ».
    
    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
    - [^] # Re: Primitive en C pour OCaml
      
      Posté par kantien le 15 mai 2017 à 16:10. Évalué à 4.
      Je me suis précipité dans mon code, celui-ci est plus « naturel » :
      
      let rec ( << ) m n = if n < 0 then m >> (~- n) else if n >= 64 then Int64.zero else Int64.shift_left m n and ( >> ) m n = if n < 0 then m << (~- n) else if n >= 64 then (if Int64.compare m Int64.zero < 0 then Int64.minus_one else Int64.zero) else Int64.shift_right m n;; val ( << ) : int64 -> int -> int64 = <fun> val ( >> ) : int64 -> int -> int64 = <fun>
      
      et on a une certaine cohérence :
      
      -16L << 60;; - : int64 = 0L -1L << 64;; - : int64 = 0L -16L >> 60;; - : int64 = -1L -1L >> 64;; - : int64 = -1L
      
      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
    - [^] # Re: Primitive en C pour OCaml
      
      Posté par snowball (site web personnel) le 16 mai 2017 à 09:07. Évalué à 6.
      Ce sont des instructions très bas niveau, cela permet d'avoir l'instruction la plus efficace sur chaque architecture et il est de la responsabilité de l'appelant de vérifier que le second paramètre se trouve bien dans les bornes où la fonction fait sens sans ambiguïté.
      
      Tu peux très bien faire, comme en Ada, ou en Haskell, et laisser une instruction de haut niveau de décalage et une autre de bas niveau plutôt que de se contenter des limitations de bas niveau liées au fonctionnement du processeur.
      
      Exemple, en Ada, tu peux écrire ceci
      
      with interfaces; use interfaces; subtype amount is natural range 0..2**6 - 1; function my_clean_shr (u : unsigned_64; a : amount) return unsigned_64 is (Shift_Right (u,a));
      
      Ce programme créée un type amount (sous type de natural) dont les éléments sont nécessairement entre 0 et 63 (si ce n'est pas le cas, une exception est levée).
      Puis il crée une fonction de décalage qui permet au processeur d'optimiser au maximum le shift_right. Qu'est-ce qu'on y gagne ?
      
      Celui qui code a maintenant obligatoirement conscience du problème du décalage qui doit être inférieur à 64 puisque s'il ne fournit pas un 'a' dans 0..63 alors le programme lancera une exception à l'exécution (et à la compilation, si la règle n'est pas respectée statiquement, ça passera pas)
      
      La fonction my_clean_shr peut maintenant être optimisée par le compilateur et avoir la même efficacité que ce qu'on peut faire salement en C sans prévenir qui que ce soit.
      
      Une fois le code pondu et testé, il sera toujours possible par la suite, de retirer l'option de compilation de vérification des ranges (avec l'option -gnatp donnée à gcc).
      
      Au final, on a une fonction de haut niveau optimisée comme si on faisait du C mais avec du code qui est clair pour tout relecteur du code.
      
      On pourra aussi plus simplement utiliser le décalage (nécessairement un peu plus lent) fourni par Ada qui ne souffre lui d'aucun problème de définition et renvoie toujours un résultat mathématiquement cohérent .
      
      Ce n'est pas parce qu'on manipule des concepts de bas niveau qu'on doit les traiter en restant bas niveau au niveau du langage. J'aurais même tendance à dire le contraire. Pour cela il faut utiliser un langage qui le permet (c'est pour ça que j'adore l'Ada, vous l'aurez remarqué :) )
# Undefined behavior

Posté par ®om (site web personnel) le 14 mai 2017 à 20:10. Évalué à 9.
```
// test.c
#include <stdio.h>

int main() {
    long i = 1;
    long x = i >> 64;
    long y = 1 >> 64;
    if (x != y)
        printf("undefined behavior spotted\n");
    return 0;
}
```
```
$ gcc -w test.c -o test && ./test
undefined behavior spotted
$ gcc -w -O1 test.c -o test && ./test
```
blog.rom1v.com
- [^] # Re: Undefined behavior
  
  Posté par snowball (site web personnel) le 15 mai 2017 à 08:02. Évalué à 2.
  
  Merci pour la remarque sur l'optimisation du compilateur (qui considère le programme comme non défini).
  Du coup je suis allé me balader ici : http://blog.rom1v.com/2014/10/comportement-indefini-et-optimisation/ et j'ai mieux compris ton post :)
  
  L'optimisation choisie par le compilateur confirme ce que je pensais: si l'on doit donner une valeur au résultat (non défini d'après la doc), ça ne peut être que la valeur 0 (la seule qui soit parfaitement logique).
  Etonant ce choix de ces langages qui considèrent le résultat comme indéfini en suivant pile poil les limitations du processeur et son jeu d'instructions.
  - [^] # Re: Undefined behavior
    
    Posté par David Marec (site web personnel) le 16 mai 2017 à 09:10. Évalué à 4.
    'optimisation choisie par le compilateur confirme ce que je pensais: si l'on doit donner une valeur au résultat (non défini d'après la doc)
    ça ne peut être que la valeur 0 (la seule qui soit parfaitement logique).
    
    En fait, non. Si vous regardez le code généré, l'optimisation va zapper tout le code et se résumer à
```
int main(){
 return 0;
}
```
    Si vous forcez l'affichage du résultat, GCC7 donnera 0, CLang donnera ce qu'il trouve sous la variable.
    Mais aucun des deux ne tentera de faire un shr.
    - [^] # Re: Undefined behavior
      
      Posté par snowball (site web personnel) le 16 mai 2017 à 09:42. Évalué à 3.
      
      Ah ok !
      Effectivement, je n'avais pas compris les choses ainsi.
      
      La question qui reste c'est "pourquoi un langage au dessus de l'assembleur ne définit-il pas a>>b dès que b dépasse la taille machine de a ? Qu'est-ce que ça apporte de laisser cette expression indéfinie alors qu'elle a naturellement du sens ?"
# La réponse est dans la doc

Posté par Taurre le 14 mai 2017 à 21:00. Évalué à 10.

Salut,

À noter que la réponse est à trouver en Assembleur, et plus précisément dans la doc de référence d'AMD ou d'Intel (
AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions, rev. 3.20, p. 283).

The processor masks the upper three bits of the count operand, thus restricting the count to a number
between 0 and 31. When the destination is 64 bits wide, the processor masks the upper two bits of the
count, providing a count in the range of 0 to 63.

Autrement dit, spécifier un nombre supérieur à 63 ne comportant pas d'autres bits à un que les deux derniers revient à préciser un décalage de zéro, ce qui correspond bien à ce que l'on obtient pour 64, mais aussi 128 et 192. ;)
- [^] # Re: La réponse est dans la doc
  
  Posté par Blackknight (site web personnel, Mastodon) le 14 mai 2017 à 21:09. Évalué à 1.
  
  Autrement dit, spécifier un nombre supérieur à 63 ne comportant pas d'autres bits à un que les deux derniers revient à préciser un décalage de zéro, ce qui correspond bien à ce que l'on obtient pour 64, mais aussi 128 et 192. ;)
  
  Je suis bien d'accord avec le fait qu'en assembleur, il est normal d'avoir un type modulaire pour cela mais bon, là, on parle de langage de haut niveau :D
  C'est bien pour cela que je parle de "problème" entre guillemets ;)
  - [^] # Re: La réponse est dans la doc
    
    Posté par Marotte ⛧ le 14 mai 2017 à 21:44. Évalué à 5. Dernière modification le 14 mai 2017 à 21:44.
    
    on parle de langage de haut niveau :D
    
    Oui mais le décalage de bit ça reste une manipulation de bas niveau.
    - [^] # Re: La réponse est dans la doc
      
      Posté par snowball (site web personnel) le 14 mai 2017 à 21:49. Évalué à 2. Dernière modification le 14 mai 2017 à 21:54.
      
      Il n'y a pas de contradiction.
      On peut utiliser un langage de haut niveau pour faire des opérations de bas niveau. L'Ada est parfait pour cela ( cf https://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/representation_clauses_and_pragmas.html )
      On peut aussi utiliser un langage de bas niveau pour faire des opérations de bas niveau (c'est juste moins pratique car le jeu d'instruction est plus limité).
- [^] # Re: La réponse est dans la doc
  
  Posté par snowball (site web personnel) le 14 mai 2017 à 21:37. Évalué à 8.
  
  Quelqu'un qui code en Pascal et qui a besoin de décaler de n bits vers la droite un espace mémoire donné n'a, a priori, pas à connaître le processeur de la machine pour lequel son code va être compilé et encore moins les limitations un poil "étranges" du jeu d'instructions de celui-ci.
  
  D'ailleurs Ada remplit, quant à lui, pleinement ce rôle qu'on attend d'un langage de haut niveau et renvoie un résultat cohérent quelque soit le processeur et son jeu d'instructions.
  
  Pour la petite histoire, les étudiants qui ont bossé sur le projet que je leur ai donné, n'ont pas tous détecté ce comportement étrange. C'est un seul binôme (sur 25) qui, au cours de tests unitaires, s'est demandé pourquoi de temps en temps des valeurs aberrantes apparaissaient alors que l'algo tenait parfaitement la route. Il a fallu pas mal de temps avant d'identifier la cause du bug et s'apercevoir aussi que la documentation de Fpc ne disait rien à ce sujet.
# en LLVM

Posté par serge_sans_paille (site web personnel) le 14 mai 2017 à 21:33. Évalué à 4.

Comme en en C ou en C++, sans surprises, d'après la doc http://llvm.org/docs/LangRef.html#lshr-instruction
If op2 is (statically or dynamically) equal to or larger than the number of bits in op1, the result is undefined.Donc undefined behavior
# C'est décrit dans la spec de Java

Posté par TilK le 14 mai 2017 à 23:02. Évalué à 4.
Je reprend ton exemple :
```
public class Shift {
    public static void main(String[] args) {
        int a = 1;
        System.out.println("Resultat : " + (a >> 64));
    }
}
```
La spécification explique :

If the promoted type of the left-hand operand is int, only the five lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x1f (0b11111). The shift distance actually used is therefore always in the range 0 to 31, inclusive.

Dans notre cas, vu que 64 (0x40) & 0x1f est égal à 0, on fait donc 1 >> 0, et donc cela vaut bien 1. C'est la même chose pour les long avec un masque plus gros d'un bit.

En gros, Java autorise n'importe quelle distance, mais si c'est plus gros que la taille de l'opérande de gauche, il fait un modulo pour avoir une valeur utilisable.
- [^] # Re: C'est décrit dans la spec de Java
  
  Posté par snowball (site web personnel) le 14 mai 2017 à 23:36. Évalué à 2.
  
  Je me demande si c'est un choix.
  Ce que fait Java c'est ce que fait l'instruction assembleur (un modulo la taille de l'opérande de gauche sur l'opérande droite avant le shift).
  
  Or, je ne comprends pas ce comportement. Mathématiquement il n'y a aucune raison objective d'agir ainsi. D'ailleurs, certains langages de haut niveau font ce que la logique commande (Python ou Ada par exemple) et d'autres appellent simplement la commande assembleur reproduisant ainsi le même comportement "illogique".
  - [^] # Re: C'est décrit dans la spec de Java
    
    Posté par TilK le 15 mai 2017 à 10:19. Évalué à 0.
    
    A mon avis, c'est clairement un choix. Cela ressemble très fortement à un integer underflow/overflow.
    
    Il y a habituellement 3 façons de les gérer :
    1. en renvoyant une erreur,
    2. en utilisant une arithmétique saturée,
    3. en utilisant une arithmétique modulaire.
    
    Ici, tu t'attends à avoir une arithmétique saturée, car cela ressemble le plus au résultat d'une division arithmétique. Je pense que certains langages ont pris le choix d'un modulo ici pour être cohérent avec leurs autres opérateurs qui utilisent une arithmétique modulaire.
    - [^] # Re: C'est décrit dans la spec de Java
      
      Posté par snowball (site web personnel) le 15 mai 2017 à 19:17. Évalué à 3.
      hmmmm,
      
      Pour ton 1. : pourquoi renvoyer une erreur (ie lever une exception) ? Qu'est-ce qui le justifierait ? Je ne me place pas dans la logique du hardware mais plutôt de ce pour quoi est fait un proco: faire du calcul mathématique.
      
      Pour ton 2. le résultat d'un shift à droite est borné (par les bornes de l'opérande de gauche) et toujours mathématiquement défini. Donc il n'y a rien à gérer ici en terme de "saturation".
      
      Pour ton 3. L'arithmétique modulaire est la base de calcul de tous les processeurs courants. C'est à dire que l'ensemble des opérations arithmétiques +, -, * doit donner un résultat juste modulo où n désigne le nombre de bits (commun) des entiers machines manipulés. Il n'y a donc jamais ni d'"underflow" ni d'"overflow" chez les entiers machines. Par contre, l'utilisateur final qui ne connaîtrait pas ce mode de fonctionnement pourrait interpréter les résultats modulaires comme des erreurs de calcul.
      
      Par exemple, si je veux le quotient de $3^{65536}$ par , on peut procéder en C avec le code suivant
      
      unsigned char u = 3, i=0; // Je décide de calculer avec u modulo 256 for (; i <16; i++,u*=u); // J'élève 16 fois au carré successivement la variable u // Je suis certain, qu'en sortie, le calcul a été fait dans l'anneau des entiers modulaires modulo 256 et que u contient le résultat.
      
      On pourrait croire dans cet exemple qu'il y a de l'overflow de partout, mais il n'en est rien. Tout est calculé modulo 256 et c'est dans le cahier des charges du processeur que de bien respecter cette règle.
      
      Pour ce qui concerne l'opération de shift à droite, elle ne fait pas partie des opérations +, - , * et ne devrait répondre qu'au seul problème du quotient d'un entier machine entre 0 et $2^{n-1}$ par une puissance positive quelconque de 2. En ce sens, le résultat initial devrait donner 0 (en tout cas jamais 1 !).
      
      Que le jeu d'instructions du processeur exige pour des raisons techniques des arguments bornés, on peut le comprendre, mais que des langages au dessus reproduisent la même chose, je ne comprends pas l'intérêt (à vrai dire il n'y a pas d'intérêt à laisser le résultat indéfini alors qu'il y a un sens tout à fait évident à donner).
      
      D'ailleurs je ne suis pas surpris qu'Ada ou Haskell donnent le comportement attendu (le comportement inattendu étant même qualifié de 'unsafe' par le compilo).
      - [^] # Re: C'est décrit dans la spec de Java
        
        Posté par snowball (site web personnel) le 17 mai 2017 à 08:47. Évalué à 1.
        
        Coquilles !
        1) Mon bout de code en C donne évidemment le reste par 256 et non le quotient.
        2) "[…] et ne devrait répondre qu'au seul problème du quotient d'un entier machine entre 0 et " et non " $2^{n-1}$ ".
# En python - mise en boite des nombres

Posté par Alex G. le 14 mai 2017 à 23:28. Évalué à 8.
En fait Python ne va pas déléguer l'opération directement au processeur comme d'autre langage, car il fait du "boxing", c'est à dire il ne permet pas à un nombre de déborder, mais gère des nombres aléatoirement grand.

J'ai pu utiliser ça il y a pas longtemps pour comparer des vecteurs de grandes tailles, et approximer un log likehood par un xor (ça marchait car je comparais deux vecteurs pour des valeurs oui/non, donc binaire). En gros je devais compter les faux positifs et faux négatifs (donc là où j'avais 1 quand j'aurais du avoir 0, et 0 quand j'aurais du avoir 1, ce que xor peut permettre de compter).
Je me suis aperçu que malgré la "mise en boite" (et donc pas mal de calculs en plus de la part de python), le xor restait assez rapide même sur de très grand nombres (de 500 000 chiffres).
```
In [5]: import random
In [7]: x = int("".join(random.choice(["0", "1"]) for i in range(500000)), 2)
In [8]: y = int("".join(random.choice(["0", "1"]) for i in range(500000)), 2)
In [9]: %timeit x ^ y
The slowest run took 10.90 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 8.94 µs per loop
```
Je pense que le premier essais est plus long à cause des chargement de la mémoire (pour les deux autres itérations, le cache du processeur joue).
- [^] # Re: En python - mise en boite des nombres
  
  Posté par Alex G. le 14 mai 2017 à 23:30. Évalué à 3.
  Ah et juste pour donner une idée:
```
In [12]: len(str(2**500000))
Out[12]: 150515
```
  ce sont des nombres qui en décimal font 150000 chiffres.
# léger HS: coquille sur C++ (et C++!=C)

Posté par gaaaaaAab le 15 mai 2017 à 06:43. Évalué à 7.

Sur le fond du journal, c'est un détail, mais si le C est du C++ valide, le contraire n'est pas vrai. Pour avoir un exemple en C/C++, il aurait fallu préférer une version en C avec du bon vieux stdio.h et du printf :-)

Avec la suite gcc/g++ 6.3, le warning est identique en C (ce qui n'est pas du tout surprenant).

sinon, dans cette exemple, tu as écrit un décalage à gauche au lieu d'un décalage à droite (j'imagine que tu t'es laissé embarquer par l'opérateur du cout)
- [^] # Re: léger HS: coquille sur C++ (et C++!=C)
  
  Posté par David Marec (site web personnel) le 15 mai 2017 à 09:14. Évalué à 5.
  
  Oui,je trouve malvenu de mettre les deux langages dans le même panier pour ce genre de problème.
  Si, dans le cas présent, la norme dit la même chose: «undefined behavior», il faut se méfier; ce n'est pas toujours vrai.
  
  À vérifier, mais je crois qu'il y a eu une tentative de «normaliser» le résultat en C++.
  - [^] # Re: léger HS: coquille sur C++ (et C++!=C)
    
    Posté par gaaaaaAab le 15 mai 2017 à 10:01. Évalué à 2.
    
    bien vu !
    Je me suis arrêté à "le compilo donne le même warning pour les deux", mais c'est vrai que ça ne suffit pas.
    Cela dit, même entre deux versions d'un seul compilateur sur un seul langage, on pourrait aussi avoir des comportements différents (surtout sur des comportements non définis).
    Dans l'absolu, il faudrait en fait préciser le couple (langage, compilo) pour chaque exemple, mais ça devient vite vachement moins facile à appréhender.
    - [^] # Re: léger HS: coquille sur C++ (et C++!=C)
      
      Posté par David Marec (site web personnel) le 15 mai 2017 à 13:42. Évalué à 2.
      
      Cela dit, même entre deux versions d'un seul compilateur sur un seul langage,
      on pourrait aussi avoir des comportements différents
      (surtout sur des comportements non définis).
      
      Dans un monde idéal, cela ne devrait arriver que pour les comportements indéfinis.
      Mais, comme on l'a vu dans une précédente dépêche sur l'ordre d'évaluation en C++, c'est aussi le cas lorsque on laisse trop le champ libre à l'interprétation.
      
      Dans l'absolu, il faudrait en fait préciser le couple (langage, compilo) pour chaque exemple,
      mais ça devient vite vachement moins facile à appréhender.
      
      Plus traître: activez les optimisations … et vous obtiendrez 0 en C++ et en C avec GCC7 et n'importe quoi avec CLang4.
      Parce qu'aucun des deux n’effectuera de shr lors de l'optimisation, en fait.
- [^] # Re: léger HS: coquille sur C++ (et C++!=C)
  
  Posté par Blackknight (site web personnel, Mastodon) le 15 mai 2017 à 09:31. Évalué à 1.
  
  sinon, dans cette exemple, tu as écrit un décalage à gauche au lieu d'un décalage à droite (j'imagine que tu t'es laissé embarquer par l'opérateur du cout)
  
  Whaa ! L'andouille !! J'avais pas vu ça :)
  Tu as raison, j'ai dû me laisser embarquer par << ce qui ne serait pas arrivé si j'avais fait du C ;)
- [^] # Re: léger HS: coquille sur C++ (et C++!=C)
  
  Posté par maxb le 15 mai 2017 à 14:42. Évalué à 3.
  Sur le fond du journal, c'est un détail, mais si le C est du C++ valide, le contraire n'est pas vrai.
  
  Si l'on veut vraiment être précis, ce n'est même pas vrai dans ce sens là non plus.
  Il me semble que la ligne suivante, tout à fait correcte en C, n'est pas valide en C++:
```
char *toto = malloc(12);
```
  La vérité, c'est que C et C++ sont deux langages distincts et que ça n'a pas de sens de parler de C/C++ comme on le voit (trop) souvent.
  - [^] # Re: léger HS: coquille sur C++ (et C++!=C)
    
    Posté par gaaaaaAab le 15 mai 2017 à 14:56. Évalué à 2.
    
    Ça peut avoir du sens de regrouper C et C++ dans certains contextes.
    
    Ça m'étonnerait un peu si c'était pas du C++ valide, parce que il me semble que la compatibilité avec le C était un principe très significatif lors de la conception du C++.
    Mais comme je pratique pas beaucoup le C++, je ne sais pas trop. En tout cas, avec le drapeau -fpermissive, g++ considère que c'est un warning, et accepte de compiler.
    - [^] # Re: léger HS: coquille sur C++ (et C++!=C)
      
      Posté par maxb le 15 mai 2017 à 15:02. Évalué à 2.
      
      C'était peut-être le cas au début, mais les langages ont bien divergé depuis le temps… Je ne pratique pas le C++ non plus, mais l'option -fpermissive est assez explicite : par défaut, c'est une erreur et ce n'est pas du C++ valide. Il faut forcer la main au compilateur pour qu'il accepte cette construction.
      - [^] # Re: léger HS: coquille sur C++ (et C++!=C)
        
        Posté par gaaaaaAab le 15 mai 2017 à 15:38. Évalué à 2.
        
        je suis allé regarder le man de g++. Effectivement, -permissive permet de compiler du code non conforme. Donc, un point pour toi, et je suis surpris :-) Je ne dirais donc plus que C est un sous-ensemble de C++.
    - [^] # Re: léger HS: coquille sur C++ (et C++!=C)
      
      Posté par Anthony Jaguenaud le 15 mai 2017 à 15:50. Évalué à 4. Dernière modification le 15 mai 2017 à 15:53.
      En fait, en C tu peux faire :
      
      (Type *) ==> void *
      et (void *) ==> (Type *)
      
      alors qu’en C++
      Tu peux faire (Type *) ==> void *
      mais il faut un cast explicite pour faire (void *) ==> (Type *).
      
      le prototype de malloc étant :
      
      void *malloc(size_t);
      
      C’est bien un cast de void * ==> vers un autre type.
      
      J’ai toujours pensé que ça vient de l’héritage :
      
      class Mere; class Fille:public Mere; // Alors Fille *fille; Mere *maman = fille; // Ok fille = maman; // Ko
      
      Si on considère que tous les types dérives de void alors ça a du sens.
# C#

Posté par Buf (Mastodon) le 15 mai 2017 à 08:24. Évalué à 4.
```
long n = 1;
Console.Write(n >> 64);
```
affiche 1.

Mais le comportement est spécifié :

When the type of x is long or ulong, the shift count is given by the low-order six bits of count. In other words, the shift count is computed from count & 0x3F

Spec

Autrement dit, un décalage de 64 est considéré comme un décalage de 0, parce que seuls les 6 bits de poids faibles sont pris en compte.
# Javascript

Posté par Pierre-Marie D le 15 mai 2017 à 09:24. Évalué à 4.
Idem en JS:
```
const a=1;
console.log(a>>63); // 0
console.log(a>>64); // 1
console.log(a>>65); // 0
```
Avec FF53 et NodeJS 6.9.2.
Voici ce qui est précisé dans le MDN:

Les opérateurs de décalage convertissent leurs opérandes en entiers 32 bits en ordre big-endian et renvoient un résultat du même type que l'opérande de gauche. L'opérande droit doit être inférieur à 32, sinon les cinq bits les plus faibles seront utilisés.
- [^] # Re: Javascript
  
  Posté par TilK le 15 mai 2017 à 09:45. Évalué à 2.
  
  A priori, ce n'est pas spécifique à mozilla, c'est comportement est défini dans les spécifications d'ECMAScript.
  
  Let shiftCount be the result of masking out all but the least significant 5 bits of rnum, that is, compute rnum & 0x1F
# En GO

Posté par eggus le 15 mai 2017 à 12:30. Évalué à 6.
```
    func main() {
        var i uint64
        i = 1
        fmt.Printf("i >> 64 : %d\n", i >> 64)
    }
```
Résultat :

i >> 64 : 0

Et le résultat est documenté dans la documentation du langage :

There is no upper limit on the shift count. Shifts behave as if the left operand is shifted n times by 1 for a shift count of n. As a result, x << 1 is the same as x*2 and x >> 1 is the same as x/2 but truncated towards negative infinity.
# Même avec le shell ça marche

Posté par calandoa le 15 mai 2017 à 15:56. Évalué à 4.
```
$ echo 1 >> 64
1
```
Et en plus c'est posix !

(bon ok, avant il faut faire :
$ ln -s /dev/sdout 64
)

Je laisse à des plus malins que moi la ruse pour :
$ echo 1 >> 63 0
- [^] # Re: Même avec le shell ça marche
  
  Posté par calandoa le 15 mai 2017 à 16:03. Évalué à 3.
  J'ai bien pensé à :
```
$ mkfifo 64
$ sed s/1/0/ < 64 &
```
  mais la sortie est toute crade :
```
$ echo 1 >> 64
$ 0

[1]  + done       sed s/1/0/ < 64
$
```

# En Haskell

Posté par hsyl20 (site web personnel) le 15 mai 2017 à 16:14. Évalué à 7.

> import Data.Word
> import Data.Bits
> (1 :: Word64) `shiftR` 64
0
> (1 :: Word64) `unsafeShiftR` 64
1

# bash

Posté par Old Geek le 16 mai 2017 à 09:09. Évalué à 3.

idem en bash
```
echo $((1>>63))
0

echo $((1>>64))
1
```

# Du haut niveau pour gérer correctement du bas niveau

Posté par snowball (site web personnel) le 17 mai 2017 à 01:16. Évalué à 10.

Ce journal montre que beaucoup de langages au dessus de l'assembleur se contentent de répliquer ce que fait le jeu d'instructions du processeur (et donc font que a >> b est indéfini dès que la valeur de b dépasse la taille machine de a en supposant que le développeur a lu la doc dans les moindres détails. Certes on est tous censés lire la doc, mais malgré tout, on augmente le risque de bugs en laissant ce genre de situations indéfinies).

Certains langages donnent un sens à "a>>b" cohérent avec les mathématiques quelque soient les valeurs de b.

J'ai cru comprendre que pour certains "décaler les bits, c'est du bas niveau, donc c'est normal qu'on ne fasse pas davantage que le jeu d'instructions du processeur". D'autres ont plutôt dit que "si on programme au dessus de l'assembleur, on perd du temps alors qu'un shr sert en général à optimiser à fond à bas niveau".

Je mettrais un bémol. Je pense qu'un langage de haut niveau peut permettre de régler les deux problèmes précédents.

Exemple en Ada:

with interfaces;use  interfaces;
[...]
  subtype amount is natural range 0..2**6 - 1;
  function my_clean_shr (u : unsigned_64; a : amount ) return unsigned_64 is (Shift_Right (u,a));
  function my_shr       (u : unsigned_64; a : natural) return unsigned_64 is (Shift_Right (u,a));

Ce bout de code crée un sous-type du type natural contraint aux valeurs de 0 à 63 puis définit deux fonctions de décalage.
La première exige que "amount" soit compris entre 0 et 63.
La seconde n'exige rien.

Lorsque l'on génère l'assembleur (avec l'option -O1) on obtient pour la première fonction

leaq    32(%rsp), %rsi
movl    $.LC0, %edx
shrq    %cl, %rax

et pour la deuxième

movl    $0, %edi
leaq    32(%rsp), %rsi
shrq    %cl, %rax
cmpl    $63, %r12d
movl    $.LC0, %edx

Le compilateur a donc généré un code plus efficace (et minimal) pour my_clean_shr (car on lui dit que l'argument "amount" est contraint entre 0 et 63 ; information dont il ne dispose pas pour my_shr).

Au final, comme je le disais un peu plus haut, on gagne sur tous les plans:
Le relecteur est au courant du problème de limitation de l'argument de droite de shr (car c'est dans la signature de la fonction).
Le code généré est aussi efficace que si on l'avait fait bêtement en C (l'assembleur est le même si on code my_shr à la mode C) avec toutes les petites surprises que ça peut laisser ces bouts de code potentiellement non définis.

(en espérant avoir été clair en cette heure tardive)

[^] # Re: Du haut niveau pour gérer correctement du bas niveau

Posté par kantien le 18 mai 2017 à 12:43. Évalué à 7.

Je me permets de concentrer dans ce commentaire ma réponse à celui-ci ainsi qu'à cet autre commentaire, étant donné que tu y reprends les mêmes idées. Tu as été clair malgré l'heure tardive, j'espère pouvoir faire de même en cette heure plus matinale.

Il me semble que dans ton approche de la question, tu mélanges plusieurs problématiques. Dans l'exemple que tu donnes ici, tu montres surtout comment un système de type avancé (ici une forme restreinte de type dépendant) permet d'être plus précis sur la spécification d'un code et comment un compilateur peut en tirer partie pour générer un code optimisé (ici en supprimant un test de comparaison à l'exécution rendu inutile par ton type amount). Cela rejoint un exemple que j'avais donné dans la dernière dépêche sur Haskell, où je montrais comment utiliser les GADT (types de données algébriques généralisés) pour exprimer la proposition : « tout arbre binaire parfait non vide a une racine ». Ce qui permettait de coder la fonction qui extrait cette racine sans que le code généré par le compilateur ait à vérifier à l'exécution que l'arbre était non vide (c'était déjà spécifié dans le type de la fonction).

Revenons à présent au sujet précis du journal : le décalage à droite bit à bit. Dans un autre commentaire, tu précises à bon droit que l'arithmétique modulaire est la base de tous les processeurs courants et dans le cas présent on fait de l'arithmétique dans l'anneau Z/nZ avec n = 2^64. Se pose alors la question que doit faire cette fonction de décalage à droite ? et tu réponds toi même : « [elle] ne devrait répondre qu'au seul problème du quotient d'un entier machine entre 0 et 2ⁿ - 1 par une puissance positive quelconque de 2 ». Ce à quoi je te répondrai : l'architecture X86 fait cela en restant dans le cadre de l'arithmétique modulaire, et ne la mélange pas avec de l'arithmétique sur les entiers. En effet prenons le type de cette fonction : function my_shr (u : unsigned_64; a : natural) return unsigned_64. Elle prend en paramètre un entier non signé sur 64 bits, un entier naturel et renvoie un entier non signé sur 64 bits. Or pour opérer au sein de l'anneau sus-mentionné, elle doit donc associer un élément de cette anneau au paramètre a : natural, puis renvoyer ensuite le quotient d'une division euclidienne effectuée au sein de l'anneau. Les processeurs X86 on fait le choix de prendre l'élément 2 ^ (a % 64), ce qui peut sembler assez « naturel » lorsque l'on pratique l'arithmétique modulaire. Exemple en OCaml sur mon X86 :

Int64.(shift_right 4L 0);;
- : int64 = 4L

Int64.(shift_right 4L 1);;
- : int64 = 2L

Int64.(shift_right 4L 64);;
- : int64 = 4L

Int64.(shift_right 4L 65);;
- : int64 = 2L

En revanche, de ce que j'ai compris, l'architecture ARM ne voit pas cela du tout comme une opération d'arithmétique modulaire, mais semble considérer une telle donnée (un entier non signé sur 64 bit) comme un suite finie de 0 et de 1 ou plutôt comme une suite stationnaire de valeur nulle à partir du rang 64 et si tu lui donne la suite u(n) elle te renvoie la suite u(n+a). Ce qui semble être le comportement que tu souhaiterais, mais ce n'est pas du tout le point de vue de l'arithmétique modulaire. Autrement dit, elle voit un entier de 64 bit comme un entier naturel compris entre 0 et 2^64 - 1 représenté en base 2, effectue une division euclidienne par une puissance de 2 et opère donc sur l'ensemble des entiers naturels.

Viens maintenant le problème des langages compilés et de la spécification qu'ils donnent à une telle primitive. Ils pourraient tout à fait faire un choix strict et défini en optant pour la vision modulaire à la X86 ou la vision entière à la ARM. La plupart on choisit d'utiliser pour chaque architecture la primitive correspondante du processeur et elle n'est donc spécifiée et définie que sur le domaine où elles coïncident, à savoir 0≤ a < 64. Si le programmeur veut une fonction plus fortement spécifiée, alors il n'a qu'à la coder lui-même.

Tu concluais ton commentaire réponse par : « c'est pour ça que j'adore l'Ada, vous l'aurez remarqué :) », je terminerai le mien par j'adore le lamba-calcul typé et rien de plus normal pour le mathématicien et logicien que je suis :) Le lamba-calcul typé (dont font partie les langages comme Haskell, OCaml ou Coq) a pour principe fondamental la correspondance preuve-programme : une programme est la preuve d'un théorème dont l'énoncé est le type ! \o/

Ce qui donne le tableau suivant :

Informatique	Mathématiques
Type	Formule
Programme	Preuve
Primitive système	Axiome
Fonction de A vers B	Preuve de « A implique B »
Paire de A et B	Preuve de « A et B »
Type somme sur A et B	Preuve de « A ou B »
Interpréteur	Théorème de correction
Décompilateur	Théorème de complétude

Si l'on prend le langage qui a le système de type le plus sophistiqué (Coq), je te laisse deviner ce que fait une fonction dont le type est « pour tout (n: nat), il existe (p:nat) tel n ≤ p et p soit premier » si on lui passe un entier en entrée. En Coq, cela pourrait se définir ainsi :

Definition greater_prime (n:nat) :=
 {p :nat | n<=p /\ prime p}.

Theorem ma_fonction n : greater_prime n.
Proof.
(* la preuve *)
Qed.

Pas besoin d'aller lire la doc pour savoir ce que fait la fonction, la lecture de son type suffit à cela. ;-)

Au final si j'étais un peu taquin, en se basant sur la popularité des langages de programmation je dirais qu'à l'heure actuelle la programmation consiste, la plupart du temps, dans l'art de faire des mathématiques comme un goret dans des langages atrophiés. En conséquence, la seule chose à faire si l'on veut savoir ce que fait une fonction, c'est d'aller lire la doc : on ne peut pas se fier uniquement à son type ni à ses attentes. Et le seul moyen de vérifier qu'elle se comporte exactement comme le spécifie la doc, c'est d'aller lire le code d'où la condition sine qua non que celui-ci soit publiquement accessible. Voilà une leçon que pourront retenir tes étudiants de cet exercice.

Comme tu enseignes les mathématiques, si le sujet t'intéresse il y a un dossier sympa sur le sujet dans la gazette des mathématiciens d'octobre 2014 : théories des types et mathématiques certifiées, et la théorie homotopique des types pousse encore plus loin la correspondance que j'ai signalée plus haut et fournit des fondements élégants à l'ensemble de l'édifice mathématique.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

[^] # Re: Du haut niveau pour gérer correctement du bas niveau

Posté par snowball (site web personnel) le 18 mai 2017 à 16:42. Évalué à 2.

Bonjour,
Merci pour ton analyse (très claire, je te rassure !). Je te rejoins quasiment en tout point. Sauf sur le point clé suivant:

Les processeurs X86 pratiquent l'arithmétique modulaire c'est à dire respectent la structure d'anneau de $\mathbb{Z}/2^n\mathbb{Z}$ pour les lois et $\times$ où n est la taille des entiers machines manipulés.

Or, le décalage à droite n'est pas une opération arithmétique sur les éléments de $\mathbb{Z}/2^n\mathbb{Z}$ mais sur les représentants entiers de ces classes compris entre 0 et .

Cette opération agit en donnant le quotient entier (et non modulaire) par . En particulier 'a' n'a aucune raison d'être modulaire. Au contraire, c'est un comportement qui pose des problèmes (d'ailleurs le comportement est choisi comme "indéfini" dans la plupart des langages classiques).

Pour résumer grossièrement, aller coller de la modularité sur l'argument du shr n'a aucun fondement arithmétique que ce soit dans $\mathbb{Z}$ ou dans $\mathbb{Z}/2^n\mathbb{Z}$ .

Ou bien, dit autrement, quelle propriété arithmétique précise, un tel fonctionnement permet-il ?

Selon moi ce comportement n'a aucune raison théorique (éventuellement un historique technique tout au plus). Il est d'ailleurs intéressant de voir que Ada a décidé de corriger ce problème sur le haut niveau. Python et Haskell également.

Quand je disais que j'adorais Ada c'était dans le cadre précis de l'école où j'enseigne où l'on a besoin d'enseigner dans les langages compilés (pour des besoins d'ingénierie). Après si je sors ma casquette perso de prof de math, je dois avouer que je ne manipule quasiment aucun langage excepté du python via Sage.
- [^] # Re: Du haut niveau pour gérer correctement du bas niveau
  
  Posté par kantien le 19 mai 2017 à 12:59. Évalué à 2.
  
  Je te rejoins quasiment en tout point. Sauf sur le point clé suivant: […]
  
  Effectivement, c'est sur ce point que l'on diverge. C'est lorsque tu écris : « [elle] ne devrait répondre qu'au seul problème du quotient d'un entier machine entre 0 et 2n - 1 par une puissance positive quelconque de 2 » en parlant de la primitive shift_right. Pour moi, elle ne devrait rien être, mais elle est ce que l'implémenteur a décidé qu'elle serait. C'est tout le problème de la spécification d'un code. C'est pour cela que j'avais écrit :
  
  En conséquence, la seule chose à faire si l'on veut savoir ce que fait une fonction, c'est d'aller lire la doc : on ne peut pas se fier uniquement à son type ni à ses attentes. Et le seul moyen de vérifier qu'elle se comporte exactement comme le spécifie la doc, c'est d'aller lire le code d'où la condition sine qua non que celui-ci soit publiquement accessible. Voilà une leçon que pourront retenir tes étudiants de cet exercice.
  
  C'est un peu comme Hilbert qui disait qu'en géométrie on s'en fout des noms point, droite ou plan et qu'on pourrait les remplacer par chope de bière, chaise et table : ce qui compte c'est l'axiomatique des structures. Dans toute cette histoire, moi ce que je vois c'est que certains langages ne te fournissent pas de base l'axiomatique que tu souhaiterais. Ce à quoi je te réponds : ils te donnent néanmoins les moyens de construire la structure que tu désires. D'ailleurs au sujet de ADA, je suis allé voir la documentation est le moins que l'on puisse dire c'est que ni le type, ni son complément dans la documentation ne permet de savoir c'est que fait cette fonction shift_right. Même grâce au complément en langue anglaise, je trouve que l'on a là une sous-spécification de son comportement. Au moins, dans certains langages qui ne font pas ce que tu souhaites, avec la documentation on sait ce qu'elle doit faire.
  
  Au fond ce que je vois, c'est qu'on a un opérateur qui agit sur un cylindre : produit cartésien d'un anneau Z/nZ avec un domaine fini. Toi tu veux que l'on prolonge le cylindre en saturant sur sa valeur au bord (ARM), d'autres recollent les bouts et opèrent sur un tore (X86). Ce qui compte surtout c'est qu'il soit possible de faire des découpages et des collages pour construire la structure que l'on souhaite, et cela tous les langages le permettent. Le rôle d'un langage de haut niveau c'est de fournir des moyens plus abstrait que l'assembleur pour effectuer ces constructions puis de passer la main au compilateur pour traduire le tout en code machine. Apprendre un langage donné consiste essentiellement à apprendre les méthodes de construction qu'il fournit pour définir des structures ainsi que les moyens pour opérer sur celles-ci.
  
  Ce que tes étudiants ont expérimenté c'est qu'un tore est cyclique sur ces deux dimensions et qu'il n'a pas du tout la même géométrie qu'un cylindre. Ce qui me rappelle un épisode des Simpson dans lequel Stephen Hawking était très intéressé par la théorie d'Homer selon laquelle l'Univers avait la forme d'un Donuts. :-P
  
  Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
  - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
    
    Posté par shbrol le 19 mai 2017 à 14:23. Évalué à 1.
    
    Ce que tes étudiants ont expérimenté c'est qu'un tore est cyclique sur ces deux dimensions et qu'il n'a pas du tout la même géométrie qu'un cylindre. Ce qui me rappelle un épisode des Simpson dans lequel Stephen Hawking était très intéressé par la théorie d'Homer selon laquelle l'Univers avait la forme d'un Donuts. :-P
    
    Merci, beau résumé !
    - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
      
      Posté par kantien le 20 mai 2017 à 15:58. Évalué à 2.
      
      De rien. Je suis content de voir qu'il y a au moins une personne qui apprécie mon humour.
      
      Mais cette lecture peut au moins répondre partiellement à la question : que peut-on vouloir modéliser avec cela ? Une piste serait alors la modélisation de l'Odysée d'Ulysse dans une vision Homérique où il n'aurait fait que voyager sur un beignet. Les grecs anciens ayant été le premier peuple à émettre l'hypothèse que la terre ne serait ni plate ni sphérique mais aurait la forme d'un beignet ! :-P
      
      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
  - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
    
    Posté par snowball (site web personnel) le 19 mai 2017 à 15:54. Évalué à 2.
    Pour moi, elle ne devrait rien être, mais elle est ce que l'implémenteur a décidé qu'elle serait.
    - Le modèle mémoire que l'on manipule, quand on joue au shifting avec des entiers machine, de façon standard, dans tous les cours d'info de la planète, c'est: "liste finie indexée par des entiers naturels (de 0 à taille_entier_machine-1)".
    - L'opérateur shift_right est, sur ce type de structure, défini de façon parfaitement standard également, que ce soit mathématiquement, comme informatiquement. Aucun cours d'info ne stipule une quelconque modularité sur la variable de décalage. Je n'ai jamais rencontré non plus une structure de ce type dans mes longues années de pratique mathématique (elle modéliserait quoi d'ailleurs cette structure ?).
    D'où ma question "quel intérêt, celui qui implémente, dans un langage de haut niveau, un tel opérateur, a t-il de lui donner ce comportement qui ne respecte ni le modèle de données ni n'apporte un quelconque service arithmétique ?" Pire encore, "pourquoi rompre un standard et générer, au mieux des comportements indéfinis, au pire des bugs ou des incompréhensions comme les ont vécues mes étudiants et comme nous les échangeons tous les deux ?".
    
    Au sujet de ces deux questions, voilà ce que raconte Wikipedia:
    
    "For example, shift-left-word in PowerPC chooses the more-intuitive behavior where shifting by the bit width or above gives zero,[1] whereas SHL in x86 chooses to mask the shift amount to the lower bits to reduce the maximum execution time of the instructions, and as such a shift by the bit width doesn't change the value."
    
    On aurait donc enfin l'explication ! X86 a choisi ce comportement indépendamment de toute considération arithmétique uniquement pour des raisons techniques de performance. C'est à dire pour des considérations de bas niveau. Il n'y a là ni vision torique, ni cylindrique justifiée par des considérations d'arithmétique modulaire, non, c'est juste un pauvre masque sur les 6 derniers bits de la variable de décalage pour augmenter, au sein du CPU, la performance de l'opérateur shr au mépris de toute cohérence arithmétique.
    
    Cette cohérence est déléguée aux langages au-dessus. Mais voilà, certains ne font rien pour corriger cette absence de cohérence arithmétique (parfois ne la documentent même pas). Voilà plus simplement ce qui est arrivé à mes étudiants.
    
    PS
    Concernant la doc Ada, je la trouve parfaitement claire, à condition que l'utilisateur sache ce qu'est un shit en mathématique sur des suites finies indexées par des entiers. Tout est là.
    - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
      
      Posté par kantien le 19 mai 2017 à 18:07. Évalué à 2. Dernière modification le 19 mai 2017 à 18:10.
      Pour ce que doit faire le shift_right, on est d'accord : il décale à droite et remplace les trous par des zéros. Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ? C'est pour cela que j'avais écrit qu'elle ne faisait vraiment sens que sur cette intervalle. Dans quel contexte va ton réellement lui passer les valeurs 64, 65 ou tout autre supérieure ? Et cela ce n'est pas sans incidence pour un implémenteur de langage haut niveau. Comme tu l'as montré pour ADA : si on évite les valeurs supérieures à 63, on évite un test de comparaison à chaque exécution sur une architecture X86. Quelle intérêt un code pourrait avoir, sur une telle instruction, de se rendre dans un domaine où la sortie vaut toujours 0 ? Et je pense que la raison qui à présider au choix de laisser le comportement non défini en dehors de ces bornes sont des raisons de performances générales : la majorité des codes l'utilisant se retrouveraient pénalisés d'un test inutile sur X86. C'était là le fruit de mes « spéculations », comme celles de Def. Et c'est aussi ce que dit wikipédia :
      
      This helps allow C compilers to emit efficient code for various platforms by allowing direct use of the native shift instructions which have differing behavior.
      
      Ensuite sur ce que fait X86, je n'ai pas dit que c'était délibéré de leur part (bien que ma formulation pouvait laisser penser le contraire) mais je ne faisais que décrire, en me basant sur son comportement, la structure mathématique qui lui correspondait : un opérateur sur un tore, son domaine se ramenant de fait à Z/2^64Z x Z/64Z. Que peut-il servir à modéliser en pratique dans le quotidien d'un programmeur, j'en sais foutre rien et je m'en fout un peu à vrai dire. Mais c'est plus drôle qu'une fonction stationnaire, et c'est joli un donut ! :-P
      
      Quoi qu'il en soit, pour un langage haut niveau qui reproduit l'instruction machine, le développeur ne peut pas s'appuyer sur le comportement de shr sur X86 s'il veut un tel comportement, mais le coder lui-même s'il veut un code portable. Comme il doit le coder lui-même s'il veut que la sortie soit constamment égale à 0.
      
      let ( >> ) m n = match n with | n when n > 63 -> Int64.zero | _ -> Int64.shift_right m n 1L >> 64;; - : int64 = 0L 1L >> 65;; - : int64 = 0L
      
      Pour ce qui est de ton autre question pour OCaml sur PowerPC, je suppose que la réponse est : la sortie est stationnairement nulle à partir de 64. Ce qui est sans doute aussi le cas en C ou C++. Mais je n'ai pas de telle machine à disposition, ni de ARM, pour vérifier.
      
      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
      - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 19 mai 2017 à 20:10. Évalué à 2.
        
        Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ?
        
        Là tu veux dire que tu trouves rare ce genre de situation ?
        
        la majorité des codes l'utilisant se retrouveraient pénalisés d'un test inutile sur X86
        
        Et là tu veux dire que finalement tu trouves fréquente ce genre de situation ? J'avoue que suis un peu perdu dans ce que tu me dis.
        
        Mais c'est plus drôle qu'une fonction stationnaire, et c'est joli un donut !
        
        Tu diras ça à mes étudiants qui ont cherché pendant une semaine d'où pouvait venir le problème alors que leur algo était parfaitement cohérent arithmétiquement parlant :)
        
        Un langage de haut niveau peut régler ce problème en fournissant deux solutions: l'une avec un type contraint qui garantit la cohérence du code tout en permettant l'optimisation sur X86 et l'autre avec un shift_right prenant un amount quelconque qui respecte ce qu'est censé faire un shift_right arithmétiquement parlant.
        
        Haskel, Python, Ada, Eiffel le proposent. D'autres langages de haut niveau ne font rien de plus que le jeu d'instruction X86 et je trouve que c'est une faiblesse (générateur de bugs). De toute façon, laisser des comportements non définis sur une partie des plages des types fournis comme arguments d'une fonction c'est casse gueule (à tout le moins on lève une exception, là c'est totalement silencieux en plus).
        
        Et puis bon, c'est quand même étrange de fournir, à haut niveau, un opérateur qui fournit le même quotient par $2^{64}$ que par 1 dans un langage de haut niveau sous prétexte que certains processeurs ont ce comportement pour de simples raisons d'optimisation.
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par kantien le 20 mai 2017 à 15:26. Évalué à 1. Dernière modification le 20 mai 2017 à 15:29.
        
        Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ?
        
        Là tu veux dire que tu trouves rare ce genre de situation ?
        
        la majorité des codes l'utilisant se retrouveraient pénalisés d'un test inutile sur X86
        
        Et là tu veux dire que finalement tu trouves fréquente ce genre de situation ? J'avoue que suis un peu perdu dans ce que tu me dis.
        
        J'émettais bien l'hypothèse que les situation où on avait besoin de sortir de ces bornes étaient rares. En conséquence, la grande majorité de codes utilisant shift_right se retrouveraient pénalisés d'un test inutile sur X86 si les implémenteurs de langage haut niveau choisissaient tous ton approche, pour la simple est bonne raison qu'il ne sortiront jamais de ces bornes et que ce test dynamique s'avérait inutile pour eux. Certains langages, dont OCaml fait partie, semblent avoir fait le choix de ne garantir le bon comportement que sur l'intervalle O .. 63 pour des raisons tout à fait légitimes d'efficacité et de le documenter. Ainsi les cas exceptionnels qui ont besoin de sortir de ces bornes doivent coder leur propre fonction avec un test sur la valeur de l'entrée. C'est un choix qui me semblent tout à fait convenable d'un point de vue pragmatique. Tu dois bien reconnaître que ton projet est un cas bien particulier à but pédagogique que des programmeurs réaliseront peut dans la réalité. Rust va même jusqu'à refuser de compiler s'il détecte statiquement que l'on sort de ces bornes.
        
        Une approche peut être plus mixte est celle de Haskell, qui se comprend et se tient aussi : mais tout cela reste une question de choix. Je suis allé voir le code qui nous intéresse et l'on trouve :
        
        (W64# x#) `shift` (I# i#) | isTrue# (i# >=# 0#) = W64# (x# `shiftL#` i#) | otherwise = W64# (x# `shiftRL#` negateInt# i#) (W64# x#) `shiftL` (I# i#) = W64# (x# `shiftL#` i#) (W64# x#) `unsafeShiftL` (I# i#) = W64# (x# `uncheckedShiftL#` i#) (W64# x#) `shiftR` (I# i#) = W64# (x# `shiftRL#` i#) (W64# x#) `unsafeShiftR` (I# i#) = W64# (x# `uncheckedShiftRL#` i#)
        
        Puis pour shiftL et shiftRl :
        
        -- Wrappers for the shift operations. The uncheckedShift# family are -- undefined when the amount being shifted by is greater than the size -- in bits of Int#, so these wrappers perform a check and return -- either zero or -1 appropriately. -- -- Note that these wrappers still produce undefined results when the -- second argument (the shift amount) is negative. -- | Shift the argument left by the specified number of bits -- (which must be non-negative). shiftL# :: Word# -> Int# -> Word# a `shiftL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0## | otherwise = a `uncheckedShiftL#` b -- | Shift the argument right by the specified number of bits -- (which must be non-negative). -- The "RL" means "right, logical" (as opposed to RA for arithmetic) -- (although an arithmetic right shift wouldn't make sense for Word#) shiftRL# :: Word# -> Int# -> Word# a `shiftRL#` b | isTrue# (b >=# WORD_SIZE_IN_BITS#) = 0## | otherwise = a `uncheckedShiftRL#` b
        
        Ce qui revient peu ou prou à implémenter les fonctions << et >> comme je l'ai fait plus haut en OCaml à partir des versions fournies par la bibliothèque standard dans le module Int64. Les implémenteurs de la bibliothèque standard OCaml n'ont pas choisi cette approche, laissant le soin aux développeurs qui en ressentent le besoin de le faire eux même.
        
        Cela étant il reste la question de la circularité du second argument, qui ne pose pas de problème en ADA, mais qui en pose un en Haskell :
        
        >import Data.Word >import Data.Bits >(1 :: Word64) `shiftR` 64 0 >(1 :: Word64) `shiftR` (maxBound :: Int) 0 >(1 :: Word64) `shiftR` (maxBound :: Int) + 1 1
        
        Raison pour laquelle j'avais posé la question qui, elle aussi, n'était pas dénuée de fondements. ;-)
        
        Et puis bon, c'est quand même étrange de fournir, à haut niveau, un opérateur qui fournit le même quotient par 2^64 que par 1 dans un langage de haut niveau sous prétexte que certains processeurs ont ce comportement pour de simples raisons d'optimisation.
        
        J'espère t'avoir fait comprendre que, bien que le comportement puissent apparaître étrange lorsqu'on l'ignore, ce n'était pas un choix dénué de fondements ni sans justifications tout à fait recevables. Le seul reproche que l'on peut faire à freePascal est de ne pas le documenter mais non d'avoir un tel comportement.
        
        Sinon toujours en étant taquin, en poussant ton principe à l'extrême, je pourrais dire : un langage qui a besoin de tests unitaires n'est pas un langage haut niveau digne de ce nom. :-P
        
        De tels langages existent et comme je ne suis pas sectaire je te propose la méthode B présentée au Collège de France par son concepteur.
        
        Cette présentation est celle d’un chercheur vieillissant qui porte un regard historique sur les trente dernières années de son travail.
        
        Il y a deux sortes de chercheurs : les prolifiques et les monomaniaques. Je fais partie de la seconde catégorie, car j'ai toujours pratiqué le même genre d’investigations, à savoir la spécification et la construction vérifiée de systèmes informatisés.
        
        Ce travail, autant théorique que pratique, s’est concrétisé au cours de toutes ces années dans trois formalismes voisins : Z, B et Event-B (dont je ne suis pas, loin de là, le seul contributeur). Je vais tenter d’expliciter comment les idées que contiennent ces formalismes et les outils correspondants ont lentement émergés de façon parfois erratique.
        
        Je tenterai aussi de préciser les multiples influences qui ont participé à cette évolution. En particulier, je montrerai comment plusieurs réalisations industrielles ont permis de progresser dans ce domaine. Mais je soulignerai aussi les échecs et parfois les rejets de la part de communautés tant universitaires qu’industrielles.
        
        Pour finir, je proposerai quelques réflexions et approches pour le financement de recherches telles que celle-ci.
        
        Présentation dont j'extrais deux diapos :
        
        la RATP décide de supprimer les tests unitaires et d'intégration
        
        Octobre 98 : lancement de la ligne 14
        
        Depuis lors pas de problèmes avec le logiciel développé avec [soit 17 ans plus tard, et il tourne, tourne, tourne…]
        
        pour remplacer l'ancienne méthodologie avec tests unitaires par celle-ci :
        
        86.000 lignes en ADA ont été produites automatiquement
        
        27.800 preuves ont été faites
        
        92% ont été prouvés automatiquement par l'Atelier B
        
        Coût des preuves interactives : 7 hommes-mois
        
        Les preuves interactives sont moins chères que les tests
        
        Tu vois ADA lui aussi n'est pas assez « haut niveau » finalement. En fait Ada est à la méthode B ce que OCaml est à Coq : le langage dans lequel est écrit son noyau ainsi que le langage cible vers lequel il « compile ». Coq qui a servi, par exemple, à ecrire un compilateur C certifié correct. Ce sont là des exemples de ce que peut faire la rigueur de la formalisation mathématique pour garantir l'absence de bug dans un logiciel, à condition d'être effectuée avec les outils et les langages adéquats. ;-)
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 20 mai 2017 à 18:19. Évalué à 1.
        
        Ainsi les cas exceptionnels qui ont besoin de sortir de ces bornes doivent coder leur propre fonction avec un test sur la valeur de l'entrée.
        
        Non.
        Si OCaml disposait de la notion de sous types (contraints) alors il disposerait de deux fonctions shr. L'une utilisant ce type contraint garantirait l'efficacité optimale et l'autre (qui ferait le test) pour assurer la cohérence de l'arithmétique pour tout valeur naturelle de l'argument.
        Il n'y aurait donc la vérification à faire que lorsque cela est nécessaire pour le développeur. On y gagnerait sur tous les plans. C'est ce que j'expliquais dans un ancien post.
        
        D'autre part une signature de la fonction shr avec deux int en entrée et un int en sortie est étrange puisque le second paramètre devrait être un entier naturel (en tout cas sûrement pas un modulaire, qui n'a aucune signification arithmétique cohérente). Du coup on se retrouve avec une fonction qui a des comportements indéfinis en fonction de certaines valeurs des paramètres ce qui est source de bug (la preuve avec mes étudiants). Là tu peux avoir des résultats qui ne lèvent aucune exception au runtime ni aucun avertissement à la compilation.
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par kantien le 20 mai 2017 à 22:37. Évalué à 1.
        
        Afr, mon compilateur interne vient d'émettre un warning : risque de boucle sans fin, abort envisageable au prochain tour. ;-)
        
        C'est ce que j'expliquais dans un ancien post.
        
        Je le sais bien c'est le premier commentaire de ce sous-fil : on boucle !!! Qu'est-ce que tu n'as pas compris dans ma réponse ? Tu m'as pourtant répondu que j'avais était très clair, là c'est moi qui ne te comprends plus.
        
        Si OCaml disposait de la notion de sous types (contraints) alors il disposerait de deux fonctions shr.
        
        J'espère que tu me pardonneras la familiarité de l'expression mais j'ai envie de te répondre : « si ma tante en avait, on l'appellerait mon oncle ». J'avais pourtant précisé dans ma réponse que les systèmes de typage était une question distincte, bien qu'elle puisse être utilisée dans le cas de Ada pour traiter le problème. Mais jusqu'à preuve du contraire, un langage doit faire avec le système de type dont il dispose. À ma connaissance il n'y a aucun plan pour intégrer cette sorte de type dans le langage, ce que je peux comprendre pour des raisons théoriques liées aux fondements du langage qu'ils seraient trop longs de développer (il y a néanmoins des sous-types contraints en OCaml, mais pas de la sorte des types range comme en Ada).
        
        Connais tu la théorie des types ? J'avais pourtant donner un lien vers un dossier de la gazette des mathématiciens sur le sujet, l'as-tu lu ? Outre son utilité pour le typage statique des langages fonctionnelles, le système F (qui est le fondement des système de type de Haskell et OCaml) a été inventé au début des années 70 par le mathématicien et logicien français Jean-Yves Girard pour des questions liées aux fondements des mathématiques. Je cite ici sa nécrologie à la page 14 :
        
        En 1953, Takeuti remarquait que la logique du second ordre permettait de formuler sans axiomes toutes les mathématiques courantes, et il proposait un procédé effectif d’élimination des coupures pour étendre le théorème de Gentzen : c’est la conjecture de Takeuti. En 1965, Tait démontrait l’existence de démonstrations sans coupure pour le calcul des séquents de Takeuti, mais l’essentiel manquait, à savoir la convergence du procédé d’élimination proposé par Takeuti. C’est ce que j’ai démontré en 1970, dans l’article [1], résultat amélioré dans [2] et [3]. En fait, ce résultat se présentait comme un système de calcul fonctionnel typé, (le système F), dans lequel on pouvait définir un type nat des entiers (i.e. dont les objets sont les entiers), avec deux théorèmes principaux :
        
        Théorème 1
        Le procédé de calcul dans F converge (normalisation).
        
        Théorème 2
        Tout algorithme fonctionnel (envoyant les entiers dans les entiers) dont on peut établir la terminaison au moyen des mathématiques courantes, se représente dans F au moyen d’un objet de type nat ⇒ nat.
        
        Le système F est par exemple utilisé par Haskell comme représentation intermédiaire pour son compilateur. Ce système a connu depuis différentes extensions, ou il y a eu d'autres système du même genre comme la théorie des types de Per Martin-Löf, le Calcul des Constructions (CoC) à la base de Coq qui devint le Calcul des Constructions Inductives, puis on a tout récemment la théorie homotopique des types. Ces théories tournent toutes autour d'une problématique : la recherche d'un système de formalisation unifié de l'ensemble de l'édifice mathématique, ainsi que la réponse à la question : « les mathématiques sont-elles cohérentes ? ». Parce que l'on parle d'arithmétique depuis le début, mais l'arithmétique est-elle une théorie cohérente ?
        
        Pour revenir sur la question initiale du journal : le décalage bit à bit vers la droite. Dans un autre commentaire, tu as écris :
        
        Haskel, Python, Ada, Eiffel le proposent. D'autres langages de haut niveau ne font rien de plus que le jeu d'instruction X86 et je trouve que c'est une faiblesse (générateur de bugs).
        
        Premièrement ce que fait Haskell, la bibliothèque standard OCaml aurait pu tout aussi bien le faire : je l'ai expliqué précédemment; cela n'a pas été l'option retenue (j'ignore, néanmoins, les raisons qui ont déterminé un tel choix). Ce n'est pas lié au possibilité du langage mais à un choix d'implémentation pour la bibliothèque standard fournie avec le compilateur. Mais ce n'est pas la seule existante, elle a des concurrentes certains développeurs ne la jugeant pas assez fournie.
        
        Deuxièmement mettre Python dans la liste sur des questions de sécurités de code : c'est une blague ou tu es sérieux ?
        
        Troisièmement, vu que tu viens de rajouter une exigence à ton cahier des charges : ne pas avoir de types cycliques pour le paramètre déterminant le degré du décalage, tu viens de les perdre tous sauf Ada. La liste des langages qui trouve grâce à tes yeux s'amenuise de plus en plus au fur et à mesure que progresse la discussion. ;-)
        
        Pour le cas de Haskell, je l'ai déjà illustré. Pour celui de Eiffel, si je lis la documentation
        
        infix "|>>" (s: INTEGER_8): INTEGER_64 Shift by s positions right (sign bit copied) bits falling off the end are lost. bit_shift_right (s: INTEGER_8): INTEGER_64 Shift by s positions right (sign bit copied) bits falling off the end are lost.
        
        Déjà le paramètre est sur 8 bit, donc ton exercice n'est pas réalisable en Eiffel avec cette version de shift_right. Et si je lis la documentation sur les INTEGER_8, dans le résumé je vois : 8 bits signed integer. J'ai comme le pressentiment qu'il est cyclique lui aussi : si un développeur Eiffel pouvait confirmer mon intuition ?
        
        Et pour le langage de départ du projet de tes élèves, FreePascal, outre le comportement du shr inattendu, il me semble bien d'après cette documentation que le type en question est lui aussi cyclique :
        
        function isBitSet(AValue, ABitNumber:integer):boolean; begin result:=odd(AValue shr ABitNumber); end;
        
        Ai-je raison de supposer que le type integer est cyclique en Pascal ?
        
        Comme de tout le fil de discussion et de tous les commentaires je suis le seul à avoir pointé du doigt l'importance de la nature du type de ce paramètre, je suis au regret de devoir émettre une nouvelle hypothèse qui me chagrine en espérant me tromper. Le « bug » n'était pas anticipé et a été découvert par hasard, et malgré son apparente solution tu en es au même point d'incompréhension que tes élèves : la source fondamentale du problème c'est la différence de géométrie entre un tore et un cylindre. ;-)
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
      - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 20 mai 2017 à 08:29. Évalué à 1.
        
        Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ?
        
        A cette question je pourrais répondre bêtement en disant que je veux que la fonction suivante calcule le quotient de n par pour toutes les valeurs de la plage des types de ses arguments.
        
        function quo_power2 (n, a: natural) return natural;
        
        Mais je vais préfère t'expliquer dans quel contexte moins artificiel on peut avoir besoin d'un décalage supérieur ou égal à 64 en te décrivant une petite partie du projet de mes étudiants.
        
        Description partielle du projet
        
        Celui-ci consiste à coder les opérations et $\times$ sur le type "double" en n'utilisant que des opérations sur les entiers unsigned sur 64 bits (les qword en Pascal). Autrement dit jouer avec la norme IEEE754 qui décrit la représentation des flottants en machine ainsi que les opérations standard sur ces flottants. Cela permet vraiment de comprendre en profondeur qu'une machine ne sait vraiment pas manipuler correctement les réels (contrairement à ce qu'ils croient tous).
        
        Description de la représentation machine des « double »
        
        Grosso modo, cette norme stipule qu'un double est un espace mémoire sur 64 bits organisé, de gauche à droite, de la façon suivante: 1 bit de signe (s) , 11 bits d'exposant (e) et 52 bits de mantisse (k). Le réel correspondant à cet espace mémoire est alors $\left(-1\right)^{s}2^{e-1023}\left(1+k2^{-52}\right)$ . Donc déjà, une remarque, il faut un langage permettant de lire un même espace mémoire avec deux typages différents (double et qword) donc, adieu Python.
        
        Addition machine des « double »
        
        Je ne vais pas traiter tous les cas mais celui qui a fait apparaître le fameux problème dont on discute : l'addition de x et y (x>y>0). Je note k et k' les mantisses entières respectives de x et y, e et e' leurs exposants.
        
        Un petit calcul montre que l'exposant de la somme est le max des deux exposants (éventuellement + 1) . Pour le calcul de la mantisse on a nécessairement, à un moment donné, $k+2^{e'-e}k'$ . Vu que e'-e<0, cela revient à diviser k' par une puissance de deux comprise entre 0 et 2046. Donc à faire un shr sur k' d'un amount compris entre 0 et 2046.
        
        Sauf que voilà, pour une raison d'optimisation qui leur était totalement inconnue, le comportement arithmétique de cette opération redevient identique modulo 64 et patatra !
        
        Quand j'ai préparé le projet chez moi, en Ada, je n'ai vu aucun problème car Ada ne reproduit pas les optimisations de bas niveau en cassant l'arithmétique. Le compilateur FreePascal lui, reproduit ce comportement arithmétique incohérent et sa doc ne dit rien à ce sujet.
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par shbrol le 20 mai 2017 à 09:32. Évalué à 3.
        
        Quand j'ai préparé le projet chez moi, en Ada, je n'ai vu aucun problème car Ada ne reproduit pas les optimisations de bas niveau en cassant l'arithmétique. Le compilateur FreePascal lui, reproduit ce comportement arithmétique incohérent et sa doc ne dit rien à ce sujet.
        
        Quel est l'intéret d'utiliser FreePascal, si le projet a été pensé et préparé en Ada ? Pourquoi ne pas utiliser Ada ?
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 20 mai 2017 à 12:00. Évalué à 2.
        
        Le choix de l'école a été de former les étudiants dans leurs deux premières années d'info sur FreePascal. Dans un post plus haut ce choix a été expliqué.
        
        Je milite à titre personnel (mais je ne fais pas partie de l'équipe d'info) pour qu'on passe, comme à l'INSA Toulouse, à Ada. Le problème c'est que ça demande beaucoup de temps (entre autres pour refaire tous les supports de cours et former les collègues qui ne connaissent pas ce langage). Je le redis au passage: ils apprennent également Python et C au cours de leur projet math et de leur projet info. Ceux qui iront dans le département info toucheront à tout.
        
        FreePascal permet de répondre malgré tout aux besoins (et même plus) qu'ont les étudiants (grands débutants en première année). Le projet que j'ai donné est destiné à des élèves en fin de premier cycle dans le cadre d'une introduction à l'analyse numérique et à la sensibilisation au problème épineux de la représentation des nombres en machine source de nombreuses erreurs de conception dans des algorithmes de calculs (phénomène de cancellation, d'absorption, gestion de l'erreur relative et de l'erreur absolue etc).
        
        Le projet n'a pas été pensé et préparé en Ada. Il a été pensé de façon théorique puis implémenté initialement en Pascal chez moi. Mon implémentation tournait parfaitement mais je n'étais pas allé faire des tests unitaires aussi poussés qu'eux tout persuadé que mon algo était bon (et il l'était !). Fallait quand même imaginer qu'un décalage de 64 entre deux exposants de deux flottants qu'on veut additionner allait provoquer cette erreur sournoise et non documentée par FreePascal.
        
        Ensuite j'ai voulu faire la même chose proprement en Ada chez moi pour le fun.
        
        Et là, je reçois un mail d'un binôme qui a le bon algo, exactement la bonne démarche, la bonne implémentation a priori, qui me dit "on a une incohérence dans des tests unitaires". Après leur propre investigation (pendant une semaine) et un ou deux échanges avec eux on isole le problème et on voit que shr a un comportement (non documenté par la doc de fpc) complètement incohérent sur le plan arithmétique. Puis je me suis aperçu avec un ami (l'auteur du journal) que de nombreux langages soit disant de haut niveau souffraient de cette incohérence qui consiste à reproduire "bêtement" ce que fait le shr des X86 pour des raisons d'optimisation à bas niveau.
        
        Une fois le bug identifié, un simple "if" a permis de régler le problème et tout revenait dans l'ordre.
        
        Voilà l'histoire :)
        
        En tout cas, j'ai trouvé ça super intéressant de suivre les remarques de chacun, ça montre un aperçu de la façon d'aborder l'arithmétique des entiers dans plein de langages et c'est chouette !
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par kantien le 24 mai 2017 à 21:43. Évalué à 2.
        
        Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ?
        
        A cette question je pourrais répondre bêtement en disant que je veux que la fonction suivante calcule le quotient de n par 2^a pour toutes les valeurs de la plage des types de ses arguments.
        
        function quo_power2 (n, a: natural) return natural;
        
        Ça m'intriguait cette histoire, et je n'arrivais pas à admettre qu'un informaticien comme Xavier Leroy ait pu faire un tel choix sans une bonne raison. Pour faire de l'arithmétique entière, il y a une bibliothèque dédiée (écrite en collaboration) : Zarith qui ne fait pas partie de la distribution officielle ni de la bibliothèque standard (elle est volontairement minimaliste).
        
        #require "zarith";; #install_printer Z.pp_print;; Z.shift_right Z.one 64;; - : Z.t = 0 Z.(shift_right (shift_left one 65) 1);; - : Z.t = 18446744073709551616 Z.(shift_right (shift_left one 64) 128);; - : Z.t = 0 Z.(shift_right (shift_left one 65) (-1));; Exception: Invalid_argument "Z.shift_right: count argument must be positive".
        
        Son objectif est de faire de l'arithmétique sur Z de manière efficace, et la doc de la fonction shift_right précise qu'elle a bien le comportement souhaité :
        
        external shift_right: t -> int -> t = shift_right@ASM (** Shifts to the right. This is an arithmetic shift, equivalent to a division by a power of 2 with rounding towards -oo. The second argument must be non-negative. *)
        
        Le module Int64 (et son compagnon Int32) ne doivent pas spécialement être fait pour cela :
        
        This module provides operations on the type int64 of signed 64-bit integers. Unlike the built-in int type, the type int64 is guaranteed to be exactly 64-bit wide on all platforms. All arithmetic operations over int64 are taken modulo 264 Performance notice: values of type int64 occupy more memory space than values of type int, and arithmetic operations on int64 are generally slower than those on int. Use int64 only when the application requires exact 64-bit arithmetic.
        
        Ici comme la précision est fixe et que la performance n'est pas déjà au top, on laisse l'appelant se charger des vérifications s'il pense que cela est nécessaire, l'appelé ne fournissant que la garantie du bon résultat dans les bornes 0 .. 63 (du moins je suppute que c'est ce genre de considération qui a du influencer le choix de cette implémentation).
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 25 mai 2017 à 15:20. Évalué à 1.
        
        De l'arithmétique sur $\mathbb{Z}$ ? Vraiment ? Ca me paraît impossible.
        
        Ada fait de l'arithmétique exacte dans $\mathbb{Z}/N\mathbb{Z}$ avec N naturel compris entre 1 et $2^{64}$ . C'est déjà pas mal du tout (avec une arithmétique optimisée au plus bas niveau pour N=8, 16, 32 ou 64. Il y a la notion de type modulaire pour cela.
        
        Pour faire de l'arithmétique sur un minuscule sous ensemble de $\mathbb{Z}$ (j'imagine que c'est ce dont tu parles) il y a le type (et des sous types) de Integer. Les opérations arithmétiques peuvent générer des exceptions si les résultats ne sont pas représentables (sortent des plages de représentation). Dans tous les cas, aucun résultat n'est donné s'il est incohérent avec l'arithmétique (ce qui n'est pas le cas de OCaml, C, C++, Pascal etc qui laissent des comportements indéfinis, sources de résultats inattendus pour celui qui n'a pas lu les moindres détails de la doc, et ils sont nombreux ceux là). Ceci est fait au prétexte de l'optimisation sur certains processeurs. Or ce prétexte s'explique par le fait que ces langages ne disposent pas de la notion de sous type contraint.
        
        En Ada, il y a deux options laissées au développeur:
        
        être certain que les opérations ne provoquent aucun overflow et demander au compilo, par une pragma clairement écrite dans le code source, de ne pas les gérer pour optimiser les calculs.
        
        laisser le compilo vérifier les "constraint errors" ce qui ralentit l'exécution mais permet de s'apercevoir, pendant la conception, d'éventuelles erreurs de programmation.
        
        Les choses sont ainsi parfaitement claires, toujours optimisées bas niveau (si besoin), aucun appel ne provoque de résultat indéfini silencieusement. A mon âge, quand je vois un langage qui ne propose pas ça, j'ai du mal à le considérer de "haut niveau" (même s'il possède d'autres qualités très intéressantes par ailleurs).
        
        C'est extrêmement formateur. Combien d'étudiants déclarent un integer pour manipuler des entiers sans se soucier de la cohérence arithmétique des résultats ? Chaque année, en C ou Pascal, avec les collègues, on en voit passer des boucles infinies par méconnaissance de la modularité du type integer dans ces langages de "haut niveau".
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 25 mai 2017 à 16:57. Évalué à 1.
        
        Je complète mon post précédent pour préciser que même GMP ne permet pas à la machine de faire d'arithmétique sur $\mathbb{Z}$ (comme aucune machine qui, pour stocker un entier, stocke ses chiffres). Cela augmente significativement les possibilités mais c'est tout.
        Je m'intéressais aux capacités natives des langages (sinon j'avais déjà évoqué gmp dans un post précédent).
    - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
      
      Posté par kantien le 19 mai 2017 à 18:46. Évalué à 2.
      
      J'ai d'ailleurs une autre question : en ADA le type natural est-il lui aussi cyclique ou, sinon, que se passe-t-il lorsque l'on arrive aux bornes ? Dans plein de langage, dont OCaml, le type du second paramètre est lui aussi cyclique (le type int c'est Z/2^63Z en 64 bits) ce qui ne ferait que repousser le comportement observé de manière tout aussi étrange lui aussi.
      
      Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
      - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par Blackknight (site web personnel, Mastodon) le 20 mai 2017 à 00:21. Évalué à 3.
        
        en ADA le type natural est-il lui aussi cyclique ou, sinon, que se passe-t-il lorsque l'on arrive aux bornes ?
        
        En Ada, il n'y a que les types définis comme modulaires qui le sont. Natural n'en fait pas partie.
        
        subtype Natural is Integer range 0 .. Integer'Last;
        
        Il s'agit d'un sous-type du type entier et comme lui, un dépassement de capacité provoque une exception.
        Le programme suivant est accepté par le compilateur moyennant un avertissement.
        
        with Ada.Text_Io; use Ada.Text_Io; procedure Nat is Nat : Natural := Natural'Last; begin Put_Line("Nat=" & Natural'Image(Nat)); Nat := Nat + 1; Put_Line("Nat=" & Natural'Image(Nat)); end Nat;
        
        gnatmake nat.adb gcc-4.9 -c nat.adb nat.adb:7:15: warning: value not in range of type "Standard.Integer" nat.adb:7:15: warning: "Constraint_Error" will be raised at run time gnatbind -x nat.ali gnatlink nat.ali
        
        A l'exécution, il arrive ce que le compilateur avait dit
        
        ./nat Nat= 2147483647 raised CONSTRAINT_ERROR : nat.adb:7 overflow check failed
        
        Voilà, le principe du moindre étonnement dans toute sa splendeur :)
        
        [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 20 mai 2017 à 08:49. Évalué à 1.
        
        J'aime beaucoup le principe du moindre étonnement :)
      - [^] # Re: Du haut niveau pour gérer correctement du bas niveau
        
        Posté par snowball (site web personnel) le 20 mai 2017 à 00:42. Évalué à 2.
        
        Côté statique
        
        with ada.text_io;use ada.text_io; procedure test_int_ada is begin put_line (natural'image(natural'last+1)); -- demander l'affiche du dernier naturel + 1 end test_int_ada;
        
        renvoie à la compilation:
        test_int_ada.adb:4:39: value not in range of type "Standard.Integer"
        test_int_ada.adb:4:39: static expression fails Constraint_Check
        
        Côté dynamique:
        
        with ada.text_io;use ada.text_io; procedure test_int_ada is i : natural := natural'last-1; begin for j in 1..2 loop i := i +1; end loop; put_line (i'img); end test_int_ada;
        
        Renvoie:
        raised CONSTRAINT_ERROR : test_int_ada.adb:6 overflow check failed
        
        Donc non le type natural n'est pas du tout cyclique. Mais…
        
        Ada gère les types modulaires
        
        Par exemple, si tu écris :
        
        type my_mod_7 is mod 7; -- ce type représente les éléments de Z/7Z [...] put_line (my_mod_7'img (my_mod_7'mod(8))); -- on affiche le représentant de la classe de 8
        
        alors ça t'affiche 1.
        
        Ada fait dont exactement ce qu'on lui demande dans la mesure du réalisable avec les types primitifs gérables par la machine.
        Si on veut un comportement modulaire, on définit comme ci-dessus le type, et on dispose de toute l'arithmétique (cohérente) sur ce type dans les limites offertes par la machine.
        Maintenant, si on veut dépasser les limites du jeu d'instruction du processeur et qu'on veut faire de l'arithmétique multi-précision ils existe bien évidemment un binding Ada pour gmp.
        
        Comparaison avec C++
        
        #include <iostream> int main() {unsigned char u=254; while (u<=255) u+=2; std::cout<<u; return 0; }
        
        Aucun warning, aucune erreur de compilation, aucune exception à l'exécution, et le programme boucle à l'infini car 'unsigned char' est vu comme un type modulaire (modulo ) ce qui ne s'appuie sur aucun fait explicable (à part le fait de vouloir représenter la table ASCCI comme un cercle). Plus intéressant, il est impossible d'arriver à un tel comportement avec Ada.

# En Eiffel

Posté par Philip Marlowe le 18 mai 2017 à 16:04. Évalué à 4.
```
    make
            -- Run application.
        local
            a, b: INTEGER_64
        do
            a := 1
            b := a.bit_shift_right (64)
            print (b.out)
        end
```
Retourne 0. Aucun commentaire ou warning à la compilation.
- [^] # Re: En Eiffel
  
  Posté par snowball (site web personnel) le 18 mai 2017 à 17:19. Évalué à 2.
  
  On peut donc rajouter Eiffel à la (courte) liste des langages compilés qui donnent un résultat arithmétiquement cohérent :)
  Merci pour l'info.
  - [^] # Re: En Eiffel
    
    Posté par reno le 19 mai 2017 à 10:30. Évalué à 4.
    
    Le contraire aurait été surprenant Eiffel étant un language de "haut niveau".
# Un utilisateur OCaml sous PowerPC

Posté par snowball (site web personnel) le 19 mai 2017 à 16:44. Évalué à 1.

Du coup, je me permets de reposer la question du journal autrement :
Sur powerpc, ça donne quoi ?
- [^] # Re: Un utilisateur OCaml sous PowerPC
  
  Posté par Blackknight (site web personnel, Mastodon) le 20 mai 2017 à 16:37. Évalué à 3.
  Alors je peux pas te dire pour PowerPC mais pour ARM, ça, je peux.
  
  Le programme suivant compilé pour une carte NUCLEO-F411RE équipée d'un microprocesseur STM32 à partir du site de développement MBED
```
#include "mbed.h"

Serial pc(USBTX, USBRX);

// main() runs in its own thread in the OS
int main() {
    int a = 1;
    pc.printf("%d\n", a >> 64);
}
```
  retourne… 0 mais envoie un avertissement
  Warning: Shift count is too large in "main.cpp", Line: 8, Col: 29Donc pour ARM, pas de "problème" :)
- [^] # Re: Un utilisateur OCaml sous PowerPC
  
  Posté par benoar le 30 mai 2017 à 22:51. Évalué à 3.
  
  [Hors Sujet, un peu]
  
  Sur PowerPC les différentes variantes du shift (comme le rotate, si on peut vraiment le considérer comme tel) sont synthétisées par une seule instruction « rlwirm » — dans la grande tradition du RISC — qui est juste paramétrée différemment. Cf. le Programming Environments Manual, dont le tableau F.4.2 trouvable ici http://www.csit-sun.pub.ro/~cpop/Documentatie_SMP/Motorola_PowerPC/PowerPc/GenInfo/pemappF.pdf résume bien la génialité de la chose : on pourrait presque imaginer, en regardant par exemple les tableaux détaillant le codage consécutif des instructions ici http://www.nxp.com/assets/documents/data/en/reference-manuals/MPCFPE32B.pdf, le câblage du CPU devant ses yeux (juste un bit change pour un paramètre différent qu'on retrouve dans plein d'instructions similaires, de manière à minimiser le coût en transistors).
  
  Malheureusement, ça n'est pas exploitable directement en C, et le compilateur doit en déduire des manipulations d'entier si l'instruction unique est émissible.
  
  Bon, ça c'était l'instruction avec une valeur de shift immédiate, mais il existe aussi les version indexées par un registre.
  
  Et pour revenir au journal, arithmétique modulo ou pas, rotate ou shift, tout est géré par cette instruction magique comme vous le souhaitez : il n'y a pas un choix plus « logique » que l'autre.
  - [^] # Re: Un utilisateur OCaml sous PowerPC
    
    Posté par snowball (site web personnel) le 31 mai 2017 à 22:34. Évalué à 2.
    Merci pour tes précisions mais je n'ai pas compris ce que fait un shift right de 64 sur un PowerPC (par exemple avec du C compilé par gcc).
    - À bas niveau il y n'y a que la logique des transistors. Là on est d'accord.
    - À plus haut niveau, on a une couche d'abstraction qui fait qu'un "computer" est là pour "calculer" en respectant des règles arithmétiques communes à tout le monde.
    La discussion (sans fin), c'est que certains langages dits de "haut niveau" ne fournissent pas cette couche d'abstraction et ce, essentiellement parce que:
    1. ils ne disposent pas de la notion de sous-type contraint (donc des fonctions prennent des arguments qui peuvent aboutir silencieusement, à des comportements non définis)
    2. ils prétendent que ça "optimise" (alors que ça pourrait l'être tout autant avec la notion de sous-type contraint comme je l'ai montré plus haut).
    
    Tu pourrais nous donner le résultat d'un shift right sur un espace mémoire de 64 bits initialisé à 1 en C avec gcc sur powerpc (si tu as ça sous la main bien évidemment) ?
# Crystal

Posté par cluxter le 10 juin 2017 à 02:10. Évalué à 3. Dernière modification le 10 juin 2017 à 02:11.

Pour information, j'ai testé en Crystal avec le programme suivant et ça renvoie 0 :
puts 1 >> 64
Oui, pas très long comme programme. C'est du Crystal ;)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.

Le problème

En C/C++

En Java

En Ada

En OCAML

En Python

Que disent les docs ?

Description partielle du projet

Description de la représentation machine des « double »

Addition machine des « double »

Côté statique

Côté dynamique:

Ada gère les types modulaires

Comparaison avec C++