Skip to content

Instantly share code, notes, and snippets.

@shlomiv
Last active December 17, 2015 06:18
Show Gist options
  • Save shlomiv/5564050 to your computer and use it in GitHub Desktop.
Save shlomiv/5564050 to your computer and use it in GitHub Desktop.
(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