Lambda the Ultimate

I am pretty sure that Erik saw this discussion after I copied it from his Facebook page, but we will have to wait for him to respond to find out about your questions.

Yes, but explicit staging (which is what a compiler does) requires manipulating some level of syntax objects, which makes composition more difficult, I believe. If you define "compilation" to be "interpreter + partial evaluation" then the problems with composition compilation go away.

Why are interpreters more composable than compilers?

manipulating some level of syntax objects, which makes composition more difficult

Composition of syntax objects can be easy or difficult, depending on the target language. State machines don't compose very nicely, for example, but FORTH code composes nicely, and so do multi-agent systems or generalized arrows.

Compilers as a whole can at least compose by staging. E.g. `compilerFooBar :: Foo -> Bar`, and `compilerBarQux :: Bar -> Qux` can easily be composed into a compilerFooQux. But the more interesting question is often whether two Bar programs can be composed, i.e. if we also have `compilerBazBar :: Baz -> Bar`, can we develop a useful compiler for a mixed FooBaz program? Here, it is the composition of `Bar` subprograms that matters, not composition of compilers.

Compilation is not the same as interpretation + partial evaluation. Interpretation suggests a certain potential for incremental computation that is not implied by compilation.

I think I need to clarify what I mean by "compilers don't compose". I do NOT mean that the definition of an individual compiler cannot be compositional. What I mean is that it is not easy to compose compilers for a modular language definition or to compose different compiler aspects/features of one language that are defined separately. The issue is that the interface between parts of a compiler involves the generated code, so the different parts of the compiler may have to cooperate to generate the right code. In other words, if A and B are compilers for aspects of a program P, then A(P) and B(P) are the code that they generate, then A(P) and B(P) must be integrated somehow. So yes, I am talking about the difficult case of a "compiler for a mixed FooBaz program" described by @dmbarbour.

Finally, I should say that "interpreters compose more easily than compilers" is a research hypothesis, not a proven fact. I'm investigating the question.

Say I have some language compiler targeting the MSIL backend. My language allows aspect-weaving. In pass one of the compiler, the compiler decides to generate a bne.un.s MSIL instruction, the short form of bne.un which means it can have a shorter label offset than a typical branching instruction. In the second pass of the compiler, aspects are weaved in at join points and I have accidentally violated the maximum branch offset allowed by the bne.un.s instruction by inserting too many intermediary instructions.

This is a typical scenario aspect weaving compilers have trouble with, as too often the languages use byte code weaving libraries that do not expose a suitable intermediate representation (too low-level, making it easy to violate stable interposition invariants such as short branches vs. long branches). Note that if I had an interpreter, there would be no "machine code" representation, typed or not, to worry about. The only composition issue is ordering syntax correctly.

As I understand it, Finally Tagless indirectly allows you to get around this, further refined through Atkey et al's Unembedding Domain Specific Languages. Atkey sets up the design argument in terms of two representations, de Bruijn indices and HOAS.

...do you mean partial evaluation? In my experience, the hard part of compilation isn't the beta-evaluation part (even under lambdas), it's the eta-rules and commuting conversions you have to do to expose the reductions. For example, suppose we want to optimize the id function below:

not : bool → bool
not b = if b then false else true

id : bool → bool 
id b = not (not b)

β-reduction gets you to:

id b = if (if b then false else true) then false else true

You need to apply a commuting conversion to turn this into:

id b = if b then (if false then false else true) else (if true then false else true)

Now, β-reduction of *this* gets you to

id b = if b then true else false

But you still need an η-rule to get:

id b = b 

Basically, the β-reductions/evaluation rules are oriented, so you always know which direction to apply them (modulo code size explosion issues), but the other rules are unoriented, and (1) in different cases you need different directions, and (2) sometimes you have to go through a worse program to get to a better one.

1. Skips writing parser and interpreter from scratch.
2. Integration with the host language is trivial.

Note, however, that embedded languages do not offer any further benefits really beyond these. For example, Erik decried Alan Kay's (spic "Allen") demo of Frank, which is built from a collection of EDSLs. But why, exactly? For example, would it be worse to verify C than to verify 5 or 6 highly targeted and small domain languages? And what about tool-ability? Despite Haskell and functional programming languages allowing you to combine 4 or more DSLs to create something like the Yesod web programming framework, why isn't there a good IDE for building Yesod apps?

Further, let's compare say Nile (part of Frank) to Conal Elliot's work on composable shaders. Which is better? And why?

Also, "internal" or embedded DSLs are not re-written in a host language. They are simply written in the host language. To achieve this affect can be quite an effort and require a team of Ph.D.'s, due to challenges with sharing and recursion associated with creating "deeply embedded" DSLs. But sometimes a shallow embedding is nice, too. For example, terms that exist only to make code more readable and are actually ignored as function inputs.

Its a good summary of the benefits of embedding. While there is a lot of interest in embedding, its not clear that it is generally "preferred" by the community. It's also not clear that it will win in the long run.

My experience so far with the GLR parser that Tijs van der Storm wrote for Enso is that writing a parser involves very little effort. Write the grammar, and it just works. GLR grammars are full context-free grammars with no restrictions (left recursion, PEG style asymmetry, etc), and they compose cleanly. We have integrated declarative creation of object graphs (a generalization of ASTs) into the grammar, so the parsing to objects (and pretty-printing) is essentially free.

As for interpreters, they do involve some effort. But we reuse them because the interpreters are first-class parts of our environment, not closed boxes. Imagine packaging the syntax/semantics of expressions, binding, and comprehensions into separate reusable "language modules" in a language library. This doesn't exist yet, but it provides a good vision for how external languages could have powerful features as easily as embedded languages.

This is a double-edged sword. In most of the recent work you mention, the current trend seems to be embedding DSLs in a way that supports multiple interpretations, optimization, and compilation. This tends to require more explicit representation of the DSL language (as an abstract AST, for example) so that it is amenable for analysis in addition to other forms of interpretation. When you do this, the boundary between the DSL and the host language becomes more difficult to cross. Allowing more of the host language to be reified into the DSL sublanguage is also an interesting research area. LINQ is a practical example of the benefits and pitfalls of this idea.

Other issues, including error messages, good syntax, and debugging, and language-specific tools are not so good for embedded languages.

The tradeoffs are significant enough that there is lots of room for research on many fronts at once.

NOTE: My understanding is that OMeta is an embedded language for grammars, but that Nile is a regular external DSL that is compiled to a lower-level language. The compiler is written using OMeta as a transformation engine.

w7cook: Imagine packaging the syntax/semantics of expressions, binding, and comprehensions into separate reusable "language modules" in a language library.

This reminds me of David Espinosa's old semantic lego work, the MetaPRL extensible compilers work, and this semantics survey based on Winskel's text.

Embedding a DSL is advantageous, but not primarily because you can reduce some chores regarding semantic analysis, compilation, etc.

Rather, the advantage is the ability to focus the embedded DSL on a small problem space - handle 80%, 96%, or 99.2% of a specific problem or class of problems. This focus allows the embedded DSL to remain simple, or even to err on the side of over-simplification. Allow the GPPL to cover corner cases and provide glue between problems (e.g. via callbacks or on-the-fly code generation).

External DSLs cannot easily remain focused. They have no mother language to depend upon, and so they must reinvent much general purpose behavior. Even SQL is Turing complete these days. But these languages fight, deny, are ashamed of their new responsibilities. Rather than growing into a responsible adult GPPLs, an external DSL becomes a man-child of the language community.

A GPPL can be designed to designed to support extension and embedding of DSLs, make it easier to integrate syntax, tools, and debugging. The PLT group has done a lot of work in this area. It is feasible to standardize some aspects of embedded language development. A common API for debug-views could be leveraged directly by an embedded compiler and even by a meta-grammar.

An interesting possibility I explore for staged DSLs with live programming: mashable, composable widget-based grammars and syntax (with bi-directional debugger views and human interaction/gestures built right in) rather than dumb text layout. A widget-AST is compiled to provide continuous feedback through an IDE (at least while that fragment is in view) even while executing some behavior.

a good embedded DSL is "just a good library," but at that point what is being said?

It says that designing a good library API is the same problem as designing a good language. It says that programming is language manipulation. That's a useful revelation, I think.

It says that designing a good library API is the same problem as designing a good language. It says that programming is language manipulation. That's a useful revelation, I think.

There is something more in Tim's post: "As soon as you need to detect/infer/enforce any semantic property that can't be encoded in your host language...". For a given DSL, not all general languages can encode it; you need a language that is expressive enough. This means that not all languages can write good libraries for this problem domain. You need expressive languages to write good libraries, and that's probably the main reason why we fight for more and more expressive languages¹.

¹: with, as a caveat, the remark by Ehud that languages that focus too much on general expressivity may have adoption troubles.

Expressiveness, as described by Matthias Felleisen, is a property that allows us to locally (i.e. within a syntactic bounding box) encode a behavior or property that would be distributed (non-local syntax) if expressed in some other language. A sufficiently expressive language should allow direct encoding of DSLs, as plain old functions, types, libraries. That is a valuable feature, certainly. All else being equal (though it never is), more expressiveness would be a good thing.

But expressiveness is not essential for making a GPPL a great host for DSLs. It is straightforward to cover a deficiency of expressiveness with one more layer of indirection, staged computation, perhaps a little shared state or inversion of control. The result is frameworks (and services, etc.).

Expressiveness is ultimately about covering "more" abstractions. But we could achieve more productive and useful languages, I think, if we can discover just the "right" abstractions and cover those very well. An alternative to seeking a more expressive language is to:

• develop a language that is better at abstracting indirection, inversion, and staging
• encode DSLs in the indirect style, as frameworks and staged computations

This is the approach I favor. Expressiveness is a property I've systematically reduced in favor of composition and modularity features. Those features - especially reactive semantics - make it easier to abstract and compose frameworks (at their interfaces) as if they were first-class entities.

We don't need more expressive languages to write good libraries or embed wonderful DSLs.

You will indeed gain a lot of flexibility by adding a layer of interpretation in between. This flexibility is, however, in the dynamic rather than static semantic. If you want to, as Tim mentions, "encode semantic properties", you also need to work at the static level: you want to lift static knowledge about the DSL into static knowledge the host language can manipulate.

I believe the ability to represent static knowledge is also a desirable form of "expressivity"; if you are not able to accept a program that you know is safe by domain-specific reasoning, or on the contrary not able to reject a program that a domain-specific analysis would deem meaningless, you are less expressive. In a Felleisen-like presentation, I would require that the syntactic translations you're considering preserve typeability of the program (both positive and negative).

If you move from a shallow to a deep embedding, you will have more flexibility to implement arbitrary dynamic rule, but you're likely to lose static knowledge as a counterpart. "Well-typed programs do not go wrong": you need to type your pieces of staged program from the point of view of its final, non-staged semantics. Even with GADTs for example, you can offer a superficial level of typing for combinators, but representing terms with binders is non-trivial. I think the "Finally Tagless" style has been effective at showing us that we can do much with simple things, but that required a lot of ingenuity, and I'm not sure it can be systematically applied to all kind of static analyses.

Encoding of semantic properties does not need to occur all in one stage. The essence of static analysis is to reject some programs after analyzing them but before running them. This is quite easy to express:

compileAtoB :: ProgramA -> Either ProgramB ErrorsInA

With staged programming, the computation of compileAtoB, in which some errors are discovered, may occur in one (of many) explicit compile-time stages. At least for cases where we know ProgramA statically, such as when it is part of our source code.

There is an ideal held by many of the more mathematically inclined PL designers: to forbid errors in the embedded DSL in the same stage as some other static analysis of the host language. This might be achieved by a sufficiently expressive type system (e.g. dependent and linear typing). One could express "this compilation isn't allowed to fail" by a partial function that only handles the success case, or by assertion, or by type annotation.

But, even without expressive analysis, staging can solve the very practical goal of detecting errors at development time. And staging naturally results in more consistent, flexible, and reusable code (rarely need to specialize code for runtime vs. compile-time, or closed system vs. open system). Staging is simple, and results in simple systems.

"Well-typed programs do not go wrong": you need to type your pieces of staged program from the point of view of its final, non-staged semantics.

You are assuming a stronger goal than may be necessary. Rather than "programs [that] do not go wrong", consider "the ability to control when and where programs go wrong, and how wrong they can go". I don't mind programs that go wrong, so long as they do so at development time, on my machine, and without any dangerous authorities. My goals include productive development, ability to refactor applications into services, and to eliminate errors before they reach the customer.

What are your goals? Why are they your goals?