More ergonomic way to compose parser combinators

[AZMCode]

For context, the std/text/parser library has parser combinators. But these combinators are unusual in the sense that they don't return functions, which can be passed into other combinators, but rather execute the combinator itself.

This means that, in order to pass the result of a parser combinator to another parser combinator, one needs to wrap the previous combinator call in a lambda, before passing into the next combinator.

For example, I have the following to help parse an array of UUID strings

pub fun uuid-array-parser(): parse list<string>
  with open-close()
  with space-around()
  with return(pair: (list<string>,list<string>))
    val (uuids,_) = pair
    uuids
  with delimited-many(No)
    whitespace()
  uuid-parser()

All this does is pass the UUID parser, in order, to a combinator which is many but with delimiters, drop the parsed delimiters, parse whitespace around the list, and parse all that wrapped in [].

I found this is the most ergonomic way to write this logic, however, the order in which the parser combinators are applied is reversed, and If I were to want to do this within a larger function, I'd need to define a lambda containing the withs, and immediately call it. For example:

fun bigger-function(): parse unit
 // Some other logic
 val parsed-uuids = ({
   with open-close()
   with space-around()
   with return(pair: (list<string>,list<string>))
     val (uuids,_) = pair
     uuids
   with delimited-many(No)
     whitespace()
   uuid-parser()
 })()
 // Use the parsed UUIDs somewhere else

While this could easily be fixed by making the parser combinators return parsers instead of the result of calling the parser, I feel this pattern is valid, and could be useful.

It would be nice if a new syntax sugar operator, say => (better operator names could be chosen), which does the same thing as the . operator, but wraps the expression before it in a lambda.

This way the logic could be written as (what looks like) chained method calls.

pub fun uuid-array-parser(): parse list<string>
  uuid-parser()
    =>delimited-many(No)
      whitespace()
    .fst()
    =>space-around()
    =>open-close()

And could be used within a bigger function without explicitly wrapping the inner expression in a lambda

fun bigger-function(): parse unit
  // Some other logic
  val parsed-uuids =
    uuid-parser()
    =>delimited-many(No)
      whitespace()
    .fst()
    =>space-around()
    =>open-close()
  // Use the parsed UUIDs somewhere else

More concretely, the operator would desugar any expression a=>b(c,d,...) into ({a}).b(c,d,...), which, of course, would eventually desugar into b(({a}),c,d,...)

[TimWhiting]

Why not?

pub fun uuid-array-parser(): parse list<string>
  open-close
     space-around
        val (uuids, _) = uuid-parser.delimited-many(No, whitespace)
        uuids

I think this is rather readable. (You don't have to actually call uuid-parser(), or do something like {uuid-parser()}, since {uuid-parser()} is equivalent to uuid-parser).

In this case the parser for something like delimited-many should accept as it's first parameter the parser to use as the child.
And I think the indentation actually helps for readability in this case, so I wouldn't use with.

[AZMCode]

That's a pretty good solution, but the indentation reminds me a bit of the Pyramid of Doom. Surely it would be best to avoid patterns which unnecessarily introduce indentation, particularly ones representing a linear sequence of steps?
Might be wrong about all this though.

While I understand {f()} is equivalent to f, I thought it might make it clearer f is a parameterless function lambda passed to the method call, rather than a value being passed into a method call, but bare f certainly looks nicer.

[TimWhiting]

I actually really like the indentation, it really mimics the structure you are parsing. I don't think it gives me pyramid of doom vibes, since parser combinators are intended to allow you to break up parsers into more manageable smaller chunks and abstractions (as in delimited-many). If the nesting is getting too deep I would suggest considering how to break the parser up into smaller nameable chunks or abstractions. In particular, in most languages that have pyramid of doom issues, the problem is made worse by all of the extraneous surrounding syntax like parentheses & braces etc. In Koka we have simple indentation, which makes it really readable, and if it becomes unreadable we have the with statement to decrease indentation when the block is the rest of the function body.

As far as your second point, in functional languages both functions and lambdas are values, so to me, it is a value being passed into a method call. Wrapping it up in a lambda to me seems pointless, since it just introduces a level of indirection that hopefully gets optimized away anyways. Maybe it is an issue of naming the parsers? Appending parser makes it seem like it is named as a value, and appending parse makes it seem it should be an action, which really just makes sense in {action()} and value contexts respectively. Instead, you could just name it as what it parses. I recognize that this is leaning on the value side. But in higher order contexts where you are passing parsers to parsers, I think that erring on the value side is the correct thing to do, and matches the rest of your names.

Compare this:

pub fun uuid-array(): parse list<string>
  open-close
     space-around
        uuid.delimited-many(No, whitespace).fst

to this:

pub fun uuid-array(): parse list<string>
  uuid()
    =>delimited-many(No)
      whitespace()
    .fst()
    =>space-around()
    =>open-close()

Which is more readable? (I also renamed yours so that it is syntax we are comparing)
To me the first is much much more readable.

[AZMCode]

Fair enough. You bring up some good points. I guess I haven't passed enough time in the funcional side of things to be comfortable accepting functions-as-values as much. In any case, I believe you might be right about the indentation after all. Maybe I'll get used to it, who knows. I appreciate the discussion nonetheless!

[TimWhiting]

Sorry if I seem like I'm dismissing your ideas. I think it is valuable to consider ideas like these. Hopefully my suggestions on how to utilize Koka's strengths and features as they currently exist don't come across wrong. I do think Koka obviously still has room to grow and change, there are plenty of rough edges still. And there are definitely idioms that come naturally to me now in Koka, but took me a while to rewire my brain to get used to. I also really enjoyed this discussion since it helped elucidate different naming and design conventions to make parsers easily composable, readable and useful.