> I have no background in the kind of theoretical CS it's using
There's an amazing amount of depth to SK logic, in terms of how we can use it, where it crops up, etc. but the basics of what it is should be graspable by any programmer. Each "combinator" is just a very simple function. We can write them in Javascript (or rewrite in any other language with first-class functions):
const I = x => x;
const K = x => (y => x);
const S = x => (y => (z => x(z)(y(z))));
const Y = x => (x(Y(x)));
When the game writes two such functions side-by-side `xy` (e.g. `SK`) that's calling the `x` function with `y` as an argument (e.g. `S(K)` in JS). The brackets in the game are for disambiguating, e.g. `SKI` is the same as `(SK)I` which is `S(K)(I)` in JS, whereas `S(KI)` is `S(K(I))` in JS.
Some things to note:
- `I` and `Y` are redundant; we can get the same behaviour using combinations of just `S` and `K`
- `S` and `K` form a turing-complete programming language. In other words, not only can we implement SK logic inside Javascript, we can also implement a Javascript interpreter as a (massive) combination of `S` and `K`.
- Since SK logic is turing-complete, we can't solve the halting problem for it (i.e. we can't always tell if a combination of `S` and `K` will eventually stop reducing or go on forever).
- Most languages, like Javascript, evaluate the argument of a function call before running the function (they are "strict" or "eager"). That might cause some of these combinations to go into an infinite loop unnecessarily: e.g. `Kxy` should reduce to `x`, regardless of what `y` is; but the Javascript equivalent above would be `K(x)(y)`, which will evaluate `x` and `y` first. If `y` happens to go into an infinite loop, trying to evaluate `K(x)(y)` in Javascript will also cause an infinite loop, even though it should ignore `y` and just return `x`.
- The `Y` combinator will always cause such infinite loops; e.g. `Y(KI)` should reduce to `KI(Y(KI))`, and the `Y(KI)` (recursive call) should get discarded to leave `I`. Yet in Javascript the arguments (`I` and `Y(K(I))`) will always be evaluated first, which causes an infinite loop/stack overflow: `Y(K(I))` will become `K(I)(Y(K(I)))`, which will evaluate `I` and `Y(K(I))`, which will become `K(I)(Y(K(I)))`, which will evaluate `I` and `Y(K(I))`, and so on.
- There are alternatives to `Y` which will work in strict/eager languages; the most popular is called `Z`; `Z` can also be implemented using just `S` and `K`.
- Languages which don't evaluate their arguments first are called "non-strict". The LazyK language has non-strict evaluation, so it's a more "correct" implementation of SK logic than the simplistic JS functions above.
- LazyK is a "toy" language. Haskell is the most famous/popular example of a "real" language which is non-strict (although it's not very famous/popular!)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Iota
#
# http://semarch.linguistics.fas.nyu.edu/barker/Iota/
#
# S = λx.λy.λz.xz(yz)
# K = λx.λy.x
# i = λc.cSK
#
# i, *ii, *i*ii, **ii*ii
# 0 100 10100 1100100 Iota is the encoding.
#
## (let iota ()
## (if (eq? #\* (read-char)) ((iota)(iota))
## (lambda (c) ((c (lambda (x) (lambda (y) (lambda (z) ((x z)(y z))))))
## (lambda (x) (lambda (y) x))))))
##
S = lambda x: lambda y: lambda z: x(z)(y(z))
K = lambda x: lambda y: x
i = lambda c: c(S)(K)
I = i(i)
def _decode(path):
bit, path = path[0], path[1:]
if bit == '0':
return i, path
A, path = _decode(path)
B, path = _decode(path)
return A(B), path
decode = lambda path: _decode(path)[0]
# K = *i*i*ii = 1010100
#
print K is i(i(i(i))) is decode('1010100')
# S = *i*i*i*ii = 101010100
#
print S is i(i(i(i(i)))) is decode('101010100')
# All of these return i itself.
print i is i
print i is i(i)(i)
print i is i( i ) ( i(i)(i) )
print i is i( i(i)(i) ) ( i )
print i is i( i(i)(i) ) ( i(i)(i) )
# Identity function
#
I is decode('100') # I.e. i(i)
- Concatenative combinators (if SK are akin to lambda calculus, then concatenative combinators are akin to Joy)
- Binary combinatory logic (a useful context for measuring kolmogorov complexity)
- Linear combinatory logic (information-preserving, reversible, etc. with analogies to quantum operations)
Yet I've never got an intuitive feel for Iota (or Jot). Perhaps your translation/implementation will help me to finally grok it! (Their Wikipedia descriptions look like a mess or parentheses!)
The whole thing with i (Iota combinator) is that contains S and K inside it and you can recover them by various self-applications of i, once you get that the magic is a bit lessened but the beauty is still there.
There's an amazing amount of depth to SK logic, in terms of how we can use it, where it crops up, etc. but the basics of what it is should be graspable by any programmer. Each "combinator" is just a very simple function. We can write them in Javascript (or rewrite in any other language with first-class functions):
When the game writes two such functions side-by-side `xy` (e.g. `SK`) that's calling the `x` function with `y` as an argument (e.g. `S(K)` in JS). The brackets in the game are for disambiguating, e.g. `SKI` is the same as `(SK)I` which is `S(K)(I)` in JS, whereas `S(KI)` is `S(K(I))` in JS.Some things to note:
- `I` and `Y` are redundant; we can get the same behaviour using combinations of just `S` and `K`
- `S` and `K` form a turing-complete programming language. In other words, not only can we implement SK logic inside Javascript, we can also implement a Javascript interpreter as a (massive) combination of `S` and `K`.
- Since SK logic is turing-complete, we can't solve the halting problem for it (i.e. we can't always tell if a combination of `S` and `K` will eventually stop reducing or go on forever).
- Most languages, like Javascript, evaluate the argument of a function call before running the function (they are "strict" or "eager"). That might cause some of these combinations to go into an infinite loop unnecessarily: e.g. `Kxy` should reduce to `x`, regardless of what `y` is; but the Javascript equivalent above would be `K(x)(y)`, which will evaluate `x` and `y` first. If `y` happens to go into an infinite loop, trying to evaluate `K(x)(y)` in Javascript will also cause an infinite loop, even though it should ignore `y` and just return `x`.
- The `Y` combinator will always cause such infinite loops; e.g. `Y(KI)` should reduce to `KI(Y(KI))`, and the `Y(KI)` (recursive call) should get discarded to leave `I`. Yet in Javascript the arguments (`I` and `Y(K(I))`) will always be evaluated first, which causes an infinite loop/stack overflow: `Y(K(I))` will become `K(I)(Y(K(I)))`, which will evaluate `I` and `Y(K(I))`, which will become `K(I)(Y(K(I)))`, which will evaluate `I` and `Y(K(I))`, and so on.
- There are alternatives to `Y` which will work in strict/eager languages; the most popular is called `Z`; `Z` can also be implemented using just `S` and `K`.
- Languages which don't evaluate their arguments first are called "non-strict". The LazyK language has non-strict evaluation, so it's a more "correct" implementation of SK logic than the simplistic JS functions above.
- LazyK is a "toy" language. Haskell is the most famous/popular example of a "real" language which is non-strict (although it's not very famous/popular!)