Lambda: the Gathering

Lambda: the Gathering is a two-player competitive game and programming language defined in the task description of the ICFP programming contest 2011.

The language works with two kinds of values: integers and functions. Each player has a set of 256 "slots", each of which stores a single value and has a hit point counter ("vitality"). The functions are combinators composed of a small set of primitives that include well-known pure combinators like S, K, I, (KI), but also ones that have side effects on the game state. There are primitives for reading the value from a slot using its number, damaging the slots of the opponent, and more.

The players act in alternating turns. Each turn, a player applies one of the 15 primitives ("cards") to one of his slots from either left or right. The resulting function call is evaluated, which may have side effects on the game, then the resulting value overwrites the same slot. The application may lead to an error (eg. using a number as a function or the other way, referring to a non-existant or dead slot), or time out (too many applications) in which case the application is halted and I is written to the slot value.

If enough damage is dealt to a slot to bring its hit point counter to zero, the slot can no longer be used for either application or for reading its value (unless it's revived). This means that if your opponent harms your slot, you will have more difficulty writing programs. The player with the most slots alive after 100000 turns wins.

The slots with the first few ordinals are the most valuable because they're the easiest for you to access (you can construct their ordinal more easily), but are also one of the most difficult for the opponent to access. Players are able to read opponent's slot, thus they may be able to reuse values the opponent constructs.

The game also has the complicated concept of zombies, which is not described here.