5 ms·

When I think of "innovation in language design", I don't really think of JIT-compiling highly dynamic behaviour. I think of inventing languages with programmin

by Athas 10y ago

When I think of "innovation in language design", I don't really think of JIT-compiling highly dynamic behaviour. I think of inventing languages with programming models that can be used for programming the heterogeneous hardware of the future (and, well, present). For example, massive parallelism is needed for both GPUs, FPGAs, clusters, and other more exotic systems, and the trick becomes how to translate portable and high-level problem descriptions to, say, highly vectorised code for GPUs, deep FPGA pipelines, or asynchronous message-passing cluster code. You can't solve that with JITs. From what I have seen, JITs are very useful for taking away the overhead of indirect calls and similar dynamic behaviour, but I don't think that's going to be the primary language design challenge of the future. No compiler can (usefully) extract significant amounts of parallelism from an algorithm which has none, and current programming models are not particularly convenient for expressing parallel algorithms. While current languages allow you to express parallelism by using low-level features, the resulting program will invariably be non-portable. High-level parallel languages (or maybe libraries) are the only solution I can see.

mike_hearn 10y ago
Actually that's not quite true: https://github.com/pcpratts/rootbeer1 https://github.com/pcpratts/rootbeer1 http://openjdk.java.net/projects/sumatra/ http://openjdk.java.net/projects/sumatra/ There has been work done on automatically identifying and running ordinary JVM hotspots on the GPU. That said, I agree that automatic parallelisation is a hard problem. I don't think it's the only interesting area of language innovation: most of the innovations making programmers lives easier in recent years have nothing to do with it.
- Athas 10y ago
  Both of those projects look like they are about designing a convenient GPU programming API for Java. Which is fine and useful, but you still have to program with an understanding of the GPU model (notably, massive threading), so it's not quite as high-level as what I believe is needed for portable performance.
  - akiselev 10y ago
    How can we even get "portable performance" between architectures like ARM and x86/64, let alone from orthogonal paradigms like CPUs and GPUs? Intel/AMD processors have complex branch predictors and instruction decoders and SIMD, ARM has conditional execution and some sort of quasi-SIMD, and GPUs have a weird hybrid of SIMD and multi-threaded-single-whatever (execution??) with sorta-kinda shared memory. Not only do these architectures implement memory access differently, the way basic control flow operations (conditionals and loops) work is physically different. That's not even including architectures like SPARC or specialized DSPs. Or FPGAs, which are a whole different universe.
    - Athas 10y ago
      It's not going to be easy, I agree. Matching hand-optimized hand-written code written by experts is not realistic for single primitives, of course. But getting close may be. It's all about programming at a high enough level that the compiler doesn't have to think too hard about what the program means, so that it can instead spend its time worrying about how to express that in the machine code of the target platform. Imperative languages are probably hopeless, but declarative languages may work. Functional languages in its current popular incarnations is about as hard to compile intelligently as imperative code, but I think that functional array programming (where bulk operations are primitives) show promise. Consider computing the average of every row of an n*m matrix 'a' (a 2D array). In Haskell-ish syntax, we would write this as: map (map (/m)) (map sum a) Now the compiler really only has to figure out two high-level things: how to apply a function (division by 'm') to every element of an array, and how to sum equally-sized segments of an array. Summing is again an instance of a more primitive bulk operation, reduction, which is parallel in theory, and has known efficient parallel implementations on most hardware. It's also possible to do some fusion for this small example, but my point is that we will need a programming model where the individual statement or expression works at a much higher level, and has much stronger properties, than in most current languages. You still need to teach the compiler about each specific hardware platform you want to target, of course (possibly by automatic learning or autotuning, as in http://www.lift-project.org/ http://www.lift-project.org/ ).
wcrichton 10y ago
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.
zzzcpan 10y ago
I agree, the headline is incorrect, the whole thing is basically a compiler infrastructure for those using Java, not about language design. And it's true that the hard part is still transforming a representation close to the problem domain into a VM-executable one, as they are worlds apart. Then there is also an ecosystem problem, which forces us into the meta world and generating specific code in a specific format instead of doing anything with a VM. I didn't really see the appeal last time we discussed it and I don't see it now.
goatlover 10y ago
Why do you need that outside of gaming and numerical computing? Most software above the system level doesn't need to be super performant, or highly parallel. It's fast enough. We got by with far less resources a decade ago, and still ran a lot of the same software. Why would we need to port all that over to GPUs, etc?
- Athas 10y ago
  Numerical computing is important for science in general, and really hard. But if you're perfectly fine with the current state of software, then sure, there's no need to change anything. Future CPUs will gain an increasing amount of their performance from parallelism - both coarse- (more cores) and fine-grained (better vector units), but there is no reason we have to exploit it. I suspect many people will want to, however, and they will likely find current programming models somewhat awkward.
- throwaway729 10y ago
  Progress on Moore's law has always created new markets that weren't predicted, or seemed unlikely/silly. There are a lot of computational tasks that can not run on a smartphone today. It'd be great to run an IDE, a few baclground classification tasks, and a high quality augmented reality VR headset app on a device with an 8 hour battery under that load and fits in my pocket. That's not happening without lots of hardware customization.
- gumby 10y ago
  It depends what you're optimizing for. If it's for programmer time / inexpensive programmers, sure. But remember the (probably apocryphal) story of Jobs complaining that the Mac took too long to boot, costing human lifetimes worth of waiting per year. Look at all the slow web pages, how slow Word or Excel are, etc -- that's a lot of human lifetimes. More relevant is power. The more wasted cycles the shorter your battery life. The hotter that device implanted in you becomes. The worse the cooling problem in the datacenter. It's naive to think that "computers are fast enough".
rch 10y ago
High level synthesis for FPGAs is coming along, slowly, and dynamic method migration has been around for at least a decade. But I agree that more efforts along those lines would be interesting to see.

by Athas 10y ago

mike_hearn 10y ago

Actually that's not quite true: https://github.com/pcpratts/rootbeer1 https://github.com/pcpratts/rootbeer1 http://openjdk.java.net/projects/sumatra/ http://openjdk.java.net/projects/sumatra/ There has been work done on automatically identifying and running ordinary JVM hotspots on the GPU. That said, I agree that automatic parallelisation is a hard problem. I don't think it's the only interesting area of language innovation: most of the innovations making programmers lives easier in recent years have nothing to do with it.

Athas 10y ago
Both of those projects look like they are about designing a convenient GPU programming API for Java. Which is fine and useful, but you still have to program with an understanding of the GPU model (notably, massive threading), so it's not quite as high-level as what I believe is needed for portable performance.
- akiselev 10y ago
  How can we even get "portable performance" between architectures like ARM and x86/64, let alone from orthogonal paradigms like CPUs and GPUs? Intel/AMD processors have complex branch predictors and instruction decoders and SIMD, ARM has conditional execution and some sort of quasi-SIMD, and GPUs have a weird hybrid of SIMD and multi-threaded-single-whatever (execution??) with sorta-kinda shared memory. Not only do these architectures implement memory access differently, the way basic control flow operations (conditionals and loops) work is physically different. That's not even including architectures like SPARC or specialized DSPs. Or FPGAs, which are a whole different universe.
  - Athas 10y ago
    It's not going to be easy, I agree. Matching hand-optimized hand-written code written by experts is not realistic for single primitives, of course. But getting close may be. It's all about programming at a high enough level that the compiler doesn't have to think too hard about what the program means, so that it can instead spend its time worrying about how to express that in the machine code of the target platform. Imperative languages are probably hopeless, but declarative languages may work. Functional languages in its current popular incarnations is about as hard to compile intelligently as imperative code, but I think that functional array programming (where bulk operations are primitives) show promise. Consider computing the average of every row of an n*m matrix 'a' (a 2D array). In Haskell-ish syntax, we would write this as: map (map (/m)) (map sum a) Now the compiler really only has to figure out two high-level things: how to apply a function (division by 'm') to every element of an array, and how to sum equally-sized segments of an array. Summing is again an instance of a more primitive bulk operation, reduction, which is parallel in theory, and has known efficient parallel implementations on most hardware. It's also possible to do some fusion for this small example, but my point is that we will need a programming model where the individual statement or expression works at a much higher level, and has much stronger properties, than in most current languages. You still need to teach the compiler about each specific hardware platform you want to target, of course (possibly by automatic learning or autotuning, as in http://www.lift-project.org/ http://www.lift-project.org/ ).

wcrichton 10y ago

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.

zzzcpan 10y ago

I agree, the headline is incorrect, the whole thing is basically a compiler infrastructure for those using Java, not about language design. And it's true that the hard part is still transforming a representation close to the problem domain into a VM-executable one, as they are worlds apart. Then there is also an ecosystem problem, which forces us into the meta world and generating specific code in a specific format instead of doing anything with a VM. I didn't really see the appeal last time we discussed it and I don't see it now.

goatlover 10y ago

Why do you need that outside of gaming and numerical computing? Most software above the system level doesn't need to be super performant, or highly parallel. It's fast enough. We got by with far less resources a decade ago, and still ran a lot of the same software. Why would we need to port all that over to GPUs, etc?

Athas 10y ago
Numerical computing is important for science in general, and really hard. But if you're perfectly fine with the current state of software, then sure, there's no need to change anything. Future CPUs will gain an increasing amount of their performance from parallelism - both coarse- (more cores) and fine-grained (better vector units), but there is no reason we have to exploit it. I suspect many people will want to, however, and they will likely find current programming models somewhat awkward.
throwaway729 10y ago
Progress on Moore's law has always created new markets that weren't predicted, or seemed unlikely/silly. There are a lot of computational tasks that can not run on a smartphone today. It'd be great to run an IDE, a few baclground classification tasks, and a high quality augmented reality VR headset app on a device with an 8 hour battery under that load and fits in my pocket. That's not happening without lots of hardware customization.
gumby 10y ago
It depends what you're optimizing for. If it's for programmer time / inexpensive programmers, sure. But remember the (probably apocryphal) story of Jobs complaining that the Mac took too long to boot, costing human lifetimes worth of waiting per year. Look at all the slow web pages, how slow Word or Excel are, etc -- that's a lot of human lifetimes. More relevant is power. The more wasted cycles the shorter your battery life. The hotter that device implanted in you becomes. The worse the cooling problem in the datacenter. It's naive to think that "computers are fast enough".

rch 10y ago

High level synthesis for FPGAs is coming along, slowly, and dynamic method migration has been around for at least a decade. But I agree that more efforts along those lines would be interesting to see.