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