Larger matrices
in [ADA]
|
Prev: Size of Vector limited to 1024 MB of Heap Size
Next: How to implement a server socket compatible to telnet?
From: Georg Bauhaus on 8 Aug 2008 11:40 Dmitry A. Kazakov schrieb: > They are not. Lisp is a list-oriented language, Prolog is a logical > inference language. Lisp and Prolog with FFI(!) are not universal? Come on. >> This notion of "purpose" is not very specific. >> Let me put is this way: Ada has to be especially good at >> systems programming, hence it has to be fairly low level. > > Wrong. Where that follows from? Systems programming need not to be > low-level. A systems programming language must provide for the low level. A language that does not provide for the low level is not a systems programming language. Ada has many features that provide for low level programming. It lacks a numer of features used in higher level programming (E.g. function environments, unbounded numbers, ...). Systems programming is not the same as low level programming or high level programming; rather, the set of objects is typically not as abstract as some mathematical N-array of numbers. The set of objects in a systems programming language is more like a real N-array of numbers: storage cells of well defined meaning, with just one layer of abstraction above the storage cells. >> What hardware? > > Vector processors. OK, I wasn't aware that the LA packages were made for vector processors only. >> Assume data flow hardware, and assume a way >> to put the function result in the input box of the next processing unit. >> What now? > > Nothing, Ada.Numerics.Generic_Real_Arrays was not designed in order to > support this hardware. Aha? I see that GNAT delegates to Fortran libraries. Traditionally, Fortran is certainly an associate of non-PC hardware. > Which is the point. Ada is not low-level, Ada is fairly low-level. >> I don't see how prototyping a hypertext graph algorithm >> requires a maximally efficient implementation of matrix >> computations. > > Because of the problem size. Incidence matrices grow as O(n**2), i.e. > extremely fast. O(N**2) is not extremely fast; many non-extreme algorithms are in this class. The case discussed hits some memory barrier at n = 5_000 and that's it. We get elaborate array indexing support in some array programming languages. If chosing one of those PLs costs me a constant factor of 10, I get all the indexing stuff in return, it seems worth the cost during prototyping. >> A production system may require increased >> efficiency. At that stage you have to pay attention to >> the tiny bits, possibly redesigning the algorithm. > > Numerics is all about algorithms. Numerics is about numbers (or about numeric control, depending). > This BTW is exactly the problem OP has. He has "prototyped" the thing using > Ada.Numerics.Generic_Real_Arrays. Now, he faces the problem that the > prototype does not scale due to stack overflow. The consequence is a need > in full redesign. Ergo, prototyping was time wasting. Nice rhetoric logic error. -- Georg Bauhaus Y A Time Drain http://www.9toX.de
From: Dmitry A. Kazakov on 8 Aug 2008 12:37 On Fri, 08 Aug 2008 17:40:16 +0200, Georg Bauhaus wrote: > Dmitry A. Kazakov schrieb: > >> They are not. Lisp is a list-oriented language, Prolog is a logical >> inference language. > > Lisp and Prolog with FFI(!) are not universal? Come on. Of course they are not. Both are domain-specific languages. >>> This notion of "purpose" is not very specific. >>> Let me put is this way: Ada has to be especially good at >>> systems programming, hence it has to be fairly low level. >> >> Wrong. Where that follows from? Systems programming need not to be >> low-level. > > A systems programming language must provide for the low > level. Nope, it must provide systems programming domain abstractions. Ada does this. This does not make it low-level. It seems that you are confusing different concepts of abstraction. Level depends on where is the ground, the underlying computational environment. This is not necessarily the hardware, but it can be one. 1. Considering hardware as the environment. Ada running on an Ada-hardware (if such existed) would make this implementation of Ada low-level. But it would not make Ada low-level, because it also runs on the hardware requiring much work to create an Ada compiler. Therefore Ada in general is high level relatively to the hardware. 2. Considering programming paradigms as the environment, i.e. the terms in which programs are thought an composed. Ada is again very high level, as it supports up to 3rd set abstractions: value -> type (sets of) -> class / generic (sets of) OO decomposition, concurrency etc. > A language that does not provide for the low level > is not a systems programming language. A logical fallacy: A => B does not imply A = B. > Ada has many features > that provide for low level programming. It lacks a numer of > features used in higher level programming (E.g. function > environments, unbounded numbers, ...). Since when unbounded numbers became high level? Consider it used to implement modular arithmetic or ASCII characters. How low-level! > Systems programming > is not the same as low level programming or high level programming; > rather, the set of objects is typically not as abstract as > some mathematical N-array of numbers. I don't see how interrupt, task or I/O port are less abstract than array. >>> What hardware? >> >> Vector processors. > > OK, I wasn't aware that the LA packages were made for vector > processors only. Take Intel x86 instead, if you don't like vector processor. >>> Assume data flow hardware, and assume a way >>> to put the function result in the input box of the next processing unit. >>> What now? >> >> Nothing, Ada.Numerics.Generic_Real_Arrays was not designed in order to >> support this hardware. > > Aha? I see that GNAT delegates to Fortran libraries. Traditionally, > Fortran is certainly an associate of non-PC hardware. That was not the point, it was as it reads, the design did not target any hardware and will be *relatively* inefficient on any existing hardware. Relatively, because it most likely will beat both Lisp and Prolog. >>> I don't see how prototyping a hypertext graph algorithm >>> requires a maximally efficient implementation of matrix >>> computations. >> >> Because of the problem size. Incidence matrices grow as O(n**2), i.e. >> extremely fast. > > O(N**2) is not extremely fast; many non-extreme algorithms > are in this class. The case discussed hits some memory barrier > at n = 5_000 and that's it. We get elaborate array indexing support > in some array programming languages. If chosing one of those > PLs costs me a constant factor of 10, I get all the indexing > stuff in return, it seems worth the cost during prototyping. No chance. O(N**2) is only memory complexity. You should also consider the number of operations required per element. Naive matrix multiplication is O(N**3). Factor 10 means (N x 10)**3 thousand times slower! And this is only the lower bound. But all this is in order learn that the fancy language X is greatly slower than Ada and is totally unsuitable for production code? I know it in advance! -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Georg Bauhaus on 8 Aug 2008 13:37 Dmitry A. Kazakov schrieb: >> A systems programming language must provide for the low >> level. > > Nope, it must provide systems programming domain abstractions. Ada does > this. This does not make it low-level. The systems programming domain abstractions are fairly low level. Please, fairly. Yes, there are some higher level abstractions, like the whole of tasking is. But tasking is far from describing the entirety of Ada. You can have the same tasking offered with much higher level PLs. > 1. Considering hardware as the environment. Ada running on an Ada-hardware > (if such existed) [...] > > 2. Considering programming paradigms as the environment, i.e. the terms in > which programs are thought an composed. Ada is again very high level, as it > supports up to 3rd set abstractions: > > value -> type (sets of) -> class / generic (sets of) Wow, "value -> type (set of)" sorts assembly languages just one tiny bit below a type safe generic O-O language: imul / fmul. No constructionist shuffling of artificial categorization frameworks will convince me that Ada is not a systems programming language. C++ is one, too. (For another example, Erlang is reportedly good if helped by a FFI.) And Ada is a rich set of fairly low-level features. (I am not away of an 'Address mechanism in ML (without FFI).) There is no EVAL or COMPILE in Ada. There is no goal directed evaluation. There is no function environment (no upward closures). There are no generators with suspension. There are no comprehensions, no infinite data structurs. There is no symbol manipulation, no expression macros, no inference. There is no higher order anything. There are no solvers. There are no graphics primitives etc.. There are good elementary data types. And then no data structures other than those that the programmer defines using the find construction primitives. Tasks and POs are built into the typesystem. Great for systems programming, and also for higher level things like ... pfhhh, whatever ... But does a shared variable mechanism lift Ada to the level of languages such as APL (which tends to have it, too)? >> A language that does not provide for the low level >> is not a systems programming language. > > A logical fallacy: A => B does not imply A = B. No wonder, you stopped after the first premise ;-) > No chance. O(N**2) is only memory complexity. You should also consider the > number of operations required per element. Naive matrix multiplication is > O(N**3). Factor 10 means (N x 10)**3 thousand times slower! And this is > only the lower bound. But all this is in order learn that the fancy > language X is greatly slower than Ada and is totally unsuitable for > production code? I know it in advance! > You can write an algorithm operating on matrices in O(Absurdly High Degree). The original question was about vector product where one operand is a row of a matrix. The specific problem seems to make it desirable to be able to say, 5 3 .. 14 by . 16 You get the idea. Other algorithms may require more elaborate subset of matrix cells. Use a language that allows you to say, using *builtin* operators, things like "Give me all blocks of neighbours no more than two edges apart." That's high level. -- Georg
From: Georg Bauhaus on 8 Aug 2008 13:42 Georg Bauhaus schrieb: > features. (I am not away of an 'Address mechanism in ML (without FFI).) aware > There are good elementary data types. And then no data structures > other than those that the programmer defines using the find fine > construction primitives.
From: Dmitry A. Kazakov on 8 Aug 2008 15:51
On Fri, 08 Aug 2008 19:37:15 +0200, Georg Bauhaus wrote: > Dmitry A. Kazakov schrieb: > >>> A systems programming language must provide for the low >>> level. >> >> Nope, it must provide systems programming domain abstractions. Ada does >> this. This does not make it low-level. > > The systems programming domain abstractions are fairly > low level. Why? Low relatively to what? > But tasking is > far from describing the entirety of Ada. You can have the same > tasking offered with much higher level PLs. Synchronization mechanisms of higher level than Ada? I am excited. You mean semaphores, I bet. Please, show us that fancy language and also how tasking there is integrated into other "higher-level" language features. >> 1. Considering hardware as the environment. Ada running on an Ada-hardware >> (if such existed) [...] >> >> 2. Considering programming paradigms as the environment, i.e. the terms in >> which programs are thought an composed. Ada is again very high level, as it >> supports up to 3rd set abstractions: >> >> value -> type (sets of) -> class / generic (sets of) > > Wow, "value -> type (set of)" sorts assembly languages > just one tiny bit below a type safe generic O-O language: imul / fmul. Assembler does not have user-defined types. In the hierarchy above all elements are user-defined. Assembler has only user-defined values. I.e. it is only at 1st set abstraction. > There is no EVAL or COMPILE in Ada. Assembler has them. > There is no goal directed evaluation. I saw this term only in the context of low-level image processing primitives. Sorry, it rings wrong bells. > There is no function environment (no upward closures). Procedural composition is itself low-level. Ada need not to worry about that low-level stuff. > There are no generators with suspension. Hydropneumatic suspension? Sorry. > There are no comprehensions, no infinite data structurs. These structures are inconsistent. > There is no symbol manipulation, no expression macros, no inference. Symbol manipulation is text processing, no problem in Ada. Macros is low-level source text processing. We don't need that. Elaborated inference is inconsistent with maintainability if not low-level. Namely, if inferred things are understandable, they are trivial. If they are non-trivial (as in Prolog), then nobody can predict the program's behavior. My favorite example is AI. Healthy man and woman need no PhD degree in order to create an intelligent system. That is a case of "inference." And it does the job, alas with a totally unpredictable outcome. Why in your opinion do people write tons [of mostly useless] scientific articles on the AI issue? They want to have it imperative! Furthermore, complexity of inference is unrelated to the abstraction level. There exist both very complex and very low-level things. > There is no higher order anything. ? > There are no solvers. Because Ada programs solve non-trivial problems. Anyway, declarative is not a synonym of higher level. "Fly to Mars" is higher level than "I like cheese." > There are no graphics primitives etc.. Turtle graphics must be of an extremely high level... You are making an error equating domain-specific to high level. It is usually reverse. Domain-specific languages are of very low level, because they translate straightforwardly into the engine, which plays the role of the hardware. This is low-level. Note that due to the limitation of the application area and because domain-specific abstractions are quite rough and irregular, such languages usually do not provide any higher level abstractions. For example, OpenGL is of 1st order. You cannot define new graphic primitives. You cannot bundle graphic primitives into generic sets of, etc. Describe a set of tables sharing some property in SQL. Declare class of rhombus-like inheritance graphs in UML. In terms of abstraction level, most of domain-specific languages stop where FORTRAN-IV began. That's why there is no 5GL, 6GL, 7GL... The idea was wrong. > But does a shared variable mechanism lift Ada to the level of > languages such as APL (which tends to have it, too)? I don't know its newer versions. Initially it was very low-level, 1st set abstraction, in the classification above. >> No chance. O(N**2) is only memory complexity. You should also consider the >> number of operations required per element. Naive matrix multiplication is >> O(N**3). Factor 10 means (N x 10)**3 thousand times slower! And this is >> only the lower bound. But all this is in order learn that the fancy >> language X is greatly slower than Ada and is totally unsuitable for >> production code? I know it in advance! >> > > You can write an algorithm operating on matrices > in O(Absurdly High Degree). The original question was about > vector product where one operand is a row of a matrix. It was matrix multiplication, I guess. > Use a language that allows you to say, > using *builtin* operators, things like > > "Give me all blocks of neighbours no more than two edges apart." > > That's high level. procedure Give_Me_All_Blocks...; This is not high level, and I know the price. Domain-specific languages are usable in domain-specific cases ... and unusable universally. In my area of professional interest we are forced to fight with various domain-specific languages on the daily basis. I have reasons to dislike them. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |