This article implements minimal S-expression input / output and list processing in various programming languages, and then John McCarthy's Primitive LISP Interpreter Description. /recursive/recursive.html) implemented by Paul Graham in Common Lisp "McCarthy's Original Lisp" (jmc.lisp) for each language This is a collection of links and common explanations of description examples that have been ported and checked for operation.
jmc.lisp)jmc.lisp with jmc.lisp)In addition, there is also an article that summarizes an example that implements only basic list processing and a simple parser of description using multiple types of parentheses, and it may be incorporated by excerpting or modifying from this description.
This article is newer and organized little by little, but there may be some inconsistencies with each linked article, or duplicate descriptions and explanations. We would appreciate your understanding.
Since the beginning of development, LISP-based languages have been implemented as a meta-circular evaluator, in which LISP itself describes its LISP processing system. Such an implementation is possible if it is a LISP processing system with the minimum functions, and the mechanism of the evaluator is very simple. In addition to McCarthy's Original Lisp, [SICP 4.1](https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/ Many description examples are available on the Web, such as book-ZH-26.html).
By referring to these, the same LISP processing system that has the properties of a hypercircular evaluator can be easily implemented in programming languages other than the LISP system, and ** is ideal for getting started with language processing system implementation ** ... It should be, but if it is a LISP processing system, it is equipped as standard with "S-expression" input / output processing that defines phrases and syntax, and basic list processing based on S-expression (car, cdr, cons, eq, eq, The implementation of atom) takes an overwhelming amount of time and effort for each development language, which is a threshold.
Therefore, ** simple S-expression input / output and basic list processing implementation example is created separately in each programming language **, and "McCarthy's Original Lisp" is possible. The purpose of each implementation example this time is to lower the initial threshold of language processing system implementation by porting and checking the operation as it is.
As shown in the following sample, there is no naming or function definition description method, and only one grouped S-expression is processed. However, because it is a dynamic scope, a recursive function is defined using a lambda expression. It can also be used (instead of Scheme's letrec or Common Lisp's labels).
(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)
The implementation contents of the evaluator body are as follows.
quote (') should be used for variable values.quote, cond and lambda can be used as syntaxcons`` car cdr ʻeq ʻatom (create cons cell internally)t (true) and nil (false) = empty list (= NULL equivalent)caar and ʻassoc` exclusively for evaluator implementationThe configuration of S-expression input / output and list processing implementation is as follows.
cons`` car cdr ʻeq ʻatom( ) ' as the lexical and spaces as the delimiter( ) bundles with cons,' inserts (quote ...), . generates cons cellsThe processing contents of s_eval are itemized as follows. In addition, unlike the original "jmc.lisp", the label function is omitted.
has a list structure and the first element ʻe1 does not have a list structure, the following processing is performed. is quote, the second element of ʻe is returned as it is. is ʻatom ʻeq car`` cdr cons`, the function is applied after evaluating the argument elements, and the result is returned.iscond, pass a list of conditional expressions and processing to ʻevcon and return the result. is regarded as a bound variable of the lambda expression, the corresponding lambda expression is obtained from the environment variable, replaced as the first element of ʻe, and the evaluation result is returned.is also a list structure and the first element islambda`, it is regarded as the value application of the lambda expression and the following processing is performed.has a configuration other than the above,()` is returned as an error.The point is to apply the value of a lambda expression after binding the lambda expression to the argument of another lambda expression, for example.
(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)
Is it a process that is executed like this? By giving a name to the lambda expression in the environment variable, you can define a recursive process that calls itself by that name.
There is only one environment variable, even though it has arguments. Therefore, it becomes a dynamic scope, but this time the evaluator considers an S expression with only a lambda expression as an error (rather, it does not return the value other than the boolean value and quoted description as it is), and the lambda expression You cannot process a lambda expression that describes a lambda expression as the processing body, that is, that returns a lambda expression. As a higher-order function function, it is equivalent to a so-called second-class object.
As a matter of fact, like a boolean value, if it is only a lambda expression, it can be returned as it is, but it must be a lexical scope that implements a closure function that holds local environment variables in the lambda expression. ， The problem of name collision (funarg) occurs. And since the value of a local environment variable in another lambda expression cannot be applied in lexical scope, for recursive processing definition, a syntax to add a variable binding directly to a global environment variable or a fixed point like a Y combinator. You will need a combinator.
In addition, although it is a simple processing system, it cannot be implemented without utilizing various functions of the host language. Therefore, appropriate type and scale as a subject for learning the language in earnest There is also (: //pico.vub.ac.be/mc/mcexplanation.html). For the time being, I found out all the strange quirks of Haskell's wrist monads (eh).
Based on the above, it is a good language processing system even though it has the minimum configuration, so it is good to show that the language can be used as it is by rewriting and enhancing the functions with reference to this content. I wonder if there is any. For example, if a person in another field thinks about changing to a programming job, an interview
Interviewer "The resume says that you can speak ◯◯ language. How well have you learned it?" You "Well, is it just an implementation of a very simple language processing system?" Interviewer "What is the specification of the implementation language? (Is it a calculator program copying sutra using the parser library?)" You "Well, at least can you define a recursive procedure?" Interviewer "!?" You "No, it was a little difficult because I didn't use the library for lexical analysis and abstract syntax tree generation." Interviewer "!?"
It's just right for ~~ to get it right ~~. That's not a lie. Eh, am I? I'm in a position to say, "It's natural to be able to do it in any language, rather it takes too much time and waste, and there is no error checking." Yes.
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) ;The function name passed as an argument does not need to be quoted
=> (10 20)
((lambda (f x y) (f x (f y '())))
(lambda (x y) (cons x (cons y '()))) ;You don't even have to quote the lambda expression passed as an argument
'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 ;Alphabet display as a symbol is all uppercase
((lambda (f x y) (funcall f x (funcall f y '()))) 'cons '10 '20) ;The function passed as an argument is executed using funcall
=> (10 20)
((lambda (f x y) (funcall f x (funcall f y '()))) ;Lambda expression passed as an argument is executed using funcall
(lambda (x y) (cons x (cons y '()))) ;lambda expressions don't need to be quoted
'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