Journal [Letlang] Hommage à Leonardo Pisano Fibonacci

Posté par David Delassus (site web personnel) le 23 mai 2022 à 12:40. Licence CC By‑SA.

Étiquettes :

mai

2022

Bonjour Nal,

Aujourd'hui, je vais te parler de la suite de Fibonacci en Letlang.

Pour la table des matières, comme d'habitude:

Prélude

Pour ceux qui ne sont pas au courant, le programme Letlang Hello World compile :

module "hello.main";

pub func main() -> @ok {
  perform debug("hello world");
  @ok;
}

Cela utilise un side effect (effet de bord pour les francophones) intégré au runtime qui ne fait pas de type checking, il disparaîtra sûrement à l'avenir pour laisser sa place à une meilleure interface, mais pour l'instant cela fait le taf :)

Ce programme prouve notamment que l'implémentation des effets de bords en utilisant genawaiter (implémentation des coroutines en Rust) fonctionne à merveille.

Le compilateur (désormais open source) est composé de 3 parties :

le parseur, écrit en Rust avec LALRPOP et Logos, j'en ai parlé dans les articles précédents de cette série
le générateur de code, écrit pour le moment en Python (histoire d'aller vite), s'occupe de générer le code Rust à partir de l'AST produit par le parseur
le runtime, écrit en Rust, est ajouté en tant que dépendance au code Rust généré par le compilateur

Chaque module Letlang va générer une crate Rust, et l'ensemble des crates est ajouté à un workspace Cargo, permettant ainsi de compiler le tout assez facilement. C'est pas forcément définitif comme manière de faire, mais pour l'instant, ça marche niquel.

Mais qu'est-ce donc que Fibonacci ?

La suite de Fibonacci est définie par :

fib(0) = 1
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

C'est l'exemple parfait pour faire du pattern matching et de la récursion. C'est aussi le projet d'exemple parfait pour continuer dans la lancée du Hello World.

Le code

Sans plus attendre :

module "fib.main";

func fib(n: int) -> int {
  match n {
    0 => 1,
    1 => 1,
    int => fib(n - 1) + fib(n - 2),
  };
}

pub func main() -> @ok {
  perform debug(fib(5));
  @ok;
}

Comme précédemment, on utilise le side effect debug(...) -> @ok pour afficher le résultat.

Le plus intéressant ici, c'est l'expression match. Elle prend en paramètre une expression (ici n), et dans son corps, un ensemble de clause.

Chaque "pattern" est un type. On a ainsi en rust:

let patternval = /* ... */;
let clause_0_type = /* ... */;
let clause_1_type = /* ... */;
let clause_2_type = /* ... */;

if clause_0_type.has(context.clone(), &patternval) {
  // ...
}
else if clause_1_type.has(context.clone(), &patternval) {
  // ...
}
else if clause_2_type.has(context.clone(), &patternval) {
  // ...
}
else {
  // throw exception
}

Le code est plutôt simple, débile même je dirais. Dans le futur il sera bien évidemment possible de "binder" des variables dans le pattern, ce qui changera cette implémentation, mais pour le moment, cela fonctionne et me permet d'avancer :)

Pour ce qui est de la récursion, pas d'unroll, pas de TCO (tail call optimization) pour le moment, donc fib(-5) générera un joli stack overflow.

La suite des événements

Le procédé est simple, on prend un exemple de programme, et on fait en sorte qu'il compile. C'est pourquoi j'ai commencé par hello-world et que j'ai enchaîné avec fibonacci. Avec suffisamment d'exemple, on couvrira l'ensemble des fonctionnalités du langage, le rendant petit à petit plus utile!

Ainsi, le prochain projet exemple sera l'automate cellulaire à la règle 110, qui démontrera la "Turing Completeness" de Letlang.

Tout est sur le dépôt Github.

Les choses avancent lentement mais sûrement, cette nouvelle étape accomplie m'emplie de joie et d'espoir pour l'avenir de ce langage.

Voilà Nal, c'est tout pour cette petite annonce, j'espère t'avoir transmis un peu de mon enthousiasme :)

# Définition décalée... f(0) = 0

Posté par Francky (site web personnel) le 23 mai 2022 à 20:56. Évalué à 7.

La bonne définition de la suite de Fibonacci est avec f(0) = 0, f(1) = 1 et f(n) = f(n-1) + f(n-2) pour n≥2

Il y a une raison pour laquelle nombre d'informaticiens commencent à 1 plutôt que zéro. Une sombre histoire de nombre d'appels (récursifs) pour déterminer f(n) avec une méthode naïve.

Mais il y a de nombreuses raisons mathématiques à préférer le décalage avec f(0) = 0, en particulier que f(p) est un nombre premier implique p = 4, ou bien p est premier.

Et oui, il y a beaucoup d'enthousiasme autour de cette suite, ses propriétés, ses défis algorithmiques et ses prolongements…

Merci pour le 'nal.
# Type des paramètres

Posté par barmic 🦦 le 24 mai 2022 à 06:55. Évalué à 7.
Merci pour le journal.

Je trouve élégant d'avoir un dispatch sur les valeurs de paramètres. Vu ta description de letlang j'aurais pensé que tu serais parti dessus. Il est bien possible (à terme peut-être pas aujourd'hui) d'écrire :
```
fibo(x: 0) -> 0 {
    0
}
fibo(x: 1) -> 1 {
    1
}
fibo(x: int > 1) -> int {
    fib(n - 1) + fib(n - 2)
}
```
Ou je me trompe ?

https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
- [^] # Re: Type des paramètres
  
  Posté par David Delassus (site web personnel) le 24 mai 2022 à 10:10. Évalué à 3.
  
  Idéalement oui, j'aimerais bien arriver à une syntaxe de ce type. Étape par étape :)
  
  https://link-society.com - https://kubirds.com - https://github.com/link-society/flowg
  - [^] # Re: Type des paramètres
    
    Posté par barmic 🦦 le 24 mai 2022 à 14:26. Évalué à 3.
    
    Bien sûr, c'était juste pour vérifier si j'avais bien compris.
    
    https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
# Complexité algorithmique

Posté par Liorel le 24 mai 2022 à 08:01. Évalué à 3.
Un point m'embête dans ton implémentation de la suite : chaque appel de la fonction appelle 2 instances supplémentaires, qui se résolvent récursivement, donc qui restent en attente jusqu'à ce que toutes les instances aient atteint 0 ou 1. Alors ça marche sans trop de problèmes pour fib(5) ou fib(7), mais essaie de calculer fib(24) et tu vas beaucoup moins rigoler. En effet, cette implémentation appelle de l'ordre de 2^n instances de la fonction. Le problème étant que quand tu écris :
```
int => fib(n - 1) + fib(n - 2),
```
tu ne gardes pas en réutilises pas le résultat de fib(n-2) pour calculer fib(n-1) : tu appelles une nouvelle instance toute neuve. Une solution est d'avoir un objet de type tuple, indiçable et de faire retourner un tuple à ta fonction :
```
0 => (0,0),
1 => (0,1),
intermediate_value = fib(n-1)
int => (intermediate_value[2], intermediate_value[2] + intermediate_value[1])
```
Ainsi, tu n'appelles ta fonction qu'une seule fois par instance, et ton temps de calcul progresse désormais en O(n) et non en O(2^n).

Ça, ce sont les sources. Le mouton que tu veux est dedans.
- [^] # Re: Complexité algorithmique
  
  Posté par David Delassus (site web personnel) le 24 mai 2022 à 10:09. Évalué à 2.
  
  Faut vraiment être condescendant pour croire que je ne connais pas la technique de mémoïsation de ce genre d'algorithme.
  
  C'est le genre de truc que tu vois à ton premier cours de programmation dynamique.
  
  Ici l'intérêt, c'est pas la suite de fibonacci en elle même, mais bien le fait que je puisse la compiler et l'exécuter en Letlang.
  
  Une implémentation future avec mémoïsation sera bien évidemment possible. Mais pour l'instant, on fait étape par étape.
  
  https://link-society.com - https://kubirds.com - https://github.com/link-society/flowg
  - [^] # Re: Complexité algorithmique
    
    Posté par chimrod (site web personnel) le 24 mai 2022 à 14:20. Évalué à 8.
    
    Je ne vois rien de condescendant dans le message auquel tu réponds. Je pense que tu fais un présupposé là il faut seulement y voir une remarque venant de quelqu’un qui a pris le temps d’écrire son commentaire, illustré par des exemples.
    
    Toutefois, et sans vouloir paraître condescendant, je veux bien que tu m’expliques comment tu compte implémenter la récursion terminale dans le langage.
    - [^] # Re: Complexité algorithmique
      
      Posté par barmic 🦦 le 24 mai 2022 à 14:25. Évalué à 10.
      
      Je ne vois rien de condescendant dans le message auquel tu réponds. Je pense que tu fais un présupposé là il faut seulement y voir une remarque venant de quelqu’un qui a pris le temps d’écrire son commentaire, illustré par des exemples.
      
      Il a pris le temps d'étaler sa culture. Il n'a pas sincèrement pris le temps de comprendre le journal. Quand quelqu'un arrive pour dire « regarder j'arrive à compiler ce petit bout de code avec mon langage qui a 3 mois », répondre « ton code me gène parce qu'il n'est pas optimal regarde comme mon code est mieux ». Je comprends tout à fait que ça gène surtout quand l'auteur s'est déjà plusieurs fois pris des procès en incompétence ici-même.
      
      https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll
      - [^] # Re: Complexité algorithmique
        
        Posté par chimrod (site web personnel) le 25 mai 2022 à 19:19. Évalué à 2.
        
        Merci, je n’avais pas eu cette lecture. Avec ton retour je vois mieux ce qui s’est joué.

Suivre le flux des commentaires

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