3 ms·

An idea I've been banging around for a while: most high performance DSLs do not have language constructs that you can't find in general purpose languages. In fa

An idea I've been banging around for a while: most high performance DSLs do not have language constructs that you can't find in general purpose languages. In fact, it's quite the opposite--these DSLs are defined more by what they lack instead of what they contain. Take for example Halide [0], the image processing DSL. It has you represent image transformations with pure functions (no side effects) on limited data types (float, int, char). These are things you can do in any modern general-purpose programming language (e.g. Haskell, Rust, Scala, etc.), but of course you can also do much more in these environments. When you take away everything but just what you need to do image processing, you can generate far faster code. If you tried to do the same thing for Rust functions, for example, it's considerably more difficult to generalize image processing code where each element of your n-D array could be a struct or a pointer. My hypothesis is that a common DSL framework would be just an ordinary programming language (e.g. an extended version of Haskell or Rust) that allows library writers to subset its AST and substitute a code generator for its preferred subset. That way, a DSL writer doesn't have to re implement expression parsing, type checking, error messages, ... but instead just has to do the code generation. Moreover, it would limit fragmentation since the DSLs are, by requirement, the same syntax as the host language, so users would have a more consistent experience between different languages instead of working across arbitrarily different syntaxes. [0] http://halide-lang.org/ http://halide-lang.org/

Athas 10y ago
I agree that achieving high performance from high-level languages relies crucially on restricting the expressive power of the language. The more powerful the language, the harder it is for a compiler to analyse the essentials of the computation and map it to hardware whose functioning may be very remote from the programmer's mental model the the program. Of course, what is "powerful" to a compiler is not necessarily what is considered "powerful" to a human, so with some cleverness it is possible to restrict languages in ways that vastly help the compiler, but seem like fairly minor concessions to a human. That is what I would call the language design questions problem of the future. Whether these restricted languages are doable as embedded DSLs in general-purpose language remains to be seen. There have been attempts that work pretty well (Accelerate for Haskell is the one I know best), but they are limited in expressibility, and the ergonomics (type errors and conceptual clarity) are not great. Also, even with all the work that has gone into Accelerate, the end result is only useful to Haskell programmers, which is a shame. Perhaps this can be solved with a sufficient amount of shared infrastructure. Access to the real AST, instead of the lifted operations used by Accelerate, would be a good start.
- kd0amg 10y ago
  Whether these restricted languages are doable as embedded DSLs in general-purpose language remains to be seen. There have been attempts that work pretty well (Accelerate for Haskell is the one I know best), but they are limited in expressibility, and the ergonomics (type errors and conceptual clarity) are not great. Ziggurat[0] was an attempt at a general-purpose system to communicate static properties of DSLs past the more general host language (where they don't necessarily apply). It probably falls under the "ergonomics are not great" category though. 0: http://www.ccs.neu.edu/home/shivers/papers/ziggurat-jfp.pdf http://www.ccs.neu.edu/home/shivers/papers/ziggurat-jfp.pdf
- notjack 10y ago
  > Whether these restricted languages are doable as embedded DSLs in general-purpose language remains to be seen I'd argue that the Racket language (or language platform, depending on your view of things) shows it's possible with its #lang mechanism and macro system. For example, though Racket proper is untyped, Typed Racket is implemented as a #lang with macros and includes an optimizing compiler that removes runtime checks on programs that typecheck successfully.
junke 10y ago
How is what you describe not the core of Lisp's philosophy?
- wcrichton 10y ago
  A good point that Lisp encapsulates a lot of the extensibility I describe, but I think there's two missing parts: a strong type system and a clear story for FFI. With Haskell (or Rust or Scala or OCaml or ...) you could take advantage of static type guarantees, both for productivity as well as for generating more efficient code. That isn't to say you can't type check Lisp code, but that you could get it for free with a statically typed language. For FFI, if your eDSL is going to be generating CUDA code or whatever, then you need a clear way to translate values between the two sides. This is easy for a language like Rust and is doable for languages like Haskell, but I don't know if anything like that has been tried for Lisp.
  - junke 10y ago
    The typing aspect is really not a problem to me, but I get what you mean (also, "strong" typing is different from "static" typing). It seems also that staged compilation is becoming more and more used in statically typed languages. As for interfacing with low-level code, this is basically a major aspect of why Common Lisp is appreciated. Interfacing with C libraries is done routinely (CFFI: https://common-lisp.net/project/cffi/manual/html_node/index.html#SEC_Contents https://common-lisp.net/project/cffi/manual/html_node/index....). You write shaders in Lisp, you can interface with CUDA, and so on.

Athas 10y ago

I agree that achieving high performance from high-level languages relies crucially on restricting the expressive power of the language. The more powerful the language, the harder it is for a compiler to analyse the essentials of the computation and map it to hardware whose functioning may be very remote from the programmer's mental model the the program. Of course, what is "powerful" to a compiler is not necessarily what is considered "powerful" to a human, so with some cleverness it is possible to restrict languages in ways that vastly help the compiler, but seem like fairly minor concessions to a human. That is what I would call the language design questions problem of the future. Whether these restricted languages are doable as embedded DSLs in general-purpose language remains to be seen. There have been attempts that work pretty well (Accelerate for Haskell is the one I know best), but they are limited in expressibility, and the ergonomics (type errors and conceptual clarity) are not great. Also, even with all the work that has gone into Accelerate, the end result is only useful to Haskell programmers, which is a shame. Perhaps this can be solved with a sufficient amount of shared infrastructure. Access to the real AST, instead of the lifted operations used by Accelerate, would be a good start.

kd0amg 10y ago
Whether these restricted languages are doable as embedded DSLs in general-purpose language remains to be seen. There have been attempts that work pretty well (Accelerate for Haskell is the one I know best), but they are limited in expressibility, and the ergonomics (type errors and conceptual clarity) are not great. Ziggurat[0] was an attempt at a general-purpose system to communicate static properties of DSLs past the more general host language (where they don't necessarily apply). It probably falls under the "ergonomics are not great" category though. 0: http://www.ccs.neu.edu/home/shivers/papers/ziggurat-jfp.pdf http://www.ccs.neu.edu/home/shivers/papers/ziggurat-jfp.pdf
notjack 10y ago
> Whether these restricted languages are doable as embedded DSLs in general-purpose language remains to be seen I'd argue that the Racket language (or language platform, depending on your view of things) shows it's possible with its #lang mechanism and macro system. For example, though Racket proper is untyped, Typed Racket is implemented as a #lang with macros and includes an optimizing compiler that removes runtime checks on programs that typecheck successfully.

junke 10y ago

How is what you describe not the core of Lisp's philosophy?

wcrichton 10y ago
A good point that Lisp encapsulates a lot of the extensibility I describe, but I think there's two missing parts: a strong type system and a clear story for FFI. With Haskell (or Rust or Scala or OCaml or ...) you could take advantage of static type guarantees, both for productivity as well as for generating more efficient code. That isn't to say you can't type check Lisp code, but that you could get it for free with a statically typed language. For FFI, if your eDSL is going to be generating CUDA code or whatever, then you need a clear way to translate values between the two sides. This is easy for a language like Rust and is doable for languages like Haskell, but I don't know if anything like that has been tried for Lisp.
- junke 10y ago
  The typing aspect is really not a problem to me, but I get what you mean (also, "strong" typing is different from "static" typing). It seems also that staged compilation is becoming more and more used in statically typed languages. As for interfacing with low-level code, this is basically a major aspect of why Common Lisp is appreciated. Interfacing with C libraries is done routinely (CFFI: https://common-lisp.net/project/cffi/manual/html_node/index.html#SEC_Contents https://common-lisp.net/project/cffi/manual/html_node/index....). You write shaders in Lisp, you can interface with CUDA, and so on.