Jump to content

APL (programming language)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 129.78.228.114 (talk) at 05:45, 26 April 2007 (Character set). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

APL
Paradigmarray, functional, structured, modular
Designed byKenneth E. Iverson
DeveloperKenneth E. Iverson
First appeared1964
Typing disciplinedynamic
Major implementations
IBM APL2, Dyalog APL, APL2000, Sharp APL
Dialects
A+
Influenced by
mathematical notation
Influenced
J, K, Nial

APL (for A Programming Language) is an array programming language based on a notation invented in 1957 by Kenneth E. Iverson while at Harvard University. It originated as an attempt to provide consistent notation for the teaching and analysis of topics related to the application of computers. The notation was later used to describe the IBM System/360 machine architecture, a description much more concise and exact than the existing documentation and revealing several previously unnoticed problems. Later, a Selectric typeball was specially designed to write a linear representation of this notation. In 1964, a subset of the notation was implemented as a programming language.

Iverson published his notation in 1962 in a book titled A Programming Language and APL got its name from the title of this book, however even early APL differs significantly from the notation described in his book. Iverson received the Turing Award in 1979 for his work.

As with all programming languages that have had several decades of continual use, APL has evolved significantly, generally in an upwards-compatible manner, from its early releases. APL is usually interpretive and interactive, features much appreciated by its users. Further, the initial lack of support for structured programming has been rectified in most of the modern APL implementations.

One much criticized (and celebrated) aspect of APL is the use of a special character set visually depicting the operations to be performed (see Character set below). These characters have all been incorporated into Unicode, and are entered by keyboard mappings or Input Method Editors.

Iverson later reworked APL into a language called J which not only greatly increases expressive power but also uses pure ASCII (with digraphs) instead of a special character set.

Overview

Over a very wide set of problem domains (math, science, engineering, computer design, robotics, data visualization, actuarial science, traditional DP, etc.) APL is an extremely powerful, expressive and concise programming language, typically set in an interactive environment. It was originally created, among other things, as a way to describe computers, by expressing mathematical notation in a rigorous way that could be interpreted by a computer. It is easy to learn but some APL programs can take some time to understand, especially for a newcomer.

Unlike traditionally structured programming languages, code in APL is typically structured as chains of monadic or dyadic functions and operators acting on arrays. As APL has many nonstandard primitives (functions and operators, indicated by a single symbol or a combination of a few symbols), it does not have function or operator precedence. Early APL implementations did not have control structures (do or while loops, if-then-else), but by using array operations, usage of structured programming constructs was just not necessary. For example, the iota function (which yields a one-dimensional array, or vector, from 1 to N) can replace for-loop iteration. More recent implementations of APL generally include comprehensive control structures, thus data structure and program control flow can be clearly and cleanly separated.

The APL environment is called a workspace. In a workspace the user can define programs and data, i.e. the data values exist also outside the programs, and the user can manipulate the data without the necessity to define a program. For example,

assigns the vector values 4 5 6 7 to N;

adds 4 to all values (giving 8 9 10 11) and prints them (the absence of the assignment arrow means "show");

prints the sum of N, i.e. 22.

The user can save the workspace with all values, programs and execution status.

APL is well-known for its use of a set of non-ASCII symbols that are an extension of traditional arithmetic and algebraic notation. These cryptic symbols, mostly the reason it is possible to formulate extremely terse and compact problem formulations in APL, make it possible to write Conway's Game of Life in one line of code (example). In nearly all versions of APL, it is theoretically possible to express any computable function in one expression, that is, in one line of code.

Because of its condensed nature and non-standard characters, APL has sometimes been termed a "write-only language", and reading an APL program can at first feel like decoding Egyptian hieroglyphics. Because of the unusual character set, many programmers use special keyboards with APL keytops for authoring APL code. Although there are various ways to write APL code using only ASCII characters, in practice, it is almost never done. (This may be thought to support Iverson’s theses about notation as a tool of thought.) Most if not all modern implementations use standard keyboard layouts, with special mappings or Input Method Editors to access non-ASCII characters. Historically, the APL font has been distinctive, with uppercase italic alphabetic characters and upright numerals and symbols. Most vendors continue to display the APL character set in a custom font.

Advocates of APL claim that the examples of "write-only" code are almost invariably examples of poor programming practice or novice mistakes, which can occur in any language. Advocates of APL also claim that they are far more productive with APL than with more conventional computer languages, and that working software can be implemented in far less time and with far fewer programmers than using other technology. Also, being compact and terse, APL lends itself well to larger scale software development as complexity arising from a large number of lines of code can be dramatically reduced. APL is often found where time-to-market is important, such as with trading systems.

Mostly due to its infix notation and its emphasis on interaction with the computer, APL can be an ideal environment for the rapid deployment of interactive Domain Specific Languages. Despite the presence of non-standard characters in the APL character set, it is possible for a user of a domain-specific language implemented in APL to write simple programs (or scripts) consisting solely of words, numbers, and familiar punctuation. Until as late as the mid-1980s, APL timesharing vendors offered applications delivered in the form of domain specific languages. On the I. P. Sharp timesharing system, a workspace called 39 MAGIC offered access to financial and airline data plus sophisticated (for the time) graphing and reporting, in the form of a domain specific language. Another example would be the GRAPHPAK workspace supplied with IBM's APL2, a demonstration version of both APL2 and GRAPHPAK can be downloaded for Windows.

Arguably, APL was designed with computer interaction, education, and mathematics, not necessarily in that order, in mind. Further, APL was designed to empower a user, a casual, non-professional programmer, perhaps an economist, actuary, or engineer, to get results from a computer. In a sense, it was the opposite of the stated purpose of Tom Lehrer's song "New Math", where the idea is both to get the right answer and to understanding what you are doing.

Iverson later designed a successor to APL called J which uses ASCII with digraphs instead of special symbols. Few other programming languages offer the comprehensive array functionality of APL. A+ is an open source programming language with many features similar if not identical to APL. The K and Q languages from Kx Systems also offer a similar language philosophy. However, the roots of the A+, J, K, and Q languages all stem from APL.

Examples

The following expression sorts a word list stored in matrix X according to word length:

File:APL Example 1.gif

The following function "life", written in Dyalog APL, takes a boolean matrix and calculates the new generation according to Conway's Game of Life:

File:LifeInApl.gif

In the following example, also Dyalog, the first line assigns some HTML code to a variable "txt" and then uses an APL expression to remove all the HTML tags, returning the text only as shown in the last line.

The following expression finds all prime numbers from 1 to R (presuming an index origin of 1). In both time and space, the calculation is O(R2).

(∼R∈R∘.×R)/R←1↓⍳R

From right to left, this means:

  1. ⍳R creates a vector containing integers from 1 to R (if R = 6 at the beginning of the program, ⍳R is 1 2 3 4 5 6)
  2. Drop first element of this vector (↓ function), i.e. 1. So 1↓⍳R is 2 3 4 5 6
  3. Set R to the vector (←, assignment primitive)
  4. Generate outer product of R multiplied by R, i.e. a matrix which is the multiplication table of R by R (∘.× function)
  5. Build a vector the same length as R with 1 in each place where the corresponding number in R is in the outer product matrix (∈, set inclusion function), i.e. 0 0 1 0 1
  6. Logically negate the values in the vector (change zeros to ones and ones to zeros) (∼, negation function), i.e. 1 1 0 1 0
  7. Select the items in R for which the corresponding element is 1 (/ function), i.e. 2 3 5

Calculation

APL was unique in the speed with which it could perform complex matrix operations. For example, a very large matrix multiplication would take only a few seconds on a machine which was much less powerful than those today. There were some technical and other economic reasons for this advantage:

  • Commercial interpreters delivered highly-tuned linear algebra library routines.
  • Very low interpretive overhead was incurred per-array—not per-element.
  • APL response time compared favorably to the runtimes of early optimizing compilers.
  • IBM provided microcode assist for APL on a number of IBM/370 mainframes.

A widely cited paper "The APL Machine" perpetuated the myth that APL made pervasive use of lazy evaluation where calculations would not actually be performed until the results were needed and then only those calculations strictly required. Although this technique was used by just a few implementations, it embodies the language's best survival mechanism: not specifying the order of scalar operations. Even as eventually standardized by X3J10, APL is so highly data-parallel, it gives language implementors immense freedom to schedule operations as efficiently as possible. As computer innovations such as cache memory, and SIMD execution became commercially available, APL programs ported with little extra effort spent re-optimizing low-level details.

Interpreters

Today, most APL language activity takes place under the Microsoft Windows operating system, with some activity under Linux, Unix, and Mac OS. Comparatively little APL activity takes place today on mainframe computers.

APLNow (formerly APL2000) offers an advanced APL interpreter which operates under Linux, Unix, and Windows. It supports Windows automation, supports calls to operating system and user defined DLLs, has an advanced APL File System, and represents the current level of APL language development. APL2000's product is an advanced continuation of STSC's successful APL*Plus/PC and APL*Plus/386 product line.

Dyalog APL is an advanced APL interpreter which operates under Linux, Unix, and Windows. Dyalog has aggressive extensions to the APL language which include new object oriented features, numerous language enhancements, plus a consistent namespace model used for both its Microsoft Automation interface, as well as native namespaces.

IBM offers a version of IBM APL2 for Linux and Windows systems. This product is a continuation of APL2 offered for IBM mainframes. IBM APL2 was arguably the most influential APL system, which provided a solid implementation standard for the next set of extensions to the language, focusing on nested arrays.

MicroAPL Limited offers APLX, a full-featured 64 bit interpreter for Linux, Windows, and Apple Mac OS systems.

Soliton Associates offers the SAX interpreter (Sharp APL for Unix) for Unix and Linux systems, which is a further development of I. P. Sharp Associates' Sharp APL product. Unlike most other APL interpreters, Kenneth E. Iverson had some influence in the way nested arrays were implemented in Sharp APL and SAX. Nearly all other APL implementations followed the course set by IBM with APL2, thus some important details in Sharp APL differ from other implementations.

Unlike most other computer languages, APL gained its foothold on mainframe timesharing systems in the 1960s through the 1980s and later, when suitably performing hardware was finally available starting in the early to mid-1980s, many users migrated their applications to the personal computer environment. This is also one of APL's survival mechanisms, the ability to move from platform to platform. APL was truly portable.

The first microcomputer implementation of APL was on the MCM/70, an 8008-based processor, in 1973, two years ahead of the beginning of the rest of the microcomputer revolution. A Small APL for the Intel 8080 called EMPL was released in 1977, and Softronics APL, with most of the functions of full APL, for 8080-based CP/M systems was released in 1979. Vanguard APL was available for Z80 CP/M-based processors in the late 1970s. TCC released APL.68000 in the early 1980s for Motorola 68000-based processors, this system being the basis for MicroAPL Limited's APLX product. I. P. Sharp Associates released a version of their APL interpreter for the IBM PC and PC/370 - for the IBM PC, an emulator was written which facilitated reusing much of the IBM 370 mainframe code. Arguably, the best known APL interpreter for the IBM Personal Computer was STSC's APL*Plus/PC.

In the early 1980s, the Analogic Corporation developed The APL Machine, which was an array processing computer designed to be programmed only in APL. There were actually three processing units, the user's workstation, an IBM PC, where programs were entered and edited, a Motorola 6800 processor which ran the APL interpreter, and the Analogic array processor which executed the primitives. At the time of its introduction The APL Machine was likely the fastest APL system available. Although a technological success, The APL Machine was a marketing failure. The initial version supported a single process at a time. At the time the project was discontinued, the design had been completed to allow multiple users. As an aside, an unusual aspect of The APL Machine was that the library of workspaces was organized such that a single function or variable which was shared by many workspaces existed only once in the library. Several of the members of The APL Machine project had previously spent a number of years with Burroughs implementing APL\700.

IBM was responsible for the introduction of APL to the marketplace. Today, the APL2 product is available for IBM mainframes with CMS and TSO; and the APL2 Workstation edition (Windows, AIX, Linux, and Solaris). Earlier, the VSAPL program product enjoyed widespread usage with CMS, TSO, VSPC, and CICS users.

Prior to APL2 and VSAPL, early IBM APL interpreters for IBM 360 and IBM 370 hardware implemented their own multi-user management instead of relying on the host services, thus they were timesharing systems in their own right. First introduced in 1966, the APL\360 system was a multi-user interpreter . In 1973, IBM released APL.SV which was a continuation of the same product, but which offered shared variables as a means to access facilities outside of the APL system, such as operating system files.

APL was first available for the IBM 1130 as APL\1130.[1]

Sharp APL was available from I. P. Sharp Associates, first on a timesharing basis, and later as a program product. Sharp APL was an advanced APL implementation with many language extensions, such as packages (the ability to put one or more objects into a single variable), file system, nested arrays, and shared variables.

APL interpreters were available from other computer manufactures as well, notably Burroughs, CDC, Data General, DEC, Harris, Hewlett-Packard, Siemens, Xerox, and others.

At one stage, Microsoft Corporation planned to release a version of APL, but these plans never materialized.

An early 1978 publication of Rodnay Zaks from Sybex was A microprogrammed APL implementation ISBN 0895880059 which is the complete, total source listing for the microcode for a PDP / LSI-11 processor implementing the APL programming language. This may have been the substance of his PhD Thesis.

Compilation

APL programs are normally interpreted and less often compiled. In reality, most APL "compilers" translated source APL to a lower level language such as C, leaving the machine-specific details to the lower level compiler. Compilation of APL programs was a frequently discussed topic in conferences. Although some of the newer enhancements to the APL language such as nested arrays have rendered the language increasingly difficult to compile, the idea of APL compilation is still under development today.

In the past, compilation was regarded as a means to achieve Fortran-like execution speed, especially on mainframe computers. Today, execution speed is less critical, considering the numbers of computer languages implemented using virtual machines. Several APL compilers did achieve varying levels of success, though comparatively little of the development effort spent on APL over the years went to perfecting compilation.

No APL compiler brought to the market was ever capable of compiling APL programs without changes, often substantial, to their content. Often, variable declarations were needed, certain language features would need to be removed or avoided, or at the very least, the APL programs would need to be cleaned up in some way. Some features of the language, such as the execute function (an expression evaluator) and the various reflection and introspection functions from APL, such as the ability to return a function's text or to materialize a new function from text, are simply not practical to implement.

The APLNext VisualAPL system is a departure from a conventional APL system in that VisualAPL is a true .Net language which is fully inter-operable with other Microsoft .Net languages such as VB.Net and C#. VisualAPL is inherently object oriented and Unicode-based. While VisualAPL incorporates most of the features of legacy APL implementations, the VisualAPL language extends legacy APL to be .Net-compliant. VisualAPL is hosted in the standard Microsoft Visual Studio IDE and as such, invokes compilation in a manner identical to that of other .Net languages. By producing .Net common language runtime (CLR) code, it utilizes the Microsoft just-in-time compliler (JIT) to support 32-bit or 64-bit hardware. Substantial performance speed-ups over legacy APL have been reported, especially when (optional) strong-typing of function arguments is used.

An APL to C# translator is available from Causeway Graphical Systems. This product was designed to allow the APL code, translated to equivalent C#, to run completely outside of the APL environment. The Causeway compiler requires a run-time library of array functions. Some speedup, sometimes dramatic, is visible, but happens on account of the optimisations inherent in Microsoft's .Net framework.

A commercial compiler was brought to market by STSC in the mid 1980s as an add-on to IBM's VSAPL Program Product. Unlike more modern APL compilers, this product produced machine code which would execute only in the interpreter environment, it was not possible to eliminate the interpreter component. The compiler could compile many scalar and vector operations to machine code, but it would rely on the APL interpreter's services to perform some more advanced functions, rather than attempt to compile them. However, dramatic speedups did occur, especially for heavily iterative APL code.

Around the same time, the book An APL Compiler by Timothy Budd appeared in print. This book detailed the construction of an APL translator, written in C, which performed certain optimizations such as loop fusion specific to the needs of an array language. The source language was APL-like in that a few rules of the APL language were changed or relaxed to permit more efficient compilation. The translator would emit C code which then be compiled and run well outside of the APL workspace.

Terminology

APL makes a clear distinction between functions and operators. Functions take values (variables or constants or expressions) as arguments, and return values as results. Operators take functions as arguments, and return related, derived functions as results. For example the "sum" function is derived by applying the "reduction" operator to the "addition" function. Applying the same reduction operator to the "ceiling" function (which returns the larger of two values) creates a derived "maximum" function, which returns the largest of a group (vector) of values. In the J language, Iverson substituted the terms 'verb' and 'adverb' for 'function' and 'operator'.

APL also identifies those features built into the language, and represented by a symbol, or a fixed combination of symbols, as primitives. Most primitives are either functions or operators. Coding APL is largely a process of writing non-primitive functions and (in some versions of APL) operators. However a few primitives are considered to be neither functions nor operators, most noticeably assignment.

Character set

APL has always been criticized for its choice of a unique, non-standard character set. The observation that some who learn it usually become ardent adherents shows that there is some weight behind Iverson's idea that the notation used does make a difference. In the beginning, there were few terminal devices which could reproduce the APL character set — the most popular ones employing the IBM Selectric print mechanism along with a special APL type element. Over time, with the universal use of high-quality graphic display and printing devices, the APL character font problem has largely been eliminated; however, the problem of entering APL characters requires the use of input method editors or special keyboard mappings, which may frustrate beginners accustomed to other languages. With the popularization of the Unicode standard, which contains the APL character set, the problem of obtaining the required fonts seems poised to go away.

From a user's standpoint, the additional characters can give APL a special elegance and concision not possible in other languages, using symbols visually mnemonic of the functions they represent. Or it can lead to a ridiculous degree of complexity and unreadability, typically when the symbols are strung together into a single mass without any comments. Or it can be unreasonably difficult and time consuming to enter then later edit those APL statements.

APL symbols and keyboard layout

Note the mnemonics associating an APL character with a letter: question mark on Q, power on P, rho on R, base value on B, eNcode on N, modulus on M and so on. This makes it easier for an English-language speaker to type APL on a non-APL keyboard providing one has visual feedback on one's screen. Also, decals have been produced for attachment to standard keyboards, either on the front of the keys or on the top of them.

¨
1
¯
2
<
3

4
=
5

6
>
7

8

9

0
-
+
÷
×
?
Q

W
ɛ
E

R

T

Y

U
̾
I

O
*
P


A

S

D
_
F

G

H

J
'
K

L
(
[
)
]

Z

X

C

V

B

N
|
M
;
,
:
.
\
/

A more up to date keyboard diagram, applicable for APL2 and other modern implementations, is available: Union layout for windows.

All APL symbols are present in Unicode (although some APL products may not yet feature this):

' ( ) + , - . / : ; < = > ? [ ]
\ _ ¨ ¯ × ÷

Additional APL characters were available by overstriking one character over another. For example, the log symbol was formed by overstriking shift-P with shift-O. This complicated correcting mistakes and editing program lines. This may have ultimately been the reason for early APL programs to have a certain dense style - they were difficult to edit.

Later IBM terminals, notably the IBM 3270 display stations, had an alternate keyboard arrangement which is the basis for some of the modern APL keyboard layouts in use today. Better terminals, namely display devices instead of printers, encouraged the development of better full screen editors, which had a measurable improvement in productivity and program readability.

See also

Usage

APL has long had a small but fervent user base. It was and still is popular in financial and insurance applications, in simulations, and in mathematical applications, often where a solution in a standard language yields excessive complexity. APL has been used in a wide variety of contexts and for many and varied purposes. Interest in APL has steadily declined since the 1980s. This was partially due to the lack of a migration path from performant mainframe implementations to early low-cost personal computer alternatives and the availability of high-productivity end-user computing tools such as Microsoft Excel and Microsoft Access. These are appropriate platforms for what may have been mainframe APL applications in the 1970s and 1980s. Many APL users migrated to the J programming languages, which offers advanced features. Lastly, the decline was also due in part to the growth of MATLAB, an interactive array-oriented platform for scientific computing, which is in many ways similar to APL, allows APL-style interactive development, and uses standard ASCII.

Standardization

APL has been standardized by the ANSI working group X3J10 and ISO/IEC Joint Technical Committee 1 Subcommittee 22 Working Group 3. The Core APL language is specified in ISO 8485:1989, and the Extended APL language is specified in ISO/IEC 13751:2001.

Quotes

  • "APL, in which you can write a program to simulate shuffling a deck of cards and then dealing them out to several players in four characters, none of which appear on a standard keyboard." David Given
It should be noted that the quote above is not literally true. All APL algorithms that shuffle a deck of cards involve the expression 52?52 to generate the numbers from 1 through 52 in random order. That's more than four characters right there, and the question mark symbol does appear on standard keyboards.
  • "APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums." Edsger Dijkstra, 1968
It should also be noted that Dijkstra was speaking at a dinner party, and that Dijkstra was a leading proponent of "structured programming", a construct which did not exist in APL at the time. One of the basic principles of structured programming was that GOTOs were considered harmful and should be avoided; APL, on the other hand, had no control structures except the GOTO in the early years.
Rho, rho, rho of X
Always equals 1.
Rho is dimension; rho rho, rank.
APL is fun!
  • "This way of doing business was so productive that it spread like wildfire. By the time the practical people found out what had happened; APL was so important a part of how IBM ran its business that it could not possibly be uprooted. The wild-eyed researchers had produced a moneymaker." Micheal S. Montalbano 1982 (see A Personal History of APL)
  • The following amusing rhyme has been circulated as part of the fortune program in numerous UNIX installations.
'Tis the dream of each programmer
Before his life is done,
To write three lines of APL
And make the damn thing run.

See also

References

  1. ^ Larry Breed (August 2006). "How We Got To APL\1130". Vector (British APL Association). 22 (3). ISSN 0955-1433.

Vendors and Organizations:

Related Dialects and Languages:

  • J is Iverson's newer array language which uses the standard ASCII font
  • A+ is a programming language with many features similar to APL and an open source implementation
  • kdb+ for high-performance relational databases
  • NumPy is a Python package for array and scientific programming.
  • Simmunity is a compiled programming language based on APL designed for Internet collaborative applications

Compilers:

History:

Applications:

Personal Views: