haskell / haskell/happy

Strict mode is not in fact strict

Open
#346 4 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
322
Forks
86
PR merge metrics
No merged PRs in 30d

Description

Lets look at a typical bit of generated happy code (without using `--coerce`):
```
happyReduce_1 = happySpecReduce_2 17 happyReduction_1
happyReduction_1 (HappyAbsSyn_2 happy_var2) (HappyAbsSyn_1 happy_var1) =
HappyAbsSyn_3 (foobar happy_var1 happy_var2)
```
So the crucial question is: does the result of `foobar` above get reduced to weak head normal form?

The answer is no. Therefore the title of the issue: this is insufficiently strict.

It's also contrary to what the user guide says.

> This option causes the right hand side of each production (the semantic value) to be evaluated eagerly at the moment the production is reduced. If the lazy behaviour is not required, then using this option will improve performance and may reduce space leaks.

Lets see why it is not strict...

```
happySpecReduce_2 nt fd ... =
let r = fn v1 v2
in happySeq r ...
```
Ok, so in `--strict` mode `happySeq = seq` and so it does reduce `fn v1 v2` to WHNF. But what is `fn` in practice? In the (typical) example above it is
```
HappyAbsSyn_3 (foobar happy_var1 happy_var2)
```
which is already in WHNF! So this does nothing. And crucially it does not reduce `foobar` to WHNF.

Why not? Because `HappyAbsSyn_3` itself is a constructor with a single non-strict field:
```
data HappyAbsSyn t1 t2 t3 = ... | HappyAbsSyn_1 t1 | HappyAbsSyn_2 ts | HappyAbsSyn_3 t3
```

So perhaps the fix is simple: make the `HappyAbsSyn_X` constructors have strict fields?

Presumably at some point in happy's history this strict mode did actually do something, but I'm guessing some change later introduced the non-strict `HappyAbsSyn` constructors and foiled the strictness. Maybe?

On the other hand the `--coerce` mode, when combined with `--strict` _does_ look like it will actually be strict. Since in this mode the non-strict `HappyAbsSyn_X` constructors are replaced by very-much-strict `unsafeCoerce#` "functions". In one real world parser, comparing `--strict --ghc` vs `--strict --ghc --coerce` nets substantial memory reductions. And previously `ghc-debug`'s thunk analysis showed that there were huge numbers of thunks originating from the generated reduction functions.

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.