An APL to C++ Translator
Vector 20:4, page 106
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 106
Abstract¶
What’s the hardest part about writing an APL Compiler? Is it the parsing of the language? No. APL syntax is relatively simple and is easy to parse. Is it the understanding of the intended operations? Not really, APL operations are high level and well understood. The real difficulty is that the target languages, typically C or C++, are so low level. The basic operations of APL do not exist in the target languages.
SmartArrays is a class library for C++ (and other languages) that provides a full set of APL-like array operations. This paper describes how C++ enhanced by SmartArrays can be a target for APL translation.
Introduction¶
There have been many efforts to write translators that convert APL2 to a compiled language. This writer managed an APL Compiler effort at IBM Yorktown for a time. SmartArrays provides the basic array operations and data of APL to the compiled languages easing the task of translating APL to these languages.
What is SmartArrays?¶
SmartArrays, from the programmer’s point of view, is a class library that can be used from C++, C#, and Java to provide to these languages APL-like multidimensional nested arrays and the functions that operate on them. The primary array object is called an ‘SmArray’ SmartArrays methods operate on SmArrays and return an SmArray as a result just like APL operations. For example, if you wanted to write in C++ some code that did this APL2 operation:
You could write:
Virtually all of the APL primitive functions and operators that are not spelled with a Quad in their name are available as methods in SmartArrays. There are also many additional array methods in SmartArrays some of which implement idiomatic expressions (like rank() and unique() ) while others are functions not available as primitives in APL (like XML, statistical, and sparse cube methods). These additional methods are not produced by the translator but might be used when fine tuning the program produced by the translator.
What is the SmartArrays APL translator?¶
The SmartArrays APL translator is an APL program that converts APL functions to C++ programs. It can be applied to a single APL function or to the main function of an application in which case it will dynamically determine what sub-functions are used and translate them also.
You translate an entire workspace of functions with a statement like the following where “MAIN” is the name of the main program of the application:
You can also translate a single defined function like this:
You would not normally translate a single line of APL except when experimenting with the translator to see what it does with various expressions. You’ll see many examples of this in this paper as a way to present various examples.
What can the SmartArrays translator translate?¶
Virtually all of the APL primitive functions and operators that are not spelled with a Quad in their name can be translated. In addition, Quad for output and Quad IO for origin control are translated.
What cannot be translated?¶
The SmartArrays APL translator is designed to be used for translating algorithms involving array computing. It would not normally be used with code that implements a user interface. It would not normally be used for code that manages files. (Although SmartArrays does contain the ability to treat a file as an array.) In general, system functions and system variables cannot be translated. The APL ‘execute’ function and defined operators cannot be translated. Operators on defined functions are not supported. Complex numbers and functions on complex numbers cannot be translated. Namespaces are not supported. Support for Global variables is limited.
APL does branching by using line numbers with labels as named constants as a syntactic helper for defining line numbers. The host languages for SmartArrays and the translator treat labels as names not numbers. Therefore, the translator must be able to determine the names of labels being selected and convert expressions to C++ using these names. Therefore, not all forms of branching can be translated.
Some Simple Examples¶
Here is a sequence of scalar functions. Notice that because the C++ arithmetic operations are overloaded for arguments that are SmartArrays, the resulting C++ code is very similar to the APL expression:
Expressions that are not in the C++ vocabulary are translated using the normal object-method application syntax of C++:
Selective assignment expressions are translated using the SmartArrays “Into” methods:
Branching expressions are translated into C++ ‘goto’ statements:
Index Origin¶
The compiled languages do not have the concept of index origin and always use zero to indicate the first item of a collection. Thus, APL programs written to use zero-origin are easier to translate. To translate a function that uses one-origin, values that select items may need to be adjusted. This can be done automatically for constant expressions. Here are some examples of origin dependent statements in a one-origin workspace where the origin can be adjusted automatically:
⊃SmA_TranslateLine 'A←X[1]'
A = X[0];
⊃SmA_TranslateLine 'A←X[⍳3]'
A = X[SmArray::scalar(3).sequence()];
Here are some examples of origin dependent statements where the translator has to ask for help with origin dependency:
In the first case, the programmer would need to know how the variable ‘I’ was defined to determine if it should be adjusted or not. In the second case, the fact that the index is a subset of a generated interval, it does not need to be adjusted.
⊃SmA_TranslateLine 'A←X[I]'
Adjust 'I' for origin? (Y/N) y
A = X[I-1];
⊃SmA_TranslateLine 'A←X[I/⍳⍴X]'
Adjust 'I.replicate(X.shape().sequence())' for origin? (Y/N) n
A = X[I.replicate(X.shape().sequence())];
The first version of the translator does not do any function or statement analysis beyond a single primitive. Enhancements to the translator could increase the number of cases that can be automatically translated. Settings of local origin are detected and honoured.
Here is a the translation of a trivial function that modifies a local origin:
⊃SmA_TranslateFn'ORGTest'
[0] Z←ORGTest R;⎕IO
[1] ⎕IO←1
[2] Z←R[I]
Adjust 'I' for origin? (Y/N) y
[3]
[4] ⎕IO←0
[5] Z←R[I]
SmArray ORGTest (SmArray R){
try {
SmArray Z;
Z = R[I-1];
Z = R[I];
return Z;
} catch( SmException e ){
std::cout << "ORGTest(): " << e.toString() << std::endl;
throw;
}
return 0;
}
Since there is no information about the value of I, when the translator sees I being used as an index, it has to ask if it should be adjusted. However, the exact same line encountered after the origin is set to zero does not require any interaction. Notice how the two translations of the index expression differ.
Translator Directives¶
In an APL program, all data is an array be it a complicated multi-dimensional nested array or a simple scalar. By default, when you translate a program from APL to C++, all operations are converted to SmartArrays methods and all data is converted to SmArrays. Here’s an example of a program that might have been written before the addition of control structures in APL that uses a scalar integer to control a loop:
[0] Z←MAX CONTROL XS;I;⎕IO
[1] ⎕IO←0
[2] I←¯1
[3] L1:I←I+1
[4] XS[I]←XX[I]+REFIT PR[I]
[5] →(I<MAX)/L1
[6] Z←+/XS
By default when this is translated to C++, you get a program that computes entirely with SmartArrays methods applied to SmArrays:
SmArray CONTROL (SmArray MAX, SmArray XS){
try {
SmArray Z;
SmArray I;
I = SmArray::scalar(-1);
L1:
I = (I+1);
XS.indexInto((XX[I]+REFIT(PR[I])),I);
if ((I<MAX).getInt() )
goto L1;
Z = XS.reduceDescending(Sm::plus);
return Z;
} catch( SmException e ){
std::cout << "CONTROL(): " << e.toString() << std::endl;
throw;
}
return 0;
}
This is an inefficient way to loop in APL and it’s an inefficient way to loop in SmartArrays. If you were writing a SmartArrays program by hand, you would normally freely intermix SmartArrays data and data of the host language and you would use SmartArrays methods and native methods as appropriate.
The translator supports a directive that may be used to declare that a set of names in your program should be treated as scalar integers. This directive is added to your APL function as a comment. Here is the directive that is useful in the CONTROL function:
This directive can be anywhere in the program. Here is the program produced
SmArray CONTROL (long MAX, SmArray XS){
try {
SmArray Z;
long I;
// SmA ScalarInt I MAX
I = -1;
L1:
I = I+1;
XS.indexInto((XX[I]+REFIT(PR[I])),I);
if (I<MAX)
goto L1;
Z = XS.reduceDescending(Sm::plus);
return Z;
} catch( SmException e ){
std::cout << "CONTROL(): " << e.toString() << std::endl;
throw;
}
return 0;
}
Note that the looping is now done using scalar integer operations of the native language.
Conclusion¶
This paper describes Release 1 of the SmartArrays translator. It has already been used to convert significant algorithms into C++. Interestingly, the company that did these translations did not do it so they could move their program development from APL to C++ but rather so they could continue to use APL for their sophisticated and constantly fine-tuned algorithms but still deliver applications in C++.
Many of the restrictions present in this first release could be removed in future versions. This writer implemented idiom recognition in IBM APL2 so that common idioms execute with the performance of a single primitive. This kind of analysis could be added to the translator. More sophisticated tracking of expressions in a one-origin workspace could lead to more completely automatic origin adjustment.
True global variables could be implemented by wrapping the translation of an APL workspace in a C++ class definition.
Versions of the translator that target C# or Java could be produced (although this is largely already supported). Versions of the translator tailored to APL2000 or Dyalog APL could be produced (although, again, this is largely already supported). Namespaces could be supported.
The SmartArrays translator can be used by companies that need to move their development to a compiled language. It can also be used by companies that want to stay in an APL development environment but deliver applications in the compiled languages. For these companies, APL could be the design language for a whole new range of applications.