Wikimore

some languages

I repeat my statement fromt the types artile: Here too, there are a lot of "some languages do this" and "most languages do that" statement which I found rather dry and theoretical. Again I have added some exampels for "this" and "that" and at least I have the feeling that the text is now more practical and lively.

Only: I have no example for start index [1] can anybody help me out here?

--Krischik 10:41, 26 Nov 2004 (UTC)

Structure of chapter and the book

Hi Krischik: I've noticed the change from integer indexes to any type of indexes. While it's correct that "arrays" can have different index types in high-level languages, I think the point here is to first begin with the absolute lowest-levels first.

In particular, I think the most elementary concepts are the node (e.g. the pair in Lisp, and a two element struct in C) and the integer indexed array. The concept of the node is really the idea of pointers with elements attached to them, and the concept of the array is a simple block of memory you access via offsets. The story I'd like to see this book tell is how, from these two ideas, you can build all other data structures. Thus, when we cover ballanced binary trees, we can mention that's how C++ implements associative arrays.

As for languages, I propose we stick to the pseudo code language and only in the node an array chapters do we show how the code would translate to equivalent C, Java, Scheme, and Python code. (Perhaps another chapter on structs could be covered, showing how to get the equivalent in Scheme.) The abstract ideas should be presented first, and then made concrete by presenting the different languages. (Note: asides and footnotes could still mention other languages, but I would want to resrict that only to widely used or historically important languages.)

So, the idea is that most of the book would be language independent except for the first two or three chapters, and then you'll see everything built up from what was presented before. This includes self-resizing arrays, associative arrays, hashtables, et cetera...

I'm eager to make the book structure changes as discussed on the main talk page as well, and I would like to know what you think.

more abstract

I do aggree with you on most points. Only I see the "low level" and "language independent" more abstract: The array consist of an index which is used to access elements.

Only actual languages restrict the kind of types which can be used as index type or element type - depending on the actual balance between flexibilty, savety and speed which is needed. Like most compiling languages need a discreed type as index type and an definite type as element type so that all elements kann be layed in one large area of memory.

As for languages: I am in favor of broadening the readers mind. Show that here is a live beyond C (no bound checks only int as index type) and Java (only primitives and pointers as element type, only int as index type).

--Krischik 11:07, 27 Dec 2004 (UTC)

beyond C and Java

To me, the life beyond C and Java is Scheme! It's probably the most important language that is radically different from the current fads. While I'd love to use, say, Smalltalk, instead of Python, that could lead the book to lose it's razor sharp focus. We can completely cover other array types, but I think we should wait until we've shown the user how to build them, first.

That is, we tell the story of the node and the array as if they "came from the heavens" as virtually all languages provide support for them. We then can discuss the concrete instantiations of these two items in the different langauges, and from then on, nothing will be from the heavens, but built-up from these simple concepts.

(So as not to get too much of a distracted reading style, we could include links at the end of chapters where we'd like to elaborate more, either links to the Ada programming book, or the wikipedia, or special end-note pages. Because this is a tutorial hitting only the main points, we should keep the side notes and distractions down. Otherwise, I'd probably go into a full-blown explaination of data structures in the Lambda Calculus, which is more suitable for the programming languages book.) MShonle 18:41, 27 Dec 2004 (UTC)

Maybe without implementation languages

Choosing the right implementation languages is diffcult indeed. Especialy here because the mainstream langugages have particulary bad array implementations (did you have a little peek at the Ada implementation). Maybe we should just explain the various features of arrays, give an overview which language implements which feature and the just link to Programming:C and Programming:Ada and so on for further reading.

The overview could be layed out as a table, then we can add as many languages as we like without causing distraction and no language advocate would feel left behind.

Of corse, you would have to first write Programming:Scheme:arrays ;-).

I don't think the Ada example is bad in this section (as long as it compiles). I think SMALL examples add some interest for more experienced readers. And small being 15 or fewer lines. Christopher.Reilly (discuss • contribs) 11:36, 17 June 2015 (UTC)

the data structure concepts are our foremost

Perhaps we differ on what we think this chapter should cover. I do not want to make an encyclopedic treatise on all of the usages of the word "array" and how this programming language or that programming language implements them differently.

To me, the purpose of the array chapter is to cover the concept of a single buffer of memory that is a table of homogenous entries, indexed with integer offsets. This is the most fundamental building block, next to the concept of the node. We need to cover the fundamentals well before we can speak of the even more advanced data-structures. (We can mention that some languages do bounds checks and others don't; and we can even mention slicing: but as an operation, not a programming language feature.)

I'm not opposed to the idea of linking to different articles, but that can lead to a very poor reading experience. I'd rather that links go only one level deep (as in the Computer science:Algorithms book), so that a student could print out each chapter and be sure they have everything they need (printing is still very common in the States).

I would like to cover that set of languages (C, Scheme, Java, and Python) in this chapter and the Node chapter in order to show how the pseudo-code language can be translated. Also, a secondary purpose is to convince the reader that isues like implementation language is not very signifigant when discussing data structures. If we present the concepts well enough they will see the forest instead of the trees.

-- MShonle 15:29, 28 Dec 2004 (UTC)

Sticking with the traditional integer-indexed (from 0) notion of array as a address-accessible contiguous block of storage is hugely important if students will be able to use this section as part of their education about data structures (and algorithms). Languages that allow other data types as array indexes are (in my experience, at least) really implementing a dictionary/hash table lookup, putting a somewhat complicated layer of abstraction underneath the familiar syntax. (I should look into the implementation details some day, but I strongly suspect that PHP does not have classic arrays at all, just dictionaries.)

Including relevant information about the special "array" tricks and variations of real-life programming languages readers will be using is important, but I believe it is confusing to place those in the main body of what should properly be a description of the fundamental/classic array.

As an instructor, I would prefer to see a clear description of a traditional array first, with the implementation details for specific popular languages moved to a second section. Having encountered this discussion about a decade later, perhaps that will be my job ;-)

--Davidhbrown (discuss • contribs) 13:29, 16 July 2014 (UTC)

set of languages

If you fix a set of languages then there will allways be advocates for other languages - like me - knocking on your door. For example: as soon as you need any of the following in C "*", "&", malloc (), free () I show you that Ada can do without ;-) .

Yes, Implementation language are not very signifigant when discussing data structures but they are when it comes down to actualy implementing them. So again: maybe we should live without and use only pseudo-code. Computer science:Algorithms certanly does - the Appendix is empty. Actualy there pseudo-code looks quite nice and understandable without a syntax guide. I am all in favor of using that and there way of using arrays (fixed bound array a [1..n] and variable bounds array a).

BTW: I know 3 of the suggested languages and I have 15 years experience in programming C and C++. I don't want the reader to belive that the criple C offers as an array is realy it.

--Krischik 17:51, 28 Dec 2004 (UTC)

OK, how about we this: We'll use only the pseduo-code as in the Algorithms book, and only for the Array and Node chapters will be include "deeper" links to cover the fundamental data structures in other languages (including Ada, if you'd like). We can speak of the "get-element" and "set-element" operations as being fundamental, and that the subscript "[]" notation is just a short-hand. (Which reminds me, perhaps getting the length of the array should be considered an operation.)

The reader won't be lead to believe that the too basic C arrays are it (i.e., you can't resize, and no bounds checks), because the rest of the book will fully cover the better data-structures.

BTW, now that you're active, take a look at my section proposal. If you're OK with it, I'll start making the changes, including chapter navigation and a "Why a Wikibook on Data Structures" message as in the Algorithms book. MShonle 18:41, 28 Dec 2004 (UTC)

well do go ahead.

pseduo-code

You where asking about an operation for the lenght of an array. I have a proposal based on Ada's operatations on arrays:

'First: index of first element
'Last: index on last element
'Lenght: shorthand for ('Last - 'First + 1)
'Range: shorthand for ['First .. 'Last]

For the pseduo-code we might drop the esoteric tic ' and use the well known dot . instead.

Example:

A : array [1 .. 10]

for I := A.First to A.Last:

repeat

or if you like functional syntax more then object.operation syntax:

A : array [1 .. 10]

for I := First (A) to Last (A):

repeat

Actualy: functional syntax reads more like natural english.

As a side note, the Ada equivalent is

for I in A'Range loop;

end loop;

But I don't think this is very suitable for pseduo-code and therefore we could drop the 'Range operation alltogether.

Saying all that, Algorithms use a ISO-Pascal like syntax:

array a[1..n]

Which works perfectly well as well.

another side note: actualy in ISO-Pascal it would be something like this:

procedure X (A : array [n .. m : integer] of character)

I prefer the functional syntax because that will be the only choice we have for, say, queues and hashtables. I.e., we can have lookup() and insert() methods, so if our most fundamental data-structures are similar (except for using the subscript operator) then things would seem to mesh better.

I do like saying simply "array a" and "value" (with no type) when the types of the elements don't really matter. That way, the code could translate just as well to an untyped language, to a language with generics, or to a language where you have to commit to the type. (Generics would only clutter the code, however important they are to use in the real-world.) MShonle 17:24, 29 Dec 2004 (UTC)

I do agree here with you.

--Krischik 18:39, 29 Dec 2004 (UTC)