IntersectMBO / IntersectMBO/plutus

Allow for retrieving the index of a SOP constructor

Open
#6,653 3 comments 0 reactions 0 assignees View on GitHub
AST Evaluation Low priority status: triaged
Dominant language
Haskell
Stars
1.6k
Forks
508
Avg merge
3d 10h
Merged PRs (30d)
22

Description

Helios folks [propose](https://x.com/helios_lang/status/1855441591701307623) to introduce a builtin allowing one to get `i` from `Term.Constr i args`.

Their reasoning is that sometimes one only needs to check whether the constructor is a specific one, instead of providing a branch for every single constructor. E.g. if you have a big sum type like

```haskell
data D = C1 | C2 | C3 | C4 | <...> | Cn
```

then you can define equality checking for such a type in linear amount of matches in, say, Plinth:

```haskell
C1 == C1 = True
C2 == C2 = True
<...>
Cn == Cn = True
_ == _ = False
```

but on the UPLC level this will give you a quadratic number of branches, because for each `Ci` to the left of `==` you'll need to explicitly handle all of `C1` ... `Cn`, because a `case` has to explicitly handle all possible constructors and there's can't be a catch-all clause.

There's a number of issues with the proposal, though. Firstly, what if those `C*` constructors carry some arguments? How will we extract them out of there if we only know the index of the constructor?

Secondly, such a builtin would break parametricity, it's the same issues as we relentlessly discussed in the `equalsCanonical` [PR](https://github.com/IntersectMBO/plutus/pull/5440) and in #5776 + #6225. I.e. we've already given up on important things because of the parametricity issue, so it's unlikely we're going to revert on that just for the purpose of having a builtin returning the index of a SOP.

Now given that SOPs are basically on [par](https://github.com/IntersectMBO/plutus/issues/5830) with builtins and we seem to have a [plan](https://github.com/IntersectMBO/plutus/issues/6602) on making `Data` as fast as SOPs, do we even need to worry about SOPs at this point? Maybe it'll turn out that just having fast `Data` is enough? Sure you can't put functions into `Data` and such, but does anybody actually care about that? Anyway, I digress.

What we could have is `case` with a default clause. That'd solve the equality issue described above. Helios folks claim it's not enough in the general case though:

> The default case would solve the issue for some common patterns, but having access to the index is still needed for the most extreme cases

so naturally I wonder what those extreme cases are.

But let's say that instead of introdcing a basic default clause, we introduce a fancy default clause giving you access to the index of the constructor. It's gonna be a bit weird, because the AST doesn't know anything about integers, but let's say we'll pull it off somehow. Would it be good or weird? It's pretty much reflection at this point and UPLC wasn't designed with any reflection capabilities in mind, so maybe that'll screw the metatheory up somehow?

Anyway, I'll mark this as low-priority, because speeding up `Data` is far more important, but now that Helios folks told us about this problem I do find the lack of default clauses unfortunate, so maybe we should do something about it.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.