a potential lisp convert, and interpreting the shootout
in [Lisp]
|
Prev: Pocket Lisp Machine
Next: Next Generation of Language
From: Rahul Jain on 4 Oct 2006 15:13 "Henry Bigelow" <hrbigelow(a)gmail.com> writes: > does the standard require that "lisp can be written in itself" as paul > graham says (whatever that means)? It doesn't explicitly require that, but it defines a turing-complete language, so yeah... you can write a lisp compiler and interpreter in lisp, as you can in C or Perl. The difference, I think, that PG is getting at is that the most basic lisp data is code itself. Thinking about code in an abstract manner is just second nature when you're programming in lisp. > and, is that why > > somehow has a drawback that aggressive type inference can't be done, > with any compiler of lisp. I don't see how those two statements could possibly correlate, and later I demonstrate more aggressive type inference being done than any other language I've heard of. >> Lisp has a much richer type system than any of the MLs. CMUCL, for >> example, can do type inference to determine whether the arcsin of a >> value rounded off to the nearest integer will fit in a machine word or >> whether it might need to have a bignum (MLs don't have bignums as part >> of the language). > > yes, but it's been mentioned several times that, in order to get lisp > code to run fast, you have to "litter it with type declarations". so, > it seems, there isn't much type inference going on. No, you "litter" it where needed. It depends from compiler to compiler. C and Java code is so littered with type declarations, the highway police would arrest the programmer if he hadn't already run into a lamppost because his code crashed. > also, i got that idea from this wikipedia page: > > http://en.wikipedia.org/wiki/Type_system > > about halfway down it mentions this: > > Static typing usually results in compiled code that executes more > quickly. When the compiler knows the exact data types that are in use, > it can produce machine code that just does the right thing. Further, > compilers in statically typed languages can find shortcuts more easily. > Some dynamically-typed languages such as Common Lisp allow optional > type declarations for optimization for this very reason. Static typing > makes this pervasive. See optimization. Haha! I just modified that paragraph last month to fix the way it described "Lisp". But yes, Common Lisp can be as static or dynamic as you want it to be. > i see. that's pretty cool. so, what is your programming style? do > you first prototype something without any type declarations, and then > add in a few in the compute-intensive code? That's the third rule of optimization applied to type declarations. So yes. :) Remember not to conflate type declarations with type checks. (Although code declared to be safe will always check types when it calls standard lisp functions.) -- Rahul Jain rjain(a)nyct.net Professional Software Developer, Amateur Quantum Mechanicist
From: Rahul Jain on 4 Oct 2006 15:29 Jon Harrop <jon(a)ffconsultancy.com> writes: > Rahul Jain wrote: >> Lisp has a much richer type system than any of the MLs. > > I'm not sure what you mean by that. ML does lots of things that Lisp does > not and vice-versa. Hmm. I'm not sure about that. All I can think of is inference of parametrized array types (non-upgraded) across functions. Lisp just doesn't _require_ those things to be done. If someone cared, they could augment a compiler to do it. What I'm talking about, to clarify, is for an array declared to have an element type of (integer 1 100), a function that returns an element of it should have an inferred return type of (integer 1 100). For: (defun test (x) (declare (type (array (integer 1 100) (*)) x)) (aref x 1)) CMUCL inferrs a return type of: Its result type is: (UNSIGNED-BYTE 8) So it has upgraded the element type to what it's actually going to store in memory. Dunno why it doesn't just propagate the element type defintion directly. >> CMUCL, for >> example, can do type inference to determine whether the arcsin of a >> value rounded off to the nearest integer will fit in a machine word or >> whether it might need to have a bignum > > ML doesn't have a numeric tower. You have to explicitly state that you want > an int, float, bignum and so on. > >> (MLs don't have bignums as part of the language). > > OCaml, SML and F# all have bignums as part of the language. Interesting. Some self-proclaimed ocaml genius claimed that it didn't have bignums. Maybe he meant that you need to explicitly... um... declare (?!?) a number to be a bignum? That would fit in with the lack of a numeric tower. >> This topic is VERY, VERY important to optimizing Lisp numeric code, so >> be SURE to study it carefully. > > In contrast, succinct ML is typically fast ML. Yeah, but you don't know if it's going to be correct unless you manually perform the kind of type inference that CMUCL does. :) On a more serious note, you still end up with the problem that your code is either slow but tolerant of different architectures or it's fast on some architectures and incorrect on others. Sure, you could maintain two parallel versions of the codebase, but don't programmers like abstraction? (yeah, I know, the mainstream abhors abstraction. They'd be happy writing machine code if they could still get paid enough for their time.) -- Rahul Jain rjain(a)nyct.net Professional Software Developer, Amateur Quantum Mechanicist
From: Javier on 4 Oct 2006 20:08 Rahul Jain ha escrito: > Hmm. I'm not sure about that. All I can think of is inference of > parametrized array types (non-upgraded) across functions. Lisp just > doesn't _require_ those things to be done. If someone cared, they could > augment a compiler to do it. > What I'm talking about, to clarify, is for an array declared to have an > element type of (integer 1 100), a function that returns an element of > it should have an inferred return type of (integer 1 100). > > For: > (defun test (x) > (declare (type (array (integer 1 100) (*)) x)) > (aref x 1)) > CMUCL inferrs a return type of: > Its result type is: > (UNSIGNED-BYTE 8) > > So it has upgraded the element type to what it's actually going to store > in memory. Dunno why it doesn't just propagate the element type > defintion directly. One important thing I miss from Lisp compared to ML, is for example the ability to test at compile time about the type of something. For example you can define a list type in the style of Lisp: type 'a lisp_list = Nil | List of 'a list so now every variable using this type can be either Nil or a list itself. Or even binary trees: type 'a btree = Empty | Node of 'a * 'a btree * 'a btree I found this feature very usefull. > Interesting. Some self-proclaimed ocaml genius claimed that it didn't > have bignums. It does: http://caml.inria.fr/pub/docs/manual-ocaml/libref/Big_int.html If you don't like those function names, you can rename the operators: let ( +$ ) = add_big_int > Maybe he meant that you need to explicitly... um... > declare (?!?) a number to be a bignum? That would fit in with the lack > of a numeric tower. I don't understand what you're talking about, but you can always convert any int or string to big_int and viceversa. > >> This topic is VERY, VERY important to optimizing Lisp numeric code, so > >> be SURE to study it carefully. > > > > In contrast, succinct ML is typically fast ML. > > Yeah, but you don't know if it's going to be correct unless you manually > perform the kind of type inference that CMUCL does. :) I think that if you are a good programmer, you must know the type of anything you are writing, even if it is writen in Lisp. And ML does allow you to use "generic" or arbitray types when you need. Just take the example of the binary tree above. > On a more serious note, you still end up with the problem that your code > is either slow but tolerant of different architectures or it's fast on > some architectures and incorrect on others. > Sure, you could maintain two > parallel versions of the codebase, but don't programmers like > abstraction? (yeah, I know, the mainstream abhors abstraction. They'd be > happy writing machine code if they could still get paid enough for their > time.) Static inference always produce faster code compared with dynamic inference, for an equivalent code base. But you usually need to declare things on dynamic languages to help the inferer, while in statically infered ones you don't, so you save a lot of time on both writing and profiling. You don't need to maintain parallel versions of the codebase, or if you do, you would also do in Lisp (this is not language specific, but the kind of algorithm/implementation you choose).
From: Jon Harrop on 5 Oct 2006 09:58 Rahul Jain wrote: > Jon Harrop <jon(a)ffconsultancy.com> writes: >> Rahul Jain wrote: >>> Lisp has a much richer type system than any of the MLs. >> >> I'm not sure what you mean by that. ML does lots of things that Lisp does >> not and vice-versa. > > Hmm. I'm not sure about that. All I can think of is inference of > parametrized array types (non-upgraded) across functions. Lisp just > doesn't _require_ those things to be done. If someone cared, they could > augment a compiler to do it. Sure, you can augment a compiler to do anything. >> OCaml, SML and F# all have bignums as part of the language. > > Interesting. Some self-proclaimed ocaml genius claimed that it didn't > have bignums. Maybe he meant that you need to explicitly... um... > declare (?!?) a number to be a bignum? That would fit in with the lack > of a numeric tower. Yes. More than just declare though, you have to annotate every literal and use different operators. >> In contrast, succinct ML is typically fast ML. > > Yeah, but you don't know if it's going to be correct unless you manually > perform the kind of type inference that CMUCL does. :) > > On a more serious note, you still end up with the problem that your code > is either slow but tolerant of different architectures or it's fast on > some architectures and incorrect on others. Sure, you could maintain two > parallel versions of the codebase, but don't programmers like > abstraction? (yeah, I know, the mainstream abhors abstraction. They'd be > happy writing machine code if they could still get paid enough for their > time.) In practice, I have never had a problem caused by fixed-precision integers. However, I have lots of problems caused by floating point precision. Does CMUCL's type inference do anything to help with that? -- Dr Jon D Harrop, Flying Frog Consultancy Objective CAML for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists
From: Joe Marshall on 5 Oct 2006 12:41
Javier wrote: > > Static inference always produce faster code compared with dynamic > inference, for an equivalent code base. http://www.hpl.hp.com/techreports/1999/HPL-1999-77.pdf ``Contrary to intuition, we demonstrate that it is possible to use a piece of software to improve the performance of a native, statically optimized program binary, while it is executing. Dynamo not only speeds up real application programs, its performance improvement is often quite significant. For example, the performance of many +O2 optimized SPECint95 binaries running under Dynamo is comparable to the performance of their +O4 optimized version running without Dynamo.'' |