MTS Volume 8 - LISP and SLIP Page 110 (110 of 160)

MTS 8: LISP and SLIP in MTS
Page Revised February 1979 June 1976
110 LISP Debugging Facilities

MTS 8: LISP and SLIP in MTS
June 1976
SLIP ____
INTRODUCTION AND HISTORICAL NOTES _________________________________
This description is a user’s guide for the double-precision version
of SLIP installed in MTS. This version of SLIP is compatible with
FORTRAN IV and can be used in conjunction with programs that are able to
call FORTRAN routines. Most of this version of SLIP is written in
FORTRAN with a small portion, the SLIP primitives, written in 360/370-
assembler language. Complete citation for the references noted are
included in the last subsection "References."
The definitive paper on SLIP by Weizenbaum (3) was published in 1963.
That paper is not a user’s guide, but achieves a general description of
SLIP by defining the available data structuring functions together with
implementational details. The paper is novel in that it includes a
listing of the FORTRAN code. Two letters to the Communications of ACM _______________________
(4,5) add information for SLIP implementors and users. Subsequently a
book by Findler, Pfaltz, and Bernstein (6) that is a readable and useful
reference for users was published. Another book by Waite (7) offers
constructive criticisms, some of which are employed in this implementa-
tion. However, these are directed mainly to the student of high-level
list-processing systems for FORTRAN IV and thus perpetuate the policy of
Weizenbaum’s paper. User functions, together with implementational
details, are presented.
This description attempts to minimize emphasis on implementational
details and concentrates instead on the user functions.
The literature indicates that many versions of SLIP, for a variety of
machines, exist. Here, every attempt has been made to maintain the
spirit of the original version of SLIP and the names and assignments of
its functions. This attempt has not been entirely successful. New or
alternate functions were required for this implementation. Care has
been exercised to state where deviation from the original version was
necessary. Essentially deviations arise from limitations obtained from
the IBM System/360/370 32-bit word size.
Basic Concepts of List Processing _________________________________
The following are the nine basic operations that can be performed on
a list consisting of "n" elements (synonymous terms for element are node ____
or item). ____
SLIP 111

Previous Page Next Page

Page 1MTSVol08-LISPAndSLIPInMTS-Jan1983.pdf

Extracted Text (may have errors)

MTS 8: LISP and SLIP in MTS
Page Revised February 1979 June 1976
110 LISP Debugging Facilities

MTS 8: LISP and SLIP in MTS
June 1976
SLIP ____
INTRODUCTION AND HISTORICAL NOTES _________________________________
This description is a user’s guide for the double-precision version
of SLIP installed in MTS. This version of SLIP is compatible with
FORTRAN IV and can be used in conjunction with programs that are able to
call FORTRAN routines. Most of this version of SLIP is written in
FORTRAN with a small portion, the SLIP primitives, written in 360/370-
assembler language. Complete citation for the references noted are
included in the last subsection "References."
The definitive paper on SLIP by Weizenbaum (3) was published in 1963.
That paper is not a user’s guide, but achieves a general description of
SLIP by defining the available data structuring functions together with
implementational details. The paper is novel in that it includes a
listing of the FORTRAN code. Two letters to the Communications of ACM _______________________
(4,5) add information for SLIP implementors and users. Subsequently a
book by Findler, Pfaltz, and Bernstein (6) that is a readable and useful
reference for users was published. Another book by Waite (7) offers
constructive criticisms, some of which are employed in this implementa-
tion. However, these are directed mainly to the student of high-level
list-processing systems for FORTRAN IV and thus perpetuate the policy of
Weizenbaum’s paper. User functions, together with implementational
details, are presented.
This description attempts to minimize emphasis on implementational
details and concentrates instead on the user functions.
The literature indicates that many versions of SLIP, for a variety of
machines, exist. Here, every attempt has been made to maintain the
spirit of the original version of SLIP and the names and assignments of
its functions. This attempt has not been entirely successful. New or
alternate functions were required for this implementation. Care has
been exercised to state where deviation from the original version was
necessary. Essentially deviations arise from limitations obtained from
the IBM System/360/370 32-bit word size.
Basic Concepts of List Processing _________________________________
The following are the nine basic operations that can be performed on
a list consisting of "n" elements (synonymous terms for element are node ____
or item). ____
SLIP 111

Help

MTS 8: LISP and SLIP in MTS
June 1976
(1) Access the kth element (1kn).
(2) Insert a new element before or after the kth.
(3) Delete the kth element.
(4) Concatenate (i.e., chain together) two or more simple lists.
(5) Split a list into two or more lists.
(6) Make a copy of a list in terms of its contents and structure.
(7) Count the number of elements on a list.
(8) Sort the elements according to some criterion; for example, in
ascending order of the integers in a given field of the
elements.
(9) Search for an element that has a particular value.
Special reference is usually made either to the first (top) or the
last (bottom) element (i.e., when k=1 or k=n). There is even a
particular terminology dealing with list processing: inserting a new
element to the top is called pushing down the list, and deleting an
element from the top is called popping up the list. Although these
terms are completely acceptable in automata theory, they may be
misleading in programming, as we will see later, since the elements
below the top element do not in fact change location.
To achieve ease and flexibility in the above-mentioned nine basic
operations, the usual sequential structure of the memory, as in FORTRAN,
must be given up. In other words, elements that are consecutive
logically on the list may not be consecutive geometrically in the
computer hardware memory. Nothing is novel about this. For example,
when we store the elements of a two-dimensional array column-wise, the
row-wise neighboring elements are no longer adjacent in the essentially
one-dimensional memory. However, if we know the location of the first
element, the dimensions of the array, and the so-called mapping function
(i.e., the algorithm of storing the array), we can easily determine the
geometrical location of any element. Some similar arrangement is needed
in the case of lists, and the solution is provided by links or, using
another term, by pointers. A part of the space representing the list
element is occupied by the name of the next element. This name field
links with, or points to, the neighboring element, which in fact may be
in any part of memory.
Let us now consider one more concept, that of the Available Space
List for free storage, before seeing how the nine basic operations are
carried out. The Available Space List is essentially a reservoir of
free space from which we draw when a new cell is needed and to which we
return cells no longer needed, in order not to run out of free space too
soon. Similarly, the SLIP system can automatically draw cells from or
return cells to this reservoir. This dynamic memory allocation enables
us to omit specifying in advance how long a list is going to be. In
fact, we can create, change the size of, and erase lists during
execution time.
The importance of the Available Space List cannot be overemphasized,
particularly in nonnumeric computations.
112 SLIP

MTS 8: LISP and SLIP in MTS
June 1976
Generally, dynamic memory management becomes indispensable whenever
data are interrelated in a complex manner, and especially when process-
ing causes data to be dynamically reorganized in an unpredictable way as
part of the solution to the problem.
Many of the problems that require these facilities are partly or
wholly symbol-manipulating in nature, such as projects in artificial
intelligence, analysis and synthesis of natural languages, computer
graphics, simulation of cognitive processes, information retrieval, etc.
However, the study of many numerically oriented problem areas is also
greatly helped by list-processing techniques. The representation and
manipulation of sparse matrices is an obvious example of this case.
The initial objection to using list-processing languages was based on
the apparent waste of memory space occupied by pointers. As we can see,
in the problem of sparse matrices, just the opposite is often true.
There are, of course, other arguments in favor of list-processing
languages.
Let us now turn back to the basic list processes. Operations 2 to 5
amount to managing the relative linkings of certain cells. The name of
the top cell is always contained in a special word, the symbolic name of
which is FAVSLC. We can say the word points to the top of Available
Space List.
We can now discuss the rest of the basic operations.
(1) Accessing the kth element consists of going along the links and
increasing a counter of the elements passed by until k is
reached.
(2) Described above.
(3) Described above.
(4) Concatenating two lists amounts to simply overwriting the
end-of-list symbol of the first list with the name of the top
cell of the second list.
(5) Splitting a list into two is the opposite of the above process.
The symbolic name of the new list is identified by SLIP with the
name of its top cell and is output in a standard manner.
(6) Copying a list is straightforward. The name of the new list is
usually output according to some convention. The name is output
also when a new empty list is created. A single cell with an
empty symbol field and no link is considered an empty list.
(7) Counting the elements of a list consists of going down the list
via the linking pointers, always adding one to a counter until
the end-of-list symbol is encountered.
(8) Sorting consists of systematically comparing "keys" and manipu-
lating the link fields whenever necessary.
(9) Searching for a special element on a list is accomplished again
by a sequence of comparisons. The result can be either a simple
yes/no answer concerning the success of the search, or the name
of the matching element when found. In case of failure, a
special symbol, such as zero, is output.
SLIP 113

Previous Page Next Page

MTS 8: LISP and SLIP in MTS
June 1976
(BREAKF FOO1 (FOO2 (GREATERP N 5) (ARGS)))
breaks all calls to FOO1 and all calls to FOO2 when N
is greater than 5 after first printing the arguments
of FOO2.
(BREAKF ((FOO4 IN FOO5) (MINUSP X) NIL))
breaks all calls to FOO4 made from FOO5 when X is
negative.
Examples:
(BREAKF FOO)
(BREAKF ((GET IN FOO) T (GO)))
TRACEF TRACEF is an FLAMBDA. For each atomic argument, it
TRACEFs the function named each time it is called.
For each list in the form (FN1 IN FN2), it TRACEFs
only those calls to FN1 that occur within FN2.
For example, (TRACEF FOO1 (SETQ IN FOO3) causes both
FOO1 and SETQ in FOO3 to be traced.
Note: The user can always call BREAKO himself to
obtain combinations of options of BREAKFUNCTION not
directly available with BREAKF and TRACEF (see section
on BREAKO below). These functions merely provide
convenient ways of calling BREAKO, and will serve for
most uses.
UNBREAK UNBREAK is an FLAMBDA. It takes a list of functions
modified by BREAKF or TRACEF and restores them to
their original state. Its value is NIL. (UNBREAK T)
will unbreak the function most recently broken.
(UNBREAK) will unbreak all of the functions currently
broken.
If one of the functions, say FN, is not broken,
UNBREAK prints "FN NOT BROKEN" for that function and
no changes are made to FN.
UNTRACEF UNTRACEF is an FLAMBDA. It is the similar to UNBREAK.
BREAK0 [fn when coms]
BREAK0 is an EXPR. It sets up a break on the function
"fn" by redefining "fn" as a call to BREAKFUNCTION
with BREAKEXPR a form equivalent to the definition of
"fn", and "when", "fn", and "coms" as BREAKWHEN,
BREAKFN, and BREAKCMDS, respectively (see BREAKFUNC-
108 LISP Debugging Facilities

MTS 8: LISP and SLIP in MTS
June 1976 Page Revised February 1979
TION). BREAK0 also adds "fn" to the front of the list
BROKENFNS. Its value is "fn".
If "fn" is nonatomic and of the form (fn1 IN fn2),
BREAK0 first calls a function which changes the name
of "fn1" wherever it appears inside of "fn2" to that
of a new function, fn1-IN-fn2, which is initially
defined as "fn1". Then BREAK0 proceeds to break on
fn1-IN-fn2 exactly as described above. This procedure
is useful for breaking on a function that is called
from many places, but where one is only interested in
the call from a specific function, e.g., (RPLACA IN
FOO), (PRINT IN FIE), etc. This only works in
interpreted functions.
ERROR PACKAGE _____________
| The error package is enabled by EVALing (DEBUG T). When an error
occurs during the evaluation of a LISP expression, control is turned
over to the error package. The idea behind the error package is that it
may be possible to "patch up" the form in which the error occurred and
| continue. Or, at least, the user may find the cause of the error more
easily if he can examine the state of the world at the time of the
error. Basically, what the error package does is call BREAKFUNCTION
with BREAKEXPR set to the form in which the error occurred. This puts
the user "in a break" around the form in which the error occurred.
BREAKFUNCTION acts just like the top level of the interpreter with some
added commands (see the section on BREAKFUNCTION). The main difference
| when the error package is enabled is that the variable bindings that
were in effect when the error occurred are still in effect. Further-
more, the expressions that were in the process of evaluation are still
| pending. While the error package is enabled, variables may be examined
or changed, and functions may be defined or edited just as if the user
were at the top level. In addition, there are several ways in which the
user can abort or continue from the point of error. In particular, if
the error can be patched up, entering "OK" will cause the program to
continue. If the error can’t be fixed, # will cause the program to exit
from the break. When the error package is being used, the prompt
character is (=); this is preceded by a level number. Note: If for
some reason, the error package is not to be invoked, it can be disabled
| by evaluating (DEBUG NIL).
LISP Debugging Facilities 109

Previous Page Next Page

Extracted Text (may have errors)

Help

loading