[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Complex numbers & Oakwood suggestions
Looks like I messed with Pandora's box when I started this thread.
Some of you--no, make that Michael Griebling and Brian Hawley--scared
the holy shit out of me. Then I decided to laugh at it, but it didn't
help very much. I'm still a tiny bit frightened... :-}
Let's summarize the bulk of replies so far. Two of them were directed
to me personally. I'll put them on the list in a companion posting.
[From: Mike Griebling <grieblm@trt.allied.com>]
> I assume these constructors would be useable in constant expressions?
Yes, CMPLX and LONGCMPLX would behave like any other predefined
function and could appear in any constant expression. For complex
constants there's also the other notation: CMPLX(1, 2) == 1+2.0i
> We also have to consider the implications of the comparison operators.
> Can we really compare REALs and COMPLEX numbers? I'm not exactly sure
> what a comparison of two complex numbers means.
As Michael Smith pointed out, there is no natural concept of
comparison between complex numbers. The comparison operators and the
predefined functions MIN/MAX wouldn't be available for complex values.
Here comes the scary part. Michael G. wants
> structured function results
> overloaded function names
> overloaded operators
Michael, you must be teasing me. Remember, we want to build an OBERON
compiler, no a C++ compiler using Oberon syntax. I never understood
the need for structured returns. Even if you have them, all you can
do is to assign them to a variable or pass them to a variable
parameter. You cannot apply any (field, index, etc) selectors to
them. Or do you want to change this also? I won't even discuss the
possibility of overloaded functions and operators...
[From: Guy Laden <laden@math.tau.ac.il>]
> If efficiency is the issue i think the first thing to do is
> profile the performance of programs compiled with an OOC implementation
> of the standard language to find the bottlenecks.
There are three kinds of efficieny to consider:
1) Execution speed of the compiled code.
Using a pointer based representation will slow it down, but not
significantly (in the average case).
2) Storage allocation.
The overhead of pointers is significant. There is the pointer
itself, the type tag on the heap, and the overhead due to alignment
and allocation restrictions of the memory allocator. Not to
mention the gargabe collection.
3) Efficiency of writing code.
You need a _very_ dedicated programmer to write large pieces of
code using a programming language that doesn't even marginally
support the notation he really needs. Any mathematician will be
disgusted to use a three operand procedure from the library to
built something as simple as a complex constant.
Adding complex types to the language will cut the overhead of 1) and
2) and will make it considerably more attractive to people who won't
even look at Oberon-2 due to the lack of 3). I don't care much about
1) and 2), but the last point is, IMO, the most important one.
> The last thing I'd like to see is yet another GNU package that
> tries to be everything to everyone.
I agree wholeheatedly.
> Does it realy make sense to experiment with language design in
> the context of OOC? Can you seriously picture yourself implementing complex
> numbers and then being ruthlessly honest enough to rip them out of the
> compiler.
No, I can't. I'd never suggest an extension without being convinced
that the OOC project would benefit from it. My reasons for adding
complex types are very low additional compiler complexity and a
possibly large group of additional users.
> Whatever you decide, I urge you to do it after OOC is complete.
A compiler is never finished ;-). Ask Frank, he'll tell you the
same, but probably in context.
Michael G.'s comment on this:
> > Whatever you decide, I urge you to do it after OOC is complete.
> I would agree with this. Let's finish a first draft compiler with working
> back-ends before we increase the complexity of the task.
See the end of this mail for a discussion of the addtional complexity.
[From: Michael Smith <msmith5@orion.it.luc.edu>]
> The implementation of complex numbers in the Oberon language would
> open up a user base amoung Physicists, Engineers (virtially all
> disciplines of Engineering), Mathematicians, Economists, Ecologists,
> &c. &c. &c. Because complex numbers have some special properties real
> numbers don't, use of real number libraries is insufficient and in
> some cases produces wrong answers.
Great that there is some support for my suggestion, even from an
unexpected angle. Adding the types to O2 will make it much more
convenient for the above mentioned groups to use O2, instead, say
Fortran or C++. Only the most basic complex arithmetic and notation
will be served by the compiler, the rest will be put into dedicated
libs, just like the real types.
> (NB: If anyone is interested in C++ pseudocode for complex functions I
> will be more than happy to provide. If we include those in a separate
> library the techheads will adore us. ...
I don't mind if a bunch of techheads see the true light of Oberon ;-).
> Of course, I know a lot more about mathematics and physics and EE than
> I know about compiler design. :)
Which makes you a user. This means you are in the best position to
make suggestions. I'll append a more detailed description of the
extensions I have in mind to this mail, so that you (and the others)
get a better picture of what these additions would mean.
[From: Brian Hawley <bhawley@luc.edu>]
> Complex numbers can be implemented using the *REAL types well enough,
> and they are only of use to a relatively small number of people.
Yes, but people who have to use them expect a little more support from
their programming language of choice (or rather, they use a language
that gives them what they want).
> Oberon is meant to be a simple, small language. A complex number
> library that is implemented using functional notation would not be
> much different in practice to use than a built-in type--you would have
> to put the module name before the functions, but that's what aliased
> module imports are for.
I don't understand the relevancy of this comment. Of couse there will
be a complex math library. Having an (unstructured, not imported)
complex type will allow to write things like
PROCEDURE sqrt (z: COMPLEX): COMPLEX;
> Most of what I know about them [complex numbers] has come from Michael
> Smith, a friend and industrial-strength math head. He and I
> implemented libraries for complex numbers in Oberon; he did the
> algorithms and I programmed them. Mike has seen the Oakwood
> guidelines, and he doesn't like them. His major concern is that they
> are implemented in the Cartesian style. Despite the popularity of
> Cartesian complex numbers, Mike has shown me that polar numbers are
> much more efficient for a wide variety of tasks. When we implemented
> our complex library, we chose not to take sides on the issue and did
> the full set of functions for both types of complex numbers.
I suppose you are talking about the same Mike Smith that contributed
the mail cited above. His personal mails differs somewhat from your
quote ;-) [see the companion posting]. About the topic
cartesian/polar: I agree that there are problems that can be solved
only be one of the representations efficiently. I don't think it's
desireable to add both to the compiler. Since both represenations
only differ in the way you look at them, it's possible to build a lib
module that defines "TYPE PCOMPLEX*=COMPLEX;" and provides functions
to handle polar complex values. The only drawback is that the
compiler won't know the difference between the two represenations.
A very simple mistake would be to add two polar numbers with the
built-in operator. IMO the polar/cartesian decision is the most
serious drawback. I won't put too much weight on it since we already
have a vote from a user on the cartesian option.
> If we are going to extend the language we should start with array literals,
> constructors and operations in the Oberon/V style. Despite the fact that V
> was designed for numeric programming, the array extensions can be useful for
> general purpose code as well. If you doubt this, take a look at how they are
> used in the Object Pascal language of Borland Delphi. They use open array
> parameters and literal arrays to implement type-safe variable arguments. I
> would love to be able to do that in Oberon. That same notation could be used
> for calls to external C functions as well. The array ops could also increase
> optimization opportunities on systems with pipelines or multiple processors
> (like your BeBox, Mike :).
Sigh. This is the other scary point. I'm writing a front-end for an
Oberon-2 compiler, not an Oberon/V, Object Pascal, or "C++ that looks
like Oberon" compiler. Your complex number mail was very convincing,
but I doubt that you can convince me to introduce new array types.
I don't know Oberon/V, but I suppose the V stands for `vector'.
Another guess of mine is that it is a language that is primarily
designed for number crunching, targeted at vector machines. I don't
think that pipelined or multi-processing machines would benefit from
this, you'll need a full-fledged vector computer for this. I won't
add such things to OOC, but from a language design point of view I'm
interested. Could you explain (and give examples, and implementation
sketches) of the Oberon/V resp. Object Pascal you like so much?
------------------------------------------------------------------------
Changes to the O2 language report to incorporate complex data types:
3.2 Numbers are (unsigned) integer, real, or complex constants. If a
real constant is specified with the suffix i, then it is interpreted
as the imagenary part of a complex number with a real part of zero.
number = integer | real | complex.
complex = real "i".
Examples:
12.3i COMPLEX 0+12.3i
4.567E8i COMPLEX 0+456700000i
0.577D-6 LONGCOMPLEX 0+0.000000577i
6.1 Basic Types
9. COMPLEX the cartesian complex numbers in REAL x REAL.
10. LONGCOMPLEX the cartesian complex numbers in LONGREAL x LONGREAL.
where REAL denotes the range [MIN(REAL)..MAX(REAL)] and LONGREAL the
range [MIN(LONGREAL)..MAX(LONGREAL)]. The types 9 and 10 are called
complex types. The numeric and complex types together form a directed
acyclic graph; the larger type inlcudes (the values of) the smaller
type:
LONGCOMPLEX--LONGREAL--REAL--LONGINT--INTEGER--SHORTINT
\ /
COMPLEX
8.2.2 Arithmetic operators
The operators +, -, *, and / also apply to operands of complex types.
The type of the result is the smallest type that includes both
operands, except for division (/), where the result is the smallest
non-integer type wich includes both operands.
The operator ~ applies to complex operands and denotes the conjugate
complex value.
8.2.4 Relations
The realtions = and # also apply to complex types.
10.3 Predeclared procedures
Function procedures
Name Argument type Result type Function
RE(z) COMPLEX REAL real part of z
RE(z) LONGCOMPLEX LONGREAL real part of z
IM(z) COMPLEX REAL imagenary part of z
IM(z) LONGCOMPLEX LONGREAL imagenary part of z
LONG(z) COMPLEX LONGCOMPLEX identity
SHORT(z) LONGCOMPLEX COMPLEX identity
CMPLX(x,y) REAL, REAL COMPLEX complex number z=x+yi
LONGCMPLX(x,y) LONGREAL, LONGREAL LONGCOMPLEX complex number z=x+yi
Appendix A: Definition of terms
Type inclusion
Numeric or complex types include (the values of) smaller numeric or
complex types according to the following DAG:
LONGCOMPLEX--LONGREAL--REAL--LONGINT--INTEGER--SHORTINT
\ /
COMPLEX
Expression compatible
operator 1st operand 2nd operand result type
+ - * numeric or numeric or smallest numeric or complex
complex complex type including both opnds
/ numeric or numeric or smallest non-integer
complex complex type including both opnds
~ complex same type as opnd
= # complex complex BOOLEAN
------------------------------------------------------------------------
Conclusions:
The above specified extensions make it possible to use the predefined
types COMPLEX and LONGCOMPLEX like any other predefined (numeric)
type, including the possibility to return them as function results.
The standard arithmetic operations + - * / are defined for complex
numbers, additionally the conjugation operator ~.
Complex numbers are part of the numeric type inclusion hierachy and
type conversion applies to them.
Example:
VAR a, result: COMPLEX; b: REAL;
result := a+b;
result := 2.0*b;
These expressions are valid. In the first `b' will be converted into
a value of type COMPLEX, added (piecewise) to `a', and stored in
`result'. In the second example the REAL value `2.0*b' will be
calculated, converted to COMPLEX, and assigned to `result'.
Complex constants can be constructed like "1.0 + 2.0i" (or with
CMPLX/LONGCMPLX), complex variables by using the predefined functions
CMPLX and LONGCMPLX.
Implementation details:
The additional complexity is minimal. All operations on complex
values are broken down to real arithmetic by the front-end. The
optimization potential is fairly high since the details of the
calculations are visible to the optimizers. There will be four
additional GSA opcodes (access|update)-(real|img) to read resp. set
the parts of a complex number. They are defined just like the
coresponding operations on record fields. With respect to procedure
calls and function returns complex values will be treated like any
other scalar value. The back-end has to decide how it passes complex
values, either per value or per reference. I can serve both choices
in the front-end.
------------------------------------------------------------------------
That's all for now. All your comments against an extension are noted,
by IMO the benefits are of greater value than the drawbcks. Again,
any comments are welcome. Please, don't scare me again ;-).
-- Michael van Acken