OK, so just for giggles, I tried to implement monads in C#.

The short version: It appears that I can create a class with forms a 
monad, however it appears to be impossible to define the concept of 
"being a monad" such that you can write code which polymorphically works 
for any monad.


The long version:

It appears that C# generics is too weak to express the necessary type 
relationships that describe what a monad is. I suspect C++ templates 
probably can do this, but C# can't. This rules out the possibility of 
writing an abstract class or an interface which describes all possible 
monads, and then writing code against that interface.

On the other hand, it appears to be quite possible to write code that 
works on one *specific* monad, decided at development-time.

OK, so let me recap what the heck a monad is. It's so abstract that it's 
awkward to put into works, but it's not particularly complicated. If the 
class Foo forms a monad, that basically means that an object of type 
Foo<int> can somehow "supply" an integer. Now there are several possible 
ways it might do that.

The simplest way is if Foo is some kind of data container. For example, 
a List<int> can "supply" integers in that it *contains* integers. So 
many sorts of container form a monad. Another way is if Foo represents 
some kind of "process". For example, Foo<int> might be some kind of 
parser object, which reads some text and parses an integer out of it. 
Most of these "process monads" have some kind of a Run() method that 
actually "executes" the action(s) in question. (The result might not be 
a simple int, of course; for example, a parser could return a parse 
error rather than an int, depending on the input supplied.)

Stepping back from that, if Foo<int> is simply an object that represents 
a supple of integers, then the Foo class forms a monad if we can define 
the following functions:

   public static Foo<T1> Inject(T1);
   public static Foo<T2> Map(Foo<T1>, Func<T1, T2>);
   public static Foo<T1> Join(Foo<Foo<T1>>);
   public static Foo<T2> Chain(Foo<T1>, Foo<T2>);
   public static Foo<T2> Bind(Foo<T1>, Func<T1, Foo<T2>>);

[This isn't quite valid C# syntax, but the meaning should be clear.]

This set is redundant; several of these functions can be defined in 
terms of each other. There are two possible minimal subsets:

- Inject() + Map() + Join()
- Inject() + Bind()

So what do all these functions do, then?

Inject() is simple enough. It takes a thing and constructs an object 
which produces that thing. For example, if Foo is a parser, then 
Inject(5) is a parser which consumes zero characters of input and just 
returns 5. It *always* returns 5, regardless of what input you run the 
parser on. (Since it ignores input anyway.) If Foo is a data container, 
then Inject(5) is just a 1-element container with a 5 in it.

The Map() function is simple enough. It takes a function and applies it 
to every element of a collection. Except that a monad isn't necessarily 
a collection. For example, I might have some parser that returns a 
single digit character, and a function that converts a digit character 
into an actual integer. Using Map(), I end up with a parser that returns 
integers not characters. (Notice that we still haven't *run* any 
parsers, just constructed a more complex parser out of a simpler one.)

If you use Map() to apply a function which produces another Foo, then 
clearly you're going to end up with a Foo<Foo<X>>. The Join() function 
unwraps a layer of wrapping. How this works depends on what the monad is 
(which is why it's definition is crucial). For a container, it's 
obvious; think about flattening a list of lists into a flat list. For 
parsers, it's taking a parser that produces a parser, and then running 
the inner parser to return the result of that. (It sounds more 
complicated than it is.)

The Bind() function actually takes a function that produces a Foo, in 
the way just described. You can think of it as taking a parser and a 
function which consults that parser's output and decides what parser to 
run next, returning that parser so that Bind() can run it. From the 
previous paragraph, it should be obvious that Bind() = Map() + Join(). 
It may be less obvious that Map() = Bind() + Inject() and Join() = 
Bind() + the identity function. So either can be defined in terms of the 
other.

The Chain() function takes two parsers, runs the first one, and then 
runs the second one. It discards the output from the first and returns 
the output from the second. This is the clue to how to implement it; 
it's simply Bind(), given a function which ignores its input and always 
returns the same output.

So anyway, we can define Foo<> and then write the above functions, and 
then Foo<> can be used as a monad. But can we write an abstract 
specification of "monad" and have multiple classes implement it? Sadly 
not, as best as I can tell.

One might naively try this:

   public static Monad<T1> Inject(T1);
   public static Monad<T2> Bind(Monad<T1>, Func<T1, Monad<T2>>)

The first method is fine. But the second doesn't work at all! The 
*intent* is that "Monad" should refer to *the same class* at all times. 
But that isn't how object-oriented class inheritance works. The Bind() 
method is implemented specially for each type of monad. It has to "look 
into" the internal structure of both monad objects - which isn't 
possible if they aren't actually both of the necessary class.

Trying to use Map() and Join() instead is no better:

   public static Monad<T2> Map(Monad<T1>, Func<T1, T2>);
   public static Monad<T1> Join(Monad<Monad<T1>>);

Map() isn't too bad - although since its implementation changes for each 
sort of monad, this really ought to be an instance method rather than 
static. But Join() is again broken. As written, it will accept 
List<Parser<int>> and Parser<List<int>>, whereas we want it to accept 
only List<List<int>> or Parser<Parser<int>>.

If we refer to a *specific* monad class, these problems go away. But if 
we try to be abstract, there's no way to enforce the required 
constraints. The only option is run-time dynamic casting - yuck!

Hmm, all those static methods though... that doesn't sound very OO, does 
it? Well, Inject() looks very much like a "factory", so perhaps we can 
have a FooMonad class that contains a (non-static) Inject(), and the 
move Bind() et al to Foo itself?

   public sealed class FooMonad
   {
     public Foo<T1> Inject<T1>(T1 datum) {...}
   }

   public sealed class Foo<T>
   {
     public Foo<T2> Map<T2>(Func<T, T2> f) {...}
     public Foo<T2> Bind<T2>(Func<T, Foo<T2>> f) {...}
   }

Even here, trying to write a type signature for Join() is problematic. 
Basically Join() takes "this" and returns a Foo<T2> - but only if 
T=Foo<T2>. How do you say that in a type signature? The only real way 
around this is to artificially stuff Join() back into FooMonad.

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> OK, so just for giggles, I tried to implement monads in C#.
>
> The short version: It appears that I can create a class with forms a
> monad, however it appears to be impossible to define the concept of
> "being a monad" such that you can write code which polymorphically works
> for any monad.
>
>
<snip>

Not sure I completely understand... The only functional language I've worked
with is LISP, and I only wrote one rather simple program in it, but in the
interest of learning...

Is this something that could be handled with a pure virtual base class which
defines those elements common to ALL monads and requires type-specific
definitions from implementers?

Or perhaps you'd need a mechanism like the STL sort routine which requires you
to pass it a compare function.

Again, I'm not sure I get the concept here...


Regards,
A.D.B.

Post a reply to this message

Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
> Again, I'm not sure I get the concept here...

Nobody outside of functional programming understands monads. Nobody outside
of functional languages needs monads. What can be deduced from this?

-- 
                                                          - Warp

Post a reply to this message

On 14/03/2013 04:58 PM, Warp wrote:
> Nobody outside of functional programming understands monads. Nobody outside
> of functional languages needs monads. What can be deduced from this?

That nobody outside of functional programming realises that that class 
they just wrote is actually a slightly buggy implementation of a monad? ;-)

Post a reply to this message

On 13/03/2013 10:22 PM, Anthony D. Baye wrote:

> Is this something that could be handled with a pure virtual base class which
> defines those elements common to ALL monads and requires type-specific
> definitions from implementers?

Again, the problem is that we need to write a method which examines TWO 
objects which must be of THE SAME class. I haven't yet found a way to 
specify that in C# (although I suspect C++ can probably do it).

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> Again, the problem is that we need to write a method which examines TWO 
> objects which must be of THE SAME class.

I don't understand at all what that even means.

Start by explaining (briefly) what "examines" means in this context.

-- 
                                                          - Warp

Post a reply to this message

Am 14.03.2013 21:02, schrieb Orchid Win7 v1:
> On 14/03/2013 04:58 PM, Warp wrote:
>> Nobody outside of functional programming understands monads. Nobody
>> outside
>> of functional languages needs monads. What can be deduced from this?
>
> That nobody outside of functional programming realises that that class
> they just wrote is actually a slightly buggy implementation of a monad? ;-)

... or that that class they just wrote actually does all they'd need 
monads for in an OO rather than functional world? :-P

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> Orchid Win7 v1 <voi### [at] devnull> wrote:
> > Again, the problem is that we need to write a method which examines TWO
> > objects which must be of THE SAME class.
>
> I don't understand at all what that even means.
>
> Start by explaining (briefly) what "examines" means in this context.
>
> --
>                                                           - Warp

http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background/2704795#
2704795

Still trying to wrap my head around it.

Regards,
A.D.B.

Post a reply to this message

Anthony D. Baye <Sha### [at] spamnomorehotmailcom> wrote:
>
http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background/2704795#
> 2704795

> Still trying to wrap my head around it.

It almost looks like it's describing inheritance. What is

"First, what is an "amplifier of types"? By that I mean some system
which lets you take a type and turn it into a more special type. For
example, in C# consider Nullable<T>. This is an amplifier of types. It
lets you take a type, say int, and add a new capability to that type,
namely, that now it can be null when it couldn't before."

other than inheritance? The next paragraphs also seem to be talking
about inheritance.

Of course the text then proceeds into blabbering about something that's
hard to understand and seems quite inconsequential. Something about
binding (which sounds like dynamic binding in inheritance, but apparently
isn't?)

-- 
                                                          - Warp

Post a reply to this message

On 14/03/2013 08:24 PM, Warp wrote:
> Orchid Win7 v1<voi### [at] devnull>  wrote:
>> Again, the problem is that we need to write a method which examines TWO
>> objects which must be of THE SAME class.
>
> I don't understand at all what that even means.
>
> Start by explaining (briefly) what "examines" means in this context.

Consider another example: Let's say you want to do something like

   public abstract class Tree
   {
     ...
     public abstract Tree Union(Tree other);
     ...
   }

So we can now write SplayTree, HeapTree, SearchTree, etc as subclasses 
of Tree. But the thing is... you can only Union() two trees together if 
they are THE SAME TYPE of tree. So you can take the union of two 
SplayTrees, or the union of two HeapTrees, but NOT the union of a 
SplayTree and a HeapTree.

But the type signature above does not express this constraint. It says 
that you can union *any* two objects so long as they are both Trees - 
which is wrong.

That's the basic problem with writing a monad interface in C# (or Java, 
for that matter). You could do a run-time type check and throw an 
exception if the types don't match, of course. But I haven't yet figured 
out how to enforce the constraint at compile-time.

(Having asked some questions on stack overflow, it appears it might 
actually be possible in C# though... I'll give it a go tomorrow.)

Post a reply to this message

Am 14.03.2013 22:20, schrieb Anthony D. Baye:

>
http://stackoverflow.com/questions/2704652/monad-in-plain-english-for-the-oop-programmer-with-no-fp-background/2704795#
> 2704795

I guess this one about wraps it up nicely (emphasis added):

--------------------------------
Monads are typically used to solve problems like:

     * I need to make new capabilities for this type and still combine 
old functions on this type to use the new capabilities.
     * I need to capture a bunch of operations on types and represent 
those operations as composable objects, building up larger and larger 
compositions until I have just the right series of operations 
represented, and then I need to start getting results out of the thing
     * I NEED TO REPRESENT SIDE-EFFECTING OPERATIONS CLEANLY IN A 
LANGUAGE THAT HATES SIDE EFFECTS

(Note that these are basically three ways of saying the same thing.)
--------------------------------

With the whole OO concept being /centered/ around operations with 
side-effects (namely modifying the object's internal state), this boils 
down to saying that monads are NOT NEEDED in an OO language. (Or, in 
other words, that monads do something that is already inherent in the OO 
concept anyway.)

I think it might also be fair to say that monads are a way to express 
certain OO ideas in functional languages.

Post a reply to this message

Am 14.03.2013 23:39, schrieb Orchid Win7 v1:
> On 14/03/2013 08:24 PM, Warp wrote:
>> Orchid Win7 v1<voi### [at] devnull>  wrote:
>>> Again, the problem is that we need to write a method which examines TWO
>>> objects which must be of THE SAME class.
>>
>> I don't understand at all what that even means.
>>
>> Start by explaining (briefly) what "examines" means in this context.
>
> Consider another example: Let's say you want to do something like
>
>    public abstract class Tree
>    {
>      ...
>      public abstract Tree Union(Tree other);
>      ...
>    }
>
> So we can now write SplayTree, HeapTree, SearchTree, etc as subclasses
> of Tree. But the thing is... you can only Union() two trees together if
> they are THE SAME TYPE of tree. So you can take the union of two
> SplayTrees, or the union of two HeapTrees, but NOT the union of a
> SplayTree and a HeapTree.

Well, this can easily be solved by making Union non-abstract and having 
it call more primitive abstract functions; e.g (using pseudocode as I 
currently don't have C# syntax memorized):

   public abstract class Tree
   {

     public abstract Tree copy();
     public abstract Iterator<Leaf> leaves();
     public abstract void addLeaf(Leaf l);

     public final Tree Union(Tree other)
     {
       Tree newTree = this.copy();
       foreach(Leaf i in other.leaves())
         newTree.addLeaf(i);
     }
   }

There. Problem solved.

Note that in OO languages it is customary to use non-lazy evaluation 
(because objects may change, so lazy evaluation is prone for effects 
that OO programmers don't expect), so there's nothing conceptually wrong 
with copying the leaves rather than creating some "meta-tree" that 
provides tree-like operations on a compound of two tree objects.

Post a reply to this message

>> So we can now write SplayTree, HeapTree, SearchTree, etc as subclasses
>> of Tree. But the thing is... you can only Union() two trees together if
>> they are THE SAME TYPE of tree. So you can take the union of two
>> SplayTrees, or the union of two HeapTrees, but NOT the union of a
>> SplayTree and a HeapTree.
>
> Well, this can easily be solved by making Union non-abstract and having
> it call more primitive abstract functions; e.g (using pseudocode as I
> currently don't have C# syntax memorized):
>
> public abstract class Tree
> {
>
> public abstract Tree copy();
> public abstract Iterator<Leaf> leaves();
> public abstract void addLeaf(Leaf l);
>
> public final Tree Union(Tree other)
> {
> Tree newTree = this.copy();
> foreach(Leaf i in other.leaves())
> newTree.addLeaf(i);
> }
> }
>
> There. Problem solved.

Note that taking the union of (say) two heap trees is a O(log N) 
operation, whereas what you just wrote is O(N).

You can, of course, NOT write an abstract interface, and just write a 
concrete Union() method [with a different type signature] for each 
concrete Tree class. That works just fine. [But now you can't write code 
that works over any Tree type and expect to do unions.]

But anyway. The example illustrates the problem. Taking the Bind() of 
two different monads isn't even *defined*. There's no sensible answer. 
So until I can find a solution to that...

Post a reply to this message

On 13/03/2013 09:30 PM, Orchid Win7 v1 wrote:
> OK, so just for giggles, I tried to implement monads in C#.
>
> The short version: It appears that I can create a class with forms a
> monad, however it appears to be impossible to define the concept of
> "being a monad" such that you can write code which polymorphically works
> for any monad.

It appears I missed the elephant in the room. Apparently C# already 
*has* several classes which form monads, and even a special monad 
comprehension syntax for dealing with them.

Consider the following Haskell parser:

   identifier :: Parser String
   identifier = do
     leading  <- many space
     first    <- letter
     rest     <- many alphanum
     trailing <- many space
     return ([first] ++ rest)

Now consider the following C# LINQ query:

   Parser<string> identifier =
     from leading in Parse.Whitespace.Many()
     from first in Parse.Letter.Once()
     from rest in Parse.LetterOrDigit.Many()
     from trailing in Parse.Whitespace.Many()
     select new string(first.Concat(rest).ToArray());

Notice any similarity?

C# *already* has monads. The designers of LINQ even explicitly mention 
Haskell and monads as influencing their design.

So much for "only functional programmers understand monads and only 
functional programmers need monads"... :-P Monads are in fact one of the 
star features of a highly commercially successful programming platform.

(Although I'll admit LINQ is definitely tailored more towards 
*container* monads rather than being a general monad framework.)

I notice in passing that there is no "interface" which describes all the 
methods you have to implement to make a monad. (Or to make something 
that LINQ will work on.) Rather, it uses a strange system of "extension 
methods" - a very un-OO concept, if you look it up. But anyway, LINQ 
queries let you easily write monadic expressions without drowning in a 
sea of lambda functions.

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> It almost looks like it's describing inheritance. What is

> "First, what is an "amplifier of types"? By that I mean some system
> which lets you take a type and turn it into a more special type. For
> example, in C# consider Nullable<T>. This is an amplifier of types. It
> lets you take a type, say int, and add a new capability to that type,
> namely, that now it can be null when it couldn't before."

> other than inheritance? The next paragraphs also seem to be talking
> about inheritance.

> Of course the text then proceeds into blabbering about something that's
> hard to understand and seems quite inconsequential. Something about
> binding (which sounds like dynamic binding in inheritance, but apparently
> isn't?)

Still waiting for an answer to this...

-- 
                                                          - Warp

Post a reply to this message

>> It almost looks like it's describing inheritance. What is
>
>> "First, what is an "amplifier of types"? By that I mean some system
>> which lets you take a type and turn it into a more special type. For
>> example, in C# consider Nullable<T>. This is an amplifier of types. It
>> lets you take a type, say int, and add a new capability to that type,
>> namely, that now it can be null when it couldn't before."
>
>> other than inheritance? The next paragraphs also seem to be talking
>> about inheritance.
>
>> Of course the text then proceeds into blabbering about something that's
>> hard to understand and seems quite inconsequential. Something about
>> binding (which sounds like dynamic binding in inheritance, but apparently
>> isn't?)
>
> Still waiting for an answer to this...

OK, so now I'm back from London, let's take a stab at this...

The originally quoted answer doesn't make a huge amount of sense to me. 
I mean, I see where the guy is trying to go, but it's not a great metaphor.

Let's say you have a Customer type. Using this, you can construct a 
List<Customer> type, which extends Customer with the ability to have 
multiple values. Similarly, Parser<Customer> extends the Customer type 
with the ability to read a customer from a string.

Except that, really, that's a rather odd way of looking at things. I 
mean, a list of customers isn't really much like a customer at all - 
it's a list! And a parser of customers isn't a customer either; it's a 
thing that might produce a customer.

The "binding" refers to binding the result of a parser (or whatever) to 
a function. In other words, you run the parser, and pass its result 
through a function to generate the final result. Really, a monad is 
simply a specific way of chaining operations together; nothing more 
complicated than that.

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> Really, a monad is 
> simply a specific way of chaining operations together; nothing more 
> complicated than that.

And this is somehow different from just a regular function somehow?

-- 
                                                          - Warp

Post a reply to this message

On 01/04/2013 04:12 PM, Warp wrote:
> Orchid Win7 v1<voi### [at] devnull>  wrote:
>> Really, a monad is
>> simply a specific way of chaining operations together; nothing more
>> complicated than that.
>
> And this is somehow different from just a regular function somehow?

Well, yeah, that's the crux of the matter.

In a pure language like Haskell, a *function* takes several inputs and 
produces an output, and that's all it's allowed to do. If you want to do 
something more complicated, you represent it as a monad.

Now, if you're working in an OO language, then you automatically have 
access to facilities like I/O, global variables, exception handling and 
so on. So you don't need a monad to represent these things.

But now suppose that you want some facility that the OO framework 
doesn't natively support. Whether it's non-deterministic computation or 
backtracking or partial failure or atomic transactions or whatever... A 
monad is one possible way of dealing with these things.

Post a reply to this message

On 28/03/2013 01:04 PM, Orchid Win7 v1 wrote:
> But anyway, LINQ
> queries let you easily write monadic expressions without drowning in a
> sea of lambda functions.

You'll be unsurprised to learn that I am currently about 40% of the way 
through implementing Parsec in C#. It turns out to be reasonably easy, 
although there are a few gotchas. (E.g., there is no C# function which 
both inserts an element into a list *and* returns the list. Which is 
annoying, since it seems you can't call void-functions from LINQ...)

Post a reply to this message

> You'll be unsurprised to learn that I am currently about 40% of the way
> through implementing Parsec in C#. It turns out to be reasonably easy,
> although there are a few gotchas. (E.g., there is no C# function which
> both inserts an element into a list *and* returns the list. Which is
> annoying, since it seems you can't call void-functions from LINQ...)

It will be interesting to compare the speed with your original...

Post a reply to this message

On 08/04/2013 09:02 AM, scott wrote:
>> You'll be unsurprised to learn that I am currently about 40% of the way
>> through implementing Parsec in C#.
>
> It will be interesting to compare the speed with your original...

For most parsing tasks, speed isn't really an issue. Usually you use 
parsers to parse human-written text, which is typically small enough 
that the time spent parsing is negligible compared to the time spent on 
subsequent processing.

(If you wanted to parse a 3GB XML file, you wouldn't use Parsec. You'd 
use one of the various XML-specific libraries which are tuned to do that 
specific job very efficiently.)

That said, I'm not tuning my C# code for speed at all, and I don't 
expect it to be particularly fast. Then again, Parsec defaults to using 
Haskell strings, which are very inefficient... It looks like being a 
tortoise race.

Post a reply to this message

> For most parsing tasks, speed isn't really an issue. Usually you use
> parsers to parse human-written text, which is typically small enough
> that the time spent parsing is negligible compared to the time spent on
> subsequent processing.

I don't know a great deal about parsers (the most I've done is made one 
to calculate very simple sums, like (5+4)/2) but AIUI things like POV 
first convert the human readable text to binary symbols (removing any 
unnecessary formatting) and then parse the binary symbols rather than 
the raw text. IDK which part typically takes longer (I guess the first 
part as that involves a lot of string searching), but the time POV 
spends "parsing" even a medium-sized scene isn't trivial.

Saying that if you're writing something to do single-line equations then 
you probably don't need to worry :-) I thought it would just be an 
interesting real-world example if you've coded the same algorithm in 
both Haskell and C# to see the difference.

Post a reply to this message

On 09/04/2013 08:14 AM, scott wrote:
>> For most parsing tasks, speed isn't really an issue. Usually you use
>> parsers to parse human-written text, which is typically small enough
>> that the time spent parsing is negligible compared to the time spent on
>> subsequent processing.
>
> I don't know a great deal about parsers (the most I've done is made one
> to calculate very simple sums, like (5+4)/2) but AIUI things like POV
> first convert the human readable text to binary symbols (removing any
> unnecessary formatting) and then parse the binary symbols rather than
> the raw text.

In other words, "lexing" (AKA "tokenising") followed by "parsing".

> IDK which part typically takes longer (I guess the first
> part as that involves a lot of string searching), but the time POV
> spends "parsing" even a medium-sized scene isn't trivial.

That's because
1) The "parsing" time includes the time taken to expand macros, because 
these work at the token level rather than some higher-level abstraction.
2) The "big" scenes are ones which include huge meshes. These 
machine-generated constructs tend to be quite large.

> Saying that if you're writing something to do single-line equations then
> you probably don't need to worry :-) I thought it would just be an
> interesting real-world example if you've coded the same algorithm in
> both Haskell and C# to see the difference.

Yeah, why not...

Post a reply to this message

scott <sco### [at] scottcom> wrote:
> I don't know a great deal about parsers (the most I've done is made one 
> to calculate very simple sums, like (5+4)/2) but AIUI things like POV 
> first convert the human readable text to binary symbols (removing any 
> unnecessary formatting) and then parse the binary symbols rather than 
> the raw text.

POV-Ray doesn't convert the SDL file into any internal binary format.
It just parses the text and creates objects as needed.

Fast parsing (regardless of whether you are interpreting as you parse or
whether you are byte-compiling it) is a difficult problem, one I have some
experience with.

The fastest possible way of parsing a text file with human-readable syntax
is to load it into an array in memory (if the file is exceedingly large
you'll have to do it in sections, but that shouldn't slow it down in any
significant way) and then parse it in-place (ie. without pulling out any
parts of it or creating new objects just to parse the thing) in a linear
fashion (ie. you traverse the array from beginning to end, without ever
going back.)

It is possible to do this kind of parsing without any kind of recursion,
but it becomes a bit complicated. Basically you need a state machine (which
has been generated at compile time into your program), and usually this
means generated code. (I suppose you could write a state machine by hand,
but it quickly becomes complicated, especially if the syntax of the thing
you are parsing is complex.)

The easiest way of writing an efficient parser by hand is to implement
a recursive descent parser (which, as said, parses the input in-place
from the array where it has been read to.) A RDP allows parsing any amount
of nested blocks in the input syntax (eg. parentheses or other types of
nested blocks) at any nesting depth, without ever having to go back in the
input (ie. just traversing the input from beginning to end once.)

What you do with the parsed information depends on what you want, but eg.
byte-compiling it into a stack-based bytecode (that can be later interpreted
in a very efficient manner) is very easy with a RDP. You could, of course,
just interpret the input directly.

-- 
                                                          - Warp

Post a reply to this message

>> I don't know a great deal about parsers (the most I've done is made one
>> to calculate very simple sums, like (5+4)/2) but AIUI things like POV
>> first convert the human readable text to binary symbols (removing any
>> unnecessary formatting) and then parse the binary symbols rather than
>> the raw text.
>
> POV-Ray doesn't convert the SDL file into any internal binary format.
> It just parses the text and creates objects as needed.

The existence of tokenize.cpp in the source made me think otherwise. 
What does this file do then?

Post a reply to this message

On 09/04/2013 02:34 PM, Warp wrote:
> The fastest possible way of parsing a text file with human-readable syntax
> is to load it into an array in memory (if the file is exceedingly large
> you'll have to do it in sections, but that shouldn't slow it down in any
> significant way) and then parse it in-place (ie. without pulling out any
> parts of it or creating new objects just to parse the thing) in a linear
> fashion (ie. you traverse the array from beginning to end, without ever
> going back.)
>
> It is possible to do this kind of parsing without any kind of recursion,
> but it becomes a bit complicated. Basically you need a state machine (which
> has been generated at compile time into your program), and usually this
> means generated code. (I suppose you could write a state machine by hand,
> but it quickly becomes complicated, especially if the syntax of the thing
> you are parsing is complex.)

Interestingly, if your parser is a monad, then you can never transform 
it into a finite state machine. Monads are just "too flexible" to permit 
this.

To be concrete: I can write a single Parsec parser which parses a file 
consisting of a BNF grammar specification followed by text written in 
that grammar. In other words, a parser which dynamically constructs a 
new parser and then runs it. Obviously there is no hope of statically 
optimising such a thing.

In Haskell we use monads to perform I/O, and for that task this level of 
flexibility is exactly what is wanted. We *want* programs to change 
their behaviour depending the input they receive. But for the problem of 
parsing a fixed grammar, that's actually a little bit *too* flexible. 
Sometimes we would like something a bit less powerful, because often 
less is more with these things. (In this case, less expressive power 
equals more optimisation capabilities.)

The problem with monads is that the bind operation feeds the result of 
one step into some arbitrary Turing-complete code block which then 
generates the next parser to run. This Turing-completeness is the source 
of the trouble; it means you can't statically analyse what the parser is 
going to try to do (c.f. Rice's theorem).

There are alternatives, however. In particular, instead of using a monad 
to do parsing, you can use something called an "applicative functor". 
(No, I'm not kidding. That's what they call it.)

Every monad is also an applicative functor. However, not all applicative 
functors are also monads. For the purpose of parsing, it's the ones that 
aren't monads which are interesting.

A few definitions. In Haskell terms, a "functor" is basically anything 
that has a Map() function. You'll recall that Map() takes a list and a 
function, and applies that function to every element of the list, 
resulting in a new list. Well, in a slightly mind-binding kind of way, 
and I/O operation is *also* a functor, because you can take (say) an I/O 
operation that returns a byte, and Map() a function from bytes to 
characters over it, resulting in a new I/O operation that returns a 
character. And, indeed, *every* monad is also a functor in this way.

So much for functors. If you have something that's a functor, and all 
you know about it is "it's a functor", then that lets you Map() it, and 
that's all you can do. This isn't terribly interesting on its own.

Now, an *applicative* functor has two additional abilities. One is that 
it has a function like Inject(), which puts a value "into" the functor. 
The other is a function that I'm going to call Apply(). It's a bit like 
Map(). But whereas Map() takes a function and a functor containing a 
value [or values], Apply() takes a functor of functions and a functor of 
values.

For example, if Parser<X> is a parser that parses an X, then

   public Parser<T2> Apply(Parser<Func<T1, T2>> p1, Parser<T1> p2)

First p1 is run, then p2 is run, then the function returned by p1 is 
executed with the result from p2 as its argument. Whatever it returns, 
the composite parser returns.

My word, that seems mighty complicated. And why would you want a parser 
that returns a function anyway?

Well, Map() lets you apply a function to *one* argument. But what if you 
have (say) a 4-argument function, and you want to run 4 parsers to 
generate each of the inputs? Well, you can do

   Map(f, p1)

That partially applies our 4-argument function "f" to the first 
argument... But now we've got a parser that returns a 3-argument 
function. We're stuck; Map() wants a function, not a parser that returns 
a function.

Now if our parser forms a monad, this is where we invoke Bind() to chain 
in the next step. But that's actually overkill; all we want is to be 
able to take a function from a parser. And that's all Apply() does. So 
we can do this:

   temp1 = Apply(f, p1);
   temp2 = Apply(temp1, p2);
   temp3 = Apply(temp2, p3);
   temp4 = Apply(temp3, p4);

Now temp4 is a parser that parses 4 things and then applies f to the 
results. In Haskell, it's not called Apply(), it's called "<*>", which 
is an infix operator, so we can just write

   temp4 = pure f <*> p1 <*> p2 <*> p3 <*> f4

which looks almost the same as

   result = f v1 v2 v3 v4

but with a bunch of <*> operators inserted between arguments. There's 
also a "<*" operator, which allows us to run a parser and skip its output:

   parser = pure f <*> arg1_parser <*> arg2_parser <* separator_parser 
<*> arg3_parser

This, by itself, doesn't allow us to parse alternatives. (But then, 
neither does a monad by itself.) We need extra combinators to handle 
that, and a few other things which are specific to parsers.

Using this framework, the parser can be represented not as an opaque 
block of Turing-complete code, but as a transparent data structure which 
can be operated on by other functions. This means you can do run-time or 
compile-time optimisations on it. In particular, you could write a 
function that takes a parser and generates a finite state machine from it.

The *other* possibility is to use something called an "arrow", but 
that's for another post...

Post a reply to this message

I'm assuming that implementing a recursive descent parser ought to be
relatively simple in Haskell, given how recursive in nature functional
programming is. (Of course this also assumes that it's easy and efficient
in Haskell to have the input as a byte array, and it's efficient to read
said array byte by byte, without much copying things around.)

An interesting thing about this type of parsing, though, is how to parse
things like numeric literals (especially if they are not integers) or
UTF-8 encoded characters.

Most languages have some kind of standard functionality for parsing the
former. The only thing one has to do is to detect when such a literal is
appearing in the input, and then call said function. (The C/C++ standard
libraries in particular offer functions to parse numeric values that are
in ASCII format in-place, without having to first copy them anywhere,
which is a major help when writing such efficient parsers.)

Parsing UTF-8 encoded characters is a bit trickier, especially if the
language does not offer standard utility functions for that purpose.
The most efficient way of doing that is to, basically, write a small
state machine that reads the input byte by byte until a character not
in a valid sequence appears, and returns how many bytes the found name
consists of. (During this parsing, or afterwards, you can then do with
those characters whatever you need to.)

(Remember that we are writing an extremely *efficient* parser here. That
means no copying characters around and parsing them separately. They have
to be parsed in-place, where they appear in the byte array.)

-- 
                                                          - Warp

Post a reply to this message

On 20/04/2013 10:31 PM, Warp wrote:
> I'm assuming that implementing a recursive descent parser ought to be
> relatively simple in Haskell, given how recursive in nature functional
> programming is.

Indeed.

> (Of course this also assumes that it's easy and efficient
> in Haskell to have the input as a byte array, and it's efficient to read
> said array byte by byte, without much copying things around.)

*Reading* from an array is easy. You only need to copy things if they 
change, and reading from something doesn't change it.

> Most languages have some kind of standard functionality for parsing the
> former.

The trouble starts when the literals you're trying to parse don't match 
the format that the standard function expects. (E.g., some languages 
allow "+7" as a valid integer, and others don't.)

> Parsing UTF-8 encoded characters is a bit trickier, especially if the
> language does not offer standard utility functions for that purpose.

Haskell provides a way to read from a file, decoding UTF-8 on the fly. 
I'm not sure how it's implemented internally though. You end up with a 
packed array of characters which you can iterate over.

> (Remember that we are writing an extremely *efficient* parser here. That
> means no copying characters around and parsing them separately. They have
> to be parsed in-place, where they appear in the byte array.)

You're probably going to struggle to get this level of efficiency from a 
programming language that uses garbage collection. Even if all the data 
is in a flat array, the array might get copied from place to place 
occasionally by the garbage collector.

(Having said that, I'm not sure whether or not Haskell's GC does any 
special handling for "large" objects. Some GCs handle these specially, 
which usually means storing them in a separate area that doesn't get 
scanned as often, so they don't need to be copied as much.)

Post a reply to this message

On 24/04/2013 08:46 AM, Orchid Win7 v1 wrote:
> Having said that, I'm not sure whether or not Haskell's GC does any
> special handling for "large" objects.

It does. It takes various steps to try to avoid copying objects larger 
than about 4KB.

Post a reply to this message