OCaml write-only
2/03/2008 10:23:00 PM
J'ai découvert un petit site sympa suite à une annonce sur la Caml-list: Anarchy Golf. Au golf, on fini un parcours en un nombre minimum de coups. Ici, on résout un problème en un nombre minimum d'octets de code. De nombreux langages sont disponibles, dont OCaml.
Le problème annoncé sur la Caml-list laisse rêveur: trouver un Quine qui soit aussi un palindrome. En clair: un programme dont l'exécution affiche le code du programme, et dont le code est un palindrome, i.e. identique qu'on le lise de droite à gauche ou le contraire. Il est assez simple d'écrire un Quine, quel que soit le langage. J'ai écrit un palindrome en Caml, c'est déja un peu plus ardu. Mais satisfaire aux deux contraintes en même temps est décourageant. Alors j'ai perdu mon temps sur d'autres problèmes plus simples, en attendant de voir les solutions à celui-ci (le 08 Février, 01:46:39 heure japonaise).
La contrainte de concision force à faire des choses illisibles. Par exemple, ma solution pour le problème rot13:
À ce stade vient l'expression consacrée à Perl: ce code est write-only. Et encore c'est assez lisible comparé aux solutions du champion de Golf en OCaml:
La concision force à faire des choses qu'on ne pourrait qualifier de bonnes pratiques de programmation. Cela dit, il faut en général réfléchir à un algorithme pas trop con pour pouvoir prétendre au podium. Par exemple, même en déployant toutes les ruses de compression possibles, je sentais bien que je n'atteindrais pas les 54 octets de
De là à comprendre la ruse, ce n'est pas si simple. Tout repose sur le fait que le code ne doit pas vraiment implémenter un interpréteur Scheme: il suffit qu'il donne les bonnes réponses pour trois entrées différentes, toujours les mêmes. La plupart des participants ont utilisé cette "faille" pour répondre, par exemple
Ici, la réponse est choisie en fonction de la longueur de la première ligne de l'entrée, cette information étant suffisante pour distinguer les tests. La solution de
La clé du mystère ? Exécuté dans la boucle d'interaction
Mais cela ne répond toujours pas au problème... enfin, pas toujours. Il aura probablement fallu à
Moi je trouve ça un peu trop immoral, mais il faut avouer que ça respecte les règles du jeu. Et on aura appris quelquechose. C'est moche, mais ça marche.
Le problème annoncé sur la Caml-list laisse rêveur: trouver un Quine qui soit aussi un palindrome. En clair: un programme dont l'exécution affiche le code du programme, et dont le code est un palindrome, i.e. identique qu'on le lise de droite à gauche ou le contraire. Il est assez simple d'écrire un Quine, quel que soit le langage. J'ai écrit un palindrome en Caml, c'est déja un peu plus ardu. Mais satisfaire aux deux contraintes en même temps est décourageant. Alors j'ai perdu mon temps sur d'autres problèmes plus simples, en attendant de voir les solutions à celui-ci (le 08 Février, 01:46:39 heure japonaise).
La contrainte de concision force à faire des choses illisibles. Par exemple, ma solution pour le problème rot13:
let rec(!)?(c=input_byte stdin)x=output_byte stdout[|c;c;65+c mod x;97+(c-6)mod x|].(c/32);!x;;!26
À ce stade vient l'expression consacrée à Perl: ce code est write-only. Et encore c'est assez lisible comparé aux solutions du champion de Golf en OCaml:
ksk.La concision force à faire des choses qu'on ne pourrait qualifier de bonnes pratiques de programmation. Cela dit, il faut en général réfléchir à un algorithme pas trop con pour pouvoir prétendre au podium. Par exemple, même en déployant toutes les ruses de compression possibles, je sentais bien que je n'atteindrais pas les 54 octets de
ksk pour écrire un interpéteur Scheme minimal. Après la fin du défi, quand son code a été publié, j'ai pu constater qu'il avait rusé:print_string[|"3";"24";"5
8
58"|].(-Obj.magic(@)mod 3)
De là à comprendre la ruse, ce n'est pas si simple. Tout repose sur le fait que le code ne doit pas vraiment implémenter un interpréteur Scheme: il suffit qu'il donne les bonnes réponses pour trois entrées différentes, toujours les mêmes. La plupart des participants ont utilisé cette "faille" pour répondre, par exemple
m.ukai, classé second en OCaml:print_string[|"24";"3";"5
8
58"|].(String.length(read_line())-16)
Ici, la réponse est choisie en fonction de la longueur de la première ligne de l'entrée, cette information étant suffisante pour distinguer les tests. La solution de
ksk reste incompréhensible: il n'y a aucune instruction de lecture, aucun test dépendant de l'entrée. Pire: si vous prenez son code et le compilez (en natif ou bytecode) vous obtiendrez un programme déterministe (il affiche toujours 3 chez moi).La clé du mystère ? Exécuté dans la boucle d'interaction
ocaml comme le fait la procédure de vérification du Code Golf, ce code a une sortie aléatoire. Selon les exécutions de ocaml ksk.ml, on reçoit la réponse de l'un des trois tests. Le hasard réside dans l'initialisation de la boucle d'interaction, qui fait que l'opérateur de concaténation (@), transtypé en un int par Obj.magic va avoir une valeur grosso-modo aléatoire. Je ne fais que constater, je ne comprends pas.Mais cela ne répond toujours pas au problème... enfin, pas toujours. Il aura probablement fallu à
ksk pas mal de patience pour soumettre et re-soumettre son code jusqu'à ce que le hasard renvoie les bonnes réponses aux bons tests, et le classe premier! Cette solution est vraiment write-only: c'est illisible, et même son exécution laisse à désirer :)Moi je trouve ça un peu trop immoral, mais il faut avouer que ça respecte les règles du jeu. Et on aura appris quelquechose. C'est moche, mais ça marche.
