From madore@news.ens.fr
Path: eleves!not-for-mail
From: madore@news.ens.fr (GroTeXdieck)
Newsgroups: ens.forum.alt.bavardage.bienheureux,ens.forum.informatique.lang
Subject: Re: Quine
Followup-To: ens.forum.informatique.lang
Date: 29 Oct 1999 11:52:54 GMT
Lines: 86
Sender: madore@goelette.ens.fr
Message-ID: <7vc1qm$845$3@clipper.ens.fr>
References: <7v6ivq$6b8$1@clipper.ens.fr> <7vajvd$88d$1@clipper.ens.fr> <7vbk1j$bvs$3@clipper.ens.fr>
NNTP-Posting-Host: goelette.ens.fr
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: clipper.ens.fr 941197974 8325 129.199.129.6 (29 Oct 1999 11:52:54 GMT)
X-Complaints-To: forum@clipper.ens.fr
NNTP-Posting-Date: 29 Oct 1999 11:52:54 GMT
X-Newsreader: Flrn (0.4.0 - 07/99)
X-Wisdom-Of-The-Day: The opposite of stability couldn't help avoid justice. 
Xref: eleves ens.forum.alt.bavardage.bienheureux:616 ens.forum.informatique.lang:248

Régis Lachaume in litteris (alt.bavardage.bienheureux:613) scripsit :
> Quelqu'un peut-il m'expliquer comment on peut écrire du unlambda ???

Écrire du Unlambda, ce n'est pas si difficile.  C'est *lire* du
Unlambda qui est (à peu près) impossible.

Voici par exemple les étapes pour écrire un programme Unlambda qui
boucle sur « Hello, world! ».

D'abord, il me faut un truc pour boucler.  Essentiellement, je veux
traduire

(define (perpetual-loop)
  (display "Hello, world!\n")
  (perpetual-loop))
(perpetual-loop)

Première étape, il faut supprimer le letrec implicite.  Cela se fait
par la manière standard : on fait une demi-boucle qui va prendre la
demi-boucle en argument.

(define (half-loop h)         ; h will be half-loop itself (so we can
  (display "Hello, world!\n") ; avoid calling half-loop from
  (h h)) ; See?               ; half-loop).
(half-loop half-loop)

Ensuite, je transforme ça en lambda-calcul pur (je note les lambdas
avec des ^ et les variables avec des $) ; on supposera que $D est une
fonction magique qui affiche « Hello, world! » et qui au demeurant se
comporte comme l'identité.  Ça donne

<half-loop> = ^h``$D$h$h
<main> = `<half-loop><half-loop>

Noter que je fais ``$D$h$h et non `$D`$h$h, parce que si j'essaye ça,
le `$h$h sera évalué d'abord et la récursion ne terminera jamais (en
gros, ça reviendrait à inverser le (h h) et le (display ...) dans le
programme en Scheme).

Maintenant, je délambdaifie le <half-loop>.  Je peux faire ça de
manière automatique :

goelette madore ~ $ guile -l 'scheme/unlambda/unlambdaify.scm' -c '(unparse (remove-lambdas (parse))) (newline)'
^h``$D$h$h
``s``s`k$Dii
goelette madore ~ $ 

Mais puisque c'est aussi court, faisons-le à la main :

^h``$D$h$h c'est ^h de (`$D$h) appliqué à ($h).  Par la définition de
s, c'est donc s appliqué à (^h`$D$h) et à (^h$h), soit
``s^h`$D$h^h$h ; le second (^h$h), c'est l'identité ; le premier
(^h`$D$h), on peut certes l'écrire ``s`k$D si on veut, mais on peut
aussi remarquer que c'est simplement $D.  Donc

<halfloop> = ``s$Di
<main> = `<halfloop><halfloop>

Reste à déterminer la fonction $D.  Il y a plein de façons possibles.
Par exemple unlambdaifier

^x``````````````.H.e.l.l.o.,. .w.o.r.l.d.!r$x

ce qui donne, pour $D,

``s``s``s``s``s``s``s``s``s``s``s``s``s``s`k.H`k.e`k.l`k.l`k.o`k.,`k. `k.w`k.o`k.r`k.l`k.d`k.!`kri

mais on peut aussi décider d'utiliser d pour simplifier les choses et
prendre, pour $D

`d`````````````.H.e.l.l.o.,. .w.o.r.l.d.!r

Bon, dernier point, plutôt que d'écrire <main>=`<halfloop><halfloop>
ce qui implique de répéter deux fois le $D ci-dessus, on va plutôt
utiliser

<double> = ^h`$h$h = ``sii

et <main> = `<double><halfloop>

Ce qui donne finalement

```sii
 ``s`d`````````````.H.e.l.l.o.,. .w.o.r.l.d.!ri

Et ça marche.