[Link article to other language version] Implementation example of simple LISP processing system [Summary of each language version]
This article is an implementation example of a simple LISP processing system ("McCarthy's Original Lisp") using an excerpt / modification of the Ruby version of the following my article. It is a summary.
In the case of implementing a LISP processing system with the minimum functions, it is very easy to implement the eval, which is the main body, but rather, S-expression input / output and list processing implementation that perform lexical / parsing are developed. It is summarized for those who have a lot of trouble for each language and it is a threshold.
The execution example is as follows. Confirmed with 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)"
The implementation contents are as follows.
quote (') should be used for variable values.quote, cond and lambda can be used as syntax ʻeq cons`` car cdr (create cons cell internally)t (true) and nil (false) = empty listFor more information on "McCarthy's Original Lisp", see Summary Article. Since it is a dynamic scope, lambda expressions are used instead of letrec (Scheme) and labels (Common Lisp) in the execution example.
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
List processing: cons`` car cdr ʻeq ʻatom
Excerpt from previous article.
S-expression input: s_read
From Previous article, change the lexical analysis part to () and ' identification (s_lex), and change the abstract syntax tree generation part Changed to generate a syntax tree by cons cell with the list processing function while supporting dot pairs and quote symbols (s_syn), and defined the S-expression input function s_read that puts them together.
S-expression output: s_string
Newly created S-expression output section. Internally, the empty list that is nil is set to output(), and the boolean value is set to output t nil.
Evaluator: s_eval + utility function
Create s_eval and utility functions based on "McCarthy's Original Lisp".
REP (no Loop)：s_rep
Define s_rep which is a collection of s_read → s_eval → s_string.
then and ʻendare increased compared to the Python version? ~~ In response to the comments, I deleted almost unnecessary `` return`` and somethen`, and it was about 60 lines / 1560 bytes. Rather, it is smaller than the Python version.return etc. from the source code (from comments)Recommended Posts