Bool to concepts

[jrbeaumont]

Added a tool to convert Boolean set/reset functions into a concept specification.

This tool generates CNF forms of the functions from whatever format they are input. It then simplifies these. CNF can be used to generate a concept specification.

Also moved CNF -> DNF converter (Cartesian Product) and DNF simplifier into BooleanFunctions, so operations on Boolean Functions, CNF or DNF form are together.

Also, on a minor note, the boolToConcepts tool will allow a user to enter a set/reset function with -s/-r flags respectively. boolToConcepts and translate tools will both allow a user to enter an output file path using the -o flag.

[snowleopard]

Let's start with modules. I think it is useful to move all Boolean stuff into Tuura.Boolean.*:

• Tuura.Parser.Boolean -> Tuura.Boolean.Parser.
• Tuura.Plato.BoolToConcept.BooleanFunctions -> Tuura.Boolean.

However, some things should still be left in the tool:

• fromFunctions :: String -> String -> (Bool, String).
• createConceptSpec :: [String] -> CNF String -> CNF String -> String.

I think some generic parts of the above two functions can be moved into Tuura.Concept.* where you could allow users to create concepts directly in Haskell from set/reset functions. For example:

combinationalGate :: Expr a -> a -> CircuitConcept a
combinationalGate setFunction signal = ...

Then there will be nice equivalences, e.g. andGate a b c == combinationalGate (and (Var a) (Var b)) c.

[jrbeaumont]

These sound like a good idea. Do you meanfromFunctions and createConceptSpec should be left in Tuura.Boolean? Or keep a module called Tuura.Plato.BoolToConcept? And leave these in there?

[jrbeaumont]

Also, as a thought, it will be tough to take an Expr a and with the resulting concept specification, and run translate/Main.hs. I am not sure how possible it is to run a translation from within a translation, if you know what I mean.

[jrbeaumont]

Ignore the previous comment, I've worked out how to produce a CircuitConcept a from Expr a

[jrbeaumont]

An issue I have found with combinationalGate :: Expr a -> a -> CircuitConcept a is that several Tuura.Boolean functions require Ord a => and so, using it in a concept specification doesn't work without being able to add Ord a => in the declaration.

[jrbeaumont]

Refactored the modules.

[snowleopard]

using it in a concept specification doesn't work without being able to add Ord a => in the declaration.

Ah, sure, go ahead and add it -- it's a relatively minor constraint.

[jrbeaumont]

It needs to be added in the declaration in a Concept file. e.g.

circuit :: Ord a => a -> a -> a -> CircuitConcept a
circuit a b c = ...

[snowleopard]

It needs to be added in the declaration in a Concept file. e.g.

Hmm, don't do this yet. Just define the combinationalGate function if you can.

[jrbeaumont]

I will see what I can do, maybe provide some errors if there are any and we can work it out from there. I was thinking of maybe providing one for a String too. I.e combinationGate :: String -> Signal -> CircuitConcept a Where the String is then parsed for a Boolean tree. So for example a*b would also work. What do you think?

[jrbeaumont]

I have implemented combinationalGate, and adjusted some of the functions to avoid needing ord, and it can be used in concept specifications now.

[snowleopard]

I've left a few comments, will do another review later today.

[jrbeaumont]

I have made those changes. hlint really helped.

[snowleopard]

OK, that's enough comments for now -- please ping me when for the next iteration.

[jrbeaumont]

@snowleopard: Next iteration done. I have noticed that not using parentheses in a set function causes it to evaluate it incorrectly. I should probably try to fix this. I believe it was initially my intention with or to try and force parentheses around every sub expression which would stop the ordering it takes. not was just there for clearer outputs with show so can continue to remain removed.

[snowleopard]

I have noticed that not using parentheses in a set function causes it to evaluate it incorrectly.

Can you give an example?

[jrbeaumont]

a*!b+!a*b An XOR, but it interprets this as a*!b

[snowleopard]

Is it parsed as a*(!b + !a*b)? Can you show the Expr after parsing?

[jrbeaumont]

After parsing it is "a" * !"b" + !"a" * "b". It doesn't help haha

[snowleopard]

I think you should derive Show for Expr, as otherwise it's not very useful. What does it print if derived?

[jrbeaumont]

Show is derived for Expr. The issue is I think it parses it too ambiguously, so eval doesn't work correctly. Showing after convertToCNF reveals: !"a"+!"b" * "a"+!"b" * "a"+"b"

[jrbeaumont]

Here is the way it has parsed it: AND (OR (AND ("a"NOT"b" ) NOT"a" ) "b") So (((a * !b) + !a) *b)

[snowleopard]

Show is derived for Expr.

No, it is not. It's your custom implementation, I meant deriving Show.

[snowleopard]

So (((a * !b) + !a) *b)

Aha, I see. So the parser doesn't handle operator precedence correctly. You need to fix this (and add some tests).

[jrbeaumont]

I think I've already fixed the precedence haha. New result: Or (And (Var "a") (Not (Var "b"))) (And (Var "b") (Not (Var "a"))) Which is: a*!b + b*!a

[jrbeaumont]

The precedence is now on And. So if someone wants to do an AO22, then they can do: a*b+c*d. However, if someone wants to do an OA22, the need to add parentheses: (a+b)*(c+d) What do you think?

[snowleopard]

@jrbeaumont Yes, these results look fine! Could you show the commit that does the fix?

[jrbeaumont]

@snowleopard: The commit is pushed

[snowleopard]

Oh, that's a tiny change :)

[jrbeaumont]

More than a full-stop ;)

[jrbeaumont]

I'll add some testing for boolToConcept next.

[jrbeaumont]

@snowleopard Testing implemented and working.

[snowleopard]

@jrbeaumont Nice tests! I've added a few comments.

Can you also examples to Tuura.Boolean functions? Similar to how I do it here:

http://hackage.haskell.org/package/algebraic-graphs-0.0.5/docs/Algebra-Graph.html#v:hasVertex

2-3 examples per function would be great. Also, make sure you are using Haddock comments syntax, so you can then run stack haddock and get nicely formatted HTML documentation.

The examples you add should also be added into tests, to make sure they are correct. For example, here are tests for the above documentation example:

https://github.com/snowleopard/alga/blob/master/test/Algebra/Graph/Test/Generic.hs#L395-L405

[snowleopard]

@jrbeaumont By the way: in order to not blow up this PR too much, why don't you fix the minor things I mentioned in comments, leaving Haddock and examples for another PR?

[jrbeaumont]

A good idea. Let's get this merged, and I can do Haddock etc for the whole repo in another PR.

[snowleopard]

Good, let me know once the minor things are fixed.

[jrbeaumont]

@snowleopard: I have fixed those issues. Please check my implementation of function and complexGate before merging.

[snowleopard]

Just one last tweak and I'll merge :)

[jrbeaumont]

@snowleopard There we go!

[snowleopard]

Great, thanks! This is now merged.