Stack operations

VECTOR Vol.16 No.4

Stack Operations

by Phil Chastney (phil@amadeus-info.freeserve.co.uk)

1. Introduction 1.1 APL uses infix notation. This has the advantage of being familiar; it has the disadvantage of being ambiguous in anything other than the simplest of expressions.

Prefix and postfix notations are unambiguous. This was proved some time ago by Lukasiewicz, but since nobody in Western Europe can pronounce his name, postfix notation is known simply as Polish notation, and prefix notation is known as Reverse Polish”. Forth and Postscript are perhaps the best known examples of such notations, although they used by some scientific calculators.

Ambiguities can be avoided with infix notation, either by fully parenthesising each expression, or by the use of some form of dot notation’, though neither has been widely adopted.

1.2 Notwithstanding the ambiguity, infix notation has been the rule rather than the exception. A number of methods of overcoming the ambiguity use: left- to-right order of evaluation, right-to-left order of evaluation, and operator hierarchy. Most languages use two or three of these methods. Given a hierarchy, there will situations where non-commutative operations occur at the same level, a simple example being 3*#3**3 (where the double asterisks denote exponentiation). Just what does that expression evaluate to? Some languages would evaluate it left-to-right (to give 19683) and some would evaluate it right-to- left (to give the rather different 7.62e12),

It is common practice in compilers to translate infix expressions to postfix, using a stack and Dijkstra’s shunting algorithm. This makes for easier code generation and faster execution.

1.3 This could be done with APL. Not in the general case - because monadic vs. dyadic use cannot be distinguished until we know all the side-effects of execution up to that point, but in most cases - because the standard recommends (but does not require) that the syntactic class of tokens is bound when execution of a line commences. But why bother with translating to postfix? APL syntax is so brilliantly designed that it is possible to interpret a statement without needing

VECTOR Vol.16 No.4

look-ahead, or any knowledge of the context other than a single stack and the current symbol. This is orders of magnitude faster than some currently fashionable languages.

2. Parentheses as Stack Operators 2.1 The following is a representation process of right-to-left evaluation of a particularly simple expression. represent anonymous temporary variables.)

expression stack 0 (A+B)xc 1 (A+B)x Cc 2 (A+B) x c 3 (AtB ) xc 4 (At B )xc 5 (A + B)xc 6 ¢ A +B)xC 7 |¢ Ty )xc 8 ( T1) xc 9 Ty xc 10 T2

2.2 The different columms of this table reflect the physical differences of the three entities:

* the expression would typically be a tokenised string, drawn from a buffer, possibly refilled from file;

* the current symbol, or a pointer thereto, would be on the registers; * the stack would be in memory, usually high memory.

2.3 The rules for interpretation are fairly simple (largely because we have left out most of the language and all error conditions). These applied there is a change in the current symbol or the top of the stack.

85

VECTOR Vol.16 No.4

3. The Semicolon as a Stack Operator right parenthesis on the stack fulfils three functions: i. it marks the start of a new evaluation, ii. it marks the end of the next unstacking operation, iii. it indicates the type of matching bracket required. We can use the semicolon to perform just the first of these functions. The semicolon is then neither more nor less than a stack operator, in the same class as the parentheses. You can, if you choose, think of it list item separator. The use of the semicolon in this way avoids the ambiguities associated with strand notation, Its use is illustrated below: expression stack 0 |99p(+A;B+C;D) 1 | 99p(+A;BtC;D ) 2 |99e(+A;BtC; D ) 3 |99p(+A;BtC 3 D) 4 |}99p(+A;Bt c 3D) 5 |99p(+A3B + sD) 6 |99p{+A; B +C;D) 7 |99p(+A; TY ;D) 8 |99p(+A ; Ty;D) 9 |99p(+ A 3T43D) 10

| 99p( + A3T15D) ll |99p ( +A3T15D) 12 |99p ( T23T1;D) 13 |99p Ts 14 |99 p 73 15 99 pT3 16 Ty

86

VECTOR Vol.16 No.4

It seen that, in this case, the result, formed by a reshape of a three-element nested vector, will be a ninety-nine element nested vector.

87

VECTOR Vol.16 No.4

nested vectors have many properties in common with character vectors

empty vector tte (} empty vector # scalar x? (X) simple expression {no implicit structuring) (no additional nesting} = 3-element vector, ABC  (A;B;C) 3-element vector unitlength vector 1¢'X* 14(X3). Unitlength vector unit-length vector, =, 'X* {no equivalent)

3.2 Nested vectors have many properties in common with character vectors, some of which are listed below. Leaving aside the strictly arithmetic functions, it would not be unreasonable to expect any function applicable to a character array to be equally applicable to a nested array. Although this happy co-incidence does not obtain precisely, in practice, we can divine the semantics of many operations by analogy.

The principal items outstanding are:

i. a more direct way of constructing a unit-length nested vector;

ii, proper consideration of the fill element to when expanding or overtaking a list;

iii, a re-examination of the semantics of indexed assignment, along the lines implemented in K.

3.3 Two areas of similarity are of interest.

Vectors are the most complicated structure that can be defined directly from the keyboard: anything more complicated must be built up by reshaping vectors.

When a simple array is indexed. by list, each of whose items is a scalar, the result is a scalar. When a nested array is indexed by list, each of whose elements is a scalar, the result is a disclosed item. There is no need for an explicit disclose function.

3.4 Early implementations of list structures (which occurred in mixed output and as the right argument to OFMT) sometimes used pointers within a list, instead of starting anew at each semicolon when evaluating an expression. This sometimes leads to weird and unexpected effects, which seen as a result of

88

VECTOR Vol.16 No.4

implementation shortcuts, or of incompletely specified semantics. Such behaviour should not occur in properly defined and implemented lists.

4, Brackets as Stack Operators 4.1 This elementary stuff, and it hardly gets more difficult when we introduce indexing, beyond the fact that miscegenation is not permitted - AC/DC nonsense, either: left parentheses must partner off with right parentheses, and left brackets must partner off with right brackets.

During interpretation, the occurrence of a right bracket in the input stream can signify either the start of an axis definition, or the start of an index list. This is not a problem: the distinction can be made during the left-to-right tokenising phase.

If we ignore its use in defining the axis operator, the occurrence of a right bracket in the input stream tells us two things:

(i) we are about to start to (ii) we shall then use that list to index into an array.

4.2 We could assign the different parts of the task to separate symbols. We could, for instance, use right and left parentheses to signal the start and end of a list, and then use this list as the right argument to an indexing function. For example, if we resurrect the [-beam function for this purpose,

then A[I3;0;K] becomes AZ(1I;9;K) which might be a useful change or addition to the definition of the language (it is easier to use the new form to write code which is independent of the rank of A), but is here primarily to illustrate the use of lists within present-day implementations.

This unbundling of functional power has always been a part of APL’s attraction. SQL requires select .. from .. where .. sortedby ..” to appear in a single statement, whereas APL provides separate intermediate results from the comparison, compress and grade, for the very good reason that these intermediate results might themselves be of use, separately.

5. Other Stack Operations 5.1 One of the interesting things you can ask about a language is: which parts of this language can we cover with a user-defined function?

89

VECTOR Vol.16 No.4

A cover function for + ? No problem. Compression? Of course. Reduction? No, sorry. Parentheses? You have got to be jokingt Why is this?

Part of the answer is that the stack is not visible to the programmer. Or maybe it is visible, but it is not directly accessible. Which leads into another interesting question: what would life be like if the stack were fully accessible?

This is not such a far-fetched notion: POP-2, for instance, made the stack available, along with facilities to assign a value to the stack, and assign a value from the stack ~ push and pop, essentially. Apart from the obvious assembler-like uses, this mechanism used to construct a partial-binding mechanism, where k arguments of an n-place function are bound, to give a new (1-k)-place function. 5.2 Parentheses represent a minor break normal flow of control; a function call represents a major break in the normal flow of control. Both use the stack to achieve the desired effect. That is to say, when we apply a function, the application operator, which applies a function to its arguments, is a stack operation.

The major steps in applying a function are: * preserve the calling environment, including a return address and an image of the current state of the symbol table;

* close the function, i.e., bind the arguments in appropriate fashion - name, value, pointer, whatever;

* transfer control.

5.3 One of the differences between C and Pascal is the order of evaluation of arguments - interfacing the two requires a bit of jiggery-pokery in assembler, to manipulate the stack.

Order of evaluation is not a problem in APL: we evaluate the right argument, derive the function (if necessary), check whether a left arg is permitted, check whether a left arg is supplied, if so we evaluate that as well, and then apply the function to its argument(s).

A function applied to a list can look like an n-place function, but the order of evaluation specifies that we build the list from the right, then apply the function. There is no ambiguity.

90

VECTOR Vol.16 No.4

With the stack visible, it would be possible to call a function FOO monadically, or stack a value, and call it niladically.

Inside FOO, in either case, we would check the stack for a right argument, and if one is found, proceed as for a monadic application of FOO; if no value is found (i.e., the stack is empty), then the function could prompt the user for the missing this is possible in Rexx, although stack markers are necessary if functions are to be prevented from stealing each others’ arguments.

5.4 Imagine if it were possible to preserve environments: backtrack programming would be so much simpler. At the moment, it is necessary to identify the values which characterise a partial solution, and administer your own stack. With environments as first class objects, it would be possible to run process A until it failed to improve by the required amount, then suspend it, revert to the calling environment, and start over with process B. If process B failed to with the goods, then we could re-activate process A. Languages exist which permit this sort of swapping, through the use of reserved words, but they appear to be largely experimental: other languages offer similar facilities via threads and/or autonomous processes, but it is rarely obvious when the result is intended to be backtrack programming,

5.5 Although they remain objects of interest the case of the semicolon, objects of fear and loathing, even paucity of other examples suggests that we are largely content to leave stack operations to the language processor.

6. Summary By consistently following syntax, we have seen how lists can be deemed to be a part language (and to have been logically a part of the language from Day One).

We can move forward from here to consider how they can the domain to construct nested arrays.

More generalised access to the stack from the high-level language would give us some interesting features, and would be an interesting experiment, but must remain a matter of low priority.

7, References The following are historical notes, from authoritative sources, as well as some original references. You will probably find similar relevant material in any good

91

VECTOR Vol.16 No.4

book on compilers. Assuming an intimate acquaintance with APL, there are no other material external references,

7.1 William van Ormand Quine, Mathematical Logic, Harper Torchbook, 1962 (1st version, 1940, 1951)

p.4l The indication of grouping by means dates from Peano. In details the usage varies from author to author. Curry’s usage (“Dots as Brackets”) is neater than that set forth here, but not as easy to read. Since parentheses are so much simpler in theory, I have preferred to retain them as the official notation and then to frame dot notation conventions with an eye to perspicuity and approximate conformity to prevalent usage.”

Quine does not mention it, but Alonzo Church, writing at about the same time, was also using a system of dots as parentheses.

7.2 David Gries, Compiler Construction for Digital Computers, Wiley, 1971.

p.247 Polish notation is used to represent arithmetic or logical expressions in a manner which specifies simply and exactly the order in which operators are to be evaluated. In addition, no parentheses are needed. In this notation, first employed by the Polish logician Lukasiewicz, the operators come immediately after the operands.”

Although everybody knows Lukasiewicz invented the so-called Polish notation, nobody appears to be able to give the original reference.

p.272 The earliest technique for translating from infix expressions to another form was given by Rutishauser [1952]. His technique consisted of repeatedly scanning the whole expression, finding the innermost simple operation, generating an internal form for it, and replacing it with a simple operand.

Dijkstra [1963] describes the use of hoc) operator precedence techniques to translate expressions to Polish notation.”

The relevant references here are as follows:

(i) H Rutishauser Automatische Rechenplanfertingung bei programmgesteuerten Rechenmaschinen Mitt. Inst. Fir Angew. Math der ETH Ziirich, Nr 3, (1952).

(ii) Dijkstra, E. W. An Algol 60 translator for the X1. (in) Annual Review in Automatic Programming 3, Pergamon Press, pp 329-356 (1963).

92

VECTOR Vol.16 No.4

TECHNICAL SECTION

This section of VECTOR is aimed principally at those of our readers who already know APL. It will contain items people with differing degrees of fluency in APL.

Contents

Hacker’s Corner: Using and Abusing Watchpoints in APL*+Win 3.6 Adrian Smith 95

At Play with J: An Open and Shut Case Gene McDonnell 99

Literate Programming with J and noweb Martin Neitzel 107

Exploring ActiveX Data Objects from a Dyalog-APL Point of View Korablev, Roche 116

93,

Renaissance Data Systems All APL Books in Print

We are pleased to announce that RDS is now on the web at www.aplbooks.cnchost.com with a display of our entire catalog of APL Books in Print. There are even some classic publications which we have received permission to reproduce. Subjects include APL and Mathematics, Learning APL, and APL for the Professional Programmer. We also carry a few books of interest from the rest of the world!

You may contact us using email at rendata@aplbooks.cnchost.com and place orders at orders@aplbooks.cnchost.com. Credit card payment is available for international customers.

Please note our new mailing address:

Renaissance Data Systems P. O. Box 313 Newtown, CT 06470.