# 程序代写代做代考 prolog data structure CSCI3180 – Principles of Programming Languages – Spring 2017

CSCI3180 – Principles of Programming Languages – Spring 2017

Assignment 4 — Declarative Programming

Deadline: Apr 23, 2017 (Sunday) 23:59

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. A binary tree is either empty or composed of a root and two children, which are binary trees
themselves. A binary tree consists of a set of nodes and lines connecting parent with children.
The nodes are depicted by circles with labels written inside.

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.

(a) Represent the binary tree shown in Figure 1(a) 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 mirror(Tree1, Tree2), where “Tree1” and “Tree2” are both
Prolog terms representing binary trees. Predicate mirror(Tree1, Tree2) is true if
“Tree1” and “Tree2” are mirror images of each other. For example, nil is the mirror
of nil. The two trees in Figure 1(b) are mirror images of each other.

(d) Give a query to generate the mirror image of the tree on the left-hand side in Figure 1(b).

(e) Based on mirror/2, define symmetric(Tree), where “Tree” is a Prolog term repre-
senting a binary tree. Predicate symmetric(Tree) is true if “Tree” is symmetric. For

1

example, nil and a single-node tree are both symmetric. The tree in Figure 1(c) is a
symmetric tree.

2. 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 uint num(X) which is true if X is a natural number.

(b) Define gt(X,Y) which is true if X is greater than Y.

(c) Give a query to list all natural numbers less than 3.

(d) Based on sum/3, define product(X,Y,Z) which is true if Z is the product of X and Y.

(e) Give a query to compute the product of 2 and 3.

(f) Give a query to compute the result of 8 divided by 4.

(g) Based on sum/3, define intdiv(X,Y,Z) which is true if Z is the integer quotient of X