lambda-core/languages/l/lua/lambda-core.lua at main · kserrec/lambda-core · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
-- _lc postfix to prevent conflict
-- Bool value
local true_lc = function(x)
	return function(y)
		return x
	end
end
local false_lc = function(x)
	return function(y)
		return y
	end
end

-- Boolean Operations
local and_lc = function(a)
	return function(b)
		return a(b)(false_lc)
	end
end

local or_lc = function(a)
	return function(b)
		return a(true_lc)(b)
	end
end

local not_lc = function(a)
	return a(false_lc)(true_lc)
end

-- Church Numerals
local zero = function(f)
	return function(x)
		return x
	end
end
local one = function(f)
	return function(x)
		return f(x)
	end
end
local succ = function(n)
	return function(f)
		return function(x)
			return f(n(f)(x))
		end
	end
end
-- This is ugly
local pred = function(n)
	return function(f)
		return function(x)
			return n(function(g)
				return function(h)
					return h(g(f))
				end
			end)(function(u)
				return x
			end)(function(u)
				return u
			end)
		end
	end
end
-- a slightly better version of pred
local pred_v2 = function(n)
	return function(f)
		return function(x)
			local helper = function(g)
				return function(h)
					return h(g(f))
				end
			end
			return n(helper)(function(_)
				return x
			end)(function(u)
				return u
			end)
		end
	end
end
-- Helper functions
local read_bool = function(b)
	return b(true)(false)
end

local read_church = function(n)
	return n(function(x)
		return x + 1
	end)(0)
end

-- Test Cases
print(read_bool(true_lc)) -- true
print(read_bool(false_lc)) -- false
print(read_bool(not_lc(true_lc))) -- false
print(read_bool(not_lc(false_lc))) -- true
print(read_bool(and_lc(true_lc)(true_lc))) -- true
print(read_bool(and_lc(true_lc)(false_lc))) -- false
print(read_bool(and_lc(false_lc)(true_lc))) -- false
print(read_bool(and_lc(false_lc)(false_lc))) -- false
print(read_bool(or_lc(true_lc)(true_lc))) -- true
print(read_bool(or_lc(true_lc)(false_lc))) -- true
print(read_bool(or_lc(false_lc)(true_lc))) -- true
print(read_bool(or_lc(false_lc)(false_lc))) -- false

print(read_church(zero)) -- 0
print(read_church(succ(zero))) -- 1
print(read_church(succ(one))) -- 2
print(read_church(succ(succ(one)))) -- 3
print(read_church(pred(one))) -- 0
print(read_church(pred_v2(one))) -- 0
print(read_church(pred(succ(one)))) -- 1
print(read_church(pred_v2(succ(one)))) -- 1
print(read_church(pred(succ(succ(one))))) -- 2
print(read_church(pred_v2(succ(succ(one))))) -- 2