Created
January 24, 2024 17:04
-
-
Save ClarkeRemy/5710c4c590bbc9ca333e19073105cb71 to your computer and use it in GitHub Desktop.
Prolog S-expr
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| :- 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). | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment