## Description

1 Introduction

Declarative programming is a programming paradigm that emphasises the expression of “what” the

problem is over “how” to solve the problem. You will gain experience of declarative programming

with Prolog (Logic Programming) and ML (Functional Programming) in this assignment.

You are supposed to test your work on the machine solar1.cse.cuhk.edu.hk using

• SICStus 3.12.7

• Standard ML of New Jersey, Version 110.0.7

They can be invoked using the commands sics and sml respectively.

2 Logic Programming

Implement the predicates or queries of the following problems in a Prolog program file named

“asg4.pl”, and recall the successor notation s() to represent natural numbers in this task. You

should clearly indicate using comments the corresponding question number of each problem.

1. Recall the list operations taught in lectures and tutorials.

(a) Define element last(X, L) which is true if the last element in list L is X. Example:

?- element last(e, [a,b,c,d,e]).

yes

(b) Define element n(X, L, N) which is true if the N-th element in list L is X. Example:

?- element n(c, [a,b,c,d,e], s(s(s(0)))).

yes

(c) Define remove n(X, L1, N, L2) which is true if the resulting list L2 is obtained from

L1 by removing the N-th element, and X is the removed element. Example:

?- remove n(X, [a,b,c,d,e], s(s(s(0))), L2).

X = c,

L2 = [a, b, d, e]

(d) Based on (c), give a query to find which list will become [c,b,d,e] after removing its

second element “a”.

(e) Define insert n(X, L1, N, L2) which is true if the resulting list L2 is obtained by

inserting X to the position before the N-th element of list L1. Example:

?- insert n(h, [a,b,c], s(s(0)), L2).

L2 = [a,h,b,c]

(f) Define repeat three(L1, L2) which is true if the resulting list L2 has each element in

list L1 repeated three times. Example:

?- repeat three([a,b,c,d,e],X).

X = [a,a,a,b,b,b,c,c,c,d,d,d,e,e,e]

(g) Based on (f), give a query to find which list will become [i,i,i,m,m,m,n,n,n] after

repeating each element of it for three times.

2. A multi-way tree is composed of a root and a sequence of sub-trees (children), which are

multi-way tree themselves. The list of sub-trees of a certain node is ordered from left to

right and also called a forest. The root of a multi-way tree is a node containing a value.

Diagrammatically, a multi-way tree consists of a set of nodes and lines connecting parents

1

a

b c d

e f g

Figure 1: An example of multi-way tree

and children. The nodes are depicted by circles with values written inside. A multi-way tree

is never empty.

In Prolog, we can represent a multi-way tree by the term “mt(X, F)”, where X denotes the

root and F denotes the forest of sub-trees. Please finish the following questions using the

successor notation s() to represent natural numbers in this task. You can use the sum/3

predicate from the lecture.

(a) Represent the multi-way tree in Figure 1 as a Prolog term, with order of the sub-trees

from left to right. (Hint: represent forest as a list of multi-way tree(s)).

(b) Define the predicate is tree(Term) which is true if Term represents a multi-way tree.

(c) Define the predicate num node(Tree, N) which is true if N is the number of nodes of

the given multi-way tree Tree.

(d) Define sum length(Tree, L) which is true if L is the sum of lengths of all internal

paths in Tree. The length of an internal path from the root node r to an internal node

n is the distance from r to n. For example, the sum of lengths of all internal paths in

the multi-way tree in Figure 1 is: 1 (b) + 1 (c) + 1 (d) + 2 (e) + 2 (f) + 2 (g) = 9

(i.e., s(s(s(s(s(s(s(s(s(0))))))))).

3 Functional Programming

Implement the required functions of the following problems in an ML program file named “asg4.ml”.

You should clearly indicate using comments the corresponding question number of each problem.

This task involves a card game simplified from Texas Hold’em. In each round, two players will

get five cards respectively. The player who has the better hand will win the game. You have to

implement several ML helper functions to determine the better hand.

Please consider the following eight different hands. (We refer to the rules defined on https:

//www.pagat.com/poker/rules/ranking.html.)

• Four of a kind

Four cards of the same rank – such as four queens. The fifth card, known as the kicker, can

be anything. Between two fours of a kind, the one with the higher set of four cards is higher,

so 3-3-3-3-A is beaten by 4-4-4-4-2. If two players have four of a kind of the same rank, the

rank of the kicker decides.

• Full House

2

This combination consists of three cards of one rank and two cards of another rank – for

example three sevens and two tens. When comparing full houses, the rank of the three cards

determines which is higher. For example 9-9-9-4-4 beats 8-8-8-A-A. If the threes of a kind

are equal, the rank of the pairs decides.

• Flush

Five cards of the same suit. When comparing two flushes, the highest card determines which

is higher. If the highest cards are equal then the second highest card is compared; if those

are equal too, then the third highest card, and so on. For example ♠K-♠J-♠9-♠3-♠2 beats

♦K-♦J-♦7-♦6-♦5 because the nine beats the seven. If all five cards are equal, the flushes

are equal.

• Straight

Five cards of mixed suits in sequence. For example ♠Q-♦J-♥10-♠9-♣8. When comparing

two sequences, the one with the higher ranking top card is better. Ace can count high or low

in a straight, but not both at once. So A-K-Q-J-10 and 5-4-3-2-A are valid straights, but

2-A-K-Q-J is not. 5-4-3-2-A, known as a wheel, is the lowest kind of straight, the top card

being the five.

• Three of a Kind

Three cards of the same rank plus two unequal cards. When comparing two threes of a kind

the rank of the three equal cards determines which is higher. If the sets of three are of equal

rank, then the higher of the two remaining cards in each hand are compared, and if those

are equal, the lower odd card is compared. So for example 5-5-5-3-2 beats K-4-4-4-5, which

beats Q-9-4-4-4, which beats Q-8-4-4-4.

• Two Pairs

A pair consists of two cards of equal rank. In a hand with two pairs, the two pairs are of

different ranks (otherwise you would have four of a kind), and there is an odd card to make

the hand up to five cards. When comparing hands with two pairs, the hand with the highest

pair wins, irrespective of the rank of the other cards – so J-J-2-2-A beats 10-10-9-9-8 because

the jacks beat the tens. If the higher pairs are equal, the lower pairs are compared, so that

for example 8-8-6-6-3 beats 8-8-5-5-4. Finally, if both pairs are the same, the odd cards are

compared, so Q-Q-5-5-4 beats Q-Q-5-5-3.

• Pair

A hand with two cards of equal rank and three cards which are different from these and from

one another. When comparing two such hands, the hand with the higher pair is better – so

for example 6-6-4-3-2 beats 5-5-4-3-2. If the pairs are equal, compare the highest ranking

odd cards from each hand; if these are equal compare the second highest odd card, and if

these are equal too compare the lowest odd cards. So J-J-9-3-2 beats J-J-8-7-3 because the

9 beats the 8.

• Nothing

Five cards which do not form any of the combinations listed above. The cards must all be

of different ranks, not consecutive, and contain at least two different suits. When comparing

two such hands, the one with the better highest card wins. If the highest cards are equal the

second cards are compared; if they are equal too the third cards are compared, and so on.

So A-J-9-5-3 beats A-10-9-6-4 because the jack beats the ten.

Note that cards are already sorted in descending order according to the rank (with A always

ordered last). The order of cards of the same rank is arbitrary. Each card has two attributes,

i.e., suit and rank. The type definition of a card in ML is shown below. The joker cards are not

included in this game. To further simplify the problem, we convert all ranks to integers. i.e., A =

1, J = 11, Q = 12, and K = 13.

datatype suit = Clubs | Diamonds | Hearts | Spades;

3

When you implement the following functions, please use pattern matching as much as possible.

1. Write an ML function check flush, which takes a list of five cards and returns if the hand

is a flush.

2. Write an ML function compare flush, which takes two flush card lists. The return value is

a string selected from three candidates. i.e., “Hand 1 wins”, “Hand 2 wins” and “This is a

tie”.

3. Write an ML function check straight, which takes a list of five cards and returns if the

hand is a straight.

4. Write an ML function compare straight, which takes two straight card lists. The return

value is a string selected from three candidates. i.e., “Hand 1 wins”, “Hand 2 wins” and

“This is a tie”.

5. Write an ML function count patterns, which takes a list of five cards and returns the hand

type (Nothing, Pair, Two Pairs, Three of a Kind, Full House, Four of a Kind) and a list of

rank-quantity pairs. Note that the list should be ordered according to the order of comparison

of each type of hand.

Here are some examples to help you understand the problem:

• The card list [(Clubs, 13), (Clubs, 11), (Spades, 7), (Spades, 3), (Hearts, 2)] should

return (Nothing, [(13, 1), (11, 1), (7, 1), (3, 1), (2, 1)]).

• The card list [(Spades, 11), (Spades, 9), (Hearts, 8), (Diamond, 8), (Diamonds, 3)]

should return (Pair, [(8, 2), (11, 1), (9, 1), (3, 1)]).

• The card list [(Clubs, 13), (Spades, 13), (Hearts, 6), (Spades, 1), (Diamonds, 1)] should

return (Two Pairs, [(13, 2), (1, 2), (6, 1)]).

• The card list [(Clubs, 10), (Clubs, 9), (Hearts, 9), (Spades, 9), (Spades, 3)] should return

(Three of a Kind, [(9, 3), (10, 1), (3, 1)]).

• The card list [(Diamonds, 6), (Clubs, 6), (Spades, 6), (Spades, 4), (Diamonds, 4)] should

return (Full House, [(6, 3), (4, 2)]).

• The card list [(Diamonds, 11), (Spades, 11), (Clubs, 11), (Hearts, 11), (Hearts, 10)]

should return (Four of a Kind, [(11, 4), (10, 1)]).

6. Write an ML function compare count, which takes two card lists and returns a string selected

from three candidates. i.e., “Hand 1 wins”, “Hand 2 wins” and “This is a tie”. You only

need to consider the remaining six cases except flush and straight, and assume that

Nothing < Pair < Two Pairs < Three of a Kind < Full House < Four of a Kind. 4 Submission Guidelines Please read the guidelines CAREFULLY. If you fail to meet the deadline because of submission problem on your side, marks will still be deducted. So please start your work early! 1. In the following, SUPPOSE your name is Chan Tai Man, your student ID is 1155234567, your username is tmchan, and your email address is tmchan@cse.cuhk.edu.hk. 2. In your source files, insert the following header. REMEMBER to insert the header according to the comment rule of Prolog and ML. 4 /∗ ∗ CSCI3180 Principles of Programming Languages ∗ ∗ — Declaration — ∗ ∗ I declare that the assignment here submitted is original except for source ∗ material explicitly acknowledged. I also acknowledge that I am aware of ∗ University policy and regulations on honesty in academic work, and of the ∗ disciplinary guidelines and procedures applicable to breaches of such policy ∗ and regulations, as contained in the website ∗ http://www.cuhk.edu.hk/policy/academichonesty/ ∗ ∗ Assignment 4 ∗ Name : Chan Tai Man ∗ Student ID : 1155234567 ∗ Email Addr : tmchan@cse.cuhk.edu.hk ∗/ The sample file header is available at http://course.cse.cuhk.edu.hk/~csci3180/resource/header.txt 3. Late submission policy: less 20% for 1 day late and less 50% for 2 days late. We shall not accept submissions more than 2 days after the deadline. 4. Tar your source files to username.tar by tar cvf tmchan.tar asg4.pl asg4.ml 5. Gzip the tarred file to username.tar.gz by gzip tmchan.tar 6. Uuencode the gzipped file and send it to the course account with the email title “HW4 studentID yourName” by uuencode tmchan.tar.gz tmchan.tar.gz \ | mailx -s “HW4 1155234567 Chan Tai Man” csci3180@cse.cuhk.edu.hk 7. Please submit your assignment using your Unix accounts. 8. An acknowledgement email will be sent to you if your assignment is received. DO NOT delete or modify the acknowledgement email. You should contact your TAs for help if you do not receive the acknowledgement email within 5 minutes after your submission. DO NOT re-submit just because you do not receive the acknowledgement email. 9. You can check your submission status at http://course.cse.cuhk.edu.hk/~csci3180/submit/hw4.html. 10. You can re-submit your assignment, but we will only grade the latest submission. 11. Enjoy your work :>

5