We have insisted repeatedly on the importance of organizing any program consisting of more than a few dozen lines into paragraphs, each of which implements a well-defined action in a manner free of close involvement with the details of other paragraphs. We also noted that the SETL's procedure and case constructs aid in achieving this. The sample programs seen so far are organized into a main program and a series of procedures. This suffices for small programs, but above a certain size (say 500 lines) additional means of grouping collections of procedures into relatively independent units become necessary. Such collections are called packages, libraries, and object classes.
In this chapter, we will describe the first two of these extended SETL structuring mechanisms systematically and will illustrate their use. Object classes will be described in Chapter 8.
7.1 Packages
SETL allows groups of procedures developed for use in one or more large applications to be grouped together in text bodies called packages, each of which is arranged in two parts: a package 'header' which simply describes the procedures, constants, and global variables that a package provides, and an associated package body which implements each of the procedures listed in the package header. A package's header announces the gift which it is prepared to make to the outside world, and is ideally all that any one other than the package's autor needs to know about it; the associated package body contains the code which implements this 'gift'. Thus the SETL package mechanism, like that of the many other languages providing similar facilities, supports the basic requirement of information hiding: to make procedures available for use without burdening their users with any of their internal details.
7.1.1 package Headers
The syntax of a package header (or 'specification') is
package <package_name> <variable and constant declarations> <procedure declarations> end [<package_name>]
The Technically, packages are 'compilation modules' at the same level as a programs.
The package header must be compiled before
its associated package body, either as part of a single, muti-dection compilation involving several packages and programs, or in a separate compilation step.
7.1.2 package Bodies
A package body contains data visible throughout the package, but not outside the package, along with
the complete definitions of the procedures in the package. The syntax of a package body is
The <use section> is a sequence of clauses of the form
See 7.1.3 for more details.
The <constant and variable declaration section> defines names which will be visible
within the package, but not outside the package. And finally the <procedure section> is a list of
procedure definitions including all procedures listed in the package header, and possibly others visible
only within the package. An example illustrating all of these components is given below.
7.1.3 Importing or 'using' a Package
To import a package a use clause is placed before the declaration section of a program or package body. The syntax of a use clause is
For example, a program importing the package 'Anything' could be written as
Here is a second, somewhat more realistic example.
7.1.4 Compilation Units and Namescopes
As noted above, programs, package specifications and package bodies are all 'compilation units'. One or more of them
can appear in a source file. package specifications must be compiled before the associated package
bodies or any other units that import the package. When a package specification is compiled, the
associated package body and any units that import the package are invalidated, and will need
recompilation. This is particularly important to keep in mind when working with mutually dependent
packages.
A potential ambiguity occurs when two packages contain a common name, and a program imports
both of those packages. SETL adopted Ada rules to handle that occurrence: duplicate names will hide
each other. However, values bound to such names are still accessible using the construction
The following example shows this:
Since the unqualified use of 'some_proc' refers to a name incnflict between the tow packages used, but the qualified names a.some_proc and b.some_proc are unambiguous, the output produced by this program is
SETL names are local to their enclosing procedures, unless they have been explicitly declared (in a var declaration, a const declaration, or a procedure definition) at the start of a
higher level package, program, or procedure. For example, in
the name 'aaa' is accessible inside the subprocedure since it has been declared global at the program level.
It is possible to access hidden names using the construction <owner>.<name>, assuming <name>
would have been visible if not hidden. This is illustrated by the following small program, which produces the output
Note that the redeclaration of the constant 'a' inside the procedure 'some_proc' hides the different declaration of this same constant at the program level, but that the subprocedure can access the hidden value using the qualified form 'test.a'.
SETL also provides a variant of the classes-objects-methods mechanism characteristic of 'object oriented' languages. SETL's object facilities support multiple inheritance, and
operator overloading for user-defined types. They allow the SETL
programmer to create his own types and to define the normal SETL operations
(+, -, * etc.) on those types. Discussion of this whole set of possiblities is postponed to Chapter 8.
Each of the he two packages that appear in this example use variables and procedures supplied by the other. The small test program shown uses both of them, and its output, which is simply
verifies that all behaves as expected.
Whenever the specifier of a package P is rcompiled, all programs, packages, or classes Q that use P must be recompiled. However, since the body of a package need not be compiled together with its specifier, the body of P can be recompiled without forcing Q to be recompiled, provided that only the body, but not the specifier, of P is recompiled. As already said,separate compilation of package specifiers and bodies is necessary if a group of packages use each other circularly, one must compile all the headers first, and then all the bodies.
The following example illustrates some of these considerations. First we compile a simple package and its specifier, after which it is used immediately in a small program.
The output produced is
Next we recompile the body of test_pak, but not its specifier:
It remains possible to execute program 'test' without recompiling it. But when this is done, the newly compiled version of procedure 'proc' will be loaded and executed, so that the output produced will be
An initial set of bodies, whch can be compiled together with these specifiers, are
In the presence of these packages the small test program
produces the output
Now we can recompile the body of test_pak_1 without having to recompile anything else. Suppose that this becomes:
Re-executing program test; now produces the output
Here is another example of the rules governing name conflicts:
This technique can clearly be used to redirect printed output to alternative files or display windows, to replace the newlines normally added by 'print' with blanks, etc.
Once a procedure has been packaged in this way, it can be utilized in any other program (or package) simply by using the package which supplies the procedure. Here is an example of how the 'search' procedure supplied by the binary_search package would be used.
Simple test programs like this are often included in the file containing the source code for packages, as illustrations of their use and as convenient small regression tests which can be executed if the package is changed in any way.
Packaging of one or more procedures often suggests their generaization. For example, ordered collections for which binary searching is effective may not be ordered as simply as the preceding example suggests. They may instead consist of pairs [key,data], the sequenceof keys being ordered, but not the associated data. To handle this and other related possibilities, we can simply replace the fixed comparison opertor appearingin the preceding code with a variable comparison operator which the package user can supply. This leads to the following version:
The package seen above retains the comparison operator to be used in the public global variable 'compare_op'; if none is supplied, then the default comparison x <= y is used instead. The second phase of the following test program supplies a procedure for comparing the first components of pairs as the 'compare_op' to be used in searching the samll database of sting pairs presented to it.
Here is another eample, a package containing an elementary procedure which factors small integers n by repeatedly finding and removing the smallest remainning factor up to sqrt(n).
The following test program uses this package to derive the results seen
When a program is first being debugged one will normally want to inspect the values which it is producing to verify that they look reasonable. Also, the while loops in the program must be approached cautiously, since any one of them might fail to terminate. Simple print statements, commonly inserted to allow value inspection, are subject to the problem that if wrongly placed they can produce floods of output. For this reason, several cycles of execution are often required befoe print statements showing a program's problems can be positioned accurately enough.
The package seen below implements a pair of routines, 'rept_limit' and 'watch', intended to relieve these difficulties. Both return closures. To control a loop using 'rept_limit', a statement like
should be inserted just before the loop, and then the statement
should be inserted at the head of the loop. In the first of these statements, 'msg' designates a string message that should identify the loop uniquely, and 'n' the maximum number of times that it should be allowed to execute without re-entry. If this limit is exceeded, an abort will be forced, and 'msg' will be incorporated in the resulting error string.
The 'watch' function is serves to monitor specified variables and/or expressions in a program by collecting their values into circular buffers of specified size, which inthe event of an error termination are sorted into execution order and printed out with specified captions. To use this function, one should insert calls
at any points in the program which are to be monitored. Here the string caption 'msg' should identify the monitoring point uniquely, while 'bufsize' designates the size of the circular buffer used to hold values collected at this point. value_list should be the value, or tuple of values, to be collected. If value_list is a tuple, and 'msg' contains commas which divide it into sections, then when an error-termination report is generated these sections will be associated with the separate tuple components to construct a line of the report. (If the tuple length of value_list is greater than the number of message sections, all the final tuple components will be associated with the last message section.)
The output produced by the following test program
which is
illustrates the use of 'bugoff_pak'. As the test program shows, the parameterless procedure 'report_watch', supplied by 'bugoff_pak', must be set as the value of the system variable 'abend_trap' for a report to be generated upon abort.
The code for 'rept_limit' is quite straightforward. 'watch(msg,n)' binds the values of 'msg' and 'n' into a pair of closures which it generates and associates with the 'msg' string. The first of these closures is the routine which collects values into a circular buffer created within the closure, while the second is merely an auxiliary routine which can be used to read this circular buffer. If closures have already been created for a given 'msg, it continues to be used, so no new closure is created.
A substantial and growing collection of SETL code packages, realizing many useful capabilities, is available with the SETL system. Many ofthese will be reviewed in Chapter 11. Here,by way of introduction to this whole area, we give an account of just one of them, 'random pak', which provides SETL with an elementary but flexible random-objects capability.
random_pak provides just two procedures:
The 'source' in a 'start_random' call can be any of:
1. An integer n. The stream consists of integers from 1 to n.
2. A positive real x. The stream consists of reals from 0.0 to x.
3. A set s. The stream consists of random elements of s.
4. A tuple t. The stream consists of random elements of t.
The 'seed' can be any integer, or can be OM, in which case the current ime is used
to generate a starting integer. Use an integer as 'seed' if you want your random selections to be repeatable.
The following small example illustrates the use of this package.
Here is output from a sample run of this program. Note that no two runs can be expected to produce the same output.
SETL is supplied with a substantial and growing collection of native packages. Here is a reasonably comprehensive list of its current members.
These native packages and the functions they provide will be reviewed systematically in Chapters 10 and 11.
When program execution begins, the current library list is searched to locate and load all the packages and classes which the program uses. This search is recursive, i.e all the packages and classes used by any of the packages or classes directly used by the program must also be located and loaded. If any is missing, or if its specifier has be recompiled after compilating of the program orof the specifier of any package or class coming later in this load order, a diagnostic in generated and recompilation is required.
A reasonable way of using SETL's library list capability is to compile all the packages and classes which you expect to use byte do not expect to change into a series of libraries grouped by functionality, and then to run with a library list consisting of a current library containing all programs and other code packages under development or expected to change, with the other, reliably invariant code libraries constituting the remainder of the library list.
This small program loads the contents of the random numbers package 'random_pak' supplied with the SETL system (which we assume has been precompiled), uses 'library_package' to acess it dynamically, and then calls the routines which it supplies (which are loaded dynamically by 'library_package') to generate a tuple of ten random numbers. (Full documentation concerning 'random_pak' is found in a later Chapter.)
The output produced is
It should be clear that this use of the library_package function gives us a 'dynamic' alternative to the ordinary diction use used to gain access to packages, and allow us to load functions from any precompiled package at any time. Since SETL also has means, described later, for compiling dynamically created strings into code, 'library_package' can be used to support fully interactive creation and use of dynamically created procedures.
Packages can be supplied with standard one-parameter routines named "explain", which if called with the parameter OM produces a briefly annotated list of the procedures in the package, and if called with the name of one of these procedure as parameter produces more detailed information about the procedure's parameteers and use.
The IDE edit window is a standard edit area in which SETL text appears with helpful syntax-sensitive coloring. The edit area supposrts a stndard set of cut-copy-paste-find-find_again-rplace-replace_again keyboard shortcuts. A few of the most commonly used operations available via the menus listed above are also available directly through minibuttons in each IDE edit window. This includes the 'indent', 'de-indent', 'comment', 'de-comment', 'compile window', 'compile and run window', and 'rerun window' operations. The following table describes five other operations of edit and search type available through edit-window minibuttons:
When the contents of a SETL edit window are compiled using either a minibuttion or a menu option, compile errors are both printed to the SETL output console and summarized in a small auxiliary window that opens just under the edit window. Error messages are tagged with the line number and character position to which they appertain, facilitating their location using line-number search.
The IDE edit window presents two more minibuttons, an edit-window help button and a tools button. When clicked, the edit-window help minibutton opens a very useful tabbed help window whose contents are read from a formattted file called 'Setl HELP'. Given a typical current version of this file, the help window will have the following tabbed sections:
Each tabbed panel of the Help window is defined by a corresponding section of the 'Setl HELP' file. Sections in this file are delimited by lines of the form
Each such section is divided into items by item header lines of the form
for example
Each item consists of a template part running from its item header line to the next following line of the form
which introduces the help subsection of the item; this is its final part.
When a tabbed panel of the Help window is selected, all the items of the corresponding section are listed in the upper half of the panel. Any of these items can be selected by clicking on it. When this is done, the text of the help subsection of the item appears in the lower half of the panel, providing a useful measure of on-line documentation.
Moreover, any of the item names listed in the upper half of the any tabbed panel of the Help window can be dragged into any currently open IDE edit window. When this is done, the corresponding item template is copied to the point at which the item name was dropped. This makes a very useful collection of illustrative code fragments available, and in favorable cases allows programs to be built by sucessive drag/drop operations, with little auxiliary typing. For example, if the 'program' item (thisis the first item in the Help window 'Programs' panel is dragged into an edit window, the code fragment
This gets the construction of small SETL programs off to a flying start.
The Help window <SCRIPT> capability. The Help window supports an even more powerful alternative to the 'template' facility that we have just described. The template part of any item can be replaced by a 'SCRIPT' subsection, introduced by a group of lines of the form
line introducing the help subsection of the same item, should be a SETL program which uses the facilities of the native package ide_pak (detailed in Chapter 11) to analyse and manipulate the contents of an edit window. Then, if the corrresponding item name is dragged into an edit window, this program will be executed, and can both print the results of an analysis of the edit window contents to SETL's output console, and/or modify the edit window contents, possibly also compiling specially modified forms of this text for experimental or debug execution.
When a SCRIPT has been set up in the format indicated and the name prefixed to the SCRIPT is dragged into an edit window, the SCRIPT's parameter-string supplied will be read, and the program SCRIPT will be executed. If the '=program_name' clause has been omitted, then the program text following the SCRIPT tag will be read, compiled into a program P, and executed. (This should be a complete SETL program.) If an '=program_name' clause s present, then the program having the specified name will be located in somelibrary of the currently active library list and executed. In either case the tool-parameter-string is available to the program P, as the value of the function 'get_parameter()' supplied by IDE_pak. Note that programs P invoked in this way will normally use IDE_pak, and possibly also the extended set of utility routines available in IDE_tools_pak.
The following example of a small Help window 'item script' of this kind reads and capitalizes the currently selected portion of an edit window onto which the item name 'capitalize' is dropped.
You can easily write programs of this kind and paste them into the 'SETL Help' file to customize your collection of SETL development tools. The 'Tools' panel derived form the SETL Help file as distributed makes a useful inital collection of tools of this kind available. As already explained, the tools in this collection are used by dragging them onto an IDE edit window, whose contents they then access, analyze, and (possibly) modify. Some of the tools apply to an entire window or to a preselected part of the window, and so can be dropped anywhere in the window. Others react in a more specific, local manner to the window position at which they are dropped.
The following table summarizes some of the tools provided in the standard collection distributed.
Since the tool modifies an auxiliary copy of the program being traced, but not the program itself, no cleanup is needed subsequent to its use.
When opened, the IDE Preferences window is seen to consist of the four tabbed seections listed in the following table
7.4 Dynamic compilation using the 'eval' function; naming conventions for 'eval'. The SETL compiler ('stlc') compiles each program and package submitted to it separately to a set of quadruples in an internal library format and stores the structures thereby generated into a library file, under the name of the program or package. During compilation, all package bodies are checked against the corresponding 'package declaration' records, to verify that every procedure defined in the body has exactly the header declared for it in the matching package declaration. If this declaration record has been compiled separately, it will have to be read in from the library file which contains it. The compiler also verifies the absence of assignments to any variable made global in any directly used package, and agreement between the number of arguments of any procedure coming from a package used and the number of parameters with which this procedure has been declared in the package. In any case, all addressed library files are be searched to see if any previously compiled program or package is being recompiled; if so, it must be replaced by its newly compiled version.
The following 'execute' or 'stlx' step then begins with a load operation which, starting with the program P to be executed, tracks transitively through the whole chain if packages referenced by use statements starting with those in P, collects all the quadruples in P and in these packages, and assigns a memory location ML to each variable mentioned in these quadruples At run-time ML holds the value of the variable, generally as a pointer to some larger heap structure. The values of variables local to a procedure Q are stacked when Q is called and unstacked while Q returns, allowing all references to variables to deal directly with the corresponding memory locations ML.
The eval(stg) function described in this section grafts a dynamic compilation capability on this structure. Every string passed to eval(stg) as an argument must have exactly the form of a legal SETL program, but without the normal 'program' header and trailer lines. Besides the names which are global in packages imported by the use statements in an eval, the names treated as global during successive eval's are exactly those names which appear either at the topmost program level (i.e. outside any procedure), either in an executable SETL statement or in a declaration; or those which appear as procedure names.
The value returned by eval(stg) is 0 if the eval can be handled sucessfully, OM if it encounters a compilation error.
These dynamic compilation conventions preserve all of SETL's syntax, much of its namescoping semantics, and allow dynamically compiled code to run almost as efficiently as precompiled code, once compilation has taken place. Since the compiler is held in memory, is quite fast, and incorporates all the necessary loader code, the environment that results is quite dynamic.
Here is a first example. Suppose that we first eval the string
So the output produced is
Next we give an example to illustrate the rule that names appearing in packages that are used globally by both static code and dynamically evaluated code packages are common across the static/dynamic boundary. The test program seen below shares use of the package 'share_names', and hence of the variable 'shared_global', with the two dynamically eval'ed code fragments it contains. For that reason, assignments mde on either side of the static/dynamic boundary are seen on the other side.
It follows that the output produced is
The variant example which folows shows that the smae use of shared global names allows procedures created dynamically in an evaled string to be passed back to static code and used there.
The output produced is
package body <package_name>
<use section>
<constant and variable declaration section>
<procedure section>
end [<package_name>]
use <package_name 1> [ , <package_name 2> ] ... ;
package Anything;
var visible_var
const visible_const := 5;
procedure visible_proc(p1,p2);
end Anything;
package body Anything;
var hidden_var;
const hidden_const := 10;
procedure visible_proc(p1,p2);
print("Hello");
end visible_proc;
procedure hidden_proc(p1,p2);
print("Goodbye");
end hidden_proc;
end Anything;
program Something;
use Anything;
visible_proc(1,2);
end Something;
package Stack_Module; -- the 'package' or 'package header'
procedure Push(rw Stack,Item);
procedure Pop(rw Stack);
end Stack_Module;
package body Stack_Module;
procedure Push(rw Stack,Item);
Stack with:= Item;
end Push;
procedure Pop(rw Stack);
if #Stack = O then
return OM; -- the SETL 'undefined' or 'null'
else
return Item from Stack;
end if;
end Pop;
end Stack_Module;
package a; -- a first package
procedure some_proc();
end a;
package body a; -- body of first package
procedure some_proc(); return 10 * "a"; end some_proc;
end a;
package b; -- a second package, also providing a procedure named 'some_proc'
procedure some_proc();
end b;
package body b; -- body of second package
procedure some_proc(); return 10 * "b"; end some_proc;
end b;
program test; -- a program using both packages
use a,b;
print(some_proc); print(a.some_proc()); print(b.some_proc()); -- use of procedures from packages
end test;
<om>
aaaaaaaaaa
bbbbbbbbbb
program my_prog;
var aaa;
bbb := 1; aaa := 2; ccc := my_proc(bbb);
procedure my_proc(b);
bbb := b; return bbb + aaa;
end my_proc;
end my_prog;
program test; -- a program using both packages
const a := 1; -- belongs to 'test'
some_proc(); -- procedure call
procedure some_proc(); -- subprocedure
const a := 2; -- belongs to 'some_proc'
print(a," ",test.a); -- both consts can be accessed using qualification where needed
end some_proc;
end test;
7.1.5 Circular Dependencies among Packages
It is possible for a package 'a' to use a package 'b' at the same time that 'b' uses 'a'. How can this be done consistently with the rule that every package used by 'a' must be compilied before 'a'? The answer is obvious if one realizes that it is only the specifier of a package, not the package body, that must be compiled before it is used. Thus mutually dependent sets of packages can be handled by compiling all the specifiers first, and then all the bodies. The following is an example of this:
package a;
var va;
procedure pa;
end a;
package b;
var vb;
procedure pb;
end b;
package body a;
use b;
procedure pa;
print(vb);
end pa;
end a;
package body b;
use a;
procedure pb;
pa();
end pb;
end b;
program test; -- over-writing the system 'print' routine
use a,b; -- save the original procedure, so that console output remains possible
vb := 999999; -- set package b variable
pb; -- call package b procedure, which invokes package a procedure to print vb
end test;
7.1.6 Separate Compilation of Packages and their Headers
The specifier of a package P must be compiled and must be available somewhere in the active library list (see below) before any other program, package, or class Q that uses P is compiled. This makes all P's externally visible procedure, variables, and constant names available during the compilation of Q, allowing spaces for the storage of the corresponding values and procedure values to be allocated and named. When a package body is compiled, the procedures actually present in it are checked for agreement with the procedures declared in its specifier, and an eror message is generated if any discrepancy is found. It is also verified that all procedures declared in the specifier are actually present in the body.
package test_pak;
procedure proc(param);
end test_pak;
package body test_pak;
procedure proc(param);
print("version 1: ",param);
end proc;
end test_pak;
program test;
use test_pak;
proc("param");
end test;
version 1: param
package body test_pak;
procedure proc(param);
print("version 2: ",param);
end proc;
end test_pak;
version 2: param
.
The following is another example of a set of packages which use each other, so that each has access to the public procedures of the other. The specifiers, which must be compiled together, are
package test_pak_1;
procedure proc_1(param);
end test_pak_1;
package test_pak_2;
procedure proc_2(param);
end test_pak_2;
package body test_pak_1;
use test_pak_2;
procedure proc_1(param);
print(param);
if #param >0 then proc_2(param(2..)); end if;
end proc_1;
end test_pak_1;
package body test_pak_2;
use test_pak_1;
procedure proc_2(param);
print(param);
if #param >0 then proc_1(param(2..)); end if;
end proc_2;
end test_pak_2;
program test;
use test_pak_1;
proc_1("param");
end test;
param
aram
ram
am
m
package body test_pak_1;
use test_pak_2;
procedure proc_1(param);
print("New Version: ",param);
if #param >0 then proc_2(param(2..)); end if;
end proc_1;
end test_pak_1;
New Version: param
aram
New Version: ram
am
New Version: m
package test_pak_1;
var test_var := "test_var in test_pak_1";
procedure test_proc();
end test_pak_1;
package body test_pak_1;
procedure test_proc();
print("test_proc in test_pak_1");
end test_proc;
end test_pak_1;
package test_pak_2;
var test_var := "test_var in test_pak_2";
procedure test_proc();
end test_pak_2;
package body test_pak_2;
procedure test_proc();
print("test_proc in test_pak_2");
end test_proc;
end test_pak_2;
program test; -- uses both packages
use test_pak_1,test_pak_2;
print("test_var: ",test_var);
print("test_var: ",test_pak_1.test_var);
print("test_var: ",test_pak_2.test_var);
test_pak_1.test_proc();
test_pak_2.test_proc();
test_proc();
end test;
At thispoint, you should be able to predict the resulting output.
7.1.7 Re-defining SETL's Built-In Procedures
SETL provides many built-in procedures. Those without write parameters may be used as first class
objects. They are all declared as part of a default scope, so the names may be hidden by any local
declarations of variables with the same name. The following example illustrates this fact. In it, the built-in 'print' function is first saved (under the name 'printit'),and then 'print' is redfined (in the subprocedure 'sub_proc') and invoked. To accomplish its output, the new 'print' invokes the built-in 'print' function as 'printit'. The output produced by the call print(99) to the redefined 'print' function is
program test; -- over-writing the system 'print' routine
const printit := print; -- save the original procedure, so that console output remains possible
sub_proc(); -- subprocedure call
procedure sub_proc(); -- sub-procedure redefines 'print'
print(99); -- invocation of redefined 'print'
procedure print(x); test.printit("I have printed: ",5 * (str(x) + " ")); end print; -- redefinition of 'print'
end sub_proc;
end test;
7.1.8 Some Examples
Packages often begin as procedures in ordinary programs which one considers to be useful enough that one wants to package them for repeated use, and perhaps generalize them also. For example, the generally useful binary search procedure of Section 5.4.4
can be wrapped in the following simple package.
package binary_search; -- binary search package
procedure search(x, t); -- iterative form of binary search procedure
end binary_search;
package body binary_search; -- binary search package
procedure search(x, t); -- iterative form of binary search procedure
lo := 1; hi := #t; -- initialize search limits
while lo < hi loop
if x <= t(mid := (lo + hi)/2) then
hi := mid;
else
lo:= mid + 1;
end if;
end loop;
return lo;
end search;
end binary_search;
program test; -- test program for binary search
use binary_search; -- use binary search package
tup := [1,4..1000];
print(search(40,tup));
end test;
package binary_search; -- binary search package, version 2
var compare_op := OM; -- comparison operator, if any is supplied
procedure search(x, t); -- iterative form of binary search procedure
end binary_search;
package body binary_search; -- binary search package
procedure search(x, t); -- iterative form of binary search procedure
lo := 1; hi := #t; -- initialize search limits
while lo < hi loop
midval:= t(mid := (lo + hi)/2);
if if compare_op = OM then x <= midval else compare_op(x,midval) end if then
hi := mid;
else
lo:= mid + 1;
end if;
end loop;
return lo;
end search;
end binary_search;
program test; -- test program binary search
use binary_search; -- use binary search package
tup := [1,4..1000]; -- test 1: default comparison
print(search(40,tup));
-- test 2: comparison of first components
tup := [["Al","Scarface gangster"],["Butch","Friend of Sundance"],["Jack","Tall, gloomy"],
["Jill","Also known as Gillian"],["Paul","Formerly known as Saul"]];
compare_op := lambda(x,y); return x(1) <= y(1); end lambda;
-- compare first components of pairs
print(search("Carl",tup));
end test;
package prime_factors_pak;
procedure prime_factors(n); -- get tuple of prime fctors of n
end prime_factors_pak;
package body prime_factors_pak;
procedure prime_factors(n); -- get tuple of prime fctors of n
facts := []; -- will collect
while even(n) loop facts with:= 2; n /:= 2; end loop; -- even factors
while exists k in [3,5..ceil(sqrt(float(n)))] | n mod k = 0 loop
facts with:= k; n /:= k; -- smallest remaining factor, up to sqrt(n)
end loop;
facts with:= n; -- the final factor
return facts;
end prime_factors;
end prime_factors_pak;
program test; -- test program for prime_factors_pak
use prime_factors_pak;
print(prime_factors(2**10 * 3**5 * 13)); -- [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 13]
print(prime_factors(1000001)); -- [101, 9901]
print(prime_factors(1000000001)); -- [7, 11, 13, 19, 52579]
end test;
7.1.9 A Package useful for early-stage Debugging
program test; -- test of debugging utilities
use bugoff_pak;
abend_trap := report_watch; -- set for report incase of error
limit := rept_limit("test loop",10); -- define limit
for j in[1..100] loop
watch("10 * j= ,20 * j= ",8)([10 * j,20 * j,99 * j]); -- watch 3 values
limit; -- limit number of iterations
watch("j after= ",5)(10 * j); -- watch 1 value
end loop;
end test;
*** Abnormal End -- source file =>
line => 16
column => 55
reached limit of 10: test loop
Call Stack
----------
Line Column File
---- ------ --------------------------------
77 17
7: 10 * j= 40, 20 * j= [80, 396].....
9: 10 * j= 50, 20 * j= [100, 495].....
11: 10 * j= 60, 20 * j= [120, 594].....
12: j after= 60
13: 10 * j= 70, 20 * j= [140, 693].....
14: j after= 70
15: 10 * j= 80, 20 * j= [160, 792].....
16: j after= 80
17: 10 * j= 90, 20 * j= [180, 891].....
18: j after= 90
19: 10 * j= 100, 20 * j= [200, 990].....
20: j after= 100
21: 10 * j= 110, 20 * j= [220, 1089].....
package bugoff_pak; -- debugging utilities
procedure rept_limit(msg,n); -- define loop limit
procedure watch(msg,n); -- define variable watch
procedure report_watch(); -- generate report on watched values
end bugoff_pak;
package body bugoff_pak; -- debugging utilities
use sort_pak,string_utility_pak;
var watchers := {}; -- variable watchers
var watch_count := 0; -- count of watch cycles
procedure rept_limit(msg,n); -- define loop limit
var m := n;
return
-:= 1) < 0 then abort("reached limit of "+ str(m) + ": " + str(msg)); end if; end lambda;
end rept_limit;
procedure watch(msg,n); -- define value watch; n is initially the size of the desired buffer
-- if the msg is comma-delimited, this will report separately on each of a tuple of values
var buffer := []; -- to be enclosed
if (closures := watchers(msg)) /= OM then return closures(1); end if; -- use existing watcher if any
closures := -- otherwise create a new pair of closures
[lambda(val);
if buffer = [] then buffer(n) := [0,val]; end if;
buffer(n) := [watch_count +:= 1,val]; n +:= 1;
if n > #buffer then n := 1; end if; -- use buffer circularly
end lambda,
lambda(); return buffer; end lambda]; -- second element just reads buffer
watchers(msg) := closures; -- post the watcher
return closures(1);
end watch;
procedure report_watch(); -- generate report on watched values
-- this is generated in sorted order of the attached watch_count values
reptuple := []; -- for sorting of accumulated reports
-,getz]] in watchers loop
bufval := getz(); -- get the buffer of saved values
reptuple +:= [[cyc,msg,val]: [cyc,val] in bufval];
end loop;
for [cyc,msg,val] in merge_sort(reptuple) loop -- print report in execution order
if "," in msg and type(val) = "TUPLE" then -- print individual elements
stg := ""; -- will build report string
np:= #(mpieces := breakup(msg,",")); -- get subitems of message
nv := #val; -- length of tuple of values
for piece = mpieces(j) loop
stg +:= piece + if j < np or np >= nv then str(val(j)) + if j = np then "" else ", " end if
else str(val(j..)) + "....." end if;
end loop;
print(cyc,": ",stg);
else -- print single item
print(cyc,": ",msg,val);
end if;
end loop;
end report_watch;
end bugoff_pak;
7.1.10 Packages supplied along with the SETL system
procedure start_random(source,seed);
-- returns a 'handle', from which a stream of random items can be generated
procedure Random(Handle); -- gets next item in an endless stream of random items
program test; -- random values test
use random_pak;
int_stream := start_random(10,OM); print([random(int_stream): j in [1..10]]); -- random integers
real_stream := start_random(1.0,OM); print([random(real_stream): j in [1..10]]); -- random reals
let_stream := start_random({x: x in "acgt"},OM); print("" +/ [random(let_stream): j in [1..10]]); -- random letters
mixture := start_random([int_stream,real_stream,let_stream],OM);
print([random(random(mixture)): j in [1..10]]); -- random mixture of the above
end test;
[1, 4, 3, 3, 7, 4, 1, 2, 6, 5]
[0.062500000000, 0.79296875001, 0.74047851459, 0.61601266571, 0.60736879422, 0.37937456663,
0.42960901774, 0.13054460326, 0.52823512128, 0.0095007302636]
catccatggt
["g", "a", 4, 0.40146602833, 0.33156534447, "t", "g", 0.44957017235, 6, "a"]
7.1.11 Native Packages : Introduction
Besides means for organizing large collections of procedures written in SETL itself, the language provides, as any modern progammming language must, means for calling functions belonging to pre-existing collections written in other languages. It is critical to be able to do this, since
The means which SETL provides for interfacing to code written in other languages (notably C, compiled languages which haveinterfaces to C,or or interpretive languages having such interfaces) is its native package mechanism. A native package consists of two parts, its (visible) specifier and its (less visible) associated DLL, which isa comiled, dynamically linkable code package written to conform to the linkage conventions detailed in Chapter 11. The specifier of a native package is almost identical with that of a standard SETL package, except for the prefixed keyword native, An example is
native package parser;
procedure parse(str); -- parse a string, returning its parse tree as a nested set of tuples
procedure compile(str); -- compile a string, writing result to current library
procedure setl_num_errors(); -- read number of errors generated during last previous 'parse' or 'compile' operation
procedure setl_err_string(err_num);
-- get text of indicated error message generated during last previous 'parse' or 'compile' operation
string_utility_pak Provides various commonly used string manipulation primitives, in high-performace form. These include string split and join operations, character suppression opertions, and upper/lowercasing. A library of high-performance operations on strings represented as flat byte-arrays is also provided. file_pak Provides various file and directory manipulation operations, including creation, deletion, listing, and navigation. rx_pak High-performance regular-expressions package derived from the Gnu library. stringm_pak High-performance exact and approximate string matching operations, including Knuth-Morris-Pratt and Boyer-Moore matching algorithms, Karp-Rabin probabilistic match, Aho-Corasik match of list of patterns to a string, suffix-tree match, edit-distance based approximate string matching and alignment, and detection of longest common substring of a pair of strings. tk_pak Interface to the Tk widget set. This is the basis for SETL's interactive Graphical Interface, described in Chapter 10. parser_pak Interface to SETL's parse and compile functions. 'Parse' analyses a SETL source file and returns its parse tree as a nested collection of tuples, making the standard SETL error messages available if there are parse errors. A 'compile' function, which takes a string as representing a SETL source file as input amd compiles it into the currently active libray is also provided. ide_pak This package gives access to the string contents of the currently active SETL edit window and makes it possible to create the interactive source-code analyisis and manipulation utilities described below. Its functions also allow the currently selected area of an edit window to be detected and manipulated. A second group of functions in this package allow the library list currently in effect to be read and modified, packages to be reloaded after compilation, and programs to be rerun. setldb_pak Extensive collection of SETL database operations, described in Chapter 12. libnr_pak Large library of high-performace numerical routines, derived from the collection described in the well-known treatise 'Numerical Recipes in C.' libntl_pak Package of integer, modular arithmetic, and modular polynomials packagederived for Victor Shoup's well-known 'NTL' library. python_pak Interface to the Python language and all of of its many libraries. In particular,this gives access to Python's internet routines, including its URL and Socket routines. grlib_pak Extensive library of image-manipulation functions. Mutiplane images are handled in both byte and floating formats. sound_pak Procedures for manipulation and analysis of sound in AIFF and related formats. midi_pak Procedures for manipulation of music in MIDI format. movie_pak Procedures for manipulation and display of video image sequences. 7.2 Libraries.
SETL compiles the source code form of programs, packages, and classes (these are its 'compilation units') into an efficiently interpretable byte-code form which it stores in specailly stuctured files called 'libraries'. At any moment during SETL operation, one of these files must be designated as the current library, and any number of others may also be designated as members of the current library list. Sucessful compilation operations write their results into the current library, erasing the previously compiled forms of any identically named programs, packages, and classes. Packages and classes used by any program, package, or class being compiled are located in the current library list, which is searched in its stated linear order. Once located, all calls to any of the procedures or constants they provide are checked for consistency with the corresponding procedure and const delarations in the appropriate source package or class. Inconsistencies are diagnosed.
7.2.1 The library_package function.
The built-in SETL function library_package can be used to load all the procedures of any precompiled SETL package. The package name should be passed as an upper-case string. 'library_package' returns a mapping of each (upper-case) name of a procedure in the package to a procedure value identical with the procedure name. Repeated calls to 'library_package' check for packages already loaded and do not load them a second time, even if they have been (dynamically) recompiled in the mean while (see 'Dynamic compilation'.) For example,the program
program test;
print(rp := library_package("RANDOM_PAK"));
rand_handle := rp("START_RANDOM")(1.0,OM);
print(rp("RANDOM")());
end test;
{["START_RANDOM", <procedure 736550592>], ["RANDOM", <procedure 736550660>]}
[0.68750000000, 0.97265625001, 0.69213867054, 0.43336498748, 0.48258955542,
0.89872033190, 0.98304035736, 0.51470808347, 0.71763429511, 0.40628701763]
7.3 SETL's Interactive Development Environment.
When first opened, the standard SETL IDE (Interactive Development Environment) presents an output console window and a menu bar with the options File, Edit, Search, Program, Library, Interface, Windows, and Help. These make the following functions available
File Standard file-management and print options, plus New", for opening a new edit window Edit Standard cut-pase etc. edit options, plus comment and decomment, indent and de-indent, and P{{references Search Standard search/replace operations; go to line Program compile file, compile contents of edit window, compile and run, rerun, etc. These is also a 'run (experimental) option, and a 'Rebuild all' operation, whiich looks for a file named 'makefile' in the same foler as the IDE executable, and compiles all the files listed in 'makefile', one after the other. The "Set Program Name' option defines the name of the program the 'Run' will execute. Library Operations for creating an empty new library file, with a specified name or with the default name setl2.lib; also an operation for setting the library list that the SETL comilier and execution system will use. Windows A list of all currently open edit windows, and of the SETL outputconsole window. This can be used to bring any of these windows to the foreground. Help Offers standard system help options.
Parenthesis balance Higlights the leftmost parentheis-balanced subsection of the currently selected edit-window section. Procedure search Pops up a menu listing all lines starting with the key woerd 'procedure'. Any of these items can be selected to jump to the corresponding procedure. Mark search Pops up a menu listing all 'marks' in the window. These are lines starting with the special comment sequence '--->', followed by a mark name. Any of these items can be selected to jump to the corresponding line. This provides an easy way to mark and jump to points of active development in a program being worked on. Recent strings repeat search Pops up a menu listing all strings that have been targets of recent search or search/rplace operations. If an item is selected from this list it becomes 'current' in the IDE's search dialog window (normally popped up by the Search menu's 'Find/Replace' option.) . Note that the search dialog window opened when the 'Find/Replace' option is selected also contains buttons which pop up list of recently used search and replace strings, which can be wused to repeat search or replace operations involving these strings. Line-number search This button always shows the number of the edit window line at which the cursor is currently positioned.
Programs List SETL statement forms, operations, and built-in functions Functions Supplementary, more extensive list of built-in SETL functions Classes and Packages Syntactic forms of packages, classes,andtheir speciiers; syntax used forclass-based operator overloading. Help itemsfor SEL's dynamic evaluation, compilation , and package/class load operations. Widgets Help and templates for SETL's Tk-based interactive graphic capabilities. Libraries Documentation concerning SETL's library management operations, and allmajor SETL-coded and native packaages Tools Basic documentation conerning collection of edit-window analysis and manipulation tools (including some debugging tools) as described below. Build Tools Experimental package of drag-and-rop SETL program construction tools. Unix Operations Experimental package of Help items and operation templates for UNIX facilities available via SETL-to-Python Interface program test; -- comment
use string_utility_pak;
print(""," ");
procedure my_proc(a); -- comment
end my_proc;
end test;
(i) tool-name (within pointed brackets, e.g. <tool-name>)
(ii) tool-parameter-string can consist of multiple lines
(iii) SCRIPT or SCRIPT=program_name (within pointed brackets)
(iv) text of tool program (ignored if SCRIPT=program_name was used)
If present, this 'SCRIPT' subsection, which extends to the following
<capitalize>
**
<SCRIPT>
program test;
use ide_pak,string_utility_pak;
[ix1,ix2] := get_selection();
if abs(ix2 - ix1) /= (ix2 - ix1) then [ix1,ix2] := [1,get_length()]; end if;
buffer_part := get_buffer()(ix1..ix2);
set_buffer(ix1,ix2,case_change(buffer_part,"lu"));
end test;
count_words prints list of words appearing in the selected window section, or the whole window rare prints list of words appearing just once or twice in the selected window section procedures generates list of all procedures defined in the selected section of an edit window traceprocs Dropping this easy-use tool on an edit widow compiles the code in the window a form incorporating additional trace statements. These statements are selected in part by initial comments beginning with the special mark "---:". This mark can be followed by a comma-separated set of procedure names, the parameters to whose sucessive entries are to be traced in detail. (If a procedure name is not otherwise marked, only the fact of entries to the procedure will be traced, but not the associated parameter values.) Debug output is only written to SETL's output console if the program is then executed and crashes. This output is iniitally saved in a circular buffer able to hold roughly enough data to report on the last 100 procedure entries befor crash; data concerning earlier calls will have been over-written and hence will be unavailable.
showprocs capitalize capitalizes selected section of code window lower decapitalizes selected section of code window trace_entry Dropping this on a procedure header inserts code which prints a report on parameter values whenever the individual procedure is called. show_entries Dropping this on a procedure header inserts code which displays the parameter values in a Tk window whenever the procedure is called. When this facility is used, the procedure being traced should be called from within a main routine invoked by a Tk event, possibly a timed event. See Chapter 10 for more detail. parse Dropping this on a code window parses the selected section of the window, which is wrapped in program and end header and trailer lines before being parsed. If the section contains no parse errors, the message 'OK' is printed. Otherwise the number of errors is printed.
parsewin Dropping this on a code window parses the entire window. If there are
no parse errors, the message 'OK' is printed. Otherwise error indications are inserted at appropriate positions in the window. These inserted lines can be removed by dropping the 'cleanup' tool on the window.
parse_cleanup Dropping this on a code window removes all error-indication lines inserted by the 'parsewin' tool profile If the code in an edit window has just been executed with the "Profiler Dump" and "Debug to File' options both set, then dropping this tag on the window will display an execution-time profile of the window, keyed to its source text.
debug_watch debug_setup This tool sets up a program for line-trace debugging and postmortem assertion checking by inserting numbered trace-lines into it.
debug_cleanup This tool removes the insertions made by the debug_setup tool.
Personal1-4 The program called Personal_j which you compile will be called when the j-th memberof this group of for items is dropped on a code window. before using them, you must supply these programs, which can use the IDE_pak procedures. HTML-setup Dropping this tool on an edit window prints a version of the code in the window, in a form suitable for HTML display. (All SETL keywords are put into boldface) HTML-head Inserts standard HTML header/tail text into edit window HTML-table Inserts standard HTML table template into edit window frames Inserts standard HTML frames template into edit window make_reveal
Run Time and code dump switches Print run-time error messages in full ('Verbose') form; trace opcodes executed, generate error messages on assertion failures, profile execution, write debug information to file. The 'profile execution' option generates counts of the number of timese each line of source code and each internal SETL opcode is executed, and the number of copy operations forced. This information can be used either for debugging or for program optimization. If the 'Debug to File' switch is set, any requested 'Opcode' or 'Profile' information will be written to an auxiliary file named 'setl2.dbg' instead of being printed to the standard output console. Compilation dump switches Can be used to print compilation error messages in full ('Verbose') form; dump lexically scanned of program and/or or parse trace; dump abstract syntax tree, symbol table, procedure table, code quadruples, and/or interpretable code. SETL's moderate internal level of code optimization can be switched on and off. Output console coloring and fonts Colors can be selected for various kinds of run-time error messages and warnings, and the message window font and font size can be set Edit window coloring and fonts Colors can be selected for reserved words, quoted strings, comments, etc., and the edit window font and font size can be set use sort_pak;
x := [1,2,-5,10];
z := add_em_up(x);
print(z);
procedure add_em_up(u); k := 5; return merge_sort([0 +/u(1..j): j in [1..#u]]); end add_em_up;
Compilation of this string proceeds just as if it read
program anonymous;
use sort_pak;
x := [1,2,-5,10];
z := add_em_up(x);
print(z);
procedure add_em_up(u); return merge_sort(k * [0 +/u(1..j): j in [1..#u]]); end add_em_up;
end anonymous;
[-10, 5, 15, 40]
(But the compiled form of 'anonymous' is held in memory rather than being written to a file.) Then the (implied immediate) execution of 'anonymous' leaves values stored in the global variables which the compiler has associated with x, z, and add_em_up. Suppose that we subsequently eval another string, say
"w := add_em_up([-1,-10,10,1]) + x + z; print(w," ",j);"
The compiler will detect the fact that it has seen the global names x, z, and add_em_up before, so that they automatically capture their previous values, 'add_em_up' beinga procedure value. But the 'k' appearing in the procedure 'add_em_up' is local to that routine, not global. So the output produced will be
[-10, 5, 15, 40]
[-55, -5, -5, 0, 1, 2, -5, 10, -10, 5, 15, 40] <om>
package share_names; -- auxiliary package to cause sharing of names with dynamically 'eval'ed code
var shared_global; -- a shared global variable
end share_names;
package body share_names; -- auxiliary package to cause sharing of names with dynamically 'eval'ed code
end share_names;
program test; -- test to show variables common between static and dynamic namescopes
use share_names;
shared_global := 888;
eval("use share_names; print(\"shared_global dynamic value1: \",shared_global); shared_global := 999;");
print("shared_global static value: ",shared_global);
eval("use share_names; print(\"shared_global dynamic value2: \",shared_global);");
end test;
shared_global dynamic value1: 888
shared_global static value: 999
shared_global dynamic value2: 999
program test; -- second test to show variables common between static and dynamic namescopes
use share_names;
eval("use share_names; shared_global := f; procedure f(x); return cos(float(999 * x)); end f; ");
print("shared_global function call: ",shared_global(88));
end test;
shared_global function call: -0.68748617663