8 ms·

You've at least heard of (if not used) a programming language heavily inspired by Miranda: Haskell. A lot of things about Miranda were really interesting; it re

by kick 7y ago

You've at least heard of (if not used) a programming language heavily inspired by Miranda: Haskell. A lot of things about Miranda were really interesting; it reflects modern languages in some ways, but looks completely foreign in other ways. Like Haskell, whitespace was significant; unlike Haskell, it was fast. Really fast. It was one of the pioneering purely-functional languages, but seems to have been mostly forgotten. That's unfortunate, because in many ways it still is superior to its successors. Their fault for keeping it proprietary for so long, really.

msie 7y ago
The language was such a pleasure to use in university in the early 90’s. Those were the days where you paid for compilers. My prof was grumbling about the licensing fees for Miranda though.
- kick 7y ago
  Yeah, it was a bit ridiculous. Incredibly good software compared to what we've got now, though.
agumonkey 7y ago
how come it was so much faster ? smaller semantics allowing for more optimizations ? or some obscure reason ?
- kick 7y ago
  Short: Haskell made a bunch of poor design decisions that they've since doubled down on, the fastest implementation isn't very good, the art of writing compilers and interpreters has effectively been lost, and Miranda was written by and designed by professionals.
  - jolux 7y ago
    "the art of writing compilers and interpreters has effectively been lost" I'm curious, how does that happen? Were the techniques used in compilers and interpreters of yore never recorded for posterity in academic papers or technical documentation?
    - kick 7y ago
      Spent a good while thinking on your question: The best stuff was all proprietary for decades. Even now, we only got Miranda's source code weeks ago. Miranda was written in the 1980s! It's the same for a lot of languages. Nial's the example I usually bring up for one that was freed far too late. People with the domain knowledge that would have helped deal with the complexity of modern systems are all either retired, have ditched PL-design, or have died. Turbo Pascal, too, although that one's kind of strange because the author of it later went on to do a complete 180° turn while still working in PL design and implementation (plus it was never freed). Ken Thompson's cc suite for Plan 9 was behind a million-dollar license fee until a decade ago, and it wasn't even for any modern CPUs. He once quit the industry to become a flight instructor; he's at Google, but he's retired now. The best advice is "Stay small!" which most Free Software compilers seem to be violently against. It's not their fault, though: it's hard not to take new code when it's offered to you! We'll probably never see the source code behind any version of the k interpreter by Arthur Whitney, and trying to get an interview with him is like going on a snipe hunt, so good luck figuring out anything about his approach besides "Small!" It doesn't help that Kx sues the hell out of anyone who's actually seen the k source and tries implementing anything remotely like it that's not a toy. Every modern compiler is for multiple architectures in convoluted ways. This is generally a terrible idea, especially with how divergent they're getting in the times we're in, even between chips that have the same instruction set. Intel x86_64 processors aggressively speculate almost as intensely as Transmeta did back in the day, but we're still treating them and AMD chips more or less the same, and we're using the same compilers that we're using on that instruction set for RISC-V and for ARM and for Itanium and for obscure 16-bit CPUs and so on. Portable compilers aren't bad in principle, but when you look at pcc compared to GCC you'll see exactly where we went wrong: pcc wasn't very optimized, it was simple, and it was understandable. Great for bootstrapping. Not great for getting the most out of your CPU. Having portable compilers that try to heavily optimize is a mistake. No one seems to know what a CPU cache is! And how many compilers do you know that compile to C, or to LLVM bytecode or similar? It's insane: nobody should be doing that! That approach doesn't make much sense! And the only argument any of these people can make is "But our language is too big for it to be practical to write something unique for each architecture! Piggybacking makes it way quicker!" No one seems to realize that their languages are getting too large. They aren't even getting too large in a graceful way: Common Lisp is probably the biggest language there is, but it's extremely portable, and is easy to write an interpreter for. Things got complicated really fast, and domain knowledge was sort of lost in the waves of proprietary compilers as they were destroyed by GCC. I appreciate that free software "won" to some extent, but if it hadn't have won as fast, we might have had some knowledge transfer happen that was actually useful. Walter Bright isn't doing magic, but he and the people he work with seem to be some of the only people in Free Software who are making a compiler that's fast and good in the x86_64 world.
  - greydius 7y ago
    Would you mind elaborating on these points?
    - kick 7y ago
      I have for most of it elsewhere in this thread (I think you can find my answers by checking my /comments), but for what I didn't get to, I'll get to tomorrow. My responses are getting worse as I tire.
- asdkjh345 7y ago
  It isn't, it is much slower. Download them both and try a few tests for yourself, GHC produces much faster binaries.
bakul 7y ago
I learned about Miranda from the appendix of "The Implementation of Functional Programming Languages" 1987 book by Simon Peyton Jones (IIRC one can find a PDF copy online). I liked it a lot though I had no access to its implementation. Glad to know it is now available. Its implementation is small by today's standards!
- soegaard 7y ago
  Ditto!
voldacar 7y ago
Are there any more modern functional languages that are as fast or faster?
- kick 7y ago
  k, J & APL, in roughly that order.
  - voldacar 7y ago
    APL is cheating since all the magic happens in highly pipelined SIMD-heavy loops :p but if it's really true that other than array languages, no modern FP language can outperform Miranda then that's really depressing. I was under the impression that GHC attempted to generate decently good code, maybe it's all the little allocations that slow Haskell down or something like that.
    - kick 7y ago
      APL isn't cheating because of that, it's cheating because it's small enough to fit in your CPU cache! I'm sure something else can beat Miranda, I'm just unsure of what. I don't really care for the FP paradigm outside of arrays and Lisp, though, so I'll be the first to admit that I haven't spent days looking; just a few hours here and there. Oh, actually: Stalin probably does. It's an R4RS compiler. Good luck getting it to compile, though. It took me a few hours and a lot of code changes to get it to compile half a decade ago (I wanted to compare the one I was writing, which was a lot worse, naturally, but much easier to compile). The compiler itself is slow as a tortoise, but it generates really wonderful code. It's probably rotted a bit now, though.
      - mlochbaum 7y ago
        No, it's the SIMD loop thing. The claim that k runs quickly because its functions fit in the CPU cache is, as far as I can tell, an off-hand comment that Arthur Whitney made once which has been repeated far more than it deserves. It's false—instruction cache behavior doesn't contribute significantly to k's advantage over other languages—for a few reasons: inner loops in array languages are 3–5 orders of magnitude smaller than the CPU cache, the loops that compiled languages produce also fit in cache, and instruction caching doesn't matter all that much for performance anyway. Despite spending plenty of time looking for it, I've never been able to measure an impact of code size on performance. Even data caching doesn't have that much of an effect: current versions of Dyalog APL almost always allocate new arrays from uncached memory (this is mostly fixed in the next version), and it's still one of the fastest array languages around. Unless you're using SIMD, code with linear access patterns can't even keep up with main memory, and the cache has no effect. Why is using SIMD cheating? SIMD loops are the only way to get the full performance out of a CPU, and fast compilers do try to produce them. If it turns out that array-based interpreters are a better way to convert programmer intentions to SIMD loops than scalar compilers (and it certainly seems that way) then the array languages are legitimately faster. I suppose SIMD is considered "non-portable" because you can't use it from C, but that's an artificial restriction coming from historical programming language design decisions. The most important vector instructions are the same in any modern vector ISA. How is using standard CPU features cheating? They're not even that much newer than double-precision float support. (I'm an implementor for Dyalog APL.)
rixed 7y ago
Do you mean that the compiler was fast or that the generated programs were fast? Do we have a competitor for Clean?
- kick 7y ago
  Clean was directly inspired by Miranda.
- rixed 7y ago
  Answering to myself: the provided implementation is an interpreter only.
wk_end 7y ago
You've made several comments here suggesting that GHC - pretty widely considered an extremely powerful compiler - is inferior to what Miranda offers. Can you substantiate your claim that Miranda is faster than Haskell/GHC? FWIW, I just tried doing a very quick dumb benchmark - the classic functional pseudo-quicksort. GHC spit out a binary that can sort 10,000,000 numbers in a few seconds on my laptop. Miranda (after cranking up the heap size a couple orders of magnitude) took noticeably more time to sort only 1,000,000.
- kick 7y ago
  I promise I'll respond to this in the morning, I'm very tired right now and don't want to give a good and reasonable question an answer that hasn't been thought out well, especially given that my responses have been getting less detailed and concise as I've gotten more tired.
- fanf2 7y ago
  Oh wow, Miranda is still using an SK combinator reduction evaluator dating from 1986, in K&R C. It isn't even using supercombinators, which I read about in https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/ https://www.microsoft.com/en-us/research/publication/the-imp... Combinators are fun, but not very fast :-) https://dl.acm.org/doi/10.1145/800087.802798 https://dl.acm.org/doi/10.1145/800087.802798 http://ioccc.org/years.html#1998_fanf http://ioccc.org/years.html#1998_fanf
- ncmncm 7y ago
  Just for comparison, C++ running the shortest, simplest possible quicksort does 100,000,000 32-bit ints in 8s. Three more lines, and it's 3.4s. That's 1.3ns each time it looks at an element. So when you are already giving up an order of magnitude or two, another doesn't matter so much. It pays then to steer the conversation toward other merits.
  - yatac42 7y ago
    > C++ and the shortest, simplest possible quicksort wk_end was talking about "functional pseudo-quicksort" on immutable linked lists. You're presumably talking about a proper quicksort on mutable arrays. That's comparing apples to oranges. And even if you weren't, how is that an argument? Person A says "X is faster than Y", then person B says "Actually I just ran X and it took 10x longer than Y" and then you say "Well Z, which isn't even part of this discussion, is 1000x faster than both X and Y, so your argument is invalid". How does that follow?

by kick 7y ago

msie 7y ago

The language was such a pleasure to use in university in the early 90’s. Those were the days where you paid for compilers. My prof was grumbling about the licensing fees for Miranda though.

kick 7y ago
Yeah, it was a bit ridiculous. Incredibly good software compared to what we've got now, though.

agumonkey 7y ago

how come it was so much faster ? smaller semantics allowing for more optimizations ? or some obscure reason ?

kick 7y ago
Short: Haskell made a bunch of poor design decisions that they've since doubled down on, the fastest implementation isn't very good, the art of writing compilers and interpreters has effectively been lost, and Miranda was written by and designed by professionals.
- jolux 7y ago
  "the art of writing compilers and interpreters has effectively been lost" I'm curious, how does that happen? Were the techniques used in compilers and interpreters of yore never recorded for posterity in academic papers or technical documentation?
  - kick 7y ago
    Spent a good while thinking on your question: The best stuff was all proprietary for decades. Even now, we only got Miranda's source code weeks ago. Miranda was written in the 1980s! It's the same for a lot of languages. Nial's the example I usually bring up for one that was freed far too late. People with the domain knowledge that would have helped deal with the complexity of modern systems are all either retired, have ditched PL-design, or have died. Turbo Pascal, too, although that one's kind of strange because the author of it later went on to do a complete 180° turn while still working in PL design and implementation (plus it was never freed). Ken Thompson's cc suite for Plan 9 was behind a million-dollar license fee until a decade ago, and it wasn't even for any modern CPUs. He once quit the industry to become a flight instructor; he's at Google, but he's retired now. The best advice is "Stay small!" which most Free Software compilers seem to be violently against. It's not their fault, though: it's hard not to take new code when it's offered to you! We'll probably never see the source code behind any version of the k interpreter by Arthur Whitney, and trying to get an interview with him is like going on a snipe hunt, so good luck figuring out anything about his approach besides "Small!" It doesn't help that Kx sues the hell out of anyone who's actually seen the k source and tries implementing anything remotely like it that's not a toy. Every modern compiler is for multiple architectures in convoluted ways. This is generally a terrible idea, especially with how divergent they're getting in the times we're in, even between chips that have the same instruction set. Intel x86_64 processors aggressively speculate almost as intensely as Transmeta did back in the day, but we're still treating them and AMD chips more or less the same, and we're using the same compilers that we're using on that instruction set for RISC-V and for ARM and for Itanium and for obscure 16-bit CPUs and so on. Portable compilers aren't bad in principle, but when you look at pcc compared to GCC you'll see exactly where we went wrong: pcc wasn't very optimized, it was simple, and it was understandable. Great for bootstrapping. Not great for getting the most out of your CPU. Having portable compilers that try to heavily optimize is a mistake. No one seems to know what a CPU cache is! And how many compilers do you know that compile to C, or to LLVM bytecode or similar? It's insane: nobody should be doing that! That approach doesn't make much sense! And the only argument any of these people can make is "But our language is too big for it to be practical to write something unique for each architecture! Piggybacking makes it way quicker!" No one seems to realize that their languages are getting too large. They aren't even getting too large in a graceful way: Common Lisp is probably the biggest language there is, but it's extremely portable, and is easy to write an interpreter for. Things got complicated really fast, and domain knowledge was sort of lost in the waves of proprietary compilers as they were destroyed by GCC. I appreciate that free software "won" to some extent, but if it hadn't have won as fast, we might have had some knowledge transfer happen that was actually useful. Walter Bright isn't doing magic, but he and the people he work with seem to be some of the only people in Free Software who are making a compiler that's fast and good in the x86_64 world.
- greydius 7y ago
  Would you mind elaborating on these points?
  - kick 7y ago
    I have for most of it elsewhere in this thread (I think you can find my answers by checking my /comments), but for what I didn't get to, I'll get to tomorrow. My responses are getting worse as I tire.
asdkjh345 7y ago
It isn't, it is much slower. Download them both and try a few tests for yourself, GHC produces much faster binaries.

bakul 7y ago

I learned about Miranda from the appendix of "The Implementation of Functional Programming Languages" 1987 book by Simon Peyton Jones (IIRC one can find a PDF copy online). I liked it a lot though I had no access to its implementation. Glad to know it is now available. Its implementation is small by today's standards!

soegaard 7y ago
Ditto!

voldacar 7y ago

Are there any more modern functional languages that are as fast or faster?

kick 7y ago
k, J & APL, in roughly that order.
- voldacar 7y ago
  APL is cheating since all the magic happens in highly pipelined SIMD-heavy loops :p but if it's really true that other than array languages, no modern FP language can outperform Miranda then that's really depressing. I was under the impression that GHC attempted to generate decently good code, maybe it's all the little allocations that slow Haskell down or something like that.
  - kick 7y ago
    APL isn't cheating because of that, it's cheating because it's small enough to fit in your CPU cache! I'm sure something else can beat Miranda, I'm just unsure of what. I don't really care for the FP paradigm outside of arrays and Lisp, though, so I'll be the first to admit that I haven't spent days looking; just a few hours here and there. Oh, actually: Stalin probably does. It's an R4RS compiler. Good luck getting it to compile, though. It took me a few hours and a lot of code changes to get it to compile half a decade ago (I wanted to compare the one I was writing, which was a lot worse, naturally, but much easier to compile). The compiler itself is slow as a tortoise, but it generates really wonderful code. It's probably rotted a bit now, though.
    - mlochbaum 7y ago
      No, it's the SIMD loop thing. The claim that k runs quickly because its functions fit in the CPU cache is, as far as I can tell, an off-hand comment that Arthur Whitney made once which has been repeated far more than it deserves. It's false—instruction cache behavior doesn't contribute significantly to k's advantage over other languages—for a few reasons: inner loops in array languages are 3–5 orders of magnitude smaller than the CPU cache, the loops that compiled languages produce also fit in cache, and instruction caching doesn't matter all that much for performance anyway. Despite spending plenty of time looking for it, I've never been able to measure an impact of code size on performance. Even data caching doesn't have that much of an effect: current versions of Dyalog APL almost always allocate new arrays from uncached memory (this is mostly fixed in the next version), and it's still one of the fastest array languages around. Unless you're using SIMD, code with linear access patterns can't even keep up with main memory, and the cache has no effect. Why is using SIMD cheating? SIMD loops are the only way to get the full performance out of a CPU, and fast compilers do try to produce them. If it turns out that array-based interpreters are a better way to convert programmer intentions to SIMD loops than scalar compilers (and it certainly seems that way) then the array languages are legitimately faster. I suppose SIMD is considered "non-portable" because you can't use it from C, but that's an artificial restriction coming from historical programming language design decisions. The most important vector instructions are the same in any modern vector ISA. How is using standard CPU features cheating? They're not even that much newer than double-precision float support. (I'm an implementor for Dyalog APL.)

rixed 7y ago

Do you mean that the compiler was fast or that the generated programs were fast? Do we have a competitor for Clean?

kick 7y ago
Clean was directly inspired by Miranda.
rixed 7y ago
Answering to myself: the provided implementation is an interpreter only.

wk_end 7y ago

You've made several comments here suggesting that GHC - pretty widely considered an extremely powerful compiler - is inferior to what Miranda offers. Can you substantiate your claim that Miranda is faster than Haskell/GHC? FWIW, I just tried doing a very quick dumb benchmark - the classic functional pseudo-quicksort. GHC spit out a binary that can sort 10,000,000 numbers in a few seconds on my laptop. Miranda (after cranking up the heap size a couple orders of magnitude) took noticeably more time to sort only 1,000,000.

kick 7y ago
I promise I'll respond to this in the morning, I'm very tired right now and don't want to give a good and reasonable question an answer that hasn't been thought out well, especially given that my responses have been getting less detailed and concise as I've gotten more tired.
fanf2 7y ago
Oh wow, Miranda is still using an SK combinator reduction evaluator dating from 1986, in K&R C. It isn't even using supercombinators, which I read about in https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/ https://www.microsoft.com/en-us/research/publication/the-imp... Combinators are fun, but not very fast :-) https://dl.acm.org/doi/10.1145/800087.802798 https://dl.acm.org/doi/10.1145/800087.802798 http://ioccc.org/years.html#1998_fanf http://ioccc.org/years.html#1998_fanf
ncmncm 7y ago
Just for comparison, C++ running the shortest, simplest possible quicksort does 100,000,000 32-bit ints in 8s. Three more lines, and it's 3.4s. That's 1.3ns each time it looks at an element. So when you are already giving up an order of magnitude or two, another doesn't matter so much. It pays then to steer the conversation toward other merits.
- yatac42 7y ago
  > C++ and the shortest, simplest possible quicksort wk_end was talking about "functional pseudo-quicksort" on immutable linked lists. You're presumably talking about a proper quicksort on mutable arrays. That's comparing apples to oranges. And even if you weren't, how is that an argument? Person A says "X is faster than Y", then person B says "Actually I just ran X and it took 10x longer than Y" and then you say "Well Z, which isn't even part of this discussion, is 1000x faster than both X and Y, so your argument is invalid". How does that follow?