Combinatris: Tetris with SKI Combinators
dirk.rave.org
dirk.rave.org
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)));
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)- Illative combinatory logic (equivalent to dependent type theory http://chriswarbo.net/blog/2012-12-01-typed_combinators.html )
- 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.
Cheers!
This is maybe different from what you’re seeking, but SPL-T is a very engaging puzzler that can lead to flow states where you’re slicing your way through perfectly balanced stacks of blocks, watching their countdowns halve each time. It’s turn-based and iOS only. Fully deterministic, very simple, but my preferred strategy is still evolving every time I play.
Quite a few puzzle games came out in the late 80's and early 90's, probably hoping to be the next Tetris, but most of them are pretty forgettable. Nothing else ever really captured that same feeling, and certainly not its broad appeal. It's just so elegantly simple.
I think the ones that have stood the test of time the best are:
Puyo Puyo:
Somewhat similar to the versus mode of Dr. Mario, but a lot faster and with a much higher skill cap. Simple mechanics, but very deep gameplay. Sadly never got a huge following outside of Asia.
Magical Drop III:
Moreso than any other game, this one makes me feel like I'm a machine performing a sorting algorithm. I mean that in the best possible way. Money Puzzle Exchanger is a very similar game that requires more advanced planning.
Puzzle Bobble:
I never got into this series but it frequently shows up on these kinds of recommendation lists.
Tetris Attack:
The name is misleading, it has nothing to do with Tetris and plays nothing like it, but a great puzzle game nonetheless.
Devil Dice is a personal favorite, but never reached the popularity of any of the above.
Some other honorable mentions that I don't know enough to comment on:
Meteos
Landmaker
Cleopatra Fortune
Klax
Columns
The list could go on and on though.
(Actually, it's θ, but suspension of disbelief and all.)