Lambda Calculus Interpreter (2).






Use of "reduce^" from Newlisp REPL


(setf [println.supressed] true [print.supressed] true)
(load "http://instprog.com/Instprog.default-library.lsp" )
(setf [println.supressed] nil [print.supressed] nil)

;---------------------------------------------------------------
; Interpreter for lambda-calculus, described in recent posts is now
; integrated in my library for Newlisp, as function "reduce^".
;
; Here is example demonstrating how it works. If you want to see
; implementatition details, check the library. Check the previous
; posts also.

(println  (reduce^ '((^ x . (x (x x))) (^ y . (y (y y)))) ;lambda-expression

                        10   ;maximal number of reductions,
                             ;useful for non-terminating lambda-expressions

                        true ;true if you want reduction steps are printed on screen
                             ;nil if you want "silent" interpretation
                        ))
                      
(println  (reduce^ '((^ x . x) (^ x . x))

                        10   
                        
                        true
                        
                        ))

(println (reduce^ '((^ x . (x x)) (^ x . (x x)))
                   
                        10
                        
                        true
                        ))

               
(exit)

; OUTPUT:
;
;   1. ==[ start ]==> ((^x.(x (x x)))(^y.(y (y y))))
;   2. ==[ beta  ]==> ((^y.(y (y y)))((^y.(y (y y)))(^y.(y (y y)))))
;   3. ==[ alpha ]==> ((^x.(x (x x)))((^y.(y (y y)))(^z.(z (z z)))))
; ...
;
;      UNREDUCED: maximal number of reductions reached.
;
; (unreduced ((((^ y . (y (y y))) ((^ y . (y (y y))) (^ y . (y (y y))))) (((^ z . (
;        z
;        (z z)))
;      (^ x1 . (x1 (x1 x1))))
;     ((^ y1 . (y1 (y1 y1))) (^ z1 . (z1 (z1 z1))))))
;   (((^ x2 . (x2 (x2 x2))) (^ y2 . (y2 (y2 y2)))) ((^ z2 . (z2 (z2 z2))) (^ x3 . (
;       x3
;       (x3 x3)))))) 10)
;
;   1. ==[ start ]==> ((^x.x)(^x.x))
;   2. ==[ alpha ]==> ((^x.x)(^y.y))
;   3. ==[ beta  ]==> (^y.y)
;   4. ==[ alpha ]==> (^x.x)
;
;      REDUCED to normal form.
;
; (reduced (^ x . x) 4)
;
;   1. ==[ start ]==> ((^x.(x x))(^x.(x x)))
;   2. ==[ alpha ]==> ((^x.(x x))(^y.(y y)))
;   3. ==[ beta  ]==> ((^y.(y y))(^y.(y y)))
;   4. ==[ alpha ]==> ((^x.(x x))(^y.(y y)))
;
;      IRREDUCIBLE: cycle.
;
; (irreducible ((^ x . (x x)) (^ y . (y y))) 4)
;
;
;



If you like this post, you'll probably like


 Almost two hundred thousand reduced lambda-expressions. 


--

No comments:

Post a Comment