Last active
December 17, 2015 06:18
-
-
Save shlomiv/5564050 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(run | |
"let count = proc(val) -(0, -(-1, val)) % perform the actual counting on church-numerlas | |
in let to-num = proc(n) ((n count) 0) % convert from church numerals to num-val | |
in let next = proc(n) proc(f) proc(x) (f ((n f) x)) % standard church numerals implementations using LC | |
in let mult = proc(m) proc(n) proc(x) (m (n x)) % multiplication in terms of CN | |
in let zero = proc(f) proc(x) x % some constants | |
in let one = proc(f) proc(x) (f x) | |
in let two = proc(f) proc(x) (f (f x)) | |
in let three = (next two) | |
in let four = ((mult two) two) | |
in let first = proc(x) proc(y) x % selectors | |
in let second = proc(x) proc(y) y | |
in let third = proc(x) proc(y) proc(z) z | |
in let pair = proc(x) proc(y) proc(f) ((f x) y) % pair, used by pred | |
in let prefn = proc(f) proc(p) ((pair (f (p first))) (p first)) % | |
in let pred = proc(n) proc(f) proc(x) (((n (prefn f))((pair x )x)) second) % the nasty pred function :) | |
in let iszero = proc(n) ((n third) first) % our non-lazy if zero? then else pattern | |
in let realize = proc(f) (f 1) % we will soon need lazy evaluation to correctly use our iszero function, 1 is a dummy value | |
% the Z-combinator - an implementation of the Y-combinator that does not assume lazyness | |
% (similar to the one in tests.scm file, even though it says Y-comb by mistake ;) ) | |
% | |
in let Z = proc(f) (proc(x) (f proc(y) ((x x) y)) proc(x) (f proc(y) ((x x) y))) | |
% the actual factorial, but with built-in laziness, otherwise 'iszero' would never terminate! | |
% notice how both end cases returns a function that disregards its input, while in the 'recursive call' the laziness gets realized internally. | |
% | |
in let fact = proc(g) proc(n) (((iszero n) proc(x) one) proc(x)((mult n)(realize (g (pred n))))) | |
% create the fixed-point recursion, and realize the lazy computaion. | |
% | |
in let F = proc(x) (realize ((Z fact) x)) | |
% and now.... tada! | |
in (to-num (F four)) ")) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment