为什么要把题目写得这么正经向啊x
做这个东西的想法来源于锦心和senioria提到的whitespace语言, 从wikipedia上的介绍上看, "正统"的whitespace更接近于用这几种空白字符编码指令, 而非senioria认为更优雅的用于编码某种组合子. 所以, senioria决定做了一个解释器.
刺猬洞里的鸽子 瑟尼欧里娅(雾)
本来是打算每次都速战速决的, 但是总是因为各种各样奇奇怪怪的原因咕咕咕了呢(笑)
不这么自闭而且不咕的话, 应该会是个很难缠的对手吧(笑)
源代码
(将就着看吧, ll对源码高亮的支持好差(捂脸
(因为有限制所以只能压缩一下传了>< src.zip (662 字节)
#lang racket
(define cl-K (curry (lambda (a b) (lazy a))))
(define cl-S
(curry (lambda (a b c)
(lazy ((cl-func (force a)) c (lazy ((cl-func (force b)) c)))))))
(define (cl-func expr)
(case expr
[(0 K) cl-K]
[(1 S) cl-S]
[else expr]))
(define (cl-pow-apply fn next pow)
(if (= 0 pow) fn
(let-values ([(expr next) (next)])
(if (equal? expr 'eof) fn
(cl-pow-apply
((cl-func fn) (cl-eval (lambda () (values expr next))))
next (- pow 1))))))
(define (cl-eval next)
(let-values ([(expr next) (next)])
(case expr
[(0 1 eof) expr]
[else
(let ([fn (cl-func expr)])
(cl-pow-apply
fn next
(if (equal? fn cl-K) 2 3)))])))
(define (read-next stream)
(let ([ch (read-char stream)])
(if (eof-object? ch) 'eof
(case ch
[(#\space) 0]
[(#\tab) 1]
[(#\newline) (cl-func (read-next stream))]
[else (read-next stream)]))))
(define (main)
(command-line
#:args (filename)
(let ([stream (open-input-file filename)])
(define (readrec)
(letrec ([norm-read (lambda () (values (read-next stream) norm-read))])
(values (cl-func (read-next stream)) norm-read)))
(define (proc)
(let ([val (force (cl-eval readrec))])
(if (equal? val 'eof) '() (cons val (proc)))))
(proc))))
(main)
这里, senioria用空格来表示数据(比特)0和组合子K, 用tab来表示数据(比特)1和组合子S; 用换行符来表示强行将之后的一个空格/tab当作组合子看待, 并且立即对这个组合子求值; 在已有的输入已经被求值完了的时候, 会将下一个输入当作组合子求值.
令a, b, c为任意表达式, 这些组合子的定义如下:
-
K a b
会被求值为a
-
S a b c
会被求值为a c (b c)
wiki上已经证明了可以自由带括号的组合子运算是完备的, 所以, 要证明senioria这里实现的组合子运算的完备性, 只需要证明任意合法的括号组合都可以被实现即可.
(然而senioria暂时证不出来了qwq(被打死