4 ms·

Why not just stop at the point that a Pair is just two pointers and a List is a bunch of nested Pairs, without any classes, deftypes or monads?) Btw, the class

Why not just stop at the point that a Pair is just two pointers and a List is a bunch of nested Pairs, without any classes, deftypes or monads?) Btw, the classic trick from SICP lectures, where a Pair was implemented as a closure (a procedure) that accepts messages (to illustrate code-is-data principle) is much more interesting abstraction than this overengineered OO stuff.)

dschiptsov 13y ago
Now I have a full keyboard instead of that clumsy phone.) The very idea "to implement a List" in what is supposed to be called a Lisp is.. well, I do respect the amount of work that has been done, but. Such kind of confusion, it seems, comes from a wrong perspective of what a Lisp is. Let's look first at what it is not. It is not some "modern OO" language with parenthesized prefix notation, it could be so boring. Second, a List is not some "data structure in Lisp", it is the most important, non-separable fundamental feature of the language. Without "native conses" a Lisp is nonsense. The explanations is going to grow lengthy, but it worth a try. A Lisp is a set of layered DSLs and ADTs. Its "miracle" in what it is small and good-enough, in accordance with "Less is more" maxima. There is no fucking "Class Node" in what a List is. It is just (cons 1 (cons 2 (cons 3 '()))) or 1:2:3:[] if you wish. The big ideas is to separate clearly the use from the implementation, which is called an Abstraction Barrier. A complete definition of the basic building block - a cons cell, or the Pair ADT is cons, car, cdr, pair? and nil while a List is just one more "constructor" - list. This is minimal and it is good-enough. It is so "good" that it "created" another small miracle - cadr/cddr notation, which is just an accidental piece of beauty created by a human mind (like a Lisp itself). Only complete tasteless person could abandon this in order to use dull and mediocre first/rest or any other names for selectors that doesn't "chain" and reflect the notion that almost everything could be made out of conses. The problem is that we have way too many of those who cannot grasp the beauty of what a cadr or cddr is. Implementation in a language's runtime is quite another topic. There we probably should have a notion of a pool-based allocation (in order to not call malloc for each cons) and locality (to properly implement persistence) etc. but these implementation specific things must never leak int "high-level" use. Again, there is no fucking Class Node. Speaking of Lisp apart form Lists is like speaking of water apart from the waves. Water has waves, Lisp has Lists in its own nature. Giving this nature of Lists we could have a general mapper procedure, or map. The idea of a Functor from Math (or these control abstractions from Haskell) has nothing to do with it. It is just the recursive nature of List's structure allows us to define recursive processes. Even trees not necessarily must have any Class Node. Here is a classic example: (define make-tree cons) (define datum car) (define children cdr) (define (leaf? n) (null? (children n))) (define (tree-map fn tree) (make-tree (fn (datum tree)) (map (lambda (ts) (tree-map fn ts)) (children tree)))) There is no "Single-Linked List Data Structure in Lisp" because there is no Lisp without conses. Last but not least. This very site is build in a dialect of Lisp which never tries to redefine what a List is. More about Lisps - http://karma-engineering.com/lab/wiki/Bootstraping http://karma-engineering.com/lab/wiki/Bootstraping More about piling up useless abstractions - http://karma-engineering.com/lab/wiki/Monads http://karma-engineering.com/lab/wiki/Monads

dschiptsov 13y ago

Now I have a full keyboard instead of that clumsy phone.) The very idea "to implement a List" in what is supposed to be called a Lisp is.. well, I do respect the amount of work that has been done, but. Such kind of confusion, it seems, comes from a wrong perspective of what a Lisp is. Let's look first at what it is not. It is not some "modern OO" language with parenthesized prefix notation, it could be so boring. Second, a List is not some "data structure in Lisp", it is the most important, non-separable fundamental feature of the language. Without "native conses" a Lisp is nonsense. The explanations is going to grow lengthy, but it worth a try. A Lisp is a set of layered DSLs and ADTs. Its "miracle" in what it is small and good-enough, in accordance with "Less is more" maxima. There is no fucking "Class Node" in what a List is. It is just (cons 1 (cons 2 (cons 3 '()))) or 1:2:3:[] if you wish. The big ideas is to separate clearly the use from the implementation, which is called an Abstraction Barrier. A complete definition of the basic building block - a cons cell, or the Pair ADT is cons, car, cdr, pair? and nil while a List is just one more "constructor" - list. This is minimal and it is good-enough. It is so "good" that it "created" another small miracle - cadr/cddr notation, which is just an accidental piece of beauty created by a human mind (like a Lisp itself). Only complete tasteless person could abandon this in order to use dull and mediocre first/rest or any other names for selectors that doesn't "chain" and reflect the notion that almost everything could be made out of conses. The problem is that we have way too many of those who cannot grasp the beauty of what a cadr or cddr is. Implementation in a language's runtime is quite another topic. There we probably should have a notion of a pool-based allocation (in order to not call malloc for each cons) and locality (to properly implement persistence) etc. but these implementation specific things must never leak int "high-level" use. Again, there is no fucking Class Node. Speaking of Lisp apart form Lists is like speaking of water apart from the waves. Water has waves, Lisp has Lists in its own nature. Giving this nature of Lists we could have a general mapper procedure, or map. The idea of a Functor from Math (or these control abstractions from Haskell) has nothing to do with it. It is just the recursive nature of List's structure allows us to define recursive processes. Even trees not necessarily must have any Class Node. Here is a classic example: (define make-tree cons) (define datum car) (define children cdr) (define (leaf? n) (null? (children n))) (define (tree-map fn tree) (make-tree (fn (datum tree)) (map (lambda (ts) (tree-map fn ts)) (children tree)))) There is no "Single-Linked List Data Structure in Lisp" because there is no Lisp without conses. Last but not least. This very site is build in a dialect of Lisp which never tries to redefine what a List is. More about Lisps - http://karma-engineering.com/lab/wiki/Bootstraping http://karma-engineering.com/lab/wiki/Bootstraping More about piling up useless abstractions - http://karma-engineering.com/lab/wiki/Monads http://karma-engineering.com/lab/wiki/Monads