My version is implemented as an old fashion console application, developed with unit tests (NUnit). Mock objects (with RhinoMock framework) are used to test from the input/output interaction point of view. Such kind of tests tells something like "when some request for the input will return some specific value that we prepare in advance, and then if the computation is correct, we should see some specific value in output".
In this post I will remind what the problem is, I'll give some snips of code with links to the sources, and other references from the msdn knowledge base.
I'll not cover advanced functional programming topics like monads (and actually I don't know if they could help to improve the design in this case; I have to investigate).
The project sources can be viewed and downloaded from
(The downloaded zip archive contains the source, a solution file produced by Xamarin, probably compatible with Visual Studio as well, and a .vim file containing some macro that I found useful to edit build and test the project from vim as well. External libraries like nunit and RhinoMock must be downloaded separately, and the references in the solution file may need to be fixed by your Ide (xamarin or Visual Studio), or even by editing the solution file (which is xml). I tried also xbuild to produce the binaries (instead of the Xamarin Ide) with mono as target. Probably msbuild with .net clr will work as well.)
Summarizing: I developed and tested it only under Mono 3.2.6 and F# 3.0 (for Mono) on a Mac laptop, using Xamarin, and sometimes also Vim.
The problem:
the user is invited to think about an animal, and the program will try to guess that animal, making some questions (like "is it a mammal?", "is it a fish?" etc...) to reduce the range of plausible guesses.
Questions and names of animals are stored in a binary tree. Leaf nodes contains the name of the animals, and non leaf nodes contain the questions.
Example: if a non leaf node contains the question "is it big?", then big animals must be found only under the yesBranch subtree, and the others animals only under the noBranch subtree (we may have troubles related to the fuzziness of term like big or small, but who cares, from now: we can just have some redundancy in knowledge because of this issue).
Example: only one leaf node is stored in the knowledge tree. In this case the engine will just guess you are thinking about an elephant, without making any question:
In the following example there is a two leaf nodes knowledge tree, separated by the question "is it big?". The engine will start asking if it is big, and then, according to the yes or no answer, it will guess that the thought animal it is Elephant or a Mouse
If the program fails its guess because the user was thinking about some other animal, then the program has the opportunity to increase the knowledge base, asking her/him to suggest a new question to distinguish the guessed animal from the thought animal and the relative yes/no answer. This is enough for the system to adapt the knowledge tree including this new leaf node reachable by the new question.
Example:
Suppose that the animal the user is thinking of is "ant": the program will ask if it is big, the user will answer no, and then the program will guess that the thought animal is a mouse.
The user will answer "no" and then so the program asks her/him to suggest as the new question to distinguish a mouse from an ant, and then she/he suggests something like "is it an insect?" and the relative answer: "yes". The program will so adapt the knowledge tree accordingly, that so will become as in the following picture:
Popular web sites like "akinator" probably work in a similar way (but they have more possible answers than only yes/no - "probably yes", "probably not", ...- an already huge knowledge base, and they are mede to guess real people - mostly famous - rather than animals name. Anyway the concept is almost the same.)
For a normal user, it may looks surprising how is it possible that a relatively low number of questions can lead to a fair guess, but the fact that few questions are enough to go deep in a huge database can be explained by mathematical properties of binaries tree data structure, which relates the number of nodes with the number of steps using a logarithmic law:
if the tree is "perfectly balanced", 10 steps are needed to guess an animal among 1024 possibilities, and if the animals are doubled (2048), then the steps needed are just one more: 11, and for 4096 leaf nodes the steps needed are 11. If the tree is not perfectly balanced the things are just a little bit worst. Anyway a logarithmic relation should still hold in the average case (as long as the user contribute adding nodes in a way that makes sense)
I defined the KnowledgeTree type as follows:
type KnowledgeTree = AnimalName of string | SubTree of Tree
and Tree = {Question: string; yesBranch: KnowledgeTree; noBranch: KnowledgeTree}
witch means that a Knowledge tree is an animal, or a question and two knowledge trees named yesBranch and noBranch (containing other knowledge trees).
An example of interaction with the program, that leads to the construction of the last tree show in the previous picture, starting from the first one, is as follows:
>think about an animal
[enter]
>is it a elephant?
no
>what animal was?
mouse
>please, write a yes/no question to distinguish a cat from a elephant
is it big?
>what is the answer to the question "is it big?" to distinguish a mouse from a elephant?
no
>ok
>think about an animal
[enter]
>is it big?
no
>is it a mouse?
no
>what animal was?
ant
>please, write a yes/no question to distinguish a ant from a cat
is it an insect?
>what is the answer to the question "is it an insect?" to distinguish a ant from a cat?
yes
>ok
>think about an animal
[enter]
>is it big?
no
>is it a mouse?
no
>is it a ant?
...
I used a pretty standard technique to to test input & output interaction: making the main just call another function (or method) passing to it instances of console based read/write interfaces (interfaces in term of O.O. programming).
Concretely:
This is the main:
[<EntryPoint>
let main argv =
let myOutputStream = new ConsoleOutput() :> OutStream
let myInputStream = new ConsoleInput() :> InStream
let tree = AnimalName "elephant"
runForever myOutputStream myInputStream tree Welcome
(source)
(the term Stream is used for input and output console, even if in functional programming it has also another meaning that I am not talking about here).
The OutStream and InStream interfaces are defined as:
type OutStream =
abstract Write: string -> unit
type InStream =
abstract Input: unit -> string
Their "Console" implementation are:
type ConsoleOutput() =
interface OutStream with
member this.Write(x) = printf "%s\n" x
type ConsoleInput() =
interface InStream with
member this.Input() = Console.ReadLine()
(source)
(The syntax ":> OutStream" used by the main is needed, and actually makes an explicit upcast to the OutStream interface,. This upcast is required, which looks quite unusual from a Java/C# point of view, but is safe as long as you are upcasting only to an interface that you know is implemented. Here In msdn is discussed the topic).
The following call
runForever myOutputStream myInputStream tree Welcome
consists in an infinite loop on standard input and output starting from the Welcome state, that I will show later.
There is an almost identical function
runUntilIndex myOutputStream myInputStream tree Welcome index
(source)
As you may guess, this one is used by the tests, that cannot run an infinite loop. Passing the initial state explicitly is useful for the tests to be more granular (example: a test assume we are in the state Welcome and another one assume we are in another state.
Actually runForever should not accept the state because it has to start always with Welcome. The parameter is there only to show the similarity with "runUntilIndex".
I have chosen to define states by the following type:
type state = | Welcome | InviteToThinkAboutAnAnimal | GuessingFromCurrentNode |AskWhatAnimalWas | ExpectingDiscriminatingQuestion | AnsweringDiscriminatingQuestion
(source)
When the program starts, the state is Welcome, and after that it goes to InviteToThinkAboutAnAnimal, and so on... the current state, the type of node we are in, and the user message determine the next state and the answer given by the program. This is regulated by "pattern matching".
The static analysis of a pattern matching, reveals incomplete pattern matching at edit or compile time, which means that if we try to mach one of such states, then we get a warning if some of the possible states is missing from the match cases (because either it means you don't need that state, and so you should remove it from the type, or either you need that type, but then it means that you should match it and if you don't, it is probably a bug).
Testing:
as said, some tests that make expectation about what should be written to the console if the user type some message, benefit from stubbing/mocking the input and the output, and by the possibility of defining a state (which will be encapsulated in a "playStructure" exchanged at each "user machine interaction"). Such test can then "tell", by tests, stories like: "When I am in this state, and I write this in input, then I expect that the program will write that in output".
(I have been a little bit creative in using an alternative to the classic given when then/arrange act assert structure of tests, particularly substituting the then - or assert - with a "verify expectations", because there are no assertion, but a verification that the expected call of the mock actually happened - and, in the case of the input stream, returning the specified values)
Some examples:
[<Test>]
let ``in the initial welcome state, should invite to think about an animal``() =
// setup
let mockrepo = new MockRepository()
let inStream = mockrepo.DynamicMock
let outStream = mockrepo.StrictMock
// expectations
Expect.Call(outStream.Write("think about an animal")) |> ignore
mockrepo.ReplayAll()
// arrange
let tree = AnimalName "elephant"
let initialState = Welcome
let numLoops = 0
// act
runUntilIndex outStream inStream tree initialState numLoops |> ignore
// verify expectations
mockrepo.VerifyAll()
(I used DynamicMock instead of StrictMock for the input because in this case we don't need any special input from the user. See this on StackOverflow about Dynamic vs Strict mock - in RhinoMock).
The following test describes when the use has in mind the only one leaf node present on the knowledge tree:
[<Test>]
let ``with a one leaf node knowledge tree, engine asks if it is the animal on that node, the user says yes, and so the engine answer with "yeah!"``() =
// setup
let mockrepo = new MockRepository()
let inStream = mockrepo.StrictMock
let outStream = mockrepo.StrictMock
// expectations
Expect.Call(outStream.Write("think about an animal")) |> ignore
Expect.Call(inStream.Input()).Return("whatever") |> ignore
Expect.Call(outStream.Write("is it a cat?")) |> ignore
Expect.Call(inStream.Input()).Return("yes") |> ignore
Expect.Call(outStream.Write("yeah!")) |> ignore
Expect.Call(inStream.Input()).Return("anything") |> ignore
mockrepo.ReplayAll()
// arrange
let tree = AnimalName "cat"
let initState = Welcome
let numOfLoops = 3
// act
runUntilIndex outStream inStream tree initState numOfLoops |> ignore
// verify expectations
mockrepo.VerifyAll()
I have some longer interaction tests I am not showing here. Those test are more fragile, but have the advantage that can explain "longer" interaction stories (i.e. I start with a node, then the structure becomes of two nodes, and then of three nodes and so on...)
About tests closer to the "real domain" I decided to test the change of the state and the message exchanged and some of the value of a record used to pass values:
[<Test>]
let ``at the initial state, Welcome, the user receive the message "please, think about an animal", and state becomes 'invitethinkaboutanimal ``()=
// arrange
let playStart = messageAndState "" Welcome (AnimalName "monkey")
// act
let result = consoleInteract playStart
// assert
Assert.AreEqual(InviteToThinkAboutAnAnimal, result.currentState)
Assert.AreEqual("think about an animal", result.messageFromEngine)
messageAndState will just build a more complex record defined as follow:
type playingStructure = {messageFromEngine: string;
mutable messageFromPlayer: string option;
currentState: state;
animalToBeLearned: string;
rootTree: AnimalKnowledge;
currentNode: AnimalKnowledge;
yesNoList: string list;
newDiscriminatingQuestion : string option}
The last part I am showing is the pattern matching related to the "state change" and message exchange between the player and the engine.
The consoleInteract function matches the states and the user messages, and returns a new "playingStructure" with the new state:
let consoleInteract playStructure =
let currentAnimal = match playStructure.currentNode with | AnimalName name -> name | _ -> "ERROR!"
let messageFromPlayer = match playStructure.messageFromPlayer with | Some X -> X | None -> ""
match playStructure.currentState with
| InviteToThinkAboutAnAnimal -> initState playStructure
| GuessingFromCurrentNode -> (
match playStructure.messageFromPlayer with
| Some "yes" -> (
match playStructure.currentNode with
| AnimalName _ -> sayYeah playStructure
| SubTree subTree -> yesSubTreeNavigation playStructure subTree
)
| Some "no" -> (
match playStructure.currentNode with
| AnimalName _ -> askWhatAnimalWas playStructure
| SubTree subTree -> noSubTreeNavigation playStructure subTree
)
| _ -> askToEnterYesOrNot playStructure
)
| Welcome -> welcomeMessage playStructure
| AskWhatAnimalWas -> askDiscriminatingQuestion playStructure messageFromPlayer currentAnimal
| ExpectingDiscriminatingQuestion -> askAnswerToDiscriminatingQuestion playStructure messageFromPlayer currentAnimal
| AnsweringDiscriminatingQuestion -> match playStructure.messageFromPlayer with
| (Some "yes"| Some "no") -> completeLearning playStructure
| _ -> haveToAnswerOnlyYesOrNot playStructure
The "messagefromplayer" contains a "option type" probably unnecessary.
Let me just show, to conclude, the code that make the program adapt the binary tree with a new question and a new animal:
let rec learn playStructure =
let currentAnimal =
match playStructure.currentNode with
| AnimalName name -> name
| _ -> failwith "ERROR, current node structure should be a leaf"
let question tree =
match tree with
| AnimalName name -> "is it a "+name+"?"
| SubTree {Question=question} -> question
let noBranch tree =
match tree with
|SubTree X -> X.noBranch
| _ -> failwith "consider the consistency of the yes no list"
let yesBranch tree =
match tree with
|SubTree X -> X.yesBranch
| _ -> failwith "consider the consistency of the yes no list"
let thisIsTheQuestion =
match playStructure.newDiscriminatingQuestion with
| Some X -> X
| None -> failwith "discriminating question cannot be empty"
match playStructure.yesNoList with
| [] -> match playStructure.messageFromPlayer with
| Some "yes" -> SubTree { Question=thisIsTheQuestion;
yesBranch = AnimalName playStructure.animalToBeLearned;
noBranch = AnimalName currentAnimal}
| Some "no" -> SubTree { Question=thisIsTheQuestion;
yesBranch = AnimalName currentAnimal;
noBranch = AnimalName playStructure.animalToBeLearned}
| _ -> failwith "called learn when user interaction is different from yes or no"
| "yes"::T -> SubTree {Question = question playStructure.rootTree;
yesBranch = learn (substituteYesNoList playStructure T);
noBranch= noBranch playStructure.rootTree
}
| "no"::T -> SubTree {Question = question playStructure.rootTree;
yesBranch = yesBranch playStructure.rootTree;
noBranch = learn (substituteYesNoList playStructure T)
}
UPDATE 8/14/2016: the previous two lines contained a bug that I reproduced by the test interaction test named "``update the knowledge tree starting from elephant (reproducing bug)``" in test file "https://github.com/tonyx/fsharpanimalquiz/blob/master/fsharpAnimalQuizKata/InteractionTests.fs"
and in the corresponding unit test "``deep descending the tree (reproducing bug)`` in the test file https://github.com/tonyx/fsharpanimalquiz/blob/master/fsharpAnimalQuizKata/UnitTests.fs
here there are the fixed version of those two lines:
| "yes"::T -> SubTree {Question = question playStructure.rootTree;
yesBranch = learn (substituteYesNoList {playStructure with rootTree = yesBranch playStructure.rootTree} T);
noBranch= noBranch playStructure.rootTree
}
| "no"::T -> SubTree {Question = question playStructure.rootTree;
yesBranch = yesBranch playStructure.rootTree;
noBranch = learn (substituteYesNoList {playStructure with rootTree = noBranch playStructure.rootTree} T)
}
(source file: https://github.com/tonyx/fsharpanimalquiz/blob/master/fsharpAnimalQuizKata/BrainModule.fs )
END UPDATE.
As you may see, many "exceptional states" are explicitly raised in case of conditions that should not happen. We have virtually "preconditions" that assume, for example, that the list of the history of answer the user has given are only "yes" and "no".
I made external call to other function that contains some long list of values for the playStructure.
I didn't show everything of the code, and I will probably work more on it.
Conclusion:
Rhino can be used quite fairly with F#. I tried also Foq, but, more than a more fancy syntax, I didn't find it so lovable.
By using F# I learn how recursion, lists, mattern matching, records, tuples, type inference work. I don't think we have to use O.O. and other clr .net related features, that will be useful anyway later to create full web or desktop applications.
I will take a look to mvc for F# later, and will come back to this topic.
Future directions: how to manage the same domain when there are more users that perhaps need to modify the tree at the same time. I think I'll manage a "event sources"-like solution.
Thanks for reading, sorry for typos, if any.
(update 8/14/2016: source code is here https://github.com/tonyx/fsharpanimalquiz )
No comments:
Post a Comment