Gödel (programming language)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Gödel
Paradigm(s) declarative, logic
Designed by John Lloyd & Patricia Hill
Developer John Lloyd & Patricia Hill
Appeared in 1992
Stable release 1.5 / August 11, 1995 (1995-08-11)
Typing discipline strong
Dialects Gödel with Generic (Parametrised) Modules
OS Unix-like
License Non-commercial research/educational use only

Gödel is a general-purpose, declarative programming language based on one of the four main programming paradigms, namely, logic programming. It was developed by Patricia M. Hill and John W. Lloyd. Basic ideas and features of Gödel are mainly taken from Prolog language. It is named in honour of logician Kurt Gödel, although the acronym ‘God's Own DEclarative Language' is sometimes used.

Gödel is a strongly typed system based on many-sorted logic with parametric polymorphism. It involves many data types and modules, supports integers and floating-point numbers of an arbitrary precision (including infinite precision). The Gödel language enables to solve constraint problems over finite domains of integers or rationals. It supports processing of finite sets. It offers a flexible computation rule and a pruning operator which generalises the commit of the concurrent logic programming languages. The declarative nature of Gödel programs makes Gödel well suited as a teaching language (because students can concentrate much more on writing down what it is they want to compute without being so concerned about how to compute it). Gödel narrows the gap between theory and practice in logic programming, since it reduces a significant number of non-logical features without useful semantics, and so Gödel language provides a bridge between theory and practice. Gödel's meta-logical facilities provide significant support for meta-programs that do analysis, transformation, compilation, verification, debugging, and so on. Gödel's meta-programs participate in building of some desirable applications: compiler-generators and declarative debuggers to debug Gödel programs (declarative debugging is an attractive debugging technique which only requires that the programmer know the intended interpretation of a program to locate certain bugs and, for example, knowledge of the procedural behaviour of the Gödel system is not needed). Gödel more easily allows a parallel implementation since there are only a couple of non-logical features to complicate matters.

Very detailed overview of Gödel programming language, precise descriptions and formal definitions of the syntax and semantics of the language with many examples and background material on logic can be found in the book.[1]

About the authors[edit]

Patricia M. Hill is a Senior Research Fellow in the Computational Logic Group at the University of Leeds. She has been doing research in logic programming since 1986.[2]

John W. Lloyd is a Professor in Research School of Computer Science at the Australian National University; he is the author of Foundations of Logic Programming.[3]

General principles of the Gödel programming language[edit]

Currently in the information (computer or digital) age, programming languages are crucial communication tools to computers, mobile (smart) telephones and other devices. Programming languages can be divided into three dominant groups: general purpose programming languages, domain specific programming languages and modelling languages. Usage of a particular type of programming language depends on the project and knowledge of particular languages. The initial point of the programming process is the understanding of a particular problem that a programmer is trying to solve. The problem is then formalised as an intended interpretation of a language which in case of Gödel is a first-order language. The intended interpretation specifies the various domains and the meaning of the symbols of the language in these domains.

The first-order language (as Gödel's intended interpretation) is, roughly speaking, a specific model of computation arising from logic programming paradigm, which is one of the four main paradigms, i.e. fundamental style of computing programming. Other paradigms are object-oriented, imperative and functional (with concrete models of computation, particularly, Turing machine for object-oriented and imperative programming, λ-calculus for functional programming paradigm. The first-order logic, sometimes called as first-order predicate calculus, the lower predicate calculus, quantification theory, and less precise as predicate logic, is a formal system used in mathematics, philosophy, linguistics and computer science. Unlike propositional logic the first-order logic uses quantified variables. The first-order logic satisfies several meta-logical theorems that make it open to analysis in proof theory. It is the standard formal logic for axiomatic systems; hence it plays an important role in the foundations of mathematics. Many common axiomatic systems, such as first-order Peano arithmetic and axiomatic set theory, including the canonical Zermelo-Frankel set theory, can be formalised as first-order theories.

Obviously, higher-order logic exists where, typically, predicates have other predicates or functions as arguments, or in which one or both of predicate quantifiers or function quantifiers are permitted. In first-order theories, predicates are often associated with sets. In interpreted higher-order theories, predicates may be interpreted as sets of sets. No first-order theory, however, can fully and categorically describe structures with an infinite domain, such as the natural numbers or the real numbers. Categorical axiom systems for these structures can be obtained in stronger logic such as second-order logic.

Once the intended interpretation is established, a program itself can be written. Program consists of two components: a logic component and a control component. The logic component is a particular kind of (polymorphic many-sorted) first-order theory which is usually suitably restricted so that an efficient theorem proving procedure can be admitted. Typically, in logic programming languages, the logic component of a program is the theory obtained by completing the collection of program statements. In other approaches to declarative programming different logics are used. For example, in functional programming, the logical component of a program can be understood to be a collection of formulas in the λ-calculus.

The control component of the program is concerned with the construction and pruning of search trees. Typically, the computation rule (which selects a subformula in a goal for an extension step) is partially specified by control declarations and the pruning of a search tree is specified by pruning operator. An important requirement of the control declarations and pruning operators of a program is that they can be deleted and what remains is a correct logic component of the program.

Declarative programming in general can be understood in a weak and a strong sense. In the weak sense, declarative programming means that programs are theories, but that a programmer may have to supply control information to produce an efficient program. Declarative programming, in the strong sense, means that programs are theories and all control information is supplied automatically by the system. In other words, for declarative programming in the strong sense, the programmer only has to provide the intended interpretation (or, perhaps, a theory which has the intended interpretation as a model). Gödel itself is a contribution to declarative programming in the weak sense. Thus Gödel programs are theories, but programmers are largely responsible for providing suitable control information.

Declarative programming is much more concerned with expressing the logic of a computation without describing its control, i.e. describing what the program should do, rather than describing how (that is the control part) it should be computed. Logical sentences can also be understood procedurally as goal-reduction procedures (also known as routines, subroutines, methods, or functions) with well set series of computational steps to be carried out. The Gödel programming language is not a procedural language. Although, the main advantage of the procedural semantics is portability, so that one could port a program from one implementation to another and be confident of identical behaviour of the program in the two systems, Gödel's procedural open semantics gives more freedom to handle it by programmers and adapt resulting programs to special project requirements; the programmer can use the known behaviour of the program executor to develop a procedural understanding of his program. This may be helpful when seeking better execution speed.

Prolog, HTML, SQL together with Gödel rank among declarative programming languages, while C/C++, Fortran and Pascal are examples of procedural programming languages.

Gödel specifications[edit]

Main facilities of the Gödel programming language are a type system, a module system, and control, meta-programming, and input/output facilities.

Types[edit]

The main reason for introducing types in logic programming languages is for knowledge representation. Intended interpretations in most logic programming applications are typed and hence using a typed language is the most direct way of capturing the relevant knowledge in the application. Also, the information given by the language declarations of a type system can be used by a compiler to produce more efficient code. Type declarations can help to catch programming errors. In a typed program, typographical errors often lead to syntax errors which can be caught by the compiler.

There are two kinds of type systems in logic. The first one is suitable for higher order logics, for example, λ-calculus. The second kind of type system studied in logic is many-sorted (first-order) logic. It is many-sorted logic which provides the foundation for type facilities in first-order logic programming languages and it is an extension of this logic that is used by Gödel. However, a many-sorted logic alone is not sufficiently flexible for a type system in a logic programming language. For this reason, Gödel allows a form of polymorphism, called parametric polymorphism, familiar from functional programming languages. Parametric polymorphism necessitates the introduction of type variables, which range over all types.

Parametric polymorphism is the second most important aspect of the type system. It is common for programmer to want to write a definition of a predicate for which the arguments of the predicate vary in used types. For example, the Append predicate is normally written so that it can append lists of any type. A symbol is polymorphic if its declaration contains a parameter; otherwise it is monomorphic. A polymorphic symbol can be understood as representing a collection of (monomorphic) symbols.

Gödel's type system is a strongly typed system. It means that each constant, function, proposition, and predicate in a program and its type must be specified by a language declaration. In particular, Gödel has specific restrictions on permitted operations involving values of different data types, preventing errors at both compilation time and execution time. Variables, by contrast, have their types derived from their contexts.

Modules[edit]

A module system simply provides a way of writing large programs so that various pieces of the program don't interfere with one another because of name clashes and also provides a way of hiding implementation details. The Gödel module system is based on these standard ideas. A Gödel program is a collection of modules. A module generally consists of two parts, the export and the local part. The export part of a module consists of language declarations for the symbols available for use in either part of the module and in the other modules which import them, control declarations, and module declarations giving the symbols from other modules which are available for use in either part of the module and in other modules which import them. The local part of a module consists of language declarations for the symbols available for use only in this part, module declarations giving the symbols from the other modules available for use in this part, control declarations, and definitions of those propositions and predicates specified by language declarations in this module.

The Gödel language include modules that process numbers, lists, strings and sets, modules that provide input/output, and modules that provide meta-programming facilities. Gödel also makes significant use of abstract data types, which are implemented by means of the module and type systems. An abstract data type consists of a type and a collection of operations on the type. Abstract data types have many advantages for software engineering, including the provision of a higher level of abstraction for programmers and the ability to change the implementation of a type without affecting existing code. The Gödel system modules provide a number of important abstract data types, including Unit (the type of units which are term-like structures), Flock (the type of ordered collections of units), Program (the type of terms representing Gödel programs), and Theory (the type of terms representing polymorphic many-sorted first order theories). The corresponding module provides a collection of operations on the type and the module system is used to hide the implementation details of these operations. Furthermore, a number of other Gödel system modules provide types which are at least partly abstract.

The Gödel language provides a rich collection of (mostly abstract) data types, useful for a variety of applications, and provides facilities for programmers to define their own abstract data types. A module consists of module declarations, language declarations, control declarations, and statements. Module declarations name modules and declare which symbols of the language are imported and exported. Language declarations define a polymorphic many-sorted language. Control declarations constrain the computation rule. Statements are the formulas in the language which define the propositions and predicates.

Language declarations begin with the keywords BASE, CONSTRUCTOR, CONSTANT, FUNCTION, PROPOSITION, or PREDICATE. These declarations declare the symbols of the language, which belong in one of the categories: base, constructor, and constant, function, proposition, or predicate.

Control[edit]

Gödel has a flexible computation rule which may select, in a goal body consisting of a conjunction of literals, a literal other than the leftmost literal. The advantages of flexible computation rule are that it can be used to ensure safeness (especially of negative calls), assist termination, assist efficiency, solve constraints, and control pruning. The computation rule is partly specified by means of DELAY control declarations, which cause certain calls to be delayed until they are sufficiently instantiated. Many Gödel system predicates have DELAY declarations. Furthermore, a programmer can encourage co-routining behaviour by means of these declarations.

Gödel has constraint-solving capabilities in the domains of integers and rational numbers. It can solve systems of (not necessarily linear) constraints which involve integers, variables which range over bounded intervals of integers, and the usual functions and predicates with integer arguments. It can also solve systems of linear rational constraints involving rationals, variables ranging over the rationals, and the usual functions and predicates with rational arguments.

The Gödel pruning operator (a difference from Prolog's pruning operator is shortly explained below), called the commit, can be used to prune away parts of a search tree and can thus affect the completeness of the search procedure. The commit is a powerful pruning operator and, in its full generality, is primarily meant to use by source-levels tools, such as partial evaluators and program transformers. Thus Gödel provides two special cases of the commit with simplified notation for use by programmers. These are the one-solution commit and the bar commit. The one-solution commit prunes the search tree in such a way as to ensure (at most) one solution of the formula it contains will be found. The bar commit which is similar to the commit of the concurrent logic programming languages, provides a means of pruning some of the branches emanating from a node in a search tree, where each branch corresponds to a statement in the program whose head unified with the selected atom in the goal labelling that node. However, while commits are infrequently needed in Gödel programs because their effect can often be achieved with declarative constructs such as negation and if-then-else, their use does detract from the major aim of Gödel, which is to have programs with the best possible declarative semantics. However, (sound) pruning operators do have an important place in logic programming languages, even though they may adversely affect the semantics of programs in which they appear.

The other facility provided by Gödel that gives a form of control is the IF-THEN-ELSE construct, which has several variations. This construct has a declarative meaning, but also provides the important control information that the condition in the IF part should be computed only once. This can result in an important saving if this condition is computationally expensive. One variation omits the ELSE part and another allows existentially quantified variables to appear in the IF and THEN parts. The IF-THEN-ELSE facility figures prominently in the Gödel programming style.

Meta-programming[edit]

A meta-program is a program which uses another program (the object program) as data. Meta-programming techniques underlie many of the applications of logic programming. For example, knowledge base systems consist of a number of knowledge bases (the object programs), which are manipulated by interpreters and assimilators (the meta-programs). Other important kinds of software, such as debuggers, compilers, and program transformers, are meta-programs.

The Gödel approach to meta-programming is to exploit abstract data types. One of the main such types is Program which is the type of a term representing an object Gödel program. Terms of type Program are complicated terms which contain a representation of all the components of a Gödel program. So, for example, the module structure must be represented, as must all the language declarations and statements appearing in the program. There are two other major abstract data types for meta-programming. One is Theory which is the type of a term representing an object polymorphic many-sorted theory. The system module Theories provides operations on this abstract data type which can be used to implement theorem provers, for example. The other type is Script which is the type of a term representing an object Gödel script. A script is similar to a program except that it has no module structure. Scripts are particularly useful as the target for partial evaluators. This, combined with the fact that a large number of useful operations are provided by these modules, means that Gödel provides a congenial environment for meta-programming.

Input/Output[edit]

Unfortunately, at the interface between a program and the external world, the declarative semantics of a program can be severely compromised. To try to ameliorate such difficulties, it is recommended that programmers exploit Gödel's module system. The idea is to have all the modules which use input/output predicates as high as possible in the module hierarchy. This means that modules not above or equal to these input/output modules will not make any calls to input/output predicates. Thus they will contain pure code together possibly with commits.

Input/output and pruning facilities adversely affect the declarative semantics of Gödel programs. Input/output introduces side-effects via read predicates. However, this problem can be ameliorated by appropriate use of the module system. Commit affects the declarative semantics because it can cause correct answers to be pruned. Fortunately, Gödel programs generally need few uses of pruning. Except where use is made of either of these two facilities, Gödel programs are declarative.

Prolog[edit]

Prolog is a general-purpose logic programming language associated with artificial intelligence and computational linguistics. Prolog is based on the first-order logic and a formal logic expressed in terms of relations, represented as facts and rules, it is declarative and a computation is initiated by running a query over these relations. The language was first designed by a group around Alain Colmerauer in France in 1972. It is one of the first logic programming languages and remains the most popular among such languages today, with many free and commercial implementations available.

Gödel compared to Prolog[edit]

In general, any programming language should satisfy five properties[citation needed]. It should be: high level (providing concepts as close as possible to those which people like to use to express their thoughts and ideas), expressive (providing concepts that can be used to model real-world situations easily and concisely), efficient (programs run at speeds and memory costs similar to competing languages), practical (that can be used for large-scale, real-world applications), and of a simple (mathematical) semantics (for which programmers can relatively easily verify and debug their programs and be assured of the correctness of program transformations, optimalisations, and so on).

Prolog is high level, efficient and practical. However, it is not sufficiently expressive as the logic it uses is untyped. Then, Prolog's semantics is not satisfactory, for example, provides a little of check, uses unsafe negation and cut, uses non-logical predicates, such as var, nonvar, assert, and retract. These problematical aspects of Prolog cause many practical Prolog programs to have no declarative semantics at all and to have unnecessarily complicated procedural semantics. This means that the analysis, transformation, optimisation, verification, and debugging of many Prolog programs is extremely difficult.

The solution to these semantic problems it to take more seriously the central thesis of logic programming, which is that

  • A program is a (first order) theory, and
  • Computation is deduction from the theory.

It is crucially important that programs can be understood directly as theories. When this is the case, they have simple declarative semantics and be much more easily verified, transformed, debugged, and so on. Each of the problematical aspects mentioned above causes difficulties precisely because it creates an impediment to the understanding of a program as theory. A Prolog program which cannot be understood in some simple way as a theory has only a procedural semantics. This leaves us in no better position to understand the program than if it was written in a conventional procedural language.

Gödel directly addresses these semantics problems of Prolog. The main design aim of Gödel is to have functionality and expressiveness similar to Prolog, but to have greatly improved declarative semantics compared with Prolog. Gödel is intended to have the same relation to Prolog as Pascal does to Fortran. Prolog was designed at the birth of logic programming before researchers had a clear understanding of how best to handle many facilities. Consequently, these facilities compromised its declarative semantics.

Prolog's approach to meta-programming is one of its most unsatisfactory aspects. Prolog does not make a clear distinction between the object level and meta-level, and does not provide explicit language facilities for representation of object level expression at the meta-level. Thus important representation (that is, naming) and semantics issues are glossed over. Prolog's meta-programming problems can be traced to the fact that it does not handle the representation requirements properly. A consequence of this is that it is not possible to understand most Prolog meta-programs as theories and hence they do not have a declarative semantics. The most obvious symptom of this is with var, which has no declarative semantics at all in Prolog. However, within the framework of the appropriate representation, a meta-program is a first order theory and the meta-logical predicates of Prolog, such as var, nonvar, assert and retract, have declarative counterparts.

Example of meta-program: the standard solve interpreter. This interpreter consists of the following definition for solve.

solve(empty)
solve(x and y) <- solve(x) & solve(y)
solve(x) <- clause(x,y) & solve(y)

together with the definition of for clause, which is used to represent the object program. However, the declarative meaning of the solve interpreter is by no means clear. The problem is that the variables in the definition of clause and the variables in the definition of solve intuitively range over different domains. Thus the intended interpretation is simply not a model of the program. What is at stake here is whether it is possible to give a simple and precise semantics to the solve interpreter and other meta-programs. If the different kinds of variable are intended to range over different domains, then there is a clear solution: we should introduce types into the language underlying the meta-program. The key aspect of the appropriate representation is that an object level variable is represented by a meta-level variable. This representation is called the non-ground representation. Then, for example, using an appropriately typed version of the solve interpreter, it is possible to prove its soundness and completeness for both the declarative and procedural semantics.

Another problem related to the fact that an object level variable is (implicitly) represented by a meat-level variable. This leads to severe semantic problems with var, for example. With this representation, there seems to be no way of giving a declarative semantics to var. To see the difficulty, consider the goals

<- var(x) & solve(p(x))

and

<- solve(p(x)) & var(x).

It the object program consists solely of the clause p(a) where a is a constant, then the first goal succeeds, while the second goal fails.

These considerations lead to another representation, called the ground representation, in which object level expressions are represented by ground terms at the meta-level. The ground representation is a standard tool in mathematical logic. Using this representation, it is possible to give appropriate definitions for declarative counterparts of the static meta-logical predicates of Prolog, such as var and nonvar.

Meta-programs are often required to manipulate the representations of object programs, creating new object program representations dynamically. For example, a partial evaluator and a program transformer both do this. To do this declaratively, we need one further idea, which is that object programs should be represented not as meta-programs, but instead as meta-level terms. Using this idea together with the ground representation, it is straightforward to set up the abstract data types used in the Gödel approach to meta-programming and to give appropriate definitions for declarative counterparts of the dynamic meta-logical predicates of Prolog, such as assert and retract.

The ground representation is easily the more important of the two representations and Gödel provides considerable support for the ground representation.

Representing object level variables by ground meta-level terms means that we can no longer make direct use of the underlying unification of the system. In principle, much low-level computation, which is normally done directly and efficiently by the system, must now be done less efficiently by explicit Gödel code. However, there is scope for dramatic improvement of the efficiency of Gödel meta-program by partial evaluation. Furthermore, there is a major implementation advantage in making programs more declarative, which is that more declarative programs are more easily parallelised.

Pruning[edit]

Prolog uses the cut as its pruning operator. However, cut has a number of semantic problems. The first of these problems is that cut, at least as it is employed in existing Prolog systems, allows considerable uncertainty about what the underlying logic component of the program is. This is because programmers can exploit the sequential nature of cut to leave “tests” out and when this is done the logic component of the program cannot be obtained by simply removing all the cuts from the program. Furthermore, there is no convention for systematically putting back the omitted tests so as to define the logic component precisely. The second problem with cut is that its use, in the presence of negation, can be unsound, in the sense that a computed answer may not be correct with respect to the completion of the logic component of the program.

For these reasons and because the commit of the concurrent logic programming languages has better semantics, Gödel's pruning operator, also called commit, is based on the commit of the concurrent languages. In fact, the simplest form of the commit (denoted | and called bar commit) is similar to the commit of the concurrent languages. Consider the following definition of the proposition M, in which we write | as a connective with the declarative meaning of conjunction.

M <- Q | R.
M <- S | T.

The informal procedural meaning of bar commit is that is finds only one solution for the formula to its left in the body and prunes all branches corresponding to other statements in the definition which contain a bar commit. The order in which the statements are tried is not specified, so that bat commit does not have the sequentially property of cut. For the above definition, if M is called and S succeeds, then only one solution will be found for S and the branch corresponding to the first statement will be pruned.

We now investigate the extent to which | supports program transformations. Consider the following program.

P <- M & L.
P <- N.
M <- Q | R.
M <- S | T.
N <- U | V.

How can we unfold on M and N in the definition for P? A first attempt might be the following definition for P.

P <- Q | R & L.
P <- S | T & L.
P <- U | V.

However, this is not correct as the | notation is unable to distinguish the commits in the first two statements from the commit in the third statement. This difficulty leads us to introduce a more flexible notation of |. This notation has the form {...}_l, where l is a label (which is a positive integer). In this notation, the previous program would be written as follows.

P <- M & L.
P <- N.
M <- {Q}_1 & R.
M <- {S}_1 & T.
N <- {U}_1 & V.

The brackets {...} capture the scope of the commit inside a statement. By convention, for | this scope is the formula to its left. The label captures the scope of the commit over the statements in the formula. When formula {W}_1 succeeds, all branches in the search tree corresponding to other statements in this definition which contain a commit labelled 1 are pruned. The other pruning that takes place is that only one solution is found for W. Now when we unfold on M and N in the definition for P, we obtain the following definition

P <- {Q}_1 & R & L.
P <-{S}_1 & T & L.
P <- {U}_2 & V.

in which the label in the commit in the definition for N has been standardised apart to avoid an unwanted coincidence with the label of the commits in the definition for M. Note that we have now correctly distinguished the commits.

Formulas[edit]

Quantifiers and conditionals are very typical for the first-order logics.

Quantifiers[edit]

In Gödel, conjunction is denoted by &, disjunction by \/, negation by ~, (left) implication by <-, (right) implication by ->, and equivalence by <->. The universal quantifier is denoted by ALL and the existential quantifier is denoted by SOME. Each quantifier has two arguments, the first being a list of the quantified variables and the second the scope of the quantifier. Note that the types of the quantified variables in the body of a statement or goal are not declared. The types of these variables are assigned by the type checker along with the types of the other variables in the statement or goal.

Quantifiers provide an expressive language in which to write goals and statements.

Conditionals[edit]

Conditionals enable to provide constructs with specialised procedural semantics. The most common such situation is when a programmer wants to use a formula of the form

(Condition & Formula1) \/ (~Condition & Formula2)

in a body. This approach has the disadvantage that Condition may be computed twice, which is undesirable if Condition is computationally expensive. For these reasons, Gödel also has IF-THEN and IF-THEN-ELSE constructs, called conditionals, which should be implemented in such a way as to avoid this inefficiency.

Sample code[edit]

The following Gödel module is a specification of the greatest common divisor (GCD) of two numbers. It is intended to demonstrate the declarative nature of Gödel, not to be particularly efficient. The CommonDivisor predicate says that if i and j are not zero, then d is a common divisor of i and j if it lies between 1 and the smaller of i and j and divides both i and j exactly. The Gcd predicate says that d is a greatest common divisor of i and j if it is a common divisor of i and j, and there is no e that is also a common divisor of i and j and is greater than d.

MODULE      GCD.
IMPORT      Integers.
 
PREDICATE   Gcd : Integer * Integer * Integer.
Gcd(i,j,d) <- 
           CommonDivisor(i,j,d) &
           ~ SOME [e] (CommonDivisor(i,j,e) & e > d).
 
PREDICATE   CommonDivisor : Integer * Integer * Integer.
CommonDivisor(i,j,d) <-
           IF (i = 0 \/ j = 0)
           THEN
             d = Max(Abs(i),Abs(j))
           ELSE
             1 =< d =< Min(Abs(i),Abs(j)) &
             i Mod d = 0 &
             j Mod d = 0.

Historical remarks[edit]

Gödel programming language benefits from previous designed languages and work of many authors. It is based on, and supposed to be a successor of Prolog that was developed by Alain Colmerauer in 1972. Gödel then contains:

  • the intensional set terms developed from set processing facilities introduced around 1980 into Prolog by David H.D. Warren
  • pruning operator first appeared in the Relational Language of Keith Clark and Steve Gregory in the early 1980s
  • the if-then-else construct and the when control declaration taken from NU-Prolog introduced by Lee Naish around 1986
  • the type system based on many-sorted first order logic with the addition of polymorphism through parameters and constructors
  • the ideas of the polymorphic component are made by Robin Milner (introduced in ML in the 1970s) and are first considered in the logic programming context by Alan Mycroft and Richard O'Keefe in 1983
  • the module system is based on standard ideas of Modula-2
  • the constraint solving facilities are partially developed by Alain Colmerauer, Joxan Jaffar, Jean-Luis Lassez (influenced by work of Kenneth Bowen and Robert Kowalski which itself relies on work of Kurt Gödel)

External links[edit]

References[edit]

  1. ^ Hill, P.M., Lloyd, J. W. (1994). The Gödel Programming Language. Massachusetts: The MIT Press. 
  2. ^ Hill, Patricia M. "Home page of Patricia Hill". 
  3. ^ Lloyd, John W. "Home page of John W. Lloyd".