Code
Diff
  • def purple():
        return 'purple'
    
    def red():
        raise ZeroDivisionError
    
    def blue():
        return (1/3) * 3
  • 1
    ...
    
    1+
    def purple():
    
    2+
        return 'purple'
    
    3+
    4+
    def red():
    
    5+
        raise ZeroDivisionError
    
    6+
    7+
    def blue():
    
    8+
        return (1/3) * 3
    
Code
Diff
  • const code = String.raw`
    true  = \ a b . a
    false = \ a b . b
    
    zero = false
    succ = \ n f x . f (n f x)
    
    y = \ f . (\ x . f (x x)) (\ x . f (x x))
    
    count = y (\ counter n b . b (counter (succ n)) (n) ) zero
    
    res = count true true true true false
    `
  • 11
    const code = String.raw`
    
    2
    true = \ a _ . a
    
    3
    false = \ _ b . b
    
    4
    id = \ x . x
    
    2+
    true  = \ a b . a
    
    3+
    false = \ a b . b
    
    55
    6
    pair = \ a b c . c a b
    
    7
    nil = \ p . p false ()
    
    8
    cons = \ v xs . pair true (pair v xs)
    
    5+
    zero = false
    
    6+
    succ = \ n f x . f (n f x)
    
    99
    10
    sub = \ a b . b true (\ _ . false) a (sub (a a id) (b () id))
    
    8+
    y = \ f . (\ x . f (x x)) (\ x . f (x x))
    
    1111
    12
    head = \ xs . xs false true
    
    13
    tail = \ xs . xs false false
    
    14
    null = \ xs. xs true false true
    
    10+
    count = y (\ counter n b . b (counter (succ n)) (n) ) zero
    
    1515
    16
    ss = \ xs . sub (head (tail xs)) (head xs)
    
    17
    18
    d = \ xs . null xs nil (null (tail xs) nil (cons (ss xs) (d (tail xs))))
    
    19
    delta = \ n xs . n xs (\ m . delta m (d xs))
    
    12+
    res = count true true true true false
    
    2020
    `
    

Background

Consider a list of numbers a. Now let us define a new list b where an element of b at index i is equal to a[i+1]-a[i]. For example:

a = < 3, 5, 8, 13 >
b = < 2, 3, 5 >

For this kata, we will say that the list b is the "1st delta" of a. If we applied the process again to get c = < 1, 2 >, then c would be the "2nd delta" of a.

Task

Write a function delta which accepts a number n, and a list of numbers xs. The function must return a list of numbers which is the "nth delta" of xs.

Encodings

  • purity -> LetRec
  • true, false -> Church encoding
  • Number -> Scott encoding
  • nil -> an empty list: \ p -> p false ()
  • cons -> add a value to a string: \ val list b1 . b1 true (\ b2 . b2 val list)

Notes

  • The input list may be finite, or infinite
  • If the input is infinite, the output should also be infinite
Code
Diff
  • const code = String.raw`
    true = \ a _ . a
    false = \ _ b . b
    id = \ x . x
    
    pair = \ a b c . c a b
    nil = \ p . p false ()
    cons = \ v xs . pair true (pair v xs)
    
    sub = \ a b . b true (\ _ . false) a (sub (a a id) (b () id))
    
    head = \ xs . xs false true
    tail = \ xs . xs false false
    null = \ xs. xs true false true
    
    ss = \ xs . sub (head (tail xs)) (head xs)
    
    d = \ xs . null xs nil (null (tail xs) nil (cons (ss xs) (d (tail xs))))
    delta = \ n xs . n xs (\ m . delta m (d xs))
    `
  • 11
    const code = String.raw`
    
    2
    succ = \ n f x . f (n f x)
    
    3
    pair = \a.\b.\c.c a b
    
    4
    fst = \pair.pair (\a.\_.a)
    
    5
    snd = \pair.pair (\_.\b.b)
    
    6
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    
    7
    next = \prev.pair (snd prev) (plus prev)
    
    8
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    
    9
    `
    
    10
    11
    // Stress testing -- "LetRec", "BinaryScott"
    
    12
    // Testing implementation of a "String" - ie. Arrays and related functions
    
    13
    const stress = String.raw`
    
    14
    # bools
    
    2+
    true = \ a _ . a
    
    3+
    false = \ _ b . b
    
    1515
    id = \ x . x
    
    16
    true = \ a b . a
    
    17
    false = \ a b . b
    
    18
    not = \ b . b false true
    
    19
    and = \ a b . a b false
    
    20
    or = \ a b . a true b
    
    21
    xor = \ a b . a (b false true) b
    
    29
    even = \ n . not (odd n)
    
    30
    mul2 = \ n _ f _ . f n
    
    31
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    32
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    6+
    pair = \ a b c . c a b
    
    7+
    nil = \ p . p false ()
    
    8+
    cons = \ v xs . pair true (pair v xs)
    
    9+
    10+
    sub = \ a b . b true (\ _ . false) a (sub (a a id) (b () id))
    
    11+
    12+
    head = \ xs . xs false true
    
    13+
    tail = \ xs . xs false false
    
    14+
    null = \ xs. xs true false true
    
    15+
    16+
    ss = \ xs . sub (head (tail xs)) (head xs)
    
    3333
    34
    # arrays as foldr (strings)
    
    18+
    d = \ xs . null xs nil (null (tail xs) nil (cons (ss xs) (d (tail xs))))
    
    19+
    delta = \ n xs . n xs (\ m . delta m (d xs))
    
    3535
    `
    

Task

Using the string encoding described below, define a term hello which is equivalent to "Hello, world!"

Encodings

  • purity -> LetRec
  • true, false -> Church encoding
  • Number -> Church encoding (only used as chars)
  • char -> a number corrosponding to ascii code
  • nil -> an empty string: \ _ -> false
  • cons -> add a char to a string: \ char string b1 . b1 true (\ b2 . b2 char string)
Code
Diff
  • const code = String.raw`
    # bools
    true = \ a b . a
    false = \ a b . b
    
    # numbers
    zero = false
    succ = \ n f x . f (n f x)
    add = \ a b f x . a f (b f x)
    mul = \ a b f . a (b f)
    
    three = \ f x . f ( f ( f x ))
    ten = succ (mul three three)
    thirtytwo = succ (succ (mul ten three))
    thirtythree = succ thirtytwo
    fortyfour = succ (add ten thirtythree)
    seventytwo = mul (succ ( succ (add three three))) (mul three three)
    hundred = mul ten ten
    hundredone = succ hundred
    hundredeight = succ (add three (add three hundredone))
    hundredeleven = add three hundredeight
    hundredforteen = add three hundredeleven
    hundrednineteen = succ (succ (add three hundredforteen))
    
    # data
    pair = \ a b c . c a b
    nil = \ _ . false
    cons = \ c s . pair true (pair c s)
    
    # [72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33]
    hello = cons seventytwo 
           (cons hundredone 
           (cons hundredeight 
           (cons hundredeight 
           (cons hundredeleven 
           (cons fortyfour 
           (cons thirtytwo 
           (cons hundrednineteen 
           (cons hundredeleven
           (cons hundredforteen
           (cons hundredeight
           (cons hundred
           (cons thirtythree
           nil ))))))))))))
    `
  • 11
    const code = String.raw`
    
    2
    succ = \ n f x . f (n f x)
    
    3
    pair = \a.\b.\c.c a b
    
    4
    fst = \pair.pair (\a.\_.a)
    
    5
    snd = \pair.pair (\_.\b.b)
    
    6
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    
    7
    next = \prev.pair (snd prev) (plus prev)
    
    8
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    
    9
    `
    
    10
    11
    // Stress testing -- "LetRec", "BinaryScott"
    
    12
    // Testing implementation of a "String" - ie. Arrays and related functions
    
    13
    const stress = String.raw`
    
    1414
    # bools
    
    15
    id = \ x . x
    
    1616
    true = \ a b . a
    
    1717
    false = \ a b . b
    
    18
    not = \ b . b false true
    
    19
    and = \ a b . a b false
    
    20
    or = \ a b . a true b
    
    21
    xor = \ a b . a (b false true) b
    
    2222
    23
    # ints -- z = endbit, f = offbit, t = onbit
    
    24
    zero = \ z _ _ . z
    
    25
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    
    26
    bool = \ n . n false (\ _ . true) (\ _ . true)
    
    27
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    
    28
    odd = \ n . n false false true
    
    29
    even = \ n . not (odd n)
    
    30
    mul2 = \ n _ f _ . f n
    
    31
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    32
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    6+
    # numbers
    
    7+
    zero = false
    
    8+
    succ = \ n f x . f (n f x)
    
    9+
    add = \ a b f x . a f (b f x)
    
    10+
    mul = \ a b f . a (b f)
    
    11+
    12+
    three = \ f x . f ( f ( f x ))
    
    13+
    ten = succ (mul three three)
    
    14+
    thirtytwo = succ (succ (mul ten three))
    
    15+
    thirtythree = succ thirtytwo
    
    16+
    fortyfour = succ (add ten thirtythree)
    
    17+
    seventytwo = mul (succ ( succ (add three three))) (mul three three)
    
    18+
    hundred = mul ten ten
    
    19+
    hundredone = succ hundred
    
    20+
    hundredeight = succ (add three (add three hundredone))
    
    21+
    hundredeleven = add three hundredeight
    
    22+
    hundredforteen = add three hundredeleven
    
    23+
    hundrednineteen = succ (succ (add three hundredforteen))
    
    24+
    25+
    # data
    
    26+
    pair = \ a b c . c a b
    
    27+
    nil = \ _ . false
    
    28+
    cons = \ c s . pair true (pair c s)
    
    3333
    34
    # arrays as foldr (strings)
    
    30+
    # [72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33]
    
    31+
    hello = cons seventytwo 
    
    32+
           (cons hundredone 
    
    33+
           (cons hundredeight 
    
    34+
           (cons hundredeight 
    
    35+
           (cons hundredeleven 
    
    36+
           (cons fortyfour 
    
    37+
           (cons thirtytwo 
    
    38+
           (cons hundrednineteen 
    
    39+
           (cons hundredeleven
    
    40+
           (cons hundredforteen
    
    41+
           (cons hundredeight
    
    42+
           (cons hundred
    
    43+
           (cons thirtythree
    
    44+
           nil ))))))))))))
    
    3535
    `
    
Code
Diff
  • const code = String.raw`
    succ = \ n f x . f (n f x)
    pair = \a.\b.\c.c a b
    fst = \pair.pair (\a.\_.a)
    snd = \pair.pair (\_.\b.b)
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    next = \prev.pair (snd prev) (plus prev)
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    `
    
    // Stress testing -- "LetRec", "BinaryScott"
    // Testing implementation of a "String" - ie. Arrays and related functions
    const stress = String.raw`
    # bools
    id = \ x . x
    true = \ a b . a
    false = \ a b . b
    not = \ b . b false true
    and = \ a b . a b false
    or = \ a b . a true b
    xor = \ a b . a (b false true) b
    
    # ints -- z = endbit, f = offbit, t = onbit
    zero = \ z _ _ . z
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    bool = \ n . n false (\ _ . true) (\ _ . true)
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    odd = \ n . n false false true
    even = \ n . not (odd n)
    mul2 = \ n _ f _ . f n
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    # arrays as foldr (strings)
    `
  • 11
    const code = String.raw`
    
    22
    succ = \ n f x . f (n f x)
    
    33
    pair = \a.\b.\c.c a b
    
    44
    fst = \pair.pair (\a.\_.a)
    
    55
    snd = \pair.pair (\_.\b.b)
    
    66
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    
    77
    next = \prev.pair (snd prev) (plus prev)
    
    88
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    
    99
    `
    
    10+
    11+
    // Stress testing -- "LetRec", "BinaryScott"
    
    12+
    // Testing implementation of a "String" - ie. Arrays and related functions
    
    13+
    const stress = String.raw`
    
    14+
    # bools
    
    15+
    id = \ x . x
    
    16+
    true = \ a b . a
    
    17+
    false = \ a b . b
    
    18+
    not = \ b . b false true
    
    19+
    and = \ a b . a b false
    
    20+
    or = \ a b . a true b
    
    21+
    xor = \ a b . a (b false true) b
    
    22+
    23+
    # ints -- z = endbit, f = offbit, t = onbit
    
    24+
    zero = \ z _ _ . z
    
    25+
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    
    26+
    bool = \ n . n false (\ _ . true) (\ _ . true)
    
    27+
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    
    28+
    odd = \ n . n false false true
    
    29+
    even = \ n . not (odd n)
    
    30+
    mul2 = \ n _ f _ . f n
    
    31+
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    32+
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    33+
    34+
    # arrays as foldr (strings)
    
    35+
    `
    
Code
Diff
  • const text = String.raw`
    succ = \n f x. f (n f x)
    pair = \a.\b.\c.c a b
    fst = \pair.pair (\a.\_.a)
    snd = \pair.pair (\_.\b.b)
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    next = \prev.pair (snd prev) (plus prev)
    fib = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    `
    
    // Proof of laziness -- using Scott
    const lazy = String.raw`
    succ = \ n _ f . f n
    inf_list = \ n b . b n (inf_list (succ n))
    counter = inf_list 0
    `
    
    // Stress testing -- "LetRec", "BinaryScott"
    // Testing implementation of a "String" - ie. Arrays and related functions
    const stress = String.raw`
    # bools
    id = \ x . x
    true = \ a b . a
    false = \ a b . b
    not = \ b . b false true
    and = \ a b . a b false
    or = \ a b . a true b
    xor = \ a b . a (b false true) b
    
    # ints -- z = endbit, f = offbit, t = onbit
    zero = \ z _ _ . z
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    bool = \ n . n false (\ _ . true) (\ _ . true)
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    odd = \ n . n false false true
    even = \ n . not (odd n)
    mul2 = \ n _ f _ . f n
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    # arrays as foldr (strings)
    `
    
  • 1616
    `
    
    1717
    1818
    // Stress testing -- "LetRec", "BinaryScott"
    
    1919
    // Testing implementation of a "String" - ie. Arrays and related functions
    
    2020
    const stress = String.raw`
    
    2121
    # bools
    
    22+
    id = \ x . x
    
    2222
    true = \ a b . a
    
    2323
    false = \ a b . b
    
    2424
    not = \ b . b false true
    
    2525
    and = \ a b . a b false
    
    2626
    or = \ a b . a true b
    
    2727
    xor = \ a b . a (b false true) b
    
    2828
    2929
    # ints -- z = endbit, f = offbit, t = onbit
    
    3030
    zero = \ z _ _ . z
    
    3131
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    
    32
    pred = \ n z f t . n z (\ m . t (pred m)) f
    
    3333
    bool = \ n . n false (\ _ . true) (\ _ . true)
    
    34+
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    
    3434
    odd = \ n . n false false true
    
    3535
    even = \ n . not (odd n)
    
    3636
    mul2 = \ n _ f _ . f n
    
    3737
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    3838
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    3939
    4040
    # arrays as foldr (strings)
    
    4141
    `
    

Running compile on stress causes timeout.

Code
Diff
  • const code = String.raw`
    succ = \n f x. f (n f x)
    pair = \a.\b.\c.c a b
    fst = \pair.pair (\a.\_.a)
    snd = \pair.pair (\_.\b.b)
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    next = \prev.pair (snd prev) (plus prev)
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    `
    
    const stress = String.raw`
    # bools
    true = \ a b . a
    false = \ a b . b
    not = \ b . b false true
    and = \ a b . a b false
    or = \ a b . a true b
    xor = \ a b . a (b false true) b
    
    # ints -- z = endbit, f = offbit, t = onbit
    zero = \ z _ _ . z
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    pred = \ n z f t . n z (\ m . t (pred m)) f
    bool = \ n . n false (\ _ . true) (\ _ . true)
    odd = \ n . n false false true
    even = \ n . not (odd n)
    mul2 = \ n _ f _ . f n
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    # arrays as foldr (strings)
    `
  • 11
    const code = String.raw`
    
    22
    succ = \n f x. f (n f x)
    
    33
    pair = \a.\b.\c.c a b
    
    44
    fst = \pair.pair (\a.\_.a)
    
    55
    snd = \pair.pair (\_.\b.b)
    
    66
    plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
    
    77
    next = \prev.pair (snd prev) (plus prev)
    
    88
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    
    99
    `
    
    10+
    11+
    const stress = String.raw`
    
    12+
    # bools
    
    13+
    true = \ a b . a
    
    14+
    false = \ a b . b
    
    15+
    not = \ b . b false true
    
    16+
    and = \ a b . a b false
    
    17+
    or = \ a b . a true b
    
    18+
    xor = \ a b . a (b false true) b
    
    19+
    20+
    # ints -- z = endbit, f = offbit, t = onbit
    
    21+
    zero = \ z _ _ . z
    
    22+
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    
    23+
    pred = \ n z f t . n z (\ m . t (pred m)) f
    
    24+
    bool = \ n . n false (\ _ . true) (\ _ . true)
    
    25+
    odd = \ n . n false false true
    
    26+
    even = \ n . not (odd n)
    
    27+
    mul2 = \ n _ f _ . f n
    
    28+
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    29+
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    30+
    31+
    # arrays as foldr (strings)
    
    32+
    `
    

Proof of Concept LC compiler and native tester in JS

How to use

  • Import the module const LC = require('LC')
  • Set any config options
  • Generate compiled user solution with LC.compile()
  • Test using normal JS test suite (Mocha)

The Kumite

In the kumite, Preloaded is used in place of the final module (in a real kata, Preloaded will simply be prepended to Solution before compilation). The constants in Code represent potential user solutions. Test Cases are as they would (potentially) appear in a real kata.

How it Works

User solutions are first parsed into term trees of Applications, Abstractions and Variables. The result is passed to evalLC which compiles.

stack is simulating recursive calls. It stores bound variable information, as well as the right hand side of applications (A) which are awaiting a value to bind to. boundVars is a Map keeping track of our environment (bound variables).

If the top term is a variable (V) we switch to the term and environment to which our variable's name is bound in boundVars

if the top term is an application (A) we pack the right term of the application, and the current environment (boundVars) into the stack, and move into the left term.

If the top term is an abstraction (L), we remove the last element of the stack. We bind it and its environment to our term's name (within boundVars), then move into the body of our term. If there is nothing in stack, then we are waiting for an input, so we pack our current environment into a function and return that, so when an argument is passed, it continues right where we left off.

Other languages

Here JS serves only as a 'host' and testing language, so other languages could likely be supported for authors who prefer it. Progress is being made on a Haskell version currently.

To do:

  • Write some large "katas" for stress testing
  • Add verbosity options
  • Construct a toString() method that applies environment variables
  • Write better errors for bad parsing
const text = String.raw`
succ = \n f x. f (n f x)
pair = \a.\b.\c.c a b
fst = \pair.pair (\a.\_.a)
snd = \pair.pair (\_.\b.b)
plus = \pair.\f.\x.(fst pair) f ((snd pair) f x)
next = \prev.pair (snd prev) (plus prev)
fib = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
`

// Proof of laziness -- using Scott
const lazy = String.raw`
succ = \ n _ f . f n
inf_list = \ n b . b n (inf_list (succ n))
counter = inf_list 0
`

// Stress testing -- "LetRec", "BinaryScott"
// Testing implementation of a "String" - ie. Arrays and related functions
const stress = String.raw`
# bools
true = \ a b . a
false = \ a b . b
not = \ b . b false true
and = \ a b . a b false
or = \ a b . a true b
xor = \ a b . a (b false true) b

# ints -- z = endbit, f = offbit, t = onbit
zero = \ z _ _ . z
succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
pred = \ n z f t . n z (\ m . t (pred m)) f
bool = \ n . n false (\ _ . true) (\ _ . true)
odd = \ n . n false false true
even = \ n . not (odd n)
mul2 = \ n _ f _ . f n
addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)

# arrays as foldr (strings)
`