User loginNavigation |
Monads vs Applicative Functors.This article (https://jobjo.github.io/2019/05/19/applicative-parsing.html) got me thinking about the structural problems with monads, namely that `bind: m a -> (a -> m b) -> m b` is opaque in its second argument. One thing that I have become increasingly concerned with over the past few years is the separation of data and code, and this article made it clear to me that monads have a problem in this respect, and at least in the case of parsers result in mixing implementation details with the application of the parser. By combining an approach focused on the initial algebra for parsers, and implementing combinators as an applicative functor (and not a monad), the "application" of the parser is reduced to a static data structure, and the `map` functions only generate output. Using continuation parsing to encode the existential types from the GADT (see https://unsafe-perform.io/posts/2020-02-21-existential-quantification-in-typescript and function overloading, I was able to port the applicative parser to TypeScript, which I have made available here https://github.com/keean/applicative_parser and as a Deno module here https://deno.land/x/applicative_parser. I also added a couple of useful helper functions based on Parsimmon's `seq` and and `seqMap` which use a little conditional-type magic to make working without operator overloading easier. The result is we can write a simple parser in TypeScript (for floats) like this: const digit = OneOf('0123456789'); const float1 = seqMap((a, b) => [...a, b], many1(digit), OneOf('.')); const float2 = seqMap((a, b) => [...a, ...b], float1, many1(digit)); const float3 = seqMap((a, b, c) => [...a, b, ...c], choice(float2, many1(digit)), OneOf('e'), many1(digit)); export const float: Parser<number> = FMap(a => parseFloat(a.join('')), choice(float3, float2, float1)); Monads are of course useful, and things aren't really so black and white, but it seems interesting to consider what can be gained from the separation of data and code possible if we limit ourselves to applicative functors. The benefits include being able to have a complete implementation for the parser initial algebra in 50ish lines of code, that you can build your parser application from the basic 9 combinators and applications can remain the same whilst you can swap different implementations (with backtracking, error reporting, greater efficiency etc). It also seems interesting to consider the initial algebra for parsers in the same way we consider Codd's five primitive operators for relational algebra. The ones used in the article are Fail/Empty/OneOf/Return/Forget/Map/Product/Either/Fix, is this minimal? There are clearly alternative formulations, for example `OneOf` isn't the only possibility, but it has the advantage that it allows the set of accepted symbols to be generated for a parser application. In the context of compiler architecture, it seems interesting that each pass of the compiler can be implemented as a recursive descent of the abstract syntax tree with case matching on node type. With this approach the parser also becomes a recursive descent with case matching over the syntax definition of the language, which seems an elegant solution. Thinking about programming languages themselves, as we can thread state through an applicative functor, and we can assign to scoped variables (map), it seems interesting to think about what a functional language that uses applicative functors to manage state and IO would look like? Obviously existing programming languages can implement applicative functors, in the same way you can write object-oriented code in procedural languages, but they don't focus on it. Likewise there is nothing stopping someone writing monadic code, but you would not want to encourage it. What would a language designed to encourage the programmer to think in an applicative, initial-algebraic way look like? By Keean Schupke at 2021-07-15 09:32 | LtU Forum | previous forum topic | next forum topic | other blogs | 6192 reads
|
Browse archives
Active forum topics |
Recent comments
21 weeks 6 days ago
21 weeks 6 days ago
21 weeks 6 days ago
44 weeks 23 hours ago
48 weeks 2 days ago
50 weeks 2 hours ago
50 weeks 2 hours ago
1 year 3 days ago
1 year 5 weeks ago
1 year 5 weeks ago