Programming with Nothing

We love Ruby for being powerful & expressive, but how much power does Ruby have if you remove all of its datatypes except for Proc and all of its features except for Proc.new and Proc#call?

The answer is roughly "the same as before", computationally speaking, but I show this practically by demonstrating proc-only Ruby implementations (i.e. Church encodings) of the booleans, the integers, lists etc and using them to build executable programs. If you haven't seen this before, you may be surprised by how far you can get without any of the "fundamental" operations and datatypes of a conventional programming language.

I'm mostly interested in the parlour game of building these representations and showing how they work; there wasn't time to go into much detail, give much motivation, or assemble much of a broad thread. So this is a fairly practical and hackish exploration of how to build simple datatypes in Ruby using only procs rather than a protracted meditation on the nature of computation.

Given at Ru3y Manor (http://rubymanor.org/3). There's a video of this talk at http://rubymanor.org/3/videos/programming_with_nothing/. The accompanying code is at https://github.com/tomstuart/nothing, and an article version is available at https://tomstu.art/programming-with-nothing.

Transcript

1. PROGRAMMING @tomstuart — RU3Y MANOR — 2011-10-29 WITH NOTHING
2. RUBY I LOVE
3. expressive flexible beautiful loads of language features loads of core functionality loads of standard libraries loads of third-party libraries
4. RUBY LET’S RUIN
5. How much can Ruby do if we remove all its features?
6. no gems no standard library no modules no classes no objects no methods
7. no control flow no assignment no arrays no strings no numbers no booleans
8. GAME JUST A
9. NOT SOFTWARE ENGINEERING ADVICE
10. HERE ARE THE RULES
11. create procs call procs (abbreviate with constants)
12. HERE IS THE GOAL
13. ” Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”. “ — Imran Ghory
14. LET’S TALK ABOUT PROCS
15. Procs are just plumbing. lambda { |x| x + 1 }.call(41) = 41 + 1 The rest of the language does the actual work.
16. Procs don’t need multiple arguments.
17. lambda { |x, y| x + y }.call(3, 4) is the same as lambda { |x| lambda { |y| x + y } }.call(3).call(4)
18. The only way to use the body of a proc is to call it.
19. lambda { |x| p.call(x) } If p is a proc, then is the same as just p
20. SYNTAX TIME STOP
21. Proc.new { |x| x + 1 } proc { |x| x + 1 } lambda { |x| x + 1 } -> x { x + 1 } Creating a proc: 1.9 1.8
22. 1.9 1.8 p === 41 Calling a proc: p.call(41) p[41] p.(41)
23. I’m going to say: lambda { |x| x + 1 }.call(41) Instead of: -> x { x + 1 }[41]
24. GO
25. (1..100). if (n % 15).zero? elsif (n % 3).zero? elsif (n % 5).zero? else end end each puts puts puts puts 'FizzBuzz' 'Fizz' 'Buzz' n.to_s do |n|
26. (1..100). if (n % 15).zero? elsif (n % 3).zero? elsif (n % 5).zero? else end end 'FizzBuzz' 'Fizz' 'Buzz' n.to_s map do |n|
27. Numbers
28. How do we represent numbers using no data, only code? All our code can do is make or call a proc.
29. Represent a number n with code that calls a proc n times.
30. def zero(proc, x) x end def one(proc, x) proc[x] end def two(proc, x) proc[proc[x]] end def three(proc, x) proc[proc[proc[x]]] end
31. ZERO = -> p { -> x { x } } ONE = -> p { -> x { p[x] } } TWO = -> p { -> x { p[p[x]] } } THREE = -> p { -> x { p[p[p[x]]] } }
32. def to_integer(proc) proc[-> n { n + 1 }][0] end >> to_integer(ZERO) => 0 >> to_integer(THREE) => 3
33. FIVE = -> p { -> x { p[p[p[p[p[x]]]]] } } FIFTEEN = -> p { -> x { p[p[p[p[p[p[p[p[p[ p[p[p[p[p[p[x]]]]]]]]]]]]]]] } } HUNDRED = -> p { -> x { p[p[p[p[p[p[p[p[p[ p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[ p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[ p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[ p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[ p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]] ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] ]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] } }
34. 1 100 15 3 5 ( if (n % 'FizzBuzz' elsif (n % 'Fizz' elsif (n % 'Buzz' else n.to_s end end ).zero? ).zero? ).zero? .. ).map do |n|
35. ONE HUNDRED FIFTEEN THREE FIVE ( if (n % 'FizzBuzz' elsif (n % 'Fizz' elsif (n % 'Buzz' else n.to_s end end ).zero? ).zero? ).zero? .. ).map do |n|
36. This code doesn’t work: the numbers aren’t Fixnums. The numeric operations must be replaced too.
37. Booleans
38. How do we represent booleans using no data, only code?
39. Booleans are used for choosing between two options. Represent a boolean with code that chooses one of two values.
40. def true(x, y) x end def false(x, y) y end
41. TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } }
42. def to_boolean(proc) proc[true][false] end >> to_boolean(TRUE) => true >> to_boolean(FALSE) => false
43. def if(proc, x, y) proc[x][y] end
44. b [x] } -> x { } IF = -> b { TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } } -> y { [y] }
45. b [x] -> x { } } IF = -> b { TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } }
46. b } IF = -> b { TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } }
47. b IF = -> b { } TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } } proc [true][false] def to_boolean(proc) end
48. proc [true][false] def to_boolean(proc) end b IF = -> b { } TRUE = -> x { -> y { x } } FALSE = -> x { -> y { y } } IF[ ]
49. (n % THREE).zero? (n % FIVE).zero? (ONE..HUNDRED).map do |n| (n % FIFTEEN).zero? 'FizzBuzz' 'Fizz' 'Buzz' n.to_s end if elsif elsif else end
50. (n % THREE).zero? (n % FIVE).zero? (ONE..HUNDRED).map do |n| (n % FIFTEEN).zero? 'FizzBuzz' 'Fizz' 'Buzz' n.to_s end IF[ ][ ][IF[ ][ ][IF[ ][ ][ ]]]
51. Predicates
52. if == 0 else end false true n end def zero?(n) ZERO = -> p { -> x { x } } ONE = -> p { -> x { p[x] } } TWO = -> p { -> x { p[p[x]] } } THREE = -> p { -> x { p[p[p[x]]] } }
53. end [-> x { }][ ] false true n def zero?(n) ZERO = -> p { -> x { x } } ONE = -> p { -> x { p[x] } } TWO = -> p { -> x { p[p[x]] } } THREE = -> p { -> x { p[p[p[x]]] } }
54. IS_ZERO = -> n { n[-> x { FALSE }][TRUE] } >> to_boolean(IS_ZERO[ZERO]) => true >> to_boolean(IS_ZERO[THREE]) => false
55. ( ).zero? ( ).zero? ( ).zero? (ONE..HUNDRED).map do |n| IF[ 'FizzBuzz' ][IF[ 'Fizz' ][IF[ 'Buzz' ][ n.to_s ]]] end ][ ][ ][ n % FIFTEEN n % THREE n % FIVE
56. ][ ][ ][ IS_ZERO[ ] IS_ZERO[ ] IS_ZERO[ ] n % FIFTEEN n % THREE n % FIVE (ONE..HUNDRED).map do |n| IF[ 'FizzBuzz' ][IF[ 'Fizz' ][IF[ 'Buzz' ][ n.to_s ]]] end
57. Numeric operations
58. Here’s some basic arithmetic I made earlier: INCREMENT = -> n { -> f { -> x { f[n[f][x]] } } } DECREMENT = -> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }] [-> y { x }][-> y { y }] } } } ADD = -> m { -> n { n[INCREMENT][m] } } SUBTRACT = -> m { -> n { n[DECREMENT][m] } } MULTIPLY = -> m { -> n { n[ADD[m]][ZERO] } } POWER = -> m { -> n { n[MULTIPLY[m]][ONE] } }
59. def mod(m, n) if n <= m mod(m - n, n) else m end end
60. m def less_or_equal?(m, n) end - <= 0 n
61. n m def less_or_equal?(m, n) end IS_ZERO[SUBTRACT[ ][ ]]
62. IS_LESS_OR_EQUAL = -> m { -> n { IS_ZERO[SUBTRACT[m][n]] } }
63. def mod(m, n) if n <= m mod(m - n, n) else m end end
64. MOD = -> m { -> n { IF[IS_LESS_OR_EQUAL[n][m]][ MOD[SUBTRACT[m][n]][n] ][ m ] } }
65. PROBLEM
66. >> to_integer(MOD[THREE][TWO]) SystemStackError: stack level too deep
67. Ruby’s if/else statement only evaluates one of its two blocks. Our IF implementation takes two values, not blocks to evaluate.
68. MOD[SUBTRACT[m][n]][n] ][ m ] } } MOD = -> m { -> n { IF[IS_LESS_OR_EQUAL[n][m]][
69. -> x { [x] } MOD[SUBTRACT[m][n]][n] ][ m ] } } MOD = -> m { -> n { IF[IS_LESS_OR_EQUAL[n][m]][
70. >> to_integer(MOD[THREE][TWO]) => 1 >> to_integer(MOD[ POWER[THREE][THREE] ][ ADD[THREE][TWO] ]) => 2
71. ANOTHER PROBLEM
72. = -> m { -> n { IF[IS_LESS_OR_EQUAL[n][m][ -> x { [x] } [SUBTRACT[m][n]][n] ][ m ] } } MOD MOD This is not an abbreviation.
73. We can solve this problem with the “Y combinator”, a famous piece of helper code for defining recursive functions.
74. Y = -> f { -> x { f[x[x]] } [-> x { f[x[x]] }] }
75. Actually, this loops forever too. We need a modified version.
76. ] } ] }] } x[x] x[x] = -> f { -> x { f[ [-> x { f[ Y
77. ] } ] }] } x[x] x[x] = -> f { -> x { f[ [-> x { f[ Z -> y { [y] } -> y { [y] }
78. [SUBTRACT[m][n]][n][x] -> m { -> n { MOD = IF[IS_LESS_OR_EQUAL[n][m]][ -> x { } ][ m ] } } MOD
79. [SUBTRACT[m][n]][n][x] -> m { -> n { MOD = IF[IS_LESS_OR_EQUAL[n][m]][ -> x { } ][ m ] } } Z[-> f { f }]
80. (ONE..HUNDRED).map do |n| IF[IS_ZERO[ 'FizzBuzz' ][IF[IS_ZERO[ 'Fizz' ][IF[IS_ZERO[ 'Buzz' ][ n.to_s ]]] end FIFTEEN THREE FIVE % % % n n n ]][ ]][ ]][
81. ]][ ]][ ]][ FIFTEEN THREE FIVE MOD[ ][ ] MOD[ ][ ] MOD[ ][ ] (ONE..HUNDRED).map do |n| IF[IS_ZERO[ 'FizzBuzz' ][IF[IS_ZERO[ 'Fizz' ][IF[IS_ZERO[ 'Buzz' ][ n.to_s ]]] end n n n
82. Lists
83. PAIR = -> x { -> y { -> f { f[x][y] } } } LEFT = -> p { p[-> x { -> y { x } } ] } RIGHT = -> p { p[-> x { -> y { y } } ] }
84. EMPTY = PAIR[TRUE][TRUE] UNSHIFT = -> l { -> x { PAIR[FALSE][PAIR[x][l]] } } IS_EMPTY = LEFT FIRST = -> l { LEFT[RIGHT[l]] } REST = -> l { RIGHT[RIGHT[l]] }
85. def range(m, n) if m <= n range(m + 1, n).unshift(m) else [] end end
86. RANGE = Z[-> f { -> m { -> n { IF[IS_LESS_OR_EQUAL[m][n]][ -> x { UNSHIFT[f[INCREMENT[m]][n]][m][x] } ][ EMPTY ] } } }]
87. ( .. ) IF[IS_ZERO[MOD[n][FIFTEEN]]][ 'FizzBuzz' ][IF[IS_ZERO[MOD[n][THREE]]][ 'Fizz' ][IF[IS_ZERO[MOD[n][FIVE]]][ 'Buzz' ][ n.to_s ]]] end ONE HUNDRED .map do |n|
88. IF[IS_ZERO[MOD[n][FIFTEEN]]][ 'FizzBuzz' ][IF[IS_ZERO[MOD[n][THREE]]][ 'Fizz' ][IF[IS_ZERO[MOD[n][FIVE]]][ 'Buzz' ][ n.to_s ]]] end RANGE[ ][ ] ONE HUNDRED .map do |n|
89. FOLD = Z[-> f { -> l { -> x { -> g { IF[IS_EMPTY[l]][ x ][ -> y { g[f[REST[l]][x][g]][FIRST[l]][y] } ] } } } }] MAP = -> k { -> f { FOLD[k][EMPTY][ -> l { -> x { UNSHIFT[l][f[x]] } } ] } }
90. n IF[IS_ZERO[MOD[n][FIFTEEN]]][ 'FizzBuzz' ][IF[IS_ZERO[MOD[n][THREE]]][ 'Fizz' ][IF[IS_ZERO[MOD[n][FIVE]]][ 'Buzz' ][ n.to_s ]]] .map do | | end RANGE[ONE][HUNDRED]
91. RANGE[ONE][HUNDRED] n IF[IS_ZERO[MOD[n][FIFTEEN]]][ 'FizzBuzz' ][IF[IS_ZERO[MOD[n][THREE]]][ 'Fizz' ][IF[IS_ZERO[MOD[n][FIVE]]][ 'Buzz' ][ n.to_s ]]] MAP[ ][-> { }]
92. Strings
93. Strings can be represented as lists of numbers. Just choose an encoding.
94. def to_char(c) '0123456789BFiuz'.slice(to_integer(c)) end def to_string(s) to_array(s).map { |c| to_char(c) }.join end
95. TEN = MULTIPLY[TWO][FIVE] RADIX = TEN TO_STRING = Z[-> f { -> n { PUSH[ IF[IS_LESS_OR_EQUAL[n][DECREMENT[RADIX]]][ EMPTY ][ -> x { f[DIV[n][RADIX]][x] } ] ][MOD[n][RADIX]] } }]
96. MAP[RANGE[ONE][HUNDRED]][-> n { IF[IS_ZERO[MOD[n][FIFTEEN]]][ ][IF[IS_ZERO[MOD[n][THREE]]][ ][IF[IS_ZERO[MOD[n][FIVE]]][ ][ ]]] }] .to_s n 'FizzBuzz' 'Fizz' 'Buzz'
97. 'FizzBuzz' 'Fizz' 'Buzz' MAP[RANGE[ONE][HUNDRED]][-> n { IF[IS_ZERO[MOD[n][FIFTEEN]]][ ][IF[IS_ZERO[MOD[n][THREE]]][ ][IF[IS_ZERO[MOD[n][FIVE]]][ ][ ]]] }] TO_STRING[ ] n
98. FIZZBUZZ FIZZ BUZZ MAP[RANGE[ONE][HUNDRED]][-> n { IF[IS_ZERO[MOD[n][FIFTEEN]]][ ][IF[IS_ZERO[MOD[n][THREE]]][ ][IF[IS_ZERO[MOD[n][FIVE]]][ ][ ]]] }] TO_STRING[ ] n
99. The constants are just abbreviations. Replace each constant with its definition to get the full program.
100. -> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { ->g { -> b { b }[-> p { p[-> x { -> y { x } } ] }[l]][x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[-> x {-> y { y } } ] }[l]] }[l]][y] }] } } } }][k][-> x { - > y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> l { -> x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x] [y] } } }[x][l]] } }[l][f[x]] } }] } }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[->y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[m][n]][-> x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[f[-> n { -> f { -> x { f[n[f][x]] } } }[m]][n]][m][x] }][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]] } } }][-> f { -> x { f[x] } }][-> f { -> x { f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f [f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] ]]]]]]]]]]]]]] }}]][-> n { -> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }] [m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]][n][x] }][m] } } }][n][-> f { -> x { f[f[f[f[f[f[f[f[f[f[f[f[f[f[f[x]]]]]]]]]]]]]]] } }]]][-> k { -> l { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } } ] }[l]][x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[- > x { -> y { y } } ] }[l]] }[l]][y] }] } } } }][k][l][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }] } }[-> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } } ] }[l]][x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][y] }] } } } }][k][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> l { -> x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x] [l]] } }[l][f[x]] } }] } }[-> l { -> x { -> x {-> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x] [y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[->l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x] [l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> f {-> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[x]] } }]][-> f { -> x { f[x] } }]][-> m { -> n { n[-> n { -> f { -> x { f[n[f] [x]] } } }][m] } }[-> m { -> n { n[-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { -> x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]]][-> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } } ] }[l]] [x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] } [l]][y] }] } } } }][k][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> l { -> x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][- > x { -> y { -> f { f[x][y] } } }[x][l]] } }[l][f[x]] } }] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[->l { - > x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { - > y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x] [y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[f[x]]] } }]][->f { -> x { x } }]][-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[-> m { -> n { n[-> m { ->n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { -> x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]]]][-> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { - > m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { f[->m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]][n][x] }][m] } } }][n][-> f { -> x { f[f[f[x]]] } }]]][-> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } } ] }[l]] [x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] } [l]][y] }] } } } }][k][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> l { -> x { -> l { -> x {-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[l][f[x]] } }] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][->x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[- > x { -> y { x } }][-> x { -> y { x } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[x]] } }]][-> f { -> x { f[x] } }]][-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[-> m { -> n { n[-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { -> x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]]][-> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { ->m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }] [m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]][n][x] }][m] } } }][n][-> f { -> x { f[f[f[f[f[x]]]]] } }]]][-> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[->x { -> y { x } } ] }[l]][x] [-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]] [y] }] } } } }][k][-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][-> l { ->x { -> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[l][f[x]] } }] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x {-> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[- >x { -> y { x } }][-> x { -> y { x } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[f[f[x]]]] } }]][-> f { -> x { f[f[f[x]]] } }]][-> f { -> x { x } }]][-> m { -> n { n[-> n { - > f { -> x { f[n[f][x]] } } }][m] } }[-> m { -> n { n[-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { -> x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]]][-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> n { -> l { -> x { -> k { -> l { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } } ] }[l]][x][-> y { g[f[-> l { -> p { p[-> x { -> y { y } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] } [l]][x][g]][-> l { -> p { p[-> x { -> y { x } } ] }[-> p { p[-> x { -> y { y } } ] }[l]] }[l]][y] }] } } } }][k][l][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }] [-> x { -> y { -> f { f[x][y] } } }[x][l]] } }] } }[l][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x {-> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][x]] } }[-> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { -> x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]]][-> x { -> y { -> f { f[x] [y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][ -> x { f[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[->f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[- > x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { -> n { -> f { -> x { f[n[f][x]] } } }[f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]][n]][x] }][-> f { -> x { x } }] } } }][n] [-> m { -> n { n[-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { -> x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]][x] } ]][-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { ->x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][-> y { x }][-> y { y }] } } }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> f { -> x { n[-> g { -> h { h[g[f]] } }][- > y { x }][-> y { y }] } } }][m] } }[m][n]][n][x] }][m] } } }][n][-> m { ->n { n[-> m { -> n { n[-> n { -> f { -> x { f[n[f][x]] } } }][m] } }[m]][-> f { -> x { x } }] } }[-> f { ->x { f[f[x]] } }][-> f { -> x { f[f[f[f[f[x]]]]] } }]]] } }][n]]]] }]
101. WHY
102. Within these constraints, we can build any data structure and implement any algorithm.
103. There is no data, only code.
104. No programming language has more computational power than -> and [].
105. What differentiates languages?
106. expressiveness aesthetic appeal safety vs. flexibility performance ecosystem community
107. Ruby is in our sweet spot. There are many languages like it, but this one is ours.
108. describe 'natural numbers' do specify { ADD[representation_of 2][representation_of 3].should represent 2 + 3 } specify { MULTIPLY[representation_of 2][representation_of 3].should represent 2 * 3 } specify { POWER[representation_of 2][representation_of 3].should represent 2 ** 3 } specify { SUBTRACT[representation_of 3][representation_of 2].should represent 3 - 2 } context 'with booleans' do (0..3).each do |n| specify { IS_ZERO[representation_of n].should represent n.zero? } specify { IS_EQUAL[representation_of n][representation_of 2].should represent n == 2 } end end context 'with recursion' do (0..5).zip([1, 1, 2, 6, 24, 120]) do |n, n_factorial| specify { FACTORIAL[representation_of n].should represent n_factorial } end [0, 1, 11, 27].product([1, 3, 11]) do |m, n| specify { DIV[representation_of m][representation_of n].should represent m / n } specify { MOD[representation_of m][representation_of n].should represent m % n } end end context 'with strings' do specify { TO_STRING[representation_of 42].should represent '42' } end end https://github.com/tomstuart/nothing
109. https://github.com/tomstuart/nothing Implement ADD, MULTIPLY and POWER for natural numbers --- a/lib/nothing.rb +++ b/lib/nothing.rb @@ -9,9 +9,9 @@ module Nothing TIMES = -> n { -> f { -> x { n[f][x] } } } INCREMENT = -> n { -> f { -> x { f[n[f][x]] } } } - # ADD = - # MULTIPLY = - # POWER = + ADD = -> m { -> n { n[INCREMENT][m] } } + MULTIPLY = -> m { -> n { n[ADD[m]][ZERO] } } + POWER = -> m { -> n { n[MULTIPLY[m]][ONE] } } # DECREMENT = # SUBTRACT = --- a/spec/nothing_spec.rb +++ b/spec/nothing_spec.rb @@ -11,9 +11,9 @@ describe Nothing do specify { TIMES[representation_of 3][-> s { s + 'o' }]['hell'].should == 'hellooo' } specify { INCREMENT[representation_of 2].should represent 2 + 1 } - specify { pending { ADD[representation_of 2][representation_of 3].should represent 2 + 3 } } - specify { pending { MULTIPLY[representation_of 2][representation_of 3].should represent 2 * 3 } } - specify { pending { POWER[representation_of 2][representation_of 3].should represent 2 ** 3 } } + specify { ADD[representation_of 2][representation_of 3].should represent 2 + 3 } + specify { MULTIPLY[representation_of 2][representation_of 3].should represent 2 * 3 } + specify { POWER[representation_of 2][representation_of 3].should represent 2 ** 3 } specify { pending { DECREMENT[representation_of 3].should represent 3 - 1 } } specify { pending { SUBTRACT[representation_of 3][representation_of 2].should represent 3 - 2 } }
110. https://github.com/tomstuart/nothing Extract INJECT from SUM and PRODUCT --- a/lib/nothing.rb +++ b/lib/nothing.rb @@ -56,9 +56,11 @@ module Nothing FIRST = -> l { LEFT[RIGHT[l]] } REST = -> l { RIGHT[RIGHT[l]] } + INJECT = Z[-> f { -> l { -> x { -> g { IF[IS_EMPTY[l]][x][-> _ { f[REST[l]][g[x] [FIRST[l]]][g][_] }] } } } }] + RANGE = Z[-> f { -> x { -> y { IF[IS_LESS_OR_EQUAL][x][y][-> _ { UNSHIFT[x] [f[INCREMENT[x]][y]][_] }][EMPTY] } } }] - SUM = Z[-> f { -> l { IF[IS_EMPTY[l]][ZERO][-> _ { ADD[FIRST[l]][f[REST[l]]] [_] }] } }] - PRODUCT = Z[-> f { -> l { IF[IS_EMPTY[l]][ONE][-> _ { MULTIPLY[FIRST[l]][f[REST[l]]] [_] }] } }] + SUM = -> l { INJECT[l][ZERO][ADD] } + PRODUCT = -> l { INJECT[l][ONE][MULTIPLY] } # CONCAT = # PUSH = # REVERSE =
111. THANK YOU https://github.com/tomstuart/nothing tom@experthuman.com @tomstuart