Surprise in array concatenation
in [ADA]
|
From: Georg Bauhaus on 5 Sep 2005 09:22 Dmitry A. Kazakov wrote: I think I can abbreviate, by answering this one: > Huh, who can solve Maxwell's equations for a TV set? Does it mean that you > can create one ignoring laws of physics? You *are* ignoring the laws of physing in building a TV set because no one *knows* whether Maxwell's equations describe any particular TV set, and no one *can* perform a complete *test*. We try to approximate, and we do believe, that's what we do. If you claim *not* to ignore the laws of physics when building TV sets, then you will have to show that all of what you build is described by Maxwell's equations (etc.). It boils down to "very likely", "I don't see otherwise", etc. But there is no mathematical demonstration of Maxwell's law describing a TV set, or is there? The laws of physics provide helpful guidance, nothing more, nothing less. No claims, please, that something is physically lawful. Maxwell himself has asked us not to talk about electrons as if we knew that they exist, or what they are. A TV set might surprise us in suggesting that Maxwell's equations aren't complete. Frankly, I won't speculate that my old TV set will do this. Likewise, a computer might surprise us in suggesting that our fine mathematically thought-out program doesn't quite behave exactly as we thought, because of the naughty computer thingy and its quirks. > Re-read what you wrote: an off-bound [array] index is an array bound! Is it > "off" or not? (:-)) We have lo, hi: arrays -> I, item: arrays x I -> values If hi is onto [1, 2, ... 5], then item(hi(Some_Array, X)) lies in values, provided hi(Some_Array, X) is defined. For example, hi(Some_Array, 17) is undefined, generating an exception in Ada terms. If Some_Array'first = 42, hi(some_array, Some_Array'First) is undefined. Exception. Enough consistency here, for my taste. > Better ADT is what Ada needs. Is Ada a Must for you? These things are built into other programming languages. >> as-soon-as cursor is off things in x | P ... > > > No! This is an extremely bad idea borrowed for C pointer arithmetic. It > presumes that cursor might be off. It is a very strong assumption, which > may have a great impact on the algorithm: Certainly off-container indices/cursors offer a practical approach. > 1. The cursor have to have "off" values. Consider the type Character, > you'll need to extend it with two values, left and right. Presently Ada > does not support this. Do you insist that every subtype must be associated with an index subtype, such that every index value can be used to denote a value from the array? > 2. There should be a way to construct off-values. That might be very > non-trivial. Example: pointers. Try to find a pointer that does not point > to some object. The Eiffel solution is to (implicitly) have class NONE be an heir of every class in the system. So NONE conforms to every type, or every type is among the progenitors of NONE. There is a single instance of NONE, called Void. A reference that isn't attached to some object refers to Void. >>Something that I think is frequently found in math literature ;-) > > > I'm not a mathematician, so I cannot tell. But I think that the set theory > explicitly forbids unbound quantifiers, which would otherwise refer to the > set of "all things" (an equivalent of "off-set" thing.) It is no-no. You mean that the set to be enumerated is given? The set need not be finite in computing science, at least this is what I remember from the pleasant days of working my way through books on the subject. Existential quantifiers can be bounded or not, if they are bounded, you have bounded minimization (finding the smallest number such that ...).
From: Dmitry A. Kazakov on 5 Sep 2005 11:50 On Mon, 05 Sep 2005 15:22:18 +0200, Georg Bauhaus wrote: > Dmitry A. Kazakov wrote: > > I think I can abbreviate, by answering this one: > >> Huh, who can solve Maxwell's equations for a TV set? Does it mean that you >> can create one ignoring laws of physics? > > You *are* ignoring the laws of physing in building a TV set > because no one *knows* whether Maxwell's equations describe > any particular TV set, and no one *can* perform a complete *test*. That's a different thing. If you discovered that according to your design the TV set would violate Ohm's law. What would you check first? The design or the theory? > Likewise, a computer might surprise us in suggesting that our > fine mathematically thought-out program doesn't quite behave exactly > as we thought, because of the naughty computer thingy and its > quirks. You are mixing inadequate and inconsistent models. >> Re-read what you wrote: an off-bound [array] index is an array bound! Is it >> "off" or not? (:-)) > > We have > lo, hi: arrays -> I, > item: arrays x I -> values > > If hi is onto [1, 2, ... 5], then item(hi(Some_Array, X)) lies in values, > provided hi(Some_Array, X) is defined. > > For example, hi(Some_Array, 17) is undefined, generating an exception in > Ada terms. > > If Some_Array'first = 42, hi(some_array, Some_Array'First) is undefined. > Exception. Enough consistency here, for my taste. What about hi >= lo? What about handling Some_Array (Some_Array'First) failure? Note that it fails not because there is no A'First, but because the index is wrong? How so? It exists, but wrong! Then what would you do with modular and enumeration types? >> Better ADT is what Ada needs. > > Is Ada a Must for you? Sure. C++ shortens my life! > These things are built into other programming > languages. Like C++? (:-)) >> 1. The cursor have to have "off" values. Consider the type Character, >> you'll need to extend it with two values, left and right. Presently Ada >> does not support this. > > Do you insist that every subtype must be associated with an index subtype, > such that every index value can be used to denote a value from the array? subtype I is Index range A'Range; -- This is legal Ada What I want is freedom. I don't want the compiler to decide for me whether there must be "off" values or not. The concept of array must be consistent with index types having no "off" values, like ring buffers. It also should consistently support arrays over empty index types. >> 2. There should be a way to construct off-values. That might be very >> non-trivial. Example: pointers. Try to find a pointer that does not point >> to some object. > > The Eiffel solution is to (implicitly) have class NONE be an heir > of every class in the system. So NONE conforms to every type, or every > type is among the progenitors of NONE. > There is a single instance of NONE, called Void. A reference that isn't > attached to some object refers to Void. This is incompatible with modular and enumeration types. It also has a distributed overhead. You either will have no by-copy types or will need to store NONE where one bit would otherwise be enough. Then making a hash function you'll need to explicitly test for NONE etc. >>>Something that I think is frequently found in math literature ;-) >> >> I'm not a mathematician, so I cannot tell. But I think that the set theory >> explicitly forbids unbound quantifiers, which would otherwise refer to the >> set of "all things" (an equivalent of "off-set" thing.) It is no-no. > > You mean that the set to be enumerated is given? Sure. And in mathematics there is no problem to write: forall x in X The concept: for I in A'First..A'Last loop is more specialized than for I in A'Range loop and even more than for X in A loop -- Not Ada! I in A'First..A'Last that A'Range is 1) ordered, 2) has the lower and upper bounds, 3) these bounds belong to the array. These assumptions are not always required. Moreover, for some arrays they are wrong. Consider making a loop over a ring buffer starting in somewhere the middle. [We have already debated unordered index types some time ago.] A very practical principle is to design software with minimal assumptions. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Gene on 5 Sep 2005 11:53 Thanks for a great discussion. I didn't say general array indexing is not useful; it obviously is. I said it's marginally useful in the literal (economist's) sense of "at the margin." A few illustrations... 1) If one had to give up a feature in order to get another, many would put general array indexing early on the chopping block. Between fixed and dynamic length arrays (and in particular bounded/unbounded strings), for example, Ada forces one to change from native array syntax to a procedural interface that hides re-sizing details. Ada programmers I know would happily give up general index ranges in order to get dynamically resizing arrays with native syntax---at least those who have worked in other languages where such are available. 2) General integer ranges for array indices are a half-hearted---at the margins---compromise wrt fully general arrays allowing any type as an index. In other words, if you put (A) 1-based arrays, (B) general discrete type array indices, and (C) fully general arrays on a conceptual scale, (B) lies _much_ closer to (A) than to (C). 3) The wonder of Ada is the predicatable, orthogonal way that syntax and semantics correspond. But we have just been observing that general integer array indexing leads to a not-very-predictable behavior in combination with slicing and catenation. If all arrays were 1-based, the problem could not have occurred. Hence this unhappy confluence of features, by conflicting with Ada's philosophy, is at the semantic margins of the language. It ought to be avoided if the goal is code with obvious meaning. E.g. after I re-coded my original example "properly" with 'First and 'Range to make its behavior correct, I quickly added a comment, -- 'First is not always 1. How marginally Ada! Again best regards to all and thanks for the discussion.
From: jimmaureenrogers@worldnet.att.net on 5 Sep 2005 13:47 Gene wrote: > Thanks for a great discussion. > > I didn't say general array indexing is not useful; it obviously is. I > said it's marginally useful in the literal (economist's) sense of "at > the margin." A few illustrations... > > 1) If one had to give up a feature in order to get another, many would > put general array indexing early on the chopping block. Between fixed > and dynamic length arrays (and in particular bounded/unbounded > strings), for example, Ada forces one to change from native array > syntax to a procedural interface that hides re-sizing details. Ada > programmers I know would happily give up general index ranges in order > to get dynamically resizing arrays with native syntax---at least those > who have worked in other languages where such are available. What kinds of projects do those Ada programmers work on? Is performance a critical requirement? Resizable arrays always provide reduced performance over fixed size arrays. Even worse, the performance penalties are driven by the data. This makes successful critical timing consistency impossible when using resizable arrays. Ada provides three kinds of strings. Those three kinds are not present merely for convenience. Each type of string represents a trade-off between efficiency and flexibility. The default fixed string type is the most efficient and least flexible. > > 2) General integer ranges for array indices are a half-hearted---at the > margins---compromise wrt fully general arrays allowing any type as an > index. In other words, if you put > (A) 1-based arrays, > (B) general discrete type array indices, and > (C) fully general arrays > on a conceptual scale, (B) lies _much_ closer to (A) than to (C). I disagree completely with what you say. General index types are popular with scripting languages and a few other new languages. None of those languages concern them selves with execution efficiency to the extent that Ada does. None of those languages are useful in hard real-time systems. Ada language features have not been added merely for the convenience of the programmer. The Ada language started with genuine design requirements. Subsequent refinements of the language have not abandoned the direction and philosophy expressed through those requirements. If you want to use a scripting language such as perl, then use perl. Do not expect all languages to be scripting languages. > > 3) The wonder of Ada is the predicatable, orthogonal way that syntax > and semantics correspond. But we have just been observing that general > integer array indexing leads to a not-very-predictable behavior in > combination with slicing and catenation. If all arrays were 1-based, > the problem could not have occurred. Hence this unhappy confluence of > features, by conflicting with Ada's philosophy, is at the semantic > margins of the language. It ought to be avoided if the goal is code > with obvious meaning. E.g. after I re-coded my original example > "properly" with 'First and 'Range to make its behavior correct, I > quickly added a comment, -- 'First is not always 1. How marginally > Ada! In fact the Ada approach is always predictable with regard to slicing and concatenation. Your experience appears to be rooted in languages with a different concept of type. For instance, C and C++ have no array types. One can define an array in each of those languages, but there is no type tag associated with such an array. One cannot look up the name of an array type in a C or C++ symbol table. Ada provides array types. Ada also provides subtypes. Every instance of an unconstrained array type is constrained. Likewise, every instance of an unconstrained array type represents a subtype of the parent unconstrained array type. All these bits of information are necessary for understanding Ada array slicing and concatenation. Every Ada array and array slice has a set of index values. Slicing an array does not "convert" the index values from their original set to an equivalent size set beginning at 1, 0, or any other value you might choose. The slice forms a view into the array from which the slice is taken. It is quite logical, and not the least marginal, that this view should maintain consistency in its representation. When concatenating two arrays, the language must join the sets of indices in a continuous set of values. Your original posting marveled that the joining of an empty array with a slice not starting at 1 resulted in an array whose 'First value was the same as the slice. Concatenating array A whose indices represent the null set with array B whose indices represent some non-null set should always result in an array whose indices are a non-null set. Moreover, the most efficient and logical merging of the two sets results in a set idenitcal to the indices of B. Jim Rogers
From: Georg Bauhaus on 5 Sep 2005 14:20
Dmitry A. Kazakov wrote: >>Likewise, a computer might surprise us in suggesting that our >>fine mathematically thought-out program doesn't quite behave exactly >>as we thought, because of the naughty computer thingy and its >>quirks. > > > You are mixing inadequate and inconsistent models. The world (our problem domain) *is* inconsistent, otherwise, if it were consistent, how could we possibly know what inconsistency is? We can agree on someting. (As I said, HALT is the limit, I think we cannot even formally decide, mathematically, whether consistency is consistent.) A computer, being a real world item, has a good chance of being whatever it is, there is no complete knowledge of a computer's consistency. Mathematically consistent programs can be helpful when the set of preferred consistency rules is both specified and relates to the program. >>We have >> lo, hi: arrays -> I, >> item: arrays x I -> values > What about hi >= lo? No problem, as hi, lo: arrays -> I are just functions. (These are "minimal" assumptions, really.) > What about handling Some_Array (Some_Array'First) > failure? Same as handling any indexing failure. But different from, and possibly unrelated to, elaborating the range that is established by a pair of index values. > Note that it fails not because there is no A'First, but because > the index is wrong? How so? It exists, but wrong! A'First for an empty array isn't wrong at all, it is just a value from the set of index values. An array is associated with two particular values from the set of index values. Then there is a function, item: arrays x I -> values, defined for some (array, index) pairs, undefined for others. > Then what would you do > with modular and enumeration types? Use subtypes. Computers are finite, so are types. So I say what I want in Ada, another value to mark off the end. Not nice but practical. (Real types exist inside computers, computed in finite time. Mathematical types can exist as "infinite" type look-alikes as in Haskell.) >>>Better ADT is what Ada needs. >> >>Is Ada a Must for you? > > > Sure. C++ shortens my life! Then don't use C++. But there are practical alternatives to C++ if you can give up some pieces of Ada. > Like C++? (:-)) Like many. > What I want is freedom. Then choose not use empty arrays, or test for 'length = 0, or build your own array abstraction, use use Ada.Containers.Vectors, ..... or do not use Ada. > I don't want the compiler to decide for me whether > there must be "off" values or not. The compiler does not force you to use "off" index values, it forces you to use Ada. When this limit is not o.K., ... > The concept of array must be consistent > with index types having no "off" values, like ring buffers. I see that you like this view, and I see that many programmers and language designers use indexing with off-bounds index values. Some languages can do without index manipulation, and with empty sets. Consider this SETL/2 example: program automatic_indexes; Couples := { ["Frank", "Lisa"], ["Joe", "Nancy"], ["Jack", "John"], ["Jack", "Lisa"] }; selpuoC := {[x, y]: [y, x] in Couples}; print("Just the Two of Us: ", {[x, y]: y = Couples(x) | #Couples{x} = 1 and #selpuoC{y} = 1}); for person in { x: x in domain Couples | #Couples{x} = 1} + { y: y in range Couples | #selpuoC{y} = 1} loop print(person, " says, 'One is enough for me!'"); end loop; end automatic_indexes; [Eiffel solution] > This is incompatible with modular and enumeration types. It also has a > distributed overhead. You either will have no by-copy types or will need to > store NONE where one bit would otherwise be enough. Then making a hash > function you'll need to explicitly test for NONE etc. Are you sure you know these things about Eiffel, as opposed to something that you think must must be the case with Eiffel? > Sure. And in mathematics there is no problem to write: > > forall x in X Like in many programming languages. > I in A'First..A'Last that A'Range is 1) ordered, 2) has the lower and upper > bounds, 3) these bounds belong to the array. These assumptions are not > always required. Moreover, for some arrays they are wrong. A range with A'Last > A'First is not wrong, I see that you don't like it. It seems you want to restrict Ada by disallowing programmers to freely use this widespread idiom for expressing empty arrays, because it violates your preferences for some consistency of ordered indexing, right? |