# 程序代写代做代考 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: We’re using the ocaml data structure (fuzzy set

membership function) from SDE1.

• The Bad News: We’re 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 set asserted 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

Here’s 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 x″j 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.0 2.0 3.0 4.0 5.0 6.0 7.0

x′1 x′2 x′3 x′4

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 *)

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 ocaml’s 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). Here’s 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 I’ll 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

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. Here’s 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