Procedural and declarative reading of facts and pr

Question

I am not really sure how to go about giving the procedural and declarative reading of facts and predicates. I was wondering if anyone could give me some guidance on how to write them.

Here is my code for inserting a Key into a binary tree:

insert(Key, null, tree(key, null, null)).
insert(Key, tree(Root, LST, RST), tree(Root, NewLST, RST)) :-
    Key < Root,
    insert(Key, LST, NewLST).
insert(Key, tree(Root, LST, RST), tree(Root, LST, NewRST)) :-
    Key > Root,
    insert(Key, RST, NewRST).

Answer 1

Note: There are bugs with OP code in the question for a binary tree. The question was for the reading of the Prolog code not the fixing of the code.

Procedural reading based on Bratko, Section 9.3 Insertion and deletion in a binary tree pg. 231

T is a binary tree. A tree can be empty, have only a root, have one leaf, or have two leafs.

---

insert(Key, null, tree(key, null, null)).

Procedural reading:
The result of inserting Key to the empty tree null is the tree tree(key,null,null).

---

insert(Key, tree(Root, LST, RST), tree(Root, NewLST, RST)) :-
    Key < Root,
    insert(Key, LST, NewLST).

Proceduralreading:
If the root of T is greater than Key then insert Key into the left subtree of T.

---

insert(Key, tree(Root, LST, RST), tree(Root, LST, NewRST)) :-
    Key > Root,
    insert(Key, RST, NewRST).

Procedural reading:
If the root of T is less than Key then insert Key into the right subtree of T.

---

Declarative reading based on The Art of Prolog, Section 3.4 Binary Trees pg. 72

Declarative reading:

• Key can be inserted into a null tree
• or if it can be inserted into the left subtree if Key is a less than the value at node
• or if it can be inserted into the right subtree if Key is a greater than the value at node.

---

A personal note on why writing the declarative meaning is important.

When trying to understand the procedural meaning, for me it explains how the code works in the procedural mode where the input parameters are set and a value is returned.

?- insert(5,null,Tree).
Tree = tree(5, null, null) ;
false. 

Note: I fixed a bug with the OP code to get that query to work as demonstarted.

or

?- insert(3,tree(5,null,null),Tree).
Tree = tree(5, tree(3, null, null), null) ;
false.

When trying to understand the declarative meaning, for me it explains how the code works in other modes where the result is given and one or more of the parameters are variables, or all of the parameters are variables (can't remember what this is called, I think it is most general question).

In this case when writing the declarative meaning, and trying queries like

?- insert(Key,X,tree(5,null,null)).
Key = 5,
X = null ;
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [9] _8894<5
ERROR:    [8] insert(_8920,tree(5,_8930,null),tree(5,null,null)) at c:/users/eric/documents/projects/prolog/so_question_101.pl:6
ERROR:    [7] <user>
   Exception: (8) insert(_8238, _8240, tree(5, null, null)) ? creep

and

?- insert(Key,Tree,tree(Root,Left,Right)).
Key = Root,
Tree = Left, Left = Right, Right = null ;
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [9] _12488<_12490
ERROR:    [8] insert(_12514,tree(_12522,_12524,_12526),tree(_12530,_12532,_12534)) at c:/users/eric/documents/projects/prolog/so_question_101.pl:6
ERROR:    [7] <user>
% Execution Aborted

tells me that one or more of these need to be addressed:

1. The modes need to be defined for the predicate
2. Guard statements need to be added to avoid the errors
3. The predicate name needs to be changed from being procedural to declarative.
4. The code needs to be made pure
5. The means of evaluation needs to be changed, e.g. using constraint programming or something else.

---

So by learning how to add modes to code to go from procedural to declarative, one can also look in the reverse of how can this can help to write better code in procedural languages.

When I write code for programming languages that do not have algebraic data types as a first class notion such as Java I have to use many if or switch statements to cover all of the combinations of the data structure. Now there are cases where the code runs correctly with out an else or default but to make the code better when I write an if or switch, I always add the else or default with assert (false) and run the code. If the assert fails it typically indicates that my reasoning about the code was wrong, and I either rewrite the code or change the assert to a comment explaining why the else or default case can occur but is not needed.