13 ms·

Fusion makes functional programming fun

37 points by dons 17y ago

asolove 17y ago
Summary: side-effect free programming allows compilers to transform high-level code into very efficient machine code. I've always wondered about the utility of this in exploratory programming. We always hear how great Lisp is because of dynamic typing, macros, etc., but once you kind-of know the solution you go back and code it efficiently. If you've implemented your code in terms of type classes in the first place, how much easier is it in Haskell to just change a few types of the inputs (List -> Vector, Integer -> Int#) and get a performance increase?
- jgrant27 17y ago
  You simply do not know Lisp. Lisp is a term to describe different dialects in a family of languages. For example : Common Lisp is a multi-paradigm Lisp that supports dynamic typing AND static typing. Haskell has NO equivalent to Common Lisp's macros. Template Haskell is not equivalent Lisp's macros. Often a Common Lisp implementation will simply require type hints to be added to gain large performance improvements. Clojure(another Lisp dialect) is the same this way.
  - dons 17y ago
    > Template Haskell is not equivalent Lisp's macros Well, Template Haskell is a compile time meta programming system based on quasi quotation and AST manipulation...
    - jgrant27 17y ago
      They are not equivalent. In Lisp there is no distinction between the syntax and the AST. In Haskell the AST is modeled using explicit data types. http://www.haskell.org/bz/thdoc.htm http://www.haskell.org/bz/thdoc.htm : "In Template Haskell, ordinary algebraic data types represent Haskell program fragments. These types modeled after Haskell language syntax and represents AST (abstract syntax tree) of corresponding Haskell code. There is an Exp type to represent Haskell expressions, Pat – for patterns, Lit – for literals, Dec – for declarations, Type – for data types and so on. You can see definitions of all these types in the module Language.Haskell.TH.Syntax."
      - jrockway 17y ago
        This is a good thing, though. With Common Lisp, you have to emulate this via a code-walking library -- and because the code-walking library just uses heuristics, you can never be sure that your macro is right in all cases. With well-defined data types for each AST node, this problem goes away. The advantage that CL-style macros have is that they are much easier to use than TH. For me, anyway, writing a Lisp macro is a trivial thing that involves almost no thinking. Writing a TH macro takes some testing and debugging.
        jgrant27 17y ago
        There's no need to 'emulate' anything 'via code-walking' and 'heuristics' when writing Lisp macros. This is a personal use case of your own. If you know how to write Lisp macros(i.e. experience) then they will be correct. Not all Lisp macros are trivial to implement even for the experienced Lisp hacker. Writing a Lisp macro requires testing and debugging. The difference is that Lisp inserts no 'airbags' between the language and the programmer. They are very powerful but you may 'hurt' yourself.
        jrockway 17y ago
        The issue comes when transforming entire expressions; what parts are code to transform, and what parts are data? You can't know, you have to guess.
        jgrant27 17y ago
        There is no guessing. You get to answer that question for yourself based on the context of your application. Many Lisps provide as much(or as little) type checking that you might want in your application.
        jrockway 17y ago
        OK, and now we've hit on the main problem I've had with Common Lisp -- every library thinks it's the only library in the universe, and they don't compose well. Your comment exactly expresses the attitude of the Common Lisp community (as I see it) -- "you should write every single line of code in your app from scratch, just for you". No thanks. The less code I have to write, the better.
  - gwern 17y ago
    Type hints are not static proofs of type-correctness, though, unless SBCL's warnings have gotten ridiculously more intelligent.
    - jgrant27 17y ago
      Your notion of 'type-correctness' seems fairly static and you don't know Common Lisp either. A type hint in Common Lisp is the same as a type declaration. Common Lisp just let's you declare the types optionally. If you declare a type for a value and then try to store a value of an incorrect type then SBCL(and many other CL compilers) will respond with a compiliation error(not a warning) : ; in: LAMBDA NIL ; (TYPE (SINGLE-FLOAT NODE)) ; ; caught ERROR: ; Bound is not *, a SINGLE-FLOAT or a list of a SINGLE-FLOAT: NODE ; ; compilation unit finished ; caught 1 ERROR condition debugger invoked on a SB-INT:COMPILED-PROGRAM-ERROR in thread #<THREAD "initial thread" RUNNING {1002A5A051}>: Execution of a form compiled with errors. Form: #'(NAMED-LAMBDA TRAVERSE-PRE-ORDER (NODE FUN) (DECLARE (TYPE (SINGLE-FLOAT NODE)) (IF NODE (PROGN (APPLY FUN (LIST NODE)) (IF (BTNODE-LEFT NODE) (TRAVERSE-PRE-ORDER (BTNODE-LEFT NODE) FUN)) (IF (BTNODE-RIGHT NODE) (TRAVERSE-PRE-ORDER (BTNODE-RIGHT NODE) FUN))))) (BLOCK TRAVERSE-PRE-ORDER)) Compile-time error: Bound is not *, a SINGLE-FLOAT or a list of a SINGLE-FLOAT: NODE Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL. restarts (invokable by number or by possibly-abbreviated name): 0: [CONTINUE] Ignore runtime option --load "tree-traversal.lisp". 1: [ABORT ] Skip rest of --eval and --load options. 2: Skip to toplevel READ/EVAL/PRINT loop. 3: [QUIT ] Quit SBCL (calling #'QUIT, killing the process). ((LAMBDA ()))
  - eru 17y ago
    What you say may be right --- but I guess you deserve the 0 points for your unwarranted smugness.
    - jgrant27 17y ago
      How is it unwarranted when Lisp is THE greatest programming language ever known ?
cousin_it 17y ago
Cool! But what if I write a more complex program that I want to perform well? Is it easy to understand where the compiler will or won't do this crazy fusion thing?
- dons 17y ago
  It's pretty easy to work out where fusion is going to happen, since it happens compositionally. You compose fusible functions, and the (.) between them is syntactically where fusion occurs. GHC will tell you how many fusion sites were found.
  - eru 17y ago
    You can also add your own fusion rules, as far as I know.
colomon 17y ago
Their code is import qualified Data.Vector as U main = print . U.sum $ U.enumFromTo 1 (100000000 :: Int) Possibly it's just because I don't grok Haskell, but that strikes me as incredibly ugly for such a simple operation. As a contrast, here's the Perl 6 version: say [+] 1..100000000 (For sure there is no Perl 6 implementation that will run the code as fast as they show GHC running it -- odds are, in fact, that the current Perl 6 implementations will be drastically slower.) I suspect there is a more elegant version in Haskell, too -- it probably just doesn't run nearly as fast. This has been one of my main gripes with my experiments with functional languages. It seems they are always showing you this beautiful elegant code, and then explaining how if you want it to be efficient, you need to use a different, much uglier, approach. Of course, the other thing with this is the example is completely unrealistic. If you actually wanted to compute that number, the fast way to do it is to use the good old formula (N * (N-1))/2 If for some reason you wanted to compute that sort of thing a lot, to would make a lot more sense to make a simple function to calculate that...
- dons 17y ago
  I'm sorry I used a trivial example -- the point was to show how the assembly corresponded to the fused loop, which necessitated a simple example. And this is the internet, so everyone tries to find a closed form for everything. Which misses the point! Of course, the Haskell: print (sum (enumFromTo 1 n)) isn't exactly bad. And you can use any of these other 134 functions to get fused loops: http://hackage.haskell.org/packages/archive/vector/0.5/doc/html/Data-Vector.html#1 http://hackage.haskell.org/packages/archive/vector/0.5/doc/h... And there's lots of interesting problems you can solve with that rich a set of primitives. This isn't an example benchmark, it's an example translation, so you can see the optimization at work. Bigger examples yield assembly that no casual reader could follow -- so don't get distracted by the fact there's a closed form!!
  - colomon 17y ago
    Glad to see there is a prettier way of doing it in Haskell! Do I understand then that this basically building up a sort of parallel language for expressions in Haskell which optimize really, really well?

37 points by dons 17y ago

Summary: side-effect free programming allows compilers to transform high-level code into very efficient machine code. I've always wondered about the utility of this in exploratory programming. We always hear how great Lisp is because of dynamic typing, macros, etc., but once you kind-of know the solution you go back and code it efficiently. If you've implemented your code in terms of type classes in the first place, how much easier is it in Haskell to just change a few types of the inputs (List -> Vector, Integer -> Int#) and get a performance increase?

jgrant27 17y ago
You simply do not know Lisp. Lisp is a term to describe different dialects in a family of languages. For example : Common Lisp is a multi-paradigm Lisp that supports dynamic typing AND static typing. Haskell has NO equivalent to Common Lisp's macros. Template Haskell is not equivalent Lisp's macros. Often a Common Lisp implementation will simply require type hints to be added to gain large performance improvements. Clojure(another Lisp dialect) is the same this way.
- dons 17y ago
  > Template Haskell is not equivalent Lisp's macros Well, Template Haskell is a compile time meta programming system based on quasi quotation and AST manipulation...
  - jgrant27 17y ago
    They are not equivalent. In Lisp there is no distinction between the syntax and the AST. In Haskell the AST is modeled using explicit data types. http://www.haskell.org/bz/thdoc.htm http://www.haskell.org/bz/thdoc.htm : "In Template Haskell, ordinary algebraic data types represent Haskell program fragments. These types modeled after Haskell language syntax and represents AST (abstract syntax tree) of corresponding Haskell code. There is an Exp type to represent Haskell expressions, Pat – for patterns, Lit – for literals, Dec – for declarations, Type – for data types and so on. You can see definitions of all these types in the module Language.Haskell.TH.Syntax."
    - jrockway 17y ago
      This is a good thing, though. With Common Lisp, you have to emulate this via a code-walking library -- and because the code-walking library just uses heuristics, you can never be sure that your macro is right in all cases. With well-defined data types for each AST node, this problem goes away. The advantage that CL-style macros have is that they are much easier to use than TH. For me, anyway, writing a Lisp macro is a trivial thing that involves almost no thinking. Writing a TH macro takes some testing and debugging.
      - jgrant27 17y ago
        There's no need to 'emulate' anything 'via code-walking' and 'heuristics' when writing Lisp macros. This is a personal use case of your own. If you know how to write Lisp macros(i.e. experience) then they will be correct. Not all Lisp macros are trivial to implement even for the experienced Lisp hacker. Writing a Lisp macro requires testing and debugging. The difference is that Lisp inserts no 'airbags' between the language and the programmer. They are very powerful but you may 'hurt' yourself.
        jrockway 17y ago
        The issue comes when transforming entire expressions; what parts are code to transform, and what parts are data? You can't know, you have to guess.
        jgrant27 17y ago
        There is no guessing. You get to answer that question for yourself based on the context of your application. Many Lisps provide as much(or as little) type checking that you might want in your application.
        jrockway 17y ago
        OK, and now we've hit on the main problem I've had with Common Lisp -- every library thinks it's the only library in the universe, and they don't compose well. Your comment exactly expresses the attitude of the Common Lisp community (as I see it) -- "you should write every single line of code in your app from scratch, just for you". No thanks. The less code I have to write, the better.
- gwern 17y ago
  Type hints are not static proofs of type-correctness, though, unless SBCL's warnings have gotten ridiculously more intelligent.
  - jgrant27 17y ago
    Your notion of 'type-correctness' seems fairly static and you don't know Common Lisp either. A type hint in Common Lisp is the same as a type declaration. Common Lisp just let's you declare the types optionally. If you declare a type for a value and then try to store a value of an incorrect type then SBCL(and many other CL compilers) will respond with a compiliation error(not a warning) : ; in: LAMBDA NIL ; (TYPE (SINGLE-FLOAT NODE)) ; ; caught ERROR: ; Bound is not *, a SINGLE-FLOAT or a list of a SINGLE-FLOAT: NODE ; ; compilation unit finished ; caught 1 ERROR condition debugger invoked on a SB-INT:COMPILED-PROGRAM-ERROR in thread #<THREAD "initial thread" RUNNING {1002A5A051}>: Execution of a form compiled with errors. Form: #'(NAMED-LAMBDA TRAVERSE-PRE-ORDER (NODE FUN) (DECLARE (TYPE (SINGLE-FLOAT NODE)) (IF NODE (PROGN (APPLY FUN (LIST NODE)) (IF (BTNODE-LEFT NODE) (TRAVERSE-PRE-ORDER (BTNODE-LEFT NODE) FUN)) (IF (BTNODE-RIGHT NODE) (TRAVERSE-PRE-ORDER (BTNODE-RIGHT NODE) FUN))))) (BLOCK TRAVERSE-PRE-ORDER)) Compile-time error: Bound is not *, a SINGLE-FLOAT or a list of a SINGLE-FLOAT: NODE Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL. restarts (invokable by number or by possibly-abbreviated name): 0: [CONTINUE] Ignore runtime option --load "tree-traversal.lisp". 1: [ABORT ] Skip rest of --eval and --load options. 2: Skip to toplevel READ/EVAL/PRINT loop. 3: [QUIT ] Quit SBCL (calling #'QUIT, killing the process). ((LAMBDA ()))
- eru 17y ago
  What you say may be right --- but I guess you deserve the 0 points for your unwarranted smugness.
  - jgrant27 17y ago
    How is it unwarranted when Lisp is THE greatest programming language ever known ?

cousin_it 17y ago

Cool! But what if I write a more complex program that I want to perform well? Is it easy to understand where the compiler will or won't do this crazy fusion thing?

dons 17y ago
It's pretty easy to work out where fusion is going to happen, since it happens compositionally. You compose fusible functions, and the (.) between them is syntactically where fusion occurs. GHC will tell you how many fusion sites were found.
- eru 17y ago
  You can also add your own fusion rules, as far as I know.

colomon 17y ago

Their code is import qualified Data.Vector as U main = print . U.sum $ U.enumFromTo 1 (100000000 :: Int) Possibly it's just because I don't grok Haskell, but that strikes me as incredibly ugly for such a simple operation. As a contrast, here's the Perl 6 version: say [+] 1..100000000 (For sure there is no Perl 6 implementation that will run the code as fast as they show GHC running it -- odds are, in fact, that the current Perl 6 implementations will be drastically slower.) I suspect there is a more elegant version in Haskell, too -- it probably just doesn't run nearly as fast. This has been one of my main gripes with my experiments with functional languages. It seems they are always showing you this beautiful elegant code, and then explaining how if you want it to be efficient, you need to use a different, much uglier, approach. Of course, the other thing with this is the example is completely unrealistic. If you actually wanted to compute that number, the fast way to do it is to use the good old formula (N * (N-1))/2 If for some reason you wanted to compute that sort of thing a lot, to would make a lot more sense to make a simple function to calculate that...

dons 17y ago
I'm sorry I used a trivial example -- the point was to show how the assembly corresponded to the fused loop, which necessitated a simple example. And this is the internet, so everyone tries to find a closed form for everything. Which misses the point! Of course, the Haskell: print (sum (enumFromTo 1 n)) isn't exactly bad. And you can use any of these other 134 functions to get fused loops: http://hackage.haskell.org/packages/archive/vector/0.5/doc/html/Data-Vector.html#1 http://hackage.haskell.org/packages/archive/vector/0.5/doc/h... And there's lots of interesting problems you can solve with that rich a set of primitives. This isn't an example benchmark, it's an example translation, so you can see the optimization at work. Bigger examples yield assembly that no casual reader could follow -- so don't get distracted by the fact there's a closed form!!
- colomon 17y ago
  Glad to see there is a prettier way of doing it in Haskell! Do I understand then that this basically building up a sort of parallel language for expressions in Haskell which optimize really, really well?