Algol 50(ID:5842/alg027)

One stimulus for writing this article was a talk entitled "Programming languages of the year 2000'' that I considered insufficiently ambitious.

It has long been said that programming languages need more of
the features of natural language, but it has not been clear what the
desirable features are, and there have been few significant conceptual
advances in the last 20 years.  It is rather clear that the surface
syntax of natural language doesn't offer much; COBOL did not turn out
to be an advance.

This article proposes several new features for programming
languages more or less taken from natural language.  We also propose
new kinds of specifications that make it easier to be confident that
the specifications express what is wanted of the program.  As a
vehicle we propose Elephant 2000, a language that would embody them.
Some features are not yet well enough defined to be included in the
program examples.

1. Elephant programs will communicate with people and other
   programs in sentences of the Elephant I-O language which have
   meanings partially determined by the Elephant language and
   partially implicit in the program itself.  Thus Elephant input
   and output include, and the I-O language distinguishes,
   requests, questions, offers, acceptances of
   offers, permissions as well as answers to questions
   and other assertions of fact.  Its outputs also include promises and statements of commitment analogous to promises.
2. Some of the conditions for correctness of an Elephant program are defined in terms of the meaning of the inputs and outputs.  We can ask whether an Elephant program fulfilled a request, answered a question truthfully and responsively, accepted an offer or fulfilled a commitment. We can also ask whether the program has authority to do what it does.  Some of such correctness conditions are intrinsic, because the text of the program determines them. Expressing these intrinsic correctness conditions as sentences of logic requires a formal theory of what it means to fullfil a commitment, etc.  This theory doesn't have to correspond exactly to human behavior or social customs; we only need analogs useful for program correctness.  They are somewhat analogous to the grammaticality conditions of present programming languages, but they are semantic rather than syntactic.
   

   For example, when a program "promises" someone to do something, it needn't believe (as Searle (1969) suggests it should) that fulfillment of the promise will do its recipient some good.  Indeed many programs that promise won't have any beliefs at all. We expect to be able to generate the intrinsic correctness sentences automatically from the text of the program.  Thus the text of the program that designates certain outputs as answers to questions, determines a logical sentence asserting that the answers are truthful.
   

3. Elephant programs do not require data structures, because program statements can refer directly to past events and states.  An Elephant interpreter keeps a history list of past events, and an Elephant compiler constructs whatever data structures in the object language are needed to remember the information needed for compiled program to behave as specified in the Elephant source program. However, it seems unlikely that it will be convenient to omit data structures completely from the language.
   
4. An Elephant program is itself a logical sentence (or perhaps a syntactic sugaring of a logical sentence).  The extensional correctness properties of the program are logical consequences of this sentence and a theory of the domain in which the program acts.  Thus no logic of programs is needed.  Any sugaring should be reversible by a statement-by-statement syntactic transformation, thus getting the logic back.
   
5. Requests, permissions and promises such as those we
   want Elephant programs to perform are called speech acts by
   philosophers and linguists.  The idea is that certain sentences
   don't have only a declarative significance but are primarily actions.  A paradigmatic example is a promise, whose utterance creates an obligation to fulfill it and is therefore not merely a statement of intention to do something.  For some purposes, we can bypass the the philosophical complexities of obligation by considering only whether a program does fulfill its promises, not worrying about whether it is obliged to.
   

   In the customary philosophical terminology, some of the outputs of Elephant programs are performative sentences, commonly referred to just as performatives.  Indeed Elephant 2000 started with the idea of making programs use performatives. However, as the ideas developed, it seemed useful to deviate from the notions of speech act discussed by J. L. Austin (1962) and John Searle (1969).  Thinking about speech acts from the design standpoint of Daniel Dennett (1971) leads to a view of them different from the conventional one.  We now refer to abstract performatives which include purely internal actions such as commitments not
   necessarily expressed in output, but on whose fulfillment the correctness of the program depends.  Taking the design stance in the
   concrete way needed to allow programs to use speech acts tends to new views on the philosophical problems that speech acts pose.
   

   Notice that it isn't necessary for most purposes to apply moral terms like honest, obedient or faithful to the program, and we won't in this paper.  However, we can incorporate whatever abstract analogs of these notions we find useful.  The philosophical investigations have resulted in ideas useful for our purposes. This is partly because programs belonging to one organization that interact with those belonging to other organizations will have to perform what amounts to speech acts, and the specifications of these programs that have to be verified often correspond to what Austin calls the happy performance of the speech acts.
   

   (McCarthy 1979a) discusses conditions under which computer programs may be ascribed beliefs, desires, intentions and other mental qualities.  It turns out that some specifications require ascription of beliefs, etc. for their proper statement, and others do not.
   

   Allowing direct reference to the past may also permit easier modification, because the program can refer to past events, e.g. inputs and outputs, directly rather than via data structures whose design has to be studied and understood.  Since referring directly to past events is characteristic of natural languages, we expect it to prove useful in programming languages.

6. The theory of speech acts distinguishes between illocutionary acts, such as telling someone something, and perlocutionary acts, such as convincing him of it.  The distinction between illocutionary and perlocutionary can be applied to speech inputs as well as outputs.  Thus there is an input distinction between hearing that and learning that analogous to the output distinction between telling and convincing.
   

   Procedures for human execution often specify perlocutionary
   acts.  For example, a teacher might be told, "Have your students
   take the test on Wednesday''.  However, including perlocutionary acts in programs is appropriate only if the program has good enough resources for accomplishing goals to make it reasonable to put the goal in the program rather than actions that the programmer believes will achieve it.  One would therefore expect perlocutionary statements mainly in programs exhibiting intentionality, e.g. having beliefs, and involving some level of artificial intelligence.
   

   Even without putting perlocutionary acts in the program itself, it is worthwhile to consider both input-output and accomplishment specifications and for programs.  These correspond to illocutionary and perlocutionary speech acts respectively.  For example, an air traffic control program may be specified in terms of the relations between its inputs and its outputs.  This is an input-output specification.  Its verification involves only the semantics of the programming language.  However, our ultimate goal is to specify and verify that the program prevents airplanes from colliding, and this is an accomplishment specification.  Proving that a program meets accomplishment specifications must be based on assumptions about the world, the information it makes available to the program and the effects of the program's actions as well on facts about the program itself.  These specifications are external in contrast to the intrinsic specifications of the happy performance of speech acts.
   

   It will often be worthwhile to formulate both input-output and
   accomplishment specifications for the same program and to relate them.
   Thus an argument based on an axiomatic theory of the relevant aspects
   of the world may be used to show that a program meeting certain input-output specifications will also meet certain accomplishment specifications.  Apparently the dependence of program specifications
   on facts about the physical world makes some people nervous.  However,
   the problem of justifying such axiomatic theories is no worse than
   that of justifying other formalized theories of the physical world in
   applied mathematics.  We are always trusting our lives to the physical
   theories used in the design of airplane wings.
   

7. The most obvious applications of Elephant are in programs that do transaction processing and refer to databases in more general ways than just answering queries and making updates. Abstract performatives will also be important for programs involved in business communication with programs belonging to other organizations.  (McCarthy 1982) suggests a "Common Business Communication Language".
   

This article is exploratory, and we are not yet prepared to argue that every up-to-date programming language of the year 2000 will include abstract performatives.  We hope that programs using performatives will be easier to write, understand, debug, modify and (above all) verify. Having a standard vocabulary of requests,
commitments, etc. will help. External link: Online copy External link: Algol 50 Home page External link: Algol 48 and 50 page