[SOLVED] Hive database ocaml data structure algorithm ECE/CPSC 3520

ECE/CPSC 3520
Spring 2017

Software Design Exercise #2

Canvas submission only

Assigned 2/23/2017; Due 3/16/2017 11:59 PM

Contents

1 Preface 3
1.1 A Little Perspective . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Standard Remarks . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Preliminary Considerations Set Representations 4
2.1 Representing Set Membership Functions, i(x) . . . . . . . . . 4
2.2 Corresponding ocaml Representation Signatures . . . . . . . . 5
2.3 The Overall Process . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Set Manipulations and Functionality to Implement (max-min

Inference) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Prototypes, Signatures and Examples of Functions to be De-
veloped 7
3.1 set intersect . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 listMaxTuples . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 listMaxTupleValue . . . . . . . . . . . . . . . . . . . . . . . 9
3.4 truncateConsequentMu . . . . . . . . . . . . . . . . . . . . . 10
3.5 listMaxTuplesAll . . . . . . . . . . . . . . . . . . . . . . . . 11
3.6 mom (Defuzzification) . . . . . . . . . . . . . . . . . . . . . . . 13

1

4 How We Will Grade Your Solution 13

5 ocaml Functions and Constructs Not Allowed 13
5.1 No let for Local or Global Variables . . . . . . . . . . . . . . 14
5.2 Only Pervasives Module and 3 Functions from the List Module

Are Allowed . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.3 No Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.4 No (Nested) Functions . . . . . . . . . . . . . . . . . . . . . . 14
5.5 Apriori Appeals . . . . . . . . . . . . . . . . . . . . . . . . . . 15

6 Format of the Electronic Submission 15

2

1 Preface

1.1 A Little Perspective

The Good News: Were using the ocaml data structure (fuzzy set
membership function) from SDE1.

The Bad News: Were doing other things with it in ocaml.

The Good News: You have 3 weeks to finish SDE2.

The Bad News: You have 3 weeks to finish SDE2.

1.2 Objectives

The objective of SDE 2 is to implement an ocaml version of a simple
fuzzy system for rule-based inference. This involves computations on
set membership functions resulting from the use of a fuzzy production. This
document specifies a number of functions which must be developed as part
of the effort.

Of extreme significance is the restriction of the paradigm to pure func-
tional programming, i.e., no imperative constructs are allowed. This
may make you unhappy and uncomfortable, but almost guarantees you will
learn something new.

This effort is straightforward, and, as mentioned, 4 weeks are allocated
for completion. The motivation is to:

Learn the paradigm of (pure) functional programming;

Implement a (purely) functional version of an interesting technology;

Deliver working functional programming-based software based upon
specifications; and

Learn ocaml.

1.3 Resources

As discussed in class, it would be foolish to attempt this SDE without care-
fully exploring:

3

1. The text, especially the many ocaml examples in Chapter 11;

2. The ocaml class lectures;

3. The background provided in this document;

4. In-class discussions, demonstrations and examples1; and

5. The ocaml reference manual (RTM).

You may use any linux version of ocaml 4.0.0

1.4 Standard Remarks

Please note:

1. This assignment assesses your effort (not mine). I will not debug
or design your code, nor will I install software for you. You (and only
you) need to do these things.

2. It is never too early to get started on this effort.

3. As noted, we will continue to discuss this in class.

2 Preliminary Considerations Set Repre-

sentations

Fuzzy (and crisp) sets are useful data structures for a number of computa-
tional tasks.

2.1 Representing Set Membership Functions, i(x)

You have gained some experience with this from SDE1, where correctness
was a concern. We revisit the necessary, basic data structures used to rep-
resent a set, via a membership function, i(x), in ocaml. One complica-
tion is the restriction of lists to be of the same type, therefore we employ
a combination of tuples and lists. We show this structure by the following
hello-world-scale example:

1Miss these at your peril.

4

(* -sample data structures- *)

let s_list1 = [(1,0.0);(2,0.3);(3,0.9);(4,1.0);(5,0.8);(6,0.5);(7,0.0)];;

let s_list2 = [(1,0.0);(2,0.5);(3,0.7);(4,0.8);(5,0.8);(6,0.25);(7,0.3)];;

let mu1 = ((1,7), s_list1);;

let mu2 = ((1,7), s_list2);;

2.2 Corresponding ocaml Representation Signatures

As seen above, we can subdivide the syntax of the membership function (a
tuple) into the domain tuple and the membership function tuple list.

val s_list1 : (int * float) list =

[(1, 0.); (2, 0.3); (3, 0.9); (4, 1.); (5, 0.8); (6, 0.5); (7, 0.)]

val s_list2 : (int * float) list =

[(1, 0.); (2, 0.5); (3, 0.7); (4, 0.8); (5, 0.8); (6, 0.25); (7, 0.3)]

val mu1 : (int * int) * (int * float) list =

((1, 7),

[(1, 0.); (2, 0.3); (3, 0.9); (4, 1.); (5, 0.8); (6, 0.5); (7, 0.)])

val mu2 : (int * int) * (int * float) list =

((1, 7),

[(1, 0.); (2, 0.5); (3, 0.7); (4, 0.8); (5, 0.8); (6, 0.25); (7, 0.3)])

Notes:

1. Carefully note the signatures from the above representations.

2. Assume the user is intelligent enough to restrict fuzzy set membership
values, i(x), to the interval [0,1]. Notice that set operations such as
intersection require:

The domains for the fuzzy sets to be the same. Here it is (1,7).
Corresponding elements in the singleton-based list representations

for all integers in the domain of each set.

For SDE2, you can assume this in your development. In other words, we
are working with good or well-formed syntactically and semantically
correct membership functions.

5

Orchard 15

Example 6

(defrule fuzzy-fuzzy-rule
;both antecedent and consequent are fuzzy objects

(temperature hot)
=>

(assert (temp_change little))
)

(temperature warm); a fact in the fact database

A graphical illustration of the matching of the fuzzy fact with the fuzzy pattern and the generation of the fuzzy
conclusion is shown below in Figure 8. Note that this type of inference method is commonly referred to as max-min
rule of inference. The conclusion set is simply clipped off at the z value. Figure 9 shows the same results using a
max-prod rule of inference. In this case the conclusion has all of its membership values scaled by the z value. The
FuzzyCLIPS function set-inference-type allows the control of which method is used.

Figure 8: Compositional rule of inference10 (max-min)

Figure 9: Compositional rule of inference (max-prod)

10 ??? is used to denote an unknown linguistic expression. The fuzzy set denoted by the linguistic expression

temp_change little once clipped or scaled is difficult to assign a linguistic expression to.

fact & antecedent fuzzy sets consequent fuzzy setasserted fuzzy set

temperature warm

temperature hot

temp_change little
temp_change???
asserted

fact & antecedent fuzzy sets consequent fuzzy set asserted fuzzy set

temperature warm

temperature hot

temp_change little
temp_change???
asserted

6

2.3 The Overall Process

Example 6 shows a sample fuzzy production and relevant fuzzy sets. Figure 8
shows the overall process of propagation of fuzzy sets via a fuzzy production.
We will implement max-min and MOM defuzzification. Ignore Figure 9,
unless you seek some perspective on alternative strategies.

The functions you will design, implement and test support the following:

1. Intersect CE and wm.

2. Determine the maximum membership function value of the above in-
tersection from step 1.

3. To get the asserted, or consequent, fuzzy set, we truncate the intensity
of the original consequent by the value computed in step 2.

4. To get an output value, we apply MOM defuzzification on the asserted,
or consequent, fuzzy set from step 3.

2.4 Set Manipulations and Functionality to Implement
(max-min Inference)

1. Set intersection;

2. Propagation of fuzzy sets via a fuzzy production condition element
(CE) mu (or ) and working memory (wm) mu contents to the fuzzy
production consequent fuzzy set mu; and

3. MOM defuzzification of the fuzzy production consequent fuzzy set mu.

3 Prototypes, Signatures and Examples of Func-

tions to be Developed

Notes:

The use of let in the following examples is only for illustration and
naming of the input i. let should not appear in your ocaml source
for anything except naming functions. See Section 5.

7

Carefully observe the function naming convention. Case mat-
ters. We will not rename any of the functions you submit.
Reread the preceding three sentences at least 3 times.

You may (actually, must) develop additional functions to assist in the
implementation of the required functions.

Carefully note the argument interface on all multiple-argument
functions you will design, implement and test. This may also
be verified by the signatures.

You should work through all the samples by hand to get a better idea of
the computation prior to function design, implementation and testing.

Note some of my signatures indicate polymorphic behavior on the fuzzy
set domain values. This is OK, although you should recall from SDE1
that we use int on our domain value representation and float for the
membership function value over the domain in the tuple list.

In what I show below, sometimes I use the entire membership function,
other times I use just the slist part. Be clear on what the each func-
tion expects as an argument and what it returns. Again, the function
description and all-important signature specify this.

3.1 set intersect

Set intersection for sets 1 and 2 is defined as the point-by-point minimum
of 1(x) and 2(x).

(**

Prototype: set_intersect mu1 mu2

Input(s): mu1 mu2

Returned Value: intersection of two input sets

Side Effects: none

Signature:

val set_intersect :

(a * b) * (c * d) list ->

(a * b) * (c * d) list -> (a * b) * (c * d) list =

Notes: Curried interface.

*)

8

Sample Use.

# set_intersect mu1 mu2;;

: (int * int) * (int * float) list =

((1, 7),

[(1, 0.); (2, 0.3); (3, 0.7); (4, 0.8); (5, 0.8); (6, 0.25); (7, 0.)])

#

3.2 listMaxTuples

Propagation of fuzzy production CE mu and wm mu contents to the conse-
quent mu is facilitated by finding the max value of the intersection of the
fuzzy production CE mu and wm mu.

(**

Prototype: listMaxTuples slist

Input(s): slist (list of int*float tuples, as shown in above mu)

Returned Value: Tuple whose membership function (float value) is largest.

Side Effects: none

Signature:

val listMaxTuples : (a * b) list -> a * b =

Notes: Assume used on list with single maximum mu value.

We will develop another function for multiple maxima.

*)

Sample Use.

# s_list1;;

: (int * float) list =

[(1, 0.); (2, 0.3); (3, 0.9); (4, 1.); (5, 0.8); (6, 0.5); (7, 0.)]

# listMaxTuples s_list1;;

: int * float = (4, 1.)

3.3 listMaxTupleValue

Here we return the value from the tuple in the above function.

(**

Prototype: listMaxTupleValue slist

9

Input(s): slist

Returned Value: value of membership function corresponding to maximum tuple,

i.e., tuple whose membership function (float value) is largest.

Side Effects: none

Signature: val listMaxTupleValue : (a * b) list -> b =

Notes: Might involve listMaxTuples.

*)

Sample Use.

# s_list1;;

: (int * float) list =

[(1, 0.); (2, 0.3); (3, 0.9); (4, 1.); (5, 0.8); (6, 0.5); (7, 0.)]

# listMaxTupleValue s_list1;;

: float = 1.

3.4 truncateConsequentMu

Heres where we adjust the consequent mu, based upon rule firing strength
(max of intersection of wm mu and CE mu).

(**

Prototype: truncateConsequentMu slist value

Input(s): original consequent mu (given in production)

Returned Value: modified consequent mu

(truncation at value)

Side Effects: none

Signature:

val truncateConsequentMu : (a * b) list -> b -> (a * b) list =

Notes: This is the truncation of the consequent fuzzy set at a level determined by parameter

value. Curried.

Sample Use.

# s_list1;;

: (int * float) list =

[(1, 0.); (2, 0.3); (3, 0.9); (4, 1.); (5, 0.8); (6, 0.5); (7, 0.)]

# truncateConsequentMu s_list1 0.5;;

: (int * float) list =

[(1, 0.); (2, 0.3); (3, 0.5); (4, 0.5); (5, 0.5); (6, 0.5); (7, 0.)]

10

3.5 listMaxTuplesAll

Here we consider the truncated membership function which probably has
more than one maximum valued tuple.

(**

Prototype: listMaxTuplesAll slist

Input(s): slist (propagated fuzzy set (consequent) mu)

Returned Value: list of all maximum-valued tuples

Side Effects: none

Signature:

val listMaxTuplesAll : (a * b) list -> (a * b) list =

Notes: Find ALL maximum-value tuples of slist

with possibly many equal maxima

*)

Sample Use.

# s_list2;;

: (int * float) list =

[(1, 0.); (2, 0.5); (3, 0.7); (4, 0.8); (5, 0.8); (6, 0.25); (7, 0.3)]

# listMaxTuplesAll s_list2;;

: (int * float) list = [(4, 0.8); (5, 0.8)]

11

22 FuzzyCLIPS Version 6.10d

Example 11

Figure 12: Example of COG defuzzification
For each shaded subsection in the figure above, the area and centre of grav-
ity is calculated according to the shape identified (i.e., triangle,
rectangle or trapezoid). The centre of gravity of the whole set is then
determined:

943.3
3.06.06.10.1

3.0333.66.05.56.1917.30.1333.2
x ====

++++++++++++
++++++++++++

====

5.4.2 Mean of Maxima Algorithm

The MOM algorithm returns the x-coordinate (x) of the point at which the maximum membership (y) value of the
set is reached.

Example 12

Given the fuzzy set illustrated in Figure 12: Example of COG defuzzification,
the MOM result would be 3.0.

If the maximum y value is reached at more than one point, then the average of all the x is taken. More formally:

====
====

J

1j

j

J

x
x

where xj are the x-coordinates of all the maxima, and J is the total number of maxima (see Figure 13: Examples of
MOM defuzzification).

1.0

0.8

0.6

0.4

0.2

x
0.0 1.02.0 3.04.05.0 6.07.0

x1 x2x3 x4
2.333 3.917 5.500 6.333

P1
P2

P3

P4

A1
1.0

A3
0.6 A4

0.3

A2
1.6

M
E
M
B
E
R
S
H
I
P

12

3.6 mom (Defuzzification)

Here we defuzzify the propagated fuzzy set using MOM (Mean of Maxima).
Figure 2 shows MOM.

(**

Prototype: mom maxlist

Input(s): list of maximum tuples from propagated (truncated) fuzzy set (consequent) mu

Returned Value: mom defuzzified value

Side Effects: none

Signature:

val mom : (int * a) list -> float =

Notes:

*)

Sample Use.

# m1;;

: (int * float) list = [(4, 0.8); (5, 0.8)]

# mom m1;;

: float = 4.5

4 How We Will Grade Your Solution

The script below will be used with varying input files and parameters.

#use sde2.caml;; (* YOUR ocaml source all the required functions

and any additional (supporting) functions you develop*)

#use inputs.caml;; (* OUR TEST inputs/cases/mu_i *)

(* sample invocation of the required functions *)

The grade is based primarily upon a correctly working solution.

5 ocaml Functions and Constructs Not Al-

lowed

Of extreme significance is the restriction of the paradigm to pure functional
programming (no side effects). No ocaml imperative constructs are
allowed. Recursion must dominate the function design process. To this
end, we impose the following constraints on the solution.

13

5.1 No let for Local or Global Variables

So that you may gain experience with functional programming, only the
applicative (functional) features of ocaml are to be used. Please reread the
previous sentence. This rules out the use of ocamls imperative features. See
Section 1.5 Imperative Features of the manual for examples of constructs
not to be used. To force you into a purely applicative style, let can only
be used for function naming. let or the keyword in cannot be used in
a function body. Reread the following sentence. Loops and local or global
variables or nested function definitions is prohibited.

5.2 Only Pervasives Module and 3 Functions from the
List Module Are Allowed

The only module you may use (other than Pervasives) is the List
module, and only the functions List.hd, List.tl and List.length
from this module. This means no list iterators. Anything else inhibits
further grading of your submission.

5.3 No Sequences

The use of sequence (6.7.2 in the ocaml manual) is not allowed.
Do not design your functions using sequential expressions or begin/end con-
structs. Here is an example of a sequence in a function body:

let print_assignment = function(student,course,section) ->

print_string student; (* first you evaluate this*)

print_string is assigned to ; (* then this *)

print_string course; (* then this *)

print_string section ; (* then this *)

print_int section; (* then this *)

print_string
;; (* then this and return unit*)

5.4 No (Nested) Functions

ocaml allows functions defined within functions definitions (another illegal
let use for SDE2). Heres an example of a nested function definition:

# let f a b =

let x = a +. b in

x +. x ** 2.;;

14

5.5 Apriori Appeals

If you are in doubt, ask and Ill provide a private-letter ruling.

The objective is to obtain proficiency in functional programming, not to try
to find built-in ocaml functions or features which simplify or trivialize the
effort. I want you to come away from SDE 2 with a perspective on (almost)
pure functional programming (no side effects).

6 Format of the Electronic Submission

The final zipped archive is to be named -sde2.zip, where
is your (CU) assigned user name. You will upload this to the Blackboard
assignment prior to the deadline.

The minimal contents of this archive are as follows:

1. A readme.txt file listing the contents of the archive and a brief de-
scription of each file. Include the pledge here. Heres the pledge:

Pledge:
On my honor I have neither given nor received aid on this
exam.

This means, among other things, that the code you submit is your
code.

2. The single ocaml source file for your function implementations. The file
is to be named sde2.caml. Note this file must include all the functions
defined in this document. It may also contain other helper or auxiliary
functions you developed.

3. A log of 2 sample uses of each of the required functions. Name this log
file sde2.log. Use something other than my examples.

The use of ocaml should not generate any errors or warnings. Recall the
grade is based upon a correctly working solution with the restrictions posed
herein.

15