Help implementing a recursive Parser

Help
#1

Hello!
As an exercise I was trying to implement my own monadic parser combinators library and to test it I wanted to implement a very simple Json parser.

My simplified Json AST and Parser are represented by the following types:

data JsonValue
  = JsonNull
  | JsonBool Boolean
  | JsonNumber Int
  | JsonString String
  | JsonArray (Array JsonValue)
  | JsonObject (Array (Tuple String JsonValue))

newtype Parser a
  = Parser (String -> Maybe (Tuple a String))

Everything was going well until I tried to implement the jsonArray Parser. Following the advise on this link https://github.com/Thimoteus/SandScript/wiki/2.-Parsing-recursively I made my Parser Lazy

instance lazyParser :: Lazy (Parser a) where
  defer f = Parser $ \input -> p input
    where
      (Parser p) = f unit

used the function fix when parsing my jsonValue

jsonValue :: Parser JsonValue
jsonValue =
  fix
    $ \p ->
        (jsonNull <|> jsonBool <|> jsonNumber <|> jsonString <|> jsonArray p)

And also made the jsonArray parser take another parser

jsonArray :: Parser JsonValue -> Parser JsonValue
jsonArray p = JsonArray <$> wrappedP open (sepByP p wsAndComma) close
  where
    open = (charP '[') *> (manyP wsP)

    close = (manyP wsP) <* (charP ']')

    wsAndComma = (manyP wsP) *> (charP ',') <* (manyP wsP)

However, I am still getting a runtime error that I have no clue how to solve

/.psci_modules/node_modules/Parser/index.js:71
            return Control_Bind.bind(Data_Maybe.bindMaybe)(v(input))(function (v1) {
                                                           ^

TypeError: v is not a function

This error only happens if I pass a jsonValue parser to jsonArray Parser. I tried passing the other parsers to jsonArray and it works, so I believe the problem may be in the way I am implementing Lazy or the way I am using the fix function.

If you have any idea of what may be happening here. Please help me! :smile:

Thanks,
Andres!

Parsing recursively with purescript-parsing
#2

This is not a correct implementation for a Lazy instance. The purpose of Lazy is to defer evaluation of the suspended term (Unit -> ...) until it is demanded. If you immediately call f unit, then this is not any different than normal strict evaluation, with all the issues it causes.

instance lazyParser :: Lazy (Parser a) where
  defer f = Parser $ \input -> let (Parser p) = f unit in p input

This calls f unit only once it is demanded by moving it inside the parser lambda.

2 Likes
#3

Thank you so much @natefaubion, I knew my implementation was wrong but couldn’t wrap my head around how to correctly implementing it.

#4

How does calling f prematurely end up causing a TypeError: v is not a function runtime failure? I would have thought such a runtime failure wasn’t possible in any compiling PureScript program without messing up in some FFI definition.

#5

General recursion and strictness are pretty delicate.

let a = a in a

Is a well-typed program (forall a. a) but it’s a bit dodgy since it’s a bottom value. PureScript will complain for this declaration, but it uses a pretty basic syntactic check, requiring all recursive references in a binding group to be guarded under a syntactic lambda. It’s pretty easy to subvert though.

let a = (\_ -> a) unit in a

Again, this is well-typed, and all references in the binding group are guarded under a syntactic lambda, so the compiler accepts it.

There’s tons of stuff on the issue tracker about this. This issue comes up in every strict language with recursion. You’ll get this behavior in Elm. I think MLs do some runtime initialization to catch this and throw an exception. Preventing it statically basically amounts to primitive effect tracking in the type system, since it’s a form of “impurity”.

5 Likes