Containers library

One question for you /prog/!

Suppose you have a brand new language, which doesn't have any library yet. Which kind of basic containers / data structure would you expect?

Vector<<><<>$$%><<>>

Vectors and Cons Cells
/thread

>>3
What is a "Cons Cell"?

XML

Rainbow Tables

>>4
E.g. x:xs of haskell.

>>3
Cons Cells are more a built-in feature than a library.

>>7
Oh, he meant library features? I thought he meant before library.

STAX

>>1
I'd prefer the Sepples approach: You should be able to implement anything in the standard library yourself if you felt so inclined. If there's one thing Sepples did right, it was the roughly equal support (improved to pretty much equal in Sepplesox) for user-defined stuff and intrinsic library stuff.

That way, if a certain implementation rubs you the wrong way, you can just as easily create your own roll - the language should support both just as well. To me, that's more important than having a ton of offerings for the standard library.

As far as things I'd expect to be in a standard library for a general-purpose language, I'd expect things used in almost every project: Easy utilities for strings, time zones, various data structures such as stack and queue (though this is by no means an exhaustive list of structures), various sorting utilities, Internet-related tasks (synchronous connection and data handling, at the very least), threading facilities. Things like that.

Cons cells. In the large scope of things you can always fake vectors.

I'd prefer the Sepples approach
IHBT :(

>>10
You seem to have confused Sepples with Lisp. Worry, this is very uncommon.

Arrays and hash tables.

>>14
Why do you need a new language? PHP does that.

>>11
Oh yeah, a nice good vector with o(n) access. Retard.

>>16
You could arrange them as trees to get O(log n), which is still not constant, but better than O(n)

ARRANGE MY ANUS

>>1
Dict and List are really the only ones I would expect. This is what Python does. Dict is not a sufficient substitute for List, because you want to be able to pop and insert elements into it without having to change all the indices yourself.

The underlying implementation of Dict is not really important, but I would make it optionally order-preserving (so the keys stay in insertion order, or you can sort it if you want).

As for Lists, I'd make the underlying implementation a simple Deque. If you want to do Python's tuple bullshit, don't expose it to the users of your language; make it a fully transparent optimization. You can do other optimizations if the array is huge, like changing it into a rope.

>>10
I really don't care about the underlying implementation or about re-implementing it myself; if I was worried about that sort of thing, I'd be using a lower-level language.

>>19
Go write an ANSI C compiler, kid.

>>20
I will, along with my job

>>1
None, because it's a brand new language without any library yet.

>>22
I don't think that's what he meant. Most languages (sepples being the exception) provide certain data structures as built-ins, not part of any library. e.g. arrays in C/Java, linked lists in Lisp, maps/hashtables/dicts in most high-level scripting languages, etc.

all you need are ints and arrays then you can build what ever you want on top of em

all you need are cars and cdrs then you can build what ever you want on top of em

>>23
Just provide what's used to implement the language. I'm not sure if you can call linked lists as built-in in Lisp: cons cells are provided because they're how EVAL and macros work, but you could reimplement cons cells or build them in other ways and the implementation will still work. Defining the line between library and language is a hard thing as in some languages it's possible to implement libraries which fit right in like they were built-ins, and it's possible to reimplement built-ins from scratch yourself. The CL standard provides a type/class system, arrays(of different kinds, from which you could technically build anything, such as structures, cons cells, classes, ...), cons cells(from which lists, alists, sets, graphs, binary trees, ... can be built), structures (whose internal representation may vary a lot - it can be built as anything, but most often it's represented internally as a tagged piece of memory and a compiler can inline access to the members), classes/objects(CLOS/MOP - from which you can build anything, again), symbols(which can be built from anything, again, they could be thought of as a structure with a few fields), packages(a named collection of symbols for providing namespaces), numbers(from efficient fixnums to bignums to rationals to complex numbers, floats, ...), characters, strings(simple arrays of characters), sequences (a type encompassing arrays, lists, and some implementations may let you add your own types - functions which work on sequences work on either concrete type of data), hash tables(which tend to be implemented as structures), functions(code objects, may be closures, lambdas, compiled or interpreted...), filenames/files, streams, conditions and so on ). What I'm getting at is that the language may offer many features, but given a few basic things like a tagged type system, with at least integers ,arrays and maybe structures(however they could be built using arrays) you can build all kinds of types and they could look and behave like they were there to begin with. If types and functions/interfaces are present in the language definition, it's probably right to call them part of the language, even though they're actually library. In the case of Lisp, you only need about 10% of the language to implement the remaining 90%, and it would appear as these features were always there.

>>26
I'm not sure if you can call linked lists as built-in in Lisp: cons cells are provided because they're how EVAL and macros work, but you could reimplement cons cells or build them in other ways and the implementation will still work.
Yes, and you could re-implement arrays in C, but you wouldn't be able to use the same syntax. Lisp does give you special syntax for its implementation of linked list, above and beyond cons cells. For instance quoting obviously builds linked lists for you.

I didn't bother reading the rest of your post. Consider using paragraphs.

>>27
Lisp lets you change the syntax as you please. The only syntax you get with cons cells are (car . cdr), quote works with it and backquote. All 3 can be reimplemented portably if you wish so. Some people actually reimplement backquote (just a few pages of code) because they want to be able to use some features portably(quasi-quoting, or making sure fresh lists are created by backquote are frequent reasons for doing this).

If the user is free to create his own syntax, own "special operators", functions, macros, "types", what else is there left?

>>27
(>>21 here)
Since I believe that every real language needs operator overloading, I don't care too much about which containers are built-in, since there shouldn't be a noticeable difference between built-in and library data structures. Even the array is optional if you have pointers (on which you can do arithmetic) available.

Yes, I'm realizing I'm getting quite close to C++ here (which doesn't mean that C++'s operator overloading is particularly good, but at least it has some form).

>>27
Paragraphs? He should start off by learning about sentences, holy shit. More than half that post is one big fucking run-on.

>>29
Since I believe that every real language needs operator overloading,
BWAHAHAHAHAHA

>>30
What's the matter, can't handle a bit of nesting?

>>29
There can be a big difference, overloading or not. Take clojure's hash maps. You don't have to do (make-hash (make-hash-pair "abc" 12) (make-hash-pair "dfg" 23)) etc.; since it's built-in you can use something like {"abc" 12, "dfg" 23}.

>>32
If the language supports reader macros ( CL has them portably ) or some other way of extending syntax, you can just add 2 macro characters for { and }, and have it expand to that upon READ. Not only that, but it would be fairly trivial to implement(less than half a page of code). Even with such read-time features, if {} don't come built in, the users of the language may shy away from wasting precious macro characters (such as {}) and just use the long form (which doesn't look tedious to write at all to me - maybe some elisp script could even speed it up).

>>32
To show how easy it is to implement this, I just quickly hacked up an implementation to do what you proposed:
(defun open-brace-reader (stream char)
  (declare (ignore char))
  (labels ((read-pair ()            
             (let ((key #1=(read stream t nil t))
                   (value #1#))
               `(make-hash-pair ,key ,value))))
    `(make-hash
      ,@(loop
           do (loop while (char= (peek-char nil stream) #\ ) do (read-char stream))
           if (char= (peek-char nil stream) #\,) do (read-char stream)
           else if (char= (peek-char nil stream) #\}) do (progn (read-char stream) (return pairs))
           do (peek-char nil stream)
           collect (read-pair) into pairs))))

(defun close-brace-reader (stream char)
  (declare (ignore char stream))
  (error "unmatched close brace"))

;;; Test:
;(with-input-from-string (i "\"abc\" 12 ,\"dfg\" 23 }")
;  (open-brace-reader i #\{)) => (MAKE-HASH (MAKE-HASH-PAIR "abc" 12) (MAKE-HASH-PAIR "dfg" 23))

;;; There is no make-hash/make-hash-pair in CL, and I should have written the
;;; reader function to use the proper hashtable functions, however, in this case
;;; I'll just reimplement them through the standard hashtable functions:

(defun make-hash-pair (key value) (list key value))

(defun make-hash (&rest pairs)
  (let ((ht (make-hash-table :test #'equal)))
    (dolist (pair pairs ht)
      (destructuring-bind (key value) pair
          (setf (gethash key ht) value)))))

;;; This implementation isn't very efficient. One could change the call to make-hash
;;; to use multiple-value-call and make-hash-pair to use values for some performance improvements

;;; Test:
;CL-USER> (MAKE-HASH (MAKE-HASH-PAIR "abc" 12) (MAKE-HASH-PAIR "dfg" 23))
;#<HASH-TABLE :TEST EQUAL :COUNT 2 {24A2B2A9}>
;CL-USER> (maphash #'(lambda (key value) (format t "key: ~s, value: ~s~&" key value)) *)
;key: "abc", value: 12
;key: "dfg", value: 23


;;; Now let's install the new syntax (in a real-world scenario, you'd want to use one of those
;;; wonderful readtable managers, as you might want to define per-file syntaxes),
;;; but this is enough for simple toys like this:

(set-macro-character #\{ #'open-brace-reader)
(set-macro-character #\} #'close-brace-reader)

;;; Test:
;CL-USER> (maphash #'(lambda (key value) (format t "key: ~S, value: ~S~&" key value)) {"abc" 12  , "dfg" 23, #\Space 'lolwut, :is-this-worth-it 'not-really! })
;key: "abc", value: 12
;key: "dfg", value: 23
;key: #\ , value: LOLWUT
;key: :IS-THIS-WORTH-IT, value: NOT-REALLY!

>>33-34
I know. I program in CL as well. Nice job actually doing it though.

My point to >>29 is that it's possible to make nice built-in data structures which could not be implemented with operator overloading alone. Reader macros aren't mere operator overloading.

Therefore >>29 has obviously not read his SICP today and should crawl back to C++, along with his job.

>>29
I don't care too much about which containers are built-in, since there shouldn't be a noticeable difference between built-in and library data structures.
Why? Explain yourself.

What would you consider 'noticeable'? For simple GUI applications, there isn't a noticeable difference between Python apps and C apps. Conversely for high performance apps, there can be a noticeable difference between C data structures and the equivalent structures with critical parts hand-written in assembly.

Almost no languages actually fit your criteria, since I can roll my own data structures in C and add an interface to it in the language. Lots of library extensions to Python do this, e.g. the array module, and you can sacrifice type-safety and bounds-checking for even more speed. Sepples only fits your criteria because it has no built-in data structures. This is not a good thing; the resulting library specifications took decades to become complete, portable, bug-free, and reasonably fast. (I still don't understand why the fuck Stroustrup didn't just write the damn things himself and MIT-license them; this is CS101 ffs.)

Lua tables come as close to a one-size-fits-all structure as I can think of.

>>37
What, those one-indexed pieces of shit? If they were one of my children, I'd disown them on the spot!

>>35
True enough; on second thought, I actually meant syntax overloading, of which operator overloading is a large, but far from sufficient, part.

>Therefore >>29 has obviously not read his SICP today and should crawl back to C++, along with his job.
I have actually (well, not today), and I do love LISP for its ability to do all that, much like I love haskell for project euler exercises. I still prefer C++ for getting real work done though, even though it's far from perfect.

>>36
>What would you consider 'noticeable'?
Visible in source code. BigInteger x = y.copy(); x.add(z); is noticeably different from int x = y; x += z;, whereas BigInteger x = y; x += z; isn't. If your language supports the latter style, I couldn't care less whether BigInteger is part of the language of part of the library - the only difference being that I may need to #include <bigint.h>.

>Almost no languages actually fit your criteria, since I can roll my own data structures in C and add an interface to it in the language.
And how does this not fit my criteria, except for the difference in syntax?

>Sepples only fits your criteria because it has no built-in data structures. This is not a good thing; the resulting library specifications took decades to become complete, portable, bug-free, and reasonably fast.
And do you think they would be complete, portable, bug-free, and reasonably fast any sooner if std::map was part of the language instead of the standard library?

My point is pretty much that in a proper language - which C++ manages reasonably well (that is, better than most imperative alternatives) in this regard - I, as a programmer, should hardly be able to see what exactly is in the language and what is in the standard library, except maybe having to include some header file or the like.

>>39
I have actually (well, not today), and I do love LISP
I do love LISP
LISP
6.5/10