Common Lisp, 560 bajtów
„Wreszcie znalazłem zastosowanie PROGV”.
(macrolet((w(S Z G #1=&optional(J Z))`(if(symbolp,S),Z(destructuring-bind(a b #1#c),S(if(eq a'L),G,J)))))(labels((r(S #1#(N 97))(w S(symbol-value s)(let((v(make-symbol(coerce`(,(code-char N))'string))))(progv`(,b,v)`(,v,v)`(L,v,(r c(1+ n)))))(let((F(r a N))(U(r b N)))(w F`(,F,U)(progv`(,b)`(,U)(r c N))))))(p()(do((c()(read-char()()#\)))q u)((eql c #\))u)(setf q(case c(#\S'(L x(L y(L z((x z)(y z))))))(#\K'(L x(L u x)))(#\I'(L a a))(#\((p)))u(if u`(,u,q)q))))(o(S)(w S(symbol-name S)(#2=format()"~A.~A"b(o c))(#2#()"~A(~A)"(o a)(o b)))))(lambda()(o(r(p))))))
Nie golfił
;; Bind S, K and I symbols to their lambda-calculus equivalent.
;;
;; L means lambda, and thus:
;;
;; - (L x S) is variable binding, i.e. "x.S"
;; - (F x) is function application
(define-symbol-macro S '(L x (L y (L z ((x z) (y z))))))
(define-symbol-macro K '(L x (L u x)))
(define-symbol-macro I '(L x x))
;; helper macro: used twice in R and once in O
(defmacro w (S sf lf &optional(af sf))
`(if (symbolp ,S) ,sf
(destructuring-bind(a b &optional c) ,S
(if (eq a 'L)
,lf
,af))))
;; R : beta-reduction
(defun r (S &optional (N 97))
(w S
(symbol-value s)
(let ((v(make-symbol(make-string 1 :initial-element(code-char N)))))
(progv`(,b,v)`(,v,v)
`(L ,v ,(r c (1+ n)))))
(let ((F (r a N))
(U (r b N)))
(w F`(,F,U)(progv`(,b)`(,U)(r c N))))))
;; P : parse from stream to lambda tree
(defun p (&optional (stream *standard-output*))
(loop for c = (read-char stream nil #\))
until (eql c #\))
for q = (case c (#\S S) (#\K K) (#\I I) (#\( (p stream)))
for u = q then `(,u ,q)
finally (return u)))
;; O : output lambda forms as strings
(defun o (S)
(w S
(princ-to-string S)
(format nil "~A.~A" b (o c))
(format nil (w b "(~A~A)" "(~A(~A))") (o a) (o b))))
Zmniejszenie beta
Zmienne są dynamicznie powiązane podczas redukcji z PROGVnowymi symbolami Common Lisp, za pomocą MAKE-SYMBOL. Pozwala to ładnie uniknąć kolizji nazewnictwa (np. Niepożądane cieniowanie powiązanych zmiennych). Mógłbym użyć GENSYM, ale chcemy mieć przyjazne nazwy dla symboli. Dlatego symbole są nazywane literami od ado z(zgodnie z pytaniem). Nreprezentuje kod znakowy następnej dostępnej litery w bieżącym zakresie i zaczyna się od 97, aliasa .
Oto bardziej czytelna wersja R(bez Wmakra):
(defun beta-reduce (S &optional (N 97))
(if (symbolp s)
(symbol-value s)
(if (eq (car s) 'L)
;; lambda
(let ((v (make-symbol (make-string 1 :initial-element (code-char N)))))
(progv (list (second s) v)(list v v)
`(L ,v ,(beta-reduce (third s) (1+ n)))))
(let ((fn (beta-reduce (first s) N))
(arg (beta-reduce (second s) N)))
(if (and(consp fn)(eq'L(car fn)))
(progv (list (second fn)) (list arg)
(beta-reduce (third fn) N))
`(,fn ,arg))))))
Wyniki pośrednie
Analizuj z ciągu:
CL-USER> (p (make-string-input-stream "K(K(K(KK)))"))
((L X (L U X)) ((L X (L U X)) ((L X (L U X)) ((L X (L U X)) (L X (L U X))))))
Redukować:
CL-USER> (r *)
(L #:|a| (L #:|a| (L #:|a| (L #:|a| (L #:|a| (L #:|b| #:|a|))))))
(Zobacz ślad wykonania)
Ładny druk:
CL-USER> (o *)
"a.a.a.a.a.b.a"
Testy
Używam ponownie tego samego zestawu testów, co odpowiedź w języku Python:
Input Output Python output (for comparison)
1. KSK a.b.c.a(c)(b(c)) a.b.c.a(c)(b(c))
2. SII a.a(a) a.a(a)
3. S(K(SI))K a.b.b(a) a.b.b(a)
4. S(S(KS)K)I a.b.a(a(b)) a.b.a(a(b))
5. S(S(KS)K)(S(S(KS)K)I) a.b.a(a(a(b))) a.b.a(a(a(b)))
6. K(K(K(KK))) a.a.a.a.a.b.a a.b.c.d.e.f.e
7. SII(SII) ERROR ERROR
Ósmy przykład testu jest zbyt duży dla powyższej tabeli:
8. SS(SS)(SS)
CL a.b.a(b)(c.b(c)(a(b)(c)))(a(b.a(b)(c.b(c)(a(b)(c))))(b))
Python a.b.a(b)(c.b(c)(a(b)(c)))(a(d.a(d)(e.d(e)(a(d)(e))))(b))
- EDYCJA Zaktualizowałem moją odpowiedź, aby zachować takie samo zachowanie grupowania jak w odpowiedzi aditsu , ponieważ napisanie kosztuje mniej bajtów.
- Pozostałą różnicę widać na testach 6 i 8. Wynik
a.a.a.a.a.b.ajest prawidłowy i nie używa jako dużo listów jako odpowiedź Python, gdzie wiązanie do a, b, ci dnie odwołuje.
Wydajność
Zapętlanie 7 powyższych testów pozytywnych i zbieranie wyników jest natychmiastowe (wynik SBCL):
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
310,837 processor cycles
129,792 bytes consed
Wykonanie tego samego testu sto razy prowadzi do… „Wyczerpanie lokalnego magazynu wątków” na SBCL, ze względu na znane ograniczenie dotyczące zmiennych specjalnych. W przypadku CCL wywołanie tego samego zestawu testów 10000 razy zajmuje 3,33 sekundy.