As a result of organizing my article "7-line interpreter implementation summary", I thought that it would not be compatible with anything other than Scheme and Python. This isn't the implementation part of the input? ”→“ Also, if there is no standard for list processing content, the implementation policy will be different for each language ”, and for the time being,“ cons car`` cdr ʻatom`` list` can be used ” As soon as I decided to summarize the description examples to be done first. Is it close to the pure LISP function implementation on the target language?
cons`` car cdrlist to generate a unidirectional list from a string of stringsPython（CPython 3.7.3）
Dot pairs are defined by tuples of pair elements (because we want them to be invariant). Use None for empty list NULL.
#### Cons cells are created by using tuple.
#### All of atoms are string and the null value is None.
def cons(x, y): return (x, y)
def car(s): return s[0]
def cdr(s): return s[1]
def atom(s): return isinstance(s, str) or s == None
def list(ts):
if not ts:
return None
else:
return cons(ts[0], list(ts[1:]))
The usage example is as follows.
def mkassoc(a, b):
if a == None or b == None:
return None
else:
return cons(cons(car(a), car(b)), mkassoc(cdr(a), cdr(b)))
def assoc(k, vs):
if vs == None:
return None
else:
if car(car(vs)) == k:
return car(vs)
else:
return assoc(k, cdr(vs))
>>> vs = mkassoc(list(("hoge", "hage", "hige")), list(("10", "20", "30")))
>>> assoc("hage", vs)
('hage', '20')
>>> car(assoc("hage", vs))
'hage'
>>> cdr(assoc("hage", vs))
'20'
#### Cons cells are created by using tuple.
#### All of atoms are string and the null value is None.
def cons(x, y): return (x, y)
def car(s): return s[0]
def cdr(s): return s[1]
def atom(s): return isinstance(s, str) or s == None
def list(ts):
if not ts:
return None
else:
return cons(ts[0], list(ts[1:]))
#### s_read
# '(a b c)'
# => ['(', 'a', 'b', 'c', ')']
def s_lex(s):
return s.replace('(', ' ( ').replace(')', ' ) ').split()
# ['(', 'a', 'b', 'c', ')']
# => ('a', 'b', 'c')
def s_syn(s):
t = s.pop(0)
if t == '(':
r = []
while s[0] != ')':
r.append(s_syn(s))
s.pop(0)
return tuple(r)
else:
if t == 'None':
return None
else:
return t
# ('a', 'b', 'c')
# => ('a', ('b', ('c', None)))
def s_sem(s):
if atom(s):
return s
elif len(s) == 0:
return None
elif s[0] == '.':
return s_sem(s[1])
else:
return cons(s_sem(s[0]), s_sem(s[1:]))
def s_read(ss): return s_sem(s_syn(s_lex(ss)))
#### s_print
def s_prcons(s):
sa_r = s_print(car(s))
sd = cdr(s)
if sd == None:
return sa_r
elif atom(sd):
return sa_r + ' . ' + sd
else:
return sa_r + ' ' + s_prcons(sd)
def s_print(s):
if atom(s):
return s
elif s == None:
return None
else:
return '(' + s_prcons(s) + ')'
>>> s_print(s_read('((Apple . 100) (Orange . 120) (Lemmon . 250))'))
'((Apple . 100) (Orange . 120) (Lemmon . 250))'
>>> x = s_read('((Apple . 100) (Orange . 120) (Lemmon . 250))')
>>> car(x)
('Apple', '100')
>>> car(car(cdr(x)))
'Orange'
>>> s_print(cdr(x))
'((Orange . 120) (Lemmon . 250))'
For the ʻatom implementation, we first define a node_t structure that can handle both strings and dot-to-pointers, and then use it to define a dot-to-dot structure. Empty list NULL uses a NULL pointer.
#include <stdio.h>
#include <stdlib.h>
/* Cons cells are created by using typedef struct. */
/* All of atoms are char* and the null value is NULL. */
typedef unsigned int value_t;
enum NODE_TAG { NODE_STRG, NODE_CONS };
typedef struct _node_t_ {
value_t value;
enum NODE_TAG tag;
} _node_t, *node_t;
node_t node(value_t value, enum NODE_TAG tag)
{
node_t n = (node_t)malloc(sizeof(_node_t));
n->value = value; n->tag = tag;
return (n);
}
typedef struct _cons_t_ {
node_t x;
node_t y;
} _cons_t, *cons_t;
node_t cons(node_t x, node_t y)
{
cons_t c = (cons_t)malloc(sizeof(_cons_t));
c->x = x; c->y = y;
node_t n = node((value_t)c, NODE_CONS);
return (n);
}
#define str_to_node(s) (node((value_t)(s), NODE_STRG))
#define node_to_str(s) ((char *)(s->value))
#define car(s) (((cons_t)(s->value))->x)
#define cdr(s) (((cons_t)(s->value))->y)
#define atom(s) (s->tag == NODE_STRG)
#define MAXSTR 64
node_t list(const char s[][MAXSTR], const int n)
{
node_t r = str_to_node(NULL);
for (int i = n - 1; i >= 0; i--) {
r = cons(str_to_node(s[i]), r);
}
return (r);
}
The usage example is as follows.
#include <string.h>
node_t mkassoc(node_t a, node_t b)
{
if (node_to_str(a) == NULL || node_to_str(b) == NULL) {
return NULL;
} else {
return cons(cons(car(a), car(b)), mkassoc(cdr(a), cdr(b)));
}
}
node_t assoc(node_t k, node_t vs)
{
if (node_to_str(vs) == NULL) {
return NULL;
} else {
if (strcmp(node_to_str(car(car(vs))), node_to_str(k)) == 0) {
return car(vs);
} else {
return assoc(k, cdr(vs));
}
}
}
int main(void)
{
const char s1[][MAXSTR] = { "hoge", "hage", "hige" };
const char s2[][MAXSTR] = { "10", "20", "30" };
node_t vs = mkassoc(list(s1, 3), list(s2, 3));
node_t k = str_to_node("hage");
node_t r = assoc(k, vs);
printf("car(assoc(\"hage\", vs)) = %s\n", node_to_str(car(r)));
printf("cdr(assoc(\"hage\", vs)) = %s\n", node_to_str(cdr(r)));
free(vs);
free(k);
free(r);
return (0);
}
car(assoc("hage", vs)) = hage
cdr(assoc("hage", vs)) = 20
Common Lisp（SBCL 1.4.16）
For reference only. Dot pairs are realized by closures. Defined by the name s_cons`` s_car s_cdr`` s_atom s_list to distinguish it from the original. Use NIL for empty list NULL.
;;;; Cons cells are created by using lambda closure.
;;;; All of atoms are string and the null value is NIL.
(defun s_cons (x y) (lambda (f) (funcall f x y)))
(defun s_car (c) (funcall c (lambda (x y) x)))
(defun s_cdr (c) (funcall c (lambda (x y) y)))
(defun s_atom (s) (and (not (functionp s)) (not (equal s NIL))))
(defun s_list (s) (if (null s) NIL (s_cons (car s) (s_list (cdr s)))))
The usage example is as follows.
(defun s_mkassoc (a b)
(if (or (equal a NIL) (equal b NIL)) NIL
(s_cons (s_cons (s_car a) (s_car b))
(s_mkassoc (s_cdr a) (s_cdr b)))))
(defun s_assoc (k vs)
(if (equal vs NIL) NIL
(if (equal (s_car (s_car vs)) k)
(s_car vs)
(s_assoc k (s_cdr vs)))))
* (defparameter vs
(s_mkassoc (s_list '("hoge" "hage" "hige")) (s_list '("10" "20" "30"))))
VS
* (s_assoc "hage" vs)
#<CLOSURE (LAMBDA (F) :IN S_CONS) {50F3E645}>
* (s_car (s_assoc "hage" vs))
"hage"
* (s_cdr (s_assoc "hage" vs))
"20"
Ruby（CRuby 2.5.5）
A dot pair is defined by a two-element (frozen) array. Use nil for empty list NULL.
#### Cons cells are created by using Array.
#### All of atoms are string and the null value is nil.
def cons(x, y) [x, y].freeze end
def car(s) s[0] end
def cdr(s) s[1] end
def atom(s) s.is_a?(String) || s == nil end
def list(s) s.size == 0 ? nil : cons(s[0], list(s[1..-1])) end
The usage example is as follows.
def mkassoc(a, b)
if a == nil || b == nil then
return nil
else
return cons(cons(car(a), car(b)), mkassoc(cdr(a), cdr(b)))
end
end
def assoc(k, vs)
if vs == nil then
return nil
else
if car(car(vs)) == k then
return car(vs)
else
return assoc(k, cdr(vs))
end
end
end
>> vs = mkassoc(list(["hoge", "hage", "hige"]), list(["10", "20", "30"]))
=> [["hoge", "10"], [["hage", "20"], [["hige", "30"], nil]]]
>> assoc("hage", vs)
=> ["hage", "20"]
>> car(assoc("hage", vs))
=> "hage"
>> cdr(assoc("hage", vs))
=> "20"
JavaScript (Node.js 10.21)
A dot pair is defined by a two-element (frozen) array. Use null for empty list NULL.
//// Cons cells are created by using Array.
//// All of atoms are string and the null value is null.
function cons(x, y) { return Object.freeze([x, y]); }
function car(s) { return s[0]; }
function cdr(s) { return s[1]; }
function atom(s) { return typeof s == 'string' || s == null; }
function list(s) { return s.length == 0 ? null : cons(s[0], list(s.slice(1))); }
The usage example is as follows.
function mkassoc(a, b) {
return a == null || b == null
? null
: cons(cons(car(a), car(b)), mkassoc(cdr(a), cdr(b)));
}
function assoc(k, vs) {
if (vs == null) {
return null;
} else {
if (car(car(vs)) == k) {
return car(vs);
} else {
return assoc(k, cdr(vs));
}
}
}
> vs = mkassoc(list(["hoge", "hage", "hige"]), list(["10", "20", "30"]))
[ [ 'hoge', '10' ], [ [ 'hage', '20' ], [ [Array], null ] ] ]
> assoc("hage", vs)
[ 'hage', '20' ]
> car(assoc("hage", vs))
'hage'
> cdr(assoc("hage", vs))
'20'
list, you can't create a" list of lists "including the Common Lisp version ... If you use cons, it's okay.