3 ms·
To be even more minimal, you can get rid of custom definitions, and encode everything as calls to the following two functions: k = -> x { ->
by chriswarbo 4y ago
To be even more minimal, you can get rid of custom definitions, and encode everything as calls to the following two functions:
k =
-> x {
-> y {
x
}
}
s =
-> x {
-> y {
-> z {
x[z][y[z]]
}
}
}
For example, 'k[x][y]' returns 'x', so
TRUE = k
FALSE is a little trickier, so we'll need to calculate its implementation based on the definition. It can't be 'k' (since that behaves like 'TRUE'), and 's' requires three arguments rather than two. Let's assume it's 'S[A]' for some argument 'A':
Let FALSE[x][y] = s[A][x][y]
= A[y][x[y]]
We need to find a value for 'A', such that 'A[y][x[y]]' returns 'y'. We can use 'k', hence 'FALSE' can be implemented as 's[k]':
FALSE[x][y] = s[k][x][y]
= k[y][x[y]]
= y
We can follow a similar procedure for the other sections of this article (numbers, lists, etc.)
https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
Note that there are alternative systems with only one definition, like https://news.ycombinator.com/item?id=31473127 https://news.ycombinator.com/item?id=31473127 , but those single definitions are quite complex, compared to s and k.
- tomstuart 4y agoFYI there’s an (explicitly interpreted, not proc-encoded) implementation of this in https://computationbook.com https://computationbook.com, including compilation from lambda calculus: https://github.com/tomstuart/computationbook/tree/master/universality_is_everywhere/ski_calculus https://github.com/tomstuart/computationbook/tree/master/uni... And also, as you imply, iota: https://github.com/tomstuart/computationbook/tree/master/universality_is_everywhere/iota https://github.com/tomstuart/computationbook/tree/master/uni...