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);
}

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

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

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.

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);
    }
}

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

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!

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

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 ?

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.