Suite à l'organisation de mon article "Résumé de l'implémentation de l'interpréteur 7 lignes", j'ai pensé qu'il ne serait compatible avec rien d'autre que Scheme et Python. Ce n'est pas la partie implémentation de l'entrée? »→« De plus, s'il n'y a pas de norme pour le contenu de traitement de la liste, la politique de mise en œuvre sera différente pour chaque langue », donc pour le moment« cons` `car cdr ʻatom`` list peut être utilisé" Dès que j'ai décidé de résumer les exemples de description à faire en premier. Est-il proche de l'implémentation de la fonction pure LISP sur la langue cible?

Pour la version Python, un exemple de description d'entrée / sortie de type S utilisant ceci est également publié (peut être déplacé vers un autre article lorsque d'autres versions linguistiques sont disponibles).

spécification

Définir paires de points (contre-cellules)
Tous les atomes sont des chaînes, la liste vide est NULL
Implémentation de cons car cdr`
Implémentation de ʻatom` pour déterminer si c'est un atome
Implémentation de list pour générer une liste unidirectionnelle à partir d'une liste de chaînes

Python（CPython 3.7.3） Les paires de points sont définies par des tuples d'éléments de paire (car nous voulons qu'ils soient invariants). Utilisez None pour la liste vide 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:]))

L'exemple d'utilisation est le suivant.

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'

(Exemple de description d'entrée / sortie de type S utilisant la définition ci-dessus)

#### 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))'

Langage C (gcc 8.3.0)

Pour l'implémentation de ʻatom, définissez d'abord une structure node_tqui peut gérer à la fois des chaînes de caractères et des structures point à pointeur, puis utilisez-la pour définir une structure point à point. La liste vide NULL utilise le pointeur NULL.

#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);
}

L'exemple d'utilisation est le suivant.

#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） Pour référence seulement. La paire de points est réalisée par fermeture. Défini par le nom s_cons`` s_car`` s_cdr`` s_atom s_list pour le distinguer de l'original. Utilisez NIL pour une liste vide 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)))))

L'exemple d'utilisation est le suivant.

(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） Une paire de points est définie par un tableau à deux éléments (gelé). Utilisez nil pour une liste vide 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

L'exemple d'utilisation est le suivant.

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) Une paire de points est définie par un tableau à deux éléments (gelé). Utilisez null pour une liste vide 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))); }

L'exemple d'utilisation est le suivant.


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'

Remarques

Informations complémentaires sur l'article

Parce qu'il est censé être utilisé comme référence, la vérification des erreurs, la modularisation et le ramasse-miettes sont tous délicieux. Il existe déjà de nombreux analyseurs de type S pratiques.
Avec la version actuelle de list, vous ne pouvez pas créer une" liste de listes "incluant la version Common Lisp ... Si vous utilisez contre, ça va.

modifier l'historique

2020-08-31: Ajout d'un exemple d'implémentation JavaScript
2020-08-30: Exemple d'utilisation unifiée pour l'implémentation de liste associative
2020-08-30: Exemple d'implémentation Ruby ajouté
2020-08-30: Première édition publiée (Python, C, Common Lisp)

[PYTHON] Fonction de traitement de liste (cons, car, cdr, atom, list) Résumé de l'exemple d'implémentation

spécification

(Exemple de description d'entrée / sortie de type S utilisant la définition ci-dessus)

Langage C (gcc 8.3.0)

Remarques

Informations complémentaires sur l'article

modifier l'historique