5 ms·

There's so pretty much seemingly unique proprietary software. A while ago I found this awesome logic minimizer called "logic Friday". [1] I don't think there's

There's so pretty much seemingly unique proprietary software. A while ago I found this awesome logic minimizer called "logic Friday". [1] I don't think there's a free or open source version of a tool like this. I have an idea that the "espresso" algorithm could be used to minimize not only electronic circuits but general boolean expressions for any programming language... I think it would do for a useful refactoring tool. 1: https://web.archive.org/web/20131022051516/http://www.sontrak.com/screenshots.html https://web.archive.org/web/20131022051516/http://www.sontra...

thaumasiotes 7y ago
> I have an idea that the "espresso" algorithm could be used to minimize not only electronic circuits but general boolean expressions for any programming language... I think it would do for a useful refactoring tool. I think the goal for most boolean expressions in code is for the reader to be able to conceptually grasp what's being checked for, not for the expression to be as short as possible. Distributive properties can make an expression shorter while simultaneously making the concepts behind the expression much more obscure.
- monocasa 7y ago
  It's useful in the compiler. For instance one optimization I haven't seen but would like to is going from if( value1 < 0 || value2 < 0 || value3 < 0 ) { to temp = value1 | value2 | value3; if( temp < 0 ) { Taking a sort of hardware, Boolean logic view makes this possible, as VHDL generally does this when synthesed.
  - thaumasiotes 7y ago
    That optimization fudges the difference between boolean or (comparing truth values) and bitwise or. It happens to work under the safe assumption that value1, value2, and value3 use sign bits (as all two's-complement integers do), but logically it's a disaster.
    - Thorrez 7y ago
      monocasa isn't saying this should be in source code, but rather the compiler should create machine code that does this. Compilers know the types, so they will know whether they're signed (if they're not signed, then < 0 can be optimized out as impossible). Compilers have no goal of creating assembly that would look good in source code.
  - adrian17 7y ago
    It seems like Clang is capable of doing this optimization: > https://godbolt.org/z/oCQNbq https://godbolt.org/z/oCQNbq
    - monocasa 7y ago
      Neat! It didn't a few years ago. This is most of the inner loop of a barycentric coordinate rasterizer, so I was pretty concerned about micro-optimizations when I was checking.
  - ospr3y 7y ago
    As a compiler writer I can tell you that this is a complex optimisation with very limited use. N.B. the || (logical or) operator is an "early out" operator whereas the | (binary or) operator is NOT The compiler would need to look for special cases of value1, value2 and value3... such as: are any of them volatile, perhaps one refers to a memory mapped I/O device, perhaps one if actually a function call, or array dereference, or pointer dereference, what about value1 being a "char" which needs to be promoted before it can be or'd, what about any of the "values" being a constant < 0 which would short circuit the "if" statement and remove the need for any tests. As I said, this is not as simple as it first appears.
  - FullyFunctional 7y ago
    Note, if the three comparisons are sufficiently predicable, then your transformation would be _less_ efficient than the simple branches. A predicable branch is almost free in a modern processor.
    - ncmncm 7y ago
      Three comparison/branch pairs are not free. Clang will optimize bool swap_if(bool c, int& a, int& b) { int ta = a, tb = b; a = (-c & tb)|((c-1) & ta); b = (-c & ta)|((c-1) & tb); return c; } into cmov instructions. Used in a quicksort partition loop as l += swap_if( *r <= pv, *l, *r); It makes quicksort fully 2x as fast as the usual branch.
      - FullyFunctional 7y ago
        Quicksort comparisons are obviously not predictable
- emmanueloga_ 7y ago
  Good point, although the idea would be you get to choose one for or the other. I think sometimes the simplified expression makes it easier to see the complement (else branch). btw, I started to think about "boolean refactoring" when I saw J. Edwards' schematic tables video [1]. 1: https://vimeo.com/140738254 https://vimeo.com/140738254
Gracana 7y ago
I like Helmut Neemann's Digital: https://github.com/hneemann/Digital https://github.com/hneemann/Digital It simulates logic, supports automated testing, simulates and analyses combinatorial and sequential logic, comes with a large library of components (generic stuff, specific 7400 logic, displays and memories, etc), it can output VHDL or Verilog, and it can export JEDEC files for GALs.
- ngcc_hk 7y ago
  This seems more interesting as it is open sourced, support current hardware etc.
- emmanueloga_ 7y ago
  Looks great, I'll give it a try! Looks like it implements a different minimization algorithm [1]. 1: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algori...
  - TimTheTinker 7y ago
    Quine McCluskey is equivalent to using Karnaugh maps. Both are basic digital logic minimization workflows, and are taught in any course covering digital logic or CS-focused discrete math.
lloydatkinson 7y ago
+1 for Logic Friday. I had fun with that, it is/was quite nice to use. I wonder what happened to it. The "sontrak.com" domain is bust now it seems. The about page has this in the copyright though: > *Espresso and misII are copyright © 1988-1993, Regents of the University of California.
coldpie 7y ago
> There's so pretty much seemingly unique proprietary software. Indeed. Something to consider when choosing a license and distribution model for your own projects, including web-based software. Your life is finite, but the life of your software may not be.
dan1234 7y ago
You should take a look at Z Notation, which is a formal specification language based around mathematics & set theory. I hated working in it and have done my best to forget everything about it.
oakwhiz 7y ago
I've used Logic Friday once to make a wired remote controller device that operated on 74-logic. I haven't really seen any tools that offer more user-friendly ergonomics for that type of problem, except maybe a curve-fitting tool called Eureqa which used to be open-source and went closed-source. Or perhaps Wolfram Mathematica could be used to spit out a few solutions, again closed-source.

thaumasiotes 7y ago

> I have an idea that the "espresso" algorithm could be used to minimize not only electronic circuits but general boolean expressions for any programming language... I think it would do for a useful refactoring tool. I think the goal for most boolean expressions in code is for the reader to be able to conceptually grasp what's being checked for, not for the expression to be as short as possible. Distributive properties can make an expression shorter while simultaneously making the concepts behind the expression much more obscure.

monocasa 7y ago
It's useful in the compiler. For instance one optimization I haven't seen but would like to is going from if( value1 < 0 || value2 < 0 || value3 < 0 ) { to temp = value1 | value2 | value3; if( temp < 0 ) { Taking a sort of hardware, Boolean logic view makes this possible, as VHDL generally does this when synthesed.
- thaumasiotes 7y ago
  That optimization fudges the difference between boolean or (comparing truth values) and bitwise or. It happens to work under the safe assumption that value1, value2, and value3 use sign bits (as all two's-complement integers do), but logically it's a disaster.
  - Thorrez 7y ago
    monocasa isn't saying this should be in source code, but rather the compiler should create machine code that does this. Compilers know the types, so they will know whether they're signed (if they're not signed, then < 0 can be optimized out as impossible). Compilers have no goal of creating assembly that would look good in source code.
- adrian17 7y ago
  It seems like Clang is capable of doing this optimization: > https://godbolt.org/z/oCQNbq https://godbolt.org/z/oCQNbq
  - monocasa 7y ago
    Neat! It didn't a few years ago. This is most of the inner loop of a barycentric coordinate rasterizer, so I was pretty concerned about micro-optimizations when I was checking.
- ospr3y 7y ago
  As a compiler writer I can tell you that this is a complex optimisation with very limited use. N.B. the || (logical or) operator is an "early out" operator whereas the | (binary or) operator is NOT The compiler would need to look for special cases of value1, value2 and value3... such as: are any of them volatile, perhaps one refers to a memory mapped I/O device, perhaps one if actually a function call, or array dereference, or pointer dereference, what about value1 being a "char" which needs to be promoted before it can be or'd, what about any of the "values" being a constant < 0 which would short circuit the "if" statement and remove the need for any tests. As I said, this is not as simple as it first appears.
- FullyFunctional 7y ago
  Note, if the three comparisons are sufficiently predicable, then your transformation would be _less_ efficient than the simple branches. A predicable branch is almost free in a modern processor.
  - ncmncm 7y ago
    Three comparison/branch pairs are not free. Clang will optimize bool swap_if(bool c, int& a, int& b) { int ta = a, tb = b; a = (-c & tb)|((c-1) & ta); b = (-c & ta)|((c-1) & tb); return c; } into cmov instructions. Used in a quicksort partition loop as l += swap_if( *r <= pv, *l, *r); It makes quicksort fully 2x as fast as the usual branch.
    - FullyFunctional 7y ago
      Quicksort comparisons are obviously not predictable
emmanueloga_ 7y ago
Good point, although the idea would be you get to choose one for or the other. I think sometimes the simplified expression makes it easier to see the complement (else branch). btw, I started to think about "boolean refactoring" when I saw J. Edwards' schematic tables video [1]. 1: https://vimeo.com/140738254 https://vimeo.com/140738254

Gracana 7y ago

I like Helmut Neemann's Digital: https://github.com/hneemann/Digital https://github.com/hneemann/Digital It simulates logic, supports automated testing, simulates and analyses combinatorial and sequential logic, comes with a large library of components (generic stuff, specific 7400 logic, displays and memories, etc), it can output VHDL or Verilog, and it can export JEDEC files for GALs.

ngcc_hk 7y ago
This seems more interesting as it is open sourced, support current hardware etc.
emmanueloga_ 7y ago
Looks great, I'll give it a try! Looks like it implements a different minimization algorithm [1]. 1: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algori...
- TimTheTinker 7y ago
  Quine McCluskey is equivalent to using Karnaugh maps. Both are basic digital logic minimization workflows, and are taught in any course covering digital logic or CS-focused discrete math.

lloydatkinson 7y ago

+1 for Logic Friday. I had fun with that, it is/was quite nice to use. I wonder what happened to it. The "sontrak.com" domain is bust now it seems. The about page has this in the copyright though: > *Espresso and misII are copyright © 1988-1993, Regents of the University of California.

coldpie 7y ago

> There's so pretty much seemingly unique proprietary software. Indeed. Something to consider when choosing a license and distribution model for your own projects, including web-based software. Your life is finite, but the life of your software may not be.

dan1234 7y ago

You should take a look at Z Notation, which is a formal specification language based around mathematics & set theory. I hated working in it and have done my best to forget everything about it.

oakwhiz 7y ago

I've used Logic Friday once to make a wired remote controller device that operated on 74-logic. I haven't really seen any tools that offer more user-friendly ergonomics for that type of problem, except maybe a curve-fitting tool called Eureqa which used to be open-source and went closed-source. Or perhaps Wolfram Mathematica could be used to spit out a few solutions, again closed-source.