Any significant program uses collections heavily, so most languages have several collection types - usually at least one sequence type and one dictionary type. Many languages have more, but library effort is limited, so every language omits some useful collections. As long as there are good alternatives, it's not a big problem.
Ruby doesn't have lists. RLisp borrows Ruby's data structures, so it doesn't have lists either. But it's a Lisp dialect! How can you have a Lisp without lists?
Pretty easily, it turns out. Despite their historical importance, lists don't have much to do with Lisp being Lisp. Their most important use is to represent S-expressions - but they aren't the only data structure that can do that. The important feature of S-expressions isn't that they read as lists - it's that they read as something simple and flexible and easy to work with. Vectors have all of these advantages, so RLisp programs are made of vectors instead of lists.
This is not traditional, but it's not a bad idea. Sure, cons and cdr are more expensive, and those are common operations on code, but performance of code manipulation is rarely a problem. And vectors are smaller than lists, which recovers some speed, and makes it cheaper to keep code around for debuggability. So I think other new Lisps should consider using vectors instead of lists.
I don't mean to suggest that lists aren't important. They are the functional sequence data structure, and every language that intends to support functional programming should have them. But RLisp is in its infancy, and it's forgivable if it doesn't have lists yet.
On the other hand, there's no excuse for its convention of writing close parentheses on their own lines. They look so lonely! More to the point, they waste space, separating the lines that have actual code. This is just as annoying in Lisp as it is in C, and there's no reason to do it in Lisp. Let indentation show program structure, and leave the parentheses at the ends of lines, regardless of whether they delimit vectors or lists.
Vectors (Arrays in Ruby terminology) in Ruby share storage space and only copy when they're modified, so RLisp cdr is still O(1), and algorithms which recursively iterate over a list Scheme-style don't suffer from performance problems, or at least they wouldn't if RLisp had proper tail recursion optimization.
ReplyDeletecons is of course O(n) and you cannot do much about it, so building vectors by recursive consing Scheme-style will be slow, and you're better off using high order functions like map or modifying the accumulator vector.
By the way I mostly agree with what you say about lonely parentheses looking bad, at least when it comes to expressions, and more recent RLisp code uses less of them.
ReplyDeleteBut I still think they make some sense when you're defining some sort of a "context", like (class ...) or (test-suite ...), and you can meaningfully add more stuff inside the context (like extra methods) without affecting the last item. Parentheses like that really don't belong with the last item of the context (like the method). It's different than cases when position of the last item is meaningful, like a return value.
I suppose this is a reminder that there's more than one way to do even something as simple as a vector. The transparent constant-time slicing is a tempting feature.
ReplyDeleteI wonder if it might not be better to just call the arrays arrays, and not offer list operations that don't have the expected performance characteristics. Ruby has plenty of collection operations, so who needs cons anyway? :)
I understand about the close parenthesis not belonging with the last item of a list - I just think that's a much smaller problem than wasting a whole line on one uninformative character. Automatic paren-matching makes adding items at the end of a list easy, but it's hard to recover wasted space. (The editor could hide redundant close-parentheses - is there already an emacs minor mode for that? - but there would need to be some indicator, to distinguish it from missing close-parens.)
In Scheme there is literally only one point where the language itself depends on the existence of lists, and that's variadic functions: the &rest is returned as a newly allocated list.
ReplyDeleteMy toy Scheme implementation will not even have lists as a first-order type: only doubles, vectors of doubles, and possibly fixnums and strings. Unfortunately, that means there are no variadic functions, only variadic macros. (It's designed to let you write flonum code in Scheme and then automatically translate those parts to C so as to avoid flonum boxing and unboxing overhead.)