ALMS(ID:2891/alm008)

ALMS - ANALYTIC LANGUAGE MANIPULATION SYSTEM [ title ]

Frederick W. Blackwell
Space Technology Laboratories, Inc.
Redondo
Beach, California

ABSTRACT

 

ALMS is a system which
permits operations to be performed upon analytic language forms with relative
ease. It has been successfully applied to such tasks as the differentiation and
factoring of algebraic expressions and the analysis of simple English sentences.
Input consists of phrases to be transformed together with equivalences which
describe operations upon these phrases. The program converts these to binary
list structures, performs the matching and substitution described by the
equivalences, and transforms the results into familiar form for output. Programs
in ALMS are themselves
organized as binary list structures, and permit recursive subroutine hierarchies
and dynamic memory allocation.

 

MANIPULATION SYSTEM

Frederick W. Blackwell
Space Technology Laboratories, Inc.
Redondo
Beach. California

SUMMARY

ALMS is a system which
permits operations to be performed upon analytic statement forms with relative
ease. The language and programs within the language have been developed over the
past two years at STL as a company-sponsored research project.

ALMS is currently
implemented on the IBM 7090 computer. The generality of procedures in
ALMS has made possible
applications in diverse areas, including differentiation and factoring of
algebraic expressions and the analysis of simple English sentences.

ALMS is a type of
list-processing language; both the data and programs in ALMS are represented in binary
list-structured form. To gain an understanding of the methods of ALMS, let us look at a simple example of
symbolic differentiation. Consider the expression
(d)/(dx) (sin 2x)
This
is input to ALMB in almost exactly this form, namely,
d/dx (sin 2x).

Thus the source list which is our expression resembles a two-address machine
code. Unary operators such as SIN have no vaddress; this is indicated by the
symbol $. Implicit above is the existence of two more ALMS statements:


  
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    

Location	u- address	v-address	Operator
x	VAR	$	E
2	INT	$	E

These are the terminal points of the tree, and carry the operation code
E(element). This is not a true operation; the u- address serves to identify the
class to which the element belongs (such as "variable" or "integer").

Also present in ALMS'
memory is a large set of transformation rules, four of which are shown in figure
2. These are equivalences that describe replacements to be made whenever the
left-hand part of a rule is found on the source list. The rules have a binary
structure like that of the source statement. In the example, part of the
expression (figure 1, box 2) is found to be like the left-hand part of rule 1
(figure 2), and replacement by the right-hand part of rule 1 yields box 3 of
figure 1. ANY1, ANY2, etc. are considered to match with anything, and in this
particular match ANY1 takes on the value x and ANY2 stands for the expression
2*x. Next, the dotted part of box 3 (figure 1) is found to be like the left-hand
part of rule 2 (figure 2), and substitution of the right-hand part is again
made. Here I1 stands for any integer, and therefore matches with the integer 2.
Continuing in like manner, the application of rule 3 transforms box 4 into box
5, and the application of rule 4 transforms box 5 into box 6, the latter being
the final result. The answer is output in familiar phrase form.

The following program of AIMS statements, which begins at L0, carries out the
operations described above:


  
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    
  
    
    
    
    

Location	uaddress	v-address	Operator
L0	L1	L2	DG
L1	SOURCE	MATCH	FIND
L2	exit	L3	IFWK
L3	L4	L0	DG
L4	L5	L6	DG
L5	--	--	COPY
L6	--	--	ERASE

Control in an ALMS program
is not sequential; rather, a push-down list of addresses of statements to be
executed is maintained. The operator DG ("do-and-go") adds its v- address to
this list. For example, statement L3 above tells us to do statement L4 and then
go to statement L0; this causes the execution of L4 and the addition of L0 to
the push-down list. Likewise, this execution of L4 adds L6 to the list, pushing
down the L0 just added. The use of DG permits recursive subroutine handling
without difficulty. Statements having FIND, COPY, or ERASE as operators return
control to the address at the head of the push-down list after their execution.
FIND has two parameters: the list which is being processed and the match list
with which it is being compared. COPY causes a substitution resulting from a
FIND, and ERASE removes the replaced part of the source list. When a COPY is
executed, space for the substitution is taken from a general memory pool;
similarly, an ERASE returns space to this pool. IFWK ("if work to do") transfers
control to the v-address if FIND was successful and to the u- address if nothing
was found.

From these basic yet powerful operations (which are realized interpretively
in ALMS) , together with a few
others, it is possible to build complex programs. One would normally not have a
single match list as has been described, since it is wasteful to run through a
list of hundreds of rules in each FIND operation. Instead, for example, it could
easily be recognized that one was trying to find the derivative of some
function. This recognition would be rapidly done with a FIND, but would be
followed by an appropriate transfer of control rather than a COPY. A succeeding
FIND would then encompass processing only a short list of rules dealing
specifically with derivatives of functions. Using such pattern recognition, an
ALMS program is built up which
in some ways may resemble the procedure a human uses in solving problems in
elementary calculus. An interesting part of the ALMS project has been deciding upon a good order in
which to attempt to apply rules, and in the case of algebra, also deciding just
what rules were necessary or useful.

ALMS has been applied to
other mathematical operations, including algebraic substitution and collection
of terms, and power series manipulations. Because algebraic expressions are
represented in essentially Polish form in ALMS, a routine was readily written which "compiles" an
expression; i.e., the machine coding is produced which will evaluate the
expression. Thus, for example, the Taylor coefficients of an analytic function
can be obtained by successive differentiation and evaluation at the required
point through the use of this routine.

A few experiments have been performed dealing with the analysis and retrieval
of information in simple English sentences. Questions based upon somewhat
stylized text have been readily answered using ALMS. ALMS
could conceivably be useful in the translation of computer
languages. Continuing work is being done in discovering new areas of
application, as well as improving the total system.