Prolog S-expr

calc.prolog

:- module(calc, [tokens//1, ast//1, ast_eval/2, eval_formatted/2, source_eval/2, source_evalFormatted/2]).

:- use_module(library(clpz)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(charsio)).
:- use_module(library(dif)).
:- use_module(library(debug)).

/** S-expression calculator

  A S-expr calculator that supports projective rational numbers.
  expressions can be evaluated with `source_evalFormatted(Src,Eval)` like so.
  ```prolog
  ?- source_evalFormatted("(- (+ -1/2 (floor 57/97)))", Eval).
     Eval = "1/2"
  ;  false.
  ```

  View the tokenizing, the building of the ast and the eventual evaluation. 
  (formatted slightly for readability)
  ```prolog
  ?- Src = "(+ 1 4.5)", 
     phrase(tokens(Tokens),Src), 
     phrase(ast(Ast),Tokens), 
     ast_eval(Ast,Eval), 
     eval_formatted(Eval,Form)
     .
     Src    = "(+ 1 4.5)", 
     Tokens = [lPar,op(+),integer(1),sign_numer_denom(+,9,2),rPar], 
     Ast    = [op(+),integer(1),sign_numer_denom(+,9,2)], 
     Eval   = sign_numer_denom(+,11,2), 
     Form   = "11/2"
  ;  false.
  ```

  numbers 
  ( "-?[1-9][0-9]*"     non-zero integer
  | "-?[0-9]+.[0-9]+"   decimal (sugar for rational numbers)
  | "-?[1-9]+/[1-9]+"   rational
  | "0"                 zero
  | "0/0"               bottom
  | "1/0"               infinity ( projective ) 
  )

  operators 
  ( (<=> _)   sign           : negArg->(-1), 0->0, posArg->1, infinity->infinity, bottom->bottom
              
  | (+ _ ..)  sum            : sum all arguments
                               ( number+infinity->infinity, bottom+infinity->bottom )
              
  | (* _ ..)  product        : multiply all arguments 
                               ( number*infinity->infinity, zero*infinity->bottom )
              
  | (- _)     negate         : negate argument, 
                               ( zero, bottom and infinity are idempotent )
              
  | (- _ ..)  subtract       : subtract from the first argument the rest
                               ( uses negation and addition rules )
              
  | (/ _)     reciprocate    : 1/argument ( zero->infinity->bottom )
              
  | (/ _ ..)  divide         : divide first argument by the rest
                               ( uses reciprocation and negation rules )

  | (% _)     fraction       : takes the fractional part of a number
                               ( idempotent on integers, zero, infinity and bottom )

  | (% _ ..)  remainder      : take the remainder of the argument by the rest, folding left to right
                               ( number%zero->infinity, infinity%zero->bottom ) 

  | (abs _)   absolute value : negArg->posArg, idempotent on non-negative values

  | (floor _) floor          : subtract the fractional part of a number, always rounds down
                               ( (arg<zero)->zero, (arg=integer+fraction)->integer,
                                 idempotent on integers, zero, infinity, and bottom 
                               )
  | (signedSqrt _) signed square root 
                             : an approximation of the square root of the absolute value, 
                               then negated if the imput was negative.
                               ( integers  => integer square root, 
                               | rationals =>   numerator integer square root 
                                              / denominator integer square root,
                               | zero, infinity, and bottom are idempotent
                               )

  )
  */

% ---- State ----

lookahead(S), [S] --> [S].

% ---- Tokenizing ----

token(lPar) --> "(".
token(rPar) --> ")".

token(op(<=>))  --> "<=>", whitespaceChar.
token(op(+))    --> "+", whitespaceChar.
token(op(-))    --> "-", whitespaceChar.
token(op(/))    --> "/", whitespaceChar.
token(op(*))    --> "*", whitespaceChar.
token(op('%'))  --> "%", whitespaceChar.
token(op(abs))        --> "abs",        whitespaceChar.
token(op(floor))      --> "floor",      whitespaceChar.
token(op(signedSqrt)) --> "signedSqrt", whitespaceChar.

token(integer(I)) --> integer(I).
token(integer(I)) --> 
  sign_numer_denom(S, N, D), 
  { D #= 1, 
    ( S=(+), I#=N 
    ; S=(-), I#= -N
    ) 
  }.
token(sign_numer_denom(S, N, D)) --> sign_numer_denom(S, N, D), {D #\= 1}.
token('1/0') --> '1/0'.
token('0/0') --> '0/0'.

whitespace --> whitespaceChar, whitespace.
whitespace --> "".
whitespaceChar --> 
  ( "\x9\"    % character tabulation
  | "\xA\"    % line feed
  | "\xB\"    % line tabulation
  | "\xC\"    % form feed
  | "\xD\"    % carriage return
  | "\x20\"   % space
  | "\x85\"   % next line
  | "\xA0\"   % no-brake space
  | "\x1680\" % ogham space mark
  | "\x2000\" % en quad
  | "\x2001\" % em quad
  | "\x2002\" % en space
  | "\x2003\" % em space
  | "\x2004\" % three-per-em space
  | "\x2005\" % four-per-em space
  | "\x2006\" % six-per-em space
  | "\x2007\" % figure space
  | "\x2008\" % punctuation space
  | "\x2009\" % thin space
  | "\x200A\" % hair space
  | "\x2028\" % line separator
  | "\x2029\" % paragraph separator
  | "\x202F\" % narrow no-break space
  | "\x205F\" % medium matematical space
  | "\x3000\" % ideographic space
  ).

tokens([T|Ts]) --> whitespace, token(T), tokens(Ts).
tokens([])     --> whitespace.


sign_numerals(+, N) --> numerals(N).
sign_numerals(-, N) --> "-", nonZeroNumerals(N). % ban -0 syntax

integer(I) --> numerals(C), { number_chars(I, C) }.
integer(I) --> sign_numerals(-, C), { number_chars(N, C), I #= -N }.

% we support projective infinity
'1/0' --> "1/0".
'0/0' --> "0/0".
% rational notation
sign_numer_denom(S, N, D) -->
  sign_numerals(S, CN), "/", nonZeroNumerals(CD),
  { number_chars(RawN, CN), number_chars(RawD, CD),
    RawN #\= 0,
    numer_demom_gcdNumer_gcdDenom(RawN, RawD, N, D)
  }.
% decimal notation for rational numbers
sign_numer_denom(S, N, D) -->
  sign_numerals(S, CInt), ".", numerals(CFract),
  { length(CFract, CFLen),
    number_chars(Int, CInt), number_chars(Fract, CFract),
    RawD #= 10^CFLen,
    RawN #= Int*RawD + Fract,
    numer_demom_gcdNumer_gcdDenom(RawN, RawD, N, D)
  }.

nonZeroNumeral(N) --> [N], { member(N, "123456789") }.

numeral('0') --> "0".
numeral(N)   --> nonZeroNumeral(N).

nonZeroNumerals([N | Ns]) --> nonZeroNumeral(N), numerals(Ns).
nonZeroNumerals([N])      --> nonZeroNumeral(N), noTrailingNum.

numerals([N | Ns]) --> nonZeroNumeral(N), allNumerals(Ns). % fix this
numerals([N])      --> nonZeroNumeral(N), noTrailingNum.
numerals(['0'])    --> "0", noTrailingNum.

allNumerals([N|Ns]) --> numeral(N), allNumerals(Ns).
allNumerals([N]) --> numeral(N), noTrailingNum.

noTrailingNum --> lookahead(X), { \+ member(X, "0123456789") }, lookahead(X).

% ---- Parsing ----

ast(integer(I))                --> [integer(I)].
ast('1/0')                     --> ['1/0'].
ast('0/0')                     --> ['0/0'].
ast(sign_numer_denom(S, N, D)) --> [sign_numer_denom(S, N, D)].
ast([op(Op) | Args])           --> [lPar], [op(Op)], args(Args), [rPar].
args([Arg| Args]) --> ast(Arg), args(Args).
args([])          --> [].


ast_eval('0/0','0/0').
ast_eval('1/0','1/0').
ast_eval(integer(I), integer(I)).
ast_eval(sign_numer_denom(S,N,D),sign_numer_denom(S,N,D)).
ast_eval(Ast,Eval) :- Ast = [op(Op)|Args], op_args_eval(Op,Args,Eval).

% ---- Eval ----

op_args_eval(Op, Args, Eval1) :-
  Args = [X0 | Rest0],
  ( X0 =  [_|_],
    ast_eval(X0,Eval0), op_args_eval(Op, [Eval0 | Rest0], Eval1)
  ; dif(X0, [_|_]),

    dif(Op,(/)), dif(Op,(-)), % the binary inverses are placed here

    Rest0 = [X1 | Rest1], X1 = [_|_], 
    ast_eval(X1, Eval0), op_args_eval(Op, [X0, Eval0 | Rest1], Eval1)
  )
  .

% sign
op_args_eval((<=>), ['1/0'], '1/0').
op_args_eval((<=>), ['0/0'], '0/0').
op_args_eval((<=>), [integer(I0)], integer(I1)) :- 
  ordering_left_right(Ord, I0, 0),
  ( Ord = (<), I1 #= -1
  ; Ord = (=), I1 #=  0
  ; Ord = (>), I1 #=  1
  ).
op_args_eval((<=>), [sign_numer_denom(S,N,_)], integer(I)) :-
  ( N #=   0, I #=  0
  ; S  = (+), I #=  1
  ; S  = (-), I #= -1
  ).

% abs
op_args_eval((abs), ['1/0'], '1/0').
op_args_eval((abs), ['0/0'], '0/0').
op_args_eval((abs), [integer(I0)], integer(I1)) :- I1 #= abs(I0).
op_args_eval((abs), [sign_numer_denom(_,N,D)], sign_numer_denom((+),N,D)).

% negation
op_args_eval((-), ['1/0'], '1/0').
op_args_eval((-), ['0/0'], '0/0').
op_args_eval((-), [integer(I0)], integer(I1))  :- I1 #= -I0.
op_args_eval((-), [sign_numer_denom(-,N,D)], sign_numer_denom(+,N,D)).
op_args_eval((-), [sign_numer_denom(+,N,D)], sign_numer_denom(-,N,D)).

% reciprocal
op_args_eval((/), [Arg], '1/0') :- Arg = ( integer(Z) | sign_numer_denom(_,Z,_) ), Z #= 0.
op_args_eval((/), ['0/0'], '0/0').
op_args_eval((/), [integer(0)], '1/0').
op_args_eval((/), ['1/0'], integer(0)).
op_args_eval((/), [integer(I)], integer(I)) :- I #= 1 ; I #= -1.
op_args_eval((/), [sign_numer_denom(S,N,D)], integer(I)) :-
  N #= 1, 
  ( S = (+), I #= D 
  ; S = (-), I #= -D
  ).
op_args_eval((/), [integer(I)], sign_numer_denom(S,1,D)) :-
  I #\= 0,
  D #= abs(I),
  ( D #=  I, S = (+)
  ; D #\= I, S = (-)
  ).
op_args_eval((/), [sign_numer_denom(S,D,N)], sign_numer_denom(S,N,D)) :- D #\= 1.



% fractional
op_args_eval('%', ['0/0'], '0/0').
op_args_eval('%', ['1/0'], '1/0').
op_args_eval('%', [Arg],integer(0)) :- Arg = integer(_) ; Arg = sign_numer_denom(_,N,N).
op_args_eval('%', [sign_numer_denom(S,N,D)], sign_numer_denom(S, N, D)) :- N #< D.
op_args_eval('%', [sign_numer_denom(S,N0,D0)],Eval) :- 
  N0 #> D0, numer_denom_fractNumer_fractDenom(N0,D0,N1,D1), 
  ( N1 #=  D1, Eval = sign_numer_denom(S, N1, D1)
  ; N1 #\= D1, Eval = integer(0)
  ).

% floor
op_args_eval(floor, ['0/0'], '0/0').
op_args_eval(floor, ['1/0'], '1/0').
op_args_eval(floor, [integer(I)], integer(I)).
op_args_eval(floor, [sign_numer_denom(S, N, D)], integer(I)) :- 
  ( S = (-), I #= (-N) div D
  ; S = (+), I #=   N  div D
  ).

% signedSqrt
op_args_eval(signedSqrt, ['0/0'], '0/0').
op_args_eval(signedSqrt, ['1/0'], '0/0').
op_args_eval(signedSqrt, [integer(I0)], Eval) :- 
  ( I0 #<  0, I1 #= abs(I0), S #= -1
  ; I0 #>= 0, I1 #= I0, S #= 1
  ),
  integer_squareroot(I1, Sqrt),
  Eval #= Sqrt*S.
op_args_eval(signedSqrt, [sign_numer_denom(S,N0,D0)], Eval ) :-
  integer_squareroot(N0,N1),
  integer_squareroot(D0,D1),
  ( N1 = D1, 
    ( S = (+), Eval = integer(1)
    ; S = (-), Eval = integer(-1)
    )
  ; dif(N1,D1),
    numer_demom_gcdNumer_gcdDenom(N1,D1,N2,D2),
    Eval = sign_numer_denom(S,N2,D2)
  ).

% addition
op_args_eval((+), [sign_numer_denom(S,N,D), integer(I)| Rest], Eval) :- op_args_eval((+), [integer(I), sign_numer_denom(S,N,D)| Rest], Eval).
op_args_eval((+), [integer(I), sign_numer_denom(S,N,D)| Rest], Eval) :-
  Abs #= abs(I),
  ( I #< 0, SI = (-)
  ; I #>=0, SI = (+)
  ),
  op_args_eval((+), [sign_numer_denom(S,N,D), sign_numer_denom(SI,Abs,1)| Rest], Eval).

op_args_eval((+), [sign_numer_denom(Sl,Nl,Dl), sign_numer_denom(Sr,Nr,Dr) | Rest], Eval) :-
  ( Sl = (+), Sln = 1; Sl = (-), Sln = -1 ),
  ( Sr = (+), Srn = 1; Sr = (-), Srn = -1 ),
  RawNumer0 #= Sln*Nl*Dr + Srn*Nr*Dl,
  ( Se = (-), RawNumer0 #< 0; Se = (+), RawNumer0 #>= 0 ),
  RawNumer1 #= abs(RawNumer0),
  RawDenom #= Dl*Dr,
  ( RawNumer1 #= 0, Calc = integer(0)
  ; RawNumer1 #\= 0,
    numer_demom_gcdNumer_gcdDenom(RawNumer1,RawDenom,Ne,De),
    Calc = sign_numer_denom(Se,Ne,De)
  ),
  ( Rest = [], Eval = Calc
  ; Rest = [_|_], op_args_eval((+), [Calc | Rest], Eval)
  ).
op_args_eval((+), ['0/0'| _], '0/0').
op_args_eval((+), [_, '0/0'| _], '0/0').
op_args_eval((+), [X, '1/0' | Rest], Eval) :- 
  dif(X,'0/0'), op_args_eval((+), ['1/0'|Rest], Eval).
op_args_eval((+), ['1/0', X| Rest], Eval) :-
  dif(X,'0/0'),
  ( Rest = [], Eval = '1/0'
  ; Rest = [_|_],  op_args_eval((+), ['1/0'|Rest], Eval)
  ).
op_args_eval((+), [integer(I), integer(J)| Rest], Eval) :-
  Calc #= I+J,
  ( Rest = [], Eval = integer(Calc)
  ; Rest = [_|_],  op_args_eval((+), [integer(Calc) | Rest], Eval)
  ).


% multiplication
op_args_eval((*), ['0/0'| _], '0/0').
op_args_eval((*), [_, '0/0' | _], '0/0').
op_args_eval((*), ['1/0', integer(I) | _], '0/0') :- I #= 0.
op_args_eval((*), [integer(I), '1/0' | _], '0/0') :- I #= 0.
op_args_eval((*), Args, Eval) :- 
  ( Args = ['1/0', X | Rest]
  ; Args = [X, '1/0' | Rest]
  ),
  dif(X, '0/0'), dif(X, integer(I)), I #= 0,
  Calc = '1/0',
  ( Rest = [_|_], op_args_eval((*), ['1/0' | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).
op_args_eval((*), Args, Eval) :- 
  ( Args = [sign_numer_denom(S,N0,D0), integer(I0) | Rest] 
  ; Args = [integer(I0), sign_numer_denom(S,N0,D0) | Rest]
  ),
  ( I0 #= 0,
    Calc = integer(0)

  ; I0 #\= 0,
    ( I0 #>= 0, SI0 = (+) 
    ; I0 #<  0, SI0 = (-) ),
    ( SI0 = S,    SEval = (+)
    ; dif(SI0,S), SEval = (-)
    ),
    RawNumer #= abs(I0)*N0,
    numer_demom_gcdNumer_gcdDenom(RawNumer,D0,N1,D1),
    ( D1 #= 1, 
      ( SEval = (+), I1 #= N1
      ; SEval = (-), I1 #= -N1
      ), 
      Calc = integer(I1)
    ; D1 #> 1,
      Calc = sign_numer_denom(SEval, N1,D1)
    )
  ),
  ( Rest = [_|_], op_args_eval((*), [Calc | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).
op_args_eval((*), [integer(Il), integer(Ir)| Rest], Eval) :-
  Calc #= Il * Ir,
  ( Rest = [_|_], op_args_eval((*), [integer(Calc) | Rest], Eval)
  ; Rest = [], Eval = integer(Calc)
  ).


op_args_eval((*), [sign_numer_denom(Sl,Nl,Dl), sign_numer_denom(Sr,Nr,Dr)| Rest], Eval) :-
  ( Sl = Sr, 
    Se = (+)
  ; ( Sl = (+), Sr = (-) 
    ; Sl = (-), Sr = (+)
    ), 
    Se = (-)
  ),
  RawNumer #= Nl*Nr, RawDenom #= Dl*Dr, numer_demom_gcdNumer_gcdDenom(RawNumer, RawDenom, Ne, De),
  Calc = sign_numer_denom(Se,Ne,De),
  ( Rest = [_|_], op_args_eval((*), [Calc | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).

% mod
op_args_eval('%', ['0/0'| _], '0/0').
op_args_eval('%', [_, '0/0' | _], '0/0').
op_args_eval('%', [_, integer(0) | _], '0/0').
op_args_eval('%', [_, '1/0' | _], '0/0').
op_args_eval('%', [integer(Il), X | Rest], Eval) :- 
  Il #= 0,
  ( X = integer(Ir),             Ir #\= 0
  ; X = sign_numer_denom(_,N,_), N #\=0
  ),
  Calc = integer(0),
  ( Rest = [_|_], op_args_eval('%', [Calc | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).
op_args_eval('%', ['1/0', integer(I) | Rest], Eval) :-
  I #\=0,
  Calc = '1/0',
  ( Rest = [_|_], op_args_eval('%', [Calc | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).
op_args_eval('%', [integer(Il), integer(Ir) | Rest], Eval) :-
  Ir #\=0,
  Calc #= Il mod Ir,
  ( Rest = [_|_], op_args_eval('%', [integer(Calc) | Rest], Eval)
  ; Rest = [], Eval = integer(Calc)
  ).
op_args_eval('%', [R, integer(I) | Rest], Eval) :-
  R = sign_numer_denom(_,_,_),
  I #\=0,
  ( I #> 0, SI = (+) 
  ; I #< 0, SI = (-)
  ),
  Abs #= abs(I),
  op_args_eval('%', [R, sign_numer_denom(SI,Abs,1) | Rest], Eval).
op_args_eval('%', [integer(I), R | Rest], Eval) :-
  I #\=0,
  R = sign_numer_denom(_,_,_),
    ( I #> 0, SI = (+) 
  ; I #< 0, SI = (-)
  ),
  Abs #= abs(I),
  op_args_eval('%', [sign_numer_denom(SI,Abs,1), R | Rest], Eval).
op_args_eval('%', [sign_numer_denom(Sl,Nl0,Dl), sign_numer_denom(Sr,Nr0,Dr) | Rest], Eval) :-
  ( ( Sl = Sr,    S = (+)
    ; dif(Sl,Sr), S = (-)
    ),
    RawDenom #= Dl*Dr,
    Nl1 #= Nl0*Dr,
    Nr1 #= Nr0*Dl,
    RawNumer #= Nl1 mod Nr1,
    ( RawNumer #\= 0,
      numer_demom_gcdNumer_gcdDenom(RawNumer,RawDenom,N,D),
      ( D #\= 1, Calc = sign_numer_denom(S,N,D)
      ; D #=  1,
        ( S = (+), I =   N 
        ; S = (-), I #= -N
        ),
        Calc = integer(I)
      )
    ; RawNumer #= 0, Calc = integer(0)
    ),
    ( Rest = [_|_], op_args_eval('%', [Calc | Rest], Eval)
    ; Rest = [], Eval = Calc
    )
  ).

  



% subtraction 
op_args_eval((-), [L, R0 | Rest], Eval) :- 
  op_args_eval((-), [R0], R1),
  op_args_eval((+), [L, R1], Calc),
  ( Rest = [_|_], op_args_eval((-), [Calc | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).

% division
op_args_eval((/), [L, R0 | Rest], Eval) :- 
  op_args_eval((/), [R0], R1),
  op_args_eval((*), [L, R1], Calc),
  ( Rest = [_|_], op_args_eval((/), [Calc | Rest], Eval)
  ; Rest = [], Eval = Calc
  ).

% ---- interpreter ----
source_eval(Src0, Eval) :-
  append(Src0," ",Src1),
  phrase(tokens(T), Src1), 
  phrase(ast(A), T), 
  ast_eval(A, Eval).

source_evalFormatted(Src, Form) :-
  source_eval(Src, Eval),
  eval_formatted(Eval,Form).

eval_formatted(Eval,Form) :-
  ( Eval = integer(I), number_chars(I,Form)
  ; Eval = sign_numer_denom(S,N,D), number_chars(N,Numer), number_chars(D,Denom), append(Numer,"/",Head), append(Head,Denom,Fraction),
    ( S=(+), Form = Fraction
    ; S=(-), append("-",Fraction,Form)
    )
  ; (Eval = '1/0' ; Eval = '0/0'), atom_chars(Eval, Form)
  ).

% utility for rational numbers

numer_denom_fractNumer_fractDenom(N0,D0,N3,D3) :- N0 #> D0, N1 #= D0-N0, numer_denom_fractNumer_fractDenom(N1,D0,N3,D3).
numer_denom_fractNumer_fractDenom(N0,D0,N1,D1) :- N0 #=< D0, gcd(N0, D0, GCD), N1 #= N0/GCD, D1 #= D0/GCD.

numer_demom_gcdNumer_gcdDenom(N,D,GN,GD) :-
    gcd(N, D, Div),
    GN #= N/Div,
    GD #= D/Div.

gcd(0,0,1).
gcd(X,Y,D)  :- X #>= 0, Y  #>=  0, gcdInner(X,Y,D).
gcd(X0,Y,D) :- X0 #< 0, X1 #= -X0, gcd(X1, Y, D).
gcd(X,Y0,D) :- Y0 #< 0, Y1 #= -Y0, gcd(X, Y1, D).


gcdInner(0,X,X)  :- X #> 0.
gcdInner(X,0,X)  :- X #> 0.
gcdInner(X,Y0,D) :- X #> 0, X #=< Y0, Y1 #= Y0-X, gcdInner(X, Y1, D).
gcdInner(X,Y,D)  :- Y #> 0, X #> Y,               gcdInner(Y,X,D).

integer_squareroot(0,0).
integer_squareroot(X,1):- X #\= 0, X #< 4.
integer_squareroot(I,Sqrt) :-
  I #>= 4,
  integer_largestPow2LessThan(I,UB),
  UBS #= UB*UB,
  integer_sqrt_upBound_upBSquare(I,Sqrt,UB,UBS).
integer_sqrt_upBound_upBSquare(I,S,UB0,UBS0):-
  UB1 #= UB0-1,
  UBS1 #= UB1*UB1,

  ordering_left_right(UIOrd0, UBS0, I),
  ordering_left_right(UIOrd1, UBS1, I),
  ( UIOrd0 = (=), S = UB0

  ; UIOrd0 = (>), ( UIOrd1 = (<) ; UIOrd1 = (=)), S = UB1

  ; UIOrd0 = (>),
    UIOrd1 = (>),
    UB2  #= (UB0 + (I // UB0)) // 2,
    UBS2 #= UB2*UB2,
    ordering_left_right(UIOrd2, UBS2, I),
    ( UIOrd2 = (=), S = UB2
    ; UIOrd2 = (>), integer_sqrt_upBound_upBSquare(I,S,UB2,UBS2)
    ; UIOrd2 = (<), integer_sqrt_upBound_upBSquare(I,S,UB1,UBS1)
    )
  ).

integer_largestPow2LessThan(0, 0).
integer_largestPow2LessThan(I, L) :-
  I #\= 0,
  integer_largestPow2_acc0_acc1(I,L,1,2).

integer_largestPow2_acc0_acc1(I,A0,A0,A1):- A1 #> I.
integer_largestPow2_acc0_acc1(I,L,_,A1):- A1 #=<  I, A2 #= A1*A1, integer_largestPow2_acc0_acc1(I,L,A1,A2).



ordering_left_right((<),X,Y) :- X #< Y.
ordering_left_right((=),X,Y) :- X #= Y.
ordering_left_right((>),X,Y) :- X #> Y.



% Tests

currentTests :- 
  displayTest__op_type_print((+), [rat, rat], yes).

displayTest__op_type_print((+), [rat, rat], YesNo) :-
  displayTestImpl__op_type_posArg_rets_print(
    (+), [rat, rat], [numer_denom(3,2), numer_denom(5,7)], 
    [ sign_numer_denom((+),31,14), sign_numer_denom((-),11,14), sign_numer_denom((+),11,14), sign_numer_denom((-),31,14) ],
    YesNo
  ),
  displayTestImpl__op_type_posArg_rets_print(
    (*), [rat, rat], [numer_denom(3,2), numer_denom(5,7)],
    [ sign_numer_denom((+),15,14), sign_numer_denom((-),15,14), sign_numer_denom((-),15,14), sign_numer_denom((+),15,14) ],
    YesNo
  ).

displayTestImpl__op_type_posArg_rets_print(Op, [rat, rat], [L, R], [E0,E1,E2,E3], YesNo) :-
  L = numer_denom(Ln, Ld),
  R = numer_denom(Rn, Rd),
  (YesNo = yes ; YesNo = no),
  L0 = sign_numer_denom((+),Ln,Ld),  R0 = sign_numer_denom((+),Rn,Rd),  op_args_eval(Op, [L0, R0], Eval0), 
  L1 = sign_numer_denom((-),Ln,Ld),  R1 = sign_numer_denom((+),Rn,Rd),  op_args_eval(Op, [L1, R1], Eval1),
  L2 = sign_numer_denom((+),Ln,Ld),  R2 = sign_numer_denom((-),Rn,Rd),  op_args_eval(Op, [L2, R2], Eval2),
  L3 = sign_numer_denom((-),Ln,Ld),  R3 = sign_numer_denom((-),Rn,Rd),  op_args_eval(Op, [L3, R3], Eval3),
  ( YesNo = yes -> writeAll([
      '(',Op,'  ',Ln,'/',Ld,'  ',Rn,'/',Rd,') = ', Eval0,' [ Expected : ',E0,' ]\n',
      '(',Op,' -',Ln,'/',Ld,'  ',Rn,'/',Rd,') = ', Eval1,' [ Expected : ',E1,' ]\n',
      '(',Op,'  ',Ln,'/',Ld,' -',Rn,'/',Rd,') = ', Eval2,' [ Expected : ',E2,' ]\n',
      '(',Op,' -',Ln,'/',Ld,' -',Rn,'/',Rd,') = ', Eval3,' [ Expected : ',E3,' ]\n',
      '\n'
    ]) 
  ; true
  ),
  E0 = Eval0,  E1 = Eval1,  E2 = Eval2,  E3 = Eval3,
  !. % this is only for testing

writeAll([]).
writeAll([X|Xs]) :- write(X), writeAll(Xs).