I-APL: Under the bonnet

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 48

I-APL is an APL interpreter specifically designed to run on small machines which are suitable for schools. Paul Chapman wrote I-APL and gave a very interesting talk to the British APL Association about its development. He had limited finances to work with, and the work was completed in about 5 months

Paul began by describing his objectives:

Objectives¶

• Standard
• Small
• Portable
• International
• Educational

Because of the tight restrictions imposed on him, certain sacrifices had to be made:

Sacrifices¶

• Speed
• Workspace Efficiency
• Special Cases
• Bells and Whistles
• Commercial Features

Paul then went on to describe the design policy he adopted.

Principles of Design¶

• Simple Data Structures
  ⇨ Low Utility Overhead
• Algorithm Factorisation
  ⇨ Code Size Reduction
• Parity with Standard
  ⇨ Reduced Debugging Problems
• FORTH-style Implementation Language
  ⇨ Portability

He then outlined the data structures required ….

Data Structures¶

Primitive:   Descriptor
             Array
             Stack
             List
             Literal

Derived:     Defined function (list)
             Line (list)
             State Indicator (stack)
             Context (list)
             Evaluation Stack (stack)
             Index Lists [;] (stack/list)
             Hash Table (list)
             etc

…. and went on to describe them in more detail.

Descriptor¶

Allocated Space:
   0   Link to Next Descriptor
   2   Address of Object
   4   Reference Count
   6   Type

Available Space:
   0   Link to Next Descriptor
   2   Address of Object
   4   Zero
   6   Link to Next Unused Descriptor

• Descriptor space cannot be reclaimed
• Descriptor address (handle) is constant throughout

Symbol¶

   0   Handle of next symbol in chain
   2   Handle of previous symbol in chain
   4   Handle of current value
   6   Number of localisations
   8   Handle of global value
  10   Length of name
  12   Name
   :
   :
   :

• Global value is available for )ERASE and )COPY
• Symbols are grouped into chains by first letter
• System functions and variables are in symbol table
• Symbol Table space can be reclaimed

Array¶

   0   Type: n or c
   2   Element size: 0, 1, 2 or 5
   3   Rank: 0 to 7
   4   Number of elements: 0 to 32766
   6   Shape
   :   :
   :   Data
   :   :

Function¶

   0   Handle of local name list
   2   Handle of function header token list
   4   Handle of line [1] token list
   :   :
   :   :
   :   :

Token list

• Each item is either a token or a character
• Tokens can be names or literals
• Characters can be primitives or delimiters

Stack¶

Root

   0   Handle of first (top) clump
   2   Offset of first free word in first clump
   4   Stack size

Clump

   0   Handle of next clump (0 for none)
   2   Bottom item in this clump
   :   :
   :   Top item in this clump

Stack: Utility Functions¶

stack_alloc   Allocate a stack
stack_push    Push item on stack
stack_pop     Pop item from stack
stack_top     Get top item of stack
stack_size    Get number of items on stack
stack_index   Get item of stack by index

Uses

• Lexical analysis
• Evaluation
• State indicator
• Building index list [;]

Order¶

• Used to access elements of an array
• Data structure drives the equivalent of nested loops

Header

   0    Current index into ravel of array
   2    Array handle
   4    Offset of first element of array
   6    Array element size
   7    Desired element size for fetch
   8    Initial index
  10    Number of elements in array

For each nested loop

   n    Adjustment to current index
   n+2  Count

Order: Example: Transpose of a 3x5 matrix¶

Indices of values:
    0  1  2  3  4
    5  6  7  8  9
   10 11 12 13 14

Order of values in result:
    0 5 10 1 6 11 2 7 12 3 8 13 4 9 14

The loop parameters to transpose the matrix:

     5   Adjustment
     3   Count
     3   Initial count
   ¯14   Adjustment
     5   Count

Order: Single Algorithm for Structural Primitives¶

• Reshape
• Reverse
• Rotate
• Transpose
• Take
• Drop
• Replicate
• Expand
• Join

And many others:

• Encode
• Decode
• Matrix Divide
• Reduce
• Scan

Recursion¶

• Standard defines operation of APL recursively
• I-APL implementation language does not allow recursion
• No CPU works recursively
• Any CPU can run recursive programs
• I-APL Uses co-routines to implement recursion

He concluded the talk by pointing out some new ideas which had been incorporated into I-APL.

Innovations¶

Fractional axis replicate/expand

      2/[0.5]'ABCD'
ABCD
ABCD
      1/[1.5]1 2 3
1
2
3
      1 0 1\[0.5]5 4 3 2 1
5 4 3 2 1
0 0 0 0 0
5 4 3 2 1

Direct Definition

      IF: ω/α
      LEV: α
      ASK: (⍴ω)↓⍞ LEV ⍞←ω←,ω

… and some extra features.

Other Extensions¶

• ⎕PW
• ⎕WA
• ⎕HC for hard copy of session
• ⎕TX for raw output to screen/printer
• ⎕MC for machine code interface
• ⎕ID to identify environment

Finally, he looked back at his initial objectives to show how they had been acheived.

Objectives Achieved¶

• Standard: First fully ISO conforming APL
• Small: Just over 25K
• Portable: Library workspaces can be exchanged
• International: Interpreter messages are defined by porter
• Educational: Direct definition, Stop and Trace

At the end of his talk, a member of the audience stood up to say that writing an ISO-standard APL interpreter in less than 25K was brilliant. Paul Chapman agreed!