Implementation example of simple LISP processing system [Summary of each language version]

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.

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.

Purpose of implementation example

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.

Overview of processing system

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.

The configuration of S-expression input / output and list processing implementation is as follows.

Explanation of the evaluator

The processing contents of s_eval are itemized as follows. In addition, unlike the original "jmc.lisp", the label function is omitted.

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.

Remarks

Supplementary information about the article

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)

Change log

Recommended Posts

Implementation example of simple LISP processing system [Summary of each language version]
Implementation example of simple LISP processing system (Java version)
Implementation example of simple LISP processing system (Ruby version)
[Swift] Simple implementation of UIImageView
Summary of Java language basics
Summary of java error processing
Implementation of asynchronous processing in Tomcat
[Kotlin] Example of processing using Enum