Re: [O] GSoC 2012 -- Elisp backend for Ragel

[Aurélien Aptel]

On Tue, Mar 27, 2012 at 11:22 PM, Achim Gratz <address@hidden> wrote:
> It needs yet another tool to fully build org-mode from scratch, which
> needs to be installed, bug-free and configured correctly.  Right now all
> one really needs to have to build org-mode is a working Emacs (even make
> is optional).

Ragel is written in C++ and has no dependency.

* every major platform has a C++ compiler
* ragel input along with generated code can be tracked in the repo
* the generated code is portable since it's elisp (doesn't need to be
regenerated on different platforms)
* the parser is a confined part of org-mode

I don't think this is a problem.

>>>  3) FSM implementation into code is inherently very simple anyway
>>
>> Well I've never done it for big language but I did not find it that
>> easy. Mistakes are easily made e.g. you end up accepting more thing
>> that the language does in order to simplify the code, etc.
>
> Which is just as easily done by specifying the syntax incorrectly.

I think the fix will be shorter and simpler in the syntax because it's
easier to reason on an abstract definition when it comes to language.
When you're neck-deep in your handwritten implementation trying to
figure what you did wrong, it can take a long time.

> No, you can (for a suitably restricted set of languages) formally proof
> that the implementation and the specification is identical for any
> input.

How would you do that programmatically?

> The assumption that an FSM running in ELisp is faster than a bunch of
> regexp has not been actually tested or has it?

I haven't tested anything yet.
If I remember correctly, the emacs regex API doesn't provide a way to
compile patterns and thus have to be compiled at each call.
Also the underlying FSM implementation uses NFA which can lead to a
exponential complexity in time [1] for certain patterns.

1: http://swtch.com/~rsc/regexp/regexp1.html