DSCN(ID:3789/dsc001)Generator for IPL-V codeDescriptive Name Compiler. This routine takes as its input a verbal definition (DSCN), in the form of an imperative sentence, of the routine to be compiled. It produces an IPL-V routine that is the translation, in the interpretive language, of that definition Related languages
References: Some experiments with a compiler that uses heuristic problem-solving techniques like those incorporated in the General Problem Solver (GPS) will be described in this report. The experiments were aimed at the dual objectives of throwing light on some methods of constructing more powerful programming languages and compilers, and of testing whether the task of writing a computer program can be regarded as a problem in the sense in which that term is used in GPS. The motivation for the compiler is supplied by a theory of problem solving that also provides the basic framework for GPS. A problem is a situation of the following kind: (1)--A partial description of a present and a desired situation, described in a state language, is given. (2)--A list of operators that can transform situations is given. Operators are named in a process language. (3)--A problem solution is a sequence of operators that will transform the present situation into the desired situation. Many techniques of problem solving can be subsumed under the following general paradigm: Means-end analysis. Given the present and desired objects, find a difference between them. Next find an operator relevant to the difference; determine if the operator can be applied to the present object. If so, apply it. (If not, describe the objects to which it would apply and transform the present object into an object of that kind-- a new desired object.) Take the new object thus obtained as the present object and repeat the process. A program can be interpreted as a sequence of operators (instructions) for transforming a present state of the computer into a desired state. The Heuristic Compiler (HC) makes use of the problem-solving schema described by taking its source language as the process language. In all cases, the target language, hence the process language, for HC is IPL-V, an interpretive list-processing language. HC works from either of two source languages, employed as the state languages for description of the programming problem. HC is itself coded in IPL-V, and has been run on the IBM-7090. At present HC consists of three general compiling routines: (1)--The State Description Compiler. This routine takes as its input a description (SDSC) of the contents of the relevant computer registers, before and after the routine to be compiled has been executed. It produces an IPL-V routine that will transform the input state description into the output state description. (2)--Descriptive Name Compiler. This routine takes as its input a verbal definition (DSCN), in the form of an imperative sentence, of the routine to be compiled. It produces an IPL-V routine that is the translation, in the interpretive language, of that definition. (3)--General Compiler. This is an executive routine that can use the SDSC compiler, the DSCN compiler, and others as subroutines. It takes as its input information about the routine to be compiled in either of the described forms. It then selects subroutines that can use this information to produce the desired IPL-V code. A computer routine can be defined by specifying the changes it produces in the contents of the storage locations it affects, or, what amounts to almost the same thing, by specifying the before-and-after conditions of these storage registers. A definition of this kind is not unequivocal, for programming is a synthetic, not an analytic task; there will generally be many programs to do the task. The SDSC Compiler applies means-end analysis in an attempt to find some one of these. The SDSC of a routine consists of a list of affected cells. For each affected cell, the SDSC specifies its input state and its output state. The routine matches the input states with the output states until it finds a difference. It searches a table of connections that associates with each difference a list of operators (previously compiled routines or .primitive instructions) that are relevant to that difference. It applies tentatively the relevant operator to the input state of the SDSC to be compiled, and determines the resulting output state. The application of the operator creates two new subproblems: Let Ia be the input state of the routine to be compiled, Oa its output state, Ib the input state of the operator, and Ob its output state. The original problem was to transform Ia into Oa. The new problems are: (1) to transform Ia into Ib (i.e., to establish the input conditions for application of the operator), and (2) to transform Ob into Oa (i.e., to transform the output state of the operator into the required output state of the routine to he compiled). Either of these new problems may reduce to the identity transformation, in which case that part of the problem is solved. If this reduction does not occur, then the same steps are applied to the new subproblem. The input statements to the DSCN Compiler, in the form of imperative sentences, resemble the input statements to familiar compilers like FORTRAN and ALGOL. The method of compilation, however, is heuristic rather than algorithmic. It involves, again, comparing the source sentence with the descriptive names of primitive processes and routines previously compiled; selecting an alreadycompiled routine with a similar name, and successively modifying it until the desired routine is obtained. When the source statements for the DSCN Compiler are at all complex, involving conditional t r a n s f e r s , the compiler constructs a flow diagram as an overall plan for its compilation. The segments of code corresponding to each of the parts of the flow diagram are then compiled separately, and assembled by associating them with the flow diagram. The ability of the Heuristic Compiler to produce programs from state descriptions hinges on the structure of the language in which the state descriptions are formulated. Using the list-processing capacities of IPL-V description lists are stored in memory that specify in as much detail as is desired the structure of the information contained in particular fields of individual registers of the computer being programmed. Thus, the compiler has access to the scheme for encoding information within individual computer words, and the encoding conventions are explicit rather than implicit as in the usual compiling schemes. For this reason, the Heuristic Compiler is a suitable basis for further experiments aimed at automating those problem-solving activities of the programmer which involve the selection of an appropriate representation of information in the computer. in Artificial intelligence and self-organizing systems view details |