In response to popular demand I have created a Spoofax project for LBNF, the grammar formalism of the BNFC project. The project contains an SDF3 definition for LBNF obtained by manually converting the LBNF grammar in LBNF, and a transformation from LBNF to SDF3.

The transformation is fairly straightforward since LBNF and SDF3 productions are similar. In particular, LBNF productions declare a constructor symbol, which is also needed in SDF3. The main distinction is the way that lists are specified. For example, the following LBNF productions

    Rule . Def ::= Label "." Cat "::=" [Item] ;
    []  . [Item] ::= ;
    (:) . [Item] ::= Item [Item] ;

translate to this SDF3 production:

    Def.Rule = [[Label] . [Cat] ::= [{Item " "}*]]

The transformation is probably somewhat rudimentary and ignores advanced features of LBNF. Yet the converter should be fairly robust, since it skips anything that it doesn't recognize. I have only tested it on the LBNF.cf file itself. More testing is needed. I will be happy to do some more work on the transformation if popular demand so requires.

Using LBNF to SDF3

To use the converter:

  • Check out the GitHub repository (https://github.com/MetaBorgCube/metaborg-lbnf) and import the project into your Eclipse with Spoofax.
  • Build the project.
  • Open a .cf file
  • Hit the 'Transform to SDF3' transformation in the 'Generation' menu
Read more

I have started writing a book about declarative language definition with the Spoofax Language Workbench. The first chapter about Getting Spoofax is done. The chapter explains how to get started for Eclipse newbies. In particular, Spoofax is now shipped as a complete Eclipse installation including JRE and the appropriate patches to the 'eclipse.ini' file, so that it should be easy to get started. In the next chapters I will be discussing the definition of a language using Spoofax from a user perspective.

The project is on GitHub and there's a website with a link to latest version:

http://declare-your-language.metaborg.org/

The book is a PDF in a format that is intended for reading on tablets (e.g. using the GoodReader app on iPad), i.e. big letters and no margins.

The source code of the book and of the accompanying Spoofax projects are all in the GitHub repository, so that it is easy to provide contributions, from typo fixes to entire chapters. Pull requests are welcome.

I'll update this post with news about new chapters.

Read more

After declarative syntax definition and declarative name binding, our next milestone on the road to a language designer's workbench is DynSem, a DSL for the specification of dynamic semantics. The DynSem prototype implementation is integrated as an experimental feature in the Spoofax Language Workbench (in the nightly build edition). In the coming months we will be further improving that integration and the documentation of DynSem. For now, there is this paper to be presented at the RTA 2015 conference:

DynSem: A DSL for Dynamic Semantics Specification by Vlad Vergu, Pierre Neron, and Eelco Visser. To appear in the proceedings of RTA 2015. Preprint PDF.

Abstract: The formal definition the semantics of a programming language and its implementation are typically separately defined, with the risk of divergence such that properties of the formal semantics are not properties of the implementation. In this paper, we present DynSem, a domain-specific language for the specification of the dynamic semantics of programming languages that aims at supporting both formal reasoning and efficient interpretation. DynSem supports the specification of the operational semantics of a language by means of statically typed conditional term reduction rules. DynSem supports concise specification of reduction rules by providing implicit build and match coercions based on reduction arrows and implicit term constructors. DynSem supports modular specification by adopting implicit propagation of semantic components from I-MSOS, which allows omitting propagation of components such as environments and stores from rules that do not affect those. DynSem supports the declaration of native operators for delegation of aspects of the semantics to an external definition or implementation. DynSem supports the definition of auxiliary meta-functions, which can be expressed using regular reduction rules and are subject to semantic component propagation. DynSem specifications are executable through automatic generation of a Java-based AST interpreter.

My slides for a talk on WebLab March 9, 2015 at the Research Seminar on Data Science, organized as part of the TU Delft events around Open Education Week 2015.

The recording of the talk is online as well.



rescalc.007

In 2012 we introduced the NaBL name binding language, which supports high-level declarative specification of name binding and scope rules of (domain-specific) programming languages. In 2013 we introduced an incremental execution engine for NaBL, which recomputes only the resolution of those names that have been affected by a change. While this provides a powerful tool for language designers, we had a hard time explaining exactly how it worked. We kept getting the question 'but what is the semantics of NaBL?' and we didn't have a good answer. Our attempts at formulating a high-level concise formalization of the semantics underlying the implementation proved that this was a non-trivial problem. In 2014 we finally managed to formulate a language-independent theory of name resolution in the form of a calculus that defines name resolution in a `scope graph'. The paper has been accepted for publication in the ESOP 2015 proceedings and is the ESOP nominee for the ETAPS 2015 best paper award:

A Theory of Name Resolution. Pierre Neron, Andrew P. Tolmach, Eelco Visser, Guido Wachsmuth. In Jan Vitek (editor), Programming Languages and Systems - 24th European Symposium on Programming, ESOP 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings. 2015

We have published an extended version of the paper as a technical report: A theory of name resolution with extended coverage and proofs (PDF)

Abstract: We describe a language-independent theory for name binding and resolution, suitable for programming languages with complex scoping rules including both lexical scoping and modules. We formulate name resolution as a two stage problem. First a language-independent scope graph is constructed using language-specific rules from an abstract syntax tree. Then references in the scope graph are resolved to corresponding declarations using a language-independent resolution process. We introduce a resolution calculus as a concise, declarative, and language-independent specification of name resolution. We develop a resolution algorithm that is sound and complete with respect to the calculus. Based on the resolution calculus we develop language-independent definitions of alpha-equivalence and rename refactoring. We illustrate the approach using a small example language with modules. In addition, we show how our approach provides a model for a range of name binding patterns in existing languages.

Update April 15, 2015: The paper won the EAPLS 2015 Best Paper Award. ETAPS Daily