2.PAK(ID:663/pak001)AI language with coroutines.AI language with coroutines and pattern matching Replacement for 1.PAK after 1.pak was found wanting, also took advantage of other developments in AI Related languages
References: Introduction In 1973, a programming language to facilitate AI research at the University of Toronto was designed and implemented. Although it was SNOBOL based, 1.PAK offered many features found in the more prominent AI languages such as PLANNER, CONNIVER, QA4 and SAIL since these languages greatly influenced its design. It thus possessed such features as a data base composed of directed labelled graphs, pattern directed information retrieval, pattern-invoked function calls and generators. 1.PAK shared another feature with other AI languages; it was a disappointment. The language, used extensively in a graduate course on AI and for a Master's thesis, was heavily criticized due to its lack of good primitives. The primitives it did provide were ill-defined and although they seemed orthogonal, the combination of some primitives yielded unexpected results. In addition, some of the primitives did too much for the user. This resulted in the user losing control of what was happening in the program and having to depend on kludges to constrain such primitives. It should be noted that such criticisms apply not only to l.PAK but to other AI languages as well. The problem thus seems one of finding "good" primitives for AI applications. This paper describes a successor to l.PAK which tries to provide some of these primitives. 2.PAK is a successor in the sense that experience gained from l.PAK has been used in the design of the new language. 2.PAK is not an extension of l.PAK. Extract: Language goals Language goals 2.PAK's goals center around two major objectives. The first is to provide a good set of primitives suitable for AI applications. The problem here rests with the choosing of the primitives to be offered. One must be careful not to choose primitives that are too low-level; otherwise the convenience of the language user'suffers. On the other hand, the primitives must not be too high-level; otherwise the adaptability of the language suffers. As example, one could consider LISP's primitives as being too low-level for AI applications and PLANNER'S primitives as being too high-level. It was the dissatisfaction with LISP that sparked the design of higher level AI languages so that a user could program his algorithms more conveniently. However, PLANNER'S automatic backtracking and pattern directed function calls proved to be so high level and powerful that they lacked the finesse the user required and subsequently could not be used. Thus the ideal solution is to find primitives that strike a happy balance between tbe two extremes and provide facilities within the language for the user to easily define any higher level primitives that may be needed for a specific application. The search for these primitives was centered around some of the previously mentioned AI languages and others including QLISP and SIMULA. Features offered by these languages were examined and a set of primitives was abstracted. The second objective is one that is overlooked by most AI languages. 2.PAK tries to accomodate principles obtained from research into programming languages in general. Such qualities as efficiency, readability, reliability and understandability are too important to any language to be omitted from the design stage and then be expected to somehow emerge when the language is completed. We believe that AI languages can greatly benefit from the experiences of programming languages in general, and that they should not set themselves apart and have to reinvent the wheel. In the light of these two major objectives, the general goals of the language are: 1) Efficiency - of program creation and execution. 2) Natural Syntax - to enhance readability of programs. 3) Understandability and Readability - through the use of simple semantics. 4) Minimality - the language should be concise. 5) Involution - consistent use of language features. 6) Orthogonality - independence of language features. 7) Simplicity - to aid in program construction. 8) Implementability - the language should be implementable cheaply and efficiently. More specific goals in terms of desired features include: 1) A wide variety of data types. 2) Generalized pattern matching without restriction to a set of data types chosen by the language designer. 3) Generalized control structures (i.e. hierarchical and heterarchical control structures). 4) Good abstraction capabilities to aid in defining higher level primitives required by specific applications. 5) Backtracking as it applies to hierarchical and heterarchical control structures. 6) Flexibility to either compile or interpret expressions within the program. 7) Strong typing of variables whenever possible to allow the system to check for "illegal datatype" errors and thereby reduce them. 8) Interactive facilities and tracing facilities to aid in debugging and program execution monitoring. Extract: Language Overview Language Overview 2.PAK is a block structured language whose main features will be discussed according to the divisions: data types, abstraction facilities, basic statements, global control structures, backtracking, pattern matching and miscellaneous. A more detailed description of 2.PAK is available in [12] . Data Types 2.PAK offers a wide variety of data types so that the user can choose what is best suited for the task at hand. There are the standard data types such as booleans, integers, reals, strings, references (i.e. pointers to user defined records or coroutines), lists and arrays. In addition there exist unevaluated expressions and hash tables as in SNOBOL, patterns which can be matched or combined to form new patterns, and records, which are user defined aggregates of basic types. For example: record BINARY_TREE( ref (BINARY_TREE) LLINK, RLINK ; string LABEL ) ; defines a record which can be used to construct string labelled binary trees. 2.PAK also possesses a data base in the form of a directed graph with labelled nodes and edges. Such a structure has shown itself to be very convenient as a representational tool, especially for semantic nets, and is very similar to SAIL's triples, PLANNER'S assertions, CONNIVER's items or QLISP's tuples and vectors. The structure provides a restricted form of associativity applicable to the nodes of the data base, i.e. for a given node, one can determine all the nodes that are related to that node by means of edges either leaving or entering that node. Thus associativity exists for the nodes of the data base, but not for the edges. This form of associativity is clearly less expensive than that provided by SAIL's triples. The basic units of the data base are the nodes, and operations exist to add or delete nodes to or from the data base, add or delete edges to or from a specific node, generate edge-node pairs whose edges match a specified pattern and enter or leave a specified node and all edges and nodes within a given radius. All 2.PAK variables must be declared and typed to alleviate the problem caused by illegal datatypes as arguments to operations. One can view type declarations as intentions of what the type of the variable is to be. The system will then provide the necessary checking either at compile or run time. If the type of a variable is not known or if it can be of more than one type, one can declare it to be of type var which allows that variable to take values of any type. Abstraction Facilities An abstraction facility is the capability of grouping together entities into a unit that can be assigned a name for reference purposes. For data types, record declaration is an abstraction facility since one can construct the required record from primitive data types and then use that record as a primitive data item of the language. For 2.PAK statements, there exist three types of abstraction facilities: procedures, function procedures and coroutines. Procedures and function procedures are defined as in most programming languages. Coroutines differ from procedures in that they can be used to achieve heterarchical control structures (see section 3.4). In addition, variables of a suspended coroutine instance can be examined or altered. Lastly, macros provide an abstraction facility for character strings within the text of the source program. For example: macro '?' replaced by '%' ; will replace all occurrences of "1' , following the macro definition, by '%'. Basic Statements The basic statements of 2.PAK are the assignment statement, statements that control local sequencing (i.e. if, while and case) and the I/O statements. Most of these statements are fairly standard as is shown by the examples: if X = Y then SAME := SAME + 1 ; end ; if X < Y then Y := X ; else COUNT := COUNT + 1 ; end ; while FLAG - true do read X ; write X ; end ; [ case PRIMARY COLOUR of 'RED' : ... ; 'YELLOW' : ... ; 'BLUE' : ... ; else : MESSAGE := 'NOT A PRIMARY COLOUR.' ; end ; The example case statement will examine the value of PRIMARY_COLOUR, which must be of string type7 and will execute the case containing that value as a case label. If the value is not in the range of specified case labels, the case having else as a case label will be executed. Global Control Structures Global control deals with the primitives that transfer control to or from procedures and coroutines. For procedures there exists the hierarchical control structure provided by the procedure call, possibly recursive, and the return statement. As is the norm for procedures, a procedure's environment is destroyed when a return is executed. On the other hand, coroutines survive transfers of control and are merely suspended until control is returned. Execution then commences at the point where the coroutine was last suspended. For coroutines, 2.PAK offers two types of control primitives which are in many respects similar to those of SIMULA. The hierarchical type, provided by invoke and detach and similar to the call/ return of procedures, is ideal when it is necessary to have a coroutine execute under the control of some other block, i.e. as is the case for generators. Thus the invoke statement, like a call, carries information to the invoked coroutine as to where a detach should return. However, the heterarchical primitive resume carries no such information. The resumed co-routine has no idea who resumed it and assumes complete control of the computation. Thus one could consider different coroutines as representing different environments and use resume to transfer control among these environments. Pattern Matching 2.PAK offers a generalized pattern matching facility not restricted to a set of data types chosen by the language designer, as is often the case. This is achieved by letting the user have the facility for defining the semantics of required pattern matching primitives and their evaluation sequences. Defining the semantics of pattern matching primitives reduces to defining a set of functions that operate on the position of a cursor within the subject structure. Such an approach to pattern matching is applicable to strings, lists, graphs or any user defined structure. The evaluation sequence of a pattern matching primitive specifies when that primitive is to be evaluated. The three possibilities are: evaluate when the primitive is encountered while the matcher is moving in the forward direction (i.e. moving left to right through the pattern), evaluate when encountered while moving in the backwards direction (i.e. backtracking), and evaluate whenever encountered. For example, the string pattern matching primitives FENCE and SUCCEED of SNOBOL exhibit the second type of evaluation sequence, while the edge expressions of l.PAK patterns show the third type. A pattern in 2.PAK is therefore composed of a sequence of boolean expressions with associated evaluation sequences. The 2.PAK pattern matcher executes the pattern in a backtracking mode whereby if an expression evaluates to true the matcher proceeds forward to the next expression; if false the matcher backtracks . For the convenience of the user, some of the more basic pattern matching primitives for strings, lists, and graphs are provided. However, these primitives should by no means be taken as dogmatic and one is still free to define his own. Sample 2.PAK patterns are found in section 4.2. Backtracking 2.PAK backtracking primitives are completely disjoint from control primitives since such a separation allows one to combine the two in the manner that produces the desired result in the most efficient way. Backtracking is therefore viewed as the means for manipulating state changes made within what is termed a context. Primitives provide facilities forentering a new context, for specifying what changes are to be backtrackable within a context, and when to back up to the previous context and what to do with the bacitrackable changes. The context feature is less prominent than CONNIVER's (where everything is carried out in a backtrackable context) and we consider it more economical since the user can choose when to use the feature. In addition, there are primitives that can be used for the heterarchical control structure provided by coroutines. Preserve binds a context to a coroutine instance and restore restores the bound context of a specified coroutine instance. Thus restore can be used in conduction with the resume statement to provide the facility of transferring control within multiple environments, each with it's own context. Another use is the evaluation of expressions outside the current environment. This can be easily achieved by restoring the desired environment, evaluating the expression and then restoring the original environment. Note that for such a task no transfer of control is necessary and that none takes place. Miscellaneous In addition to the described features, 2.PAK provides miscellaneous built-in functions to aid the user. These functions include: apply - Similar to the apply function of SNOBOL, this function provides a dynamic function calling facility. compile - This function accepts as argument a string representation of a 2.PAK expression and returns its equivalent unevaluated expression. eval - This function evaluates a 2.PAK unevaluated expression and returns the produced result. trace - This function allows the user to enable tracing of changes made to a specified variable or transfers or control to or from a specific procedure or coroutine. The language also provides toggles to facilitate extensive tracing. For example, setting the toggle .CTRACE. to 10 will result in the tracing of the next 10 transfers of control made by any coroutine of the program. Other toggles include: trace all variable changes (.TRACE.), trace all function calls and returns (.FTRACE.), and trace the evaluation sequence of pattern matches (.PATTERN.). in IJCAI-75 Proceedings of the 4th International Joint Conference on Artificial Intelligence, 1975 Tbilisi, USSR view details The complexity of the above descriptions (especially that for "detach") is indicative of the complexity of the definition of Simula and arises from the fact that the run-time structure of a Simula program is a complex tree structure. During the design of the sequence control aspect of ACL, the sequence control model was used not only to describe Simula from its standard, but also to describe other languages whose semantics are based on the accounts of Simula presented by Dahl and Hoare[5], and Wang and Dahl[33]. These latter accounts are more easily understood than the Simula standard and have been regarded as a more accessible definition of the language. For example, the 2.PAK language[20] has an instance creation operation based on the Dahl and Hoare description of the corresponding Simula primitive; the description of the 2.PAK feature is as follows in the sequence control model: d = { A <- create d; A.caller <- current; return A; enter A} and the corresponding detach operation is now: detach = {enter current.caller} which are clearly markedly different from the Simula features described earlier. Furthermore, the features described by Wang and Dahl are even more different from the original Simula features and hence even more confusing for someone trying to understand the Simula language. These differences illustrate the importance of comparative models such as the sequence control model in understanding existing languages and descriptions of them. Abstract: Design is a difficult human activity which typically involves choices being made from among a number of design alternatives; good design results from explicit choices being made from among clearly known design alternatives. Abstraction, and hence modelling, is a powerful tool in the process of comparing design alternatives. This paper describes a number of applications of a range of models being used in design tasks related to software engineering activities. These applications include the design of programming languages and the design of a number of tools to support software engineering activities in Hingston, P. F. (Ed.) Proc. 1994 Western Australian Computer Science Symposium (Claremont, Western Australia, September 1994) view details |