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?

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