Code
Diff
  • const code = String.raw`
    Y = \ f . ( \ x . f (x x) ) ( \ x . f (x x) )
    True = \ t f . t
    False = \ t f . f
    Succ = \ n s z . s (n s z)
    Pred = \ n s z . n ( \ f g . g (f s) ) (\_.z) \x.x
    Minus = \ m n . n Pred m
    Times = \ m n s . m (n s)
    isZero = \ n . n (\_.False) True
    isNotZero = \ n . n (\_.True) False
    And = \ x y . x y x
    Or = \ x . x x
    GT = \ x y . isNotZero (Minus x y)
    Mod = \ n m . ( \ r . isZero (Minus m r) 0 r ) (( \ n m . ( \ d . isZero d n (Mod d m) ) (Minus n m) ) n m)
    
    # function isPrime(n) {
    #   const trial = function trial(i) {
    #     return i * i > n || n % i != 0 && trial(i+1) ;
    #   } ;
    #   return n > 1 && trial(2) ;
    # }
    
    isPrime = \ n . ( \ trial . And (GT n 1) (trial 2) )
                    ( Y \ trial i . Or (GT (Times i i) n) (And (isNotZero (Mod n i)) (trial (Succ i))) )
    `
  • 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
    `
    
    2+
    Y = \ f . ( \ x . f (x x) ) ( \ x . f (x x) )
    
    3+
    True = \ t f . t
    
    4+
    False = \ t f . f
    
    5+
    Succ = \ n s z . s (n s z)
    
    6+
    Pred = \ n s z . n ( \ f g . g (f s) ) (\_.z) \x.x
    
    7+
    Minus = \ m n . n Pred m
    
    8+
    Times = \ m n s . m (n s)
    
    9+
    isZero = \ n . n (\_.False) True
    
    10+
    isNotZero = \ n . n (\_.True) False
    
    11+
    And = \ x y . x y x
    
    12+
    Or = \ x . x x
    
    13+
    GT = \ x y . isNotZero (Minus x y)
    
    14+
    Mod = \ n m . ( \ r . isZero (Minus m r) 0 r ) (( \ n m . ( \ d . isZero d n (Mod d m) ) (Minus n m) ) n m)
    
    1010
    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
    
    16+
    # function isPrime(n) {
    
    17+
    #   const trial = function trial(i) {
    
    18+
    #     return i * i > n || n % i != 0 && trial(i+1) ;
    
    19+
    #   } ;
    
    20+
    #   return n > 1 && trial(2) ;
    
    21+
    # }
    
    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)
    
    33
    34
    # arrays as foldr (strings)
    
    23+
    isPrime = \ n . ( \ trial . And (GT n 1) (trial 2) )
    
    24+
                    ( Y \ trial i . Or (GT (Times i i) n) (And (isNotZero (Mod n i)) (trial (Succ i))) )
    
    3535
    `
    

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

Encodings

  • purity -> Let
  • true, false -> Church encoding
  • Number -> Church encoding (only used as chars)
  • char -> a number corresponding to ascii code
  • nil -> an empty string: \ _ -> false
  • cons -> add a char to a string: \ char string b1 . b1 true (\ b2 . b2 char string)

Fixed for existing bugs. Now with number literals.

Code
Diff
  • const code = String.raw`
    # Preloaded
    
    true = \ a b . a
    false = \ a b . b
    
    pair = \ a b c . c a b
    nil = \ _ . false
    cons = \ c s . pair true (pair c s)
    
    # Code
    hello = cons 72
          ( cons 101
          ( cons 108
          ( cons 108
          ( cons 111
          ( cons 44
          ( cons 32
          ( cons 119
          ( cons 111
          ( cons 114
          ( cons 108
          ( cons 100
          ( cons 33
                 nil
          ))))))))))))
    `
  • 11
    const code = String.raw`
    
    2
    # bools
    
    2+
    # Preloaded
    
    3+
    33
    true = \ a b . a
    
    44
    false = \ a b . b
    
    55
    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
    
    2626
    pair = \ a b c . c a b
    
    2727
    nil = \ _ . false
    
    2828
    cons = \ c s . pair true (pair c s)
    
    2929
    30
    # [72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33]
    
    31
    hello = cons seventytwo 
    
    11+
    # Code
    
    12+
    hello = cons 72
    
    13+
          ( cons 101
    
    14+
          ( cons 108
    
    15+
          ( cons 108
    
    16+
          ( cons 111
    
    17+
          ( cons 44
    
    18+
          ( cons 32
    
    19+
          ( cons 119
    
    20+
          ( cons 111
    
    21+
          ( cons 114
    
    22+
          ( cons 108
    
    23+
          ( cons 100
    
    24+
          ( cons 33
    
    25+
                 nil
    
    26+
          ))))))))))))
    
    4545
    `
    

fixing bugs in the parser

  • numbers were wrapped in a spurious V
  • () was not accepted
Code
Diff
  • const code = String.raw`
    add = \ m n s z . m s (n s z)
    go = \ return a b . return b (add a b)
    K = \ x _ . x
    fibonacci = \ n . n go K 0 1
    `
  • 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
    
    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)
    
    2+
    add = \ m n s z . m s (n s z)
    
    3+
    go = \ return a b . return b (add a b)
    
    4+
    K = \ x _ . x
    
    5+
    fibonacci = \ n . n go K 0 1
    
    3535
    `
    

show decoded value in test failure message.

valueOf and decoded are defined on Function.prototype; things won't work ( for different reasons ) if not.

toInt has been removed from awaitArg; it didn't seem useful.

testing seems faster. (??) failing tests take relatively long though ( and longer than succeeding tests of the same size ). fortunately, a failing test stops the it group, so it doesn't seem a major problem.

I have tried to make awaitArg.term to print a nice lambda expression. couldn't do it.

a failed test now shows

expected { [Function: awaitArg]
  term: { name: 'f', body: { name: 'x', body: [Object] } },
  env: {},
  decoded: 6765 } to equal 6764

Updates to fromInt and toInt

Probably gives initial compile and runtime efficiency improvements, both in time and space.

I feel clever. :P

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
    `
    
    1010
    1111
    // Stress testing -- "LetRec", "BinaryScott"
    
    1212
    // Testing implementation of a "String" - ie. Arrays and related functions
    
    1313
    const stress = String.raw`
    
    1414
    # bools
    
    1515
    id = \ x . x
    
    1616
    true = \ a b . a
    
    1717
    false = \ a b . b
    
    1818
    not = \ b . b false true
    
    1919
    and = \ a b . a b false
    
    2020
    or = \ a b . a true b
    
    2121
    xor = \ a b . a (b false true) b
    
    2222
    2323
    # ints -- z = endbit, f = offbit, t = onbit
    
    2424
    zero = \ z _ _ . z
    
    2525
    succ = \ n _ f t . n (t zero) t (\ m . f (succ m))
    
    2626
    bool = \ n . n false (\ _ . true) (\ _ . true)
    
    2727
    pred = \ n z f t . n z (\ m . t (pred m)) (\ m . bool m (f m) z)
    
    2828
    odd = \ n . n false false true
    
    2929
    even = \ n . not (odd n)
    
    3030
    mul2 = \ n _ f _ . f n
    
    3131
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    3232
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    3333
    3434
    # arrays as foldr (strings)
    
    3535
    `
    

compile development

  • better error messages ( where possible )
  • compiling immediate numbers ( when appropriate )
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))))
    `
  • 11
    const code = String.raw`
    
    2
    succ = \n f x. f (n f x)
    
    2+
    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
    `
    

compile development

  • better error messages ( where possible )
  • compiling immediate numbers ( when appropriate )
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))))
    `
  • 1
    const text = String.raw`
    
    1+
    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)
    
    8
    fib = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    
    9
    `
    
    10
    11
    // Proof of laziness -- using Scott
    
    12
    const lazy = String.raw`
    
    13
    succ = \ n _ f . f n
    
    14
    inf_list = \ n b . b n (inf_list (succ n))
    
    15
    counter = inf_list 0
    
    16
    `
    
    17
    18
    // Stress testing -- "LetRec", "BinaryScott"
    
    19
    // Testing implementation of a "String" - ie. Arrays and related functions
    
    20
    const stress = String.raw`
    
    21
    # bools
    
    22
    true = \ a b . a
    
    23
    false = \ a b . b
    
    24
    not = \ b . b false true
    
    25
    and = \ a b . a b false
    
    26
    or = \ a b . a true b
    
    27
    xor = \ a b . a (b false true) b
    
    28
    29
    # ints -- z = endbit, f = offbit, t = onbit
    
    30
    zero = \ z _ _ . z
    
    31
    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
    
    33
    bool = \ n . n false (\ _ . true) (\ _ . true)
    
    34
    odd = \ n . n false false true
    
    35
    even = \ n . not (odd n)
    
    36
    mul2 = \ n _ f _ . f n
    
    37
    addSlow = \ a b . bool b (addSlow (succ a) (pred b)) a
    
    38
    subSlow = \ a b . bool a (bool b (subSlow (pred a) (pred b)) a) (zero)
    
    39
    40
    # arrays as foldr (strings)
    
    8+
    fibonacci = \n. fst (n next (pair (\_.\b.b) (succ (\_.\b.b))))
    
    4141
    `
    
Arrays
Code
Diff
  • function remove (arr, n) {
      if ( n >= 0 )
        arr.splice(n, 1);
      return arr;
    }
  • 11
    function remove (arr, n) {
    
    2
      if (n < 0 || n >= arr.length) return arr;
    
    3
      arr.splice(n, 1);
    
    2+
      if ( n >= 0 )
    
    3+
        arr.splice(n, 1);
    
    44
      return arr;
    
    55
    }
    

fib is O(n²) in practice, probably because of BigInt arithmetic.

There is also an optimisation calculating fib(n) in terms of fib(approx half n), which is actually logarithmic before BigInt arithmetic. That's even faster, in this case.

Code
Diff
  • function fib(n) {
      for ( let [a,b]=[0n,1n], i=0;; i++ )
        if ( i<n )
          [a,b] = [b,a+b];
        else
          return a;
    }
  • 1
    module Example where
    
    2
    3
    import Data.Semigroup (Endo(..),stimes)
    
    4
    5
    fib :: Integer -> Integer
    
    6
    fib = fst . (`appEndo` (0,1)) . (`stimes` Endo ( \ (a,b) -> (b,a+b) ))
    
    1+
    function fib(n) {
    
    2+
      for ( let [a,b]=[0n,1n], i=0;; i++ )
    
    3+
        if ( i<n )
    
    4+
          [a,b] = [b,a+b];
    
    5+
        else
    
    6+
          return a;
    
    7+
    }
    
Code
Diff
  • module Example where
    
    import Data.Semigroup (Endo(..),stimes)
    
    fib :: Integer -> Integer
    fib = fst . (`appEndo` (0,1)) . (`stimes` Endo ( \ (a,b) -> (b,a+b) ))
  • 11
    module Example where
    
    22
    33
    import Data.Semigroup (Endo(..),stimes)
    
    44
    55
    fib :: Integer -> Integer
    
    6
    fib n = fst $ n `stimes` Endo ( \ (a,b) -> (b,a+b) ) `appEndo` (0,1)
    
    6+
    fib = fst . (`appEndo` (0,1)) . (`stimes` Endo ( \ (a,b) -> (b,a+b) ))
    

Endo wraps a function; appEndo unwraps it.

stimes composes a wrapped function with itself n times. It is optimised to take O(log n) time.

module Example where

import Data.Semigroup (Endo(..),stimes)

fib :: Integer -> Integer
fib n = fst $ n `stimes` Endo ( \ (a,b) -> (b,a+b) ) `appEndo` (0,1)
Code
Diff
  • public static class ReverseFactorial  {
      public static int Kata(long n) {
        long i = 1;
        while ( n > 1 ) n /= i += 1 ;
        return (int) i;
      }
    }
  • 1
    using System;
    
    2
    3
        public static class ReverseFactorial
    
    4
        {
    
    5
            public static int Kata(long n)
    
    6
            {
    
    7
              if(n == 0) return 1;
    
    8
              for (long i = 2; n / i > 1; i++)
    
    9
              {
    
    10
                n /= i;
    
    11
              }
    
    12
              return (int) n;
    
    13
            }
    
    14
        }
    
    1+
    public static class ReverseFactorial  {
    
    2+
      public static int Kata(long n) {
    
    3+
        long i = 1;
    
    4+
        while ( n > 1 ) n /= i += 1 ;
    
    5+
        return (int) i;
    
    6+
      }
    
    7+
    }
    

custom.map and custom.filter should return custom arrays, not ordinary ones.

wrapper can be used for random tests as well.

Code
Diff
  • // this code should fail the tests // it does
    
    function totalAgeYoungerThan0(people, age) {
      let totalAge = 0;
      for ( let i=0; i in people; i++ ) // this will just always return 0 with the arguments we send
        if ( people[i].age < age )
          totalAge += people[i].age;
      return totalAge;
    }
    
    // this code should fail the tests // it does
    
    function totalAgeYoungerThan1(people,tooOld) {
      let totalAge = 0;
      for ( const {age} of people ) // this will throw because our argument isn't iterable
        if ( age < tooOld )
          totalAge += age;
      return totalAge;
    }
    
    // this code should fail the tests // it does
    
    function totalAgeYoungerThan2(xs, age) {
      const [person,...persons] = xs; // this will throw on not iterable
      if ( person===undefined )
        return 0;
      else if ( person.age < age )
        return totalAgeYoungerThan2(persons,age) + person.age;
      else
        return totalAgeYoungerThan2(persons,age);
    }
    
    // this code should theoretically pass the tests // it does
    // it includes the word `for` but not in a for loop
    
    function totalAgeYoungerThan3(people, age) {
      return people
        .filter(person => person.age < age)
        .reduce((formula, person) => formula + person.age, 0)
    }
    
    // passes
    
    function totalAgeYoungerThan4(people, age) {
      return people
        .filter(person => person.age < age)
        .reduce((sum, person) => sum + person.age, 0)
    }
    
    // passes
    
    const get = i => o => o[i] ;
    const lt = x => y => y < x ;
    const plus = (x,y) => y+x ;
    
    function totalAgeYoungerThan5(people,age) {
      return people.map(get("age"))
                   .filter(lt(age))
                   .reduce(plus,0)
                   ;
    }
  • 4343
    4444
    function totalAgeYoungerThan4(people, age) {
    
    4545
      return people
    
    4646
        .filter(person => person.age < age)
    
    4747
        .reduce((sum, person) => sum + person.age, 0)
    
    4848
    }
    
    49+
    50+
    // passes
    
    51+
    52+
    const get = i => o => o[i] ;
    
    53+
    const lt = x => y => y < x ;
    
    54+
    const plus = (x,y) => y+x ;
    
    55+
    56+
    function totalAgeYoungerThan5(people,age) {
    
    57+
      return people.map(get("age"))
    
    58+
                   .filter(lt(age))
    
    59+
                   .reduce(plus,0)
    
    60+
                   ;
    
    61+
    }
    
Loading more items...