Failed Tests

### Feature testing

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 ```
Failed Tests

### Counter POC

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
```````
•  1 1 ```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 ``` 5 5 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) ``` 9 9 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)) ``` 11 11 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 ``` 15 15 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 ``` 20 20 ```` ```

## 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`.

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 "`n`th 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

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
````
```

### Hello World (POC LC Kata)

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 `char`s)
• `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
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 ))))))))))))
```````
•  1 1 ```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 14 ```# bools ``` 15 − ```id = \ x . x ``` 16 16 ```true = \ a b . a ``` 17 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 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) ``` 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) ``` 33 33 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 )))))))))))) ``` 35 35 ```` ```

### POC LC crosscompiler in JS

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)
```````
•  1 1 ```const code = String.raw` ``` 2 2 ```succ = \ n f x . f (n f x) ``` 3 3 ```pair = \a.\b.\c.c a b ``` 4 4 ```fst = \pair.pair (\a.\_.a) ``` 5 5 ```snd = \pair.pair (\_.\b.b) ``` 6 6 ```plus = \pair.\f.\x.(fst pair) f ((snd pair) f x) ``` 7 7 ```next = \prev.pair (snd prev) (plus prev) ``` 8 8 ```fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b)))) ``` 9 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 ``` 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 + ```` ```

### eval + options development

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
````
```
Failed Tests

### Crosscompiler bug exhibition

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)
```````
•  1 1 ```const code = String.raw` ``` 2 2 ```succ = \n f x. f (n f x) ``` 3 3 ```pair = \a.\b.\c.c a b ``` 4 4 ```fst = \pair.pair (\a.\_.a) ``` 5 5 ```snd = \pair.pair (\_.\b.b) ``` 6 6 ```plus = \pair.\f.\x.(fst pair) f ((snd pair) f x) ``` 7 7 ```next = \prev.pair (snd prev) (plus prev) ``` 8 8 ```fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b)))) ``` 9 9 ```` ``` 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
• 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)
```````