IntersectMBO / IntersectMBO/plutus

`isFunctionType` in `PlutusIR.Transform.ThunkRecursions` misses a case for polymorphic functions

Open
#4,782 4 comments 0 reactions 0 assignees View on GitHub
Costing Low priority Performance status: triaged
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.