Possible approaches to dialect selection

Question

In my language, I'd like to allow users to define custom 'dialects'. A dialect is, essentially, an object capable of parsing a source code in a particular grammar and returning a common high-level intermediate representation for it. The idea is to allow DSLs and interoperability with other languages through the same import system. (An important detail is that a dialect can only affect the whole file at once).

My question is, how could a dialect be specified for a file. (If you know any language that already implements a similar feature, please point me to it as well). One particular issue is, the dialect grammars could provide syntax conflicting with whatever is used for selecting the dialect (if, for instance, the dialect models an existent language).

^{// I already have some ideas, and will post them as an answers, but I'm still interested in a potential better approach}

Answer 1

Racket's languages as libraries¹ feature uses a #lang dialect-name header at the top of the file. These languages can operate either by macro-rewriting across the entire (LISP) program file, or as a reader macro that replaces the bytes-to-S-expression translation entirely. For example, #lang algol60 is supported out of the box, and processes the rest of the file as ALGOL; in theory this might conflict with the DSLs, but it doesn't seem to arise in practice as they can just ignore the first line.

Racket envisaged a series of layered teaching dialects inspired by SP/k, but SP/k did not provide any way to specify the subset in use. In the Racket model, the student would specify the dialect in use at the top of the file, and move through different headers as they progressed. Much more distinct dialects are also enabled by Racket's system.

¹_{Languages as Libraries. Sam Tobin-Hochstadt, Vincent St-Amour, Ryan Culpepper, Matthew Flatt, Matthias Felleisen. Programming Language Design and Implementation (PLDI), 2011. https://doi.org/10.1145/1993498.1993514}

---

Perl has also allowed a similar thing for many years. For example, use Lingua::Romana::Perligata; at the top of the file allows the remainder of the program to be written in a Latinate dialect, dynamically translated by the code in the given module. use Acme::Bleach; also has the side effect of replacing every other printable character in the file itself; while these examples are clearly jokes, the system permits arbitrary source rewriting and could implement other entirely-different languages as well.

---

A number of language-oriented programming tools, like Cedalion, allow the user to combine multiple different DSLs in one program. These all use the same host platform, and so are interoperable, but the specification of the dialect in use is generally out-of-band: the user edits code via a projectional editor, not as raw text in an outside editor, so the surface syntax they see does not need to include all of the data the system uses to determine the language. The language is more of a display grammar for the internal representation than a parsing grammar for text streams.

This approach relies on a common editing environment (or at least cooperating ones), but avoids all conflicting-syntax issues. There can be some semantic limits on the languages in practice, though in theory they can have unrestricted ability to have any syntax-semantic combinations. Storing the information outside of the program text is a good solution if you're in that scenario.

---

An arguably-similar approach is how polyglot .NET projects work: C#, VB.NET, and F# code can coexist in the same solution (and other .NET languages), and a combination of file extensions and outside project files indicate which language each source file uses. These languages are all interoperable and work on the same platform, so it is a very close real-world model to what you describe.

---

Wyvern² has an approach to embedding arbitrarily-parsed source within a file using whitespace-delimited blocks. This model uses indented blocks below ordinary method calls, where the expected type of a hole in the method arguments determines the parser used for the code. These parsers can be arbitrarily different from the host language, and in theory you could have a few lines of ordinary Wyvern code setting things up and then a block containing the bulk of the program in any other language. This model has the benefit of generality, although for the direct case you're aiming at it's substantively a more verbose version of Racket's #lang header.

²_{Cyrus Omar, Darya Kurilova, Ligia Nistor, Benjamin Chung, Alex Potanin, and Jonathan Aldrich. Safely composable type-specific languages. In Proceedings of the 28th European Conference on Object- oriented Programming (ECOOP), 2014. https://doi.org/10.1007/978-3-662-44202-9_5}

---

Designing dialects for a language called Grace was one of the topics of my PhD thesis and a preceding ECOOP paper³. In that model, there were three parts:

1. A dialect "abc" heading at the top of the file, identifying an importable module defining the dialect. This module would be loaded and define an object.

2. Implicitly enclosing the file's code within the object defined by that module, so that it would be in the lexical scope of any names defined by the object. This virtual nesting was intransitive, so a a file is in only its own dialect, not its dialect's dialect.

   This language had mixfix multi-part method names, and all its default control structures like if (condition) then {} else {} were defined like that, so it was possible to create very different dialects with just this. However, very core elements (like method declarations) would be common to all dialects. A follow-up work⁴ extended those mixfix methods to allow them to be defined with dynamic patterns, allowing more distant domain-specific languages.

3. Giving the AST of the file to a static checker method defined by that object, before execution or during compilation. This checker was able to report errors and reject the code, or produce other outputs, but by design choice could not make any mutations to it (though it is a pretty trivial extension to add that).

In this model, a dialect could define a domain-specific language that replaced all built-in definitions and structures and looked very different, but retained the overarching surface syntax. This sidesteps the issue of the dialect import itself being incompatible with the created syntax, but isn't able to be entirely different to the host, though it could have the flavour of a very different (even existing) system; for example, there was an APL-like dialect created, where many real APL programs could run with very minimal changes, but not all and not none.

³_{Graceful Dialects. Michael Homer, Timothy Jones, James Noble, Kim B. Bruce, Andrew P. Black. European Conference on Object-Oriented Programming (ECOOP), 2014. https://doi.org/10.1007/978-3-662-44202-9_6}

⁴_{From APIs to Languages: Generalising Method Names. Michael Homer, Timothy Jones, James Noble. Dynamic Language Symposium (DLS), 2015. https://doi.org/10.1145/2816707.2816708}

Answer 2

One possible approach is to do something similar to how Python handles source file encodings. Essentially, this relies on a specific comment at the beginning of the file. This only imposes a relatively small limitation on the dialect of having a specific syntax for comments

Answer 3

The dialect could be identified by the file extension. Either the dialects could declare supported extensions, or a dialect-for-extension lookup table can be maintained. However, allowing imported files to have different extensions has the consequence of allowing conflicting imports (when there are two files with the same name but different extensions), which is undesireable

Answer 4

One possibility for sufficiently dynamic languages would be to start evaluating source code before you're done parsing. This would allow one to define DSLs in source code, for example:

define-dsl test {
    // actual dsl implementation left as exercise for reader
}

test [this is a nonsense dsl] // use dsl in same source file

This would also allow you to separate these out in different modules, which means you can use import statements or declarations to essentially select a dialect:

// main.ext
import test_dsl

test [this is a nonsense dsl] // use dsl in main source file

// test_dsl.ext

define-dsl test {
    // actual dsl implementation left as exercise for reader
}

Answer 5

Swift allows the construction of DSLs with @resultBuilder. These DSLs apply per-block, not per-file, so multiple of them can coexist. SwiftUI, the third and most recent of Apple's UI frameworks, makes heavy use of these.

In order to function as a result builder, a type must meet the following requirements:

• It must be marked @resultBuilder. In order to prevent accidental instantiation, the most common spelling is @resultBuilder public enum FooBuilder {}.
• It must have either:
  • A static func buildBlock(...) -> Component, where Component is any type, or
  • A static func buildPartialBlock(first: Component) -> Component AND a static func buildPartialBlock(accumulated: Component, next: Component) -> Component.
• It may also have a number of other methods to enable various features, such as static func buildOptional(_: Component?) -> Component to support if statements.

To use an example from the proposal:

// Original source code:
@TupleBuilder
func build() -> (Int, Int, Int) {
  1
  2
  3
}

// This code is interpreted exactly as if it were this code:
func build() -> (Int, Int, Int) {
  let _a = TupleBuilder.buildExpression(1)
  let _b = TupleBuilder.buildExpression(2)
  let _c = TupleBuilder.buildExpression(3)
  return TupleBuilder.buildBlock(_a, _b, _c)
}

Notice that the usage of the DSL is indicated with @TupleBuilder before the function declaration. For function-typed arguments ("trailing closures"), this is even less intrusive:

func iNeedAFoo(@FooBuilder builder: () -> Foo) {
  let foo = builder()
  // ...
}

iNeedAFoo {
  // This block is implicitly @FooBuilder because of the function declaration
}

Result builders intentionally limit what DSLs can do, which has its fair share of pros and cons, more than I can completely cover here. The fact that many usages are implicit makes code cleaner, but it can also obfuscate what's going on. The diagnostics around result builders also used to be poor and required extra work on the API authors to work around (example).

Answer 6

One possible approach would be to use PEG (probably with Packrat) for parsing your core language, which allows to extend your parser dynamically. You simply define extension points in your original grammar (e.g., at expressions, statements, definitions, constants, etc.), and then add new parsers that are invoked when those points are reached - with PEG ordered choice it's much easier to do than with the more classical parsing techniques.

You can see an example of this approach here.