Limiting the scope for my own sanity here, there may yet be some application in various hardware level emulations of continuation passing calculi, perhaps building on static single assignment. It might be possoble to derive an interesting instruction set from the sorts of intermediate representations we see in compiler infrastructures like LLVM, but it is hard to guess how these hardware designs would benefit haskell, rather than the other way around. Cheers, Darren On Jan 19, 2016 14:44, "Auke Booij" wrote:

This question is much more involved than you seem to be suggesting. It's not just about adding "some instructions for Haskell support". You have to think about how you want to express /every/ haskell term as a series of bits (preferably predictably many bits), and find a (finite) combination of logical gates to do arbitrary computations with them.

If you want to go anywhere in this directions, perhaps a good start would be implementing a processor with instructions for (untyped) lambda calculus. One approach for this could be to take a (mathematical) model of lambda calculus and see how its elements can be represented as natural numbers.

This implementation, I suspect, would be terribly inefficient. Think about what the lambda application gate would look like in terms of NAND gates. Yes, it can probably be done in theory. No, it won't be pretty. And forget about practical.

Finally, a major advantage of having such "raw" language as an instruction set is that it allows many many optimizations (e.g. pipelining (which, I would say, is the single most important reason that processors are able to run at GHzs instead of MHzs (Pentium 4 processors, famed for their high clock speed, had 31 pipeline stages))) that I cannot imagine being possible in anything close to a "lambda calculus processor".

What is the added value you hope to achieve?

On 19 January 2016 at 22:12, Henning Thielemann wrote:

...

Hi all,

every now and then I think it would be cool to have a microprocessor that supports Haskell in a way. A processor where lazy evaluation is not

...

but an optimization opportunity, a processor that can make use of the explicit data dependencies in Haskell programs in order to utilize many computation units in parallel. I know of the Reduceron project, which evolves only slowly and if it somewhen is ready for use it is uncertain whether it can compete with stock CPUs since FPGA's need much more chip space for the same logic.

I got to know that in todays x86 processors you can alter the instruction set, which is mainly used for bugfixes. Wouldn't it be interesting to add some instructions for Haskell support? However, I suspect that such a

...

might be rendered invalid by new processor generations with changed internal details. Fortunately, there are processors that are designed for custom instruction set extensions: https://en.wikipedia.org/wiki/Xtensa

Would it be sensible to create a processor based on such a design? I have no idea what it might cost, and you would still need some peripheral circuitry to run it. What could processor instructions for Haskell support look

overhead patch like?

...

Has anyone already thought in this direction? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

---

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

On 20/01/2016, at 12:03 pm, Henning Thielemann wrote:

I am not thinking about a radically different machine language, just a common imperative machine language with some added instructions for tasks often found in machine code generated from Haskell. E.g. mainstream processors support C function calls with special jump instruction and stack handling. Maybe there could be instructions that assist handling thunks or Haskell function calls.

I was at a presentation once where the speaker showed how (thanks to the fact that Prolog doesn't evaluate arguments in calls) calling a procedure and executing the procedure could be overlapped, getting a factor of 2 speedup for an important part of the code. At another presentation a speaker showed how using a special outboard coprocessor could dramatically speed up memory management. I suspect that neither technique would be much help on today's machines and for Haskell. However, there is a hint here that doing something quite different might pay off. For example, if branch predictors don't do well with thunk handling, maybe there is a way of processing thunks that a quite different kind of branch predictor *might* cope with. Or maybe something that's expecting to process thousands of microthreads might not care about branch prediction. (Although that idea has been tried as a way of handling memory latency, I don't think it's been tried for Haskell.) Perhaps you might look for something different; instead of 'faster on similar hardware' you might look at 'cheaper'. Could a specialised Haskell processor use less energy than a standard CPU? Don't quit your day job, but don't be too sure there's nothing left to think of either.

You are unneccessary overly pessimistic, let me show you somethings you, probably, have not thought or heard about. 2016-01-20 10:51 GMT+03:00 Joachim Durchholz :

Am 19.01.2016 um 23:12 schrieb Henning Thielemann:

...

Fortunately, there are processors that are designed for custom instruction set extensions: https://en.wikipedia.org/wiki/Xtensa

Unfortunately, the WP article does not say anything that couldn't be said about, say, an ARM core. Other than that Xtensa core being some VLIW design.

Would it be sensible to create a processor based on such a design?

...

Very, very unlikely, for multiple reasons.

Special-purpose CPUs have been built, most notably for LISP, less notably for Java, and probably for other purposes that I haven't heard of. Invariably, their architectural advantages were obsoleted by economy of scale: Mainstream CPUs are being produced in such huge numbers that Intel etc. could affort more engineers to optimize every nook and cranny, more engineers to optimize the structure downscaling, and larger fabs that could do more chips on more one-time expensive but per-piece cheap equipment, and in the end, the special-purpose chips were slower and more expensive. It's an extremely strong competition you are facing if you try this.

Also, it is very easy to misidentify the actual bottlenecks and make instructions for the wrong ones. If caching is the main bottleneck (which it usually is), no amount of CPU improvement will help you and you'll simply need a larger cache. Or, probably, a compiler that knows enough about the program and its data flow to arrange the data in a cache-line-friendly fashion.

A demonstration from the industry, albeit not quite hardware industry: http://www.disneyanimation.com/technology/innovations/hyperion - "Hyperion handles several million light rays at a time by sorting and bundling them together according to their directions. When the rays are grouped in this way, many of the rays in a bundle hit the same object in the same region of space. This similarity of ray hits then allows us – and the computer – to optimize the calculations for the objects hit." Then, let me bring up an old idea of mine: https://mail.haskell.org/pipermail/haskell-cafe/2009-August/065327.html Basically, we can group identical closures into vectors, ready for SIMD instructions to operate over them. The "vectors" should work just like Data.Vector.Unboxed - instead of vector of tuple of arguments there should be a tuple of vectors with individual arguments (and results to update for lazy evaluation). Combine this with sorting of addresses in case of references and you can get a lot of speedup by doing... not much.

I do not think this is going to be a long-term problem though. Pure languages have huge advantages for fine-grained parallel processing, and CPU technology is pushing towards multiple cores, so that's a natural match. As pure languages come into more widespread use, the engineers at Intel, AMD etc. will look at what the pure languages need, and add optimizations for these.

Just my 2 cents. Jo

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

More info on microcode updates can be found in https://www.dcddcc.com/pubs/paper_microcode.pdf Salient points: - Microcode is entirely undocumented. - Microcode is indeed encrypted, though there seem to be loopholes. - Microcode update times can take up to 2 million CPU cyles. - Microcode updates could be an unexpected attack vector. Maybe. Regards, Jo