Cet article implémente le traitement minimal d'entrée / sortie d'expression S et de liste dans divers langages de programmation, puis [Description primitive de l'interpréteur LISP] de John McCarthy (http://www-formal.stanford.edu/jmc/jmc). /recursive/recursive.html) implémenté par Paul Graham en Common Lisp "McCarthy's Original Lisp" (jmc.lisp) pour chaque langue Il s'agit d'un ensemble de liens et d'explications courantes d'exemples de description qui ont été portés et vérifiés pour leur fonctionnement.
jmc.lisp)jmc.lisp avec jmc.lisp)En outre, il existe également un article qui résume un exemple qui implémente uniquement un traitement de liste de base et un simple analyseur de description utilisant plusieurs types de parenthèses, et il peut être incorporé en extrayant ou en modifiant cette description.
Cet article est plus récent et organisé petit à petit, mais il peut y avoir des incohérences avec chaque article lié, ou des descriptions et des explications en double. Nous apprécierions votre compréhension.
Depuis le début du développement, le langage LISP a été implémenté comme un évaluateur méta-circulaire, dans lequel le système de traitement LISP est décrit par LISP lui-même. Une telle implémentation est possible s'il s'agit d'un système de traitement LISP avec les fonctions minimales, et le mécanisme de l'évaluateur est très simple. En plus de McCarthy's Original Lisp, [SICP 4.1](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/ De nombreux exemples de description sont disponibles sur le Web, comme book-ZH-26.html).
En faisant référence à ceux-ci, le même système de traitement LISP qui a les propriétés d'un évaluateur hypercirculaire peut être facilement implémenté dans des langages de programmation autres que le système LISP, et ** est idéal pour démarrer avec l'implémentation du système de traitement du langage ** ... Il devrait l'être, mais s'il s'agit d'un système de traitement LISP, il est équipé en standard d'un traitement d'entrée / sortie "S expression" qui définit les phrases et la syntaxe, et d'un traitement de liste de base basé sur l'expression S (car, cdr, cons, eq, eq, L'implémentation d'atome) prend énormément de temps et d'efforts pour chaque langage de développement, ce qui est un seuil.
Par conséquent, ** un simple exemple d'implémentation d'entrée / sortie de type S et de traitement de liste de base est créé séparément dans chaque langage de programmation **, et "McCarthy's Original Lisp" est possible. Le but de chaque exemple d'implémentation est cette fois d'abaisser le seuil initial d'implémentation du système de traitement de langage en portant et en vérifiant l'opération telle qu'elle est.
Comme illustré dans l'exemple suivant, il n'y a pas de méthode de description de dénomination ou de définition de fonction et un seul groupe d'expressions S est traité. Cependant, comme il s'agit d'une étendue dynamique, une fonction récursive est définie à l'aide d'une expression lambda. Il peut également être utilisé (à la place des étiquettes letrec ou Common Lisp` de Scheme).
(car (cdr '(10 20 30)))
=> 20
((lambda (x) (car (cdr x))) '(abc def ghi))
=> def
((lambda (f x y) (f x (f y '()))) 'cons '10 '20)
=> (10 20)
((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)
=> (10 (20 ()))
((lambda (assoc k v) (assoc k v))
'(lambda (k v)
(cond ((eq v '()) nil)
((eq (car (car v)) k)
(car v))
('t (assoc k (cdr v)))))
'Orange
'((Apple . 120) (Orange . 210) (Lemmon . 180)))
=> (Orange . 210)
Le contenu de la mise en œuvre du corps de l'évaluateur est le suivant.
quote (` ``) doit être utilisé pour les valeurs de variable.quote, cond et lambda peuvent être utilisés comme syntaxecons`` car`` cdr ʻeq ʻatom (créer une cellule contre en interne)t (true) et nil (false) = liste vide (= équivalent NULL)caar et ʻassoc` exclusivement pour l'implémentation de l'évaluateurLa configuration de l'implémentation du traitement des entrées / sorties et des listes de type S est la suivante.
cons`` car`` cdr ʻeq ʻatom () `` '' comme phrase et des espaces comme délimiteur.( ) avec cons,`` insère(quote ...), .` génère une cellule contreLe contenu de traitement de s_eval est le suivant. De plus, contrairement à l'original «jmc.lisp», la fonction «label» est omise.
a une structure de liste et que le premier élément ʻe1 n'a pas de structure de liste, le traitement suivant est effectué. est quote, le deuxième élément de ʻe est renvoyé tel quel. est ʻatom ʻeq car cdr cons`, la fonction est appliquée après avoir évalué les éléments d'argument, et le résultat est retourné. est cond, passez une liste d'expressions conditionnelles et de traitement à ʻevcon et renvoyez le résultat. est considéré comme une variable de liaison de l'expression lambda, l'expression lambda correspondante est obtenue à partir de la variable d'environnement, remplacée comme premier élément de ʻe, et le résultat de l'évaluation est renvoyé.a également une structure de liste et que le premier élément estlambda`, il est considéré comme l'application de valeur de l'expression lambda et le traitement suivant est effectué.a une configuration autre que celle ci-dessus,()` est renvoyé comme une erreur.Le but est d'appliquer la valeur de l'expression lambda après avoir lié l'expression lambda à l'argument d'une autre expression lambda, par exemple.
(s_eval '((lambda (f) (f '(a b c))) '(lambda (x) (cdr x))) '()))
=> (s_eval '(f '(a b c)) '((f (lambda (x) (cdr x))) . ()))
=> (s_eval '((lambda (x) (cdr x)) '(a b c)) '((f (lambda (x) (cdr x))) . ()))
=> (s_eval '(cdr x) '((x (a b c)) (f (lambda (x) (cdr x))) . ()))
=> (cdr (s_eval 'x '((x (a b c)) (f (lambda (x) (cdr x))) . ())))
=> (cdr '(a b c))
=> (b c)
Est-ce un processus qui est exécuté comme ça? En donnant un nom à l'expression lambda dans la variable d'environnement, vous pouvez définir un processus récursif qui s'appelle lui-même par ce nom.
Il n'y a qu'une seule variable d'environnement, même si l'argument tourne. Par conséquent, cela devient une portée dynamique, mais cette fois, l'évaluateur considère une expression S avec uniquement une expression lambda comme une erreur (plutôt, elle ne renvoie pas telle quelle sous forme de valeur autre qu'une valeur booléenne et une description entre guillemets), et il s'agit d'une expression lambda. Une expression lambda qui décrit une expression lambda en tant que corps de traitement, c'est-à-dire une expression lambda qui renvoie une expression lambda ne peut pas être traitée. En tant que fonction de fonction d'ordre supérieur, elle équivaut à ce que l'on appelle un objet de seconde classe.
En fait, il n'est pas impossible de renvoyer l'expression lambda telle quelle, comme la valeur booléenne, mais il doit s'agir d'une portée lexicale qui contient la variable d'environnement locale dans l'expression lambda et implémente la fonction de fermeture. ， Le problème du conflit de nom (funarg) se produit. Et puisque la valeur de la variable d'environnement locale dans une autre expression lambda ne peut pas être appliquée dans la portée lexicale, pour la définition de traitement récursif, la syntaxe pour ajouter la variable liant directement à la variable d'environnement globale et au point d'immobilité tel que le combinateur Y. Vous aurez besoin d'un combinateur.
De plus, bien qu'il s'agisse d'un système de traitement simple, il ne peut pas être implémenté sans utiliser diverses fonctions de la langue hôte. Par conséquent, type et échelle appropriés en tant que matière pour apprendre sérieusement la langue //pico.vub.ac.be/mc/mcexplanation.html). Pour le moment, j'ai découvert toutes les étranges habitudes de la monade de poignet de Haskell (hein).
Sur la base de ce qui précède, c'est un bon système de traitement du langage même s'il a la configuration minimale, il est donc bon de montrer que le langage peut être utilisé tel quel en réécrivant et en améliorant les fonctions en référence à ce contenu. Je me demande s'il y en a. Par exemple, lorsqu'une personne dans un autre domaine envisage de passer à un emploi de programmation, un entretien
Interviewer "Le CV dit que vous pouvez parler la langue ◯◯. Dans quelle mesure l'avez-vous bien apprise?" Vous "Eh bien, est-ce juste une simple implémentation d'un système de traitement du langage?" Interviewer "Quelles sont les spécifications du langage d'implémentation? (S'agit-il d'une copie de programme informatique utilisant la bibliothèque d'analyseurs?)" Vous "Eh bien, au moins pouvez-vous définir une procédure récursive?" Intervieweur "!?" Vous "Non, c'était un peu difficile car je n'ai pas utilisé la bibliothèque pour l'analyse de phrases et la génération d'arbres de syntaxe abstraite." Intervieweur "!?"
C'est juste pour ~~ de bien faire les choses ~~. Ce n'est pas un mensonge. Hein, je suis? Je suis en mesure de dire: "Il est naturel de pouvoir le faire dans n'importe quelle langue, cela prend plutôt trop de temps et de perte, et il n'y a pas de vérification des erreurs."
sample.scm
(car (cdr '(10 20 30)))
=> 20
((lambda (x) (car (cdr x))) '(abc def ghi))
=> def
((lambda (f x y) (f x (f y '()))) cons '10 '20) ;Le nom de la fonction passé en argument n'a pas besoin d'être entre guillemets
=> (10 20)
((lambda (f x y) (f x (f y '())))
(lambda (x y) (cons x (cons y '()))) ;L'expression lambda passée en argument n'a pas non plus besoin d'être entre guillemets
'10 '20)
=> (10 (20 ()))
(letrec ((assoc_ (lambda (k v)
(cond ((eq? v '()) '())
((eq? (car (car v)) k)
(car v))
(else (assoc_ k (cdr v)))))))
(assoc_ 'Orange
'((Apple . 120) (Orange . 210) (Lemmon . 180))))
=> (Orange . 210)
sample.lsp
(car (cdr '(10 20 30)))
=> 20
((lambda (x) (car (cdr x))) '(abc def ghi))
=> DEF ;L'affichage de l'alphabet en tant que symbole est entièrement en majuscules
((lambda (f x y) (funcall f x (funcall f y '()))) 'cons '10 '20) ;La fonction passée en argument est exécutée en utilisant funcall
=> (10 20)
((lambda (f x y) (funcall f x (funcall f y '()))) ;L'expression lambda passée en argument est exécutée à l'aide de funcall
(lambda (x y) (cons x (cons y '()))) ;les expressions lambda n'ont pas besoin d'être entre guillemets
'10 '20)
=> (10 (20 NIL))
(labels ((assoc_ (k v)
(cond ((eq v '()) '())
((eq (car (car v)) k)
(car v))
(t (assoc_ k (cdr v))))))
(assoc_ 'Orange
'((Apple . 120) (Orange . 210) (Lemmon . 180))))
=> (ORANGE . 210)
Recommended Posts