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?
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.
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 :
"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."
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.
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.
I don't understand what 'airbags' haskell inserts. Ok, it might be a bit trickier to write macros since it doesn't have
such uniform syntax, but can you not still express all of the same meta-programming constructs?
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.
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.
It seems that you have a beef with a particular(or multiple) Common Lisp libraries. Fair enough.
However, I never said that you should write every line of code in your app from scratch. I did say that you should OWN the decisions for YOUR app.
I believe that this more accurately describes the attitude of the CL community (and that of many other languages too).
My point was that meta-programming is more powerful in Lisp than Haskell(as far as I'm aware). That's pretty much it.
Does that mean it's impossible to use Template Haskell to add new syntax? It strikes me as a serious limitation if you could only specify different ways to evaluate code that is already well-formed Haskell.
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 ()))
$ sbcl
This is SBCL 1.0.18.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.
SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses. See the CREDITS and COPYING files in the
distribution for more information.
* (defun foo (x) (declare (type array x)) (car x))
; in: LAMBDA NIL
; (CAR X)
;
; note: deleting unreachable code
;
; caught WARNING:
; Asserted type LIST conflicts with derived type (VALUES ARRAY &OPTIONAL).
; See also:
; The SBCL Manual, Node "Handling of Types"
;
; compilation unit finished
; caught 1 WARNING condition
; printed 1 note
First of all, you have modified the function that I posted (you changed the type declaration from a list to an array).
Second, you do not read your compiler warning messages.
SBCL is trying to tell you that you shouldn't type something as an array when you are clearly attempting to use it as a list e.g. calling the CAR function on an array makes no sense. A list and an array in Lisp are not the same. The CAR function in Lisp only works on lists.
* (defun foo (x) (declare (type array x)) (car x))
; in: LAMBDA NIL
; (CAR X)
;
; caught WARNING:
; Asserted type LIST conflicts with derived type (VALUES ARRAY &OPTIONAL).
; See also:
; The SBCL Manual, Node "Handling of Types"
It's correctly warning you before you even try and call the foo function, because it will fail no matter what you pass to it !
> First of all, you have modified the function that I posted (you changed the type declaration from a list to an array).
How would I demonstrate SBCL's ability to detect type errors except by making a type error? Your example showed nothing; 'type' could be a null-op for all it does.
And checks about primitive types are all well and good, but how far does it go? Not being much of a lisper, it's hard for me to give whole classes of example where SBCL's warnings are non-existent, incorrect, or buried under a flurry of others. If I declare a custom CLOS object with multiple fields/methods/whatever and call a field/method which doesn't exist, is SBCL still smart enough to warn me? I dunno.
There is no concept of a 'primitive' type in Common Lisp.
It handles type-checking for built-in types or for your own custom declared types. CL's type system is very powerful.
Here's a type-checking example related to CLOS :
;; High safety settings are required by SBCL for type checking of slots
;; See --> http://www.apl.jhu.edu/~hall/Lisp-Notes/Defclass.html
(declaim (optimize
(speed 0) (compilation-speed 0) (safety 3) (debug 3)))
(defclass circle()
((center :type cons
:accessor circle-center
:initarg :center)
(radius :type fixnum
:accessor circle-radius
:initarg :radius)))
(defmethod circle-area ((x circle))
(* pi (expt (circle-radius x) 2)))
(let ((c (make-instance 'circle :center '(0 0) :radius 4)))
(format t "~A~%" (circle-area c))
(setf (circle-center c) '(2 3))
(setf (circle-radius c) 7)
;; this will fail at compile with a TYPE-ERROR
;(setf (circle-radius c) "B")
;; this will fail at compile with a UNDEFINED-FUNCTION
;; because the method does not exist
;(location c)
)
Erm, what? This is supposed to show smart compile-time checking about runtime behavior?? This no more demonstrates what you apparently think it demonstrates than I could demonstrate Haskell's type-soundness by taking some Template Haskell, inserting 'head []', and saying 'it crashes during compilation, eureka!'
What would be fairer would be wrapping all that in a '(defun foo () )', in which case one doesn't get any warning relating to the 'location c' or "B":
* (load "foo.cl")
STYLE-WARNING: Implicitly creating new generic function CIRCLE-AREA.
; in: LAMBDA NIL
; ((LET ((C (MAKE-INSTANCE 'CIRCLE :CENTER '# :RADIUS 4)))
; (FORMAT T "~A~%" (CIRCLE-AREA C))
; (SETF (CIRCLE-CENTER C) '(2 3))
; (SETF (CIRCLE-RADIUS C) 7)
; (SETF (CIRCLE-RADIUS C) "B")
; (LOCATION C)))
;
; caught ERROR:
; illegal function call
;
; compilation unit finished
; caught 1 ERROR condition
It's runtime checking. I really don't care though. Common Lisp just has a different approach, it sits between static typing and dynamic typing. It's type declarations are for optimization. Which I see as the main benefit anyway.
Besides, I've been around long enough to have seen applications that were implemented using statically-typed languages, simply explode. Static typing, IMHO, is extremely overrated. Since many statically typed languages make it easy to cast one type into another, you can't trust it to be anything more than an optimization hint.
This been quite the diversion(thanks). I'm mainly interested in meta-programming in Haskell & how it compares with Lisp.
Actually, if I understood the HyperSpec correctly, in theory a conformant Common Lisp implementation would be allowed to just crash if you declared that x is a list and then you call it with something else. By declaring the type like this, you're telling the compiler: "I assure you that x will definitely be a list".
Of course, in practice implementations like to check everything by default.
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...
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!
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!!
In a way. It's a subset of Haskell focused on array operations that optimize really really well. You can use these instead of list operations, basically, and getter performance in all sorts of ways.
You could get very good performance when you do the fusion manually, too. The really exciting thing about fusion is that it allows really fast code that _composes_ well.
Composability is also what makes Haskellers excited about Monads and software transactional memory (STM). STM give composable concurrency --- in contrast with locks which are notoriously uncomposable.
Yes, you can of course use lists. I'm interested in getting the compiler to produce the best code it can, hence I use slightly different libs and flags and such.
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?
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.
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?