程序代写代做代考 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
