TLDR; do you know of any general purpose languages that can also compile a function to some representation of AND/OR gates (or NAND gates, or whatever)?

Edit: actually any algebra/formal-logical system is also fine (not just boolean algebra).

Yes, a A LOT of additional info is needed, like defining how input/output is defined, and I am interested in how those would be specified. I’m not interested in printing an actual circuit, just the boolean-logic level. And I’m mostly asking because I feel like most compilers can’t generate a clean/mathematical representation from their AST. There’s AST to IR, there’s hard-coded optimizations on the IR, and then there’s hard-coded mappings from the IR to assembly, but at no point (AFAIK) is the code turned into a algebraic/logical system where something like De Morgan’s Law can be applied. And that seems really sad to me.

So you could say my real question is: what compilers have a strong logical/algebraic internal representation of their own AST?

Maybe something like Haskell or Prolog do this. The Wolfram Language almost certainly does but it’s closed source.

  • @Tubbles
    link
    11 year ago

    Another way could be to run that through a compiler with optimization activated, and then decompile the resulting binary back to code. But if you want to optimize hot code then usually mathematical reduction is seldomly wherein the problem lies

    • @[email protected]OP
      link
      fedilink
      2
      edit-2
      1 year ago

      I don’t know about math reduction not being the bottle neck. If I was custom optimizing hot code then yeah, cache hit optimization is huge, but I’m thinking of generic optimizations on hot code that only the compiler looks at. Beyond out-of-order-execution and SIMD kind of algebraic shuffling. For example, I want to be confident that the compiler would transform something like

      for each in range(x) x += x

      into x*=x+1

      And based on stuff like this (which is shockingly recent IMO) I don’t think modern compilers can even find that shortcut right now. Which is kinda sad when you think about it.

      If x=65536, any non-algebraic optimizaiton would be vastly inferior. And sure an experienced dev wouldn’t make this kind of mistake, but I bet half the code running on the average computer wasnt written by experienced devs. And its not like its an either-or situation, we can do both optimization steps.