Flat: Formal LAnguage Translation

[Peter Kelly <pm...@apache.org>]

For the past year or so I’ve been playing around with the idea of developing a programming language specifically for expressing translations between different formal languages (in the programming language sense, not natural languages).

A document format used for word processing/other office-style applications can be considered a formal language, where it is possible to specify its structure in some formal notation, such as BNF. ODF and OOXML both fit this criteria, as they use XML and their tree structure is defined by the RelaxNG schemas that are part of the specifications - there are copies of these in the ‘schemas’ directory in the Corinthia repository. The zip-packaging complicates this a little, but it would be feasible to find a way to express this formally in terms of what files are required in a package, how they relate to one another, and what schema each must conform to.

I believe that ODF, OOXML, and HTML are not the only file formats we should consider supporting in Corinthia - there are numerous others, including:

- Markdown [1] / MultiMarkdown [2] / CommonMark [3]
- reStruturedText [4] (popular in the Python world)
- AsciiDoc [5]
- RTF [6]
- LaTeX [7]
- Various Wiki markup languages

All of these languages are difficult to parse manually, and really need to be tackled through the use of a parser generator or other language processing toolkit.

Let’s face it, C sucks for what we’re doing, as it’s too low level and we constantly have to take care of manual memory management, awkward string handling, and protecting against crashes that can so often arise due to NULL pointer dereferences, memory corruption, use-after-free and other bugs. The Objective C version of the code was better, but still not ideal, and not cross platform.

One programming language I’ve been especially inspired by in some past work I’ve done is Stratego/XT [8]. It includes the following features:

- A grammar specification language (SDF), which can be used as input to parser generators, which will automatically construct abstract syntax trees, expressed in the ATerm format (which is similar to Lisp’s S-expressions).

- The Stratego language, which allows specification of rewrite rules based on pattern matching, in a notation similar to that used to express the denotational semantics of programming languages. The language also includes the ability to express strategies for how rewrite rules should be applied, such as pre-order or post-order traversal of the syntax tree, repeated attempts at rule application, and so forth; these strategies can be composed in arbitrary ways. The language is also a powerful functional programming language in it’s own right, and has many other features for analysis of syntax trees to determine things like variable scopes.

- A pretty-printing language for concisely describing how an abstract syntax tree can be turned back into a text file in a given language, for later compilation or editing.

Sadly, Stratego/XT itself seems to have fallen into a state of disrepair, and many of the links on the website are broken (but can probably be dug up with a bit of work). Their publications page (http://strategoxt.org/Stratego/StrategoPublications <http://strategoxt.org/Stratego/StrategoPublications>) has plenty of good info though. They’ve now moved on to what is called the Spoofax Language Workbench which, even more sadly, depends on both Java and Eclipse. I’m sure it’s possible to get the core language operating standalone, but I haven’t looked into it.

Anyway, Stratego fundamentally changed the way I thought about the process of writing compilers, and opened my eyes to a whole world of possibilities in program transformation. I've found it useful in several different contexts, such as instrumenting code for performance measurement, and detecting plagiarism in student code submissions for CS assignments.

Another important development in the last decade or so has been Parsing Expression Grammars (PEGs), and packrat parsing [10]. The two key papers you want to read on these are [11] and [12], although Bryan Ford and others have published many other papers on the technique. PEGs are context-aware grammars that combine both lexical and syntactic analysis (unlike the separation seen in flex & bison). They are readily composable, and avoid many of the ambiguity problems inherent with context-free grammars, such as the “dangling else” problem. A good example of a PEG-based parser implementation is Grako [13], which is implemented in Python.

Having seen these various things, and thinking about how to make the process of writing document format translators easier, I’m of the view that it would be immensely advantageous for us to have these concepts combined into a single language/runtime library. In principle, this could be developed independently of Corinthia, but I think would be better done as part of the project as it’s something which we have a very direct application for, namely writing filters for the above-mentioned file formats, and possibly porting the OOXML filter and ODF filter across to as well. It’s also been several years since I’ve had a chance to sink my teeth into some real programming language research, and I’m keen to get back to my roots.

I’ve done about seven or eight prototypes so far, in both C and more recently Python - so far addressing only the parsing and syntax tree construction aspects, without any thought yet as to the language itself. I’m currently spending a lot of time with the famous “Dragon Book”, reviewing the chapters on parsing and syntax-directed translation, and implementing the algorithms described in the text to solidify my understanding of how they work. I can share the code if you’re interested, though right now it’s all completely undocumented and nowhere near ready for use by others, and you’ll probably find either the dragon book itself or other online tutorials to be more useful. I should emphasis that it’s all throwaway code, and I intend on doing a “proper” implementation from scratch within the Corinthia repository.

I’ve pretty much figured out what needs to be done for the parsing and syntax tree construction, and the next step is coming up with a suitable runtime representation, that can be used both directly from C code, and from the “Flat” language (whatever form it eventually takes), and potentially bindings to other languages like Python and JavaScript. What I envisage here is an approach in which all such data structures are immutable, structured using ATerms (which Stratego uses, and are like S-expressions), and have transformations expressed in a purely functional style, with Stratego-style pattern matching.

Our current runtime representation of data obtained from source files is XML, since this is what the currently-supported formats are based on. We could either stick with this, translating to and from the ATerm-style syntax where appropriate, or (and I would argue this is better), to use a common type system for all transformations. The advantage of the latter is that all transformations could be subject to type checking, which means the Flat compiler would statically guarantee that the output produced by e.g. a HTML to ODF translation fully conforms to the ODF schema, the same way that a C/Java compiler does type checking. This would allow us to have formally-verified translations between file formats.

The transformations would not necessarily have to use code generation; we could alternatively implement them via an interpreter. Both could be supported, with back-ends that output in C code, or bytecode that is understood by the interpreter. In either case, there will need to be runtime support consisting of a garbage collector and likely an exception handling mechanism; a debugger and a Python-style REPL interface would also be handy for development purposes.

As an example of the type of grammar I’m thinking of, see the following one for MultiMarkdown (but imagine it without the semantic actions, which are written in C):

https://github.com/fletcher/MultiMarkdown-4/blob/master/parser.leg <https://github.com/fletcher/MultiMarkdown-4/blob/master/parser.leg>

I still have a lot of reading to do on many topics, and I’ve been meaning to start discussing it here on the list for a long time but have yet to get around to it. Sorry for dumping so much stuff at once (and I realise it’s pretty heavy), but at least now we can start to get the discussion going about what we want in a transformation language, and how we can make the development of new filters easier.

[1] http://daringfireball.net/projects/markdown/syntax <http://daringfireball.net/projects/markdown/syntax>
[2] http://fletcherpenney.net/multimarkdown/ <http://fletcherpenney.net/multimarkdown/>
[3] http://commonmark.org <http://commonmark.org/>
[4] http://docutils.sourceforge.net/rst.html <http://docutils.sourceforge.net/rst.html>
[5] http://www.methods.co.nz/asciidoc/ <http://www.methods.co.nz/asciidoc/>
[6] http://www.microsoft.com/en-US/Download/details.aspx?id=10725 <http://www.microsoft.com/en-US/Download/details.aspx?id=10725>
[7] http://www.latex-project.org <http://www.latex-project.org/>
[8] http://strategoxt.org <http://strategoxt.org/>
[9] http://strategoxt.org/Spoofax/WebHome <http://strategoxt.org/Spoofax/WebHome>
[10] http://bford.info/packrat/ <http://bford.info/packrat/>
[11] http://bford.info/pub/lang/packrat-icfp02.pdf <http://bford.info/pub/lang/packrat-icfp02.pdf>
[12] http://bford.info/pub/lang/peg.pdf <http://bford.info/pub/lang/peg.pdf>
[13] https://pypi.python.org/pypi/grako/3.6.1 <https://pypi.python.org/pypi/grako/3.6.1>
[14] http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811 <http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811>

—
Dr Peter M. Kelly
pmkelly@apache.org

PGP key: http://www.kellypmk.net/pgp-key <http://www.kellypmk.net/pgp-key>
(fingerprint 5435 6718 59F0 DD1F BFA0 5E46 2523 BAA1 44AE 2966)

Re: Flat: Formal LAnguage Translation

[jan i <ja...@apache.org>]

Hi

I like the idea about formal language translation, it is commonly used
between
compilers (I used the principle years ago writing a basic->C cross
compiler).

However I have a feeling that the exceptions (maybe not the right word) in
OOXML and ODF
makes a formal language converter next to impossible. F.x. converting
tables from ODF to OOXML would be a piece of cake, but going from OOXML to
ODF you first need to detect if
it is a table at all or just styled paragraphs.

I do not want to sound negative, but I do see theoritical problems because
the formats can
be used in so many different ways (unlike the compiler case, where the
compiler itself is the
ultimate judge).

rgds
jan i

On Tuesday, June 16, 2015, Ian C <ia...@amham.net> wrote:

> Thanks Peter,
>
> On Tue, Jun 16, 2015 at 2:16 AM, Peter Kelly <pmkelly@apache.org
> <javascript:;>> wrote:
>
> > For the past year or so I’ve been playing around with the idea of
> > developing a programming language specifically for expressing
> translations
> > between different formal languages (in the programming language sense,
> not
> > natural languages).
> >
> > A document format used for word processing/other office-style
> applications
> > can be considered a formal language, where it is possible to specify its
> > structure in some formal notation, such as BNF. ODF and OOXML both fit
> this
> > criteria, as they use XML and their tree structure is defined by the
> > RelaxNG schemas that are part of the specifications - there are copies of
> > these in the ‘schemas’ directory in the Corinthia repository. The
> > zip-packaging complicates this a little, but it would be feasible to
> find a
> > way to express this formally in terms of what files are required in a
> > package, how they relate to one another, and what schema each must
> conform
> > to.
> >
> > I believe that ODF, OOXML, and HTML are not the only file formats we
> > should consider supporting in Corinthia - there are numerous others,
> > including:
> >
> > - Markdown [1] / MultiMarkdown [2] / CommonMark [3]
> > - reStruturedText [4] (popular in the Python world)
> > - AsciiDoc [5]
> > - RTF [6]
> > - LaTeX [7]
> > - Various Wiki markup languages
> >
> > All of these languages are difficult to parse manually, and really need
> to
> > be tackled through the use of a parser generator or other language
> > processing toolkit.
> >
> > Let’s face it, C sucks for what we’re doing, as it’s too low level and we
> > constantly have to take care of manual memory management, awkward string
> > handling, and protecting against crashes that can so often arise due to
> > NULL pointer dereferences, memory corruption, use-after-free and other
> > bugs. The Objective C version of the code was better, but still not
> ideal,
> > and not cross platform.
> >
> > One programming language I’ve been especially inspired by in some past
> > work I’ve done is Stratego/XT [8]. It includes the following features:
> >
> > - A grammar specification language (SDF), which can be used as input to
> > parser generators, which will automatically construct abstract syntax
> > trees, expressed in the ATerm format (which is similar to Lisp’s
> > S-expressions).
> >
> > - The Stratego language, which allows specification of rewrite rules
> based
> > on pattern matching, in a notation similar to that used to express the
> > denotational semantics of programming languages. The language also
> includes
> > the ability to express strategies for how rewrite rules should be
> applied,
> > such as pre-order or post-order traversal of the syntax tree, repeated
> > attempts at rule application, and so forth; these strategies can be
> > composed in arbitrary ways. The language is also a powerful functional
> > programming language in it’s own right, and has many other features for
> > analysis of syntax trees to determine things like variable scopes.
> >
> > - A pretty-printing language for concisely describing how an abstract
> > syntax tree can be turned back into a text file in a given language, for
> > later compilation or editing.
> >
> > Sadly, Stratego/XT itself seems to have fallen into a state of disrepair,
> > and many of the links on the website are broken (but can probably be dug
> up
> > with a bit of work). Their publications page (
> > http://strategoxt.org/Stratego/StrategoPublications <
> > http://strategoxt.org/Stratego/StrategoPublications>) has plenty of good
> > info though. They’ve now moved on to what is called the Spoofax Language
> > Workbench which, even more sadly, depends on both Java and Eclipse. I’m
> > sure it’s possible to get the core language operating standalone, but I
> > haven’t looked into it.
> >
> > Anyway, Stratego fundamentally changed the way I thought about the
> process
> > of writing compilers, and opened my eyes to a whole world of
> possibilities
> > in program transformation. I've found it useful in several different
> > contexts, such as instrumenting code for performance measurement, and
> > detecting plagiarism in student code submissions for CS assignments.
> >
> > Another important development in the last decade or so has been Parsing
> > Expression Grammars (PEGs), and packrat parsing [10]. The two key papers
> > you want to read on these are [11] and [12], although Bryan Ford and
> others
> > have published many other papers on the technique. PEGs are context-aware
> > grammars that combine both lexical and syntactic analysis (unlike the
> > separation seen in flex & bison). They are readily composable, and avoid
> > many of the ambiguity problems inherent with context-free grammars, such
> as
> > the “dangling else” problem. A good example of a PEG-based parser
> > implementation is Grako [13], which is implemented in Python.
> >
> > Having seen these various things, and thinking about how to make the
> > process of writing document format translators easier, I’m of the view
> that
> > it would be immensely advantageous for us to have these concepts combined
> > into a single language/runtime library. In principle, this could be
> > developed independently of Corinthia, but I think would be better done as
> > part of the project as it’s something which we have a very direct
> > application for, namely writing filters for the above-mentioned file
> > formats, and possibly porting the OOXML filter and ODF filter across to
> as
> > well. It’s also been several years since I’ve had a chance to sink my
> teeth
> > into some real programming language research, and I’m keen to get back to
> > my roots.
> >
> > I’ve done about seven or eight prototypes so far, in both C and more
> > recently Python - so far addressing only the parsing and syntax tree
> > construction aspects, without any thought yet as to the language itself.
> > I’m currently spending a lot of time with the famous “Dragon Book”,
> > reviewing the chapters on parsing and syntax-directed translation, and
> > implementing the algorithms described in the text to solidify my
> > understanding of how they work. I can share the code if you’re
> interested,
> > though right now it’s all completely undocumented and nowhere near ready
> > for use by others, and you’ll probably find either the dragon book itself
> > or other online tutorials to be more useful. I should emphasis that it’s
> > all throwaway code, and I intend on doing a “proper” implementation from
> > scratch within the Corinthia repository.
> >
> > I’ve pretty much figured out what needs to be done for the parsing and
> > syntax tree construction, and the next step is coming up with a suitable
> > runtime representation, that can be used both directly from C code, and
> > from the “Flat” language (whatever form it eventually takes), and
> > potentially bindings to other languages like Python and JavaScript. What
> I
> > envisage here is an approach in which all such data structures are
> > immutable, structured using ATerms (which Stratego uses, and are like
> > S-expressions), and have transformations expressed in a purely functional
> > style, with Stratego-style pattern matching.
> >
> > Our current runtime representation of data obtained from source files is
> > XML, since this is what the currently-supported formats are based on. We
> > could either stick with this, translating to and from the ATerm-style
> > syntax where appropriate, or (and I would argue this is better), to use a
> > common type system for all transformations. The advantage of the latter
> is
> > that all transformations could be subject to type checking, which means
> the
> > Flat compiler would statically guarantee that the output produced by
> e.g. a
> > HTML to ODF translation fully conforms to the ODF schema, the same way
> that
> > a C/Java compiler does type checking. This would allow us to have
> > formally-verified translations between file formats.
> >
> > The transformations would not necessarily have to use code generation; we
> > could alternatively implement them via an interpreter. Both could be
> > supported, with back-ends that output in C code, or bytecode that is
> > understood by the interpreter. In either case, there will need to be
> > runtime support consisting of a garbage collector and likely an exception
> > handling mechanism; a debugger and a Python-style REPL interface would
> also
> > be handy for development purposes.
> >
> > As an example of the type of grammar I’m thinking of, see the following
> > one for MultiMarkdown (but imagine it without the semantic actions, which
> > are written in C):
> >
> > https://github.com/fletcher/MultiMarkdown-4/blob/master/parser.leg <
> > https://github.com/fletcher/MultiMarkdown-4/blob/master/parser.leg>
> >
> > I still have a lot of reading to do on many topics, and I’ve been meaning
> > to start discussing it here on the list for a long time but have yet to
> get
> > around to it. Sorry for dumping so much stuff at once (and I realise it’s
> > pretty heavy), but at least now we can start to get the discussion going
> > about what we want in a transformation language, and how we can make the
> > development of new filters easier.
> >
>
> Head exploded now :-) Whilst a lot of the detail went over my head I have
> been working with ANTLR for the past few years and found 11 and 12
> interesting. But the heavy maths leaves me high and dry. Notionally though
> I do think we should/could express the mapping between elements in such a
> way that the translations could be generated, without missing cases. Or at
> least unknowingly missing cases.
>
> My work in my day job with the compiler I work on was the feeder for the
> tool I developed to track how much of a schema is used and how. Which seems
> to me to be very similar problem. Instead of just tracking we map or
> generate a new representation.
>
> >
> > [1] http://daringfireball.net/projects/markdown/syntax <
> > http://daringfireball.net/projects/markdown/syntax>
> > [2] http://fletcherpenney.net/multimarkdown/ <
> > http://fletcherpenney.net/multimarkdown/>
> > [3] http://commonmark.org <http://commonmark.org/>
> > [4] http://docutils.sourceforge.net/rst.html <
> > http://docutils.sourceforge.net/rst.html>
> > [5] http://www.methods.co.nz/asciidoc/ <
> http://www.methods.co.nz/asciidoc/
> > >
> > [6] http://www.microsoft.com/en-US/Download/details.aspx?id=10725 <
> > http://www.microsoft.com/en-US/Download/details.aspx?id=10725>
> > [7] http://www.latex-project.org <http://www.latex-project.org/>
> > [8] http://strategoxt.org <http://strategoxt.org/>
> > [9] http://strategoxt.org/Spoofax/WebHome <
> > http://strategoxt.org/Spoofax/WebHome>
> > [10] http://bford.info/packrat/ <http://bford.info/packrat/>
> > [11] http://bford.info/pub/lang/packrat-icfp02.pdf <
> > http://bford.info/pub/lang/packrat-icfp02.pdf>
> > [12] http://bford.info/pub/lang/peg.pdf <
> > http://bford.info/pub/lang/peg.pdf>
> > [13] https://pypi.python.org/pypi/grako/3.6.1 <
> > https://pypi.python.org/pypi/grako/3.6.1>
> > [14]
> >
> http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
> > <
> >
> http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
> > >
> >
> > —
> > Dr Peter M. Kelly
> > pmkelly@apache.org <javascript:;>
> >
> > PGP key: http://www.kellypmk.net/pgp-key <
> http://www.kellypmk.net/pgp-key>
> > (fingerprint 5435 6718 59F0 DD1F BFA0 5E46 2523 BAA1 44AE 2966)
> >
> >
> --
> Cheers,
>
> Ian C
>


-- 
Sent from My iPad, sorry for any misspellings.

Re: Flat: Formal LAnguage Translation

[Ian C <ia...@amham.net>]

Thanks Peter,

On Tue, Jun 16, 2015 at 2:16 AM, Peter Kelly <pm...@apache.org> wrote:

> For the past year or so I’ve been playing around with the idea of
> developing a programming language specifically for expressing translations
> between different formal languages (in the programming language sense, not
> natural languages).
>
> A document format used for word processing/other office-style applications
> can be considered a formal language, where it is possible to specify its
> structure in some formal notation, such as BNF. ODF and OOXML both fit this
> criteria, as they use XML and their tree structure is defined by the
> RelaxNG schemas that are part of the specifications - there are copies of
> these in the ‘schemas’ directory in the Corinthia repository. The
> zip-packaging complicates this a little, but it would be feasible to find a
> way to express this formally in terms of what files are required in a
> package, how they relate to one another, and what schema each must conform
> to.
>
> I believe that ODF, OOXML, and HTML are not the only file formats we
> should consider supporting in Corinthia - there are numerous others,
> including:
>
> - Markdown [1] / MultiMarkdown [2] / CommonMark [3]
> - reStruturedText [4] (popular in the Python world)
> - AsciiDoc [5]
> - RTF [6]
> - LaTeX [7]
> - Various Wiki markup languages
>
> All of these languages are difficult to parse manually, and really need to
> be tackled through the use of a parser generator or other language
> processing toolkit.
>
> Let’s face it, C sucks for what we’re doing, as it’s too low level and we
> constantly have to take care of manual memory management, awkward string
> handling, and protecting against crashes that can so often arise due to
> NULL pointer dereferences, memory corruption, use-after-free and other
> bugs. The Objective C version of the code was better, but still not ideal,
> and not cross platform.
>
> One programming language I’ve been especially inspired by in some past
> work I’ve done is Stratego/XT [8]. It includes the following features:
>
> - A grammar specification language (SDF), which can be used as input to
> parser generators, which will automatically construct abstract syntax
> trees, expressed in the ATerm format (which is similar to Lisp’s
> S-expressions).
>
> - The Stratego language, which allows specification of rewrite rules based
> on pattern matching, in a notation similar to that used to express the
> denotational semantics of programming languages. The language also includes
> the ability to express strategies for how rewrite rules should be applied,
> such as pre-order or post-order traversal of the syntax tree, repeated
> attempts at rule application, and so forth; these strategies can be
> composed in arbitrary ways. The language is also a powerful functional
> programming language in it’s own right, and has many other features for
> analysis of syntax trees to determine things like variable scopes.
>
> - A pretty-printing language for concisely describing how an abstract
> syntax tree can be turned back into a text file in a given language, for
> later compilation or editing.
>
> Sadly, Stratego/XT itself seems to have fallen into a state of disrepair,
> and many of the links on the website are broken (but can probably be dug up
> with a bit of work). Their publications page (
> http://strategoxt.org/Stratego/StrategoPublications <
> http://strategoxt.org/Stratego/StrategoPublications>) has plenty of good
> info though. They’ve now moved on to what is called the Spoofax Language
> Workbench which, even more sadly, depends on both Java and Eclipse. I’m
> sure it’s possible to get the core language operating standalone, but I
> haven’t looked into it.
>
> Anyway, Stratego fundamentally changed the way I thought about the process
> of writing compilers, and opened my eyes to a whole world of possibilities
> in program transformation. I've found it useful in several different
> contexts, such as instrumenting code for performance measurement, and
> detecting plagiarism in student code submissions for CS assignments.
>
> Another important development in the last decade or so has been Parsing
> Expression Grammars (PEGs), and packrat parsing [10]. The two key papers
> you want to read on these are [11] and [12], although Bryan Ford and others
> have published many other papers on the technique. PEGs are context-aware
> grammars that combine both lexical and syntactic analysis (unlike the
> separation seen in flex & bison). They are readily composable, and avoid
> many of the ambiguity problems inherent with context-free grammars, such as
> the “dangling else” problem. A good example of a PEG-based parser
> implementation is Grako [13], which is implemented in Python.
>
> Having seen these various things, and thinking about how to make the
> process of writing document format translators easier, I’m of the view that
> it would be immensely advantageous for us to have these concepts combined
> into a single language/runtime library. In principle, this could be
> developed independently of Corinthia, but I think would be better done as
> part of the project as it’s something which we have a very direct
> application for, namely writing filters for the above-mentioned file
> formats, and possibly porting the OOXML filter and ODF filter across to as
> well. It’s also been several years since I’ve had a chance to sink my teeth
> into some real programming language research, and I’m keen to get back to
> my roots.
>
> I’ve done about seven or eight prototypes so far, in both C and more
> recently Python - so far addressing only the parsing and syntax tree
> construction aspects, without any thought yet as to the language itself.
> I’m currently spending a lot of time with the famous “Dragon Book”,
> reviewing the chapters on parsing and syntax-directed translation, and
> implementing the algorithms described in the text to solidify my
> understanding of how they work. I can share the code if you’re interested,
> though right now it’s all completely undocumented and nowhere near ready
> for use by others, and you’ll probably find either the dragon book itself
> or other online tutorials to be more useful. I should emphasis that it’s
> all throwaway code, and I intend on doing a “proper” implementation from
> scratch within the Corinthia repository.
>
> I’ve pretty much figured out what needs to be done for the parsing and
> syntax tree construction, and the next step is coming up with a suitable
> runtime representation, that can be used both directly from C code, and
> from the “Flat” language (whatever form it eventually takes), and
> potentially bindings to other languages like Python and JavaScript. What I
> envisage here is an approach in which all such data structures are
> immutable, structured using ATerms (which Stratego uses, and are like
> S-expressions), and have transformations expressed in a purely functional
> style, with Stratego-style pattern matching.
>
> Our current runtime representation of data obtained from source files is
> XML, since this is what the currently-supported formats are based on. We
> could either stick with this, translating to and from the ATerm-style
> syntax where appropriate, or (and I would argue this is better), to use a
> common type system for all transformations. The advantage of the latter is
> that all transformations could be subject to type checking, which means the
> Flat compiler would statically guarantee that the output produced by e.g. a
> HTML to ODF translation fully conforms to the ODF schema, the same way that
> a C/Java compiler does type checking. This would allow us to have
> formally-verified translations between file formats.
>
> The transformations would not necessarily have to use code generation; we
> could alternatively implement them via an interpreter. Both could be
> supported, with back-ends that output in C code, or bytecode that is
> understood by the interpreter. In either case, there will need to be
> runtime support consisting of a garbage collector and likely an exception
> handling mechanism; a debugger and a Python-style REPL interface would also
> be handy for development purposes.
>
> As an example of the type of grammar I’m thinking of, see the following
> one for MultiMarkdown (but imagine it without the semantic actions, which
> are written in C):
>
> https://github.com/fletcher/MultiMarkdown-4/blob/master/parser.leg <
> https://github.com/fletcher/MultiMarkdown-4/blob/master/parser.leg>
>
> I still have a lot of reading to do on many topics, and I’ve been meaning
> to start discussing it here on the list for a long time but have yet to get
> around to it. Sorry for dumping so much stuff at once (and I realise it’s
> pretty heavy), but at least now we can start to get the discussion going
> about what we want in a transformation language, and how we can make the
> development of new filters easier.
>

Head exploded now :-) Whilst a lot of the detail went over my head I have
been working with ANTLR for the past few years and found 11 and 12
interesting. But the heavy maths leaves me high and dry. Notionally though
I do think we should/could express the mapping between elements in such a
way that the translations could be generated, without missing cases. Or at
least unknowingly missing cases.

My work in my day job with the compiler I work on was the feeder for the
tool I developed to track how much of a schema is used and how. Which seems
to me to be very similar problem. Instead of just tracking we map or
generate a new representation.

>
> [1] http://daringfireball.net/projects/markdown/syntax <
> http://daringfireball.net/projects/markdown/syntax>
> [2] http://fletcherpenney.net/multimarkdown/ <
> http://fletcherpenney.net/multimarkdown/>
> [3] http://commonmark.org <http://commonmark.org/>
> [4] http://docutils.sourceforge.net/rst.html <
> http://docutils.sourceforge.net/rst.html>
> [5] http://www.methods.co.nz/asciidoc/ <http://www.methods.co.nz/asciidoc/
> >
> [6] http://www.microsoft.com/en-US/Download/details.aspx?id=10725 <
> http://www.microsoft.com/en-US/Download/details.aspx?id=10725>
> [7] http://www.latex-project.org <http://www.latex-project.org/>
> [8] http://strategoxt.org <http://strategoxt.org/>
> [9] http://strategoxt.org/Spoofax/WebHome <
> http://strategoxt.org/Spoofax/WebHome>
> [10] http://bford.info/packrat/ <http://bford.info/packrat/>
> [11] http://bford.info/pub/lang/packrat-icfp02.pdf <
> http://bford.info/pub/lang/packrat-icfp02.pdf>
> [12] http://bford.info/pub/lang/peg.pdf <
> http://bford.info/pub/lang/peg.pdf>
> [13] https://pypi.python.org/pypi/grako/3.6.1 <
> https://pypi.python.org/pypi/grako/3.6.1>
> [14]
> http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
> <
> http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
> >
>
> —
> Dr Peter M. Kelly
> pmkelly@apache.org
>
> PGP key: http://www.kellypmk.net/pgp-key <http://www.kellypmk.net/pgp-key>
> (fingerprint 5435 6718 59F0 DD1F BFA0 5E46 2523 BAA1 44AE 2966)
>
>
-- 
Cheers,

Ian C