#14847 - sajiimori - Tue Jan 13, 2004 6:40 am
This thread is (initially) about the things that Haskell has that Common Lisp does not -- yet. ;-)
I bet functional pattern matching would be a breeze to implement in Lisp. CLOS already has a form of it, since methods can dispatch on the type or value of any of the arguments (and CLOS is implemented in Lisp).
All you'd have to do is write a macro to transform this:
| Code: |
(defpatfun factorial (0) 1)
(defpatfun factorial (x)
(* x (factorial (- x 1))))
|
into this:
| Code: |
(defun factorial (x)
(cond ((= x 0) 1)
(t (* x (factorial (- x 1))))))
|
More complex patterns could be made by pairing argument names with predicate expressions that determine whether there is a match:
| Code: |
(defpatfun blah ((x (or (equal x "one")
(equal x "two"))))
"x was one or two")
(defpatfun blah (x)
"x was something else")
|
Is there anything else it would have to do?
I don't know how hard it would be to implement lazy evaluation. Is it mostly used for long/infinite sequences where each value depends on the previous, or are the effects of lazy evaluation pervasive throughout most Haskell applications?
Anybody have any neat examples of lazy evaluation that would be hard to rewrite in a strict language?
#14860 - jma - Tue Jan 13, 2004 6:55 pm
One major advantage that Lisp has over Haskell is the interactive nature of it. Some Haskell implementations have interactive debugging, but it is rare (and poorly implemented).
Lisp's syntax has always been its advantage and greatest dis-service (IMO). It allows writing of code that writes code, which is incredible. However, it also is very annoying and can be cumbersome. With Haskell, since interactive debugging and syntax aren't much of an issue, there are some great syntax forms created do simplify code.
As a note, I'll be using the syntax from Clean for my examples, which is very close to Haskell. For example:
| Code: |
| [y \\ y <- m | y < 5] |
This little code segement will return a list of all numbers from list m that are less than 5. While certainly possible in Lisp (easily, too), having the syntax to do it in a single line is very nice. Also, while an extreme case, and overly used in Haskell tutorials, Quicksort is a good example of this (and other features) in action:
| Code: |
// An empty list returns an empty list
qsort [] = []
qsort [x:xs] = qsort lt ++ [x] ++ qsort ge
where
lt = [y \\ y <- xs | y < x]
ge = [y \\ y <- xs | y >= x] |
lt and ge are used before being defined, and are local functions to qsort. Pattern matching of functions is obvious. Another huge syntax feature is being able to split the CAR and CDR of a list (done with [x:xs]). The list generator syntax as described above is there, too.
How about where the lazy evaluation comes into play. Let's say I create a list of 1000 numbers and pass it to the qsort routine above. Now I only care about the 4 smallest numbers (the first 4 values in the list). The qsort routine will not execute until requested, and obviously only on those elements that are needed, meaning (in this extreme case), only the lt (less than) recursive routine will execute, and only until the first 4 values have been found.
Another wonderous feature of Haskell is continuations. This is very similar to Lisp's closures, but (IMO) more powerful. For those that don't know what a closure is, I suggest reading up... closures are wonderful things, as are high-order functions. In Haskell, let's say I make a function that will add two numbers:
| Code: |
| my_adder n1 n2 = n1 + n2 |
Simple enough. Of course, because of high-order functions (like Lisp) I can pass around my_adder to functions like any other object. But, with continuations, it allows me to pass around a partially completed function call...
Whoa! What just happened? Well, because of currying, add_5 is a function that returns a continuation. Passing only 1 argument to a function that expects 2 returns a function that expects 1. Now doing:
Can you tell I get excited about this? Oh well, enough talk for now... can't wait to continue the thread, though :)
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#14934 - sajiimori - Wed Jan 14, 2004 11:25 pm
Note: This is probably old news to some of you -- I'm still trying to sort it all out, and this sort of discussion helps.
| Quote: |
Lisp's syntax has always been its advantage and greatest dis-service (IMO). It allows writing of code that writes code, which is incredible. However, it also is very annoying and can be cumbersome. With Haskell, since interactive debugging and syntax aren't much of an issue, there are some great syntax forms created do simplify code.
|
The great syntax debate! Until recently, I would have said, "What's so great about people debating over whose syntax is better?" But I misunderstood the nature of the debate. The real question is: should we even *have* syntax? That is, should the textual representation of code match 1-to-1 with the parse tree, or should the code be internally rearranged according to complex built-in rules?
I'm leaning more and more toward "no syntax". The problem with syntax is that if you don't like what the language gives you, you're pretty much stuck. The language designers must try to predict all the ways that programmers will try to use the language, and for me, they have always failed. There comes a time when I want to do something that's truly awkward, and I have no way of making it less so.
Because CL has no syntax (besides read-macros like #'), I can extend the language as I please, and make it fit the domain of my application. If I find that something is inelegant in plain CL, I can make it elegant by changing the language.
For example:
| Code: |
; [y \\ y <- m | y < 5]
; idiomatic CL:
(remove-if-not #'(lambda (y) (< y 5)) m)
; a utility in my environment:
(defmacro relate (op &rest args)
`#'(lambda (n) (,op n ,@args)))
; with relate:
(remove-if-not (relate < 5) m)
|
About qsort:
| Code: |
; qsort [] = []
; qsort [x:xs] = qsort lt ++ [x] ++ qsort ge
; where
; lt = [y \\ y <- xs | y < x]
; ge = [y \\ y <- xs | y >= x]
; An equally inefficient "quick" sort:
(defun qsort (lst)
(when lst
(nconc (remove-if-not (relate < (car lst)) (cdr lst))
(list (car lst))
(remove-if-not (relate > (car lst)) (cdr lst)))))
|
What if you want to make qsort faster in Haskell? Does it have destructive operations, or are you always forced to produce so much garbage? Because I want a language that I can use in as many situations as possible, a language that forces me to be inefficient won't do. =)
All-or-nothing lazy evaluation is easy enough:
| Code: |
(defmacro lazily (&rest exp)
`(let (val)
#'(lambda ()
(unless val (setf val ,exp))
val)))
(let ((x (lazily big-computation1))
(y (lazily big-computation2))
(z (lazily big-computation3)))
(cond (test1 (+ (x) (y)))
(test2 (+ (x) (z)))
(test3 (+ (y) (z)))))
|
I don't know if the parens around x/y/z can be eliminated with symbol macros (I haven't been using Lisp that long).
Obviously, the more interesting sort of lazy evaluation is for list construction, where only the portion you ask for is constructed (along with whatever that portion depends on, I suppose).
| Quote: |
Let's say I create a list of 1000 numbers and pass it to the qsort routine above. Now I only care about the 4 smallest numbers (the first 4 values in the list). The qsort routine will not execute until requested, and obviously only on those elements that are needed, meaning (in this extreme case), only the lt (less than) recursive routine will execute, and only until the first 4 values have been found.
|
In a Haskell compiler, lazy code must automatically be expanded to strict code at compile-time (it determines what work *really* has to be done). Lazily-constructed lists (whether they're lists of all primes or sorted versions of other lists) must internally carry enough state to hold the values that have already been computed, plus information about how to find more values (i.e. a closure).
I'm having trouble imagining what sort of strict code the lazy qsort would compile to. Do you have an idea of what that would look like in Lisp/pseudocode/whatever?
I'll be back with a macro for continuations. :-)
#14937 - sajiimori - Wed Jan 14, 2004 11:53 pm
An inefficient first try:
| Code: |
(defmacro defcontinuable (name args &body body)
`(defun ,name (&rest args)
(if (= (length args) ,(length args))
(apply #'(lambda ,args ,@body) args)
#'(lambda (&rest newargs)
(apply #',name (append args newargs))))))
; Usage:
(defcontinuable blah (a b c)
(* a (+ b c)))
; these all return 14
(blah 2 3 4)
(funcall (blah 2 3) 4)
(funcall (blah 2) 3 4)
(funcall (funcall (blah 2) 3) 4)
|
The runtime portion of the code can be optimized by determining the number of arguments at compile-time, and by avoiding the append.
#14942 - jma - Thu Jan 15, 2004 1:01 am
Very nice!
Two of the very best languages every are also two of the oldest: Lisp and Forth. Because (as you suggest) both lean as closely as they can to syntax-less code. And both are extensible (which requires syntax-less code).
Lisp and Forth always amaze me in what is possible. I love looking at C code in comparison and always laugh. For example, coding an ARM assembler (with parser) in C/C++ is a rather large endeavour. However, in Forth, my ARM (and THUMB) assembler is about 200 lines of code. I'm sure the same techniques used could be done in Lisp equally well.
One disadvantage is the needed to define extra syntax to accomplish the goal, though. Continuations are a thing of beauty. Your defcontuable is a good example of Lisp being at its best, but some downsides include: spaghetti code (relative, I admit)?, can you tell what executes at compile vs. run time?, and it does require using a new definition, whereas Haskell just has it out-of-the-box. So what? Well, because it is out-of-the-box, serious optimizations can be made.
Haskell follows currying rules. No function takes more than 1 argument. Each function is made up of smaller functions that each take a single value and return a new one. Passing just a single argument to a routine that needs two will return a pointer to the next function... much faster than your Lisp code. However, admittedly this will slow down overall if not used properly.
I suggest trying a little Forth. Forth and Haskell are my two favorite languages. Forth is good because it keeps you so close to the hardware -- it really is just a high-level assembler. Once you grok the power of Forth, you start to become very aware of what is being compiled and it becomes a nagging itch to try and optimize everywhere you can :)
I'm thoroughly enjoying this thread, I just hope it doesn't turn into a language vs. language debate -- I'd much rather focus on what makes each different and their strengths. Who knows, perhaps a new language will emerge from it?
Jeff
Note: if you want true, syntax-less code, check out Chuck Moore's colorForth: http://www.colorforth.com/cf.html
_________________
massung@gmail.com
http://www.retrobyte.org
#14947 - sajiimori - Thu Jan 15, 2004 2:53 am
I'm going to comment on your comments, and you'll just have to take my word that I'm not trying to start a hopeless language debate or a flamewar or anything. =)
On the other hand, I am very interested in the more general language-vs-language issue. Existing languages do have their strengths and weaknesses, but that doesn't mean I intend to use them all equally -- I want to find/develop the best one! ^_^
| Quote: |
One disadvantage is the needed to define extra syntax to accomplish the goal, though.
|
Hmm...I'm not sure I understand. Do you mean defining new operators? The code I posted is still made up entirely of s-expressions, all using plain old prefix notation. In contrast, the Loop facility in CL really does add syntax (which is part of why it's contreversial):
| Code: |
(loop for item in list
unless (member item result)
collect item into result
finally (return result)))
|
| Quote: |
spaghetti code (relative, I admit)?
|
Really?? Sure, it's dense -- Lisp tends to be that way. But spaghetti? It's only 6 lines, containing one branch. If my spaghetti looked like that, I'd send it back and complain. ;-)
| Quote: |
can you tell what executes at compile vs. run time?
|
Not according to ANSI Common Lisp -- it's implementation-defined. The standard only says that the code has to behave the same whether it's interpreted or compiled. If I wasn't sure about something, I'd probably check my compiler's output, or ask the developers.
But is it so bad to know? There's a difference between "knowing" and "having to think about", and if I decide that speed is not an issue, I can forget all about run-time vs compile-time.
| Quote: |
... much faster than your Lisp code.
|
Hey, gimme a break! =) I know it's not as fast as it can be -- I'm still learning. Removing the append and declaring the function inline could potentially reduce the currying process to returning a pointer (depending on the implementation, obviously).
| Quote: |
Once you grok the power of Forth, you start to become very aware of what is being compiled and it becomes a nagging itch to try and optimize everywhere you can :)
|
That's interesting. Maybe a lot can be said about a language based on what sort of itches you develop after using them. In the couple months I've used Lisp, the itch I've most often encountered is to mold the language in ways that make my code more natural, concise, and focused.
In fact, that pretty much sums up the reasons I stopped using C-like languages. Did you see my thread about trying to add Properties to C++? It was a joke! :O
I've been thinking about doing more with Forth, but I haven't found a reason. Is there an equivalence of code and data? Without that, it's impossible to do something like the Loop facility I mentioned earlier. If I want to make an embedded language like that, I have to be able to write code that writes code on-the-fly.
If I can't do that, but I still find that Forth is better than plain CL for a particular task, I can always add Forth to Lisp. ;-) In the end, I want a language that I can use in as many situations as possible, and I suspect that the answer is "the most flexible one".
When reading Forth code I feel like the parentheses are all still there, just implicit -- put an opening parenthesis at the start of an argument list, a closing one after the function word, then move the function word just after the opening paren, and you've got a Lisp form. There's no punctuation to obscure your view, but that means you have to rely on your knowledge about which words are data and which ones are functions.
#14956 - jma - Thu Jan 15, 2004 7:10 am
To reply briefly to two comments:
| Quote: |
| Really?? Sure, it's dense -- Lisp tends to be that way. But spaghetti? |
I did say "relative" :) mostly because I assume anyone with serious knowledge on Lisp could either a) do it better or b) understand it very easily. While I "technically" know Lisp, I'm hardly any kind of expert. I rarely use it for anything... and for speed:
| Quote: |
| Hey, gimme a break! =) I know it's not as fast as it can be -- I'm still learning. |
No problem. :) What I mean by this is the general speed of Lisp. The language does a lot for you under the hood. For example, try compiling this in Lisp:
| Code: |
| (defun my-add (a b) (+ a b)) |
Take a look at the compiled assembly. It is insane! That's because there is a lot of type checking, etc. going on (are a and b floats? bignums? ints?) Haskell doesn't haven that problem because it is strong typed (yet another language discussion). That was my only intention on commenting about speed.
| Quote: |
| There's a difference between "knowing" and "having to think about", and if I decide that speed is not an issue, I can forget all about run-time vs compile-time. |
That's my experience coming through. I code compilers (as a hobby) and do embedded programming for a living. Speed is almost always critical to what I do. I it sends shivers down my spine when I hear kids today not thinking about it, using the excuse that "the compiler or computer will make up for it" (not to imply that you are stating that).
| Quote: |
| I've been thinking about doing more with Forth, but I haven't found a reason. Is there an equivalence of code and data? Without that, it's impossible to do something like the Loop facility I mentioned earlier. |
I don't know the loop thread you are referring to. Usually I just pop my head in here to see if there is anything interesting and then leave. Only recently have I begun actually taking an interest :)
As for Forth and code/data: the answer is yes, but not to the extent of Lisp. I code almost exclusively embedded software, and Forth was designed for that purpose. So there are no 'lists' per-se unless you code them yourself. It isn't dynamic or have any kind of garbage collecting. In fact, usually Forth data is statically allocated. People usually freak when they hear this, but at the same time, a typical program of mine (we're talking ~ 1000 lines) has about 5-10 variables. Everything is "dynamically" done on the stack. The ARM assembler I referred to before has only 2 variables.
Forth is very easily extensible. As a brief example, in TIN (the underlying core of Dragon BASIC), the peephole optimizer is a simple extension of defining functions. In Lisp, it would be like creating a macro called DEFOPTIMIZED. It allows me to create routines with completely different syntax and optimizations for them. For example:
| Code: |
:OPTIMIZED ASM-LSHIFT (compile assembly code ) ;
:OPTIMIZED ASM-ADD ( compile assembly code ) ;
: ASM-LSL-ADD ( compiled optimized assembly code ) ;
OPTIMIZE ASM-LSHIFT ASM-ADD SUBSTITUTE ASM-LSL-ADD |
This is a simple example, but as the compiler runs and encounters ASM-LSHIFT followed by ASM-ADD, instead of running those, it will instead pattern match them and execute the ASM-LSL-ADD instead. As for creating code that makes code. Yes, it is possible. No, not nearly as easily as in Lisp. However, aside from those in A.I. fields, I rarely meet anyone who uses Lisp to do this (not counting macros, which Forth can do easily with IMMEDIATE words).
To consider a list of positive things in languages that I've used and like (or dislike), several things come to mind...
o Type-less (Lisp). Very nice, but lacks optimization capabilities
o Implied arguments (Forth/Haskell). Makes for fast subroutine calls
o Interactive debugging. Once used, I pity the fool that doesn't have it
o Small. This may just be me, but optimizations become very easy the smaller the code-base. CL is just plain huge, as is Haskell and others. And I'd much rather use a simple K&R C than MFC any day...
o Syntax-less. This is the only way to get extensibility.
o Functional. Except it needs something other than monads. I also disagree with the side-effects of Lisp and Scheme. There is something out there better, yet to be discovered (I can just feel it).
Trying not to troll here at the end, but I'd like to add that I think OOP is a waste. It is good for some things, but there is nothing it does that can't be done without it. And if you really want it, given a language that is extensible, it should be easy to add.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#14963 - sajiimori - Thu Jan 15, 2004 10:16 am
| Quote: |
I don't know the loop thread you are referring to.
|
I gave the example earlier in the same post.
| Quote: |
As for creating code that makes code. Yes, it is possible. No, not nearly as easily as in Lisp. However, aside from those in A.I. fields, I rarely meet anyone who uses Lisp to do this (not counting macros, which Forth can do easily with IMMEDIATE words).
|
Macros are like functions that don't evaluate their arguments, and return code. This code:
| Code: |
(defmacro while (test &body body)
`(do ()
((not ,test) nil)
,@body))
(while (< x 10)
(print (incf x)))
|
...is essentially the same as this:
| Code: |
(defun while (test &body body)
`(do ()
((not ,test) nil)
,@body))
(eval (while '(< x 10)
'(print (incf x))))
|
Macros just make things prettier by automatically quoting arguments and evaluating the generated code. So specifying "not counting macros" is a little strange -- it's like saying "hardly anybody generates code, except in the most convenient way". =)
| Quote: |
Type-less (Lisp). Very nice, but lacks optimization capabilities
|
CL is not typeless at all, and it's very optimizable. Example:
| Code: |
(defun my-add (a b)
(declare (fixnum a b))
(the fixnum (+ a b)))
|
If you look at the assembly for that, you'll find that it's remarkably similar to C compiler output (on fast implementations, of which there are several -- try CMUCL). You just have to give the compiler the information it needs. It has no way of knowing whether a and b are small enough to fit in registers, and no way of knowing whether a + b will cause an overflow. Even in Haskell, that information just isn't available to the compiler unless you provide it.
| Quote: |
Implied arguments (Forth/Haskell). Makes for fast subroutine calls
|
Example? It reminds me of optional arguments (which CL has), but I'm not sure if that's what you mean.
| Quote: |
CL is just plain huge, as is Haskell and others.
|
True. I'd like to argue that CL has a relatively small "core" language, but with a large "library", but in reality that distinction just doesn't exist -- the line between language and library blurs the more you learn Lisp, because it becomes clear that each new "library" function is really extending the language. I mean, things that seem like primitives in other languages (if, defun, let) are implemented as macros in many versions of CL.
To complicate things further, the CL standard doesn't specify which parts of the language have to be implemented as primitives.
But *some* distinction has to be made between a statement like "CL is large" versus, for instance, "C++ is large". Perhaps it's sufficient to say that C++, the language, minus the standard library, is *irreducably* large. You can't implement a part of it in a subset of it, without bootstrapping a new compiler.
So while the decision regarding where to draw the line between "primitive" and "library/extention/utility" in CL is somewhat arbitrary (Pure Lisp only needs 7 primitive operators), it's easy enough to recognize that the vast majority of it can be implemented in the remaining portion.
| Quote: |
Functional. Except it needs something other than monads. I also disagree with the side-effects of Lisp and Scheme. There is something out there better, yet to be discovered (I can just feel it).
|
Cool, I look forward to using it. ;-)
On a related note, I was asking earlier about how one might go about optimizing that qsort you posted. Is it possible to avoid producing so much garbage? Side-effects are handy when efficiency is a concern -- you need them if you're going to sort in-place.
| Quote: |
Trying not to troll here at the end, but I'd like to add that I think OOP is a waste. It is good for some things, but there is nothing it does that can't be done without it. And if you really want it, given a language that is extensible, it should be easy to add.
|
I think Paul Graham said it well:
| Quote: |
With eight lines of code we have made plain old pre-CLOS Lisp into an object-oriented language [including inheritence]. How did we manage to achieve such a feat? There must be some sort of trick involved, to implement object-oriented programming in eight lines of code.
There is a trick, but it is not a programming trick. The trick is, Lisp already was an object-oriented language, or rather, something more general. All we had to do was put a new facade on the abstractions that were already there.
|
In other words, the generality and flexibility of Lisp actually has to be constrained to make it act like an OO language.
#14984 - jma - Thu Jan 15, 2004 6:53 pm
| Quote: |
| Macros just make things prettier by automatically quoting arguments and evaluating the generated code. So specifying "not counting macros" is a little strange -- it's like saying "hardly anybody generates code, except in the most convenient way". =) |
I meant to imply that macros create code at compile-time. I don't know many Lispers (other than A.I. developers) that create code (at run-time) to execute (at run-time).
| Quote: |
| CL is not typeless at all, and it's very optimizable. |
As I stated earlier, I don't want this to come down to a this language vs. language debate, which you called "hopeless". All languages were created for a problem to be solved. Use the language that better suits the problem. It just seems like you have your heart set on proving Lisp can be a do-all =) and that's fine if Lisp makes you happy. It is a good language -- no doubt, I'm just trying to examine what makes the languages we are discussing good and bad. Without that, there is no room for improvement.
In all my time programming, there appear to be trade-offs that just can't seem to be avoided, no matter what language you use:
o Typeless adds felxibility, but removes optimization -- especially in an interactive environment.
o There is a linear exchange between speed at run-time vs. speed of programming. I can code qsort in Haskell much faster than in C, but the C code executes much faster.
o You can't have both low-level access and high-level abstraction (or can you?). At least I have yet to see it.
I'm also curious in the computer world, where the "breaking point" of usefullness lies. For example, the more libraries, functions and syntax constructs a language has, typically the more useful it is. However, when it gets to be too large, the speed, optimizations and degree to which the language can be improved on drop dramatically. The same can be said for operating systems and and software package... What is the point to which you say, "this is what it does and no more! If you want to expand, fine, use what is provided!" As examples I give: Windows, Lisp, C++, Python, ANS Forth and the list could go on... no language can or should be a do-all for everyone. The minute it tries to be it becomes doomed.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#14992 - sajiimori - Thu Jan 15, 2004 8:51 pm
The thing is, I'm not content to just list off the supposed benefits of each language and leave it at that. (Otherwise a C++ guy could come in and say it makes your software more modular, reusable, and safe.) The differences between languages are more complex than what you can fit on a bullet-pointed list. If I don't give the best presentation of CL that I can, I won't be satisfied that we've discovered any sort of interesting relationship between the languages.
You said Lisp (presumably CL) is typeless (I think you meant "dynamically typed", which is different), and that you can't optimize that. I honestly thought you'd accept my straightforward correction, because the statement was flat-out false.
If you want me to ignore such things, what would be the point of this thread? To pat ourselves on the back for using cool languages?
| Quote: |
o Typeless adds felxibility, but removes optimization -- especially in an interactive environment.
|
Agreed. I want a language that allows me to do both, depending on how fast I want to write. Worrying about types while building a prototype is annoying. (BTW, if you want to see a real typeless language, rather than just a dynamically typed one, I can send you a compiler I wrote -- there is truly zero type information.)
| Quote: |
o There is a linear exchange between speed at run-time vs. speed of programming. I can code qsort in Haskell much faster than in C, but the C code executes much faster.
|
Absolutely. So, I want a language where I can write code fast and have it run slow, or spend more time on it and have it run fast.
| Quote: |
o You can't have both low-level access and high-level abstraction (or can you?). At least I have yet to see it.
|
I don't see why not. All you have to do is take <insert-favorite-abstract-language> and add low-level primitives that provide direct memory/hardware access, right? The only real-life examples I know of are from Lisp (sorry).
Corman Lisp for Windows has inline assembler (as I'm sure others do).
Lisp Machines (at least by Symbolics) had drivers and garbage collectors written in Lisp.
Movitz: A Common Lisp OS development platform
http://www.cs.uit.no/~frodef/los0/
| Quote: |
For example, the more libraries, functions and syntax constructs a language has, typically the more useful it is. However, when it gets to be too large, the speed, optimizations and degree to which the language can be improved on drop dramatically.
|
I don't see any reason that a large library would affect efficiency (I dunno about syntax -- my gut tells me that shouldn't affect (runtime) speed either). I guess it's true that with each improvement, there's less improvement remaining to be done.
I'd say the bigger issue is how hard it is to learn the language. I don't like languages that are so big that no one person knows the whole thing (like the Win32 API).
That's another benefit of extensible languages -- the language designers don't have to provide everything from the start. =)
#14993 - ampz - Thu Jan 15, 2004 9:29 pm
One could say that working with the win32 API means you are working at a much higher abstraction level compared to working directly with GBA hardware.
Still, a win32 application requires ten times the amount of code compared to the same application on GBA.
I don't find java or C++ any bit faster to code in than C, and the extra complexity just irritates me.
Never tried Lisp.
I prefer C and the just the standard libs. Simplicity is a good thing.
#14994 - jma - Thu Jan 15, 2004 9:37 pm
| sajiimori wrote: |
| The thing is, I'm not content to just list off the supposed benefits of each language and leave it at that. (Otherwise a C++ guy could come in and say it makes your software more modular, reusable, and safe.) |
I just think a bullet points list is a good place to start. Without defining what you need or want, whatever you come up with will be lacking. And perhaps in doing so you will find contradictory requirements. As far as this hypothetical "C++ guy", there would be nothing wrong with those statements. Admittedly, those statements are more about good programming in general, though, and have nothing to do with a particular language.
| Quote: |
| If I don't give the best presentation of CL that I can, I won't be satisfied that we've discovered any sort of interesting relationship between the languages. |
What kind of relationship are you looking for? If you just want to compare Haskell and Lisp, I can do that =) If you want to look more in depth at a meriad of languages to see what makes each special, a little less time spent on each would be in order.
IMHO, Haskell is nothing more than someone who liked Lisp, but didn't like a) side-effects, b) those damn parens and c) dynamic type system. Once he removed those features, it left him open to the possibilities of doing some other things (like the list generator syntax) to make his life easier. Neither method is right or wrong, and which is better is only defined by the problem being solved at the moment.
| Quote: |
| You said Lisp (presumably CL) is typeless (I think you meant "dynamically typed", which is different) |
I did, my bad.
| Quote: |
| I honestly thought you'd accept my straightforward correction, because the statement was flat-out false. |
I feel that it was "techincally" false, but not "flat-out" false. =) By this I merely mean to imply that when I'm programming, I don't want to have to go back and re-code just to add something as simple as a type optimization (this has the potential of breaking code). Some optimizations need to be done by hand (loops, pointers, etc). However, I feel that many optimizations are the compiler's duty: types, inlining, register allocation, etc.
| Quote: |
| If you want me to ignore such things, what would be the point of this thread? To pat ourselves on the back for using cool languages? |
It certainly would be easier =). Perhaps we're both looking at this thread from a different perspective as to what we want to get out of it. From your statement above, I gather you just want to compare Haskell and Lisp:
| Quote: |
| This thread is (initially) about the things that Haskell has that Common Lisp does not -- yet. ;-) |
However, I'm hoping to take it a step further and try and distinguish what the reasons are, what can be gained from each, and what new language could get the best of both worlds.
So far, it seems as though anything Haskell can do, Lisp can do, too. The Haskell versions will execute faster than the Lisp code, only because the Lisp wasn't (initially) designed to do what Haskell is doing (like continuations). But at the same time, Lisp is extensible, which is why it is possible to add these abilities to it (and why the optimizer will have a difficult time compensating).
However, try not to compare Lisp to Haskell as: Haskell can do this... well, with a little work, so can Lisp! So can C for that matter. Look at GHC (http://www.haskell.org/ghc), it compiles Haskell code to C, so C must be able to do what Haskell can. Does that make C equivelant or better than Haskell? Instead, try to answer the question: why does Haskell exist? what problems does it solve (easily)?
| Quote: |
I'd say the bigger issue is how hard it is to learn the language. I don't like languages that are so big that no one person knows the whole thing (like the Win32 API).
That's another benefit of extensible languages -- the language designers don't have to provide everything from the start. =) |
Agreed.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#14995 - sajiimori - Thu Jan 15, 2004 10:51 pm
| Quote: |
One could say that working with the win32 API means you are working at a much higher abstraction level compared to working directly with GBA hardware.
Still, a win32 application requires ten times the amount of code compared to the same application on GBA.
|
Win32 abstracts a very different set of capabilities than the GBA hardware interface, so it's not really informative to compare the amount of code it takes to perform particular tasks with each. How much code does it take to make a tile engine with sprites on Win32? How much does it take to put up a scalable, scrollable window with a title bar and icons on GBA? Who cares? =)
| Quote: |
I don't find java or C++ any bit faster to code in than C, and the extra complexity just irritates me.
|
As far as C++, I definitely agree. In all fairness though, I don't think the focus of C++ is making it faster to write code. It seems to be more about fixing problems with C regarding modularity, generality, and safety -- barriers to writing really large applications.
With Java, it depends. Garbage collection and all the extra safety checks let me code really sloppily if I feel like it -- but the fact is, I simply hate Java. It's main purpose seems to be putting a straight-jacket on large teams of mediocre programmers, so none of them will break anything too badly.
| Quote: |
Never tried Lisp.
I prefer C and the just the standard libs. Simplicity is a good thing.
|
I like simplicity too. Until I started using Lisp, C was the simplest thing I had used.
| Quote: |
What kind of relationship are you looking for?
|
Pretty much this one:
| Quote: |
Haskell is nothing more than someone who liked Lisp, but didn't like a) side-effects, b) those damn parens and c) dynamic type system. Once he removed those features, it left him open to the possibilities of doing some other things (like the list generator syntax) to make his life easier.
|
Thanks. :-)
I asked earlier about side-effects in Haskell (twice) -- I guess you probably have limited time to post. So, can you sort in-place in Haskell to avoid garbage?
| Quote: |
If you want to look more in depth at a meriad of languages to see what makes each special, a little less time spent on each would be in order.
|
Familiar with Meyers-Briggs personality profiles? Sounds like the difference between an "ST" and an "NT". STs tend to want to survey a wide range of topics and get a feel for the landscape, whereas NTs usually want to focus on one thing at a time, until they really get to the bottom of things. In other words, I analyze things to death. ;-)
| Quote: |
...when I'm programming, I don't want to have to go back and re-code just to add something as simple as a type optimization (this has the potential of breaking code).
|
Interesting. I really don't know Haskell so you'll have to bear with me: Do you have to specify types from the beginning (like C), or does the compiler implicitly type everything? Can you specify that an integer is small enough to fit in a register (so it doesn't have to check if it's an oversized number at runtime), or specify that the addition of 2 integers won't overflow a register?
| Quote: |
However, try not to compare Lisp to Haskell as: Haskell can do this... well, with a little work, so can Lisp! So can C for that matter.
|
Yeah, you can implement Haskell or Lisp in C, same as any other Turing Complete language. But trying to add continuations to C (without bootstrapping a new compiler) isn't the same thing. You can't encapsulate it, or make its usage anywhere near as simple as it is in Haskell. Every time you want to use a continuation, you have to rewrite all the structural code to support it.
In short, the difference is between "Sure, my language can do that with a little extra work (every time I want to do it)" compared to "My language can do that (with comparably simple usage) if I implement it once and throw it in my startup image".
(BTW, you seem to be speculating a lot about what CL optimizers can and cannot do compared to Haskell optimizers. Do you have any support, or are you just thinking out loud?)
#14996 - ampz - Thu Jan 15, 2004 11:02 pm
| sajiimori wrote: |
| Quote: |
I don't find java or C++ any bit faster to code in than C, and the extra complexity just irritates me.
|
As far as C++, I definitely agree. In all fairness though, I don't think the focus of C++ is making it faster to write code. It seems to be more about fixing problems with C regarding modularity, generality, and safety -- barriers to writing really large applications.
With Java, it depends. Garbage collection and all the extra safety checks let me code really sloppily if I feel like it -- but the fact is, I simply hate Java. It's main purpose seems to be putting a straight-jacket on large teams of mediocre programmers, so none of them will break anything too badly.
|
I agree. The java syntax and naming conventions are better than C++.
| Quote: |
| Quote: |
Never tried Lisp.
I prefer C and the just the standard libs. Simplicity is a good thing.
|
I like simplicity too. Until I started using Lisp, C was the simplest thing I had used.
|
Oh, sounds like I should try Lisp...
What I do miss is a hardware description language that make sense... VHDL is crap.
#14997 - jma - Thu Jan 15, 2004 11:08 pm
| sajiimori wrote: |
| Familiar with Meyers-Briggs personality profiles? Sounds like the difference between an "ST" and an "NT". STs tend to want to survey a wide range of topics and get a feel for the landscape, whereas NTs usually want to focus on one thing at a time, until they really get to the bottom of things. In other words, I analyze things to death. ;-) |
Haha! I have heard that before... :)
| Quote: |
| Quote: |
...when I'm programming, I don't want to have to go back and re-code just to add something as simple as a type optimization (this has the potential of breaking code).
|
Interesting. I really don't know Haskell so you'll have to bear with me: Do you have to specify types from the beginning (like C), or does the compiler implicitly type everything? |
Haskell is interesting in this regard. Like Lisp, you can do it yourself or leave it to the compiler. However, it is better (IMO) in both regards. For example:
When the compiler encounters this, it will attempt to "figure out" what n is. With the * operator, it will then guess that it is a number, but no more than that, so it actually codes integer, real, complex, etc, much in the same way that Lisp would. However, it also catches type errors at compile time (like if I tried to do SQ "Hello, world!").
Now, if I want to tell the compiler myself what type n is, that is trivial to do and then lets the compiler only handle that type. The difference is that all I need to do is code a single line to prototype the function:
| Quote: |
| (BTW, you seem to be speculating a lot about what CL optimizers can and cannot do compared to Haskell optimizers. Do you have any support, or are you just thinking out loud?) |
Thinking out loud. I've been writing compilers (Forth mostly) for quite a while now, and I have quite a bit of experience with optimizing, etc. However, I do have 0 (z-e-r-o) experience with Lisp compilers. I'm sure they are better than I make them out to be, I can see the potential difficulties in designing one.
| ampz wrote: |
| Still, a win32 application requires ten times the amount of code compared to the same application on GBA. |
That is only because you need to work through the OS (and Microsoft sucks). Coding "Hello, world!" on Linux is probably the same size or smaller than the GBA equivelant (because the GBA requires a tileset, palette, etc).
| Quote: |
| I don't find java or C++ any bit faster to code in than C, and the extra complexity just irritates me. |
Probably just because you aren't as familiar with either of them (please correct me if I'm wrong -- about complexity). But likewise, C++ and Java are far more verbose than C, so perhaps that is what you were referring to? =)
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#14999 - tepples - Thu Jan 15, 2004 11:15 pm
| sajiimori wrote: |
| How much code does it take to make a tile engine with sprites on Win32? |
Typically, a 2D game programmer on Windows would find a permissively licensed tile engine that runs on top of the Allegro library and reuse it.
| Quote: |
| How much does it take to put up a scalable, scrollable window with a title bar and icons on GBA? |
You're limited to four overlapping windows, but it's relatively easy to do something like this in GBA tile modes.
| Quote: |
I asked earlier about side-effects in Haskell (twice) -- I guess you probably have limited time to post. So, can you sort in-place in Haskell to avoid garbage? |
I'd like to clarify that though garbage collection takes time, so do malloc() and free(). A program realizes benefits of avoiding garbage largely in the CPU's data cache.
| Quote: |
STs tend to want to survey a wide range of topics and get a feel for the landscape, whereas NTs usually want to focus on one thing at a time, until they really get to the bottom of things.
|
In other words, some people search for knowledge breadth-first, whilst others do a depth-first search. Remember that depth-first search can prove dangerous without iterative deepening.
Within this analogy, wisdom gained through experience becomes a heuristic, which permits best-first methods such as A* for STs and pruning for NTs.
| Quote: |
| I really don't know Haskell so you'll have to bear with me: Do you have to specify types from the beginning (like C), or does the compiler implicitly type everything? |
Haskell has some form of "type inference," whatever that is.
| Quote: |
| But trying to add continuations to C (without bootstrapping a new compiler) isn't the same thing. |
Extending a language with "lots of syntax" doesn't require "bootstrapping a new compiler." Look at Qt's MOC, which extends C++ with signal/slot semantics by preprocessing the source code. Heck, look at early C++ compilers that output C source code, which they pass on to the system's native C compiler.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#15004 - ampz - Fri Jan 16, 2004 12:23 am
| tepples wrote: |
| Quote: | | How much does it take to put up a scalable, scrollable window with a title bar and icons on GBA? |
You're limited to four overlapping windows, but it's relatively easy to do something like this in GBA tile modes.
|
So true :)
Even in windows, games and applications use several layers of librarys and APIs on top of each other in order to do stuff that can be handled by the hardware in the first place.
The PC graphics hardware can do much more than the GBA hardware can do. Still, we have ten layers of librarys inbetween that many times just consume CPU and memory resources and sometimes even make it more complex to do what you want to do.
| Quote: |
| Quote: |
I asked earlier about side-effects in Haskell (twice) -- I guess you probably have limited time to post. So, can you sort in-place in Haskell to avoid garbage? |
I'd like to clarify that though garbage collection takes time, so do malloc() and free(). A program realizes benefits of avoiding garbage largely in the CPU's data cache.
|
The new dynamic arrays and alloca fetures in C do not take any time at all. Not a single cycle. They also eliminate the risk for memory leaks. Of course they cannot replace malloc in all applications.
#15005 - sajiimori - Fri Jan 16, 2004 12:33 am
| Quote: |
Typically, a 2D game programmer on Windows would find a permissively licensed tile engine that runs on top of the Allegro library and reuse it.
...
You're limited to four overlapping windows, but it's relatively easy to do something like this in GBA tile modes.
|
tepp, you just dodged the point like Neo dodging bullets. :-D
*imagines tepples leaning backwards in slow motion*
| Quote: |
I'd like to clarify that though garbage collection takes time, so do malloc() and free().
|
Sure. That's why I was talking about sorting in place -- it doesn't need either.
| Quote: |
A program realizes benefits of avoiding garbage largely in the CPU's data cache.
|
That depends on lots of things, obviously. On medium-to-small systems (no cache, less than a meg of RAM), the problem might be in maintaining consistent performance. In any case, we can at least say that producing no garbage is generally more efficient than producing lots of it, all other things being equal.
| Quote: |
Remember that depth-first search can prove dangerous without iterative deepening.
|
A thread is a short enough iteration for me, so I feel confident about doing an in-depth comparison between Lisp and Haskell. I chose Lisp because it's currently my favorite language, and I chose Haskell because it's sort of the "latest and greatest" of functional languages, and lots of pros really dig it. Also, having somebody here who knows it helps. ;-)
| Quote: |
Extending a language with "lots of syntax" doesn't require "bootstrapping a new compiler." Look at Qt's MOC, which extends C++ with signal/slot semantics by preprocessing the source code. Heck, look at early C++ compilers that output C source code, which they pass on to the system's native C compiler.
|
Ah, but then you are no longer using the same language. MOC is a compiler: it's a program that translates from one language to another (presumably lower-level) language. Code that uses MOC is not in C++, because a proper C++ implementation won't understand it.
Similarly, just because a C++ compiler happens to output C, that doesn't mean you're writing in C. Same goes for compiling C to assembly.
To clarify: when I say "extending a language", I don't just mean inventing a new language based on an old one. I mean implementing new language features, in the same language, while retaining the exact same compiler.
#15006 - jma - Fri Jan 16, 2004 12:40 am
| sajiimori wrote: |
| I asked earlier about side-effects in Haskell (twice) -- I guess you probably have limited time to post. So, can you sort in-place in Haskell to avoid garbage? |
Just to answer this, I don't know. To my knowledge, the answer is 'no'. But I'm not a Haskell expert by any stretch of my [wild] imagination =)
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#15007 - sajiimori - Fri Jan 16, 2004 12:58 am
| Quote: |
However, it also catches type errors at compile time (like if I tried to do SQ "Hello, world!").
|
That's cool -- my CL implementation doesn't catch argument type errors at compile-time, presumably because symbols can refer to different functions at different times, so it theoretically can't know if there's a problem. Maybe symbols should not be allowed to rebind their function values, once assigned. I don't think it would be a big loss.
| Code: |
; SQ :: Int -> Int
; When you declare types in CL, you specify them
; inside the function, rather than as a seperate prototype.
; However, it's slightly more general because you can
; declare the type of the result of any expression,
; not just the results of whole functions.
(defun sq (x)
(declare (fixnum x))
(the fixnum (* x x)))
|
#15019 - jma - Fri Jan 16, 2004 4:20 am
| ampz wrote: |
| The new dynamic arrays and alloca fetures in C do not take any time at all. Not a single cycle. |
This just wrong. The time may be small, but it is there. Nothing (I repeat -- nothing) is free. alloca() allocates data on the stack, which means returning a value that is based on the SP (a simple SUB instruction) which takes (at least) 1 cycle.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#15027 - poslundc - Fri Jan 16, 2004 6:01 am
| jma wrote: |
| ampz wrote: | | The new dynamic arrays and alloca fetures in C do not take any time at all. Not a single cycle. |
This just wrong. The time may be small, but it is there. Nothing (I repeat -- nothing) is free. alloca() allocates data on the stack, which means returning a value that is based on the SP (a simple SUB instruction) which takes (at least) 1 cycle. |
Rats... so much for my plan to use the pointers returned by alloca for all of my mathematical calculations, thereby optimizing them to infinite speed... :(
Dan.
#15037 - ampz - Fri Jan 16, 2004 11:58 am
| jma wrote: |
| ampz wrote: | | The new dynamic arrays and alloca fetures in C do not take any time at all. Not a single cycle. |
This just wrong. The time may be small, but it is there. Nothing (I repeat -- nothing) is free. alloca() allocates data on the stack, which means returning a value that is based on the SP (a simple SUB instruction) which takes (at least) 1 cycle.
Jeff |
Yes, true, the alloca requires one cycle to calculate the pointer, but the dynamic arrays do not neccessarily require that (assuming a good optimising compiler).
#15068 - sajiimori - Fri Jan 16, 2004 8:44 pm
| Code: |
f()
{
int i;
i = g();
int a[i];
}
|
How could the compiler know how much stack to allocate?
#15074 - ampz - Fri Jan 16, 2004 9:26 pm
A declaration after a statement?
#15075 - sajiimori - Fri Jan 16, 2004 9:31 pm
Yup, C99 adds dynamic arrays, and declarations at any point in the body.
#15076 - tepples - Fri Jan 16, 2004 9:33 pm
Perfectly valid in C99. It expands to the equivalent | Code: |
int f()
{
int i;
i = g();
{
int a[i];
}
} |
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#15078 - jma - Fri Jan 16, 2004 9:42 pm
| sajiimori wrote: |
| Code: |
f()
{
int i;
i = g();
int a[i];
}
|
How could the compiler know how much stack to allocate? |
Using ARM assembly (this is a GBA forum after all), this would be the only possible optimization for this (assuming both i and a were stored in registers):
| Code: |
f:
BL ( g ) ; r0 = return value
MOV r5,r0 ; i = r5
SUB r4,sp,r5 LSL #2 ; allocate dynamic memory on stack
; notice: the allocation still took a cycle
; ...
LDR r0,[r4,#4] ; load a[1]
; ... |
It would be rare to see this be the only code generated by the compiler, though. The compiler needs to take into account other variabilities (like multiple, local arrays, etc.)
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#15079 - sajiimori - Fri Jan 16, 2004 10:02 pm
Then again, taking the code literally:
In principle, there should be situations where the compiler can't know how much stack to allocate -- I'm just too lazy to make one up. ;-)
#15090 - tepples - Fri Jan 16, 2004 11:32 pm
| jma wrote: |
| Code: | f:
BL ( g ) ; r0 = return value
MOV r5,r0 ; i = r5
SUB r4,sp,r5 LSL #2 ; allocate dynamic memory on stack
; notice: the allocation still took a cycle
; ...
LDR r0,[r4,#4] ; load a[1]
; ... |
|
What if this gets interrupted? Does what's allocated get overwritten with saved registers?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#15091 - sajiimori - Fri Jan 16, 2004 11:50 pm
Seems like the function needs a proper stack frame, then SUB sp,sp,r5 LSL#2
#15093 - jma - Sat Jan 17, 2004 12:54 am
Of course, to be totally anal about it :P it could be in THUMB mode, too...
LSL R4,R5,#2
NEG R4,R4
ADD R4,SP
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#15495 - sajiimori - Fri Jan 23, 2004 6:43 am
I've been messing around with the idea of a strongly, implicitly typed Lisp. My approach is to translate to human-readable C. I'm not sure how it's going to work out, but it's been interesting so far.
Here's some test input:
| Code: |
; I'm co-opting 'declaim' to play the role of prototypes for now.
; The vertical bars are needed to make the Lisp reader
; case-sensitive.
(declaim (function |puts| (string)))
(defun main-test (x y)
(plus-two 2)
(plus-two 8.71)
; (plus-two "hello") <-- compile-time error
(factorial 5)
(if x
(test "x isn't zero")
(test "x is zero")))
(defun plus-two (x) (+ x 2))
(defun test (str)
; This 'if' returns two different types, but it doesn't
; cause an error because the return value isn't
; used.
(if str
2
"asdf")
(let ((x 5.2) (y 2))
(|puts| str)
(+ x y)))
(defvar global-thing 10)
(defvar another-thing "qwerty")
(defun factorial (x)
(if (= x 0)
1
(* x (factorial (- x 1)))))
; This code goes into main(), because it's
; at the toplevel.
(main-test 5 10)
|
And the resulting C output:
| Code: |
int puts(char*);
float main();
float MAIN(int, int);
float TEST(char*);
int FACTORIAL(int);
int PLUS_TWO(int);
float PLUS_TWO(float);
char* ANOTHER_THING = "qwerty";
int GLOBAL_THING = 10;
float main()
{
return
MAIN(5, 10);
}
float MAIN(int X, int Y)
{
PLUS_TWO(2);
PLUS_TWO(8.71);
FACTORIAL(5);
return
X ?
TEST("x isn't zero") :
TEST("x is zero");
}
float TEST(char* STR)
{
int __gensym2;
float __gensym1;
STR ?
2 :
"asdf";
return
__gensym1 = 5.2,
__gensym2 = 2,
puts(STR),
__gensym1 + __gensym2;
}
int FACTORIAL(int X)
{
return
X == 0 ?
1 :
X * (FACTORIAL(X - 1));
}
float PLUS_TWO(float X)
{
return
X + 2;
}
int PLUS_TWO(int X)
{
return
X + 2;
}
|
You'll probably notice that this is actually C++ code because it uses function overloading. Especially note the 2 versions of PLUS_TWO that are automatically generated, and also the percolation of the type of 5.2 + 2, so that the return type of main() is determined to be float. Unused functions are not generated.
Some of the code generation strategies obviously flip-flop between breaking operations into statements, and trying to squeeze everything into single expressions (evidenced by the neurotic use of the comma operator).
Problems are arising now that I want to introduce 'while' and 'switch', because those can't be embedded in expressions (in either C99 or C++). Because Lisp allows arbitrary nesting of conditionals, local declarations, and iteration constructs, and C is just not up for that task, I'm left with 2 options:
1) Break everything down into statements. Very ugly, and hard to generate.
2) Use GNU extensions for embedding statements in expressions.
CLICC is an existing Lisp -> C translator that attempts to implement almost all of CL. Because it uses the first approach, its output is pretty hard to follow...
Comments/suggestions?
#15508 - jma - Fri Jan 23, 2004 5:12 pm
Not a bad first crack, Sajiimori. The difficulty you are going to have will not be in translating simple routines like the ones above, but rather these issues:
o Closures
o Symbols & Quoting
o Tail-recursion
o Garbage collection
C/C++ compilers almost never optimize tail-recursive functions. Hell, they won't even optimize tail-calls. As this is a very important aspect of functional programming (because so many functions are tail-recursive) this could come back to bite you.
Symbols and quoting will probably be even more difficult for you. So far you have a decent system for compiling typed functions, but what about untyped? If you are serious about this project, you need to take a step back and work out a (even simple) system for passing CELLS or OBJECTS instead of typed data. This doesn't necessarily mean using C++ (which would be incredibly slow). This system could also help you with GC, too. A simple example would be (in C):
| Code: |
typedef enum LISPTYPE {
INT = 0,
CHAR,
STRING,
CONS,
FLOAT,
SYMBOL,
} LISPTYPE;
typedef struct LISPOBJ {
unsigned int refCount;
LISPTYPE type;
} LISPOBJ;
typedef struct LISPINT {
LISPOBJ obj;
long value;
} LISPINT;
typedef struct LISPCONS {
LISPOBJ obj;
LISPOBJ *car;
LISPOBJ *cdr;
} LISPCONS;
/* TODO: all other types */
unsigned int OBJECT_SIZE(LISPTYPE type) {
switch(type) {
case INT: return sizeof(LISPINT);
case CONS: return sizeof(LISPCONS);
/* TODO: ... */
}
}
LISPOBJ *New(LISPTYPE type) {
LISPOBJ *obj = (LISPOBJ*)malloc(OBJECT_SIZE(type));
obj->type = type;
obj->refCount = 0; /* <--- IMPORTANT! */
/* TODO: add obj to the global GC */
return obj;
}
LISPOBJ *AddRefCount(LISPOBJ *obj) {
obj->refCount++;
return obj;
}
LISPOBJ *Release(LISPOBJ *obj) {
if (!--obj->refCount) {
free(obj);
return 0;
}
return obj;
} |
This should give a kind of starting point. Now, you construct your Lisp primitive functions (libraries) that are made up of C functions:
| Code: |
LISPOBJ *Plus(LISPOBJ *o1,LISPOBJ *o2) {
if (o1->type == INT && o2->type == INT) {
LISPINT *obj = (LISPINT*)New(INT);
obj->value = ((LISPINT*)o1)->data + ((LISPINT*)o2)->data;
return AddRefCount(obj);
}
/* TODO: other types */
}
LISPOBJ *Car(LISPOBJ *cons) {
if (cons->type != CONS) {
/* TODO: error */
}
return AddRefCount(((LISPCONS*)cons)->car);
} |
I think you can get the idea from these... You also need a hash table of some kind to help sort out symbols (of course, you'll need 2, one for functions and one for variables if you want lisp-2 vs. lisp-1).
The garbage collector could initially be a simple linked list, but should eventually be something much more efficient. It would just be a linked list of LISPOBJ types, and every once in a while, just call a Collect routine:
| Code: |
typedef struct GC {
LISPOBJ *obj;
struct GC *next;
} GC;
void Collect(GC *gc) {
if (!gc->obj->refCount) {
/* TODO: remove from list and free(obj); */
}
Collect(gc->next);
} |
Also, take a look at Gambit (a Scheme->C compiler). It does a very good job, and it is worth looking at. If you are serious about the project, though, and would like to work with someone, I'd be happy to lend help where I can.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#15511 - tepples - Fri Jan 23, 2004 6:06 pm
| jma wrote: |
| C/C++ compilers almost never optimize tail-recursive functions. |
According to this page at RedHat.com about GCC, GCC does optimize tail recursion.
| Quote: |
| Code: | typedef struct LISPOBJ {
unsigned int refCount;
LISPTYPE type;
} LISPOBJ; |
|
Does reference counting work well once reference graphs become circular?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#15513 - jma - Fri Jan 23, 2004 7:04 pm
| tepples wrote: |
| jma wrote: | | C/C++ compilers almost never optimize tail-recursive functions. |
According to this page at RedHat.com about GCC, GCC does optimize tail recursion. |
That's good to know!
| Quote: |
| Does reference counting work well once reference graphs become circular? |
No, but it's a starting point. Circular references are pretty rare. Usually you see them in binary trees and linked lists (pointers to the parent nodes), but that can be avoided if you know ahead of time.
Jeff
_________________
massung@gmail.com
http://www.retrobyte.org
#15517 - sajiimori - Fri Jan 23, 2004 9:19 pm
First off, I don't intend to implement garbage collection in the near future. If everything else works out somehow, I'm confident that garbage collection could be implemented in a future implementation (for instance, when I get the compiler to compile itself). On the other hand, I'm not confident that everything else is going to work, so GC is low priority.
I think tail-recursion won't be very hard (it's high on my to-do list). If I'm not mistaken, all you have to do is find out if none of the return values from recursive calls are altered before being returned themselves, and if that's the case, replace the calls with assignments to the args and a jump to the top of the function. Are there any harder cases than that?
I don't have a really complete, intuitive understanding of closures yet. What do you think of this?
| Code: |
(defun make-adder (x)
#'(lambda (y) (+ x y)))
|
| Code: |
/* shared lisp struct */
struct __closure
{
void* enclosed;
void* func;
};
/* generated code */
struct __gentype1
{
int X;
};
int __genfunc1(__gentype1* __gensym1, Y)
{
return
__gensym1->X + Y;
}
__closure* MAKE_ADDER(int X)
{
__closure* c = malloc(sizeof(__closure));
c->enclosed = malloc(sizeof(__gentype1));
((__gentype1*) c->enclosed)->X = X;
c->enclosed->func = __genfunc1;
return c;
}
|
Here, the enclosed variable X is copied, but that won't do for closures that alter their enclosed variables. I could have them save a pointer instead, but that won't do if it's pointing to a stack variable and the closure is returned.
So basically, it just has to be a bit smart about things, if I want it to be as fast as hand-coded C. Here is a worst-case scenario (which should be rare):
| Code: |
(defun test (x)
(let ((c #'(lambda () (incf x))))
(c)
(print x)
c))
|
Here, X is captured by the closure, altered by the closure, used by 'test', then the closure is returned. The closure needs a pointer, but it can't point to the real stack variable, so 'test' has to malloc a new version of its argument and copy the value in before creating the closure.
About dynamic typing: I simply don't intend to allow it. Even CONS cells will be typed (the downside being that lists can only hold one type -- use structs for more complicated data). If I can't make the whole system pervasively typed, then I'll probably abandon the project and stick with CL.
Here's what a strongly-typed list of int's might look like:
| Code: |
union int_CELL
{
int_CONS* cons;
int atom;
};
struct int_CONS
{
int_CELL car, cdr;
int car_is_atom :1;
int cdr_is_atom :1;
};
|
Quoted lists should be easy, but symbols: I am totally clueless on this one. A string for every symbol? An enum of all symbols? When is the actual text of a symbol needed, if I am not supplying EVAL?
Ideally, a symbol is just an int, but I don't know if I can get away with that...
#29892 - sajiimori - Fri Nov 26, 2004 9:01 am
| Quote: |
| I think tail-recursion won't be very hard... |
My, how things have changed in almost a year! I had no idea what "tail call" really implied back then.
On syntax-versus-no-syntax, I've swung back to syntax. No-syntax is technically superior but humans need visual cues. After over a year with Lisp I still feel relief when returning to languages with mixed puncutation and fixity -- it makes things pop out.
Looks like we were using a weird definition of "continuation". Continuations are totally different from the result of a partial application (which is simply a closure) -- they allow you to backtrack during computation by taking a snapshot of a state and calling it like a function.
There is no debate about the speed of code produced by current Haskell and Lisp implementations. With CMUCL, Lisp is now a fast language. Perhaps Haskell could one day become fast, but the compiler technology isn't there yet.
So why am I digging up this old thread? Well, I'm learning Haskell and I've got a problem. ^_^ | Code: |
class Clip a where
-- Restrict a value into a min/max range
clip :: a -> a -> a -> a
{- class/instance/whatever to make clip work on Ord -} where
clip val min max
| val < min = min
| val > max = max
| otherwise = val |
Clip is a class rather than a plain function because I also want to clip vectors and such.
Any takers?