| Code |
# Y combinator
Y = \g . (\x . g (x x)) \x . g (x x)
rec = \f . f (Y f)
# lists
# using false as "nil" in lists, so you use a list like this:
# DUMMY can be anything, but it needs to be there
# here's how you use a list:
# aList (\h t DUMMY . {list-case}) {empty-case}
# If the list is not empty, h and t are the head and tail of the list and it returns list-case. DUMMY is not used, but needs to be there
# If the list is empty, it returns empty-case
cons = \a b f.f a b
nil = false
head = \l . l (\h t D . h) nil
tail = \l . l (\h t D . t) nil
null = \l . l (\h t D . false) true
last = rec \last l . l (\h t D . null t h (last t)) nil
append = rec \append l1 l2 . l1 (\h t D . cons h (append t l2)) l2
reverse = \l . (rec \rev l res . l (\h t D . rev t (cons h res)) res) l nil
# list constructor: [1,2,3]
# this uses some parsing rules: =(]=, =.=, and =)=
[ =(]= \item f . f (cons item nil)
, =.= \l item f . f (cons item l)
] =)= reverse
# Booleans t = \x y . x f = \x y . y not = \a . a f t # 10 x 9 grid (a 9x9 grid for missiles and aliens and a 9x1 row for the ship) # a grid row applies a function of 9 arguments to its values # a grid cell represents a value from 0 to 4 (empty, ship, alien1, alien2, missile) # higher values 'beat' lower values # cells are functions of 5 arguments and they indicate their value by returning the nth argument (like booleans) # cell functions e = \1 2 3 4 5 . 1 s = \1 2 3 4 5 . 2 a1 = \1 2 3 4 5 . 3 a2 = \1 2 3 4 5 . 4 m = \1 2 3 4 5 . 5 cell = \n f . f n isE = \n . n t f f f f # (larger a b) returns the larger value -- for missiles vs aliens and aliens vs the ship larger = \n1 n2 . n1 n2 (n2 n1 n1 n2 n2 n2) (n2 n1 n1 n1 n2 n2) (n2 n1 n1 n1 n1 n2) n1 # row functions row = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 r . r 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 left = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 r . r 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 right = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 r . r 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 cellA = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 . cell 1 cellZ = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 . cell 19 get1 = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 . 1 # return a new row with each element applied to a function row-to-func = \g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 r . r (1 g) (2 g) (3 g) (4 g) (5 g) (6 g) (7 g) (8 g) (9 g) (10 g) (11 g) (12 g) (13 g) (14 g) (15 g) (16 g) (17 g) (18 g) (19 g) # return a new row with a function applied to each element func-to-row = \g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 r . r (g 1) (g 2) (g 3) (g 4) (g 5) (g 6) (g 7) (g 8) (g 9) (g 10) (g 11) (g 12) (g 13) (g 14) (g 15) (g 16) (g 17) (g 18) (g 19) # to calculate the value: # 1) get the first result by applying the first cell to the function 'first' # 2) get the next result for every other element by applying previous result to the function 'f' and applying the result of that to the row element # 3) get the final value by applying the final result to the function 'last' rowReduce = \first g last 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 . 1 first g 2 g 3 g 4 g 5 g 6 g 7 g 8 g 9 g 10 g 11 g 12 g 13 g 14 g 15 g 16 g 17 g 18 g 19 last empty = row e e e e e e e e e e e e e e e e e e e arow1 = row e e e e e a1 e a1 e a1 e a1 e a1 e e e e e gridStart = row arow1 empty arow1 empty arow1 empty arow1 empty empty empty empty empty empty empty empty empty empty empty empty shipStart = row e e e e e e e e e s e e e e e e e e e # grid functions identity = \x . x ignore = \x . row onFirstEmpty = \1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 . 1 identity ignore ignore ignore ignore # compare a cell with the first row element. If they're both e, return a cell with e otherwise return one of the non-e values check1 = \n r . r \m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 m11 m12 m13 m14 m15 m16 m17 m18 m19 . cell (n m1 n n n n) check19 = \n r . r \m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 m11 m12 m13 m14 m15 m16 m17 m18 m19 . cell (n m19 n n n n) isAllFirstEmpty = rowReduce cellA check1 isE isAllLastEmpty = rowReduce cellZ check19 isE allLeft = row-to-func left allRight = row-to-func right # counter counter = \1 2 3 4 5 6 7 8 9 10 11 12 c . c 1 2 3 4 5 6 7 8 9 10 11 12 cNext = \1 2 3 4 5 6 7 8 9 10 11 12 c . c 2 3 4 5 6 7 8 9 10 11 12 1 cTrue = \1 2 3 4 5 6 7 8 9 10 11 12 . 1 slowest = counter t f f f f f f f f f f f slower = counter t f f f f f t f f f f f slow = counter t f f f t f f f t f f f fast = counter t f f t f f t f f t f f faster = counter t f t f t f t f t f t f fastest = counter t t t t t t t t t t t t # game functions cflip = \n . n e s a2 a1 m flip = func-to-row cflip allFlip = row-to-func flip start = \statef . statef gridStart shipStart t slowest checkDir = \grid left? . left? (grid isAllFirstEmpty) (not (grid isAllLastEmpty)) next = \grid ship left? ctr statef . (\dir . statef (ctr cTrue (grid (dir allLeft allRight) allFlip) grid) ship dir (ctr cNext)) (checkDir grid left?) #events moveLeft = \grid ship left? ctr . next grid (ship (ship onFirstEmpty left)) left? ctr moveRight = \grid ship left? ctr . next grid (ship (ship right onFirstEmpty right)) left? ctr stay = \grid ship left? ctr . next grid ship left? ctr fire = \grid ship left? ctr . next (missile grid ship) ship left? ctr # accessors first = \a b c d . a second = \a b c d . b num = \n 0 1 2 3 4 . n 0 1 2 3 4 |
Here's my simplistic version of "space invaders". It's not as deluxe as the real one, but the point is to show how you might make a video game with Lambda Calculus.
The only thing that works right now is the left and right arrow keys :).
The "Code" section shows all of the Lambda Calulus code. JavaScript provides the key event (or an empty key event) and the game state to a Lambda Calculus function to calculate the next state of the game. Then, it uses other Lambda Calculus functions to inspect the current state so it can display it.
The state is a Lambda Calculus function and the key events are functions as well: moveLeft, moveRight, stay, and fire. To get the next state, JavaScript calls (state event), which returns another state (which is also a function, of course). The first state is equal to (start), which provides the aliens' and the ship's initial positions.
The screen is a grid of values, with a row of values underneath. A row has 19 values in it, so it's a function which applies its argument to its 19 values. The grid is really a "row of rows". You can use (left) and (right) to rotate the values and (get1) to get the first value. The base values are numbers from 0 to 4, represented with 5 argument functions that return the Nth argument, depending on which number the function represents.
The only thing that works right now is the left and right arrow keys :).
The "Code" section shows all of the Lambda Calulus code. JavaScript provides the key event (or an empty key event) and the game state to a Lambda Calculus function to calculate the next state of the game. Then, it uses other Lambda Calculus functions to inspect the current state so it can display it.
The state is a Lambda Calculus function and the key events are functions as well: moveLeft, moveRight, stay, and fire. To get the next state, JavaScript calls (state event), which returns another state (which is also a function, of course). The first state is equal to (start), which provides the aliens' and the ship's initial positions.
The screen is a grid of values, with a row of values underneath. A row has 19 values in it, so it's a function which applies its argument to its 19 values. The grid is really a "row of rows". You can use (left) and (right) to rotate the values and (get1) to get the first value. The base values are numbers from 0 to 4, represented with 5 argument functions that return the Nth argument, depending on which number the function represents.