One class, many games¶
The engine has to call Snap's step for a Snap table and Alba's step for
an Alba table, without knowing about either. Lean's tool for this is the
type class: a list of things a type must provide, and, for each type
that provides them, an instance that says how.
The Game class¶
Here is the whole class, from Engine/Protocol.lean:
class Game (σ : Type) where
/-- Game-specific action type. -/
Action : Type
/-- Game-specific event type. -/
Event : Type
name : String
init : Json → Except String σ
/-- How many seats the game has. Seats are numbered from 0. -/
seats : σ → Nat
decodeAction : Json → Except String Action
/-- The transition function. The whole point of the project: rules live here. -/
step : σ → Nat → Action → Except Rejection (σ × List Event)
/-- The moves offered to a viewer (seats in choices labelled by name). -/
actions : Names → σ → Viewer → List ActionSpec
observe : σ → Viewer → Json
/-- What is happening now. -/
phase : Names → σ → PhaseInfo
/-- The seats the table is openly waiting on. (Only public facts: a move
the table cannot know about is not announced here.) -/
waitingFor : σ → List Nat
/-- The game's words: its title, its rules in plain language, and the
names of everything a player sees. -/
catalogue : σ → Json
encodeEvent : Event → Json
/-- An event in plain words, naming each seat by its player's name. -/
describe : Names → Event → String
/-- Who may see each event. -/
audience : Event → Audience := fun _ => .everyone
/-- `none` while the game is in progress. -/
outcome : Names → σ → Option Outcome
Read the first line: class Game (σ : Type) where. σ (the Greek letter
sigma, type \sigma) is a type parameter: it stands for the type of a
game's state, whatever that game is. For Snap it will be Snap's State, for
Alba, Alba's. A class looks like a structure, and it is one: each line
below is a field. The difference is in how its values are found, as you'll
see shortly.
The fields are the questions the engine asks:
ActionandEventare fields whose values are types. Each game has its own kind of move and its own kind of event, so the class doesn't say what they are, only that the game must say. Lean lets a type be a value like any other.stepis the rules. Its type mentionsActionandEvent, so it is Snap's own moves that Snap'ssteptakes.observe,actions,phase,waitingFor,catalogue,describeandoutcometurn a state into what players are shown.audiencehas a default,fun _ => .everyone: a game that says nothing about it has only public events.
Except String σ, the type of init, is the Except you met in Snap: an
error or a value. Starting a game can fail, if the config asks for
something the game doesn't allow.
An instance for each game¶
Here is how Snap answers the questions, at the end of Games/Snap/Game.lean:
instance : Game State where
Action := Action
Event := Event
name := "snap"
init cfg := do
let seed ← cfg.optNat "seed" 0
let maxFlips ← cfg.optNat "maxFlips" 2000
-- A game must allow at least one flip; see `Proofs.Snap.deal_capOk`.
if maxFlips = 0 then throw "config 'maxFlips' must be at least 1"
pure (State.deal seed maxFlips)
decodeAction j :=
match j.get? "id" >>= Json.getStr? with
| some "flip" => pure .flip
| some "snap" => pure .snap
| some other => throw s!"unknown action '{other}'"
| none => throw "missing action id"
seats _ := 2
step := step
actions _ := actions
observe := observe
phase := phase
waitingFor := waitingFor
catalogue := catalogue
encodeEvent := Event.toJson
describe := Event.describe
outcome := outcome
instance : Game State where says: here is how Snap's State is a game.
Each field is filled with something from Snap's files. Action := Action
looks odd, but the left side is the class's field and the right side is
Snap's own Action type, the flip or the snap. step := step is the
step you read in Snap's rules, unchanged. seats _ := 2 ignores the state:
Snap always has two players.
- Lol and Alba each end their own
Game.leanwith their own instance, `instance - Game State where
, for their ownState. Lol'sseatscounts its players, itsaudienceis Lol's ownEvent.audience, and itsinitchecks that there are two to four players. Alba'sinit` checks for five to ten. None of them mentions another game.
With the instances in place, Game.name of a type finds that game's answer:
/-- info: "snap" -/
#guard_msgs in
#eval Game.name Games.Snap.State
/-- info: "lol" -/
#guard_msgs in
#eval Game.name Games.LoL.State
/-- info: "alba" -/
#guard_msgs in
#eval Game.name Games.Alba.State
And Game.Action of a type is that game's own type of move. These are
proofs by rfl, because Lean works out each side to the same type:
example : Game.Action Games.Snap.State = Games.Snap.Action := rfl
example : Game.Action Games.LoL.State = Games.LoL.Move := rfl
example : Game.Action Games.Alba.State = Games.Alba.Move := rfl
Snap's moves are called Action; Lol's and Alba's are called Move. The
class doesn't mind: the instance says which type is meant.
Finding the instance¶
Here are the types of two of the class's fields, as Lean sees them from outside:
/-- info: @Game.seats : {σ : Type} → [self : Game σ] → σ → Nat -/
#guard_msgs in
#check @Game.seats
/--
info: @Game.step : {σ : Type} → [self : Game σ] → σ → Nat → Game.Action σ → Except Rejection (σ × List (Game.Event σ))
-/
#guard_msgs in
#check @Game.step
(@ asks Lean to show every argument, even the ones you never write.) Two
new kinds of argument appear before the state:
{σ : Type}, in curly brackets, is an implicit argument. You don't pass it: Lean works it out from the other arguments. Given a Snap state,σmust be Snap'sState.[self : Game σ], in square brackets, is an instance argument. You don't pass it either: once Lean knowsσ, it searches for the instanceGame σand passes that. This search is what makes a class different from a structure.
So Game.seats s, for a Snap state s, becomes Snap's seats, and for an
Alba state, Alba's. A function can ask for the same two arguments, and then
it works for every game:
/-- Every seat at the table, for any game. -/
def everyone {σ : Type} [Game σ] (s : σ) : List Nat :=
List.range (Game.seats s)
/-- info: [0, 1] -/
#guard_msgs in
#eval everyone (Games.Snap.State.deal 3 100)
/-- info: [0, 1, 2] -/
#guard_msgs in
#eval everyone (Games.LoL.init 3 5 4).1
/-- info: [0, 1, 2, 3, 4, 5, 6] -/
#guard_msgs in
#eval everyone (Games.Alba.init 7 5)
everyone was written once, with no game in mind. Every function in
Engine/Session.lean is written like this. The file says so once, near the
top, with variable {σ : Type} [Game σ]: a variable line adds those
arguments to every definition after it that uses them, so they needn't be
repeated.
When Lean can't work out σ by itself, you can name it: (σ := Games.Snap.State)
passes the argument called σ explicitly. Game.audience takes an event,
not a state, and Lean doesn't work backwards from an event's type to the game
it belongs to: without (σ := …) it reports a type mismatch. With it, this
asks each game who may see an event:
/-- info: Engine.Audience.everyone -/
#guard_msgs in
#eval Game.audience (σ := Games.Snap.State) (Games.Snap.Event.recycled 0)
/-- info: Engine.Audience.only [1] -/
#guard_msgs in
#eval Game.audience (σ := Games.LoL.State) (Games.LoL.Event.drew 1 .seer)
/-- info: Engine.Audience.everyone -/
#guard_msgs in
#eval Game.audience (σ := Games.LoL.State) (Games.LoL.Event.nodded 1)
Snap never set audience, so it has the default. Lol's card drawn by seat 1
is for seat 1 only.
Functions as data¶
The engine writes every seat by its player's name, but no game stores names:
a name is not part of the rules. Instead, the questions that need names
(actions, phase, describe, outcome) take them as an argument, of
this type:
/-- What the players at a table are called, seat by seat: the engine writes
every seat by its name. (A name is only a label: no rule looks at it.) -/
abbrev Names := Nat → String
abbrev is a def that Lean unfolds whenever it likes, so Names is just
another way to write Nat → String: a function from a seat number to a
name. A function is a value, like a number or a list, so it can be passed
in. Here is one that names two seats, and the same Snap event described
with it and with the engine's default:
/-- info: @[reducible] def Engine.Names : Type :=
Nat → String -/
#guard_msgs in
#print Names
/-- Two players' names, as a function from seat to name. -/
def ours : Names := fun i => if i = 0 then "Ada" else "Brian"
/-- info: "Brian called snap and won 4 cards" -/
#guard_msgs in
#eval Games.Snap.Event.describe ours (.snapped 1 4)
/-- info: "Player 2 called snap and won 4 cards" -/
#guard_msgs in
#eval Games.Snap.Event.describe seatName (.snapped 1 4)
The default, seatName, counts from one, as people do:
/-- The name for a seat when a table gives none: "Player 1" is seat 0. -/
def seatName (i : Nat) : String := s!"Player {i + 1}"
Because the names arrive from outside, Snap's rules can't depend on them, and the engine proves it, as the next chapter shows.
Exercises¶
- Write
isOver, which says whether a game of any kind is over (hint:Game.outcomegivesnonewhile it goes on;Option.isSomesays whether it issome). Check with#guardthat a fresh game of each of Snap, Lol and Alba is not over. - Prove that
Game.seats s = 2for every Snap states. - Write a
Namesthat calls seats by their number counting from zero ("Seat 0"), and use it to describe Snap's.recycled 0event.
Solution
/-- Is the game over? For any game. -/
def isOver {σ : Type} [Game σ] (s : σ) : Bool :=
(Game.outcome seatName s).isSome
#guard !isOver (Games.Snap.State.deal 3 100)
#guard !isOver (Games.LoL.init 2 3 4).1
#guard !isOver (Games.Alba.init 5 3)
/-- Snap always has two seats, whatever the state. -/
example (s : Games.Snap.State) : Game.seats s = 2 := rfl
/-- Seats called by their number, counting from zero. -/
def fromZero : Names := fun i => s!"Seat {i}"
/-- info: "Seat 0 turned their face-up pile over to make a new stack" -/
#guard_msgs in
#eval Games.Snap.Event.describe fromZero (.recycled 0)
The second is rfl because Lean finds Snap's instance, whose seats
is fun _ => 2, and works it out. The same statement for Lol would not
be rfl: Lol's seat count depends on the state.