Re: [Boost-announce] Formal Review Tribool
Hi, I am happy to contribute my review for the tribool library. I am a software engineer developing EDA (Electronic Design Automation) software, so I think I can contribute my 2 cents to the review of tribool, as I think EDA tools will benefit from this library. I did not compile the library. I have made a quick reading of this library, but an in-depth study of this problem domain before. First of all, my first comment is about the library's name, as well as the class name. In logic circuit simulation, there are 4 values : 0, 1, x ( which is tribool referred to as undetermine ), and z ( represents high impedance - or disconnection, and sometime referred to as "tri state" ). So, I think users will find it quite confusing when they see the 'tri' in the library's name. Since the library implements a logic value which has some value that is unknown, I would suggest 'unknown bool' or 'x bool'. Now to the interface. I think that a macro which enables renaming of the x value should not be supplied. This will make people's code less standard. Same as we all know what 'true' and 'false' mean, we should adopt a unique name for 'unknown yet quite determined logic value'. I think the default 'undetermine' name is not a good name. My suggestions : logic_x, x_value, x_logic, unknwon_bool . I also think the default tribool constructor should create a tribool object which is 'undetermine'. (Not false, as in the documentation) Besides the above, I think the interface of the class is good and succinct. Some point for thought : Users might want arrays of tribools, with all the support of bitwise operations. Is this should be a part of tribool as well ? I do not know. Now I will refer to the implementation. In real-life problems, programs might make a heavy usage of the tribool class for simulations of logic circuits. A logic circuit (at least the combinatoric part) is a DAG where nodes are logic gates, and directed archs are wires. This graph might be the result of a synthesis process, where a high level language for hardware description (e.g Verilog) is compiled into this DAG. Note : This is a very general and simple description of the process. Life are much more difficult. So, outputs will be calculated by performing lexicographic order of the DAG, and calculating from inputs to outputs. I am telling this, to convince that performance is *very* important here. With a quick look at the implementation code, I think that calculating the value using branches (if else) will not result with good performance. Calculations with true/false values only is fast - CPU vendors dedicate special hardware for this, so calculation can be made in one machine cycle. Even bitwise calculation (up to some word width) is done in one machine cycle. Compilers are making use of this, and (hopefully) compiles boolean and bitwise operators to the appropriate instruction. Unfortunately, I did not see any CPU which supports built in true/false/X arithmetic. And even if there are such CPUs available, we will not be able to use it, since boost libraries should be portable. So, it is very tempting to think - how can we implement efficient true/false/X arithmetic using the existing boolean arithmetic ? One tempting idea is to represent true/false/X with some integers, and use bitwise arithmetic to get the right results. It seems there are no such integer values. I think I even managed to proof this. Since there is already a library implementing 4 values logic (0,1,x,z) - which is SystemC - I took a quick look on how they do it with their 4-states logic data type called sc_logic. They use an approach which I think should be also used in tribool. It seems that they maintain lookup tables for each operation: AND, OR, NOT, XOR (!=) and XNOR (==). As the internal representation of tribool is enumerated type, we can use the integer value of this enumerated type to access the lookup tables (primitive 2D fixed-size and fixed-values arrays) and get the result of the calculation. This will be much faster since most CPUs has a special addressing mode for accessing arrays. So, I suggest to change implementation to use class-static fixed array to perform calculations. I know that the spirit of Boost is portability and not performance, but since what is suggested here is actually very similar to a primitive data type which might be heavily used in applications, I think it is important to consider performance as well. I hope this review would be found useful. Haim -- _____________________________________________________ Haim Cohen Software Engineer haim.cohen@analog.com / haimcohen2002@hotmail.com Analog Devices Israel (972) - 9 - 9715 406
From: Haim Cohen <haim.cohen@analog.com>
First of all, my first comment is about the library's name, as well as the class name. In logic circuit simulation, there are 4 values : 0, 1, x ( which is tribool referred to as undetermine ), and z ( represents high impedance - or disconnection, and sometime referred to as "tri state" ). So, I think users will find it quite confusing when they see the 'tri' in the library's name. Since the library implements a logic value which has some value that is unknown, I would suggest 'unknown bool' or 'x bool'.
First, you say that the indeterminate value should be named "x" because "x" is the indeterminate state in electronics. When looking for a non-descriptive identifier, one often resorts to things like "x," so there's some programming precedent for "x" meaning "arbitrary value." However, "indeterminate" leaves no doubt as to the meaning of the value and doesn't depend upon one's experience with electronics. Another possibility would be "unknown" as that is equally descriptive and is definitely shorter (less typing!). Second, you say that the library name should not be "tribool" but instead should be "unknown_bool" or "x_bool" to avoid confusion with tristate logic. Do you seriously think electronics domain programmers will think that "boost::tribool" is related to tristate logic? I don't see that as likely. That doesn't mean there isn't value in your suggestion to change the library name. As I've already rejected the "x" notion, that leaves "unknown_bool" or, by extension, "indeterminate_bool." While these names suggest that there is an unknown or indeterminate Boolean value, they don't suggest to me a type that includes true, false, *and* unknown/indeterminate. "tribool," OTOH, clearly indicates that it is a type that includes exactly three logic states, though it doesn't name any of them. Furthermore, "tribool" paves the way for the possibility of adding quadbool or multibool to Boost. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;
Rob Stewart wrote:
meaning "arbitrary value." However, "indeterminate" leaves no doubt as to the meaning of the value and doesn't depend upon one's experience with electronics. Another possibility would be I agree. Although I see the highest potential of the library in EDA applications, the meaning of the value should not depend on any problem domain - like electronics. I guess I was little bit biased here by my problem domain.
As I've already rejected the "x" notion, that leaves "unknown_bool" or, by extension, "indeterminate_bool." While these names suggest that there is an unknown or indeterminate Boolean value, they don't suggest to me a type that includes true, false, *and* unknown/indeterminate. "tribool," OTOH, I disagree. IMHO, The name unknown_bool hints that in addition to the 2 traditional values of bool, there is also an unknown bool. I am not a native user of the English language, but this is what the name unknown_bool hints *me*.
Haim
----- Original Message ----- From: "Haim Cohen" <haim.cohen@analog.com>
First of all, my first comment is about the library's name, as well as the class name. In logic circuit simulation, there are 4 values : 0, 1, x ( which is tribool referred to as undetermine ), and z ( represents high impedance - or disconnection, and sometime referred to as "tri state" ). So, I think users will find it quite confusing when they see the 'tri' in the library's name. Since the library implements a logic value which has some value that is unknown, I would suggest 'unknown bool' or 'x bool'.
Now to the interface. I think that a macro which enables renaming of the x value should not be supplied. This will make people's code less standard.
Ironically, it was disagreements over the name of the 3rd state that resulted in the macro, although I think I agree with you. Users may just have to deal with our choice of name (for their own good <g>).
Same as we all know what 'true' and 'false' mean, we should adopt a unique name for 'unknown yet quite determined logic value'. I think the default 'undetermine' name is not a good name. My suggestions : logic_x, x_value, x_logic, unknwon_bool .
I agree with Rob Stewart's comments about using "x". As for "unknown", I'm pretty flexible: tribool originally had "unknown", but I seem to recall that earlier informal review favored "indeterminate".
Some point for thought : Users might want arrays of tribools, with all the support of bitwise operations. Is this should be a part of tribool as well ? I do not know.
I think this would be a useful feature, and I believe Pavel (?) had mentioned interest in writing something like this. It would probably be similar to dynamic_bitset. [snip]
So, I suggest to change implementation to use class-static fixed array to perform calculations.
Agreed.
I hope this review would be found useful.
Absolutely. Thank you. Doug
"Doug Gregor" <gregod@cs.rpi.edu> wrote:
Some point for thought : Users might want arrays of tribools, with all the support of bitwise operations. Is this should be a part of tribool as well ? I do not know.
I think this would be a useful feature, and I believe Pavel (?) had mentioned interest in writing something like this. It would probably be similar to dynamic_bitset.
It started but got stalled somewhere. I may try to complete it but it depends on many factors. /Pavel
participants (4)
-
Doug Gregor -
Haim Cohen -
Pavel Vozenilek -
Rob Stewart