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.
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:
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
It is straightforward to see that if we ask whether is connected to any node, the answer would be false. Now, what if the graph is changed, say by adding a new node and an edge from to ? Of course, the above procedure will return the wrong answer when we ask whether is connected to . 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.
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).
Next, against the above knowledge base, we give the following query:
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.