Add `IfThenElse` to the AST

[effectfully]

Alex Nemish reports on X:

Validators are glorified IfThenElses. Blockchain space is very expensive.

IfThenElse is one of the most used builtins.

Minswap contract has 96 IfThenElses.

It's used as (force (apply(apply(apply(force (builtin ifThenElse)) cond) (delay t) (delay f))))

Instead of (ifThenElse t f).

It's 8*5 + 7=47 bits instead of 5 bits, 10 times more.

Practically, we use force/delay ONLY because of IfThenElse is a builtin and it doesn't have lazy semantics.

10-15% all ALL Cardano bytecode in the blockchain is just that.

Minswap contract has 1350 force/delay nodes of 8213. It's 16%.

Unnecessary. Redundant.

My response was

This would be extremely awkward. Builtins are fully customizable in Core UPLC and hardcoding IfThenElse into the AST would mean that Bool needs to be hardcoded too and now we have "native" and "external" builtins...

but we should perhaps at least try adding an IfThenElse node to the AST to see how it affects performance. Maybe the awkwardness is worth it.

[colll78]

16% is crazy. If that number is actually correct then I personally would prefer any amount of awkwardness over 15% of all byte-code being force/delay.

That’s an extremely large performance tradeoff just to avoid awkwardness.

[effectfully]

16% is crazy. If that number is actually correct then I personally would prefer any amount of awkwardness over 15% of all byte-code being force/delay.

That’s an extremely large performance tradeoff just to avoid awkwardness.

Weren't you the person who said "The cost of bytes is so low" recently? :stuck_out_tongue:

Seriously though:

• 16% isn't crazy, we've optimized runtime by ~100x from the original version incrementally and without changing the AST
• IfThenElse is pattern matching for Bool, we also have [] and Data. Do you want us to hardcode pattern matching into the AST for lists and Data as well? Probably some of those 16% come from handling of lists and Data. At that point it'd perhaps be easier to just hardcode all builtins, although in that case I'm not sure how to handle builtins used for costing or testing.

extremely large performance tradeoff

I don't know how 16% of delay/force nodes translates to performance, but if we take it literally as 16% slowdown, then it's not extremely large, it's not even large. There are ways to improve performance by about as much without introducing "awkwardness", i.e. without slowing development down (increasing maintenance costs, increasing the cost of adding new features, spending time formalizing and specifying the updated AST etc) and increasing the risk of messing up the semantics of the language as that's what "awkwardness" translates to.

I was explicitly told that I should not spend any significant amount of time improving performance after I'd invested some effort in that as this wasn't deemed a priority. The latter is the reason why things don't become faster, not our lack of imagination.

Also, IfThenElse is for converting built-in Bool to SOPs (or Scott-encoded Bool as it used to be the case), not for using it 96 times within your contract. It's for interfacing, not for the logic. So maybe this is simply an issue of not holding the thing right.

[colll78]

16% is crazy. If that number is actually correct then I personally would prefer any amount of awkwardness over 15% of all byte-code being force/delay. That’s an extremely large performance tradeoff just to avoid awkwardness.

Weren't you the person who said "The cost of bytes is so low" recently? 😛

The cost of storage bytes is relatively low, but the deserialization fee per reference script byte is extremely high. So much so that most major dApp protocol revenue was cut in half by its introduction.

Seriously though:

• 16% isn't crazy, we've optimized runtime by ~100x from the original version incrementally and without changing the AST

Were these optimizations to Plutus or to UPLC?

• IfThenElse is pattern matching for Bool, we also have [] and Data. Do you want us to hardcode pattern matching into the AST for lists and Data as well? Probably some of those 16% come from handling of lists and Data. At that point it'd perhaps be easier to just hardcode all builtins, although in that case I'm not sure how to handle builtins used for costing or testing.

Yes, I personally don't see why core language features (pattern matching Lists and Data) are implemented as builtins, to me builtins should be reserved for functions that would be prohibitively expensive to implement natively in UPLC (ie. hashing primitives, signature verification primitives, serialization primitives, zk primitives, bitwise primitives, advanced data-structures, list utilities inc. filter, sort, etc, and whatnot).

I don't know how 16% of delay/force nodes translates to performance, but if we take it literally as 16% slowdown, then it's not extremely large, it's not even large. There are ways to improve performance by about as much without introducing "awkwardness", i.e. without slowing development down (increasing maintenance costs, increasing the cost of adding new features, spending time formalizing and specifying the updated AST etc) and increasing the risk of messing up the semantics of the language as that's what "awkwardness" translates to.

The reason it contributes to performance (by performance I mean in the context of onchain code, the ex-units that dApp developers care about). Is that the most impactful optimization techniques in onchain code involve trade-offs between script-size and ex-units. This results in a tight balancing act when making a production smart contract, the goal is to minimize ex-units while keeping the script size below (often as close as possible to) the ~16kb limit. Unrolling recursion, large lookup tables, and aggressive inlining are all powerful optimizations that reduce ex-units at the cost of increasing script size. When 16% of the script size is occupied by force/delay, that is 16% that could be used for either more features in the contract or more optimization via the above techniques.

I was explicitly told that I should not spend any significant amount of time improving performance after I'd invested some effort in that as this wasn't deemed a priority. The latter is the reason why things don't become faster, not our lack of imagination.

I don’t know why it was decided that you shouldn’t spend any significant amount of time on performance when that is the number one concern of dApp developers. Aside from smart contract auditing, the vast majority of the contracting work we do at Anastasia Labs is for is smart contract optimization to enhance the throughput of dApp protocols. It is the same for every dApp, a massive amount of time is spent on script optimization (often at the expense of code-readability and occasionally even security), all because without such optimizations, throughput is not sufficient.

[christianschmitz]

If we would go so far as to actually create an IfThenElse term, I suggest making such a term accept a variable number of arguments (similar to case), and implicitly delaying those arguments.

So we can generate UPLC code like:

IfThenElseTerm(<cond0>, <case0>, <cond1>, <case1>, <cond2>, <case2>, <default>)

Instead of:

force ifThenElse(
  <cond0>, 
  delay <case0>, 
  delay force ifThenElse(
    <cond1>,
    delay <case1>,
    delay force ifThenElse(
      <cond2>,
      delay <case2>
      delay <default>
    )
  )
)

Such a term would also offer a cleaner and more efficient solution for complicated pattern-matching branches

[effectfully]

With #7029 merged you can now write for a built-in boolean b

case b
  falseBranch
  trueBranch

which is as close to native IfThenElse as it gets. I'm therefore closing this issue.