5 ms·

Common Lisp doesn’t just have LOOP, it also has Series [1]. I think the actual philosophical difference may be that Haskell does this with compiler support for

by wrs 6y ago

Common Lisp doesn’t just have LOOP, it also has Series [1]. I think the actual philosophical difference may be that Haskell does this with compiler support for stream function composition, whereas Common Lisp does it with a set of language-level macros any user could write (if they were as smart as Richard Waters). [1] https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node347.html https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node347.html

_delirium 6y ago
To get a feel for how these compare, the Common Lisp Cookbook gives some examples for how to do different common operations using the loop, series, and iterate packages: https://lispcookbook.github.io/cl-cookbook/iteration.html https://lispcookbook.github.io/cl-cookbook/iteration.html
dllthomas 6y ago
Stream fusion in Haskell is done with rewrite rules. On the one hand, it's totally true that you're no longer really writing Haskell, and the facility for rewrite rules itself needed (at some point) to be added to the compiler. But at this point I can make my own data structures fuse (potentially in new ways) without further changes to the compiler. https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#rewrite-rules https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...
dan-robertson 6y ago
Strictly speaking, Common Lisp does not have series because they were not included in ANSI Common Lisp. Therefore even though you could use the macros provided with a separate streams package, you’d need to make sure that all your code used that package (rather than the CL definitions of let and lambda and so on) and properly declared stream functions. This ends up making code using streams not super composable which isn’t great. I also think it’s a bit unfair to say that Haskell’s stream fusion requires special compiler support. The compiler doesn’t recognise list functions specifically or have special cases for list-looking-types (except for syntax). Instead there is a general mechanism to say “at stage number x, replace expressions that look like y with z”, where there are something like 10 stages and expressions y and z are type checked so these transformations are only applied in “valid” cases. I think saying that this is special compiler support for stream fusion is like saying that macros are special compiler support for series in CL. A final thing to note is that because of lazy evaluation, stream fusion in Haskell doesn’t change the semantics of the Haskell list functions from how they would behave without it. In Common Lisp streams must be explicitly separated from lists because they are semantically different (in the evaluation order of the functions that act on them).
- wrs 6y ago
  My impression was some of those expressions were added to the compiler specifically to make stream fusion work well enough to use. Even if so, it’s a good point that laziness makes streams more “natural” in Haskell so that was just a performance improvement, not a semantic change. Certainly laziness is a big “philosophical difference” between the two!
  - eru 6y ago
    Yes. And laziness works because Haskell is pure-by-default. Yes. Though if we were starting from scratch today, perhaps we would see a total language, ie one where all functions terminate. That would allow the compiler much more freedom in how to order evaluation.
- reikonomusha 6y ago
  GHC does have special support for fusion and rewriting. See e.g. [1]. The laziness comes with the language, but turning it efficient requires a series of these rewrite rules expressed as GHC-specific metadata. [1] https://markkarpov.com/tutorial/ghc-optimization-and-fusion.html#rewrite-rules https://markkarpov.com/tutorial/ghc-optimization-and-fusion....
  - sukilot 6y ago
    GHC is the most complicated compiler of any language (or very near to it), except perhaps Mathematica which is similar: It's an optimizer for a graph-reduction engine. It doesn't mean much to call out "special support" for any one bit of style of programming, since the language itself has nearly no concept of performance -- you just write functional code and the compiler will find the fastest runtime computation of the evaluation that it can.
    - eru 6y ago
      > It doesn't mean much to call out "special support" for any one bit of style of programming, since the language itself has nearly no concept of performance -- you just write functional code and the compiler will find the fastest runtime computation of the evaluation that it can. While GHC is glorious, it's still very limited in what it can do, performance wise. You are right that languages themselves seldom have a direct concept of performance. But language features and restrictions have a big impact on achievable performance. Eg Haskell's purity-by-default means that the compiler has quite a bit of freedom when choosing how to translate something like eg the 'map' or 'filter' functions. The equivalent in C++ gives the compiler less flexibility, because the helper function handed over at runtime might have side-effects. Similarly, Haskell functions are still allowed one important side effect: non-determination. In a more restricted language like Agda that's not allowed. Thus giving the compiler more degrees of freedom to work with. Or in a different direction: the query optimizers for SQL can do very impressive work, because SQL is so limited.

by wrs 6y ago

_delirium 6y ago

To get a feel for how these compare, the Common Lisp Cookbook gives some examples for how to do different common operations using the loop, series, and iterate packages: https://lispcookbook.github.io/cl-cookbook/iteration.html https://lispcookbook.github.io/cl-cookbook/iteration.html

dllthomas 6y ago

Stream fusion in Haskell is done with rewrite rules. On the one hand, it's totally true that you're no longer really writing Haskell, and the facility for rewrite rules itself needed (at some point) to be added to the compiler. But at this point I can make my own data structures fuse (potentially in new ways) without further changes to the compiler. https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#rewrite-rules https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...

dan-robertson 6y ago

Strictly speaking, Common Lisp does not have series because they were not included in ANSI Common Lisp. Therefore even though you could use the macros provided with a separate streams package, you’d need to make sure that all your code used that package (rather than the CL definitions of let and lambda and so on) and properly declared stream functions. This ends up making code using streams not super composable which isn’t great. I also think it’s a bit unfair to say that Haskell’s stream fusion requires special compiler support. The compiler doesn’t recognise list functions specifically or have special cases for list-looking-types (except for syntax). Instead there is a general mechanism to say “at stage number x, replace expressions that look like y with z”, where there are something like 10 stages and expressions y and z are type checked so these transformations are only applied in “valid” cases. I think saying that this is special compiler support for stream fusion is like saying that macros are special compiler support for series in CL. A final thing to note is that because of lazy evaluation, stream fusion in Haskell doesn’t change the semantics of the Haskell list functions from how they would behave without it. In Common Lisp streams must be explicitly separated from lists because they are semantically different (in the evaluation order of the functions that act on them).

wrs 6y ago
My impression was some of those expressions were added to the compiler specifically to make stream fusion work well enough to use. Even if so, it’s a good point that laziness makes streams more “natural” in Haskell so that was just a performance improvement, not a semantic change. Certainly laziness is a big “philosophical difference” between the two!
- eru 6y ago
  Yes. And laziness works because Haskell is pure-by-default. Yes. Though if we were starting from scratch today, perhaps we would see a total language, ie one where all functions terminate. That would allow the compiler much more freedom in how to order evaluation.
reikonomusha 6y ago
GHC does have special support for fusion and rewriting. See e.g. [1]. The laziness comes with the language, but turning it efficient requires a series of these rewrite rules expressed as GHC-specific metadata. [1] https://markkarpov.com/tutorial/ghc-optimization-and-fusion.html#rewrite-rules https://markkarpov.com/tutorial/ghc-optimization-and-fusion....
- sukilot 6y ago
  GHC is the most complicated compiler of any language (or very near to it), except perhaps Mathematica which is similar: It's an optimizer for a graph-reduction engine. It doesn't mean much to call out "special support" for any one bit of style of programming, since the language itself has nearly no concept of performance -- you just write functional code and the compiler will find the fastest runtime computation of the evaluation that it can.
  - eru 6y ago
    > It doesn't mean much to call out "special support" for any one bit of style of programming, since the language itself has nearly no concept of performance -- you just write functional code and the compiler will find the fastest runtime computation of the evaluation that it can. While GHC is glorious, it's still very limited in what it can do, performance wise. You are right that languages themselves seldom have a direct concept of performance. But language features and restrictions have a big impact on achievable performance. Eg Haskell's purity-by-default means that the compiler has quite a bit of freedom when choosing how to translate something like eg the 'map' or 'filter' functions. The equivalent in C++ gives the compiler less flexibility, because the helper function handed over at runtime might have side-effects. Similarly, Haskell functions are still allowed one important side effect: non-determination. In a more restricted language like Agda that's not allowed. Thus giving the compiler more degrees of freedom to work with. Or in a different direction: the query optimizers for SQL can do very impressive work, because SQL is so limited.