We'll implement Knuth Shuffle (also known as Fisher/Yates shuffle) from Rosetta Code. This produces a random permutation of a vector.
Dyadic ?
, or deal, looks an ideal candidate here. Recall from the previous part that x ? y
means take x
unique items from the population 1 ... y
. This means that x ? x
will give a random permutation of all the values 1 ... x
, which we can use as vector indices.
What else will we need?
⍴
or $RH
).[
... ]
.Putting this together:


Let's try to run this and see if it works:
SHUFFLE1 11 22 33
11 33 22
SHUFFLE1 11 22 33
22 11 33
SHUFFLE1 11 22
22 11
SHUFFLE1 11 22
22 11
SHUFFLE1 11 22
11 22
SHUFFLE1 ,11
11
In the last example we need to use ravel (,
) to change the input scalar 11 into a vector of length 1 containing 11.
This function will also work on strings, which are treated as vectors of characters:
SHUFFLE1 'FACE'
FCEA
SHUFFLE1 'FACE'
ACFE
What if we wanted to implement the algorithm itself, rather then just use deal? Let's start by looking at the pseudocode given on Rosetta Code. For a vector with indices 0  last:
for i from last downto 1 do:
let j = random integer in range 0 ≤ j ≤ i
swap items[i] with items[j]
What language features will we need from APL?
i
and j
mean we will need to declare local variables in our function.→
or $GO
) testing whether we have reached the start of the vector or not.?
. v[x,y] = v[y,x]
to swap elements at x
and y
.Here's the complete program:


Line 2 is tricky: it branches to lines in the vector in round brackets based on the expression in the square brackets. If I
is less than or equal to 1 then the expression evaluates to 2, so control jumps to line 7 (S ← V
) where the output value is assigned and the function ends. Otherwise it will continue to line 3 and swap an element.
Running this on some test cases shows this works as expected.
Ideally we'd like to use idiomatic APL and avoid a loop altogether. Modern APLs have control structures like repeat
, but I can't see an easy way to do this in APL\360  if you can, please add a comment!
Let's do a test by running each of these implementations 60,000 times with the same input (1 2 3). We can use code like this:


On my system, SHUFFLE1 takes 7.3s to run and SHUFFLE2 24.6s, which we'd expect as SHUFFLE1 uses the system provided deal function.
I also ran a quick check for randomness by printing the results to a file and seeing how many times each permutation occurred. Over 60,000 runs we'd expect each permutation to appear around 10,000 times; SHUFFLE1 was within 0.5% of that and SHUFFLE2 0.6%.
Internally, ?
uses a pseudorandom number generator so true randomness cannot be achieved. Also with a 32 bit word, the number of possible states is 2^32, which limits the number of combinations that can occur. For example, if we wanted to shuffle a deck of 52 cards there are 52! combinations, much more than 2^32.
APL's use of a large number of symbols is what first strikes you when learning the language. I found by going through the tutorials that you start picking them up quite quickly, and it's not hard to write simple programs. However, reading other people's programs can be difficult, given its compact form and righttoleft structure; I imagine that understanding a large APL code base would take some time.
The language itself is unique and even beautiful; some times I feel like I'm writing mathematics rather than coding. If you have the opportunity then I'd recommend trying it out.
The transliterations needed on emulated MTS add another level of difficulty and unless you want to experience the historical aspects of running APL like this I'd recommend learning APL with a modern implementation that can use APL symbols directly. There are several commercial implementations that run on modern hardware, for example Dynalog. The GNU project also has GNU APL. Several languages have been derived from APL, including K, used for financial analysis.
Full source code for this program can be found on github.
Jeff Atwood's Coding Horror blog has a good post on shuffling with a followup on the dangers of misimplementing the algorithm.
Eugene McDonnell wrote an interesting article on How the Roll Function Works in APL\360 and other APLs, giving insight on its implementation.
To see some amazing APL oneliners in action, check out Sixteen APL AmuseBouches.
]]>As the emulated system dows not support entry and display of APL symbols, we will have to use transliterations, eg * for the multiply symbol ×. The code samples below show the original version on the left and the transliterated version on the right. An appendix at the end of this post lists all symbols used and their transliterations.
Similar to the last language we looked at, PIL, when APL starts up it allows you to enter expressions and get results immediately. The prompt is eight leading spaces and results are printed in the first column.


We can enter simple arithmetic functions and get results as expected.


These are all dyadic functions, ie they take a left and right parameter. Many APL functions also have monadic versions which take only one parameter on the right. Let's look at how the four basic arithmetic functions work:


Plus and minus work as expected; note that negative numbers are displayed with a leading underscore to represent the −
symbol. Multiply and divide give more interesting results. Multiply gives the signum of its parameter: 1 if negative, 0 if zero or 1 if positive. Divide gives the reciprocal of its parameter.
The modulus operator (∣
or $
) works the opposite way around from what you may be used to from other languages, so 10 ∣ 12
is 2
.
Order of execution is strictly right to left; using brackets allows you to specify what operators works on what parameters


Values can be assigned to a variable with ←
(=
). Variable names need to start with a letter. Underlined letters can also be used; these are transliterated to lower case letters.


As well as single numbers, you can have vectors of numbers. These are entered by separating the elements with spaces. Operators work on vectors as well.


If the dimension of the parameters differ, APL will extend the shorter vector as appropriate  so 1 2 3 × 2
will give 2 4 6
.
Strings are introduced using quotes; internally APL treats them as vectors of characters.
Booleans are represented as numbers with a value of 0 or 1. These are returned by comparison functions like equal, greater or equal (=
, ≥
or =
, $GE
). Logical operators like and (∧
or &
) can operate on these.


The rho function (⍴
or $,
) gives the dimension of a vector when used moadically. Used dyadically, it can create a matrix from a vector on its right side by giving the shape on the left side.


Comma (,
) used dyadically is called catenate, and adds to a vector.


Monadic comma (known as ravel) turns a scalar into a vector


A vector of length 1 looks like a scalar when displayed. We can tell them apart with double rho, which gives the rank.


Iota (⍳
, which can be transliterated as any of $IO
, $IN
or $.
) creates a sequence when used monadically and gives index positions when used dyadically. Square brackets can be used to extract elements based on index positions.


There are over 50 APL functions so it would be difficult to go through them all here, but let's take a brief tour to show some of them in action.
Ceiling (⌈
or $CE
, $MA
) and floor (⌊
or $FL
, $MI
) rounds up/down when used monadically and finds the max/min when used dyadically


Factorial (!
) means take m of n when used dyadically:


Rotation (⌽
, $RO
):


Take (↑
, $TA
) and drop (↓
, $DR
):


Grade up (⍋
or $GU
) gives sorted indices, with grade down doing sort in reversed order.


?
used monadically is known as roll, producing a random number between 1 and the right hand argument. Used dyadically, it is known as deal: x ? y
means take x
unique items at random from the population 1 .. y
.


Decode (⊥
or $DE
, $BA
) converts bases. Encode (⊤
or $EN
, $RP
) goes the other way. Below we show 2 hours 30 minutes decoded into number of minutes and then reencoded.


An operator in APL differs from a function in that it takes a function on its left hand side. One example is reduction (/
or %
): in the example below we give it the plus function which will sum up the elements on the right


Let's try it with 
:


Why does it return 2? This is due to the right to left associativity of APL: we coild expand this as 1  (2  (3  4)).
You can define your own functions with del (∇
or "
), Starting a line with del creates a function: the rest of the line specifies the variable that will contain the return value, the function name and its parameters. On subsequent lines, APL will prompt you for the next statement with the line number. A del on its own will close the function. A simple example for a monadic function called INCR
that increments its right hand side:


Dyadic functions are created by giving variables before and after the function names. For example, the hypotenuse function:


Apart from the parameters, any variables used in defined functions will be global by default. To set up local variables, add a semicolon and the variable names on the function definition line.


Flow control in a function can be introduced with the branch function (→
or $GO
), which takes the line number to branch to on the right hand side. Branching to line number 0 is equivalent to returning from the function: we saw the in part 1 of this series with the line


which would branch to line 2 if N
was less than 5, else return from
the function.
After defining a function, you can list its contents by entering del, the function name, quad (⎕
or #
) in square brackets then del, all on the same line.


You can edit or append lines in a function by replacing quad in the above example with a line number. Line numbers can include decimal points, eg to insert a line between current lines 1 and 2 you'd do ∇FOO[1.5]∇
To delete an entire function you need to use the erase system command with the function name, eg )ERASE FOO
.
System commands, starting with )
, manipulate the APL environment. )OFF
will quit APL, )FNS
and )VARS
will list currently defined functions and variables respectively.
To manage sets of functions and variables, APL has the concept of workspaces. The current set can be saved to a named workspace, eg FOO
by the user with the command )SAVE FOO
and then loaded later with )LOAD FOO
. APL will also automatically save the current set to the workspace CONTINUE
on exit and load it again at startup. To wipe out the current running set, use )CLEAR
; to delete from disk user )DROP ws
.
There are also system workspaces, organised into libraries identified by numbers. Use )LIB n
to see the workspaces in library n
and then )LOAD n ws
to load a names workspace. For example, let's look at the workspace APLCOURSE
in library 1. This defines a function DESCRIBE
which explains its contents.
)LIB 1
ADVANCEDE
APLCOURSE
CLASS
NEWS
PLOTFORMA
TYPEDRILL
WSFNS
EIGENVALU
BRFNS
)LOAD 1 APLCOURSE
SAVED 16.13.05 08%08%68
)FNS
B1X CHECK DESCRIBE DIM DRILL DYAD1 DYAD2 EASY
EASYDRILL FORM FUNDRILL GET INPUT QUES RANDOM
REDSCAPATCH REPP TEACH
DESCRIBE
THE MAIN FUNCTIONS IN THIS LIBRARY WORKSPACE ARE:
TEACH
EASYDRILL
ALL OTHER FUNCTIONS ARE SUBFUNCTIONS AND ARE NOT
SELFCONTAINED.
SYNTAX DESCRIPTION
______ ___________
TEACH AN EXERCISE IN APL FUNCTIONS USING SCALARS
AND VECTORS. THE FUNCTION PRINTS OUT THE
CHOICES AND OPTIONS AVAILABLE. EXAMPLES
ARE SELECTED AT RANDOM WITH A RANDOM
STARTING POINT.
EASYDRILL THIS IS THE SAME AS TEACH EXCEPT THAT THE
PROBLEMS SELECTED ARE GENERALLY SIMPLER IN
STRUCTURE. PROBLEMS INVOLVING VECTORS OF
LENGTH ZERO OR ONE ARE EXCLUDED.
Workspace 6 contains a resource management game called KINGDOM.
In the next post we'll look at implementing a real program in APL.
This post has only scratched the surface of APL. See the Further Information section in the APL introduction post for more resources to learn about APL.
This is a copy of the table UM Computing Center Memo 382, excluding characters that are marked as not in use.
Meaning  APL Symbol  Transliteration 

And  ∧  & 
Branch  →  $GO $> 
Ceiling  ⌈  $CE $MA 
Circular functions  ○  $$ $CI $PI 
Comma  ,  , 
Comment / lamp  ⍝  $* $CO 
Compression  /  % 
Compression axis 1  ⌿  $C1 
Deal / random  ?  ? 
Decode  ⊥  $DE $BA 
Del  ∇  " 
Delta  Δ  $" 
Delta underlined  ⍙  $U" 
Divide  ÷  / 
Drop  ↓  $DR $DO 
Encode  ⊤  $EN $RP 
Equal  =  $EQ 
Expansion  \  $% 
Expansion axis 1  ⍀  $X1 
Exponentiation  ⋆  @ 
Factorial  !  ! $FA $BC 
Floor  ⌊  $FL $MI 
Grade down  ⍒  $GD 
Grade up  ⍋  $GU 
Greater or equal  ≥  $GE 
Greater than  >  $GT 
Ibeam  ⌶  $IB $SY 
Iota  ⍳  $IO $IN $. 
Less or equal  ≤  $LE 
Less than  <  $LT 
Locked function  ⍫  $L" 
Logarithm  ⍟  $@ $LO $LN 
Membership  ∈  $EP $ME 
Minus  −   
Modulus  ∣   $MO 
Multiply  ×  * 
Nand  ⍲  $N& 
Negation / overbar  −  _ $ 
Nor  ⍱  $N $WR 
Not  ~  $NO 
Not equal  ≠  $NE 
Null  ∘  $: 
Or  ∨   $OR 
Period  .  . 
Plus  +  + 
Quad  ⎕  # 
Quadquote  ⍞  $# 
Quote  '  ' 
Random  ?  ? 
Rho / dimension  ⍴  $, $RH $DI 
Rotation  ⌽  $RO $RV 
Rotation axis 1  ⊖  $R1 
Semicolon  ;  ; 
Specification  ←  = 
Take  ↑  $TA $UP 
Transposition  ⍉  $TR 
Underlined letters  A  Z  a  z _A  _Z 
The concepts behind APL came from work done by Kenneth E. Iverson at Harvard in the late 1950s. He wrote the book A Programming Language from which APL got its name. He moved to IBM in the early 1960s and helped produce the first working version of the language. IBM distributed versions of APL in the 1960s and 1970s, during which time the language was refined into APL2. Implementations were made for other architectures, including microcomputers in the 1980s.
APL is unique for its use of special symbols for functions and the ability to operate on multidimensional arrays. Put together, this allows a small amount of code to do a large amount of work. An example (from Wikipedia to compute the prime numbers from 1 to R:
(~R∊R∘.×R)/R←1↓ιR
The version of APL on MTS is based on APL\360, developed at IBM in the late 1960s. This was adapted to use the local MTS file system and devices, and portions for multiuser support were removed as they were not needed on MTS. Later versions of IBM APL did run on MTS but are not available on the D6 distribution due to copyright reasons.
APL symbols were supported using teletypewriters with a custom keyboard layout and typeballs that could display these symbols on paper.
Not all users would have this special teletypwriter, so APL supports the standard keyboard and printer character set using transliterations for symbols. For example, the divide operator ÷
is replaced with /
and the ceiling operator ⌈
, which finds the maximum of its arguments, is replaced with either $MA
or $CE
.
The hardware used by MTS for APL is not supported on Hercules so we will need to use these transliterations when running MTS under emulation.
Unlike other languages seen so far, we do need to set up APL before using it by installing it from the D5 tapes. The below method was adapted from work done by user halfmeg on the H390MTS list.
Start with a regular D6.0 setup as described in this guide. Ensure that MTS is not running before following these steps.
Get a copy of the D5 tapes from Bitsavers and extract into a temporary directory.
Locate the files d5.0t1.aws
and d5.0t2.aws
under the extraction directory and copy these to the Tapes
directory under your MTS install
Edit your hercules.cnf
and add these lines. These tape devices are unused in the stock D6.0 install; if you have already assigned these for your own use then change the device names here and in the instructions below.
# Add D5 tapes needed to restore APL
018B 3420 Tapes/d5.0t1.aws ro # T90B, D5.0T1
018C 3420 Tapes/d5.0t2.aws ro # T90C, D5.0T2
The batch instructions to restore APL from these disks is available as a card deck from my github repo on MTS languages. Download that file and copy it to Units/RDR1.txt
under your Hercules install, replacing the existing file. Note that the whitespace in the first line is important, so clone the git repo or download the file as raw text.
Start up MTS as normal, including HASP. When it is running, type devinit c
from the Hercules console to load the card deck. You should see the below printed on the MTS console if this worked.
00051 MTS **** Remove tape from T90B (6250 BPI)
00051 MTS **** Remove tape from T90C (6250 BPI)
The output from the batch job can be found on the printer in Hercules file Units/PTR2.txt
. Examine it for any errors; you can ignore lines like You restored files saved before FEB. 22, 1988
. You should see that job extracted files from the tape and set permissions appropriately.
Finally, test that it works by logging into a normal user account (eg ST01) and running
$run *APL,par=sp,noball
The APL start up message should appear. Type )LIB 1
and you should see this listing of library files:
ADVANCEDE
APLCOURSE
CLASS
NEWS
PLOTFORMA
TYPEDRILL
WSFNS
EIGENVALU
BRFNS
Type )OFF
to exit APL.
When you next shutdown MTS, you can comment out the two D5.0 tapes in hercules.cnf
to free up these devices for future use.
*APL
*APL
is an interactive environment where you can enter expressions and program lines. To start APL, run *APL
with the parameters sp
(to print spaces after each operator) and noball
(to indicate we are not using the special APL typeball.
APL prompts with six leading spaces. You can enter expressions and get results back immediately, aligned in column 1.
System commands start with )
. )SOURCE
will read lines from a given text file and execute them. )CONTINUE
will save a copy of the current workspace to a binary file which will automatically be loaded next time you start APL. )OFF
will exit APL.
As an example, here's a simple program to print 'Hello, world!' five times. This uses a simple loop  there's probably a more concise way to do this.
First, create a file called hello.apl
containing the following lines:
"HELLO
N=1
'Hello, world!'
N=N+1
$GO 2 * N $LE 5
"
Then start APL and load the text file:
# $run *apl par=sp,noball
# Execution begins 16:30:56
SAVED 16.30.28 05%27%17
)SOURCE HELLO.APL
After you enter the )SOURCE
command APL will read the file but will not prompt you it has completed. Press the ATTN
key to interrupt APL and return control to you. You can then enter HELLO
to run the loaded program:
HELLO
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
)OFF
16.31.16 05%27%17 CONTINUE
16.31.16 05%27%17
CONNECTED 0.00.19
CPU TIME 0.00.00
# Execution terminated 16:31:15 T=0.034
In the next post we'll look at the APL language in more detail.
IBM's APL\360 Primer is a great first read as it introduces the APL\360 system and APL language in a tutorial form. The APL\360 User's Manual can then be consulted for more indepth information.
A classic introduction to APL is "APL 360: An Interactive Approach" by Gillman and Rose. A copy can be found at the Software Preservation Group of the Computer History Museum.
UM Computing Center Memo 382 is a guide to the implementation of APL\360 on MTS. I recommend reading the printed copy of this memo from the above source as it includes the hand written APL symbols missing on the source copy.
]]>