J'ai essayé l'expression des nombres naturels et le traitement arithmétique uniquement avec le traitement de liste

Les résultats des différentes définitions de la version Scheme sont les suivants.

guile> l2
(a a)
guile> l3
(a a a)
guile> (l+ l2 l3)
(a a a a a)
guile> (l* (l+ l2 l3) (l- (l* l2 l3) l2))
(a a a a a a a a a a a a a a a a a a a a)
guile> (l= (l+ l2 l3) l5)
#t
guile> (l< l5 (l+ l1 l3))
#f

Contexte

Mon article de série "Exemple d'implémentation de système de traitement LISP simple (version ◯◯)" est [Définition du système de traitement LISP primitif](http: // www -Implémentons la version Common Lisp ("jmc.lisp") de -formal.stanford.edu/jmc/recursive/recursive.html dans chaque langage de programmation. Par conséquent, il a été initialement configuré comme un [évaluateur supercirculaire] auto-descriptible (https://en.wikipedia.org/wiki/Meta-circular_evaluator), et bien que ce soit l'ensemble minimum de spécifications linguistiques, c'est une [liste associative]. LISP qui peut normalement décrire les procédures récursives qui traitent (https://ja.wikipedia.org/wiki/%E9%80%A3%E6%83%B3%E9%85%8D%E5%88%97) C'est un système de traitement.

Cependant, pour cette raison, il ne peut pas gérer les valeurs numériques et les opérations. Il existe également une situation dans laquelle Numéro d'église ne peut pas être implémenté en raison de la portée dynamique. Il est très facile d'incorporer l'arithmétique entière et la portée lexicale (fonction plus proche) dans le système de traitement, mais le but des articles de la série ci-dessus est "Abaissons le premier seuil d'implémentation du système de traitement du langage", et l'expansion des fonctions est la suivante. Dans le cadre de, j'aimerais que vous l'essayiez vous-même. Cependant, j'aimerais essayer le calcul numérique avec les spécifications actuelles. Je voudrais montrer le calcul du nombre de Fibonacci et le problème FizzBuzz comme exemple de code.

Quand je cherchais sur le Web en y réfléchissant, "Pure LISP devrait être exprimé dans une liste. », Mais je n'ai pas trouvé d'exemple que j'ai réellement essayé, donc je n'ai pas d'autre choix que d'organiser les spécifications d'implémentation en fonction du nombre d'éléments dans Scheme, puis de les réécrire dans« jmc.lisp »et d'autres langages. Voyons voir ...

Version du schéma

L'exemple de mise en œuvre est le suivant. Puisqu'il est censé être réécrit dans l'ensemble minimum de "jmc.lisp" et d'autres langages, il est décrit avec les fonctions et la syntaxe minimales. ~~ Buchake, l + est ʻappend`. ~~

listcalc.scm

;;;; +, -, *, =, < for list numbers
(define l+  (lambda (x y)    (cond ((null? x) y)  (else (cons (car x) (l+ (cdr x) y))))))
(define l-  (lambda (x y)    (cond ((null? y) x)  (else (l- (cdr x) (cdr y))))))
(define l*_ (lambda (x y tx) (cond ((null? y) x)  (else (l*_ (l+ x tx) (cdr y) tx)))))
(define l*  (lambda (x y)    (cond ((null? y) l1) (else (l*_ x (cdr y) x)))))

(define l=
  (lambda (x y)
    (cond ((and (null? x) (null? y)) #t)
          ((and (not (null? x)) (null? y)) #f)
          ((and (null? x) (not (null? y))) #f)
          (else (l= (cdr x) (cdr y))))))
(define l<
  (lambda (x y)
    (cond ((and (null? x) (null? y)) #f)
          ((and (not (null? x)) (null? y)) #f)
          ((and (null? x) (not (null? y))) #t)
          (else (l< (cdr x) (cdr y))))))

;;;; utility numbers
(define l0 '())
(define l1 '(a))
(define l2 '(a a))
(define l3 '(a a a))
(define l4 '(a a a a))
(define l5 '(a a a a a))

Voici un exemple d'exécution du calcul du nombre de Fibonacci. Confirmé avec GNU Guile 3.0.

$ guile
guile> (load "./listcalc.scm")
guile> (define fib
...      (lambda (x)
...        (cond ((l= x l0) l0)
...              ((l= x l1) l1)
...              (else (l+ (fib (l- x l1))
...                        (fib (l- x l2)))))))
guile> (fib (l* l2 l5))
(a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a)
guile> (length (l* l2 l5))
10
guile> (length (fib (l* l2 l5)))
55

Ensuite, le problème FizzBuzz.

guile> (define ldiv? (lambda (x y) (cond ((null? x) #t) ((l< x y) #f) (else (ldiv? (l- x y) y)))))
guile> (define FizzBuzz
...      (lambda (x n r)
...        (cond ((l< n x) (reverse r))
...              ((and (ldiv? x l3) (ldiv? x l5))
...               (FizzBuzz (l+ x l1) n (cons 'FizzBuzz r)))
...              ((ldiv? x l3)
...               (FizzBuzz (l+ x l1) n (cons 'Fizz r)))
...              ((ldiv? x l5)
...               (FizzBuzz (l+ x l1) n (cons 'Buzz r)))
...              (else
...               (FizzBuzz (l+ x l1) n (cons x r))))))
guile> (FizzBuzz l1 (l* (l* l2 l5) l5) '())
((a) (a a) Fizz (a a a a) Buzz Fizz (a a a a a a a) (a a a a a a a a) Fizz Buzz (a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a) (a a a a a a a a a a a a a a) FizzBuzz (a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a) Buzz Fizz (a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a) Fizz Buzz (a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) FizzBuzz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Buzz Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz Buzz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) FizzBuzz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Buzz)
guile> (length (l* (l* l2 l5) l5))
50
guile> (map (lambda (x) (cond ((list? x) (length x)) (else x)))
...         (FizzBuzz l1 (l* (l* l2 l5) l5) '()))
(1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz)

Version "jmc.lisp"

Pour le moment, vérifiez l'exécution avec la version JavaScript (Node.js 10.21). Tout d'abord, le calcul du nombre de Fibonacci.

$ nodejs
> .load jmclisp.js
(Affichage lorsque le fichier de lecture est coupé)
> s_rep(" \
... ((lambda (and_ not_ null_    \
.....           l+ l- l*_ l* l= l< \
.....           l0 l1 l2 l3 l4 l5  \
.....           fib)               \
.....    (fib (l* l5 l2)))         \
..... '(lambda (x y) (cond (x (cond (y 't) ('t nil))) ('t nil)))              \
..... '(lambda (x) (cond (x nil) ('t 't)))                                    \
..... '(lambda (x) (eq x '()))                                                \
..... '(lambda (x y) (cond ((null_ x) y) ('t (cons (car x) (l+ (cdr x) y))))) \
..... '(lambda (x y) (cond ((null_ y) x) ('t (l- (cdr x) (cdr y)))))          \
..... '(lambda (x y tx) (cond ((null_ y) x) ('t (l*_ (l+ x tx) (cdr y) tx)))) \
..... '(lambda (x y) (cond ((null_ y) l1) ('t (l*_ x (cdr y) x))))            \
..... '(lambda (x y)                                   \
.......    (cond ((and_ (null_ x) (null_ y)) 't)         \
.........          ((and_ (not_ (null_ x)) (null_ y)) nil) \
.........          ((and_ (null_ x) (not_ (null_ y))) nil) \
.........          ('t (l= (cdr x) (cdr y)))))             \
..... '(lambda (x y)                                   \
.......    (cond ((and_ (null_ x) (null_ y)) nil)        \
.........          ((and_ (not_ (null_ x)) (null_ y)) nil) \
.........          ((and_ (null_ x) (not_ (null_ y))) 't)  \
.........          ('t (l< (cdr x) (cdr y)))))             \
..... '() '(a) '(a a) '(a a a) '(a a a a) '(a a a a a) \
..... '(lambda (x)                         \
.......    (cond ((l= x l0) l0)              \
.........          ((l= x l1) l1)              \
.........          ('t (l+ (fib (l- x l1))     \
...........                  (fib (l- x l2)))))) \
..... )")
'(a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a)'

Ensuite, le problème FizzBuzz.

> s_rep(" \
... ((lambda (and_ not_ null_ reverse_       \
.....           l+ l- l*_ l* l= l<             \
.....           l0 l1 l2 l3 l4 l5              \
.....           ldiv FizzBuzz)                 \
.....    (FizzBuzz l1 (l* (l* l2 l5) l5) '())) \
..... '(lambda (x y) (cond (x (cond (y 't) ('t nil))) ('t nil))) \
..... '(lambda (x) (cond (x nil) ('t 't)))     \
..... '(lambda (x) (eq x '()))                 \
..... '(lambda (x)                             \
.......    (cond ((null_ x) '())                 \
.........          ('t (l+ (reverse_ (cdr x))      \
...........                  (cons (car x) '())))))  \
..... '(lambda (x y) (cond ((null_ x) y) ('t (cons (car x) (l+ (cdr x) y))))) \
..... '(lambda (x y) (cond ((null_ y) x) ('t (l- (cdr x) (cdr y)))))          \
..... '(lambda (x y tx) (cond ((null_ y) x) ('t (l*_ (l+ x tx) (cdr y) tx)))) \
..... '(lambda (x y) (cond ((null_ y) l1) ('t (l*_ x (cdr y) x))))            \
..... '(lambda (x y)                                   \
.......    (cond ((and_ (null_ x) (null_ y)) 't)         \
.........          ((and_ (not_ (null_ x)) (null_ y)) nil) \
.........          ((and_ (null_ x) (not_ (null_ y))) nil) \
.........          ('t (l= (cdr x) (cdr y)))))             \
..... '(lambda (x y)                                   \
.......    (cond ((and_ (null_ x) (null_ y)) nil)        \
.........          ((and_ (not_ (null_ x)) (null_ y)) nil) \
.........          ((and_ (null_ x) (not_ (null_ y))) 't)  \
.........          ('t (l< (cdr x) (cdr y)))))             \
..... '() '(a) '(a a) '(a a a) '(a a a a) '(a a a a a) \
..... '(lambda (x y)                    \
.......    (cond ((null_ x) 't)           \
.........          ((l< x y) nil)           \
.........          ('t (ldiv (l- x y) y)))) \
..... '(lambda (x n r)                                     \
.......    (cond ((l< n x) (reverse_ r))                     \
.........          ((and_ (ldiv x l3) (ldiv x l5))             \
...........           (FizzBuzz (l+ x l1) n (cons 'FizzBuzz r))) \
.........          ((ldiv x l3)                                \
...........           (FizzBuzz (l+ x l1) n (cons 'Fizz r)))     \
.........          ((ldiv x l5)                                \
...........           (FizzBuzz (l+ x l1) n (cons 'Buzz r)))     \
.........          ('t                                         \
...........           (FizzBuzz (l+ x l1) n (cons x r)))))       \
..... )")
'((a) (a a) Fizz (a a a a) Buzz Fizz (a a a a a a a) (a a a a a a a a) Fizz Buzz (a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a) (a a a a a a a a a a a a a a) FizzBuzz (a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a) Buzz Fizz (a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a) Fizz Buzz (a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) FizzBuzz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Buzz Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz Buzz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) FizzBuzz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Fizz (a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a) Buzz)'

Version Python

Puisqu'il s'agit d'une destination de réécriture, utilisez des expressions spécifiques à Python sans vous en soucier. Cependant, dans le but de cette fois, la génération du générateur et le traitement de calcul numérique ne sont pas effectués («[0] * 3» etc. est NG, «len» est OK, y compris la vérification de fonctionnement).

listcalc.py

# +, -, *, =, < for list numbers
def ladd(x, y): return x + y
def lsub(x, y): return x[len(y):]
def lmul(x, y): return sum([x for i in y], [])
def leql(x, y): return len(x) == len(y)
def lltn(x, y): return len(x) <  len(y)

# utility numbers without arithmetic operations
l0 = []
l1 = [0]
l2 = [0,0]
l3 = [0,0,0]
l4 = [0,0,0,0]
l5 = [0,0,0,0,0]

Voici un exemple d'exécution du calcul du nombre de Fibonacci.

$ python3 -i listcalc.py
>>> def fib(x):
...     if   leql(x, l0): return l0
...     elif leql(x, l1): return l1
...     else:
...         return ladd(fib(lsub(x, l1)),
...                     fib(lsub(x, l2)))
...
>>> fib(lmul(l2, l5))
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> len(lmul(l2, l5))
10
>>> len(fib(lmul(l2, l5)))
55

Ensuite, le problème FizzBuzz.

>>> def ldiv(x, y):
...     if    not x:      return True
...     elif  lltn(x, y): return False
...     else: return ldiv(lsub(x, y), y)
...
>>> def FizzBuzz(x, n, r):
...     if lltn(n, x): return r
...     elif ldiv(x, l3) and ldiv(x, l5):
...         return FizzBuzz(ladd(x, l1), n, r + ['FizzBuzz'])
...     elif ldiv(x, l3):
...         return FizzBuzz(ladd(x, l1), n, r + ['Fizz'])
...     elif ldiv(x, l5):
...         return FizzBuzz(ladd(x, l1), n, r + ['Buzz'])
...     else:
...         return FizzBuzz(ladd(x, l1), n, r + [x])
...
>>> FizzBuzz(l1, lmul(lmul(l2, l5), l5), [])
[[0], [0, 0], 'Fizz', [0, 0, 0, 0], 'Buzz', 'Fizz', [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', 'Buzz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'FizzBuzz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Buzz', 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', 'Buzz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'FizzBuzz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Buzz', 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', 'Buzz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'FizzBuzz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Fizz', [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 'Buzz']
>>> [len(x) if isinstance(x, list) else x for x in FizzBuzz(l1, lmul(lmul(l2, l5), l5), [])]
[1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz', 16, 17, 'Fizz', 19, 'Buzz', 'Fizz', 22, 23, 'Fizz', 'Buzz', 26, 'Fizz', 28, 29, 'FizzBuzz', 31, 32, 'Fizz', 34, 'Buzz', 'Fizz', 37, 38, 'Fizz', 'Buzz', 41, 'Fizz', 43, 44, 'FizzBuzz', 46, 47, 'Fizz', 49, 'Buzz']

Remarques

Informations complémentaires sur l'article

• Je me demande si le problème FizzBuzz était excessif ... Mais c'est un exemple de programme standard.

Journal des modifications

• 20/09/2020: Ajouté car j'ai oublié de publier la définition de la fonction de la version Python du problème FizzBuzz.
• 18/09/2020: Ajout de la version Python
• 2020-09-18: Première édition publiée (version Scheme, version "jmc.lisp")