Artificial-intelligence programming languages

Type of physical science: Computation

Field of study: Artificial intelligence

There is a sense in which every computer program, when it is running, defines a language. Its syntax confines the questions that the user will be allowed to ask; its meaning describes the kinds of answers that the computer can give. To qualify as a programming language, that language must be general and flexible enough so that questions of many kinds can be asked. The goal of programming languages for artificial intelligence is to permit the computer's answers to reflect answers that a person might give.

Overview

The goal of computer science is to model the world by a computer program. For example, an inventory program might have for each automobile part a record of the quantity on hand, the number sold, the number lost, and the quantity below which one needs to reorder (the reorder point). Changes in the data of the program reflect changes in the real world. The goal of artificial intelligence is to model the world of a human by a computer program. For example, an artificially intelligent inventory program might have a robot that can package orders for parts, a reasoning facility to warn the user that too many parts have been lost, the ability to ask questions and to receive answers in English, the ability to discover that a part is defective by looking at it, or the ability to improve where it sets the reorder point by learning from the history of past sales. If one accepts for the sake of discussion that one cannot reason without language, then one wonders what appropriate language exists for thought. If a machine is going to do the thinking, then the artificial language to achieve that purpose must be devised. Every computer-programming language has been used to test ideas of artificial intelligence.

FORTRAN, written in 1954, was the first widely used programming language. FORTRAN is an acronym for "formula translation," used because the language was designed for numerical applications; however, by 1960, packages of FORTRAN subroutines were available that allowed programmers to manipulate lists of symbols more easily. The behavioral sciences saw from the start the power of a computer as a general symbol manipulator rather than merely a numerical calculator. For example, in 1959, Allen Newell and Fred M. Tonge introduced a FORTRAN-based package of list-processing subroutines that they called Information Processing Language V (IPL-V), based on ideas developed by Newell, John Clifford Shaw, and Herbert A. Simon.

The idea of using a collection of subroutines to perform general symbol manipulation, however, is an ad hoc solution. At the same time, John McCarthy, a mathematics professor at Dartmouth College, created a language designed especially for symbol manipulation. He called it LISP, for "list processor," and fashioned its syntax after a variation of first-order predicate logic developed by Alonzo Church in the 1930s. McCarthy did not intend for LISP to use first-order predicate logic; it was only Church's notation that he borrowed, not the restrictions of that logic.

For several reasons, LISP is often considered the first artificial-intelligence programming language. The first reason is that artificial intelligence subscribes to what Newell and Simon called the "physical symbol system hypothesis" (PSSH), which states that physical-symbol systems are "necessary and sufficient . . . for general intelligent action," and LISP is a symbol-manipulating language. Second, if a machine is to be artificially intelligent, it should be able to learn. LISP is able to create data as it is running, which it then executes, resulting in a program that is self-modifying. This process strongly suggests an analogy with learning, a necessary ability for any artificial intelligence. John von Neumann characterized modern computers as machines that can treat commands as data or treat data as commands, so LISP is not the only programming language to exploit the feature. Prior to LISP, however, the only language available that could take advantage of this power was the computer's native "machine language," not a friendly environment at all in which to represent highly abstract concepts. Third, LISP has features that easily allow it to be a multiparadigm language. LISP was written to be primarily a functional language, but because each constant in LISP has associated with it a "property list" that is adequate for representing frames, and because frames can include anonymous functions, LISP can be used to program in an object-oriented style. LISP includes a GOTO command, so one can program in LISP in a procedural style as well, such as in the style of FORTRAN. Briefly, LISP is close enough to the hardware of a computer to be flexible, yet close enough to paradigms of thinking to be useful.

Other features of LISP made it suitable initially for research in artificial intelligence. Variables do not need to be declared. An interactive environment encourages rapid turnaround from an idea to its implementation. As an extensible language, LISP can be extended to include new features that remain part of the extended language. LISP features have been adopted by numerous other computer languages, and many of its dialects are still widely used in artificial intelligence, including Common Lisp and Scheme.

In 1980, Japan began a ten-year nationwide effort to become a leader in artificial intelligence. Its government and its major electronics corporations launched an initiative called the Fifth Generation Computer Systems Project. The project based the five traditional subareas of artificial intelligence—natural language processing, expert systems, machine learning, image processing, and robotics—on an obscure computer language called Prolog.

Prolog (from programmation en logique, French for "logic programming") was invented by Philippe Roussel and Alain Colmerauer in Marseilles, France, in 1972 to investigate natural language processing. As a logic-programming language, Prolog can be thought of as a database of facts that describe relations between objects and the rules that allow the programmer to reason about those objects. The only control structure of a pure logic-programming language is theorem proving; the only method of assigning variables is a kind of template-matching called unifaction. Prolog, like LISP before it, includes some procedural elements as well, but it is useful as an artificial-intelligence language because it is the only logic language with some degree of international standardization. Although pattern matching and theorem proving are not very useful for balancing one's checkbook, they describe very well the five subareas of artificial intelligence.

A logic language is adequate. The Japanese initiative determined its efficiency by creating special hardware optimized to execute logic programs to make them especially fast. Even with that, however, a logic program often entails searching a large database of possibilities and requires long chains of reasoning. Again, a multiparadigm language allows logic to be used when it is helpful; however, more efficient procedural elements need to be used when speed is important. In the early days of artificial intelligence, "intelligence" meant heuristic search techniques. Heuristics are guesses for speeding up the process of answering questions. Artificial intelligence should be viewed more properly as the science of how machines represent and use knowledge.

One way to solve the efficiency problem is to do what the human brain does: look for the answer in more than one place at the same time, or process in parallel. Parallel processing may solve some of the problems of inefficient artificial-intelligence programs. Research continues on how best to program for parallel processing and how it can be applied to artificial intelligence.

LISP is flexible; it can be modified to present an appearance similar to that of Prolog. A language represents a way of thinking about a problem. There is no doubt that even low-level machine language could be used if the only issues were what is possible. Prolog's syntax is close to first-order predicate calculus as used by mathematicians. Thus, the distance that a programmer has to span between a thought and its expression is much smaller than in LISP.

One paradigm of artificial-intelligence languages is programming by constraints. A logic language is a special kind of constraint language: the axioms and the goal to be proved must be constrained to be true simultaneously. The problem with this method of programming is that a solution is not always possible. As an example, for a system of simultaneous equations with decimal numbers as coefficients, an approximate decimal solution is always possible in a reasonable time. Yet if the coefficients are whole numbers and a whole-number solution is required, then the general solution grows exponentially with the size of the problem.

The domain of discourse is more important in constraint programming than in other paradigms. In addition to logic constraints, constraint programming has permeated artificial intelligence in two important ways. First, there are specific problems that lend themselves to specification by constraints. The standard method to discover the electric current flowing in any part of a circuit involving resistance, capacitance, and inductance is to use Gustav Robert Kirkhoff's laws. In 1978, Johan de Kleer and Gerald Jay Sussman created an artificial-intelligence program that was able to solve such problems, including features to allow troubleshooting and causal reasoning to aid in circuit design. Second, computer-aided graphics design has incorporated constraints in programs interacting with the designer, so that, for example, a line segment can be constrained to be vertical or a circle can be constrained to pass through two points. This latter example shows the influence of an object-oriented approach, too, for if a line segment is not only its set of points, then it is an object with various properties. Besides specific examples, the entire neural-network approach to artificial intelligence, which models the brain at a fine level of granularity, is a method that allows a model of connected neurons to settle on the strengths of the connections by a process of constraints.

Another paradigm of artificial-intelligence programming is that of object-oriented languages. When it was first introduced, object-oriented programming stood procedural programming on its head. In procedural programming, one writes subroutines that happen to contain data and that receive and supply other data. One subroutine passes data to another subroutine, which in turn passes data to another. In object-oriented programming, one creates data (objects) that happen to have procedures associated with them.

The goal of computer science is to model the real world. It is natural in doing so to think in terms of objects in the world, such as automobiles, families, foods, or corporate enterprises. A procedural style reflects how a computer arrives at answers; an object-oriented style reflects how the questions and the answers are related in the world. Thus, object-oriented languages, unlike LISP and Prolog, got their start not in artificial intelligence but in the broader area of simulation. Marvin Minsky, often regarded along with McCarthy as a father of artificial intelligence, proposed in 1975 that objects or frames be used in artificial intelligence. Some artificial-intelligence languages, such as FRL (Frame Representation Language) and KL-ONE (Knowledge Language ONE), were written by research laboratories to investigate Minsky's proposal.

Object-oriented languages became widely available in the 1990s, though the object-oriented paradigm is used mostly as part of other, more comprehensive systems, known as multiparadigm languages. For example, the language LOOPS, developed at the Xerox Palo Alto Research Center, is an adaptation of LISP with object-oriented extensions. Poplog is a language from England that combines Prolog and LISP. Trilogy is a language combining four paradigms: functional, logic, constraint, and procedural. C++ is a free-form, general-purpose multiparadigm language that combines features of both high-level (more abstract) and low-level (less abstract) programming languages and can be used to write either object-oriented or procedural code. Java is a portable object-oriented language that can run on any device via a Java virtual machine (JVM); many of its features, especially inheritance—the ability of a program to incorporate the characteristics of a previously defined object or class into a new object or class—evolved from earlier developments in artificial-intelligence programming. C++ and Java are both popular languages for programming artificial intelligence due to their ubiquity and the speed of their execution. Another popular language is Python, a high-level multiparadigm language that combines built-in abstract structures with the ability to incorporate C++ modules for greater speed.

Applications

Logic programming can be used in each of the five major subareas of artificial intelligence: natural language processing, expert systems, machine learning, image processing, and robotics. In natural language processing, the syntax of a sentence in a particular language, such as English, can be described by rules of logic, and the specific pattern of a given sentence can be matched to the general pattern of the rules of logic. A dictionary of the meanings of individual words or parts of words can be structured to describe each entry's logical relations with other dictionary entries. Thus, both the structure and the meaning of a sentence can be described by logic, or at least the denotation of the sentence. The emotions of a sentence, its purpose as a speech act, its connotations, and its metaphors are matters of ongoing research.

The major feature of an expert system is its ability to explain the logical basis on which its decision is made. If an expert system is programmed in a logic language, then the user can request the justification of any answer by replaying the sequence of logical steps that led to it.

Machine learning can be described in terms of rules that allow induction, the reverse of deduction. Logic programs can embody these rules. The following is an example of induction: because every crow that I have seen is black, all crows are black. Inductive reasoning is not as certain as deductive reasoning—after all, there are albino crows—but it forms the major way in which one learns, namely by generalizing from experience. Deductive logic is powerful enough to express as rules of logic not only facts about the world ("This crow is black") but also rules about those facts ("After you have seen three black crows and none of any other color, conclude that all crows are black").

Image processing requires the ability to recognize both low-level patterns, such as edges and areas, and high-level patterns, such as tables and chairs. Logic programs assign values to variables by pattern matching. Thus, they are well suited to express both low-level and high-level rules involving patterns. One drawback of this is that there is no pattern that fits all things that are chairs and none that fits nothing but chairs. This central problem of artificial intelligence is called the frame problem.

Among other things, robotics deals with how a robot can plan a sequence of actions. A plan can be expressed in logic, again making logic programming ideal for expressing how to constrain a robot's motion. There is only one disadvantage of a pure logic language. The ability of a computer program to affect the world outside the computer depends on the side effects of executing the program. Usually a logic language does not have a good mechanism for evoking physical actions. When the statement "Lift the brick" is established to be true, the computer must have some way of actually moving effectors to lift the brick. This can be done by using a multiparadigm language, in which pure logic is allowed to have some procedural elements.

Context

As early as the seventeenth century, German philosopher and mathematician Gottfried Wilhelm Leibniz hoped that a language for thought, a "rational calculus" as he called it, would allow encyclopedic knowledge to be written in an unambiguous way. In his "best of all possible worlds," as Voltaire satirically dubbed it, arguments could be settled by appeal to objectivity. Leibniz never succeeded, but he made good progress. He invented not only differential and integral calculus, which provided a powerful analytic language for a large amount of physical science, but also a binary, or base-two, arithmetic, which is the arithmetic used by modern digital computers.

In 1854, George Boole wrote his treatise The Laws of Thought, in which he proposed an algebra of logic, not just first-order logic but the logic of statements without variables that are either true or false. This algebra became the basis for digital logic as used by digital computers. In the 1930s, Claude Shannon showed that Boolean algebra could be realized in relay switches, allowing logic of a special narrow sort to finally become completely electromechanical. In the 1940s, Alan Turing, Church, and others showed that a machine could make deductions with the full power of first-order predicate logic. Thus, insofar as artificial intelligence is based on deductive reasoning and deductive reasoning is based on such a logic, the goal of artificial intelligence has been met.

However, reasoning is not only deductive conclusions derived from axioms that are timeless and certain. To accommodate different patterns of reasoning, artificial-intelligence research is applying various logics, such as time-dependent logics. Some of them regard time as a sequence of points; others regard it as possibly overlapping intervals. Modal logics allow an expert system to express degrees of believability in the conclusions that it draws and to reason hypothetically, contrary to fact. Defeasible logics allow an expert system to withdraw axioms that result in false conclusions. Second-order predicate logics allow an expert system to reason about its own reasoning. As the field continues to advance, programming languages will look more and more like the languages that people use for everyday conversation.

Principal terms

CONSTRAINTS LANGUAGE: a programming language in which each statement narrows down the possible answers that can be given

FIRST-ORDER PREDICATE LOGIC: a formalism for deductive reasoning that includes constants (representing nouns), allows variables (such as pronouns) to range in value over the constants, and includes predicates (representing verbs)

FRAME: a collection of related data and procedures whose size is not fixed; data values are found by asking for them by category; default values or procedures may be provided, either as a part of the frame or inherited from another frame

FUNCTIONAL LANGUAGE: a programming language in which every statement returns a value, the primary control structure is recursion, and transfer of control may not use a GOTO command

INTERPRETATIONS: a declarative reading, as a formula of logic, and a procedural reading, as instructions that a computer obeys to discover the truth of that formula

LOGIC LANGUAGE: a programming language in which every statement has two interpretations

MULTIPARADIGM LANGUAGE: a programming language that allows two or more methods of programming

OBJECT-ORIENTED LANGUAGE: a programming language in which frames communicate with one another by requesting services

RECURSION: a procedure that calls on a second copy of itself to answer a simpler version of the question that was posed to the first copy

Bibliography

Abelson, Harold, Gerald J. Sussman, and Julie Sussman. Structure and Interpretation of Computer Programs. 2nd ed. Cambridge: MIT P, 1996. Print. This introductory computer-science text is used at the Massachusetts Institute of Technology. It describes the essence of computer science, using LISP as the vehicle.

Clocksin, W. F., and C. S. Mellish. Programming in Prolog. 5th ed. New York: Springer, 2003. Print. This standard reference and introduction to Prolog is geared toward the novice. Its relationship to logic is explained in the appendix.

Hofstadter, Douglas R. Metamagical Themas: Questing for the Essence of Mind and Pattern. New York: Basic, 1985. Print. Chapter 13 discusses the frame problem of recognizing the letter A. Several chapters discuss LISP.

McMillan, Ken, Aart Middeldorp, and Andrei Voronkov, eds. Logic for Programming, Artificial Intelligence, and Reasoning: 19th International Conference. Berlin: Springer, 2013. Print.

Meyer, Bertrand. Object-Oriented Software Construction. 2nd ed Englewood Cliffs: Prentice, 1997. Print. This book is an introduction to object-oriented programming, though not within the context of artificial intelligence.

Richert, Willi, and Luis Pedro Coelho. Building Machine Learning Systems with Python. Birmingham: Packt, 2013. Print.

Russell, Stuart, and Peter Norvig. Artificial Intelligence: A Modern Approach. 3rd ed. Upper Saddle River: Prentice, 2010. Print.

Tourtesky, David. Common LISP: A Gentle Introduction to Symbolic Computation. Redwood City: Benjamin, 1990. Print. This is a good introduction to LISP for the beginner.

Watson, Mark. Practical Artificial Intelligence Programming in Java. 4th ed. N.p.: n.p., 2013. Web. 2 Jan. 2014.

Computer Programs and Subroutines