Schéma d'équivalence symbolique

Question

La plate-forme sur laquelle je travaille est DrScheme.

J'ai vu qu'une paire (a b) [construit par (cons a b)] est mis en œuvre dans la langue comme une procédure qui ressemble à ceci:

(define (cons a b) 
    (lambda(pick) 
    (cond ((= pick 1) a) 
      ((= pick 2) b)))) 

et les sélecteurs:

(define (car x) (x 1)) 
(define (cdr x) (x 2)) 

Ensuite, il sont des listes, construites avec une expression comme (cons a (cons b (cons c (cons ...)))).

Maintenant, ce que j'essaie de comprendre ce (dactylographié sur l'invite de DrScheme):

> (define l1 '(a b c)) 
> (define l2 (list 'a 'b 'c)) 
> l1 
(a b c) 
> l2 
(a b c) 
> (eq? l1 l2) 
#f 

Ok, l2 est juste une liste (qui est une procédure, ect ...) comme i » Nous avons décrit la situation, mais ... ce que est l1? Un symbole? Une séquence de personnage? Et quoi que ce soit, comment est-il mis en œuvre dans la langue? Merci!

Answer 1

l1 est également juste une liste contenant les mêmes éléments. Notez que cela renvoie également #f:

(define l1 '(a b c)) 
(define l2 '(a b c)) 
(eq? l1 l2) 

Bien que cela retourne #t:

(define l1 '(a b c)) 
(define l2 (list 'a 'b 'c)) 
(equal? l1 l2) 

La raison est que eq? vérifie si l1 et l2 sont des références au même objet en mémoire, alors que equal? vérifie si elles avoir le même contenu.

Answer 2

Les listes ne sont pas atomes, c'est la partie importante ici. Les symboles sont cependant des atomes, ce qui signifie que lorsqu'ils sont identiques, ils résident dans la même mémoire, ils sont comme des nombres et peuvent en effet être vus comme des indicateurs. Les symboles ne sont pas mutables aussi, un symbole foo est comme un nombre 3. Les listes ne sont cependant pas des atomes, deux listes, ou des chaînes de vecteurs ayant le même contenu peuvent très bien résider dans deux endroits différents de la mémoire.

eq? tests sur l'emplacement de la mémoire uniquement. eqv? tests d'équivalence, ce qui est vague et cela dépend de quelle implémentation, la norme Scheme est assez libérale avec cela, il dit seulement qu'il doit au moins être un surensemble de eq? essentiellement. equal? à l'autre extrémité teste l'égalité structurelle et le fait de manière récursive, c'est donc une opération très coûteuse et c'est pourquoi les symboles sont souvent préférés aux chaînes pour les identifiants.

(define l1 (list 1 2 3)) 
(define l2 (list 1 2 3)) 
(eq? l1 l2) ; ===> #f in most implementations 
(equal? l1 l2) ; ===> #t in all implementations 
(eqv? l1 l2) ; ===> #t in some implementations 
(define l3 (cdr l1)) 
(define l4 (cdr l1)) 
(eq? l3 l4) ; ===> #t, this means that they 'share memory', if you change l3 or l4, l1 will change with it, beware. This is how car and cdr work, they do not copy. 
(define l6 (cons 1 l4)); 
(eq? l1 l6) ; ===> #f again, cons does allocate new memory, but the tails may very well share it, s in this case, l6 does share its tail with all lists except l2 here in memory. 

En outre, un peu de terminologie, par contre crée une paire, ce qui est différent d'une liste de deux éléments, il crée une paire (a . b) la liste (a b) est en fait identique à la paire (a . (b .()))

également , contre et car et cdr sont des primitives, l'implémentation que vous voyez ci-dessous est la démonstration dans Structure et implémentation de programmes d'ordinateur qui montre qu'ils ne sont pas strictement nécessaires comme eux, mais les avoir comme primitives augmente considérablement les performances, donc mieux vaut ne pas -définissez vos contre, la voiture et les CDR.

Answer 3

> > (define l1 '(a b c)) 
> > (define l2 (list 'a 'b 'c)) 
> > l1 (a b c) 
> > l2 (a b c) 
> > (eq? l1 l2) 
> #f 

Ok, l2 est juste une liste (qui est une procédure, ect ...) comme je l'ai décrit demeure, mais ... ce qui est l1? Un symbole? Une séquence de personnage? Et quoi que ce soit , comment est-il mis en œuvre dans la langue? Merci!

Une définition de la forme:

(< définir name> < expression>)

Lors de l'exécution de l'expression < expression> est évalué, et le résultat est une valeur. Cette valeur est stockée quelque part en mémoire. Pour utiliser cette valeur dans d'autres calculs, vous pouvez utiliser le nom < La terminologie est que le nom <> est lié à la valeur. La chose importante à noter est que le nom < nom n'apparaît que dans le code source de votre . Il n'est pas présent lors de l'exécution. Demander si le nom l1 est un symbole n'a donc aucun sens.

Une stratégie possible pour un compilateur de traduire (définir < nom> < expression>) est la suivante (en ignorant que les implémentations Scheme ont garbage collection).

1. réserve un m de cellules de mémoire pour un pointeur p
2. de code de sortie qui calcule la valeur v de
3. stocker l'adresse de la cellule de mémoire qui contient v dans la cellule de mémoire m.

Notez que le nom < nom> n'apparaît pas dans cette liste.