The results of various definitions for the Scheme version are as follows.
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
My series article "Simple LISP processing system implementation example (◯◯ version)" is [Primitive LISP processing system definition](http: // www -Let's implement the Common Lisp version ("jmc.lisp") of -formal.stanford.edu/jmc/recursive/recursive.html in each programming language. So, it was originally configured as a self-describable super-circular evaluator, and despite the minimum set of language specifications, [associative list] LISP that can normally describe recursive procedures that process (https://ja.wikipedia.org/wiki/%E9%80%A3%E6%83%B3%E9%85%8D%E5%88%97) It is a processing system.
However, for that reason, it cannot handle numerical values and operations. Due to the dynamic scope, Church number cannot be implemented. Incorporating integer arithmetic and lexical scope (closure function) into the processing system is very easy, but the purpose of the above series articles is "Let's lower the first threshold of language processing system implementation", and the function expansion is next. The intention is that you should try it yourself as a step in. However, I would like to do numerical operations with the current specifications. I would like to show the Fibonacci number calculation and FizzBuzz problem as sample code.
When I was searching the Web while thinking about that, "Pure LISP should be expressed in a list. However, there is no way to actually try it, so first organize the implementation specifications based on the number of elements in Scheme, and then rewrite it in "jmc.lisp" and other languages. Let's see ...
The implementation example is as follows. Since it is supposed to be rewritten to the minimum set "jmc.lisp" and other languages, it is described with the minimum functions and syntax. ~~ Buchake, l + is ʻ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))
An example of executing Fibonacci number calculation is as follows. Confirmed with 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
Next, the FizzBuzz problem.
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)
For the time being, check the execution with JavaScript version (Node.js 10.21). First, Fibonacci number calculation.
$ nodejs
> .load jmclisp.js
(Display when reading file is cut)
> 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)'
Next, the FizzBuzz problem.
> 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)'
Since it is a rewrite destination, use Python named entities without worrying about it. However, for the purpose of this time, generator generation and numerical calculation processing are not performed ([0] * 3 etc. is NG, len is OK including operation check, a mystery standard).
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]
An example of executing Fibonacci number calculation is as follows.
$ 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
Next, the FizzBuzz problem.
>>> 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']
Recommended Posts