Content deleted Content added
m Reverted edits by 103.25.231.2 (talk) to last revision by Martinjanda (HG) |
|||
Line 19:
}}
'''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
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.
== About the authors ==
Line 31:
== General principles of the Gödel programming language ==
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
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.
Line 39:
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
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
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.
Line 90:
=== Prolog ===
[[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
The language was first designed by a group
=== Gödel compared to Prolog ===
In general, any programming language should satisfy five properties. 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.
The solution to these semantic problems it to take more seriously the central thesis of logic programming, which is that
Line 139 ⟶ 134:
=== Pruning ===
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
▲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; 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: 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 language]]s. 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.
Line 148 ⟶ 141:
M <- S | T.
The informal procedural meaning of bar commit is
We now investigate the extent to which | supports program transformations. Consider the following program.
| |||