From: andrew@rentec.com (Andrew Mullhaupt)
Newsgroups: comp.lang.apl
Subject: Re: SIGNUM of teaching numerical methods
Date: 30 Jul 92 19:02:03 GMT
Organization: Renaissance Technologies Corp., Setauket, NY.

In article <1992Jul28.144811.21701@yrloc.ipsa.reuter.COM> rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
>In article <1117@kepler1.rentec.com> andrew@rentec.com (Andrew Mullhaupt) writes:
>>In article <1992Jul23.045513.20017@yrloc.ipsa.reuter.COM> rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) writes:
>>>In article <1088@kepler1.rentec.com> andrew@rentec.com (Andrew Mullhaupt) writes:
>>
>>Yes. And what I _really_ want to know is why is this not a problem which
>>has been solved ten years ago?
>
>Well, partially because nobody knew HOW to solve it then. A major problem
>with traditional functional languages is making them run fast on REAL 
>problems. Researchers are only now coming up with ideas on speedups
>for such languages. And not all of the languages being dealt with have
>the flexibility of APL with respect to late binding, array type, rank,
>shape changes, etc.

This is a good reason to blow of APL's late binding. Functional languages
are probably not the answer, but if you want to tout one as a general
purpose language you _have_ to solve this issue.

>>Agree. In fact the strongest programmer I know regards anything where you
>>don't have asynchronous parallelism as trivial. He's probably in some sense
>>right.
>
>According to The Venerable Bede, appeal to authority is the weakest form
>of argument.

I'll take this clever little self reference as an intended pun... :-)

>>I may be wrong, but I think (based on my very limited exposure) that J does
>>not go in the direction I'm pointing in. So from where I sit the field is
>>vacant in the search for post-APL.
>
>OK, so you don't like J and APL. What direction DO you like? Why?

I like traditional compiled languages for their performance. The inclusion
of array operations in FORTRAN 90 shows that large scale operations can
efficiently be handled in this context. It is possible to use a nice 
environment and a compiler, using tricks like incremental compilation and
mixed compilation/interpretation. The main difference in language processing
is no longer compilation/interpretation, but whether you have picked semantics
which allow for highly efficient elaboration. As you have noted, you can
put in some convenient ideas in a traditionally interpreted language, and
never be able to make them go fast. C is a great example of a language where
a lot of inconvenient stuff is there because it's easy to see how to make
it go fast.

I think ANSI Standard Language Extended Pascal (1990) is a very good idea,
since it points in the direction of a much more flexible type system. Before
anyone gets out their "I hate Pascal" attitude, remember that Extended Pascal
is not available anywhere yet (that I know of), and is very much more than the
usual (ISO) Standard Pascal, much more than VMS Pascal, too. It's pretty much
still a 'paper language'. Aside from this (large) defect, the only other
problem with that I can see is that it doesn't go much in the possibly
important direction of treating functions as data. (e.g. Objects, Classes,
etc.). However, not having any actual implementations to talk about means
that there might be some critical flaw hidden in all the fancy new stuff.

The important issues in a general scientific language are twofold:

1. The language itself.

2. How the language deals with it's environment.

For 1, we want both fast big operations and fast little operations. I would
include almost all the APL array operations, and the "self describing" aspect
of APL arrays. (Homogeneous arrays). We want ALGOL-style block structure,
scope and visibility, and flow of control. (I favor Dijkstra's constructs,
but that's a detail). Functions and procedures are typed, as are their
arguments, although using something like Extended Pascal _schemata_, we will
allow formal parameters to belong to "type-families". (APL arrays fit neatly
into this BTW). We want _at least_ concurrent assignment, and a well defined
system of implicit type-casting (again X-Pascal or Algol 68 can be a model).
We want complex arithmetic in a natural way, and _not_ as a user defined
add-in.

We want some not-so usual things, too. In particular, we want the ability
to define functions at run time, in a couple of ways. (I think that the
full lambda caluculus might not be necessary, but I haven't checked.) In
particular, we want the ability to define one function as a restriction 
of another, say

		newfun(b, d) := oldfun(a, b, c, d, e);

in which newfun gets the values a, c and e bound to it. Now the values
may be pointer or reference values, (e.g. C++), so we have full flexibility.
We would like to be able to do this _implicitly_ by casting (and here is
where we might need the whole lambda calculus):

	newfun := (function_type) oldfun(a, b, c, d, e) (b,d);

One classic need for this is when writing multidimensional optimization code
you want to be able to do the line search using a one-dimensional routine,
such as:

	one_D_minimize((f_type) f(p + t +.x d) (t));

or (less commonly) using multidimensional constrained optimization, you
can contruct Lagrangians:

	L(x, lambda) := (f_type) (f(x) + lambda +.x constraint(x));

Since the language will have a lot of knowledge about implicit casting,
not require explicit casts, so we should be able to write


	one_D_minimize(f(p + t +.x d) (t));

	L(x, lambda) := f(x) + lambda +.x constraint(x);

without further ado. Now in an interpreted language, this is a formula for
performance disaster - since all this type calculation, etc., must be done
(in some cases) as often as once for each call. However, since the language
is to be compiled, and the binding to be controlled by the type of the
formal parameters, this is not a big deal.

The wary reader may want to know what happens if L(x, lambda) is defined
as above, but then L is called with x and lambda of different shapes? There
is no problem since if this is allowable, (i.e. the formal parameters have
a shape attribute which can change) then the compiler knows that it has
to write code for L which takes into account these shapes, _and_ knows enough
to force the result type of L to be "shapeable".

Some of this may strike the APL or Lisp programmer as no news. In a sense the
only news is that the language will provide the programmer with the ability
to make typing decisions for the compiler. Suppose that we instead defined

	L(scalar x, scalar lambda) := f(x) + lambda +.x constraint(x);

then we are telling the compiler that L only handles scalar x and lambda. By
similar methods, we can control the result type, and all the implicit casts
can be made explicit if desirable. The compiler is expected to take advantage
of this information in a useful way.

We want to be able to define functions which are prefix, infix and postfix.
We forbid whitespace in names, so we hope that multiplication will be given
the "juxtaposition" syntax which is sometimes proposed. I don't feel too
strongly about these syntactic issues, but I see no real objection* to being
able to use the postfix function (.)T for transpose, so that a Householder
matrix could be given by:

	P := Id - 2 (v (v)T) / ((v)T v);

and the usual application (i.e compute PA) would be:

	A + v (-2 / ((v)T v)) (A)T v;

So the ever present Householder application functions are:

	row.house(A, v) := A + v (-2 / ((v)T v)) ((A)T v);

	col.house(A, v) := A + (-2 / ((v)T v)) (A v) (v)T;

Where the extra parentheses insure the best order of operations (although
it might be OK to leave it up to a smart enough compiler).

*Yes, I am saying that the problem of parsing the language is do-able even
though it isn't obvious at this point.

Keep in mind that since functions are 'first class data' that we need no
separate notion of 'operator' such as in APL2. I also think that you don't
have to go very far to get 'object oriented'. I'm not convinced that's what
you want, though.

Now aside from the question of parsing this (provisional) syntax, everything
we have proposed is pretty much existing compiler technology, and can go
fairly fast, except for the case where we define a function at run time
and then only evaluate it infrequently. I'm willing to let this one go
for the moment since it is not expected to be a pressing issue, but in
principle we demand that this be done 'as fast as possible for the hardware
involved', (whatever that means).

So what else? We want to be able to talk about data structures without
_necessarily_ giving a low-level implementation. For this, I like the
idea of defining structures by a function type. For example, a (rooted,
ordered, i.e. "computer science") binary tree can be regarded as a function
mapping paths (e.g. sequences of <rchild> and <lchild>) to some kind of
value, possibly a default (nil) value. A subtree is obviously a restriction
of this function, and the semantics of insertion, deletion, traversal, etc.
can all be accomodated by definig appropriate functions which take the tree
as arguments. This is certainly elegant, and it isn't new either (it's based
on the Vienna Definition Language spec for PL/I). But will it be fast enough?

In some cases, the fact that the compiler is going to work very hard to do a
good job on function restrictions, this may be adequate for many of the more
difficult uses of the structure - i.e. heterogeneous data associated with the
binary tree, etc. However we should provide the traditional low level recursive
data manipulations in some form (e.g. referent data, maybe even pointers...)

In favor of the function-based approach, some large scale operations on
recursive data structures are already defined, and there is the possibility
of using type-pragmas to clue the compiler in on what might be a good way
to implement the functions. (E.g. inlining, hashing/caching recent values,
etc.)


As for the second issue, (how the language interacts with it's environment)
I adopt a pretty pragmatic line.

1. No replacement of the O/S file system. Nobody needs this kind of
   portability. Instead, a standard environment is defined which can
   be used for portability, but it is not expected to be full bandwidth.

2. Compatability with fully promiscuous calling in and out of the language
   and other traditional languages, _no_ requirement of copying data. It
   is expected that the compiler will be able to handle alien calling
   conventions _even in some cases at run time_. Scrambled name linking
   (i.e. C++) will be accomodated in some way.

3. Where possible, memory management is provided which allows for the user
   to specify what kind of backing is used. Multiple separate memory managers
   will be permissible. It will be effectively possible to give memory back
   to the O/S. It will be possible to "print the pointers" if desired.

4. Where possible, dynamic loading is supported, so that programs can be
   modified at run time _in addition_ to the program's internal capability
   to redefine its function variables.

5. Providing duplicate services to the O/S will be discouraged. Rather, it
   will be encouraged for the O/S services to be accessed in the usual way
   for that O/S.

6. With the possible exception of persistent variables, (see "print the
   pointers", above), the language will not introduce any special kind
   of file or format. In the case of persistent variables, the language
   will provide complete documentation for any file format used _and this
   documentation will be in the public domain_. Because of the widespread
   promiscuity of this language, it will be possible to provide libraries
   callable from other languages which can use these persistent variables,
   without the need for a full implementation of the language. It is
   encouraged that these libraries will be available separately from the
   full language system.
   
7. In the manner of Algol 68, a 'standard environment' may be provided.
   This will allow for modularization of the implementation of the 
   language. Additionally, parts of this environment will allow the
   individual user to have _complete control over the style and
   appearance of the language_. In particular, it will be _trivial_ for
   every user to change the syntax in any consistent way because the
   language will apply a (nearly reversible) preprocessor to source code. It
   will be expected that before looking at someone else's code, you will
   run it through their preprocessor and through the inverse of you own.
   Nobody will fight over begin...end vs. {..}. People will be able to
   write source assuming right-to-left order of execution since they
   will be able to configure their preprocessor to stick in lots of
   parentheses, etc. Internationalization of the source can be done here.
   Arthur Whitney will be able to remove all whitespace before he looks
   at anyone else's code. Someone who wants to use glyptic runes to
   represent the language will be free to do so. Nobody will _have_ to
   swallow anyone else's idea of how the language should look. People
   will be able to process their code through special filters which
   will provide for fancy stuff like run time profiling, tracing, etc.

   This preprocessor will do a heap of syntax checking, etc. and will
   also be able to (if desired) insert code where it seems needed. In
   particular, people who don't want to declare all their variables
   can have the preprocessor supply "Miranda declarations" of undeclared
   variables. It will also be possible for the preprocessor to be invoked
   interactively (perhaps in the form of an editor) where context sensitive
   help will be availalble. This help will be expected to be user-modifiable
   so that vendor-specific, platform-specific and even site-specific help
   on translation will be of use.

Now there is a lot more to say, but perhaps by now you get the picture.
What I am in favor of is a system which has a flexible, interactive front
end, with a heavy emphasis on several different levels of language translation
(and even some CASE like aspects). Stupid issues, like character set, key
words, native language, etc., are settled in a way which provides each
human as wide a lattitude as possible in their expression. The development
of source in this language system proceeds through various stages towards
a pretty hard-core language at the end of source preprocessing. This
target language is then dealt with by the back end of the system, which
should (in a full implementation) look like an interpreter which knows
how to compile pieces and then link them in automatically. As development
proceeds towards the finished product, the amount of code which is interpreted
goes to zero, at which point the program is totally compiled.

As far as I can tell, the only parts of this plan which isn't already done
somewhere in computer science are certain aspects of the syntax translation
of the language, and the part about function restrictions in compiled
languages - although I bet compiled Lisp has things like this, but with
'type' not being so useful as it would be here.

Later,
Andrew Mullhaupt


Newsgroups: comp.lang.apl