IntersectMBO / IntersectMBO/plutus
`isFunctionType` in `PlutusIR.Transform.ThunkRecursions` misses a case for polymorphic functions
- Dominant language
- Haskell
- Stars
- 1.6k
- Forks
- 508
- Avg merge
- 3d 10h
- Merged PRs (30d)
- 22
Description
### Summary
[`isFunctionType` in `PlutusIR.Transform.ThunkRecursions`](https://github.com/input-output-hk/plutus/blob/c8d4364d0e639fef4d5b93f7d6c0912d992b54f9/plutus-core/plutus-ir/src/PlutusIR/Transform/ThunkRecursions.hs#L98) misses a case for polymorphic functions. This means that the `thunkRecursions` pass will create a non-strict let-binding for such functions, which in the subsequent `compileNonStrictBindings True` will then give an unnecessary (Scott-encoded) unit argument. This matters, because this unit argument then makes it all the way through to the untyped Plutus core, resulting in larger than necessary core (indeed, Section 7 of "Formal Specification of the Plutus Core Language" explicitly states that the reason force/delay were introduced in the first place is the size of these unit arguments).
### Steps to reproduce the behavior
Consider
```haskell
newtype Reverse = Reverse (forall a. [a] -> [a])
reversePoly :: [a] -> [a]
reversePoly = reversePoly' []
reversePoly' :: [a] -> [a] -> [a]
reversePoly' acc [] = acc
reversePoly' acc (x:xs) = reversePoly' (x:acc) xs
reverseMono :: [Integer] -> [Integer]
reverseMono = reverseMono' []
reverseMono' :: [Integer] -> [Integer] -> [Integer]
reverseMono' acc [] = acc
reverseMono' acc (x:xs) = reverseMono' (x:acc) xs
compiledReversePoly :: CompiledCode (Reverse)
compiledReversePoly = $$(compile [|| Reverse reversePoly ||])
compiledReverseMono :: CompiledCode ([Integer] -> [Integer])
compiledReverseMono = $$(compile [|| reverseMono ||])
```
(the `newtype` is merely there to give `CompiledCode` a monomorphic type). If we trace the compilation of the monomorphic reverse through the pipeline, just before `thunkRecursions` we have
```haskell
let rec data List :: * -> * a = Nil | Cons a (List a)
in let rec !reverseMono = λ(acc :: List Integer) (ds :: List Integer) -> Nil_match {Integer} ds {∀ _. List Integer} (λ{_} -> acc) (λ(x :: Integer) (xs :: List Integer) {_} -> reverseMono (Cons {Integer} x acc) xs) {_}
in reverseMono (Nil {Integer})
```
(this is using my custom pretty-printer, excuse the non-standard syntax); the subsequent `thunkRecursions` pass then does not affect `reverseMono` binding at all, and consequently `compileNonStrictBindings True` doesn't do anything either. In the polymorphic case we see instead
```haskell
let rec data List :: * -> * a = Nil | Cons a (List a)
in let rec !reversePoly = λ{a} (acc :: List a) (ds :: List a) -> Nil_match {a} ds {∀ _. List a} (λ{_} -> acc) (λ(x :: a) (xs :: List a) {_} -> reversePoly {a} (Cons {a} x acc) xs) {_}
in λ{a} -> reversePoly {a} (Nil {a})
```
which then by `thunkRecursions` is turned into
```haskell
let rec data List :: * -> * a = Nil | Cons a (List a)
in let rec reversePoly = λ{a} (acc :: List a) (ds :: List a) -> Nil_match {a} ds {∀ _. List a} (λ{_} -> acc) (λ(x :: a) (xs :: List a) {_} -> reversePoly {a} (Cons {a} x acc) xs) {_}
in λ{a} -> reversePoly {a} (Nil {a})
```
and then by `compileNonStrictBindings True` into
```haskell
let rec data List :: * -> * a = Nil | Cons a (List a)
in let rec !reversePoly = λ(arg :: ∀ a. a -> a) {a} (acc :: List a) (ds :: List a) -> Nil_match {a} ds {∀ _. List a} (λ{_} -> acc) (λ(x :: a) (xs :: List a) {_} -> reversePoly (λ{a} (x :: a) -> x) {a} (Cons {a} x acc) xs) {_}
in λ{a} -> reversePoly (λ{a} (x :: a) -> x) {a} (Nil {a})
```
where we see that Scott-encoded unit argument being introduced. This then makes it all the way to the core.
### Actual Result
The untyped Plutus core for `reversePoly` is
```
let* s = \ s_0 x -> let* reversePoly = s_0 s_0 in \ ~ acc ds -> ds ! (\ ~ -> acc) (\ x_0 xs ~ -> reversePoly (\ ~ x_1 -> x_1) ! (\ ~ case_Nil case_Cons -> case_Cons x_0 acc) xs) !
reversePoly_0 = s s
in \ ~ -> reversePoly_0 (\ ~ x_2 -> x_2) ! (\ ~ case_Nil_0 case_Cons_0 -> case_Nil_0)
```
### Expected Result
The untyped Plutus core for `reverseMono` is
```
reverseMono =
let* s = \ s_0 x -> let* reverseMono = s_0 s_0 in \ ds -> ds ! (\ ~ -> x) (\ x_0 xs ~ -> reverseMono (\ ~ case_Nil case_Cons -> case_Cons x_0 x) xs) !
reverseMono_0 = s s
in reverseMono_0 (\ ~ case_Nil_0 case_Cons_0 -> case_Nil_0)
```
which is significantly smaller. _Some_ size difference is perhaps expected (polymorphism leading to force/delay constructors elsewhere), but that is orthogonal to this ticket. The extra ` (\ ~ x_2 -> x_2)` argument in the polymorphic version should not be needed.
### Describe the approach you would take to fix this
_No response_
### System info
The above is tested with 4127e9cd6e889824d724c30eae55033cb50cbf3e , though I see that `isFunctionType` has not changed in latest `master`.
Contributor guide
Research direction
Start in plutus-core/plutus-ir/src/PlutusIR/Transform/ThunkRecursions.hs at isFunctionType, then trace the polymorphic and monomorphic examples through thunkRecursions and compileNonStrictBindings True. Done means the polymorphic case no longer receives the unnecessary Scott-encoded unit argument in the untyped Plutus core, while the existing monomorphic behavior remains unchanged.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100