10 ms·

Mike Pall: Ramblings on languages and architectures

146 points by asb 14y ago

mwcampbell 14y ago
EDIT: Expanded my question about Mike's opinion of FP. This perspective from a compiler developer lends credence to Stanislav Datskovskiy's rants about the importance of the underlying CPU architecture. Stanislav has done some work on a new dataflow-based CPU architecture (http://www.loper-os.org/?p=846 http://www.loper-os.org/?p=846). I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. After all, FP languages that don't allow reassignment of variables are in SSA form already, unless I misunderstand what SSA form is.
- catwell 14y ago
  Warning: I am far from being knowledgeable about compilers. That being said... SSA is actually more appropriate for imperative languages. Compilers for functional languages tend to use other intermediate representations such as CPS / ANF. They are "equivalent" though: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.3282&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34....
  - cwzwarich 14y ago
    In practice, working with them can be quite different. In a lexically scoped representation (either ANF or CPS) you have to preserve lexical scoping after each transformation, which can be pretty annoying if you want to do optimizations in their full generality. With SSA, you have to preserve dominance, but you don't have to update the dominator tree (the equivalent of the information encoded in the lexical scoping of ANF / CPS) if you don't want to; you can simply recompute it. Of course, the advantage that ANF / CPS have is that they can naturally represent higher-order programs, but for first-order programs they don't really have any advantage over SSA.
  - toolslive 14y ago
    I always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)
    - abecedarius 14y ago
      What do you mean by FST?
      - catwell 14y ago
        In that context it means Finite State Transducer. Basically it is a FSM (Finite State Machine) that generates an output depending on its input. I don't think you lose too much meaning of his sentence if you replace FST by Turing Machines (the more usual comparison to lambda-calculus).
        abecedarius 14y ago
        Ah, thanks. I thought the comment had some precise dualities in mind, but I guess not? (There is such a correspondence for CPS and SSA, cf Appel's paper.)
- mikemike 14y ago
  Converting to SSA form is comparatively easy. The interesting question is how pure a particular SSA variant actually is (hint: almost none are in practice). Just the fact that a language is closer to SSA form doesn't make it interesting. If a compiler is able to turn pretty much every source language into SSA, then why should I bother to do part of its work by hand? Much more relevant is how easy it is to express my intentions as a programmer and how much of that ends up helping the compiler and the CPU to execute the code faster. I really don't want this to turn into a flame-war about the merits of functional programming. The Wikipedia article has a nice list of the typical concepts: http://en.wikipedia.org/wiki/Functional_programming#Concepts http://en.wikipedia.org/wiki/Functional_programming#Concepts ... and the particular mix simply doesn't appeal to me personally.
  - DanWaterworth 14y ago
    It's interesting that you say that you are doing the compiler's work when you program functionally. Imperative compilers have three steps: they compile from an imperative language to SSA (which is almost functional), they then optimizes the SSA and then convert back to an imperative language. The reason that they convert the program into SSA is because it is much easier to reason about the program in that form. My take is that imperative compilers are an admission that functional programs are easier to reason about.
    - SomeCallMeTim 14y ago
      >My take is that imperative compilers are an admission that functional programs are easier to reason about. If you're implying that "easier to reason about" for a compiler is equivalent to "easier to reason about" for humans, I think that's a fallacy. Where functional programming fails is in performing tasks that are predominantly imperative; say, anything involving real-time behavior, like games or animation. And by "fails" I mean that an imperative language is easier for humans to follow when it maps more directly to the problem at hand.
      - DanWaterworth 14y ago
- yvdriess 14y ago
  > I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. As the FP community has consolidated around Haskell, this usually refers to the Haskell feature set: Graph reduction, lazy semantics. Graph reduction is extremely imperative (see: spineless stackless g-machine), which makes it map well on a Von Neumann processor, but limits the amount of exploitable parallelism. Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics. A functional language using eager semantics and string-reduction execution would map much better on, say, a parallel dataflow processor. Research in this direction got buried as parallel research money evaporated in the early 90's
  - mwcampbell 14y ago
    Would Standard ML be a suitable language for the kind of research you describe?
    - yvdriess 14y ago
      Very likely. At the very least a subset or with some additions, I-structures come to mind. If you're interested, someone already did some legwork on this, using an eager version of Haskell: [1] S. Aditya, Arvind, J.-W. Maessen, L. Augustsson, and R. S. Nikhil, “Semantics of pH: A parallel dialect of Haskell,” presented at the FPCA 95, 1995, pp. 35–49.
  - radm 14y ago
    But these kinds of languages do exist and it's reasonable to think about writing compilers for them and/or subsets.
    - yvdriess 14y ago
      I haven't heard of any recent string reduction languages. The last I heard about it was in Kent Dybvig 'Three Scheme Implementations' thesis, where he used it to map Scheme on a dataflow-like FP architecture (IIRC).
- riffraff 14y ago
  I may be wrong, but doesn't SSA imply the usage of the strange PHI thingy? I think it's a relatively simple transformation from a FP language without reassignment but I believe it's one significant difference at the surface level.
  - seabee 14y ago
    Doesn't an FP language without reassignment imply the existence of a function like phi to perform nontrivial control flow?
yvdriess 14y ago
Great to see Mike come to such conclusions. I've been interested myself in old dataflow architectures work for the same reasons. Some scholarly input: > But most of the existing ones are visual languages. The dataflow architecture guys were making textual languages from the start. Others spinned off dataflow (synchronous dataflow, for example) for SE purposes, rather than parallelism. e.g.: Lustre, LabView. > Ok, so I have plenty of ideas for all levels of the stack, but not enough time to pursue them with sufficient rigor. It could help to look at people that have tried to do the same thing. At the language level, lookup Sisal, Id, Val or pHaskel for example. A small selection, from bottom to top of the stack: To go completely off the hardware deep-end: [1] J. Gurd, C. Kirkham, and I. Watson, “The Manchester prototype dataflow computer,” Commun. ACM, vol. 28, no. 1, pp. 34–52, 1985. This imparts some intuition on how a civilised language can map on dataflow instructions. Made by hardware guys. [2] R. S. Nikhil, “Executing a program on the MIT tagged-token dataflow architecture,” Computers, IEEE Transactions on, vol. 39, no. 3, pp. 300–318, 1990. SISAL: SSA language oriented for numerical/HPC work. Made by compiler guys. [3] J. Gaudiot, T. DeBoni, J. Feo, W. Böhm, W. Najjar, and P. Miller, “The Sisal project: real world functional programming,” Compiler optimizations for scalable parallel systems, pp. 45–72, 2001. And somewhat more high-level, for the FP crowd: [4] P. Barth and R. Nikhil, “M-structures: extending a parallel, non-strict, functional language with state,” Functional Programming Languages and Computer Architecture, pp. 538–568, 1991. [5] Arvind, R. S. Nikhil, and K. K. Pingali, “I-structures: data structures for parallel computing,” Transactions on Programming Languages and Systems (TOPLAS, vol. 11, no. 4, Oct. 1989.
- mikemike 14y ago
  Thanks for the references! I'll have a read over the weekend. The problem with textual data-flow programming languages is that I haven't seen any that aren't ugly beyond repair.
  - scott_s 14y ago
    Look for the term "streaming". My project is distributed, asynchronous streaming (research name "System S", product name "InfoSphere Streams") which uses a dataflow language called SPL (Streams Processing Language). However, it allows imperative code at the vertices in the dataflow graph. It's appropriate for large scale streaming across whole clusters. The StreamIt project at MIT is not distributed and is synchronous, which maps to single chips much better. In fact, it grew out of making DSPs (digital signal processors) more programmable.
qznc 14y ago
> Ok, so I have plenty of ideas for all levels of the stack, but not enough time to pursue them with sufficient rigor. Did he publish those ideas somewhere?
deleted 14y ago
[deleted]
DanWaterworth 14y ago
I've also been thinking about processor architecture recently. My conclusion was that it is ludicrous to have processors' main input language be Turing-complete. Processors need to perform optimizations, to do that they need to make assumptions. In this sense, a Turing-complete input language is the worst possible choice.
- mikeash 14y ago
  What kind of input language would be both useful for general computation and not Turing-complete?
  - DanWaterworth 14y ago
    If I were to design a processor, it would essentially execute programs written in a total functional language with corecursion. So you would be able to create Turing-complete programs, but most of the time, the processor will be evaluating expressions in a primitive recursive subset that it can reason about and aggressively optimize.
    - mikeash 14y ago
      Turing-complete but with clean subsets seems completely different from not using a Turing-complete input language at all.
      - DanWaterworth 14y ago
        In order to execute a total functional language, you have to basically split the processor into two. I'll call these two parts the evaluator and the executor. * It's the evaluator's job to evaluate expressions. Expressions are primitive recursive so they always normalize. * The executor's job is to talk to the outside world and to provide data to the evaluator and receive commands from the evaluator. It also can't get stuck in an infinite loop; it must eventually provide data to the evaluator after receiving a command. The only way an infinite loop can happen is if the evaluator and the executor get stuck together. When I said processor before, I was referring to the part that did the processing: i.e. the evaluator.
williamaadams 14y ago
How timely that The Adapteva Parallela computer board was just made available as well. Perhaps something interesting can happen at the confluence of that hardware and these compiler thoughts.
- yvdriess 14y ago
  This is where it needs to happen. The problem is that co-designing a new hardware/software stack from scratch is the computer science equivalent of a moonshot.
  - williamaadams 14y ago
    In the case of Adapteva, I think it's helped along because their starting point is fairly standard. Using Arm, Ansi C, Ubuntu, etc. They have an fpga on their board, and then their specialized parallel processing chip. They support OpenCL. I'm not a compiler guy, but it seems to me that various concepts can be injected at different levels of this hardware stack, slowly but surely, without having to create the entire thing from scratch.
  - jacques_chester 14y ago
    Moonshots get made from time to time, however: * Intel's iAPX "mainframe in a chip" project [1] was aimed at directly supporting HLL features, * The Rekursiv chip project [2] was intended for an objected-oriented language, * The Transputer was meant to support Occam [3] and there have probably been others. [1] http://en.wikipedia.org/wiki/Intel_iAPX_432 http://en.wikipedia.org/wiki/Intel_iAPX_432 [2] http://en.wikipedia.org/wiki/Rekursiv http://en.wikipedia.org/wiki/Rekursiv [3] http://en.wikipedia.org/wiki/Transputer http://en.wikipedia.org/wiki/Transputer
  - knz42 14y ago
    The word "moonshot" is close to the truth, yet there are strategies to overcome the adoption threshold. That was precisely the topic of my PhD dissertation, and I concur that the Adapteva guys have chosen a sound approach. But Epiphany is not a dataflow architecture, and suffers from execution efficiency problems in individual cores. Dataflow is really the way to go to lower energy consumption dramatically. Funny this topic comes up. It just happens the EU has recently invested in such a project to co-design a dataflow processor and software stack. It was north of a million euros for the initial proof-of-concept research, and the results are slowly starting to trickle through. Some references: - http://staff.science.uva.nl/~poss/pub/poss.12.dsd.pdf http://staff.science.uva.nl/~poss/pub/poss.12.dsd.pdf - http://staff.science.uva.nl/~poss/pub/poss.13.micpro.pdf http://staff.science.uva.nl/~poss/pub/poss.13.micpro.pdf (I am one of the authors; ping me for more information)
jacques_chester 14y ago
I'm reminded a bit of the logic that lead to Itanium: all this silicon dedicated to doing voodoo mind reading on linear machine code is wasteful. Let's instead push parallelism up into the compilers. It didn't quite work out that way, but as a handy side effect it killed off PA-RISC and Alpha with little more than a few press releases.
- protomyth 14y ago
  I often wonder if it was the theory that was broken or the implementation? I doubt anyone will tread that way for quite a while due to the wreckage.
  - jacques_chester 14y ago
    Basically, Intel & HP bet on the appearance of "Sufficiently Smart Compilers". And they didn't turn up. Most of the code people want to run on high CPUs is written in C or Fortran. Producing correct parallel code from branchy, pointer-filled, shared-everything codebases is difficult. Basically they gambled on the mother of all handwaves and lost.
jbrennan 14y ago
I feel like you could do even better if you approached a language design from the other side, instead of focussing on the lower-level aspects to instead be thinking of higher level aspects. If I were designing a programming language, I would start with what the development environment would look like, what tools do I want to build to support development in the language, etc., and then build the language to support that. It seems so often languages are built, and then the tools are an afterthought, things like debugging, visualizing program flow, code assist, whatever it may be. What if program flow (that is, what's going on inside the program) were in mind from the start, instead of something you try and add later. Just my thoughts. Is this a feasible way to design a language?
- MattJ100 14y ago
  Depends what your goal is. Your approach is to optimize for developer productivity. Mike's is to optimize for machine productivity. The question is whether it is possible to do both at once, hence Mike's point about the ideal language needing to find the right high-level abstractions (machine-efficient and developer-intuitive). What we currently have is somewhere in-between, but more towards the machine-efficient side. It's quite easy to produce inefficient code, without realising it, in today's high-level languages.
  - jbrennan 14y ago
    >Your approach is to optimize for developer productivity. Mike's is to optimize for machine productivity. Yeah that's a valid point. And it's probably just my lack of experience in language design or just general naïveté. It seems like for most devices (modern smartphones, tablets, traditional computers) are fast enough that we'd be better served focusing on developer productivity in newer languages. Sure, they'll never compete with C in terms of efficiency. Besides, I can still easily create terribly inefficient code in C ;)
    - justincormack 14y ago
      Devices maybe but servers less so, if you can get a 100x performance increase from going g from say PHP to LuaJIT then you can save a lot of money without a productivity loss.
asb 14y ago
I still don't understand the policy of editors changing post titles here. The original title was "Mike Pall (LuaJIT) on programming language design". Maybe "Ramblings on languages and architectures" like the original posting is better, but I don't see the win in removing the author's name from it. After all, the reason we're all initially interested is that these thoughts are from Mike Pall, author of perhaps the most impressive dynamic language JIT.
- imsofuture 14y ago
  At this point, why is there even a title field available?
- asb 14y ago
  One of the anonymous editors has added back "Mike Pall" to the title. Thanks.
mwcampbell 14y ago
Would a CPU architecture that executed LLVM bitcode, or some other encoding of LLVM IR, be significantly less wasteful than what we have now? I wonder because LLVM IR is already SSA-based and is designed for optimization passes in a compiler. And it exists and is used today.
wmf 14y ago
Check out the TRIPS/EDGE architecture: http://www.cs.utexas.edu/~trips/overview.html http://www.cs.utexas.edu/~trips/overview.html It uses dataflow to efficiently execute individual instructions while atomically committing groups of instructions to preserve understandable semantics. While tiled architectures are common now, most of them have one core per tile. TRIPS built a large, high-performance core out of simple tiles so it can run different types of code efficiently.
- microarchitect 14y ago
  That link is missing their evaluation of TRIPS, which they did in 2008 after they built the chips: http://www.cs.utexas.edu/~bmaher/pubs/asplos09.pdf http://www.cs.utexas.edu/~bmaher/pubs/asplos09.pdf My impression is that TRIPS is much too complicated to be clocked at comparable frequencies to commercial processors. Their ISA also appears very hard to compile to.
craigyk 14y ago
Mike Pall was the first person I've ever met (via his postings and projects) that made me think, holy cow, this dude is way smarter than me. I've heard some people conjecture that it's actually a pseudonym for a group of people.... but I actually prefer to think it's one guy, by himself, getting awesome shit done.
- justincormack 14y ago
  "Some people" includes Roberto Ierusalimschy, the inventor of Lua, although he told me he now knows someone who has met Mike so he believes he is actually a singleton.

146 points by asb 14y ago

EDIT: Expanded my question about Mike's opinion of FP. This perspective from a compiler developer lends credence to Stanislav Datskovskiy's rants about the importance of the underlying CPU architecture. Stanislav has done some work on a new dataflow-based CPU architecture (http://www.loper-os.org/?p=846 http://www.loper-os.org/?p=846). I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. After all, FP languages that don't allow reassignment of variables are in SSA form already, unless I misunderstand what SSA form is.

catwell 14y ago
Warning: I am far from being knowledgeable about compilers. That being said... SSA is actually more appropriate for imperative languages. Compilers for functional languages tend to use other intermediate representations such as CPS / ANF. They are "equivalent" though: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.3282&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34....
- cwzwarich 14y ago
  In practice, working with them can be quite different. In a lexically scoped representation (either ANF or CPS) you have to preserve lexical scoping after each transformation, which can be pretty annoying if you want to do optimizations in their full generality. With SSA, you have to preserve dominance, but you don't have to update the dominator tree (the equivalent of the information encoded in the lexical scoping of ANF / CPS) if you don't want to; you can simply recompute it. Of course, the advantage that ANF / CPS have is that they can naturally represent higher-order programs, but for first-order programs they don't really have any advantage over SSA.
- toolslive 14y ago
  I always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)
  - abecedarius 14y ago
    What do you mean by FST?
    - catwell 14y ago
      In that context it means Finite State Transducer. Basically it is a FSM (Finite State Machine) that generates an output depending on its input. I don't think you lose too much meaning of his sentence if you replace FST by Turing Machines (the more usual comparison to lambda-calculus).
      - abecedarius 14y ago
        Ah, thanks. I thought the comment had some precise dualities in mind, but I guess not? (There is such a correspondence for CPS and SSA, cf Appel's paper.)
mikemike 14y ago
Converting to SSA form is comparatively easy. The interesting question is how pure a particular SSA variant actually is (hint: almost none are in practice). Just the fact that a language is closer to SSA form doesn't make it interesting. If a compiler is able to turn pretty much every source language into SSA, then why should I bother to do part of its work by hand? Much more relevant is how easy it is to express my intentions as a programmer and how much of that ends up helping the compiler and the CPU to execute the code faster. I really don't want this to turn into a flame-war about the merits of functional programming. The Wikipedia article has a nice list of the typical concepts: http://en.wikipedia.org/wiki/Functional_programming#Concepts http://en.wikipedia.org/wiki/Functional_programming#Concepts ... and the particular mix simply doesn't appeal to me personally.
- DanWaterworth 14y ago
  It's interesting that you say that you are doing the compiler's work when you program functionally. Imperative compilers have three steps: they compile from an imperative language to SSA (which is almost functional), they then optimizes the SSA and then convert back to an imperative language. The reason that they convert the program into SSA is because it is much easier to reason about the program in that form. My take is that imperative compilers are an admission that functional programs are easier to reason about.
  - SomeCallMeTim 14y ago
    >My take is that imperative compilers are an admission that functional programs are easier to reason about. If you're implying that "easier to reason about" for a compiler is equivalent to "easier to reason about" for humans, I think that's a fallacy. Where functional programming fails is in performing tasks that are predominantly imperative; say, anything involving real-time behavior, like games or animation. And by "fails" I mean that an imperative language is easier for humans to follow when it maps more directly to the problem at hand.
    - DanWaterworth 14y ago
yvdriess 14y ago
> I wonder why Mike considers the usual blend of concepts provided by FP languages to not be worthwhile. As the FP community has consolidated around Haskell, this usually refers to the Haskell feature set: Graph reduction, lazy semantics. Graph reduction is extremely imperative (see: spineless stackless g-machine), which makes it map well on a Von Neumann processor, but limits the amount of exploitable parallelism. Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics. A functional language using eager semantics and string-reduction execution would map much better on, say, a parallel dataflow processor. Research in this direction got buried as parallel research money evaporated in the early 90's
- mwcampbell 14y ago
  Would Standard ML be a suitable language for the kind of research you describe?
  - yvdriess 14y ago
    Very likely. At the very least a subset or with some additions, I-structures come to mind. If you're interested, someone already did some legwork on this, using an eager version of Haskell: [1] S. Aditya, Arvind, J.-W. Maessen, L. Augustsson, and R. S. Nikhil, “Semantics of pH: A parallel dialect of Haskell,” presented at the FPCA 95, 1995, pp. 35–49.
- radm 14y ago
  But these kinds of languages do exist and it's reasonable to think about writing compilers for them and/or subsets.
  - yvdriess 14y ago
    I haven't heard of any recent string reduction languages. The last I heard about it was in Kent Dybvig 'Three Scheme Implementations' thesis, where he used it to map Scheme on a dataflow-like FP architecture (IIRC).
riffraff 14y ago
I may be wrong, but doesn't SSA imply the usage of the strange PHI thingy? I think it's a relatively simple transformation from a FP language without reassignment but I believe it's one significant difference at the surface level.
- seabee 14y ago
  Doesn't an FP language without reassignment imply the existence of a function like phi to perform nontrivial control flow?

yvdriess 14y ago

Great to see Mike come to such conclusions. I've been interested myself in old dataflow architectures work for the same reasons. Some scholarly input: > But most of the existing ones are visual languages. The dataflow architecture guys were making textual languages from the start. Others spinned off dataflow (synchronous dataflow, for example) for SE purposes, rather than parallelism. e.g.: Lustre, LabView. > Ok, so I have plenty of ideas for all levels of the stack, but not enough time to pursue them with sufficient rigor. It could help to look at people that have tried to do the same thing. At the language level, lookup Sisal, Id, Val or pHaskel for example. A small selection, from bottom to top of the stack: To go completely off the hardware deep-end: [1] J. Gurd, C. Kirkham, and I. Watson, “The Manchester prototype dataflow computer,” Commun. ACM, vol. 28, no. 1, pp. 34–52, 1985. This imparts some intuition on how a civilised language can map on dataflow instructions. Made by hardware guys. [2] R. S. Nikhil, “Executing a program on the MIT tagged-token dataflow architecture,” Computers, IEEE Transactions on, vol. 39, no. 3, pp. 300–318, 1990. SISAL: SSA language oriented for numerical/HPC work. Made by compiler guys. [3] J. Gaudiot, T. DeBoni, J. Feo, W. Böhm, W. Najjar, and P. Miller, “The Sisal project: real world functional programming,” Compiler optimizations for scalable parallel systems, pp. 45–72, 2001. And somewhat more high-level, for the FP crowd: [4] P. Barth and R. Nikhil, “M-structures: extending a parallel, non-strict, functional language with state,” Functional Programming Languages and Computer Architecture, pp. 538–568, 1991. [5] Arvind, R. S. Nikhil, and K. K. Pingali, “I-structures: data structures for parallel computing,” Transactions on Programming Languages and Systems (TOPLAS, vol. 11, no. 4, Oct. 1989.

mikemike 14y ago
Thanks for the references! I'll have a read over the weekend. The problem with textual data-flow programming languages is that I haven't seen any that aren't ugly beyond repair.
- scott_s 14y ago
  Look for the term "streaming". My project is distributed, asynchronous streaming (research name "System S", product name "InfoSphere Streams") which uses a dataflow language called SPL (Streams Processing Language). However, it allows imperative code at the vertices in the dataflow graph. It's appropriate for large scale streaming across whole clusters. The StreamIt project at MIT is not distributed and is synchronous, which maps to single chips much better. In fact, it grew out of making DSPs (digital signal processors) more programmable.

qznc 14y ago

> Ok, so I have plenty of ideas for all levels of the stack, but not enough time to pursue them with sufficient rigor. Did he publish those ideas somewhere?

deleted 14y ago

[deleted]

DanWaterworth 14y ago

I've also been thinking about processor architecture recently. My conclusion was that it is ludicrous to have processors' main input language be Turing-complete. Processors need to perform optimizations, to do that they need to make assumptions. In this sense, a Turing-complete input language is the worst possible choice.

mikeash 14y ago
What kind of input language would be both useful for general computation and not Turing-complete?
- DanWaterworth 14y ago
  If I were to design a processor, it would essentially execute programs written in a total functional language with corecursion. So you would be able to create Turing-complete programs, but most of the time, the processor will be evaluating expressions in a primitive recursive subset that it can reason about and aggressively optimize.
  - mikeash 14y ago
    Turing-complete but with clean subsets seems completely different from not using a Turing-complete input language at all.
    - DanWaterworth 14y ago
      In order to execute a total functional language, you have to basically split the processor into two. I'll call these two parts the evaluator and the executor. * It's the evaluator's job to evaluate expressions. Expressions are primitive recursive so they always normalize. * The executor's job is to talk to the outside world and to provide data to the evaluator and receive commands from the evaluator. It also can't get stuck in an infinite loop; it must eventually provide data to the evaluator after receiving a command. The only way an infinite loop can happen is if the evaluator and the executor get stuck together. When I said processor before, I was referring to the part that did the processing: i.e. the evaluator.

williamaadams 14y ago

How timely that The Adapteva Parallela computer board was just made available as well. Perhaps something interesting can happen at the confluence of that hardware and these compiler thoughts.

yvdriess 14y ago
This is where it needs to happen. The problem is that co-designing a new hardware/software stack from scratch is the computer science equivalent of a moonshot.
- williamaadams 14y ago
  In the case of Adapteva, I think it's helped along because their starting point is fairly standard. Using Arm, Ansi C, Ubuntu, etc. They have an fpga on their board, and then their specialized parallel processing chip. They support OpenCL. I'm not a compiler guy, but it seems to me that various concepts can be injected at different levels of this hardware stack, slowly but surely, without having to create the entire thing from scratch.
- jacques_chester 14y ago
  Moonshots get made from time to time, however: * Intel's iAPX "mainframe in a chip" project [1] was aimed at directly supporting HLL features, * The Rekursiv chip project [2] was intended for an objected-oriented language, * The Transputer was meant to support Occam [3] and there have probably been others. [1] http://en.wikipedia.org/wiki/Intel_iAPX_432 http://en.wikipedia.org/wiki/Intel_iAPX_432 [2] http://en.wikipedia.org/wiki/Rekursiv http://en.wikipedia.org/wiki/Rekursiv [3] http://en.wikipedia.org/wiki/Transputer http://en.wikipedia.org/wiki/Transputer
- knz42 14y ago
  The word "moonshot" is close to the truth, yet there are strategies to overcome the adoption threshold. That was precisely the topic of my PhD dissertation, and I concur that the Adapteva guys have chosen a sound approach. But Epiphany is not a dataflow architecture, and suffers from execution efficiency problems in individual cores. Dataflow is really the way to go to lower energy consumption dramatically. Funny this topic comes up. It just happens the EU has recently invested in such a project to co-design a dataflow processor and software stack. It was north of a million euros for the initial proof-of-concept research, and the results are slowly starting to trickle through. Some references: - http://staff.science.uva.nl/~poss/pub/poss.12.dsd.pdf http://staff.science.uva.nl/~poss/pub/poss.12.dsd.pdf - http://staff.science.uva.nl/~poss/pub/poss.13.micpro.pdf http://staff.science.uva.nl/~poss/pub/poss.13.micpro.pdf (I am one of the authors; ping me for more information)

jacques_chester 14y ago

I'm reminded a bit of the logic that lead to Itanium: all this silicon dedicated to doing voodoo mind reading on linear machine code is wasteful. Let's instead push parallelism up into the compilers. It didn't quite work out that way, but as a handy side effect it killed off PA-RISC and Alpha with little more than a few press releases.

protomyth 14y ago
I often wonder if it was the theory that was broken or the implementation? I doubt anyone will tread that way for quite a while due to the wreckage.
- jacques_chester 14y ago
  Basically, Intel & HP bet on the appearance of "Sufficiently Smart Compilers". And they didn't turn up. Most of the code people want to run on high CPUs is written in C or Fortran. Producing correct parallel code from branchy, pointer-filled, shared-everything codebases is difficult. Basically they gambled on the mother of all handwaves and lost.

jbrennan 14y ago

I feel like you could do even better if you approached a language design from the other side, instead of focussing on the lower-level aspects to instead be thinking of higher level aspects. If I were designing a programming language, I would start with what the development environment would look like, what tools do I want to build to support development in the language, etc., and then build the language to support that. It seems so often languages are built, and then the tools are an afterthought, things like debugging, visualizing program flow, code assist, whatever it may be. What if program flow (that is, what's going on inside the program) were in mind from the start, instead of something you try and add later. Just my thoughts. Is this a feasible way to design a language?

MattJ100 14y ago
Depends what your goal is. Your approach is to optimize for developer productivity. Mike's is to optimize for machine productivity. The question is whether it is possible to do both at once, hence Mike's point about the ideal language needing to find the right high-level abstractions (machine-efficient and developer-intuitive). What we currently have is somewhere in-between, but more towards the machine-efficient side. It's quite easy to produce inefficient code, without realising it, in today's high-level languages.
- jbrennan 14y ago
  >Your approach is to optimize for developer productivity. Mike's is to optimize for machine productivity. Yeah that's a valid point. And it's probably just my lack of experience in language design or just general naïveté. It seems like for most devices (modern smartphones, tablets, traditional computers) are fast enough that we'd be better served focusing on developer productivity in newer languages. Sure, they'll never compete with C in terms of efficiency. Besides, I can still easily create terribly inefficient code in C ;)
  - justincormack 14y ago
    Devices maybe but servers less so, if you can get a 100x performance increase from going g from say PHP to LuaJIT then you can save a lot of money without a productivity loss.

asb 14y ago

I still don't understand the policy of editors changing post titles here. The original title was "Mike Pall (LuaJIT) on programming language design". Maybe "Ramblings on languages and architectures" like the original posting is better, but I don't see the win in removing the author's name from it. After all, the reason we're all initially interested is that these thoughts are from Mike Pall, author of perhaps the most impressive dynamic language JIT.

imsofuture 14y ago
At this point, why is there even a title field available?
asb 14y ago
One of the anonymous editors has added back "Mike Pall" to the title. Thanks.

mwcampbell 14y ago

Would a CPU architecture that executed LLVM bitcode, or some other encoding of LLVM IR, be significantly less wasteful than what we have now? I wonder because LLVM IR is already SSA-based and is designed for optimization passes in a compiler. And it exists and is used today.

wmf 14y ago

Check out the TRIPS/EDGE architecture: http://www.cs.utexas.edu/~trips/overview.html http://www.cs.utexas.edu/~trips/overview.html It uses dataflow to efficiently execute individual instructions while atomically committing groups of instructions to preserve understandable semantics. While tiled architectures are common now, most of them have one core per tile. TRIPS built a large, high-performance core out of simple tiles so it can run different types of code efficiently.

microarchitect 14y ago
That link is missing their evaluation of TRIPS, which they did in 2008 after they built the chips: http://www.cs.utexas.edu/~bmaher/pubs/asplos09.pdf http://www.cs.utexas.edu/~bmaher/pubs/asplos09.pdf My impression is that TRIPS is much too complicated to be clocked at comparable frequencies to commercial processors. Their ISA also appears very hard to compile to.

craigyk 14y ago

Mike Pall was the first person I've ever met (via his postings and projects) that made me think, holy cow, this dude is way smarter than me. I've heard some people conjecture that it's actually a pseudonym for a group of people.... but I actually prefer to think it's one guy, by himself, getting awesome shit done.

justincormack 14y ago
"Some people" includes Roberto Ierusalimschy, the inventor of Lua, although he told me he now knows someone who has met Mike so he believes he is actually a singleton.