Derivation is a popular example about symbolic computation,  i.e.  symbolic analysis from the mathematical approach.

This example demonstrates the expressive power and ease-of-use of symbolic manipulation in Prolog (more examples here: http://en.allexperts.com/e/p/pr/prolog.htm).

Procedural approach to Prolog, Derivation

d(X,X,1) :- !.                               /* 1  x     dx = 1                     */
d(C,X,0) :- atomic(C).                       /* 2  c     dx = 0                     */
d(-U,X,-A) :- d(U,X,A).                      /* 3  -u    dx = - d u dx              */
d(U+V,X,A+B) :- d(U,X,A), d(V,X,B).          /* 4  u+v   dx = d u dx + d v dx       */
d(U-V,X,A-B) :- d(U,X,A), d(V,X,B).          /* 5  u-v   dx = d u dx - d v dx       */
d(C*U,X,C*A) :- C \= X, d(U,X,A), !.         /* 6  c*u   dx = c*d u dx              */
d(U*V,X,B*U+A*V) :- d(U,X,A), d(V,X,B).      /* 7  u*v   dx = u*d v dx + v*d u dx   */
d(U/V,X,A) :- d(U*V^(-1),X,A).               /* 8  u/v   dx = d (u*v)^-1 dx         */
d(U^C,X,C*U^(C-1)*W) :- C \= X, d(U,X,W).    /* 9  u^c   dx = c*u^(c-1)*d u dx      */
d(log(U),X,A*U^(-1)) :- d(U,X,A).            /*10  ln(u) dx = u^-1 * d u dx         */

Derivation in Visual Prolog

d(int(_),_) = int(0). 

d(var(X),X) = int(1):- !.
d(var(_),_) = int(0):-!.
d(plus(U,V),X) = plus(d(U,X),d(V,X)).

d(minus(U,V),X) = minus(d(U,X),d(V,X)).

d(mult(U,V),X) = plus(mult(d(U,X),V),mult(U,d(V,X))).

d(div_(U,V),X) = div_(minus(mult(d(U,X),V),mult(U,d(V,X))),mult(V,V)).

d(ln(U),X) =  mult(div_(int(1),U),d(U,X)).

d(potens(E1,int(I)),X) = mult(mult(int(I),potens(E1,int(I-1))),d(E1,X)).

d(sin(U),X) = mult(cos(U),d(U,X)).

d(cos(U),X) = minus(int(0),mult(sin(U),d(U,X))).

d(tan(U),X) = mult(potens(sec(U),int(2)),d(U,X)).

Starting derivation

differentiate(STR) = ResultStr:-
  InputExpression = diff::parse(Str,EXP),
  DifferentiatedExpression = diff::d(InputExpression,"x"),
  OutputExpression = diff::reduce(DifferentiatedExpression),
  ResultStr = diff::writeexp(OutputExpression).

The Atomistic Correspondence for the Procedural Definition

Let’s assume SE to be the base class for all atomistic objects. It is then the definition for AHO. Let’s  Symbol be the definition for the whole model semantics, here derivation.

Model Weaver to create the atomistic model:

differentiateExpression(Str) = OutputExpression:-
   S = s::new(),
   BuiltModel = sEModelBuilder::build(S:parse(Str)),
   ResultExpression = BuiltModel:d("x"),
   ResultElement = seData::new(ResultExpression),
   OutputExpression = ResultElement:reduce().

Interface for the Symbol:

interface symbol
 domains
  exp      =
   var(string);
   int(integer);
   plus(exp,exp);
   minus(exp,exp);
   …
   potens(exp,exp);
   ref(se).          /* this is a reference to a symbolic element, AHO */
 predicates
   parse: (string) -> exp determ.
   writeExp: (exp) -> string.
 end interface symbol

To convert a procedural Prolog-derivation model into an atomistic one, there is only one definition needed to add into the original code:

d(ref(SE),X) =  SE:d(X).

Architecture for the Derivation Example

Summary

This application shows that it is possible to translate “procedural”, i.e. non-object-based programs into atomistic ones, when the semantics is formal.

Some links

Advertisements