# MIT License, Copyright (c) 2022 Marvin Borner # Heavily inspired by the works of T.Æ. Mogensen (see refs in README) :import std/Combinator . :import std/Pair . :import std/Logic . # negative trit indicating coeffecient of (-1) t< [[[2]]] # returns whether a trit is negative t [[[1]]] # returns whether a trit is positive t>? [0 false true false] # zero trit indicating coeffecient of 0 t= [[[0]]] # returns whether a trit is zero t=? [0 false false true] :test (t) (false) :test (t? t<) (false) :test (t>? t>) (true) :test (t>? t=) (false) :test (t=? t<) (false) :test (t=? t>) (false) :test (t=? t=) (true) # shifts a negative trit into a balanced ternary number up-neg [[[[[2 (4 3 2 1 0)]]]]] ^<( up-neg :test (^<(+0)) ((-1)) :test (^<(-1)) ((-4)) :test (^<(+42)) ((+125)) # shifts a positive trit into a balanced ternary number up-pos [[[[[1 (4 3 2 1 0)]]]]] ^>( up-pos :test (^>(+0)) ((+1)) :test (^>(-1)) ((-2)) :test (^>(+42)) ((+127)) # shifts a zero trit into a balanced ternary number up-zero [[[[[0 (4 3 2 1 0)]]]]] ^=( up-zero :test (^=(+0)) ([[[[0 3]]]]) :test (^=(+1)) ((+3)) :test (^=(+42)) ((+126)) # shifts a specified trit into a balanced ternary number up [[[[[[5 2 1 0 (4 3 2 1 0)]]]]]] :test (up t< (+42)) (^<(+42)) :test (up t> (+42)) (^>(+42)) :test (up t= (+42)) (^=(+42)) # shifts the least significant trit out - basically div by 3 down [snd (0 z a< a> a=)] z (+0) : (+0) a< [0 [[^<1 : 1]]] a> [0 [[^>1 : 1]]] a= [0 [[^=1 : 1]]] # negates a balanced ternary number negate [[[[[4 3 1 2 0]]]]] -( negate :test (-(+0)) ((+0)) :test (-(-1)) ((+1)) :test (-(+42)) ((-42)) # converts a balanced ternary number to a list of trits list! [0 z a< a> a=] z [[0]] a< [t< : 0] a> [t> : 0] a= [t= : 0] # TODO: Tests! # strips leading 0s from balanced ternary number strip [fst (0 z a< a> a=)] z (+0) : true a< [0 [[^<1 : false]]] a> [0 [[^>1 : false]]] a= [0 [[(0 (+0) ^=1) : 0]]] %( strip :test (%[[[[0 3]]]]) ((+0)) :test (%[[[[2 (0 (0 (0 (0 3))))]]]]) ((-1)) :test (%(+42)) ((+42)) # extracts least significant trit from balanced ternary numbers lst [0 t= [t<] [t>] [t=]] :test (lst (-1)) (t<) :test (lst (+0)) (t=) :test (lst (+1)) (t>) :test (lst (+42)) (t=) # extracts most significant trit from balanced ternary numbers # TODO: Find a more elegant way to do this (and resolve list import loop?) mst [fix (last (list! %0))] last Z [[<>?0 [false] [<>?(snd 1) (fst 1) (2 (snd 1))] I]] <>?( [0 [[[false]]] true] fix [((t? 0) || (t=? 0))) 0 t=] :test (mst (-1)) (t<) :test (mst (+0)) (t=) :test (mst (+1)) (t>) :test (mst (+42)) (t>) # returns whether balanced ternary number is negative negative? [t? (mst 0)] >?( positive? :test (>?(+0)) (false) :test (>?(-1)) (false) :test (>?(+1)) (true) :test (>?(+42)) (true) # checks whether balanced ternary number is zero zero? [0 true [false] [false] I] =?( zero? :test (=?(+0)) (true) :test (=?(-1)) (false) :test (=?(+1)) (false) :test (=?(+42)) (false) # converts the normal balanced ternary representation into abstract # -> the abstract representation is used in eq?/add/sub/mul abstract! [0 z a< a> a=] z (+0) a< [[[[[2 4]]]]] a> [[[[[1 4]]]]] a= [[[[[0 4]]]]] ->^( abstract! :test (->^(-3)) ([[[[0 [[[[2 [[[[3]]]]]]]]]]]]) :test (->^(+0)) ([[[[3]]]]) :test (->^(+3)) ([[[[0 [[[[1 [[[[3]]]]]]]]]]]]) # converts the abstracted balanced ternary representation back to normal # using ω to solve recursion normal! ω rec rec [[0 (+0) [^<([3 3 0] 0)] [^>([3 3 0] 0)] [^=([3 3 0] 0)]]] ->_( normal! :test (->_[[[[3]]]]) ((+0)) :test (->_(->^(+42))) ((+42)) :test (->_(->^(-42))) ((-42)) # checks whether two balanced ternary numbers are equal # larger numbers should be second argument (performance) # -> ignores leading 0s! eq? [[abs 1 ->^0]] abs [0 z a< a> a=] z [=?(->_0)] a< [[0 false [2 0] [false] [false]]] a> [[0 false [false] [2 0] [false]]] a= [[0 (1 0) [false] [false] [2 0]]] (=?) eq? :test ((-42) =? (-42)) (true) :test ((-1) =? (-1)) (true) :test ((-1) =? (+0)) (false) :test ((+0) =? (+0)) (true) :test ((+1) =? (+0)) (false) :test ((+1) =? (+1)) (true) :test ((+42) =? (+42)) (true) :test ([[[[(1 (0 (0 (0 (0 3)))))]]]] =? (+1)) (true) # I believe Mogensen's Paper has an error in its inc/dec/add/mul/eq definitions. # They use 3 instead of 2 abstractions in the functions, also we use switched # +/0 in comparison to their implementation, yet the order of neg/pos/zero is # the same. Something's weird. # adds (+1) to a balanced ternary number (can introduce leading 0s) inc [snd (0 z a< a> a=)] z (+0) : (+1) a< [0 [[^<1 : ^=1]]] a> [0 [[^>1 : ^<0]]] a= [0 [[^=1 : ^>1]]] ++( inc # adds (+1) to a balanced ternary number and strips leading 0s ssinc strip . inc :test ((++(-42)) =? (-41)) (true) :test ((++(-1)) =? (+0)) (true) :test ((++(+0)) =? (+1)) (true) :test ((++(++(++(++(++(+0)))))) =? (+5)) (true) :test ((++(+42)) =? (+43)) (true) # subs (+1) from a balanced ternary number (can introduce leading 0s) dec [snd (0 z a< a> a=)] z (+0) : (-1) a< [0 [[^<1 : ^>0]]] a> [0 [[^>1 : ^=1]]] a= [0 [[^=1 : ^<1]]] --( dec # subs (+1) from a balanced ternary number and strips leading 0s sdec strip . dec :test ((--(-42)) =? (-43)) (true) :test ((--(+0)) =? (-1)) (true) :test ((--(--(--(--(--(+5)))))) =? (+0)) (true) :test ((--(+1)) =? (+0)) (true) :test ((--(+42)) =? (+41)) (true) # adds two balanced ternary numbers (can introduce leading 0s) # larger numbers should be second argument (performance) add [[abs 1 ->^0]] abs [c (0 z a< a> a=)] b< [1 ^>(3 0 t<) ^=(3 0 t=) ^<(3 0 t=)] b= [up 1 (3 0 t=)] b> [1 ^=(3 0 t=) ^<(3 0 t>) ^>(3 0 t=)] a< [[[1 (b< 1) b<' b= b<]]] b<' [1 ^=(3 0 t<) ^<(3 0 t=) ^>(3 0 t<)] a> [[[1 (b> 1) b= b>' b>]]] b>' [1 ^>(3 0 t=) ^=(3 0 t>) ^<(3 0 t>)] a= [[[1 (b= 1) b< b> b=]]] z [[0 --(->_1) ++(->_1) ->_1]] c [[1 0 t=]] (+) add # adds two balanced ternary numbers and strips leading 0s sadd strip .. add :test (((-42) + (-1)) =? (-43)) (true) :test (((-5) + (+6)) =? (+1)) (true) :test (((-1) + (+0)) =? (-1)) (true) :test (((+0) + (+0)) =? (+0)) (true) :test (((+1) + (+2)) =? (+3)) (true) :test (((+42) + (+1)) =? (+43)) (true) # subs two balanced ternary numbers (can introduce leading 0s) # larger numbers should be second argument (performance) sub [[1 + -0]] (-) sub # subs two balanced ternary numbers and strips leading 0s ssub strip .. sub :test (((-42) - (-1)) =? (-41)) (true) :test (((-5) - (+6)) =? (-11)) (true) :test (((-1) - (+0)) =? (-1)) (true) :test (((+0) - (+0)) =? (+0)) (true) :test (((+1) - (+2)) =? (-1)) (true) :test (((+42) - (+1)) =? (+41)) (true) # returns whether number is greater than other number # larger numbers should be second argument (performance) gre? [[>?(1 - 0)]] (>?) gre? :test ((+1) >? (+2)) (false) :test ((+2) >? (+2)) (false) :test ((+3) >? (+2)) (true) # returns whether number is less than other number # smaller numbers should be second argument (performance) les? [[? 0)]] (<=?) leq? :test ((+1) <=? (+2)) (true) :test ((+2) <=? (+2)) (true) :test ((+3) <=? (+2)) (false) # returns whether number is greater than or equal to other number # smaller numbers should be second argument (performance) geq? [[!(1 =?) geq? :test ((+1) >=? (+2)) (false) :test ((+2) >=? (+2)) (true) :test ((+3) >=? (+2)) (true) # muls two balanced ternary numbers (can introduce leading 0s) mul [[1 (+0) a< a> a=]] a< [^=0 - 1] a> [^=0 + 1] a= [^=0] (*) mul smul strip .. mul :test (((+42) * (+0)) =? (+0)) (true) :test (((-1) * (+42)) =? (-42)) (true) :test (((+3) * (+11)) =? (+33)) (true) :test (((+42) * (-4)) =? (-168)) (true) # greatest common divisor gcd Z [[[(1 =? 0) case-eq ((1 >? 0) case-gre case-les)]]] case-eq 1 case-gre 2 (1 - 0) 0 case-les 2 1 (0 - 1) :test ((gcd (+2) (+4)) =? ((+2))) (true) :test ((gcd (+10) (+5)) =? ((+5))) (true) :test ((gcd (+3) (+8)) =? ((+1))) (true) # factorial function fac Z [[(0