Classical Programming vs. Knowledge-based Programming: Example

Continuing from my last post, let me give you an example on how classical programming differs from knowledge-based programming (the example is taken from Prof. Franz Baader's lecture notes). Consider the acyclic graph in the picture below.

With regards to the above acyclic graph, we would like to solve the following problem: given to node $latex x$ and $latex y$ in the graph, determine whether these two nodes are connected.

In the classical programming, this problem can be solved by giving a procedure that gives you precisely the desired answer, namely "yes" if  both nodes are connected, and "no" otherwise. This procedure might be something like this:

[sourcecode language="ruby" light="true" wraplines="false"]

procedure connected(x,y)
if x = a then
if y = b or y = c then
return true
else
return (connected(b,y) or connected(c,y))
else
if x = b then
if y = d or y = e then
return true
else
return false
else
if x = c then
if y = e then
return true
else
return false
else
return false
[/sourcecode]

It is straightforward to see that if we ask whether $latex e$ is connected to any node, the answer would be false. Now, what if the graph is changed, say by adding a new node $latex f$ and an edge from $latex e$ to $latex f$? Of course, the above procedure will return the wrong answer when we ask whether $latex e$ is connected to $latex f$. We might have to modify the whole program to incorporate this new case.

On the other hand, the knowledge-based programming will solve the above problem in a different way. First, the graph, i.e., the problem description and its restrictions are specified explicitly as the knowledge about graph and the meaning of "connected". For example, the following knowledge base gives a correct description of the graph and the "connectedness" between nodes in the graph.

[sourcecode language="ruby" light="true" wraplines="false"]

directly-connected(a,b).
directly-connected(a,c).
directly-connected(b,d).
directly-connected(b,e).
directly-connected(c,e).

connected(x,y) if directly-connected(x,y).
connected(x,y) if directly-connected(x,z) and connected(z,y).

[/sourcecode]

Next, against the above knowledge base, we give the following query:

[sourcecode language="ruby" light="true" wraplines="false"]

connected(a,b)?

[/sourcecode]

To answer the above query, we simply run a general problem solver and get the answer. Thus, classical programming focuses more on "how" to obtain the solution, while knowledge-based programming would focus more on "what" the solution would be like.

In practice, this distinction may not be as strict as what the example illustrated. Classical programming typically also allows parts of the program to contain the data structures that describe the problem specification, whereas some knowledge-based programming applications encode the knowledge about application in the program using procedural rules.

In knowledge representation and reasoning, one of the main research theme is about formulating and specifying languages that allow users to express knowledge symbolically and developing algorithms which can perform as a general problem solver for queries by users to the knowledge base.

Related articles

• Classical Programming vs. Knowledge-based Programming