Mike Pall: Ramblings on languages and architectures

http://www.freelists.org/post/luajit/Ramblings-on-languages-and-architectures-was-Re-any-benefit-to-throwing-off-lua51-constraints

by asb • 13 years ago

146 96 13 years ago

freelists.org

mwcampbell6• 13 years 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).

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.

catwell2• 13 years 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....

cwzwarich2• 13 years 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• 13 years ago

I always considered CPS and SSA to be duals. (Just like FST and Lambda-calculus are duals)

mikemike3• 13 years 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 ... and the particular mix simply doesn't appeal to me personally.

DanWaterworth11• 13 years 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.

yvdriess10• 13 years 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

mwcampbell6• 13 years ago

Would Standard ML be a suitable language for the kind of research you describe?

radm2• 13 years ago

But these kinds of languages do exist and it's reasonable to think about writing compilers for them and/or subsets.

triplepoint2172• 13 years ago

> Relying on lazy semantics also wrecks parallelism, because some evaluation branches cannot be visited ahead of time, without changing the program's semantics.

For a pure functional language, like Haskell, speculatively evaluating pieces of it in parallel shouldn't hurt anything (since they are guaranteed not to have side effects).

It is my understanding that the lazy semantics of Haskell mostly mean that you shouldn't be making any assumptions about the order of evaluation which would seem to be useful from an optimization perspective.

I am still new to FP and Haskell, so please correct me if I am misinterpreting things.

riffraff• 13 years 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• 13 years ago

Doesn't an FP language without reassignment imply the existence of a function like phi to perform nontrivial control flow?

yvdriess10• 13 years 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.

mikemike3• 13 years 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• 13 years 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.

yvdriess10• 13 years ago

Indeed. Many, lacking compiler research know-how, just make it a graph-encoding language, which is really not the point of dataflow. Any language trivially mapping to SSA semantics is already a dataflow language, essentially.

SISAL isn't all that bad, ignoring the 80's syntax:

  function BottlesOfBeer(i : integer returns array[string])
    let
      s,bottles,preface,n,nextbottles :=
        if i = 1 then
          "1"," bottle","If that bottle","No more"," bottles"
         elseif i = 2 then
           itoa(2)," bottles","If one of those bottles",itoa(1)," bottle"
         else
           itoa(i)," bottles","If one of those bottles",itoa(i-1)," bottles"
         end if;
    in
      array[1:
        s || bottles || " of beer on the wall", 
        s || bottles || " of beer!",
        preface || " should happen to fall... ",
        n || nextbottles || " of beer on the wall!",
        ""
      ]
    end let
  end function

jackrusher• 13 years ago

We built a dataflow system for Complex Event Processing (CEP) at one of my previous startups. It included both a visual programming GUI and a non-hideous programming language called SPLASH that allowed one to code nodes of the dataflow graph. The product is now known as the SAP Sybase Event Stream Processor, and this page has an example of SPLASH: http://www.sybase.com/products/financialservicessolutions/co...

(Jon Riecke <http://scholar.google.com/citations?user=lSdHdpUAAAAJ&hl...; did most of the work on the language.)

Serow2252• 13 years ago

You mentioned in your original post that pure visual programming languages have issues, and having a ton of experience with one (Simulink), I wouldn't disagree - especially as the 'codebase' size increases. However a hybrid visual/code approach can work quite well, in my experience; see Stateflow and MATLAB Coder, which are embedded within the graphical Simulink environment.

mikeei• 13 years ago

Very interesting track for somebody eager to learn. May I consider Alice ML and Mozart Oz to be examples of textual data-flow languages. I wonder why these research projects have obv. slowed down resp. never really took off.

P.S.: I was fascinated after reading Peter van Roys book some time ago and still wonder about this a bit disappointed.

qznc• 13 years 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?

DanWaterworth11• 13 years 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.

mikeash3• 13 years ago

What kind of input language would be both useful for general computation and not Turing-complete?

DanWaterworth11• 13 years 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.

williamaadams2• 13 years 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.

yvdriess10• 13 years 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.

williamaadams2• 13 years 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_chester5• 13 years 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

[2] http://en.wikipedia.org/wiki/Rekursiv

[3] http://en.wikipedia.org/wiki/Transputer

knz426• 13 years 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.13.micpro.pdf

(I am one of the authors; ping me for more information)

jacques_chester5• 13 years 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• 13 years 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_chester5• 13 years 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.

jbrennan3• 13 years 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• 13 years 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.

jbrennan3• 13 years 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 ;)

mamcx• 13 years ago

I think the same. I have dream to build one myself, but lack the expertise and the time for it. However, I think on it very similar to how build a "normal" app: The end-user, thinking in the most tedious work (like debugging, pass data & transformation, etc) then think in how could be it write. In fact I look at my past projects and try to remember what were the parts that waste more time...

But is certainly harder than think: How make recursion?

asb2• 13 years 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• 13 years ago

At this point, why is there even a title field available?

asb2• 13 years ago

One of the anonymous editors has added back "Mike Pall" to the title. Thanks.

mwcampbell6• 13 years 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• 13 years ago

Check out the TRIPS/EDGE architecture: 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• 13 years 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

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• 13 years 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.

justincormack2• 13 years 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.

Mike Pall: Ramblings on languages and architectures

Related Stories