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

How exactly would you implement arrays if they weren't a C++ built-in?

>>41
Pointer arithmetic. After all, array[index] is just *(array + index).

(I wonder how the bbcode gods will react to my array index?)

>>2
Treating arrays as flat memory might be wrong too. It's right for low-level languages like C, but what unless you're designing a low-level language, you might want to consider that an array may be not just a simple indexed buffer, but a more complex structure, for example it could containg a length to be used for bounds checking, a base item type (from which you could find out the size of the item), and so on. It's also questionable if you need built-in operators for pointer arithimethic by default. Some higher-level languages do provide "functions" or "operators" which work directly with the memory, and the compiler would efficiently inline such code, but if the language is high-level enough, you won't need to use pointers except in a few situations:
1)Implement some new data structures from scatch.
Why? If the language was well-thought, you wouldn't have to use those low-level operators except to implement such code.
2) The compiler is rather poor and you want to optimize certain code for more speed.
This may be useful in the case the compiler is lacking or you have some clever optimizations, but most of the code won't need it.
3) You're juggling some foreign data and need to be able to access it using a precise memory layout.
It's possible to make a FFI which abstracts such pointer access, so you might not need to touch the data directly yourself.
4) You're doing something platform-specific.

It's up to you to decide what kind of language you want to make. If you want to make a low-level language like C, then you could give pointer arithimethic their own special syntax as it occurs frequently enough. If you're doinga high-level language, just consider providing some functions/operators which can do pointer arithimethic, and "calls" to which the compiler can optimize very well, however there is no need to add special syntax for it, unless the language is inadequate.

You should take my opinion with a grain of salt, as of the past year, I've become to believe that syntax is very unimportant, and semtantics are truly what matters. S-Expressions or equivlents is just enough for me. Some people claim that they need visual cues to better understand code, but I know that I don't need more visual cues than just indentation and easily readable function names.

>>39,29
Visible in source code.
Ah, I misunderstood; I thought you meant performance-wise. In this case, the vast majority of high-level languages (basically all those that support operator overloading) fit this criteria, making it a mostly meaningless observation. C++ is nothing special in this regard; I'm not sure why you think this is 'getting close to C++'.

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?
Yes. Lots of platforms still claim C++ support without STL. Even though STL is part of the specification, people still think it's optional and think that having C libraries with a C++ compiler is 'good enough' (Symbian C++ is a perfect example).

AFAIK Common Lisp used to have similar problems, with certain compilers/interpreters claiming compliance without supporting e.g. hash maps. Implementors just don't seem to care whether it's in the spec; 'libraries are optional' seems to be the overriding mentality.

Conversely, there are a number of Python interpreters available; how many do you see claiming compliance without supporting dict?

>>43
It's right for low-level languages like C, but what unless you're designing a low-level language, you might want to consider that an array may be not just a simple indexed buffer, but a more complex structure
In fact C is the only widely used language I can think of where arrays are raw indexed buffers. Even Fortran arrays have length information.

>>44
AFAIK Common Lisp used to have similar problems, with certain compilers/interpreters claiming compliance without supporting e.g. hash maps. Implementors just don't seem to care whether it's in the spec; 'libraries are optional' seems to be the overriding mentality.
Could you please elaborate more on that?

>>44
C++ is nothing special in this regard; I'm not sure why you think this is 'getting close to C++'.
Oh, that was just a reference to the C++ hatred on /prog/.

Yes. Lots of platforms still claim C++ support without STL. Even though STL is part of the specification, people still think it's optional and think that having C libraries with a C++ compiler is 'good enough' (Symbian C++ is a perfect example).
Really? Although this is of course partially justified (on such platforms it is probably much easier to copy-paste in an implementation of the standard library than it would be to add a compiler), my answer to >>1 would then become "work out the standard library you want, then remove the name 'standard library' and call it all core language components". That, or we should just ignore Symbian et al.

>>44
AFAIK Common Lisp used to have similar problems, with certain compilers/interpreters claiming compliance without supporting e.g. hash maps. Implementors just don't seem to care whether it's in the spec; 'libraries are optional' seems to be the overriding mentality.

I thought they had a similar situation pre-CL, which is why CL was made. I haven't heard of anything which is so non-compliant. What people whine about today are things like missing a MOP feature here and there, inconsistent threading APIs, or FFIs. Besides the MOP, those things are not standarized, which is why people have developed compatiblity layers/libraries to act as a defacto standard for those wanting such features.

s/standarized/standardized

>>44
>>48
The Lisp situation was somewhat different. Before Common Lisp there were quite a few Lisp dialects that could be considered major: while they didn't behave identically, this wasn't a matter of not conforming to the standard since they didn't claim to be the same language—there was no standard they should have been conforming to. It was similar to the Python or Perl situation today, or to Clojure.

When the Common Lisp standard was created, vendors modified their Lisps into Common Lisps. There was definitely a period of non-compliance, but I would say that it was due to the fact that it takes time to make changes, not to disinterest in meeting the spec. It made no sense for vendor or customer to wait for every piece of CL to be in place before releasing, which would have meant languishing legacy dialects and a long wait for any significant upgrades or fixes that would come with the CL. Dialects with the manpower to do so met the standard long ago, and smaller ones when they could.

>>50
>>44,48

Optimized my quotes.

From one perspective, the only "high level" data structure you need is a ordered dictionary/associative array/hash, and the rest can be trivially (if sometimes inefficiently) made out of it. From another perspective, you don't need any data structures at all as long as you provide constructs for creating them.

Ultimately, it depends on what sort of language you're trying to make.

Interpreted languages, where speed is secondary, have only high-level constructs, with resizable arrays/dynamic arrays/vectors/array lists and unordered dictionaries/associative array/hash being the most important data structures out of the box.  Mid-level languages (C#, Java, C++) tend to have those plus dedicated linked list, array, and hashtable implementations as part of big standard libraries containing everything ever. Lower level languages will basically expect you to implement everything (see C, which doesn't even have "proper" arrays, just convenient syntax for allocating blocks of memory on the stack).

>>50
Seeing "Common Lisp" and "vendors" in the same gist makes me shit brix laughing.

>>53
uh, why?

>>50
Which explains why Common Lisp is so schizophrenic - it's a whole bunch of divergent languages all thrown into one single Design By Committee process. The end result isn't that bad, but it's about as coherent as C++, which is hardly a compliment.

Worst of all, the market for Lisp started dying afterwards so Common Lisp has remained largely static since, and the entire Lisp family has struggled to get out of the CL shadow.

>>55
What exactly do you think is wrong with CL?

>>55
Not really. The committee did a good job, and it's far better designed than C++. Much clearer, much more usable.

Worst of all, the market for Lisp started dying afterwards so Common Lisp has remained largely static since, and the entire Lisp family has struggled to get out of the CL shadow.
You want to support that assertion? Reasons that it had more to do with that than with being tied to an unfeasible and dying platform, being caught in the AI winter, and being the subject of derision from “cleanliness”-obsessed Schemers who, let's face it, are out of their minds, would be nice.

being the subject of derision from “cleanliness”-obsessed Schemers who, let's face it, are out of their minds
Yep, guilty as charged

No data structures, OP, only words of memory. Anything built-in is ugly, even if its usage is strictly implicit (e.g. a stack for local variables and return addresses).

Yes, I do enjoy programming in assembly.

>>59
Enjoy having to translate your thoughts so that the machine can understand it, I'll be here toggling my switches like a real programmer.

>>60
Same language, different editor.

>>61
No, that was machine code. No assembly required.

>>62
Machine code is assembly, though.
Much like 01000001 and A represent the same character, 10010000 and nop represent the same instruction. All an assembler does is translate from one form to the other.

Unless we're talking about those disgusting macro assemblers.

>>63
Unless we're talking about those disgusting macro assemblers.
Like, C programming language?

>>63
All an assembler does is translate from one form to the other.
Perhaps more importantly, it will also resolve addresses for you, which arguably makes it a significantly different language.

>>63
who would believe that?

>>65
this

>>65
I don't see how this makes that great of a difference; whether you're saying call fibs or call 0x1234, you mean the exact same thing. The structure of the code is exactly the same, it's just the names that have changed. Comparing assembly to machine code is like comparing two C programs that execute in the exact same way, but where the variables in one of them are just named v1, v2, v3, and so on.

>>68
I don't see how this makes that great of a difference;
At the very least, it means I can modify the code between points X and Y in the following code without changing line Z:

Z: jmp Y
X: spam
   spam
   spam
Y: eggs
Therefore, assembly provides a significant abstraction layer over plain machine code.

whether you're saying call fibs or call 0x1234, you mean the exact same thing.
Sure, and when I say fibs(); I still mean the same thing. That doesn't make C and assembly equivalent.

The structure of the code is exactly the same, it's just the names that have changed.
In the same way that the structures of a C program and a pascal program are the same, I guess.

Comparing assembly to machine code is like comparing two C programs that execute in the exact same way, but where the variables in one of them are just named v1, v2, v3, and so on.
I find it more like comparing C code to pascal code that execute in the exact same way, but where "{" is called "begin" and so on.

>>69
You can do that, but you'll have to recalculate the offsets each time. Some people also tend to make larger nop buffers for easier relocation, and there's assemblers out there that don't have labels, you just assemble at fixed locations in memory (this is especially true of various debuggers which let you change code as the program is running, as well as some rudimentary hex editors which have an assembler for some platform). The minimal assembler just needs an offset and instruction mnemonic, given those 2 things, it can calculate what the machine code for that instruction will be and assemble it at a specific address. There is no requirement for an assembler to have support for labels. Assembly language is no more than one of many possible human-readable representations for the hardcoded opcodes of a CPU platform. They are for all purposes equivalent as long as a translation between instruction mnemonic and bytecode is clearly defined.

>>70
There is no requirement for an assembler to have support for labels.
Right, and there's no requirement for an assembler to have support for mnemonics either. If it doesn't support either, we call this assembler "cp".

Assembly language is no more than one of many possible human-readable representations for the hardcoded opcodes of a CPU platform.
By that logic, so is C if we restrict it to a single platform. (inb4 "portable assembler" - the same thing can be said about pascal.)

>>71
Right, and there's no requirement for an assembler to have support for mnemonics either.

Most assemblers I've seen didn't have support for labels. Only full-fledged assemblers have support for them. (There are many assembler libraries, assemblers+disassemblers as part of debuggers, hex editors and disassemblers with integrated assemblers which don't have support for "labels". Labels are just an abstraction. A CPU's manual defines mnemonics and their translations, not the specific notation that can be used by some random full-fledged assembler. Even if such rudimentary assemblers shouldn't be used for real coding work, I've written functions to be used in them in an ad-hoc manner and re-adjusted offsets post-assembly, which of course worked just fine).

If it doesn't support either, we call this assembler "cp".
That depends on how the opcodes are built. Some architectures have fairly fine-grained opcodes, encoded at the bit level, and cp might not be enough as it works with bytes, and besides, rudimentary assemblers are quite useful to be used as libraries. If you were to just enter the opcodes manually, you'll end up having to implement the assembler yourself, at which point you'll realize that adding support for labels is just a very simple, tiny piece of functionality that you must add compared to the rest of the program.

C isn't exactly portable assembler, even if I sometimes like to call it that. Of those full-fledged assemblers, macro assemblers are the most "powerful" ones, but they still can't reach C, as they can't do their own register allocation like C compilers can. At the same time, you may be able to predict how a C compiler would compile some piece of code if you knew the compiler and the flags used, but it's possible to implement a C compiler which is standards compliant, but generates code with very different properties than you might expect (with regards to things like the 'stack', or 'register usage', which can't be controlled by the user in portable ways, but some implementations do provide unportable ways).

Are you guys still arguing about whether or not assembly and machine code are "the same language"? Who gives a fuck, it's just semantics.

I haven't seen an argument this stupid since that guy tried to tell me "const" wasn't short for "constant".

>>73
It isn't. It's short for love. （　♥‿♥）

Are you GAY?
Are you a NIGGER?
Are you a GAY NIGGER?

If you answered "Yes" to all of the above questions, then GNAA (GAY NIGGER ASSOCIATION OF AMERICA) might be exactly what you've been looking for!

<-- check em dubz