Scheme版について諸々定義してやってみた結果は次の通り．
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
経緯
拙作シリーズ記事『簡易LISP処理系の実装例（◯◯版）』は，原初のLISP処理系定義のCommon Lisp版（"jmc.lisp"）を各プログラミング言語で実装してみようというもので，もともと自己記述可能な超循環評価器として構成されていただけあり，最小セットの言語仕様ながら，連想リストを処理する再帰手続きなどが普通に記述できるLISP処理系です．
が，それだけに，数値や演算が扱えません．ダイナミックスコープのためチャーチ数が実装できないという事情もあります．処理系に整数演算やレキシカルスコープ（クロージャ機能）を組み込むこと自体はとても簡単なのですが，上記シリーズ記事の趣旨は『言語処理系実装の最初の敷居を下げてみよう』であり，機能拡張は次のステップとして各自で試してほしいという意図があります．でも，現仕様のままで数値演算もやってみたい．フィボナッチ数計算やFizzBuzz問題をサンプルコードとして示したい．
と，そんなことを考えながらWeb検索をしていたところ，『純LISPたるもの，全てリストで表現するべきだ』といった言葉が出てきて，でも実際に試した例は出てこなくて，しかたがないので，まずはSchemeで要素数ベースの実装仕様を整理したのち，"jmc.lisp"その他の言語に書き直してみよう…というのが経緯です．
Scheme版
実装例は次の通り．最小セットの"jmc.lisp"や他の言語への書き直しを想定しているため，最低限の関数や構文で記述しています．ぶっちゃけ，l+は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))
フィボナッチ数計算の実行例は次の通り．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
続けて，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)
"jmc.lisp"版
とりあえずJavaScript版（Node.js 10.21）で実行確認．まず，フィボナッチ数計算．
$ nodejs
> .load jmclisp.js
（ファイル読み込み時の表示はカット）
> 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)'
続けて，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)'
Python版
書き換え先なので，気にせずPython固有表現を使用．ただし，今回の趣旨から，ジェネレータ生成や数値演算処理は行わないということで（[0] * 3などはNG，lenは動作確認を含めてOK，という謎基準）．
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]
フィボナッチ数計算の実行例は次の通り．
$ 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
続けて，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']
備考
記事に関する補足
- FizzBuzz問題はやりすぎたかな…．でも，サンプルプログラムの定番だしなあ．
更新履歴
- 2020-09-20：Python版のFizzBuzz問題の関数定義の掲載を忘れていたため追加
- 2020-09-18：Python版を追加
- 2020-09-18：初版公開（Scheme版，"jmc.lisp"版）