[Lier l'article à 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") utilisant un extrait / modification de la version Java 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, la mise en œuvre de l'évaluateur (eval), qui est le corps principal, est très facile, mais plutôt l'implémentation du traitement d'entrée / sortie et de liste de type S qui effectue une analyse de phrase / syntaxe est développée. 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 Java 11.0.8.
$ java jmclisp
(car (cdr '(10 20 30)))
20
$ java jmclisp
((lambda (x) (car (cdr x))) '(abc def ghi))
def
$ java jmclisp
((lambda (f x y) (f x (f y '()))) 'cons '10 '20)
(10 20)
$ java jmclisp
((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)
(10 (20 ()))
$ java jmclisp
((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 vide ="nil"Pour 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.java
//
// JMC Lisp: defined in McCarthy's 1960 paper,
// with S-expression input/output and basic list processing
//
import java.util.Scanner;
class pair {
private Object x, y;
public pair(Object car, Object cdr) {
x = car; y = cdr;
}
public Object car() { return x; }
public Object cdr() { return y; }
}
public class jmclisp {
// basic list processing: cons, car, cdr, eq, atom
private static Object cons(Object s1, Object s2) {
return new pair(s1, s2);
}
private static Object car(Object s) { return ((pair)s).car(); }
private static Object cdr(Object s) { return ((pair)s).cdr(); }
private static Boolean eq(Object s1, Object s2) {
if (s1 instanceof String && s2 instanceof String) {
return ((String)s1).equals((String)s2);
} else {
return false;
}
}
private static Boolean atom(Object s) { return (s instanceof String); }
// S-expression output: s_string
private static Object s_strcons(Object s) {
Object sa_r = s_string(car(s));
Object sd = cdr(s);
if (eq(sd, "nil")) { return sa_r; }
else if (atom(sd)) {
return (String)sa_r + " . " + (String)sd;
} else {
return (String)sa_r + " " + (String)s_strcons(sd);
}
}
private static Object s_string(Object s) {
if (eq(s, "nil")) { return "()"; }
else if (atom(s)) { return s; }
else { return "(" + (String)s_strcons(s) + ")"; }
}
// lexical analysis for S-expression: s_lex
private static String[] s_lex(String s) {
return s.replace("(", " ( ")
.replace(")", " ) ")
.replace("'", " ' ")
.trim().split(" +");
}
// abstract syntax tree generator: s_syn
private static int posl;
private static String[] rl;
private static Object quote(Object x) {
if ((posl >= 0) && (rl[posl]).equals("'")) {
posl = posl - 1;
return cons("quote", cons(x, "nil"));
} else {
return x;
}
}
private static Object s_syn() {
String t = rl[posl];
posl = posl - 1;
if (t.equals(")")) {
Object r = (Object)"nil";
while (!((rl[posl]).equals("("))) {
if ((rl[posl]).equals(".")) {
posl = posl - 1;
r = cons(s_syn(), car(r));
} else {
r = cons(s_syn(), r);
}
}
posl = posl - 1;
return quote(r);
} else {
return quote((Object)t);
}
}
// JMC Lisp evaluator: s_eval
private static Object caar(Object x) { return car(car(x)); }
private static Object cadr(Object x) { return car(cdr(x)); }
private static Object cadar(Object x) { return car(cdr(car(x))); }
private static Object caddr(Object x) { return car(cdr(cdr(x))); }
private static Object caddar(Object x) { return car(cdr(cdr(car(x)))); }
private static Boolean s_null(Object x) {
if (eq(x, "nil")) { return true; }
else { return false; }
}
private static Object s_append(Object x, Object y) {
if (s_null(x)) { return y; }
else {
Object r = s_append(cdr(x), y);
return cons(car(x), r);
}
}
private static Object s_list(Object x, Object y) {
return cons(x, cons(y, "nil"));
}
private static Object s_pair(Object x, Object y) {
if (s_null(x) && s_null(y)) {
return "nil";
} else if (!(atom(x)) && !(atom(y))) {
return cons(s_list(car(x), car(y)),
s_pair(cdr(x), cdr(y)));
} else {
return "nil";
}
}
private static Object s_assoc(Object x, Object y) {
if (s_null(y)) { return "nil"; }
else if (eq(caar(y), x)) { return cadar(y); }
else { return s_assoc(x, cdr(y)); }
}
private static Object s_atom(Object s) { return atom(s) ? "t" : "nil"; }
private static Object s_eq(Object s1, Object s2) { return eq(s1, s2) ? "t" : "nil"; }
private static Object s_eval(Object e, Object a) {
if (eq(e, "t")) { return "t"; }
else if (eq(e, "nil")) { return "nil"; }
else if (atom(e)) { return s_assoc(e, a); }
else if (atom(car(e))) {
if (eq(car(e), "quote")) { return cadr(e); }
else if (eq(car(e), "atom")) { return s_atom(s_eval(cadr(e), a)); }
else if (eq(car(e), "eq")) { return s_eq( s_eval(cadr(e), a),
s_eval(caddr(e), a)); }
else if (eq(car(e), "car")) { return car( s_eval(cadr(e), a)); }
else if (eq(car(e), "cdr")) { return cdr( s_eval(cadr(e), a)); }
else if (eq(car(e), "cons")) { return cons( s_eval(cadr(e), a),
s_eval(caddr(e), a)); }
else if (eq(car(e), "cond")) { return evcon(cdr(e), a); }
else { return s_eval(cons(s_assoc(car(e), a), cdr(e)), a); }
} else if (eq(caar(e), "lambda")) {
return s_eval(caddar(e),
s_append(s_pair(cadar(e), evlis(cdr(e), a)), a));
} else {
System.out.println("Error");
return "nil";
}
}
private static Object evcon(Object c, Object a) {
if (eq(s_eval(caar(c), a), "t")) { return s_eval(cadar(c), a); }
else { return evcon(cdr(c), a); }
}
private static Object evlis(Object m, Object a) {
if (s_null(m)) { return "nil"; }
else { return cons(s_eval(car(m), a), evlis(cdr(m), a)); }
}
// REP (no Loop): s_rep
private static void s_rep(String s) {
rl = s_lex(s);
posl = rl.length - 1;
System.out.println(s_string(s_eval(s_syn(), "nil")));
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s = "", i;
do {
i = scan.nextLine();
s = s + i;
} while (!(i.equals("")));
s_rep(s);
}
}
Traitement de la liste: cons`` car`` cdr ʻeq ʻatom, sortie de l'expression S: s_string
Extrait de Article précédent. Conscell est construit en utilisant le type Object.
Entrée d'expression S: s_lex et s_syn
Nouvellement créé. La partie d'analyse de phrase s_lex organise une chaîne de caractères en identifiant () ʻet', et la partie de génération d'arbre de syntaxe abstraite s_syn` prend en charge les parenthèses entre les points imbriqués et les symboles de guillemets, et est une fonction de traitement de liste. Générez un arbre de syntaxe.
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_lex → s_syn → s_eval → s_string. Décrivez également de saisir plusieurs lignes jusqu'à ce qu'une ligne vide soit entrée avec la fonction main pour créer une chaîne de caractères, et passez-la à s_rep.
Recommended Posts