Récusivité terminale ?

[jack-ft]

Je ne veux pas faire tout l'exercice à ta place!

Voici un petit bout du parser.
Il traite un 'begin' implicite.
Il doit être, en gros, le premier appel à qui l'on passe:
- le nom de la fonction
- la liste des expressions du corps de la fonction
- #t

Les fonctions retournent #t si c'est récursif terminal et #f si c'est récursif non terminal.

Code :

1
2
3
4
5
6
7
8
9
10
(define (trec-body fun body term)
  (if (null? body) #t
    (if (null? (cdr body))
        ;; Last expression of body
        (trec-expr fun (car body) (and term #t))
      (and
       ;; Some non-last expression
       (trec-expr fun (car body) (and term #f))
       ;; Continue with the other expressions
       (trec-body fun (cdr body) term)))))

Le paramètre 'term' est très important!

Lorsqu'il est #t, il indique qu'on est dans un bout d'arbre ignorable (c'est-à-dire une imbrication de 'if' ou une dernière instruction).
Lorsqu'il est #f, il indique qu'on est "sous" une fonction non-ignorable (comme '+' par exemple).

Il détermine ce qu'on doit retourner si on rencontre la fonction au cours du parsing.
Plus précisément, la fonction qui retourne effectivement des valeurs et détermine si c'est récursif-terminal ou non ressemble à ceci:

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(define (trec-expr fun expr term)
  (cond
   ((not (pair? expr)) #t)
   ((eq? fun (car expr))
    ;; Found a call to 'fun'
    (if (not term) #f ;; No need to continue
      ;; Checks 'fun's args, but with 'term' set to false
      (trec-body fun (cdr expr) #f)))
   ;; This is not a call to fun. Go inside.
   (else
    (case (car expr)
      ((if) (trec-if fun (cdr expr) term))
      ((cond) (trec-cond fun (cdr expr) term))
      ;; Idem for every special form like:
      ;; apply case cond define do fluid-let lambda let let* letrec named-lambda etc.
      ((let) (trec-let fun (cdr expr) term))
      ...
      (else
       ;; This is a normal function (like '+' 'cons' etc.)
       ;; Checks its args, with 'term' set to false
       (trec-body fun (cdr expr) #f))))))

Elle devrait aussi traiter les lambda...

[kbprince]

Merci Beaucaup !

Cepedant il y a des anomalie dans la deuxième fonction :

Code :

((eq fun (car expr))

, la 4ème ligne le 'eq' n'est pas identifier :

Code :

expand: unbound identifier in module

, c'est le message qui c'est affichait , mais vous l'aviez précisé dans les messages précédents , Google est mon ami, Donc j'ai tapé le CODE ERREUR c'est un equivalent de equal? en ' # dr racket ' .

Code :

((cond) (trec-if cond (cdr expr) term))

: à la 13eme ligne , la fonction ' trec-if ' n'est pas défini.

Est que vous pouvez me faire un résumé du travail que vous avez accompli pour moi .

Merci

[jack-ft]

Envoyé par kbprince

Merci Beaucaup !

Cepedant il y a des anomalie dans la deuxième fonction :

Code :

((eq fun (car expr))

, la 4ème ligne le 'eq' n'est pas identifier :

Code :

expand: unbound identifier in module

, c'est le message qui c'est affichait , mais vous l'aviez précisé dans les messages précédents , Google est mon ami, Donc j'ai tapé le CODE ERREUR c'est un equivalent de equal? en ' # dr racket ' .

Effectivement, 'eq' est une fonction lisp!
C'est la fonction de comparaison de 2 symboles.
Il faut la "traduire" en scheme: peut-être 'eq?' ou 'equal?' ou '='... à vérifier...

Code :

((cond) (trec-if cond (cdr expr) term))

: à la 13eme ligne , la fonction ' trec-if ' n'est pas défini.

Ben oui. ça fait partie de ce qu'il te reste à faire, ainsi que 'trec-cond' à la 14ème ligne (et non trec-if), ainsi que tous les autres parsers pour les formes spéciales: 'trec-apply' 'trec-case' 'trec-define' 'trec-do' 'trec-fluid-let' 'trec-lambda' 'trec-let' 'trec-let*' 'trec-named-lambda' etc.

Par exemple, pour 'trec-if', il faut plonger en mode term=#f pour la condition, mais en mode term&=#t (c'est-à-dire term=term) pour le 'then' et pour le 'else' (en s'inspirant du code de 'trec-body', sauf que c'est beaucoup plus simple car ce n'est pas récursif (il n'y a pas d'itération dans le 'if', contrairement au 'begin')).

Est que vous pouvez me faire un résumé du travail que vous avez accompli pour moi .

Merci

Je pense en avoir suffisamment fait et tapé dans les posts précédents!

Je t'invite à lire et comprendre le code et à relire attentivement mes posts!

Si tu trouves la définition méta-circulaire de l'interprète scheme, ça pourrait aussi te servir de modèle. Sinon, je sais que ça existe pour lelisp et c'est un exercice assez courant (comment définir la fonction 'eval' en lisp).

PS: j'ai modifié le code du post précédent!

Bon courage pour la suite!

[kbprince]

Je vous remercie pour tous, vous avez fait plus que la moitié du programme, mais ce travail vous appartien a vous et pas a moi , conclusion je sais pas ce qui ce passe dans le programme , comment l'utiliser , ce que je dois completer.

Au fait , si vous devier juste m'expliqué les parametre que vous avez utilisé , comme sa moi quand j'ecrirai le mode d'emploi pour le prof, je serai quoi expliqué.

Et sa pourra m'aider a traiter les autre 'trec speciale'.

Encore Merci Pour Tous

[jack-ft]

Envoyé par kbprince

Je vous remercie pour tous, vous avez fait plus que la moitié du programme, mais ce travail vous appartien a vous et pas a moi , conclusion je sais pas ce qui ce passe dans le programme , comment l'utiliser , ce que je dois completer.

Tout le code qui est dans les forums est libre de droits (sauf mention contraire).

Il faut effectivement que tu comprennes le code pour te l'approprier!

Le mieux serait que tu relises tout et que tu l'expérimentes sur des exemples simples.

Au fait , si vous devier juste m'expliqué les parametre que vous avez utilisé , comme sa moi quand j'ecrirai le mode d'emploi pour le prof, je serai quoi expliqué.

Et sa pourra m'aider a traiter les autre 'trec speciale'.

Encore Merci Pour Tous

Dans le post 21, les paramètres sont plus ou moins indiqués.

Toutes les fonctions 'trec-*' retournent #f si elles ont détecté un appel de 'fun' non récursif terminal, #t sinon.

Pour trec-body (qui devrait en fait s'appeler 'trec-begin'):
- fun: un symbole, le nom de la fonction dont on cherche les appels dans 'body'
- body: une liste d'expressions, c'est-à-dire le contenu d'un 'begin' (implicite ou explicite) (par exemple issu du corps d'une fonction)
- term: un booléen qui détermine la valeur à retourner lorsque un appel à 'fun' est détecté dans 'body'
#t indique qu'on est dans un bout d'arbre ignorable (c'est-à-dire une imbrication de 'if' ou une dernière instruction d'un 'begin').
#f indique qu'on est "sous" une fonction non-ignorable (comme '+' par exemple).

Pour trec-expr:
- fun: un symbole, le nom de la fonction dont on cherche les appels dans 'expr'
- expr: une expression lisp
- term: un booléen qui détermine la valeur à retourner lorsque un appel à 'fun' est détecté dans 'expr'
#t indique qu'on est dans un bout d'arbre ignorable (c'est-à-dire une imbrication de 'if' ou une dernière instruction).
#f indique qu'on est "sous" une fonction non-ignorable (comme '+' par exemple).
Lorsque 'trec-expr' détecte que 'expr' est un appel à 'fun', c'est-à-dire de la forme ('fun' args...), et que term == #f (indiquant qu'on a "traversé" une fonction non-ignorable), alors elle retourne #f, indiquant que cet appel n'est pas récursif-terminal. Tous les retours de fonctions appelantes 'trec-*' devront alors retourner #f.

Bonne continuation!

[kbprince]

Bonjour
Il me reste une dernière chose à vous demander , les 'trec-*' , que je dois définir , quel est leurs fonctions ? Par exemple : la fonction de 'trec-lampda' ? 'Trec-cond' ? 'Trec-casé' ? Etc ...
Merci.

[jack-ft]

Envoyé par kbprince

Bonjour
Il me reste une dernière chose à vous demander , les 'trec-*' , que je dois définir , quel est leurs fonctions ? Par exemple : la fonction de 'trec-lampda' ? 'Trec-cond' ? 'Trec-casé' ? Etc ...
Merci.

Ben, c'est écrit dans mon dernier post:
Toutes les fonctions 'trec-*' retournent #f si elles ont détecté un appel de 'fun' non récursif terminal, #t sinon.

De plus, chaque fonction 'trec-something' parse une expression (something args...)... sauf 'trec-body' qui parse un 'begin' implicite!

Du coup, l'écriture du vrai 'trec-begin' est immédiate:

Code :

1
2
3
4
5
(define (trec-begin fun expr term)
  (if (null? expr)
    (error "bad call to trec-begin" expr)
    ;; Parse the body of the 'begin' expr
    (trec-body fun (cdr expr) term)))

Finalement 'trec-body' pourrait s'appeler 'trec-implicit-begin'!


Pour comprendre l'histoire du paramètre 'term', voici un exemple:

Cette fonction 'membre' est récursive-terminale:

Code :

1
2
3
4
5
6
(define (membre a l)
  (if (not (pair? l))
    0
    (if (eq a (car l))
      1
      (membre a (cdr l)))))

La fonction 'erbmem' n'est pas récursive terminale

Code :

1
2
3
4
5
6
(define (erbmem a l)
  (if (not (pair? l))
    0
    (+ (+ a (car l))
      1
      (erbmem a (cdr l)))))

à cause du fait que j'ai remplacé l'un des 'if' par '+', et, pourtant, elles se ressemblent beaucoup!

Conclusion: la position seule de l'appel de la fonction dans son propre corps ne peut pas suffire à déterminer si c'est récursif terminal. Il faut vraiment prendre en compte que l'appel de 'membre' est imbriqué sous 2 'if' (ce qui ne gêne pas la récursivité terminale) alors que l'appel de 'erbmem' est imbriqué sous un '+', ce qui empêche la récursivité terminale.

Dans http://fr.wikipedia.org/wiki/R%C3%A9cursion_terminale , on trouve:

Code :

tail_recursive() est une récursion terminale, tandis que not_tail_recursive() ne l'est pas, car sa dernière instruction est une composition faisant intervenir l'appel récursif.

Dans un langage qui utilise l'instruction 'return', c'est très simple de déterminer ce qui est ou non récursif terminal.
Il suffit de vérifier que tous les appels de la fonction sont juste précédés du mot return!

Le problème, dans scheme (ou lisp), c'est qu'il n'y a pas d'instruction 'return' parce que tout est implicitement un return!

Si on ajoutait des returns dans scheme, on pourrait réécrire 'membre' de la façon suivante:

Code :

1
2
3
4
5
6
7
(define (membre a l)
  (return
    (if (not (pair? l))
      0
      (if (eq a (car l))
        1
        (membre a (cdr l))))))

qui est équivalent à:

Code :

1
2
3
4
5
6
7
(define (membre a l)
  (if (not (pair? l))
    (return 0)
    (return
      (if (eq a (car l))
        1
        (membre a (cdr l))))))

qui est équivalent à:

Code :

1
2
3
4
5
6
(define (membre a l)
  (if (not (pair? l))
    (return 0)
    (if (eq a (car l))
      (return 1)
      (return (membre a (cdr l))))))

et là, ô magie!, on voit clairement que l'appel de 'membre' est récursif terminal (puisque, sur la dernière ligne, les mots 'return' et 'membre' sont consécutifs).

Dans les transformations successives, les 'return's ont "traversé" les 'if's, mais ils ne peuvent pas traverser les autres fonctions:

Code :

1
2
3
4
5
6
7
(define (erbmem a l)
  (return
    (if (not (pair? l))
      0
      (+ (+ a (car l))
        1
        (erbmem a (cdr l))))))

est équivalent à:

Code :

1
2
3
4
5
6
7
(define (erbmem a l)
  (if (not (pair? l))
    (return 0)
    (return
      (+ (+ a (car l))
        1
        (erbmem a (cdr l))))))

et on ne peut pas aller plus loin! Le 2ème return ne peut pas traverser le '+'.

On voit donc clairement que l'appel de 'erbmem' n'est PAS récursif terminal (puisque le dernier appel de 'erbmem' n'est pas immédiatement précédé de 'return'.

Est-ce clair?

As-tu écrit le 'trec-if' ?
C'est le minimum pour tester la récursivité terminale des fonctions simples qui ont été mentionnées dans les différents posts.
Il est très simple (pas plus de 5 ou 6 lignes) et ressemble en partie aux autres 'trec-*' déjà écrits.

[kbprince]

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
(define (trec-if fun if term)
  (if (not (pair? term))
    0
    (if (equal? if (car term))
      1
      (trec-if if (cdr term)))))

(define (trec-cond a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-cond a (cdr l)))))

(define (trec-named-lambda a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-named-lambda a (cdr l)))))

(define (trec-let a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-let a (cdr l)))))

(define (trec-let* a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-let* a (cdr l)))))

(define (trec-letrec a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-letrec a (cdr l)))))

(define (trec-case a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-case a (cdr l)))))

(define (trec-apply a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-apply a (cdr l)))))

(define (trec-define a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-define a (cdr l)))))

(define (trec-do a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-do a (cdr l)))))
(define (trec-fluid a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (trec-fluid a (cdr l)))))

(define (term a df)
  (if (null? df)#f
      (if (equal? (trec-if df)(cdr df))#f
          (if (equal? (trec-cond df)(cdr df))#f
              (if (equal? (trec-case df)(cdr df))#f
                  (if (equal? (trec-apply df)(cdr df))#f
                      (if (equal? (trec-define df)(cdr df))#f
                          (if (equal? (trec-named-lambda df)(cdr df))#f
                              (if (equal? (trec-let df)(cdr df))#f
                                  (if (equal? (trec-let* df)(cdr df))#f
                                  (if (equal? (trec-letrec df)(cdr df))#f
                                  (if (equal? (trec-fluid df)(cdr df))#f
                                  (if (equal? (trec-do df)(cdr df))#f
                                      #t)))))))))))))

          








(define (trec-body fun body term)
  (if (null? body) #t
    (if (null? (cdr body))
        ;; Last expression of body
        (trec-expr fun (car body) (and term #t))
      (and
       ;; Some non-last expression
       (trec-expr fun (car body) (and term #f))
       ;; Continue with the other expressions
       (trec-body fun (cdr body) term)))))

(define (trec-expr fun expr term)
  (cond
   ((not (pair? expr)) #t)
   ((eq? fun (car expr))
    ;; Found a call to 'fun'
    (if (not term) #f ;; No need to continue
      ;; Checks 'fun's args, but with 'term' set to false
      (trec-body fun (cdr expr) #f)))
   ;; This is not a call to fun. Go inside.
   (else
    (case (car expr)
      ((if) (trec-if fun (cdr expr) term))
      ((cond) (trec-cond fun (cdr expr) term))
      ;; Idem for every special form like:
      ((apply) (trec-apply fun (cdr expr) term))
      ((case) (trec-case fun (cdr expr) term))
      ((define) (trec-define fun (cdr expr) term))
      ((do) (trec-do fun (cdr expr) term))
      ((fluid) (trec-fluid fun (cdr expr) term))
      ((let) (trec-let fun (cdr expr) term))
      ((let*) (trec-let* fun (cdr expr) term))
      ((letrec) (trec-letrec fun (cdr expr) term))
      ((named-lambda) (trec-named-lambda fun (cdr expr) term))
      
   ;; apply case cond define do fluid-let lambda let let* letrec named-lambda etc.
       
      (else (trec-body fun (cdr expr) #f))))))

[kbprince]

Je vous ai posteé , dans le message précédent le programme que j'ai envoyé pour le prof , j'ai précisez dass le comptre rendu qu'il marchait pas , j'avais pas fini la fonction qui utlise les parse au complet.

Donc c'est trop tard ! ,enfin je l'ai rendu mai je l'ai pa finil .

[jack-ft]

Envoyé par kbprince

Code :

C'était bien essayé (au hasard?), mais ce n'est pas tout à fait ça...

Comme indiqué précédemment, toutes les fonctions 'trec-*' doivent retourner un booléen et non 0 ou 1.

Le premier argument des 'trec-*' est toujours 'fun' puisque c'est la fonction dont on cherche les appels dans le parsing.

Toutes les fonctions trec-* sont forcément fortement récursives, puisqu'il faut parser jusqu'au bout de l'arbre.
Généralement, elles vont appeler 'trec-expr' ou 'trec-body'

Par exemple, la fonction 'trec-if' dit que si on rencontre 'fun' dans la partie 'test', alors ce n'est pas terminal, par contre, si on la rencontre dans le then ou le else, c'est terminal.
C'est pour ça qu'on passe respectivement #f term et term:

Code :

1
2
3
4
5
6
7
8
(define (trec-if fun expr term)
  (if (null? expr)
    (error "bad call to trec-if" expr)
    (and
      (trec-expr fun (cadr expr) #f) ; Parse the 'test'
      (trec-expr fun (caddr expr) term) ; Parse the 'then'
      (if (null? (cdddr expr) #t ; No 'else'
        (trec-expr fun (cadddr expr) term))))) ; Parse the 'else'

Avec les trec-body, trec-expr et trec-if que je t'ai fournies, tu peux déjà vérifier qu'elles parsent correctement les fonctions 'membre' et 'erbmem', ainsi que la plupart des fonctions sans fonction auxiliaire.

Voilà.

[jack-ft]

Envoyé par kbprince

Je vous ai posteé , dans le message précédent le programme que j'ai envoyé pour le prof , j'ai précisez dass le comptre rendu qu'il marchait pas , j'avais pas fini la fonction qui utlise les parse au complet.

Donc c'est trop tard ! ,enfin je l'ai rendu mai je l'ai pa finil .

Dommage! Il aurait peut-être fallu commencer plus tôt!

[kbprince]

Code :

C'était bien essayé (au hasard?), mais ce n'est pas tout à fait ça...

Oui j"avais vraiment mis cà au hasard, je me suis au moin je vais etre recompensé pour avoir essayer.

Code :

Avec les trec-body, trec-expr et trec-if que je t'ai fournies, tu peux déjà vérifier qu'elles parsent correctement les fonctions 'membre' et 'erbmem', ainsi que la plupart des fonctions sans fonction auxiliaire.

c'a veux dire que ma fonction

Code :

(define (term fun expr))

marche trés bien?(parceque j'a vu que vous pas fait de commentaire sur ca.

avec la fonction trec-expr' sa donne toujour '#t'

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
> (trec-expr  membre term '
((define (membre a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (membre a (cdr l))))))))
 #t
> (trec-expr  erbmem term '
(define (erbmem a l)
  (if (not (pair? l))
    0
    (+ (+ a (car l))
      1
      (erbmem a (cdr l)))))))
#t , donc lle booleen ne marche pas , pour l'instant .

>

quand j'utilise la fonction 'trec-body' sa ma donne sa comme résultat:

Code :

1
2
3
4
5
6
7
8
9
10
11
(trec-body  membre term '
((define (membre a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (membre a (cdr l)))))))


. . cdr: expects argument of type <pair>; given #<procedure:term>
>

Merci !

[jack-ft]

Envoyé par kbprince

Code :

C'était bien essayé (au hasard?), mais ce n'est pas tout à fait ça...

Oui j"avais vraiment mis cà au hasard, je me suis au moin je vais etre recompensé pour avoir essayer.

Je suis pas sûr que ce soit une très bonne idée...

L'ensemble du code peut donner l'impression d'un poème dont certains vers sont de parfaits alexandrins tandis que d'autres semblent avoir été écrits par un enfant... (ce n'est qu'une métaphore! (je ne veux ni m'encenser ni te vexer!))

Et le prof risque de ne pas aimer s'il demande un travail personnel!
S'il juge sur la capacité à susciter un travail collaboratif, ça peut le faire...

Code :

Avec les trec-body, trec-expr et trec-if que je t'ai fournies, tu peux déjà vérifier qu'elles parsent correctement les fonctions 'membre' et 'erbmem', ainsi que la plupart des fonctions sans fonction auxiliaire.

c'a veux dire que ma fonction

Code :

(define (term fun expr))

marche trés bien?(parceque j'a vu que vous pas fait de commentaire sur ca.

Je n'ai pas tout commenté!
Si j'étais le correcteur, j'aurais fait plus de commentaires!

En ce qui concerne ta fonction 'term':
- je trouve que c'est confusant de lui donner le même nom que la variable 'term'
- comment peux-tu espérer qu'elle marche alors que TOUS les appels ne respectent pas le protocole des fonctions!
ex: dans (if (equal? (trec-if df) (cdr df))#f, tu appelles trec-if avec un seul argument alors que toutes les fonctions 'trec-*' en attendent 3.

Je suis vraiment triste que tu n'aies pas compris cela!

avec la fonction trec-expr' sa donne toujour '#t'

Code :

Comme indiqué dans le post 21:

Il doit être, en gros, le premier appel à qui l'on passe:
- le nom de la fonction
- la liste des expressions du corps de la fonction
- #t

Code :

1
2
3
4
(define (trec-df? df) ; df == le 'define'
  (trec-body (caadr df) ; le nom
    (cddr df) ; la liste des instructions de la fonction
    #t))

En effet, 'trec-body' parse une liste d'instructions (un 'begin' implicite).

Donc, en gros (si on n'utilise pas trec-df?):

Code :

1
2
3
4
5
6
7
(trec-body 'membre ; le nom de la fonction et non sa valeur
 '((if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (membre a (cdr l)))))
 #t)

quand j'utilise la fonction 'trec-body' sa ma donne sa comme résultat:

Code :

Merci !

à débeuguer...
mais, comme tu lui passes un 'define', il faut voir comment il le parse.
Probablement en appelant 'trec-define', mais ça ne rentre plus dans le cadre d'une fonction sans sous-fonction!

[kbprince]

La fonction 'trec-body' teste si la fonction es récursive ou pas , et la fonction 'trec-expr' teste si la fonction es en récursivité terminal, c'est bien sa ? ,
Donc pour faire le teste, en utilise directement la fonction 'trec'expr'!

Code :

1
2
3
4
5
(define (term fonction expr)
       
      (if (equal? (trec-if fonction expr)(cdr expr))#f
         
                                      #t))

j'ai remodifié la fonction mais sa marche pas toujours.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> (trec-expr  prod term '
(define (prod n);produit des nombres jusqu'à n
  (if (= n 0)
      1
      (* n (prod (- n 1))))))
#t
> (trec-expr  membre term '

(define (membre a l)
  (if (not (pair? l))
    0
    (if (equal? a (car l))
      1
      (membre a (cdr l))))))

#t

la permeire fonction n'est pas Rterminal mais sa renvoi toujours true.

[kbprince]

Bonjour
Même La fonction 'teec-expr' auquel j'ai apporté les modification ne marche pas aussi?

[kbprince]

Maintenant que le délai est passé est que , je peux avoir tout le programme?
Merci de m'avoir aidé en tout cas ,j'ai bien grandi avec vous, je vous ecrirai prochainement pour lles questions sur les partiel.

[jack-ft]

Envoyé par kbprince

La fonction 'trec-body' teste si la fonction es récursive ou pas , et la fonction 'trec-expr' teste si la fonction es en récursivité terminal, c'est bien sa ? ,

Non, pas du tout!

La fonction 'trec-expr' doit retourner #t si l'expression scheme passée en paramètre est récursive terminale (vis à vis de la fonction passée) et doit retourner #f si elle est récursive non terminale.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(trec-expr 'foo '() #t)
=> #t

(trec-expr 'foo '(+ 2 3) #t)
=> #t

(trec-expr 'foo '(bar) #t)
=> #t

(trec-expr 'foo '(foo) #t)
=> #t

(trec-expr 'foo '(foo (+ 3 4)) #t)
=> #t

(trec-expr 'foo '(begin (print "coucou") (foo)) #t)
=> #t

(trec-expr 'foo '(begin (bar) (print "coucou")) #t)
=> #t

(trec-expr 'foo '(begin (foo) (print "coucou")) #t)
=> #f

(trec-expr 'foo '(if (null? l) #f (foo (cdr l))) #t)
=> #t

(trec-expr 'foo '(or (null? l) #f (foo (cdr l))) #t)
=> #f

(trec-expr 'foo '(foo (+ 3 4) (foo 1)) #t)
=> #f

La fonction 'trec-body' doit retourner #t si la liste d'expressions est récursive terminale et doit retourner #f si elle est récursive non terminale.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(trec-body 'foo '() #t)
=> #t

(trec-body 'foo '((bar)) #t)
=> #t

(trec-body 'foo '((foo)) #t)
=> #t

(trec-body 'foo '((foo (+ 3 4))) #t)
=> #t

(trec-body 'foo '((print "coucou") (foo)) #t)
=> #t

(trec-body 'foo '((bar) (print "coucou")) #t)
=> #t

(trec-body 'foo '((foo) (print "coucou")) #t)
=> #f

(trec-body 'foo '((if (null? l) #f (foo (cdr l)))) #t)
=> #t

(trec-body 'foo '((or (null? l) #f (foo (cdr l)))) #t)
=> #f

[jack-ft]

Envoyé par kbprince

Maintenant que le délai est passé est que , je peux avoir tout le programme?

Bien sûr que tu peux l'avoir: il suffit que tu l'écrives!

ou que quelqu'un d'autre l'écrive!

Pour avoir quelque chose de vraiment complet, il faut probablement y passer pas mal de temps. Je serais assez curieux de voir la solution proposée par ton prof. Peux-tu la poster ici (ou poster un lien) quand tu l'auras?

[jack-ft]

Envoyé par jack-ft

Bien sûr que tu peux l'avoir: il suffit que tu l'écrives!

ou que quelqu'un d'autre l'écrive!

Pour avoir quelque chose de vraiment complet, il faut probablement y passer pas mal de temps.

Finalement, j'ai fait un 'sudo apt-get install mit-scheme'.
J'ai recopié les fonctions que j'avais proposées.
J'ai choisi que les fonctions trec-* (comme trec-if et trec-begin) reçoivent la forme complète (c'est-à-dire avec le 'if' et le 'begin').
J'ai ajouté quelques tests de vérification sur les fonctions proposées dans ce post (j'ai pas mal galéré pour avoir un simple 'eval' qui marche! )

Ce n'est pas complet (il n'y a que trec-if et trec-begin), mais ça marche pour toutes les fonctions sans sous-fonction.

Et voilà le boulot (une cinquantaine de lignes de code et une centaine de lignes de tests):

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
(define (trec-df? df)                   ; df == le 'define'
  (trec-implicit-begin
   (first (second df))      ; le nom
   (cddr df)                ; la liste des instructions de la fonction
   #t))

(define (trec-implicit-begin fun body term)
  (if (null? body) #t
      (if (null? (cdr body))
          ;; Last expression of body
          (trec-expr fun (first body) (and term #t))
          (and
           ;; Some non-last expression
           (trec-expr fun (first body) (and term #f))
           ;; Continue with the other expressions
           (trec-implicit-begin fun (cdr body) term)))))

(define (trec-expr fun expr term)
  (cond
   ((not (pair? expr)) #t)
   ((eq? fun (first expr))
    ;; Found a call to 'fun'
    (if (not term) #f ;; No need to continue
        ;; Checks 'fun's args, but with 'term' set to false
        (trec-implicit-begin fun (cdr expr) #f)))
   ;; This is not a call to fun. Go inside.
   (else
    (case (first expr)
      ((if) (trec-if fun expr term))
      ((begin) (trec-begin fun expr term))
      ;; Idem for every special form like:
      ;; apply case cond define do fluid-let lambda let let* letrec named-lambda etc.
      ;;((cond) (trec-cond fun (cdr expr) term))
      ;;((let) (trec-let fun expr term))
      ;;...
      (else
       ;; This is a normal function (like '+' 'cons' etc.)
       ;; Checks its args, with 'term' set to false
       (trec-implicit-begin fun (cdr expr) #f))))))

(define (trec-if fun expr term)
  (if (null? expr)
      (error "bad call to trec-if" expr)
      (and
       (trec-expr fun (second expr) #f)           ; Parse the 'test'
       (trec-expr fun (third expr) term)          ; Parse the 'then'
       (if (null? (cdddr expr)) #t                ; No 'else'
           (trec-expr fun (fourth expr) term))))) ; Parse the 'else'

(define (trec-begin fun expr term)
  (if (null? expr)
      (error "bad call to trec-begin" expr)
      ;; Parse the body of the 'begin' expr
      (trec-implicit-begin fun (cdr expr) term)))

;;; ----------------------------------------------------------------

(define jd-assert-environment (the-environment))

(define (jd-assert-true expr) (jd-assert-equals expr #t))
(define (jd-assert-false expr) (jd-assert-equals expr #f))
(define (jd-assert-equals expr expected)
  (let ((value (eval expr jd-assert-environment)))
    (if (not (eq? expected value))
        (error expr " returned " value " - Expected: " expected))))

;;; ----------------------------------------------------------------

(jd-assert-true '(trec-expr 'foo '() #t))
(jd-assert-true '(trec-expr 'foo '(+ 2 3) #t))
(jd-assert-true '(trec-expr 'foo '(bar) #t))
(jd-assert-true '(trec-expr 'foo '(foo) #t))
(jd-assert-true '(trec-expr 'foo '(foo (+ 3 4)) #t))
(jd-assert-true '(trec-expr 'foo '(begin (print "coucou") (foo)) #t))
(jd-assert-true '(trec-expr 'foo '(begin (bar) (print "coucou")) #t))
(jd-assert-false '(trec-expr 'foo '(begin (foo) (print "coucou")) #t))
(jd-assert-true '(trec-expr 'foo '(if (null? l) #f (foo (cdr l))) #t))
(jd-assert-false '(trec-expr 'foo '(or (null? l) #f (foo (cdr l))) #t))
(jd-assert-false '(trec-expr 'foo '(foo (+ 3 4) (foo 1)) #t))

(jd-assert-true '(trec-implicit-begin 'foo '() #t))
(jd-assert-true '(trec-implicit-begin 'foo '((bar)) #t))
(jd-assert-true '(trec-implicit-begin 'foo '((foo)) #t))
(jd-assert-true '(trec-implicit-begin 'foo '((foo (+ 3 4))) #t))
(jd-assert-true '(trec-implicit-begin 'foo '((print "coucou") (foo)) #t))
(jd-assert-true '(trec-implicit-begin 'foo '((bar) (print "coucou")) #t))
(jd-assert-false '(trec-implicit-begin 'foo '((foo) (print "coucou")) #t))
(jd-assert-true '(trec-implicit-begin 'foo '((if (null? l) #f (foo (cdr l)))) #t))
(jd-assert-false '(trec-implicit-begin 'foo '((or (null? l) #f (foo (cdr l)))) #t))

(jd-assert-true
 '(trec-df?
   '(define (membre a l)
      (if (not (pair? l))
          0
          (if (eq a (car l))
              1
              (membre a (cdr l)))))))

(jd-assert-false
 '(trec-df?
   '(define (erbmem a l)
      (if (not (pair? l))
          0
          (+ (+ a (car l))
             1
             (erbmem a (cdr l)))))))

(jd-assert-true
 '(trec-df?
   '(define (somraux n acc)
      (if (= n 0)
          acc
          (somraux (- n 1) (+ n acc))))))

(jd-assert-false
 '(trec-df?
   '(define (aplatir-interne e r)
      (if (pair? e)
          (aplatir-interne (car e) (aplatir-interne (cdr e) r))
          (if (null? e) r (cons e r))))))

(jd-assert-true
 '(trec-df?
   '(define (multraux a b acc)
      (if (= a 0)
          acc
          (multraux (- a 1) b (+ b acc))))))

(jd-assert-true
 '(trec-df?
   '(define (rac2 n r)                  ; racine carré
      (if (> (carre r) n)
          (- r 1)        
          (rac2 n ( + r 1))))))

(jd-assert-false
 '(trec-df?
   '(define (mult a b)             ; multiplication avec des ( + et -)
      (if (= a 0)
          0
          (+ b (mult (- a 1) b))))))

(jd-assert-true
 '(trec-df?
   '(define (praux p n acc)
      (if (= p 0)
          acc
          (praux (- p 1) n (* n acc))))))

(jd-assert-false
 '(trec-df?
   '(define (reconstruire exp)
      (if (pair? exp)
          (list 'cons (reconstruire (car exp))
                (reconstruire (cdr exp)) )
          (list 'quote exp)))))

(jd-assert-false
 '(trec-df?
   '(define (compter mot phrase)
      (if (pair? phrase)
          (+ (if (equal? mot (car phrase)) 1 0) ; Notez l'alternative sous l'addition!
             (compter mot (cdr phrase)) )
          0 ))))

(jd-assert-false
 '(trec-df?
   '(define (fact1 a)
      (if (= a 0)
          1
          (* a (fact1 (- a 1)))))))

[kbprince]

je vous remercie pour la correction , mais au fait le programme il a marché , c'est moi qui a mal ecrit les arguments .
Sur l'argument 'fun' il fallait l'ecrire avec l'apostrophe , et moi je l'ai fait sans aposthrophe. Du coup le programme il marchais avant que vous me donniez la corrections.mais déja trop tard

Merci pour tous ! A bientôt