こんな表作るより先に print-as-golf を作るべきではないだろうか

ごめん、また Lazy K の話なんだ。
チャーチ数にはやたらと (S(KS)K) が出てくるので、(S(KS)K) を纏めると短くなることが多い。ということで、 (S(KS)K) を後ろにつけるとチャーチ数になる式。0、1、4、16、64 など prelude.scm、prelude-numbers.scm のままの方が短くなる数もあるので注意。

0	K(KI)
1	KI
2	SS(KI)
3	SS(SS(KI))
4	SSI(SS(KI))
5	SS(SSI(SS(KI)))
6	S(SSS)(SS(KI))
7	SS(S(SSS)(SS(KI)))
8	S(S(KS)(SS))I(SS(KI))
9	SS(SS)(SS(KI))
10	SS(SS(SS)(SS(KI)))
11	SS(SS(SS(SS)(SS(KI))))
12	S(SSS)(SS(SS(KI)))
13	SS(S(SSS)(SS(SS(KI))))
14	SS(SS(S(SSS)(SS(SS(KI)))))
15	SS(SS(SS(S(SSS)(SS(SS(KI))))))
16	SS(SSI)(SS(KI))
17	SS(SS(SSI)(SS(KI)))
18	SS(SS(SS(SSI)(SS(KI))))
19	SS(SS(SS(SS(SSI)(SS(KI)))))
20	S(SSS)(SSI(SS(KI)))
21	SS(S(SSS)(SSI(SS(KI))))
22	SS(SS(S(SSS)(SSI(SS(KI)))))
23	SS(SS(SS(S(SSS)(SSI(SS(KI))))))
24	S(SI(SS(KI)))(S(SSS)(SS(SS(KI))))
25	S(SS(KI))(SS(SSI(SS(KI))))
26	SS(S(SS(KI))(SS(SSI(SS(KI)))))
27	SSI(SS(SS(KI)))
28	SS(SSI(SS(SS(KI))))
29	SS(SS(SSI(SS(SS(KI)))))
30	S(SSS)(SS(SSI(SS(KI))))
31	SS(S(SSS)(SS(SSI(SS(KI)))))
32	S(SS(SSI(SS(KI))))(SS(KI))
33	SS(S(SS(SSI(SS(KI))))(SS(KI)))
34	S(SI(SS(KI)))(SS(SS(SSI)(SS(KI))))
35	SS(S(SI(SS(KI)))(SS(SS(SSI)(SS(KI)))))
36	SS(S(SSS))(SS(KI))
37	SS(SS(S(SSS))(SS(KI)))
38	SS(SS(SS(S(SSS))(SS(KI))))
39	SS(SS(SS(SS(S(SSS))(SS(KI)))))
40	S(SI(SS(KI)))(S(SSS)(SSI(SS(KI))))
41	SS(S(SI(SS(KI)))(S(SSS)(SSI(SS(KI)))))
42	S(SSS)(S(SSS)(SS(KI)))
43	SS(S(SSS)(S(SSS)(SS(KI))))
44	SS(SS(S(SSS)(S(SSS)(SS(KI)))))
45	SS(SS(SS(S(SSS)(S(SSS)(SS(KI))))))
46	SS(SS(SS(SS(S(SSS)(S(SSS)(SS(KI)))))))
47	SS(SS(SS(SS(SS(S(SSS)(S(SSS)(SS(KI))))))))
48	S(SI(SS(SS(KI))))(SS(SSI)(SS(KI)))
49	S(SS(KI))(SS(S(SSS)(SS(KI))))
50	SS(S(SS(KI))(SS(S(SSS)(SS(KI)))))
51	SS(SS(S(SS(KI))(SS(S(SSS)(SS(KI))))))
52	SS(SS(SS(S(SS(KI))(SS(S(SSS)(SS(KI)))))))
53	SS(SS(SS(SS(S(SS(KI))(SS(S(SSS)(SS(KI))))))))
54	S(SI(SS(KI)))(SSI(SS(SS(KI))))
55	SS(S(SI(SS(KI)))(SSI(SS(SS(KI)))))
56	S(SSS)(SS(S(SSS)(SS(KI))))
57	SS(S(SSS)(SS(S(SSS)(SS(KI)))))
58	SS(SS(S(SSS)(SS(S(SSS)(SS(KI))))))
59	SS(SS(SS(S(SSS)(SS(S(SSS)(SS(KI)))))))
60	S(SI(SS(KI)))(S(SSS)(SS(SSI(SS(KI)))))
61	SS(S(SI(SS(KI)))(S(SSS)(SS(SSI(SS(KI))))))
62	S(SI(SS(KI)))(SS(S(SSS)(SS(SSI(SS(KI))))))
63	S(SI(SS(S(SSS)(SS(KI)))))(SS(SS)(SS(KI)))
64	S(S(SSS)(SS(KI)))(SS(KI))
65	SS(S(S(SSS)(SS(KI)))(SS(KI)))
66	SS(SS(S(S(SSS)(SS(KI)))(SS(KI))))
67	SS(SS(SS(S(S(SSS)(SS(KI)))(SS(KI)))))
68	S(SI(SSI(SS(KI))))(SS(SS(SSI)(SS(KI))))
69	SS(S(SI(SSI(SS(KI))))(SS(SS(SSI)(SS(KI)))))
70	S(SI(SS(S(SSS)(SS(KI)))))(SS(SS(SS)(SS(KI))))
71	SS(S(SI(SS(S(SSS)(SS(KI)))))(SS(SS(SS)(SS(KI)))))
72	S(SSS)(S(S(KS)(SS))I(SS(KI)))
73	SS(S(SSS)(S(S(KS)(SS))I(SS(KI))))
74	S(SI(SS(KI)))(SS(SS(S(SSS))(SS(KI))))
75	SS(S(SI(SS(KI)))(SS(SS(S(SSS))(SS(KI)))))
76	S(SI(SS(KI)))(SS(SS(SS(S(SSS))(SS(KI)))))
77	SS(S(SI(SS(KI)))(SS(SS(SS(S(SSS))(SS(KI))))))
78	S(SI(SS(KI)))(SS(SS(SS(SS(S(SSS))(SS(KI))))))
79	SS(S(SI(SS(KI)))(SS(SS(SS(SS(S(SSS))(SS(KI)))))))
80	S(SI(SSI(SS(KI))))(S(SSS)(SSI(SS(KI))))
81	SS(SS(SS))(SS(KI))
82	SS(SS(SS(SS))(SS(KI)))
83	SS(SS(SS(SS(SS))(SS(KI))))
84	SS(SS(SS(SS(SS(SS))(SS(KI)))))
85	SS(SS(SS(SS(SS(SS(SS))(SS(KI))))))
86	SS(SS(SS(SS(SS(SS(SS(SS))(SS(KI)))))))
87	S(S(S(SSS)(SS(KI)))S)(SS(SS(SS))(SS(KI)))
88	S(S(S(SSS)(SS(KI)))S)(SS(SS(SS(SS))(SS(KI))))
89	S(S(S(S(KS)(SS))I(SS(KI)))S)(SS(SS(SS))(SS(KI)))
90	S(SSS)(SS(SS)(SS(KI)))
91	SS(S(SSS)(SS(SS)(SS(KI))))
92	SS(SS(S(SSS)(SS(SS)(SS(KI)))))
93	SS(SS(SS(S(SSS)(SS(SS)(SS(KI))))))
94	SS(SS(SS(SS(S(SSS)(SS(SS)(SS(KI)))))))
95	SS(SS(SS(SS(SS(S(SSS)(SS(SS)(SS(KI))))))))
96	S(SI(S(SSS)(SS(KI))))(SS(SSI)(SS(KI)))
97	S(S(SS(SSI)(SS(KI)))S)(SS(SS(SS))(SS(KI)))
98	S(SI(SS(KI)))(S(SS(KI))(SS(S(SSS)(SS(KI)))))
99	S(S(SS(SS)(SS(KI)))S)(S(SSS)(SS(SS)(SS(KI))))
100	S(SS(KI))(SS(SS(SS)(SS(KI))))
101	SS(S(SS(KI))(SS(SS(SS)(SS(KI)))))
102	SS(SS(S(SS(KI))(SS(SS(SS)(SS(KI))))))
103	SS(SS(SS(S(SS(KI))(SS(SS(SS)(SS(KI)))))))
104	SS(SS(SS(SS(S(SS(KI))(SS(SS(SS)(SS(KI))))))))
105	S(SI(SS(SSI(SS(KI)))))(SS(S(SSS)(SSI(SS(KI)))))
106	S(S(SS(SSI)(SS(KI)))S)(S(SSS)(SS(SS)(SS(KI))))
107	S(S(SS(SSI)(SS(KI)))S)(SS(S(SSS)(SS(SS)(SS(KI)))))
108	S(SI(SS(SS(KI))))(SS(S(SSS))(SS(KI)))
109	SS(S(SI(SS(SS(KI))))(SS(S(SSS))(SS(KI))))
110	S(SSS)(SS(SS(SS)(SS(KI))))
111	SS(S(SSS)(SS(SS(SS)(SS(KI)))))
112	SS(SS(S(SSS)(SS(SS(SS)(SS(KI))))))
113	SS(SS(SS(S(SSS)(SS(SS(SS)(SS(KI)))))))
114	SS(SS(SS(SS(S(SSS)(SS(SS(SS)(SS(KI))))))))
115	SS(SS(SS(SS(SS(S(SSS)(SS(SS(SS)(SS(KI)))))))))
116	S(SI(SSI(SS(KI))))(SS(SS(SSI(SS(SS(KI))))))
117	S(S(SS(S(SSS))(SS(KI)))S)(SS(SS(SS))(SS(KI)))
118	S(S(SS(S(SSS))(SS(KI)))S)(SS(SS(SS(SS))(SS(KI))))
119	S(SI(SS(S(SSS)(SS(KI)))))(SS(SS(SSI)(SS(KI))))
120	S(SI(S(SSS)(SS(KI))))(S(SSS)(SSI(SS(KI))))
121	S(SS(KI))(SS(SS(SS(SS)(SS(KI)))))
122	SS(S(SS(KI))(SS(SS(SS(SS)(SS(KI))))))
123	SS(SS(S(SS(KI))(SS(SS(SS(SS)(SS(KI)))))))
124	SS(SS(SS(S(SS(KI))(SS(SS(SS(SS)(SS(KI))))))))
125	S(SS(SS(KI)))(SS(SSI(SS(KI))))
126	SS(S(SS(SS(KI)))(SS(SSI(SS(KI)))))
127	SS(SS(S(SS(SS(KI)))(SS(SSI(SS(KI))))))
128	S(SS(S(SSS)(SS(KI))))(SS(KI))

作り方

(use srfi-1)
(load "./lazier.scm")
(load "./prelude.scm")

(define (flatlength lis)
  (if (null? lis)
    0
    (if (list? (car lis))
      (+ (flatlength (car lis)) (flatlength (cdr lis)))
      (+ 1 (flatlength (cdr lis))))))

(lazy-def '(x1+ n) '(s s n))
(lazy-def '(x+ m n) '(s(s m s)n))
(lazy-def '(x* m n) '(s(s i m)n))
(lazy-def '(x^ m n) '(s n m))
(lazy-def '(xn^n n) '(x^ n n))
(lazy-def '(xnn+1 n) '(s(s s s)n))
(lazy-def '(xn^n+1 n) '(x^ n (x1+ n)))

(define (laze1op op x lis)
  (laze (list op (list-ref lis x) )))
(define (lazeinfix op x y lis)
  (laze (list op (list-ref lis x) (list-ref lis y))))
(define (pow x y)
  (if (= y 0) 1 (* x (pow x (- y 1)))))
(define (findlz x lis)
  (car
    (sort
         (append
           (map (lambda(y)(laze1op 'xn^n y lis))
                (filter (lambda(y)(= x (pow y y))) (iota 4)))
           (map (lambda(y)(laze1op 'xnn+1 y lis))
                (filter (lambda(y)(= x (* y (+ 1 y)))) (iota 15)))
           (map (lambda(y)(laze1op 'xn^n+1 y lis))
                (filter (lambda(y)(= x (pow y (+ 1 y)))) (iota 4 2)))
           (map (lambda(y)(lazeinfix 'x+ y (- x y) lis)) (iota (- x 1) 1))
           (map (lambda(y)(lazeinfix 'x* y (quotient x y) lis))
                (filter (lambda(y)(= 0 (modulo x y))) (iota (- x 2) 2)))
           (fold
             (lambda (z cor)
               (append
                 (map (lambda(y)(lazeinfix 'x^ (car z) y lis))
                      (filter (lambda(y)(= x (pow (car z) y))) (iota (cdr z) 2)))
                 cor))
             ()
             '((2 . 8)(3 . 5)(4 . 4)(5 . 3)(6 . 3)))
           (map (lambda(y)(lazeinfix 'x^ y 2 lis))
                (filter (lambda(y)(= x (pow y 2))) (iota 16 2)))
           (list (laze1op 'x1+ (- x 1) lis)))
         (lambda(x y)(< (flatlength x)(flatlength y))))))
(define (loop x lis)
  (if (> x 128)
    lis
    (loop (+ x 1) (append lis (list (findlz x lis))))))

(lazy-def 'x0 '(lambda(x) 0))
(lazy-def 'x1 '(lambda(x) 1))
(for-each 
  (lambda(n chnum) (print n) (print-as-cc chnum))
  (iota 129)
  (loop 2 (list (laze 'x0) (laze 'x1))))

効率を度外視してるので、遅いです。