src/HOL/Predicate_Compile_Examples/Code_Prolog_Examples.thy
changeset 41457 3bb2f035203f
parent 40271 6014e8252e57
child 41956 c15ef1b85035
equal deleted inserted replaced
41456:006d85ad56d3 41457:3bb2f035203f
    51 | "D \<noteq> N - B ==> D \<noteq> B - N ==> Da = D + 1 ==> nodiag B Da L ==> nodiag B D (N # L)"
    51 | "D \<noteq> N - B ==> D \<noteq> B - N ==> Da = D + 1 ==> nodiag B Da L ==> nodiag B D (N # L)"
    52 
    52 
    53 text {*
    53 text {*
    54 qdelete(A, [A|L], L).
    54 qdelete(A, [A|L], L).
    55 qdelete(X, [A|Z], [A|R]) :-
    55 qdelete(X, [A|Z], [A|R]) :-
    56 	qdelete(X, Z, R).
    56   qdelete(X, Z, R).
    57 *}
    57 *}
    58 
    58 
    59 inductive qdelete :: "int => int list => int list => bool"
    59 inductive qdelete :: "int => int list => int list => bool"
    60 where
    60 where
    61   "qdelete A (A # L) L"
    61   "qdelete A (A # L) L"
    62 | "qdelete X Z R ==> qdelete X (A # Z) (A # R)"
    62 | "qdelete X Z R ==> qdelete X (A # Z) (A # R)"
    63 
    63 
    64 text {*
    64 text {*
    65 qperm([], []).
    65 qperm([], []).
    66 qperm([X|Y], K) :-
    66 qperm([X|Y], K) :-
    67 	qdelete(U, [X|Y], Z),
    67   qdelete(U, [X|Y], Z),
    68 	K = [U|V],
    68   K = [U|V],
    69 	qperm(Z, V).
    69   qperm(Z, V).
    70 *}
    70 *}
    71 
    71 
    72 inductive qperm :: "int list => int list => bool"
    72 inductive qperm :: "int list => int list => bool"
    73 where
    73 where
    74   "qperm [] []"
    74   "qperm [] []"
    75 | "qdelete U (X # Y) Z ==> qperm Z V ==> qperm (X # Y) (U # V)"
    75 | "qdelete U (X # Y) Z ==> qperm Z V ==> qperm (X # Y) (U # V)"
    76 
    76 
    77 text {*
    77 text {*
    78 safe([]).
    78 safe([]).
    79 safe([N|L]) :-
    79 safe([N|L]) :-
    80 	nodiag(N, 1, L),
    80   nodiag(N, 1, L),
    81 	safe(L).
    81   safe(L).
    82 *}
    82 *}
    83 
    83 
    84 inductive safe :: "int list => bool"
    84 inductive safe :: "int list => bool"
    85 where
    85 where
    86   "safe []"
    86   "safe []"
    87 | "nodiag N 1 L ==> safe L ==> safe (N # L)"
    87 | "nodiag N 1 L ==> safe L ==> safe (N # L)"
    88 
    88 
    89 text {*
    89 text {*
    90 queen(Data, Out) :-
    90 queen(Data, Out) :-
    91 	qperm(Data, Out),
    91   qperm(Data, Out),
    92 	safe(Out)
    92   safe(Out)
    93 *}
    93 *}
    94 
    94 
    95 inductive queen :: "int list => int list => bool"
    95 inductive queen :: "int list => int list => bool"
    96 where
    96 where
    97   "qperm Data Out ==> safe Out ==> queen Data Out"
    97   "qperm Data Out ==> safe Out ==> queen Data Out"
   111   | Minus expr expr | Uminus expr | Pow expr int | Exp expr
   111   | Minus expr expr | Uminus expr | Pow expr int | Exp expr
   112 
   112 
   113 text {*
   113 text {*
   114 
   114 
   115 d(U + V, X, DU + DV) :-
   115 d(U + V, X, DU + DV) :-
   116 	cut,
   116   cut,
   117 	d(U, X, DU),
   117   d(U, X, DU),
   118 	d(V, X, DV).
   118   d(V, X, DV).
   119 d(U - V, X, DU - DV) :-
   119 d(U - V, X, DU - DV) :-
   120 	cut,
   120   cut,
   121 	d(U, X, DU),
   121   d(U, X, DU),
   122 	d(V, X, DV).
   122   d(V, X, DV).
   123 d(U * V, X, DU * V + U * DV) :-
   123 d(U * V, X, DU * V + U * DV) :-
   124 	cut,
   124   cut,
   125 	d(U, X, DU),
   125   d(U, X, DU),
   126 	d(V, X, DV).
   126   d(V, X, DV).
   127 d(U / V, X, (DU * V - U * DV) / ^(V, 2)) :-
   127 d(U / V, X, (DU * V - U * DV) / ^(V, 2)) :-
   128 	cut,
   128   cut,
   129 	d(U, X, DU),
   129   d(U, X, DU),
   130 	d(V, X, DV).
   130   d(V, X, DV).
   131 d(^(U, N), X, DU * num(N) * ^(U, N1)) :-
   131 d(^(U, N), X, DU * num(N) * ^(U, N1)) :-
   132 	cut,
   132   cut,
   133 	N1 is N - 1,
   133   N1 is N - 1,
   134 	d(U, X, DU).
   134   d(U, X, DU).
   135 d(-U, X, -DU) :-
   135 d(-U, X, -DU) :-
   136 	cut,
   136   cut,
   137 	d(U, X, DU).
   137   d(U, X, DU).
   138 d(exp(U), X, exp(U) * DU) :-
   138 d(exp(U), X, exp(U) * DU) :-
   139 	cut,
   139   cut,
   140 	d(U, X, DU).
   140   d(U, X, DU).
   141 d(log(U), X, DU / U) :-
   141 d(log(U), X, DU / U) :-
   142 	cut,
   142   cut,
   143 	d(U, X, DU).
   143   d(U, X, DU).
   144 d(x, X, num(1)) :-
   144 d(x, X, num(1)) :-
   145 	cut.
   145   cut.
   146 d(num(_), _, num(0)).
   146 d(num(_), _, num(0)).
   147 
   147 
   148 *}
   148 *}
   149 
   149 
   150 inductive d :: "expr => expr => expr => bool"
   150 inductive d :: "expr => expr => expr => bool"
   160 | "d x X (Num 1)"
   160 | "d x X (Num 1)"
   161 | "d (Num n) X (Num 0)"
   161 | "d (Num n) X (Num 0)"
   162 
   162 
   163 text {*
   163 text {*
   164 ops8(E) :-
   164 ops8(E) :-
   165 	d((x + num(1)) * ((^(x, 2) + num(2)) * (^(x, 3) + num(3))), x, E).
   165   d((x + num(1)) * ((^(x, 2) + num(2)) * (^(x, 3) + num(3))), x, E).
   166 
   166 
   167 divide10(E) :-
   167 divide10(E) :-
   168 	d(((((((((x / x) / x) / x) / x) / x) / x) / x) / x) / x, x, E).
   168   d(((((((((x / x) / x) / x) / x) / x) / x) / x) / x) / x, x, E).
   169 
   169 
   170 log10(E) :-
   170 log10(E) :-
   171 	d(log(log(log(log(log(log(log(log(log(log(x)))))))))), x, E).
   171   d(log(log(log(log(log(log(log(log(log(log(x)))))))))), x, E).
   172 
   172 
   173 times10(E) :-
   173 times10(E) :-
   174 	d(((((((((x * x) * x) * x) * x) * x) * x) * x) * x) * x, x, E)
   174   d(((((((((x * x) * x) * x) * x) * x) * x) * x) * x) * x, x, E)
   175 *}
   175 *}
   176 
   176 
   177 inductive ops8 :: "expr => bool"
   177 inductive ops8 :: "expr => bool"
   178 where
   178 where
   179   "d (Mult (Plus x (Num 1)) (Mult (Plus (Pow x 2) (Num 2)) (Plus (Pow x 3) (Num 3)))) x e ==> ops8 e"
   179   "d (Mult (Plus x (Num 1)) (Mult (Plus (Pow x 2) (Num 2)) (Plus (Pow x 3) (Num 3)))) x e ==> ops8 e"