Misplaced Pages

#768231

62-495: SAIL's main feature is a symbolic data system based upon an associative store based on LEAP by Jerry Feldman and Paul Rovner. Items may be stored as unordered sets or as associations (triples). Other features include processes, procedure variables, events and interrupts, contexts, backtracking and record garbage collection . It also has block-structured macros, a coroutining facility and some new data types intended for building search trees and association lists. The GOGOL compiler

124-476: A conditional compilation system using statements, as opposed to pre-processor directives as found in C. IFCR would compile the blocks between the corresponding THENC and ELSEC or ENDC . The condition in the IFCR must be known at compile time, so, like C, was normally a DEFINE d value. The main difference between SAIL and other ALGOL-derived languages was its inclusion of the associative store from

186-406: A choice point. If the choice point has an associated time later than that of the variable, it is unnecessary to revert the variable when the choice point is backtracked, as it was changed before the choice point occurred. Local variable In computer science , a local variable is a variable that is given local scope . A local variable reference in the function or block in which it

248-511: A data type had only recently been introduced when SAIL was being written. This feature thus shows the signs of being "bolted on" to the language syntax. For instance a record structure was defined using the RECORD!CLASS statement: RECORD!CLASS person (STRING name, address; INTEGER accountnum; REAL balance) . This statement worked in a fashion similar to the RECORD statement in Pascal, defining

310-456: A definite conclusion, it should return false . An incorrect true result may cause the backtrack procedure to miss some valid solutions. The procedure may assume that reject ( P , t ) returned false for every ancestor t of c in the search tree. On the other hand, the efficiency of the backtracking algorithm depends on reject returning true for candidates that are as close to the root as possible. If reject always returns false ,

372-650: A document formatting system called PUB, and BRIGHT, a clinical database project sponsored by the National Institutes of Health . In 1978, there were half a dozen different operating systems for the PDP-10: ITS (MIT), WAITS (Stanford), TOPS-10 (DEC), CMU TOPS-10 (Carnegie Mellon), TENEX ( BBN ), Tymcom-X (Tymshare), and TOPS-20 (DEC, based on TENEX). SAIL was ported from WAITS to ITS so that MIT researchers could make use of software developed at Stanford University . Every port usually required

434-477: A fashion similar to C's #define macros. A difference was that the delimiters around the substitution had to be defined, for instance REQUIRE "[][]" DELIMITERS;DEFINE maxSize=[100]; . One common use of these macros was to define character constants like CRLF , as these were not part of the basic language. Another was to redefine the COMMENT statement to the shorter ! . The system also included

496-421: A greater impact on subsequent choices). One could also allow the next function to choose which variable should be assigned when extending a partial candidate, based on the values of the variables already assigned by it. Further improvements can be obtained by the technique of constraint propagation . In addition to retaining minimal recovery values used in backing up, backtracking implementations commonly keep

558-478: A label. The CASE was similar to switch in C, but normally used a somewhat different syntax, like CASE i OF ("Zero","One","Two"); , which returns the appropriate string based on the value of i. If one wanted to test explicit values in the CASE, the values had to be in square brackets: This code will ignore values like 1 to 3, and only return a value for the listed values. Note that

620-431: A language was its use of associative storage, more commonly known today as a Map or Dictionary. In LEAP, one could set the value of a field in a type using a triple, with the first entry being the variable name, the second being the field name, and the third the value. Further improvements were added by Russell Taylor, Jim Low and Hana Samet, who added processes, procedure variables, interrupts, context, matching procedures,

682-482: A lexical or dynamic scope , though lexical (static) scoping is far more common. In lexical scoping (or lexical scope; also called static scoping or static scope), if a variable name's scope is a certain block, then its scope is the program text of the block definition: within that block's text, the variable name exists, and is bound to the variable's value, but outside that block's text, the variable name does not exist. By contrast, in dynamic scoping (or dynamic scope), if

SECTION 10

#1732776094769

744-475: A list of integers x = ( x [1], x [2], …, x [ n ]) , each in some range {1, 2, …, m }, that satisfies some arbitrary constraint (Boolean function) F . For this class of problems, the instance data P would be the integers m and n , and the predicate F . In a typical backtracking solution to this problem, one could define a partial candidate as a list of integers c = ( c [1], c [2], …, c [k]) , for any k between 0 and n , that are to be assigned to

806-410: A new macro system, and other features. Development then passed to Taylor, John Reiser and Robert Smith, who added a debugger, a system-level print statement, records, and performed the conversion from Standord's own SUAI to TENEX . It was later ported to DEC's TOPS-10 as well, while the original TENEX version worked without modification under TOPS-20 . Like many ALGOL systems, and the later Pascal ,

868-418: A number of standard functions like square root , all of the common math operators, and was otherwise similar to most ALGOL derivatives for normal programming. Strings were manipulated using array slicing , with aStr[i TO j] returning the substring with characters from i to j, or aStr[i FOR j] which returned the substring starting at i and running for j characters. The INF (inity) keyword represented

930-425: A set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps. Conceptually, the partial candidates are represented as the nodes of a tree structure , the potential search tree. Each partial candidate is the parent of the candidates that differ from it by

992-399: A single extension step; the leaves of the tree are the partial candidates that cannot be extended any further. The backtracking algorithm traverses this search tree recursively , from the root down, in depth-first order . At each node c , the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole sub-tree rooted at c is skipped ( pruned ). Otherwise,

1054-500: A solution to the given instance P . The algorithm can be modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of partial candidates, or after spending a given amount of CPU time. Examples where backtracking can be used to solve puzzles or problems include: The following is an example where backtracking is used for the constraint satisfaction problem : The general constraint satisfaction problem consists in finding

1116-422: A specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility. The backtracking algorithm enumerates

1178-461: A variable name's scope is a certain block, then its scope is that block and all functions transitively called by that block (except when overridden again by another declaration); after the block ends, the variable name does not exist. Some languages, like Perl and Common Lisp , allow the programmer to choose static or dynamic scoping when defining or redefining a variable. Examples of languages that use dynamic scoping include Logo , Emacs lisp , and

1240-415: A variable trail, to record value change history. An efficient implementation will avoid creating a variable trail entry between two successive changes when there is no choice point, as the backtracking will erase all of the changes as a single operation. An alternative to the variable trail is to keep a timestamp of when the last change was made to the variable. The timestamp is compared to the timestamp of

1302-572: A way to detect this situation, at least for some candidates c , without enumerating all those m n -tuples. For example, if F is the conjunction of several Boolean predicates, F = F [1] ∧ F [2] ∧ … ∧ F [ p ] , and each F [ i ] depends only on a small subset of the variables x [1], …, x [ n ] , then the reject procedure could simply check the terms F [ i ] that depend only on variables x [1], …, x [ k ] , and return true if any of those terms returns false . In fact, reject needs only check those terms that do depend on x [ k ], since

SECTION 20

#1732776094769

1364-400: Is applicable, however, backtracking is often much faster than brute-force enumeration of all complete candidates, since it can eliminate many candidates with a single test. Backtracking is an important tool for solving constraint satisfaction problems , such as crosswords , verbal arithmetic , Sudoku , and many other puzzles. It is often the most convenient technique for parsing , for

1426-645: Is declared overrides the same variable name in the larger scope. In programming languages with only two levels of visibility, local variables are contrasted with global variables . On the other hand, many ALGOL -derived languages allow any number of nested levels of visibility, with private variables, functions, constants and types hidden within them, either by nested blocks or nested functions . Local variables are fundamental to procedural programming , and more generally modular programming : variables of local scope are used to avoid issues with side-effects that can occur with global variables . Local variables may have

1488-520: Is distinct from other usages of the static keyword , which has several different meanings in various languages. Perl supports both dynamic and lexically-scoped local variables. The keyword local is used to define local dynamically-scoped variables, while my is used for local lexically-scoped variables. Since dynamic scoping is less common today, the Perl documentation warns that " local isn't what most people think of as “local”.". Instead,

1550-484: Is part of stdlib as opposed to being part of the language itself as in SAIL. SAIL's input/output system was based on the idea of numbered "channels" in a fashion somewhat similar to the scanner entries. To open a file, one first called GETCHAN to return a value of a free channel, and then OPEN ed it with various parameters to describe the file and modes of operation. RELEASE was equivalent to close. Once opened,

1612-609: The FORWARD qualifier, used to insert forward declarations , typically when two procedures call each other. RETURN worked as in C, exiting the procedure and returning to the caller, as well as optionally returning a value if the procedure uses one. Parameters passed to the procedures could be by VALUE or REFERENCE , the later allowing values to be passed back. The basic variable types in SAIL are integers , reals (floating point), booleans , and strings . Type conversions were automatic, so INTEGER i;i←SQRT(5); would convert

1674-592: The Father field to "Harry". This results in a triple of the form (Father, Tom, Harry). The associated libraries could then find all the Family_Member s with "Harry" as the Father , perhaps returning "Tom" and "Alice". The following code, found in the Tutorial, converts an input string to upper case. A number of interesting software systems were coded in SAIL, including some early versions of FTP and TeX ,

1736-476: The INCHWL function was an INPUT hard-wired to the user terminal and always open, and it returns its break character in the system variable !SKIP! . The PRINT function normally output to the same terminal channel, but could also be directed at any other opened channel. As a systems programming language, performance was important and to help with this, SAIL included a DEFINE which used string-replacement in

1798-407: The local keyword gives a temporary, dynamically-scoped value to a global (package) variable, which lasts until the end of the enclosing block. However, the variable is visible to any function called from within the block. To create lexically-scoped local variables, use the my operator instead. To understand how it works consider the following code: this will output: This happens since

1860-417: The knapsack problem and other combinatorial optimization problems. It is also the program execution strategy used in the programming languages Icon , Planner and Prolog . Backtracking depends on user-given " black box procedures " that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than

1922-550: The LEAP language. This system provided a system that allowed data to be placed in record-like structures and then saved, retrieved and searched. In this respect it was similar to the data handling features in COBOL . The basis for the store was the association or triple , which allowed a data value to be associated with a named slot in a record. For instance, one might make a record of the type Family_Member with Name "Tom" and set

SAIL (programming language) - Misplaced Pages Continue

1984-459: The actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test. In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters , root , reject , accept , first , next , and output . These procedures should take

2046-405: The algorithm (1) checks whether c itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees of c . The two tests and the children of each node are defined by user-given procedures. Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of

2108-439: The algorithm will still find all solutions, but it will be equivalent to a brute-force search. The accept procedure should return true if c is a complete and valid solution for the problem instance P , and false otherwise. It may assume that the partial candidate c and all its ancestors in the tree have passed the reject test. The general pseudo-code above does not assume that the valid solutions are always leaves of

2170-457: The basic structure of SAIL is based on the block , which is denoted by the code between the keywords BEGIN and END . Within a block there is further structure, with the declarations of local variables at the top, if any, and the code, or statements , following. In contrast to most dialects, SAIL allowed one to place a string after the BEGIN , like BEGIN "program" , and then end

2232-405: The block in which they are declared. Programming languages that employ call by value semantics provide a called subroutine with its own local copy of the arguments passed to it. In most languages, these local parameters are treated the same as other local variables within the subroutine. In contrast, call by reference and call by name semantics allow the parameters to act as aliases of

2294-464: The block with END "program" . The compiler would use these, if entered, to check for proper bracketing. SAIL did not include the equivalent of a PROGRAM block as in Pascal, nor a main as in C, execution started with the first line of code in the outermost block. Standard statements included IF...THEN...ELSE , FOR...STEP...UNTIL...DO , WHILE...DO for top-tested loops, WHILE...UNTIL for bottom-tested, and GOTO which used

2356-585: The call next ( P , s ) should return the next sibling of node s , in that order. Both functions should return a distinctive "NULL" candidate, if the requested child does not exist. Together, the root , first , and next functions define the set of partial candidates and the potential search tree. They should be chosen so that every solution of P occurs somewhere in the tree, and no partial candidate occurs more than once. Moreover, they should admit an efficient and effective reject predicate. The pseudo-code above will call output for all candidates that are

2418-422: The end of the string, so one could aStr[i TO INF] to return everything from i on. String functions and operators included EQU for testing if two strings were equal, the ampersand for concatenation, LENGTH , and LOP which removes the first character from the string. There was no way to compare strings other than EQU , operators like < were defined only for numbers. The concept of records as

2480-582: The file could be read, subject to the scanning rules noted above, by calling INPUT and looking for the end-of-file. Files did not have names as part of the OPEN, instead, LOOKUP could be used to point a channel at a given file, ENTER made a new file associated with a channel, and RENAME allowed an existing file name to be changed. One can open an existing file for writing using GETCHAN... OPEN... LOOKUP... ENTER . There were numerous special handlers and variables that were used during I/O. For instance,

2542-434: The first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it

SAIL (programming language) - Misplaced Pages Continue

2604-429: The first k variables x [1], x [2], …, x [ k ] . The root candidate would then be the empty list (). The first and next procedures would then be Here length ( c ) is the number of elements in the list c . The call reject ( P , c ) should return true if the constraint F cannot be satisfied by any list of n integers that begins with the k elements of c . For backtracking to be effective, there must be

2666-452: The function also have access to the (single, statically allocated ) variable. In all of the above languages, static variables are declared as such with a special storage class keyword (e.g., static ). Static locals in global functions have the same lifetime as static global variables , because their value remains in memory for the life of the program, but have function scope (not global scope), as with automatic local variables. This

2728-410: The global variable $ a is modified to a new temporary (local) meaning inside f() , but the global value is restored upon leaving the scope of f() . Using my in this case instead of local would have printed 1 three times since in that case the $ a variable would be limited to the static scope of the function f() and not seen by g() . Randal L. Schwartz and Tom Phoenix argue that

2790-412: The instance data P as a parameter and should do the following: The backtracking algorithm reduces the problem to the call backtrack ( P , root ( P )), where backtrack is the following recursive procedure: The reject procedure should be a Boolean-valued function that returns true only if it is certain that no possible extension of c is a valid solution for P . If the procedure cannot reach

2852-440: The last item cannot have a semicolon following. DONE exited from a block, typically used in loops, and CONTINUE returned to the top of the block. An infinite loop was typically implemented with WHILE TRUE DO... . Procedures were implemented in a fashion similar to the C programming language , with the return type, if any, in front of the name, for instance, STRING PROCEDURE toUpper(STRING originalStr);BEGIN... . Note

2914-563: The name file of a person, for instance, the syntax was PRINT(person:name[rp]); . In addition to basic string functionality, SAIL included a string scanner system as part of the basic language. SCAN worked on string variables, while the otherwise similar INPUT was used to scan strings being read from a file. Both used a system known as a "break table" which consisted of a set of characters that represented places to stop reading, examples include linefeeds, various whitespace, and punctuation. These tables were stored in special structures, and

2976-564: The operator local should have had a different name like save . Ruby as a language was inspired also by Perl, but in this case, the notation was made simpler: a global variable name must be preceded by a $ sign, like $ variable_name , while a local variable has simply no $ sign in front of its name, like variable_name (while in perl all scalar values have a $ in front). Note that Ruby only provides built-in support for statically-scoped local variables like Perl's my , not dynamically-scoped local variables like Perl's local . There

3038-494: The opposite, demanding the procedure have no local variables at all, not allowing GOTO out of the function, and could not refer to enclosing procedure's variables. These directives could avoid the requirement of filling out a complete activation record , thereby improving performance. This also had the side-effect of meaning that variables declared within a procedure that was not marked RECURSIVE would not be reset between calls, acting similar to C's static . SAIL also included

3100-440: The potential search tree. In other words, it admits the possibility that a valid solution for P can be further extended to yield other valid solutions. The first and next procedures are used by the backtracking algorithm to enumerate the children of a node c of the tree, that is, the candidates that differ from c by a single extension step. The call first ( P , c ) should yield the first child of c , in some order; and

3162-522: The rewriting of I/O code in each application. A machine-independent version of SAIL called MAINSAIL was developed in the late 1970s and was used to develop many eCAD design tools during the 1980s. MAINSAIL was easily portable to new processors and operating systems, and was still in limited use as of 2005. Backtracking Backtracking is a class of algorithms for finding solutions to some computational problems , notably constraint satisfaction problems , that incrementally builds candidates to

SECTION 50

#1732776094769

3224-584: The shell languages bash , dash , and the MirBSD Korn shell ( mksh )'s "local" declaration. Most other languages provide lexically scoped local variables. In most languages, local variables are automatic variables stored on the call stack directly. This means that when a recursive function calls itself, local variables in each instance of the function are given distinct addresses . Hence variables of this scope can be declared, written to, and read, without any risk of side-effects to functions outside of

3286-452: The solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic textbook example of the use of backtracking is the eight queens puzzle , that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in

3348-435: The string) and finally the "modes", flags that indicated how the system should work. Once set, the program could then repeatedly call SCAN or INPUT and be returned complete strings. This included a reference parameter, normally brkchar, that contained the character that caused the break, allowing one to test, for instance, for end-of-file characters. The system is conceptually similar to C's strtok functionality, which

3410-418: The system allowed only 54 of these, a number that is not explained in the documentation. To build a new table, one first called GETBREAK which returned the next free slot in the table, or "table number". This would be followed by a SETBREAK , which took the table number, a string with the break characters, another string of "omit characters" which were simply ignored during reading (as if they were not in

3472-481: The template for the record. To create a record, one used the NEW!RECORD statement, which returned a RECORD!POINTER . Pointers were typed, and could be typed to more than one type, for instance, RECORD POINTER (person,university) rp; defines rp, a pointer to either a person or university record. Pointers could also be declared to point to ANY!CLASS . Accessing the data in a record was similarly idiosyncratic; to print

3534-420: The terms that depend only on x [1], …, x [ k − 1] will have been tested further up in the search tree. Assuming that reject is implemented as above, then accept ( P , c ) needs only check whether c is complete, that is, whether it has n elements. It is generally better to order the list of variables so that it begins with the most critical ones (i.e. the ones with fewest value options, or which have

3596-410: The uncommon use of the semicolon here, whereas Pascal would immediately follow with a block, typically a BEGIN . In order to improve performance, SAIL added two procedure qualifiers, SIMPLE and RECURSIVE . RECURSIVE told the compiler that the procedure might call itself, and thus its local variables had to be written to the stack, not just the subroutine return information. SIMPLE did

3658-482: The value 5 to a double as that is what SQRT requires, and then cast the result to an integer. Any of these types can be turned into an array by adding the ARRAY qualifier and placing the array bounds in brackets, for instance, REAL ARRAY weeks[1:52]); . SAIL supported 1-d and 2-d arrays. The language used the left-arrow for assignment, ← , or the underscore on platforms that did not have Stanford ASCII . It included

3720-415: The values passed as arguments, allowing the subroutine to modify variables outside its own scope. A special type of local variable, called a static local, is available in many mainstream languages (including C / C++ , Visual Basic , VB.NET and PHP ) which allows a value to be retained from one call of the function to another – it is a static variable with local scope. In this case, recursive calls to

3782-512: Was originally written by Bill McKeeman on the PDP-1 . It was essentially an integer -only version of ALGOL-60 with a number of additions to provide direct access to the memory and other hardware to allow it to be used as a systems programming language . It reduced arrays to a single dimension, removed any ability to perform dynamic memory allocations, but did add some additional string functionality. A greatly updated version by John Sauter, GOGOL II,

SECTION 60

#1732776094769

3844-652: Was written as part of a port of the underlying operating system from ODIN to THOR. When the Stanford AI Lab received their PDP-6 , Sauter, Pettit and (mostly) Dan Swinehart wrote GOGOL III for the new machine. Swinehart, joined by Robert Sproull, merged the GOGOL syntax with additions from the contemporary versions of the LEAP language to produce the first version of SAIL in November 1969. The main feature of LEAP as

#768231