3 ms·

Church numerals are essentially like the unary notation. 1. 0 : Think of 'y' as a blank blackboard in (\ x (\ y . y )), because when you apply it to two argume

• naikrovek 6y ago
  What's x represent? What's y represent? What's the backslash represent? What's the period represent? BASIC questions for things no one thinks to teach. Ever. People who teach this only know how to teach it to people who already know it. Us lower-class ignoramuses can do without, I guess. Thanks for trying, though, seriously.
  • sn41 6y ago
    No need to be aggressive, I am not being condescending. x and y are variables. \ is a notation people use because you cannot type lambdas in ASCII. For the basic rules regarding application, you need to understand substitution rules.
  • chriswarbo 6y ago
    We can translate it quite easily into Javascript, if you're familiar with that: > What's x represent? In JS this would be written as the variable 'x' > What's y represent? In JS this would be written as the variable 'y' > What's the backslash represent? In JS this would be written as the keyword 'function' > What's the period represent? In JS this would be the keyword 'return', or as '=>' using function arrow notation. For example, '\ x (\ y . y )' (AKA zero) in JS would be: function(x) { return function(y) { return y; }; } Or, with arrow notation, as simply 'x => (y => y)' The number one would be 'x => (y => x(y))' The number two would be 'x => (y => x(x(y)))' And so on: we represent the number N as functions taking two arguments, which apply the first argument to the second argument N times. Lambda calculus functions can only take one argument at a time, hence we need two nested functions in order to take two arguments. Javascript functions can take more than one argument, so we could do this instead '(x, y) => x(x(y))' The argument names are arbitrary; here they're 'x' and 'y', but we could use 'foo' and 'bar', 'hello' and 'world', or whatever. If you want a more intuitive idea about "how" these work, and how to use them, then you can think of each number N as a loop performing N iterations. The first argument is the 'loop body' or 'stepping function', the second argument is the initial value/accumulator. For example, if we want to add two numbers A and B, which are represented in this way, we can make a new number (AKA function taking two arguments AKA loop) which runs the A loop, with the result of running the B loop as its initial value (using the same 'step' each time), e.g. \x. \y. A x (B x y) Or, in JS notation and more descriptive variable names: add = A => B => step => init => A(step)(B(step)(init)) We can multiply A and B by looping: start with zero (AKA init), then add B on to it A times: zero = step => init => init times = A => B => step => init => A(add(B))(zero)(step)(init) Notice that 'times' doesn't use its 'step' and 'init' arguments directly, they're just passed straight into the result. That's just busy-work, so we can simplify it away (this is called "eta reduction"): times = A => B => A(add(B))(zero) We can pass in anything we like as our 'step' and 'init' arguments. Here's how to recover native JS numbers: churchToInt = A => A(x => x + 1)(0) Encodings of other data structures work in a similar way: - We write a function which takes in one function for each 'case' ('successor' or 'zero', if we're encoding numbers using Peano's axioms; 'true' or 'false' if we're encoding booleans; 'nil' or 'cons' if we're encoding a list; etc.) - We return the argument corresponding to the value we've encoded (e.g. an encoding of zero returns the argument corresponding to zero; an encoding of true returns the argument corresponding to true; etc.) - If we have a composite data structure, we first apply that argument to each of our nested values (e.g. a 'successor' value contains another number (its predecessor), so the argument corresponding to successor gets called with that value) Some examples: // Booleans have two cases, neither contain any sub-values true = T => F => T false = T => F => F // This only has one case, but it contains three sub-expressions (it's a triplet) // This is polymorphic in the type of 'red', 'green' and 'blue', but they could be // e.g. numbers colour = red => green => blue => x => x(red)(green)(blue) // A 4-tuple. If A, B, C and D are booleans then it's a nibble nibble = A => B => C => D => x => x(A)(B)(C)(D) // A pair. If HIGH and LOW are nibbles then it's a byte byte = HIGH => LOW => x => x(HIGH)(LOW) // Binary trees with values in the leaves leaf = VALUE => node => leaf => leaf(VALUE) node = LEFT => RIGHT => node => leaf => node(LEFT(node)(leaf))(RIGHT(node)(leaf)) // Some values, encoded using the above emptyNibble = nibble(false)(false)(false)(false) fullNibble = nibble(true)(true)(true)(true) emptyByte = byte(emptyNibble)(emptyNibble) fullByte = byte(fullNibble)(fullNibble) red = colour(fullByte)(emptyByte)(emptyByte) white = colour(fullByte)(fullByte)(fullByte)
    • naikrovek 6y ago
      You're trying so hard but it isn't sticking for me. Maybe I am too stupid. Not seeking pity! Being honest with myself
      • chriswarbo 6y ago
        It's just data modelling, except instead of trying to fit our data into some arrangement of pointers (in a C-like language), or some combination of numbers/strings/lists/dicts (in a scripting language), or some algebraic datastructure (in an ML/Haskell-like language), instead we're trying to fit our data into some arrangement of anonymous functions. I picked JS syntax since it's familiar to many people. If you're more comfortable with some other language, maybe try translating those examples into that language (the language must support first-class/anonymous functions; trying this with e.g. function pointers in C would be even more horrible!) Then just play around with these functions a little; get a feel for how they behave; e.g. you could call them with strings like "foo", "bar", etc. and see what they return. Maybe write some input/output tables to see what's happening. Then imagine that your language only has functions; nothing else. Try to find an alternative to if/else which only uses functions (hint: the 'true' and 'false' definitions above will help!). You've already seen how to write finite loops (that's how numbers are represented); try to write an infinite loop (this is easier if you're giving names to functions, like I did with 'add', 'times', etc. above). Then try writing an anonymous infinite loop, only using anonymous functions (hint: look at the URL of this site). This is largely an academic exercise, but it can bring a deeper appreciation/understanding of what we can do with functions. Smalltalk famously uses a similar approach to this for branching (myBool ifTrue: x else: y) and looping (myNum timesRepeat: x); Smalltalk had a huge influence on OOP and scripting languages.