[generics-rep] Trivial genericShow blows up the call stack

[karljs]

I have the following code in my library:

data VVis a
  = Fill a (Frame a)
  | ...

derive instance genericVVis :: Generic (VVis a) _
instance showVVis :: Show a => Show (VVis a) where
  show = genericShow

data Frame a = Frame
  { frameMax :: a
  , frameMin :: a
  }

derive instance genericFrame :: Generic (Frame a) _
instance showFrame :: Show a => Show (Frame a) where
  show = genericShow

If I now load my code in a REPL and create the following trivial value:

> Fill 2.0 (Frame {frameMax: 1.0, frameMin: 0.0})
return new Data_Show.Show(Data_Generic_Rep_Show.genericShow(genericVVis)(Data_Generic_Rep_Show.genericShowSum(Data_Generic_Rep_Show.genericShowConstructor(Data_Generic_Rep_Show.genericShowArgsProduct(Data_Generic_Rep_Show.genericShowArgsArgument(dictShow))(Data_Generic_Rep_Show.genericShowArgsArgument(showFrame(dictShow))))(new Data_Symbol.IsSymbol(function () {
                                                                             ^

RangeError: Maximum call stack size exceeded
...

This is a very small value, so I don't understand why this is blowing up the call stack. Could somebody help me understand please?

[derektmueller]

I get the same error for the following code:

module Main where

import Prelude
import Effect (Effect)
import Effect.Console (log)
import Foreign
import Foreign.Class (class Encode, class Decode)
import Foreign.Generic (defaultOptions, genericEncode, genericDecode, encodeJSON, decodeJSON)
import Foreign.JSON
import Data.Generic.Rep (class Generic)
import Data.Generic.Rep.Show (genericShow)

data Tree a = Leaf a | Branch (Tree a) (Tree a)
derive instance genericTree :: Generic (Tree a) _
instance showTree :: Show a => Show (Tree a) where 
  show = genericShow

main :: Effect Unit
main = do
  log $ show (Branch (Leaf 1) (Leaf 2))
  pure unit

For some reason it's fixed by changing

  show = genericShow

to

  show x = genericShow x

It might have something to do with the type being recursive, since I'm not able to reproduce the callstack error for @karljs's VVis datatype, but I can if I make it recursive. For example,

data VVis a = Fill a (Frame a) | Something (VVis a)

[safareli]

I also got similar error

var GenericShowArgs = function (genericShowArgs) {
                               ^
RangeError: Maximum call stack size exceeded

when used implemented show for this types using generic

type Name = String
type Only = Boolean

data Group t
  = Describe Only Name (Array (Group t))
  | SetExecution Execution (Array (Group t))
  | It Only Name t
  | Pending Name

data Result  = Success | Failure Error
data Execution = Parallel | Sequential

[safareli]

here is travis error https://travis-ci.org/purescript-spec/purescript-spec/builds/466438964#L1159 and commit purescript-spec/purescript-spec@48bdf25 in case someone wants to look into it at some point

[garyb]

That one isn't quite so trivial, since the first case is not recursive, but thanks for the example!

[safareli]

travis (CI) not trivial :p

[paulikauro]

I stumbled across this while trying to find a smaller datatype for which the stack overflow error happens. This code results in a compile error 🤔

module A where
import Data.Generic.Rep
import Data.Show.Generic
import Data.Show
data Nat = Z | S Nat
derive instance Generic Nat _
instance Show Nat where show = genericShow

[1 of 1] Compiling A
Error found:
at src/A.purs:7:1 - 7:43 (line 7, column 1 - line 7, column 43)

  The value of $showNat3 is undefined here, so this reference is not allowed.


See https://github.com/purescript/documentation/blob/master/errors/CycleInDeclaration.md for more information,
or to contribute content related to this error.

For some reason it's fixed by changing

  show = genericShow

to

  show x = genericShow x

Curiously, that also fixes the compile error.
I'm using PureScript 0.15.4

[garyb]

Curiously, that also fixes the compile error.
I'm using PureScript 0.15.4

This is a very common thing that's needed when defining generic instances (or perhaps more accurately, when using default member implementations) for recursive types. I think unless the recursion in the type appears under a lambda, the instance will always require eta expansion - otherwise we'll get stack overflow/infinite loops, much like the original example in this issue. This is a consequence of PureScript being strictly evaluated.

I've not looked at this for a long time, but possibly the "actual" issue for the initial example is that the compiler should be detecting the cycle and failing to do so, since the eta expansion did fix second example given.

In the past I argued for automatic eta expansion of these cases when we can detect them, but there wasn't much enthusiasm for it since it would be a bit magical and ad-hoc, but maybe there's a principled scheme that could be concocted that would make it acceptable. I just eta expand and move on these days. 😄