Re: Tristate - wanna?
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
Re: Tristate - wanna?
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".)
Re: Tristate - wanna?
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.
Re: Tristate - wanna?
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
Re: Tristate - wanna?
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
Re: Tristate - wanna?
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.
Re: Tristate - wanna?
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?
Re: Tristate - wanna?
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.
Re: Tristate - wanna?
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
:)
Re: Tristate - wanna?
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.
Re: Tristate - wanna?
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
Re: Tristate - wanna?
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 ?
Re: Tristate - wanna?
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.
Re: Tristate - wanna?
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
Re: Tristate - wanna?
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!
Tristate - wanna?
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);
}
Re: Tristate - wanna?
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.
Re: Tristate - wanna?
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
Re: Tristate - wanna?
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. yesunknown should be unknown.
Re: Tristate - wanna?
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((193value3)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((nono)==no(noyes)==no(yesno)==no(yesyes)==yes
(nounknown)==no(yesunknown)==unknown
(unknownno)==no(unknownyes)==unknown(unknownunknown)==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);
}
}
Re: Tristate - wanna?
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
