This post isn’t really about the Maybe Monad of course. It is more focused on the State Monad, but I have a weakness for alliteration.
What do
space suits
nuclear waste containers
romantic conquests
monsters
macros
containers
conversations
have in common? They’ve all been used as metaphors for monads.
Last time I looked, the Haskell wiki listed 29 tutorials on the subject, and that is where all these allusions come from.
Such a wealth of explanatory fauna demands its own (meta-)explanation. Maybe monads are so wildly popular that there is monadic gold rush to cash in on the monad education and training market. And yet, the long-awaited landmark tome, “Category Theory for Dummies in 21 days and 1001 nights” is nowhere to be found.
Tangent: There is of course, Benjamin Pierce's delightfully slim book on the topic which is as close to a gentle introduction as one can come.
Could it just be that people just have a hard time understanding monads? If so, what are the prospects of mass adoption? Or making Just(something) out of Nothing am I?
By now you realize that if monads were a stock, I’d be shorting it. I’m going to go get myself in a huge amount of trouble now, just as I did when I took a hideously pragmatic tack on continuations some years ago.
The most important practical contribution of monads in programming is, I believe, the fact that they provide a mechanism to interface pure functional programming to the impure dysfunctional world.
The thing is, you don’t really need them for that. Just use actors. Purely functional actors can interact with the stateful world, and this has been known since before Haskell was even conceived.
Tangent: Before you crucify me for being so narrow minded, pray consider the mitigating circumstance that I have used the words "practical" and "pure functional programming" in the same sentence. There are many who regard that, rather than my disrespectful attitude toward monads, as grounds for my institutionalization.
Some kind soul will doubtless point out to me how you can view actors as monads or some such. Be that as it may, it is beside the point. You can invent, build and most importantly, use, actors without ever mentioning monads. Carl Hewitt and his students did that decades ago.
Tangent: I have to say how amazing that is. Actors were first conceived by Hewitt in 1973(!), and Gul Agha's thesis has been around for 25 years. I firmly believe actors are the best answer to our concurrency problems, but that is for another post.
You can write an actor in a purely functional language, and have it send messages to file systems, databases or any other other stateful actor. Because the messages are sent asynchronously, you never see the answer in the same activation (aka turn) of the actor, so the fact that these actors are stateful and may give different answers to the same question at different times does not stain your precious snow white referential transparency with its vulgar impurity. This is pretty much what you do with a monad as well - you bury the stateful filth in a well marked shallow grave and whistle past it.
Of course, your troubles are by no means over. Actors or monads, the state is out there and you will have to reason about it somewhere. But better you reason about it in a well bounded shallow grave than in C.
What is important to me is that the notion of actors is intuitive (a pesky property of Dijkstra’s hated anthropomorphisms, like self) for many people. Yes, there are many varieties of actors and I have my preferences - but I’ll take any one of them over a sheaf of categories.
Speaking of those preferences, look at the E programming language (I often point at Mark Miller’s PhD thesis) or on AmbientTalk. I would like to have something similar in Newspeak (and in its hypothetical functional subsets, Avarice and Sloth).
Of course, there is much to be said for a programming culture that excludes anyone without at least the potential of a PhD. Indeed, if you can surround yourself with such people, you can do amazing things with just Java, C++ and Python (though they will still be more productive if they have the good taste to use something nicer). So perhaps the true value of monads lies in their exclusionary nature.
Nevertheless, there is more work to be done than some small, celebrated priesthood can or will do all by itself. There is real value in functional programming in some contexts, and it needs to integrate with stateful programming. Actors provide a model that is much easier for most humans to relate to.
Showing posts with label Functional Programming. Show all posts
Showing posts with label Functional Programming. Show all posts
Sunday, January 23, 2011
Saturday, December 11, 2010
Reflecting on Functional Programming
In this post, I wanted to make a case for reflection in the context of pure functional programming. I don’t know that pure functional languages should be different than other languages in this regard, but in practice they are: they generally do not have reflection support.
To demonstrate the utility of reflection, I’m going to revisit one of my favorite examples, parser combinators. In particular, we’ll consider how to implement executable grammars. Executable grammars are a special flavor of a parser combinator library that allows semantic actions to be completely separated from the actual grammar. I introduced executable grammars as part of the Newspeak project.
Consider the following grammar:
In Newspeak, we’d write:
Now let’s define some semantic action, say, creating an AST. The Newspeak library let’s me do this in a subclass, by overriding the code for the production thus:
No prior parser combinator library allowed me to achieve a similar separation of grammar and semantic action. In particular, I don’t quite see how to accomplish this in a functional language.
In the functional world, I would expect one function would define the actual grammar, and another would perform the semantic actions (in our example, build the AST). The latter function would transform the result of basic parsing as defined by the grammar, producing an AST as the result. We’d use pattern matching to define this function. I’d want to write something like:
where makeAST maps a concrete parse tree into an abstract one. Which in this case looks pretty easy.
The question arises: where did the patterns ifStatement, returnStatement, number and identifier come from?
Presumably, our parser combinator library defined them based on our input grammar. The thing is, the library does not know the specifics of our grammar in advance. It cannot predefine data constructors for each conceivable production. Instead, it should create these data constructors dynamically each time it processes a specific grammar.
How does one create datatypes dynamically in a traditional functional language? I leave that as an exercise for the reader.
Ok, so while it is clear that creating datatypes on the fly would be very helpful here, it is also clear that it isn’t easy to do in the context of such languages. How would you describe the type of the library? The datatype it returns is created per grammar, and depends on the names of the grammar production functions. Not easy to characterize via Hindley-Milner. And yet, once the library created the datatype, we actually could utilize it in writing type safe clients.
Instead, our library will probably generate values of some generic datatype for parse trees. A possible representation is a pair, consisting of a tag of type string representing the name of the production used to compute the tree, and a list consisting of the elements of the tree, including vital information such as where in the input stream a given token was found and what string exactly represented it. We cannot elide such lexical information, because some users of our library will need it (say, pretty printers). Then I can write:
Obviously, we’ve lost the type safety of the previous version. Ironically, the inability of the language to generate types dynamically forces code to be less statically type safe.
Now ask yourself - how does our combinator library produce values of type parsetree with an appropriate tag? For each parsetree value p(tag, elements), the tag is a string corresponding to the name of the production that was used to compute p. How does our library know this tag? The tag is naturally specified via the name of the production function in the grammar. To get at it, one would need some introspection mechanism to get the name of a function at run time. Of course, no such mechanism exists in a standard functional language. It looks like you’d have to force the user to specify this information redundantly as a string, in addition to the function name (you still need the function name so that other productions can refer to it).
You might argue that we don’t really need the string tags - just return a concrete parse tree and distinguish the cases by pattern matching. However, it isn’t generally possible to tell the parse tree for a number from that for an identifier without re-parsing. Even when you can tell parse trees apart, the resulting code is ugly and inefficient, as it is repeating some of the parser’s work.
We could approach the problem via staged execution, writing meta-program that statically transformed the grammar into a program that would provide us with the nice datatype constructors I suggested in the beginning. If one goes that route, you might as well define an external DSL based on BNF or PEGs.
So, I assert that reflection is essential to this task, and dynamic type generation would be helpful as well, which would require dependent types and additional reflective functionality. However, maybe I’ve overlooked something and there is some other way to achieve the same goal. I’m sure someone will tell me - but remember, the library must not burden the user by requiring redundant information or work, it must operate independent of the specifics of a given grammar, and it must keep semantic actions entirely separate.
In any case, I think there is considerable value in adding at least a measure of introspection, and preferably full reflection, to traditional functional languages, and interesting work to be done fleshing it out.
To demonstrate the utility of reflection, I’m going to revisit one of my favorite examples, parser combinators. In particular, we’ll consider how to implement executable grammars. Executable grammars are a special flavor of a parser combinator library that allows semantic actions to be completely separated from the actual grammar. I introduced executable grammars as part of the Newspeak project.
Consider the following grammar:
statement -> ifStatement | returnStatement
ifStatement -> ‘if’ expression ‘then’ expression ‘else’ expression
returnStatement -> ‘’return’ expression
expression -> identifier | number
In Newspeak, we’d write:
class G = ExecutableGrammar ( |
(* lexical rules for identifier, number, keywords elided *)
(* The actual syntactic grammar *)
statement = ifStatement | returnStatement.
ifStatement = if, expression, then, expression, else, expression.
returnStatement = returnSymbol, expression.
expression = identifier | number.
|)()
Now let’s define some semantic action, say, creating an AST. The Newspeak library let’s me do this in a subclass, by overriding the code for the production thus:
class P = G ()(
ifStatement = (
super ifStatement wrap:[:if :e1 :then :e2 :else :e3 |
IfStatementAST if: e1 then: e2 else: e3
].
)
returnStatement = (
super returnStatement wrap:[:return :e | ReturnStatementAST return: e].
)
)
No prior parser combinator library allowed me to achieve a similar separation of grammar and semantic action. In particular, I don’t quite see how to accomplish this in a functional language.
In the functional world, I would expect one function would define the actual grammar, and another would perform the semantic actions (in our example, build the AST). The latter function would transform the result of basic parsing as defined by the grammar, producing an AST as the result. We’d use pattern matching to define this function. I’d want to write something like:
makeAST =
fun ifStatement(ifKw, e1, thenKw, e2, elseKw, e3) =
IfStatementAST(makeAST(e1), makeAST(e2), makeAST(e3)) |
fun returnStatement(returnKw, e) = ReturnsStatementAST(makeAST(e)) |
fun identifier(id) = IdentifierAST(id) |
fun number(n) = NumberAST(id)
where makeAST maps a concrete parse tree into an abstract one. Which in this case looks pretty easy.
The question arises: where did the patterns ifStatement, returnStatement, number and identifier come from?
Presumably, our parser combinator library defined them based on our input grammar. The thing is, the library does not know the specifics of our grammar in advance. It cannot predefine data constructors for each conceivable production. Instead, it should create these data constructors dynamically each time it processes a specific grammar.
How does one create datatypes dynamically in a traditional functional language? I leave that as an exercise for the reader.
Ok, so while it is clear that creating datatypes on the fly would be very helpful here, it is also clear that it isn’t easy to do in the context of such languages. How would you describe the type of the library? The datatype it returns is created per grammar, and depends on the names of the grammar production functions. Not easy to characterize via Hindley-Milner. And yet, once the library created the datatype, we actually could utilize it in writing type safe clients.
Instead, our library will probably generate values of some generic datatype for parse trees. A possible representation is a pair, consisting of a tag of type string representing the name of the production used to compute the tree, and a list consisting of the elements of the tree, including vital information such as where in the input stream a given token was found and what string exactly represented it. We cannot elide such lexical information, because some users of our library will need it (say, pretty printers). Then I can write:
makeAST =
fun parsetree(“if”, [ifKw, e1, thenKw, e2, elseKw, e3]) =
IfStatementAST(makeAST(e1), makeAST(e2), makeAST(e3)) |
fun parsetree(“return”, [returnKw, e]) = ReturnsStatementAST(makeAST(e)) |
fun parsetree(“id”,[id]) = IdentifierAST(id) |
fun parsetree(“number”,[in]) = NumberAST(in)
Obviously, we’ve lost the type safety of the previous version. Ironically, the inability of the language to generate types dynamically forces code to be less statically type safe.
Now ask yourself - how does our combinator library produce values of type parsetree with an appropriate tag? For each parsetree value p(tag, elements), the tag is a string corresponding to the name of the production that was used to compute p. How does our library know this tag? The tag is naturally specified via the name of the production function in the grammar. To get at it, one would need some introspection mechanism to get the name of a function at run time. Of course, no such mechanism exists in a standard functional language. It looks like you’d have to force the user to specify this information redundantly as a string, in addition to the function name (you still need the function name so that other productions can refer to it).
You might argue that we don’t really need the string tags - just return a concrete parse tree and distinguish the cases by pattern matching. However, it isn’t generally possible to tell the parse tree for a number from that for an identifier without re-parsing. Even when you can tell parse trees apart, the resulting code is ugly and inefficient, as it is repeating some of the parser’s work.
We could approach the problem via staged execution, writing meta-program that statically transformed the grammar into a program that would provide us with the nice datatype constructors I suggested in the beginning. If one goes that route, you might as well define an external DSL based on BNF or PEGs.
So, I assert that reflection is essential to this task, and dynamic type generation would be helpful as well, which would require dependent types and additional reflective functionality. However, maybe I’ve overlooked something and there is some other way to achieve the same goal. I’m sure someone will tell me - but remember, the library must not burden the user by requiring redundant information or work, it must operate independent of the specifics of a given grammar, and it must keep semantic actions entirely separate.
In any case, I think there is considerable value in adding at least a measure of introspection, and preferably full reflection, to traditional functional languages, and interesting work to be done fleshing it out.
Wednesday, May 12, 2010
Patterns of Dynamic Typechecking
Dynamic type tests are ubiquitous in programming. Regardless of whether the programming language is statically or dynamically typed, object-oriented or functional, the need to establish what sort of value you are dealing with at run time is always there.
In object oriented languages constructs like Java’s instanceOf (or C# typeOf, or Smalltalk isKindOf:) serve this need - as do casts.
Some functional languages put a large emphasis on being “completely statically typed”. In fact, these languages rely heavily on dynamic typechecking in the guise of pattern matching. Somewhere in the middle lie constructs like typecase.
In most languages, constructs for dynamic typechecking undermine data abstraction. They allow one to test for the implementation type of a value. Checking whether an object is an instance of a particular class, or pattern matching against a specific datatype constructor suffer from this problem. In contrast, testing whether a value supports an interface is harmless. Dynamically typed languages don’t support that however.
An old trick is to add methods that support these kind of type queries. Where you might, in Java, define a class A that implements an interface T, you would simply define a method isT on A, that returns true. The problem is that you then need to define a version of isT that returns false for all other types that you might possibly encounter. To be safe, you’d add isT to Object. This is monkey patching of the highest order, and readers of this blog know my view “People don’t let Primitive Primates Program”.
However, there is an out. Define the default version of doesNotUnderstand: to check if the method name is of the form isX, where X has the form of a type identifier. If so, return false. Now all you need to do is define isT for the classes that actually support the T interface. Credit to Peter Ahe for proposing this. It’s in the current Newspeak implementation.
Pattern matching is much more general than isT however; using isT is equivalent to a simple nullary pattern - except for this annoying issue with data abstraction.
Recently, we’ve seen approaches that overcome the data abstraction problem: Scala and F# introduce pattern matching mechanism that allow you to preserve data abstraction. It was Scala’s influence, combined with demand from users at Cadence, that prompted me to examine the idea of supporting pattern matching in Newspeak.
One can’t just go graft a pattern matching construct on to Newspeak however. The only operations allowed in Newspeak are message sends. If we can’t express the matching constructs via messages, they cannot go into the language. This led me to the idea of pattern literals: a special syntax for patterns, that denotes a pattern object. We already have special syntax for number objects, string objects, closure objects etc., so adding pattern objects fits in quite naturally. The nice thing about such an approach is that patterns are first class values. Patterns can be abstracted over in methods, stored in slots and data structures, serialized to disk or what have you. You can’t do that with a pattern in ML or Haskell.
So what exactly would pattern matching in Newspeak look like? Well, Felix Geller has recently completed his masters thesis at HPI Potsdam on just that question. Felix has implemented an experimental language extension supporting pattern literals and integrated it into the Newspeak IDE. The new language features should be available in the next Newspeak refresh (coming to a computer near you, summer 2010).
In the new extension (NS3) patterns are matched against objects via a protocol very similar to Scala’s extractors, thereby preserving data abstraction. However, there is no special construct for pattern matching. Instead, complex patterns can be composed out simpler ones using combinators.
Of course, a quick scan of the literature shows that the functional community got there first. Mark Tullsen proposed first class patterns with combinators for Haskell a decade ago, and there are several other papers dealing with the idea. However, having a proposal does not guarantee that a feature is in fact included in a language; in practice, none of the popular functional languages supports first class patterns.
First class patterns combined with data abstraction are a potent combination. We mean to use them as first class queries that can be sent to objects of various sorts - ordinary in-memory collections, or databases, or logic programs. This is reminiscent of LINQ, except that the queries are first class so they can be abstracted over. You can write code that takes queries as parameters, accepts queries as input from the user, serializes and deserializes queries to persistent storage (allowing you to do meta-queries) and so on. And the beauty of a language like Newspeak is that all this requires but a fraction of the machinery you need in a mainstream setting.
Felix’s thesis will soon be available as a technical report. I am reluctant to steal his thunder before that, but once the report is out, I'll put out a follow up post that illustrates how this works and why it is neat.
In object oriented languages constructs like Java’s instanceOf (or C# typeOf, or Smalltalk isKindOf:) serve this need - as do casts.
Some functional languages put a large emphasis on being “completely statically typed”. In fact, these languages rely heavily on dynamic typechecking in the guise of pattern matching. Somewhere in the middle lie constructs like typecase.
In most languages, constructs for dynamic typechecking undermine data abstraction. They allow one to test for the implementation type of a value. Checking whether an object is an instance of a particular class, or pattern matching against a specific datatype constructor suffer from this problem. In contrast, testing whether a value supports an interface is harmless. Dynamically typed languages don’t support that however.
An old trick is to add methods that support these kind of type queries. Where you might, in Java, define a class A that implements an interface T, you would simply define a method isT on A, that returns true. The problem is that you then need to define a version of isT that returns false for all other types that you might possibly encounter. To be safe, you’d add isT to Object. This is monkey patching of the highest order, and readers of this blog know my view “People don’t let Primitive Primates Program”.
However, there is an out. Define the default version of doesNotUnderstand: to check if the method name is of the form isX, where X has the form of a type identifier. If so, return false. Now all you need to do is define isT for the classes that actually support the T interface. Credit to Peter Ahe for proposing this. It’s in the current Newspeak implementation.
Pattern matching is much more general than isT however; using isT is equivalent to a simple nullary pattern - except for this annoying issue with data abstraction.
Recently, we’ve seen approaches that overcome the data abstraction problem: Scala and F# introduce pattern matching mechanism that allow you to preserve data abstraction. It was Scala’s influence, combined with demand from users at Cadence, that prompted me to examine the idea of supporting pattern matching in Newspeak.
One can’t just go graft a pattern matching construct on to Newspeak however. The only operations allowed in Newspeak are message sends. If we can’t express the matching constructs via messages, they cannot go into the language. This led me to the idea of pattern literals: a special syntax for patterns, that denotes a pattern object. We already have special syntax for number objects, string objects, closure objects etc., so adding pattern objects fits in quite naturally. The nice thing about such an approach is that patterns are first class values. Patterns can be abstracted over in methods, stored in slots and data structures, serialized to disk or what have you. You can’t do that with a pattern in ML or Haskell.
So what exactly would pattern matching in Newspeak look like? Well, Felix Geller has recently completed his masters thesis at HPI Potsdam on just that question. Felix has implemented an experimental language extension supporting pattern literals and integrated it into the Newspeak IDE. The new language features should be available in the next Newspeak refresh (coming to a computer near you, summer 2010).
In the new extension (NS3) patterns are matched against objects via a protocol very similar to Scala’s extractors, thereby preserving data abstraction. However, there is no special construct for pattern matching. Instead, complex patterns can be composed out simpler ones using combinators.
Of course, a quick scan of the literature shows that the functional community got there first. Mark Tullsen proposed first class patterns with combinators for Haskell a decade ago, and there are several other papers dealing with the idea. However, having a proposal does not guarantee that a feature is in fact included in a language; in practice, none of the popular functional languages supports first class patterns.
First class patterns combined with data abstraction are a potent combination. We mean to use them as first class queries that can be sent to objects of various sorts - ordinary in-memory collections, or databases, or logic programs. This is reminiscent of LINQ, except that the queries are first class so they can be abstracted over. You can write code that takes queries as parameters, accepts queries as input from the user, serializes and deserializes queries to persistent storage (allowing you to do meta-queries) and so on. And the beauty of a language like Newspeak is that all this requires but a fraction of the machinery you need in a mainstream setting.
Felix’s thesis will soon be available as a technical report. I am reluctant to steal his thunder before that, but once the report is out, I'll put out a follow up post that illustrates how this works and why it is neat.
Subscribe to:
Posts (Atom)