Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment — Declarative Programming
1 Introduction
Declarative programming is a programming paradigm that expresses the logic of a computation
without describing its control flow. You will gain experience of declarative programming with an
emphasis on Prolog and ML in this assignment.
2 Logic Programming
Implement the required predicates or queries of the following two problems in a Prolog program file
named “asg4.pl”. You should clearly indicate using comments the corresponding question number
of each sub-problem. Note that the answers which are queries should be written in comments as
well.
1. Recall the successor notation for representing natural numbers, and the sum(X,Y,Z) relation
defined in the lecture which is true if Z is the sum of X and Y .
(a) Define natNum(X) which is true if X is a natural number.
(b) Define lt(X,Y) which is true if X is less than Y.
(c) Give a query to find natural numbers less than 3.
(d) Define geq(X,Y) which is true if X is equal to or greater than Y.
(e) Define max(X,Y,Z) which is true if Z is the maximum of X and Y.
(f) Based on sum/3, define difference(X,Y,Z) which is true if X minus Y is equal to Z.
(g) Based on lt/2, geq/2 and difference/3, define mod(X,Y,Z) which is true if X mod Y
is equal to Z.
2. A binary tree is either empty or composed of a root and two children, which are binary
trees themselves. The root of a binary tree is a node containing a value. Diagramatically, a
binary tree consists of a set of nodes and lines connecting parents and children. The nodes
are depicted by circles with values written inside. Empty binary trees are not shown in the
diagram.
Figure 1: An example of binary tree
In Prolog, we represent an empty tree by the atom “nil” and a non-empty tree by the term
“bt(X,L,R)”, where X denotes the root node, L and R denote the left and right subtrees
respectively.
1
(a) Represent the binary tree shown in Figure 1 as a Prolog term.
(b) Define the predicate isTree(Term), where “Term” can be any Prolog term. Predicate
isTree(Term) is true if “Term” represents a binary tree.
(c) Define the predicate isLeaf(X,Tree), where “X” is a tree node, “Tree” is a binary tree.
A leaf is a node with no children. Predicate isLeaf(X,Tree) is true if “X” is a leaf node
of the given “Tree”.