www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Tristate - wanna?

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
While messing with std.allocator I explored the type below. I ended up 
not using it, but was surprised that implementing it was quite 
nontrivial. Should we add it to stdlib?

Theory: http://en.wikipedia.org/wiki/Three-state_logic

struct Tristate
{
     private ubyte value;
     private static Tristate make(ubyte b)
     {
         Tristate r = void;
         r.value = b;
         return r;
     }

     enum no = make(0), yes = make(1), unknown = make(4);

     this(bool b) { value = b; }

     void opAssign(bool b) { value = b; }

     Tristate opUnary(string s)() if (s == "~")
     {
         return this == unknown ? this : make(!value);
     }

     Tristate opBinary(string s)(Tristate rhs) if (s == "|")
     {
         // | yields 0, 1, 4, 5
         auto v = value | rhs.value;
         return v == 4 ? unknown : make(v & 1);
     }

     Tristate opBinary(string s)(Tristate rhs) if (s == "&")
     {
         // & yields 0, 1, 4
         return make(value & rhs.value);
     }

     Tristate opBinary(string s)(Tristate rhs) if (s == "^")
     {
         // + yields 0, 1, 2, 4, 5, 8
         auto v = value + rhs.value;
         return v >= 4 ? unknown : make(!!v);
     }
}

unittest
{
     Tristate a;
     assert(a == Tristate.no);
     static assert(!is(typeof({ if (a) {} })));
     assert(!is(typeof({ auto b = Tristate(3); })));
     a = true;
     assert(a == Tristate.yes);
     a = false;
     assert(a == Tristate.no);
     a = Tristate.unknown;
     Tristate b;
     b = a;
     assert(b == a);
     auto c = a | b;
     assert(c == Tristate.unknown);
     assert((a & b) == Tristate.unknown);
     a = true;
     assert(~a == Tristate.no);
     a = true;
     b = false;
     assert((a ^ b) == Tristate.yes);
}
Oct 26 2013
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 10/26/2013 8:42 AM, Andrei Alexandrescu wrote:

 While messing with std.allocator I explored the type below. I ended up not
using
 it, but was surprised that implementing it was quite nontrivial. Should we add
 it to stdlib?

 Theory: http://en.wikipedia.org/wiki/Three-state_logic


When I worked on the ABEL programming language, which was for designing 
programmable logic devices, we found it useful to have an additional state, 
"don't care".
Oct 26 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/26/13 12:17 PM, Walter Bright wrote:

 On 10/26/2013 8:42 AM, Andrei Alexandrescu wrote:

 While messing with std.allocator I explored the type below. I ended up
 not using
 it, but was surprised that implementing it was quite nontrivial.
 Should we add
 it to stdlib?

 Theory: http://en.wikipedia.org/wiki/Three-state_logic


 When I worked on the ABEL programming language, which was for designing
 programmable logic devices, we found it useful to have an additional
 state, "don't care".


Yah, that would be four-valued logic: 
http://en.wikipedia.org/wiki/Four-valued_logic.

One challenge in Tristate (or the as-of-yet-unwritten Fourstate) is to 
define the primitives |, &, ^, and ~ with minimum of operations. For 
example Tristate still has conditionals in two of them, which I think 
could be cleverly avoided.


Andrei
Oct 26 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/26/2013 11:06 PM, Andrei Alexandrescu wrote:

 On 10/26/13 12:17 PM, Walter Bright wrote:

 On 10/26/2013 8:42 AM, Andrei Alexandrescu wrote:

 While messing with std.allocator I explored the type below. I ended up
 not using
 it, but was surprised that implementing it was quite nontrivial.
 Should we add
 it to stdlib?

 Theory: http://en.wikipedia.org/wiki/Three-state_logic


 When I worked on the ABEL programming language, which was for designing
 programmable logic devices, we found it useful to have an additional
 state, "don't care".


 Yah, that would be four-valued logic:
 http://en.wikipedia.org/wiki/Four-valued_logic.

 One challenge in Tristate (or the as-of-yet-unwritten Fourstate) is to
 define the primitives |, &, ^, and ~ with minimum of operations. For
 example Tristate still has conditionals in two of them, which I think
 could be cleverly avoided.


 Andrei


The following implementation does not use conditionals; probably not 
minimal.

struct Tristate{
     private ubyte value;
     private static Tristate make(ubyte b){
         Tristate r = void;
         r.value = b;
         return r;
     }

     enum no = make(0), yes = make(2), unknown = make(6);

     this(bool b) { value = b; }

     void opAssign(bool b) { value = b; }

     Tristate opUnary(string s)() if (s == "~"){
         return make((193>>value&3)<<1);
     }

     Tristate opBinary(string s)(Tristate rhs) if (s == "|"){
         return make((12756>>(value+rhs.value)&3)<<1);
     }

     Tristate opBinary(string s)(Tristate rhs) if (s == "&"){
         return make((13072>>(value+rhs.value)&3)<<1);
     }

     Tristate opBinary(string s)(Tristate rhs) if (s == "^"){
         return make((13252>>(value+rhs.value)&3)<<1);
     }
}

unittest{
     with(Tristate){
         assert(~no==yes&&~yes==no&&~unknown==unknown);

         assert((no|no)==no&&(no|yes)==yes&&(yes|no)==yes&&(yes|yes)==yes&&
                (no|unknown)==unknown&&(yes|unknown)==yes &&
 
(unknown|no)==unknown&&(unknown|yes)==yes&&(unknown|unknown)==unknown);

         assert((no&no)==no&&(no&yes)==no&&(yes&no)==no&&(yes&yes)==yes&&
                (no&unknown)==no&&(yes&unknown)==unknown&&
 
(unknown&no)==no&&(unknown&yes)==unknown&&(unknown&unknown)==unknown);

         assert((no^no)==no&&(no^yes)==yes&&(yes^no)==yes&&(yes^yes)==no&&
                (no^unknown)==unknown&&(yes^unknown)==unknown&&
 
(unknown^no)==unknown&&(unknown^yes)==unknown&&(unknown^unknown)==unknown);
     }
}
Oct 26 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/26/13 5:13 PM, Timon Gehr wrote:

 The following implementation does not use conditionals; probably not
 minimal.


Thanks! Fixed two minor bugs:


      this(bool b) { value = b; }

      void opAssign(bool b) { value = b; }


These should shift b so it becomes 2 if true.

Pushed your code with the fixes and a full truth table unittest:

https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L236

Nice work. I'd say this is nontrivial enough to be put in the standard 
library.


Andrei
Oct 26 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/27/2013 02:11 AM, Andrei Alexandrescu wrote:

 On 10/26/13 5:13 PM, Timon Gehr wrote:

 The following implementation does not use conditionals; probably not
 minimal.


 Thanks! Fixed two minor bugs:


      this(bool b) { value = b; }

      void opAssign(bool b) { value = b; }


 These should shift b so it becomes 2 if true.
 ...


Good point.


 Pushed your code with the fixes and a full truth table unittest:

 https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L236

 Nice work. I'd say this is nontrivial enough to be put in the standard
 library.


 Andrei


Thanks!
Oct 27 2013
parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
On 10/27/13, 11:07, Timon Gehr wrote:

 On 10/27/2013 02:11 AM, Andrei Alexandrescu wrote:

 On 10/26/13 5:13 PM, Timon Gehr wrote:

 The following implementation does not use conditionals; probably
 not minimal.


 Thanks! Fixed two minor bugs:


 this(bool b) { value = b; }

 void opAssign(bool b) { value = b; }


 These should shift b so it becomes 2 if true. ...


 Good point.


 Pushed your code with the fixes and a full truth table unittest:

 https://github.com/andralex/phobos/blob/allocator/std/allocator.d#L236




Nice work. I'd say this is nontrivial enough to be put in the standard

 library.


 Andrei


 Thanks!


Couldn't this be optimized further, by doubling the constants?

(A>>(a+b)&3)<<1 ==> A2>>(a+b)&6 ?
Oct 30 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 10/30/2013 04:43 PM, Lionello Lunesu wrote:

 On 10/27/13, 11:07, Timon Gehr wrote:

 On 10/27/2013 02:11 AM, Andrei Alexandrescu wrote:

 On 10/26/13 5:13 PM, Timon Gehr wrote:

 The following implementation does not use conditionals; probably
 not minimal.


 ...




 Couldn't this be optimized further, by doubling the constants?

 (A>>(a+b)&3)<<1 ==> A2>>(a+b)&6 ?


It seems so. I am astonished that the compilers don't seem to figure 
this out on their own. It seems basic enough.
Oct 30 2013
prev sibling parent Johan Engelen <j j.nl> writes:
On Saturday, 26 October 2013 at 21:05:36 UTC, Andrei Alexandrescu 
wrote:

 One challenge in Tristate (or the as-of-yet-unwritten 
 Fourstate) is to define the primitives |, &, ^, and ~ with 
 minimum of operations. For example Tristate still has 
 conditionals in two of them, which I think could be cleverly 
 avoided.


Have you tried to find ideas from LDC's output ?
I've seen impressive LLVM optimization results (and 
vectorizations) for this sort of stuff.

-Johan
Mar 27 2016
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 10/26/2013 05:42 PM, Andrei Alexandrescu wrote:

 While messing with std.allocator I explored the type below. I ended up
 not using it, but was surprised that implementing it was quite
 nontrivial. Should we add it to stdlib?

 Theory: http://en.wikipedia.org/wiki/Three-state_logic


"The term tri-state[1] should not be confused with ternary logic 
(3-value logic)."


 ...

      Tristate opBinary(string s)(Tristate rhs) if (s == "&")
      {
          // & yields 0, 1, 4
          return make(value & rhs.value);
      }


This does not seem right. yes&unknown should be unknown.
Oct 26 2013
parent Denis Shelomovskij <verylonglogin.reg gmail.com> writes:
27.10.2013 4:08, Timon Gehr пишет:

 On 10/26/2013 05:42 PM, Andrei Alexandrescu wrote:

 While messing with std.allocator I explored the type below. I ended up
 not using it, but was surprised that implementing it was quite
 nontrivial. Should we add it to stdlib?

 Theory: http://en.wikipedia.org/wiki/Three-state_logic


 "The term tri-state[1] should not be confused with ternary logic
 (3-value logic)."


So this thread is about a three-valued logic with same truth tables as 
in Kleene's and Priest's logics.

See:
* http://en.wikipedia.org/wiki/Many-valued_logic
* http://en.wikipedia.org/wiki/Three-valued_logic


-- 
Денис В. Шеломовский
Denis V. Shelomovskij
Oct 28 2013
prev sibling next sibling parent reply Lionello Lunesu <lionello lunesu.remove.com> writes:
On 10/26/13, 17:42, Andrei Alexandrescu wrote:

 unittest
 {
      Tristate a;
      assert(a == Tristate.no);


Why not have '0' map to unknown? Seems to more useful, like float.nan 
and the like.

L.
Oct 31 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/31/13 2:35 AM, Lionello Lunesu wrote:

 On 10/26/13, 17:42, Andrei Alexandrescu wrote:

 unittest
 {
      Tristate a;
      assert(a == Tristate.no);


 Why not have '0' map to unknown? Seems to more useful, like float.nan
 and the like.


So logical operations are closer to the built-in Boolean ones, and 
conversion from bool is simple. If there's no such advantage, 0 should 
be the most frequent value (comparisons against 0 are smallest and fastest).

One possibility is to make the initial value unknown by default (which 
is a great idea).

I'll post shortly an update to Ternary (better name) along with 
additions to std.allocator.


Andrei
Oct 31 2013
prev sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 26 October 2013 at 15:41:32 UTC, Andrei Alexandrescu 
wrote:

 While messing with std.allocator I explored the type below. I 
 ended up not using it, but was surprised that implementing it 
 was quite nontrivial. Should we add it to stdlib?


I can think of many variants of for this. What about

     { yes, // 1 chance
       no, // 0 chance
       likely, // > 1/2 chance
       unlikely, // < 1/2 chance
       unknown // any chance
     }

?

Partial implementation at

https://github.com/nordlow/justd/blob/master/fuzzy.d#L15

:)
Mar 26 2016
next sibling parent reply Alex Parrill <initrd.gz gmail.com> writes:
On Saturday, 26 March 2016 at 22:11:53 UTC, Nordlöw wrote:

 On Saturday, 26 October 2013 at 15:41:32 UTC, Andrei 
 Alexandrescu wrote:

 While messing with std.allocator I explored the type below. I 
 ended up not using it, but was surprised that implementing it 
 was quite nontrivial. Should we add it to stdlib?


 I can think of many variants of for this. What about

     { yes, // 1 chance
       no, // 0 chance
       likely, // > 1/2 chance
       unlikely, // < 1/2 chance
       unknown // any chance
     }

 ?

 Partial implementation at

 https://github.com/nordlow/justd/blob/master/fuzzy.d#L15

 :)


If we're going down that route, might as well use state tables. 
With CTFE + templates, you could possibly do something like this:


	immutable State[] StateOrTable = ParseStateTable!q{
	        | yes | no       | likely | unlikely | unknown
	------------------------------------------------------
	yes     | yes | yes      | yes    | yes      | yes
	no      | yes | no       | likely | unlikely | unknown
	likely  | yes | likely   | likely | likely   | likely
	unlikely| yes | unlikely | likely | unlikely | unknown
	unknown | yes | unknown  | likely | unknwon  | unknown
	};

	State opBinary(string op)(State other)
	if(op == "||") {
		return StateOrTable[this.value*NumStates+other.value];
	}

Though I see issues with having a generic n-state value template 
and also rewriting `a != b` to `!(a == b)`; I suspect that there 
may be some class of values where the two are not equivalent.
Mar 26 2016
next sibling parent reply crimaniak <crimaniak gmail.com> writes:
On Saturday, 26 March 2016 at 22:39:58 UTC, Alex Parrill wrote:

...

 If we're going down that route, might as well use state tables.


...

For Boolean, Ternary, and N-state logic:

a && b == min(a, b)
a || b == max(a, b)
~a == N-1-a

why to optimize it more?
Mar 26 2016
parent reply Alex Parrill <initrd.gz gmail.com> writes:
On Sunday, 27 March 2016 at 02:19:56 UTC, crimaniak wrote:

 On Saturday, 26 March 2016 at 22:39:58 UTC, Alex Parrill wrote:

 ...

 If we're going down that route, might as well use state tables.


 ...

 For Boolean, Ternary, and N-state logic:

 a && b == min(a, b)
 a || b == max(a, b)
 ~a == N-1-a

 why to optimize it more?


That's incorrect for the `unknown` value.

Lets say you represented true as 1f, false as 0f, and unknown as 
NaN...

std.algorithm.max(0, 0f/0f) = 0, but should be NaN
std.math.fmax(1, 0f/0f) = NaN, but should be 1

N-state logic isn't just about probabilities either. According to 
Wikipedia, Bochvar's three-valued logic has an "internal" state, 
where any operation with `internal` results in `internal` 
(similar to NaN). More broadly, the values and operations between 
them could be whatever the mathematician or developer wants, so a 
truth table is one of the ways to generally specify an operator.
Mar 26 2016
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/26/2016 10:36 PM, Alex Parrill wrote:

 N-state logic isn't just about probabilities either. According to
 Wikipedia, Bochvar's three-valued logic has an "internal" state, where
 any operation with `internal` results in `internal` (similar to NaN).
 More broadly, the values and operations between them could be whatever
 the mathematician or developer wants, so a truth table is one of the
 ways to generally specify an operator.


BTW there's a tri-state logic type in std.allocator. Care to take a look 
at how it might be improved? -- Andrei
Mar 26 2016
prev sibling parent crimaniak <crimaniak gmail.com> writes:
On Sunday, 27 March 2016 at 02:36:47 UTC, Alex Parrill wrote:
...

 a && b == min(a, b)
 a || b == max(a, b)
 ~a == N-1-a

 why to optimize it more?


 That's incorrect for the `unknown` value.

 Lets say you represented true as 1f, false as 0f, and unknown 
 as NaN...

 std.algorithm.max(0, 0f/0f) = 0, but should be NaN
 std.math.fmax(1, 0f/0f) = NaN, but should be 1

 N-state logic isn't just about probabilities either. According


  Yes, you right, I mean logic as probability approximation 
(Godel). But in this case you can't assign arbitrary codes to 
values. False == 0, unknown == 1 and true == 2 is here.


 to Wikipedia, Bochvar's three-valued logic has an "internal" 
 state, where any operation with `internal` results in 
 `internal` (similar to NaN). More broadly, the values and 
 operations between them could be whatever the mathematician or 
 developer wants, so a truth table is one of the ways to 
 generally specify an operator.


  Fully arbitrary logic needs tables, yes.
Mar 27 2016
prev sibling parent sarn <sarn theartofmachinery.com> writes:
On Saturday, 26 March 2016 at 22:39:58 UTC, Alex Parrill wrote:

 On Saturday, 26 March 2016 at 22:11:53 UTC, Nordlöw wrote:

 I can think of many variants of for this. What about

     { yes, // 1 chance
       no, // 0 chance
       likely, // > 1/2 chance
       unlikely, // < 1/2 chance
       unknown // any chance
     }

 ?


 If we're going down that route, might as well use state tables. 
 With CTFE + templates, you could possibly do something like 
 this:


 	immutable State[] StateOrTable = ParseStateTable!q{
 	        | yes | no       | likely | unlikely | unknown
 	------------------------------------------------------
 	yes     | yes | yes      | yes    | yes      | yes
 	no      | yes | no       | likely | unlikely | unknown
 	likely  | yes | likely   | likely | likely   | likely
 	unlikely| yes | unlikely | likely | unlikely | unknown
 	unknown | yes | unknown  | likely | unknwon  | unknown
 	};


I just hope we don't end up with an abomination like Microsoft's 
MsoTriState:
https://msdn.microsoft.com/en-us/library/office/ff860737.aspx

(A "tristate boolean" with five values, three of which are "not 
supported".)
Mar 27 2016
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 26 March 2016 at 22:11:53 UTC, Nordlöw wrote:

 Partial implementation at

 https://github.com/nordlow/justd/blob/master/fuzzy.d#L15


moved to

https://github.com/nordlow/justd/blob/master/nstate.d#L15
Mar 31 2016