Parametrised parser

[timjs]

Hi all!

I'm trying to write a small parser lib which is parametrised over the input type and the error type. Based on the parse effect in std/text/parse I started with

pub alias parser<e,x,s,a> = () -> <parse<x,s>|e> a

pub type result<x,s,a>
  Done(result: a, rest : sslice)
  Fail(error : x, rest : sslice)

pub effect parse<x,s>
  final ctl fail(error : x) : a
  ctl pick() : bool
  fun satisfy(pred : (sslice) -> maybe<(a,sslice)>) : maybe<a>

pub fun parse(input : sslice, p : parser<e,x,s,a>) : e result<x,s,a>
  var current := input
  handle p
    return(x)
      Done(x, current)

    final ctl fail(msg)
      Fail(msg, current)

    ctl pick()
      val save = current // save current input
      match resume(True)
        Done(x, rest) -> Done(x, rest)
        _ ->
          current := save // backtrack to saved input
          resume(False)

    fun satisfy(pred)
      match pred(current)
        Just((init, rest)) ->
          current := rest
          Just(init)
        Nothing -> Nothing

Now, as soon as I replace the sslice with s everywhere, I get an error that that Koka expects the handler to have a <div,parse<s>> effect:

lib/parse.kk(15,10): error: effects do not match
  context        :   handle p
                   ...
                               _err2 -> err1
  term           :          p
  inferred effect: <parse<$a>|$e>
  expected effect: <div,parse<$a>|_e1>

Any hints of what's going on here?

[TimWhiting]

I've updated your code to show the error location a bit better.
You were missing the type 'a' in your effect type which was a first problem. After adding that you are able to make everything generic except the parse function.

pub effect parse<a,x,s>
  final ctl fail(error : x) : a
  ctl pick() : bool
  fun satisfy(pred : (s) -> maybe<(a,s)>) : maybe<a>

pub alias parser<e,x,s,a> = () -> <parse<a,x,s>|e> a

pub type result<x,s,a>
  Done(result: a, rest : s)
  Fail(error : x, rest : s)

pub fun parse(input : sslice, p : parser<e,x,sslice,a>) : e result<x,sslice,a>
  var current := input
  handle p
    return(x)
      Done(x, current)

    final ctl fail(msg)
      Fail(msg, current)

    ctl pick()
      val save = current // save current input
      match resume(True)
        Done(x, rest) -> Done(x, rest)
        _ ->
          current := save // backtrack to saved input
          resume(False)

    fun satisfy(pred)
      match pred(current)
        Just((init, rest)) ->
          current := rest
          Just(init)
        Nothing -> Nothing

fun psomething(): <parse<char, string, sslice>> char
  match satisfy(fn(x:sslice) if x.string == "a" then Just(('a', x)) else Nothing)
    Just(x) -> x
    Nothing -> fail("expected 'a'")

fun show(result: result<string,sslice,char>)
  match result
    Done(r, rest) -> "Got: " ++ r.string ++ " Left: " ++ rest.string
    Fail(msg, rest) -> "Failed: " ++ msg ++ " Left: " ++ rest.string

fun main()
  parse("".slice, psomething).show.println

This works, but if you change sslice to s in parse you get the div effect.

I found the issue, it is in resolveHeapDiv in src/Type/InferMonad.hs. All reads of a ref or var automatically get a div effect. It's just that most of the time the compiler can show that it won't be divergent and can automatically remove the effect. In this case it has to make some conservative guess for whatever reason.

To get it to work without messing with the compiler you can insert the divergent effect (both in the effect type of parser as well as of parse):

pub effect parse<a::V,x::V,s::V>
  final ctl fail(error : x) : a
  ctl pick() : bool
  fun satisfy(pred : (s) -> maybe<(a,s)>) : maybe<a>

pub alias parser<e,x,s,a> = () -> <parse<a,x,s>,div|e> a

pub type result<x,s,a>
  Done(result: a, rest : s)
  Fail(error : x, rest : s)

pub fun parse(input : s, p : parser<e,x,s,a>) : <div|e> result<x,s,a>
  var current := input
  handle p
    return(x)
      Done(x, current)

    final ctl fail(msg)
      Fail(msg, current)

    ctl pick()
      val save = current // save current input
      match resume(True)
        Done(x, rest) -> Done(x, rest)
        _ ->
          current := save // backtrack to saved input
          resume(False)

    fun satisfy(pred)
      match pred(current)
        Just((init, rest)) ->
          current := rest
          Just(init)
        Nothing -> Nothing

fun psomething(): <parse<char, string, sslice>> char
  match satisfy(fn(x:sslice) if x.string == "a" then Just(('a', x)) else Nothing)
    Just(x) -> x
    Nothing -> fail("expected 'a'")

fun show(result: result<string,sslice,char>)
  match result
    Done(r, rest) -> "Got: " ++ r.string ++ " Left: " ++ rest.string
    Fail(msg, rest) -> "Failed: " ++ msg ++ " Left: " ++ rest.string

fun main()
  parse("".slice, psomething).show.println

[timjs]

Yeah, that's exactly the problem 😅 I don't want to insert div everywhere, as I think it isn't divergent. But it's good to know that the compiler is conservative at this, and that you found the place where it happens.

[timjs]

I took another look and the extra type parameter a in the parse effect should not be a problem. As a matter of fact, I don't think it should be there, as fail and satisfy really should be able to parse anything, it should not be part of the interface of the effect.

The main errors are that result and satisfy were not generic enough (there was still sslices in it), and parse was to generic (the ss should be sslices). This works without any div effects:

pub alias parser<e,x,s,a> = () -> <parse<x,s>|e> a

pub type result<x,s,a>
  Done(result: a, rest : s)
  Fail(error : x, rest : s)

pub effect parse<x,s>
  final ctl fail(error : x) : a
  ctl pick() : bool
  fun satisfy(pred : (s) -> maybe<(a,s)>) : maybe<a>

pub fun parse(input : sslice, p : parser<e,x,sslice,a>) : e result<x,sslice,a>
  var current := input
  handle p
    return(x)
      Done(x, current)

    final ctl fail(msg)
      Fail(msg, current)

    ctl pick()
      val save = current // save current input
      match resume(True)
        Done(x, rest) -> Done(x, rest)
        _ ->
          current := save // backtrack to saved input
          resume(False)

    fun satisfy(pred)
      match pred(current)
        Just((init, rest)) ->
          current := rest
          Just(init)
        Nothing -> Nothing

[TimWhiting]

Hmm, I thought I tried that, guess not. Nice work!