This was surprisingly addictive. I have no background in the kind of theoretical CS it's using, but still managed to pick up on a few patterns and see how you could progress with a more thorough understanding.
> 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.
This is interesting. I've been hoping for someone to really come up with a Tetris-like game where you can get into the zone and just play. You know, simple to learn, hard to master, based on a single fundamental algorithm of some sort, etc. Lumines was close, and fun, but got a bit repetitive after a while. But since then, nothing I've seen has really done it. Anything I'm missing?
I always really liked Dr Mario for the combos. It was satisfying to have so much potential building up on the board until I got that red-blue pill I needed, and watching the whole thing cascade. Two player is even more fun.
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.
Monday morning task: reply to this tab from Friday afternoon, haha.
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:
[1] http://www.angelfire.com/tx4/cus/combinator/birds.html