[Lien de l'article vers une autre version linguistique] Exemple d'implémentation d'un système de traitement LISP simple [Résumé de chaque version linguistique]
Cet article est un exemple d'implémentation d'un système de traitement LISP simple ("McCarthy's Original Lisp") qui utilise un extrait et une modification de la version Ruby de mon article suivant. C'est un résumé.
Dans le cas de la mise en œuvre du système de traitement LISP avec les fonctions minimales, il est très facile de mettre en œuvre l'évaluateur (eval), qui est le corps principal. Il est résumé pour ceux qui ont beaucoup de mal pour chaque langue et c'est un seuil.
L'exemple d'exécution est le suivant. Confirmé avec Ruby 2.5.5.
$ irb --simple-prompt
>> load "jmclisp.rb"
=> true
>> s_rep("(car (cdr '(10 20 30)))")
=> "20"
>> s_rep(gets.chomp)
((lambda (x) (car (cdr x))) '(abc def ghi))
=> "def"
>> s_rep("((lambda (f x y) (f x (f y '()))) 'cons '10 '20)")
=> "(10 20)"
>> s_rep("((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)")
=> "(10 (20 ()))"
>> s_rep("((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 est le suivant.
quote (` ``) doit être utilisé pour les valeurs de variable.quote, cond et lambda peuvent être utilisés comme syntaxe ʻeq cons`` car`` cdr (créer une cellule contre en interne)t (true) et nil (false) = liste videPour plus de détails sur «McCarthy's Original Lisp», reportez-vous à Résumé de l'article. Puisqu'il s'agit d'une portée dynamique, l'expression lambda est utilisée à la place de letrec (Scheme) et labels (Common Lisp) dans l'exemple d'exécution.
jmclisp.rb
####
#### JMC Lisp: defined in McCarthy's 1960 paper,
#### with S-expression input/output and basic list processing
####
#### basic list processing: cons, car, cdr, eq, atom
def cons(x, y) [x, y].freeze end
def car(s) s[0] end
def cdr(s) s[1] end
def eq(s1, s2) s1 == s2 end
def atom(s) s.is_a?(String) || eq(s, nil) || eq(s, true) || eq(s, false) end
#### S-expression input: s_read
def s_lex(s)
for p in ['(',')','\''] do
s = s.gsub(p, " #{p} ")
end
s.split
end
def s_syn(s)
def quote(x, s)
if s.length != 0 && s[-1] == '\'' then
s.delete_at(-1)
cons("quote", cons(x, nil))
else x
end
end
t = s.delete_at(-1)
if t == ')' then
r = nil
while s[-1] != '(' do
if s[-1] == '.' then
s.delete_at(-1)
r = cons(s_syn(s), car(r))
else
r = cons(s_syn(s), r)
end
end
s.delete_at(-1)
quote(r, s)
else
quote(t, s)
end
end
def s_read(s) s_syn(s_lex(s)) end
#### S-expression output: s_string
def s_strcons(s)
sa_r = s_string(car(s))
sd = cdr(s)
if eq(sd, nil) then sa_r
elsif atom(sd) then "#{sa_r} . #{sd}"
else "#{sa_r} #{s_strcons(sd)}"
end
end
def s_string(s)
if eq(s, nil) then "()"
elsif eq(s, true) then "t"
elsif eq(s, false) then "nil"
elsif atom(s) then s
else "(#{s_strcons(s)})"
end
end
#### JMC Lisp evaluator: s_eval
def caar(x) car(car(x)) end
def cadr(x) car(cdr(x)) end
def cadar(x) car(cdr(car(x))) end
def caddr(x) car(cdr(cdr(x))) end
def caddar(x) car(cdr(cdr(car(x)))) end
def s_null(x) eq(x, nil) end
def s_append(x, y)
if s_null(x) then y
else cons(car(x), s_append(cdr(x), y))
end
end
def s_list(x, y) cons(x, cons(y, nil)) end
def s_pair(x, y)
if s_null(x) and s_null(y) then nil
elsif (not atom(x)) and (not atom(y))
cons(s_list(car(x), car(y)), s_pair(cdr(x), cdr(y)))
else nil
end
end
def s_assoc(x, y)
if eq(caar(y), x) then cadar(y)
else s_assoc(x, cdr(y))
end
end
def s_eval(e, a)
if eq(e, "t") then true
elsif eq(e, "nil") then false
elsif atom(e) then s_assoc(e, a)
elsif atom(car(e))
if eq(car(e), "quote") then cadr(e)
elsif eq(car(e), "atom") then atom(s_eval(cadr(e), a))
elsif eq(car(e), "eq") then eq( s_eval(cadr(e), a), s_eval(caddr(e), a))
elsif eq(car(e), "car") then car( s_eval(cadr(e), a))
elsif eq(car(e), "cdr") then cdr( s_eval(cadr(e), a))
elsif eq(car(e), "cons") then cons(s_eval(cadr(e), a), s_eval(caddr(e), a))
elsif eq(car(e), "cond") then evcon(cdr(e), a)
else s_eval(cons(s_assoc(car(e), a), cdr(e)), a)
end
elsif eq(caar(e), "lambda")
s_eval(caddar(e), s_append(s_pair(cadar(e), evlis(cdr(e), a)), a))
else print("Error")
end
end
def evcon(c, a)
if s_eval(caar(c), a) then s_eval(cadar(c), a)
else evcon(cdr(c), a)
end
end
def evlis(m, a)
if s_null(m) then nil
else cons(s_eval(car(m), a), evlis(cdr(m), a))
end
end
#### REP (no Loop): s_rep
def s_rep(e) s_string(s_eval(s_read(e), s_read("()"))) end
Traitement de la liste: cons`` car`` cdr ʻeq ʻatom
Extrait de Article précédent.
Entrée d'expression S: s_read
À partir de Article précédent, changez la partie d'analyse de phrase en () et `` identification ( s_lex), et changez la partie de génération d'arbre de syntaxe abstraite. Changé pour générer un arbre de syntaxe par contre cellule avec fonction de traitement de liste tout en prenant en charge la paire de points et le symbole de guillemet (s_syn), et défini la fonction d'entrée d'expression Ss_read` qui les résume.
Sortie de l'expression S: s_string
La section de sortie de type S est nouvellement créée. En interne, une liste vide qui est "nil" est définie sur output(), et une valeur booléenne est définie sur output t`` nil.
Evaluateur: s_eval + fonction utilitaire
Création de la fonction s_eval et de la fonction utilitaire basée sur " McCarthy's Original Lisp ".
REP (no Loop)：s_rep
Définissez s_rep qui est une collection de s_read → s_eval → s_string.
Recommended Posts