We define a semantics for the arithmetic part of PASCAL by giving it

an interpretation in LCF, a language based on the typed λ-calculus.

Programs are represented in terms of their abstract syntax. We show

sample proofs, using LCF, of some general properties of PASCAL and

the correctness of some particular programs. A program implementing

the McCarthy Airline reservation system is proved correct.

In this paper we show that every flowchart program can be written

without 'go-to' statements by using 'while' statements. The main

idea is to introduce new variables to preserve the values of certain

variables at particular points in the program; or alternatively, to

introduce special boolean variables to keep information about the

course of the computation. The new programs preserve the 'topology'

of the original program, and are of the same order of efficiency. We

also show that this cannot be done in general without adding

variables.

A winged edge polyhedron representation is stated and a set of

primitives that preserve Euler's F-E+V=2 equation are explained.

Present use of this representation in Artificial Intelligence for

computer graphics and world modeling is illustrated and its intended

future application to computer vision is described.

This paper describes KRL, a Knowledge Representation Language designed for

use in understander systems. It outlines both the general concepts which

underlie our research and the details of KRL-0, an experimental

implementation of some of these concepts. KRL is an attempt to integrate

procedural knowledge with a broad base of declarative forms. These forms

provide a variety of ways to express the logical structure of the

knowledge, in order to give flexibility in associating procedures (for

memory and reasoning) with specific pieces of knowledge, and to control

the relative accessibility of different facts and descriptions. The

formalism for declarative knowledge is based on %2structured conceptual

objects%* with associated %2descriptions%*. These objects form a network

of %2memory units%* with several different sorts of linkages, each having

well-specified implications for the retrieval process. Procedures can be

associated directly with the internal structure of a conceptual object.

This %2procedural attachment%* allows the steps for a particular operation

to be determined by characteristics of the specific entities involved.

The control structure of KRL is based on the belief that the next

generation of intelligent programs will integrate data-directed and

goal-directed processing by using multi-processing. It provides for a

priority-ordered multi-process agenda with explicit (user-provided)

strategies for scheduling and resource allocation. It provides

%2procedure directories%* which operate along with %2process frameworks%*

to allow procedural parameterization of the fundamental system processes

for building, comparing, and retrieving memory structures. Future

development of KRL will include integrating procedure definition with the

descriptive formalism.

An information processing model of some important aspects of

inductive reasoning is presented within the context of one

scientific discipline. Given a collection of experimental (mass

spectrometry) data from several chemical molecules the computer

program described here separates the molecules into "well-behaved"

subclasses and selects from the space of all explanatory processes

the "characteristic" processes for each subclass. The definitions of

"well-behaved" and "characteristic" embody several heuristics which

are discussed. Some results of the program are discussed which have

been useful to chemists and which lend credibility to this approach.

The program called Heuristic DENDRAL solves scientific induction

problems of the following type: given the mass spectrum of an

organic molecule, what is the most plausible hypothesis of organic

structure that will serve to explain the given empirical data. Its

problem solving power derives in large measure from the vast amount

of chemical knowledge employed in controlling search and making

evaluations.

A brief description of the task environment and the program is given

in Part I. Recent improvements in the design of the program and the

quality of its performance in the chemical task environment are

noted.

The acquisition of task-specific knowledge from chemist-'experts',

the representation of this knowledge in a form best suited to

facilitate the problem solving, and the most effective deployment of

this body of knowledge in restricting search and making selections

have been major foci of our research. Part II discusses the

techniques used and problems encountered in eliciting mass spectral

theory from a cooperative chemist. A sample 'scenario' of a session

with a chemist is exhibited. Part III discusses more general issues

of the representation of the chemical knowledge and the design of

processes that utilize it effectively. The initial, rather straight-

forward, implementations were found to have serious defects. These

are discussed. Part IV is concerned with our presently-conceived

solutions to some of these problems, particularly the rigidity of

processes and knowledge-structures.

An experimental system for automatically generating certain simple

kinds of programs is described. The programs constructed are

expressed in a subset of ALGOL containing assignments, function

calls, conditional statements, while loops, and non-recursive

procedure calls. The input is an environment of primitive programs

and programming methods specified in a language currently used to

define the semantics of the output programming language. The system

has been used to generate programs for symbolic manipulation, robot

control, everyday planning, and computing arithmetical functions.

The objectives of the research reported here are to develop an

automated decision process for real time allocation of defense

missiles to attacking ballistic missiles in general war and to

demonstrate the effectiveness of applying heuristic learning to seek

optimality in the process. The approach is to model and simulate a

missile defense environment and generate a decision procedure

featuring a self-modifying, heuristic decision function which

improves its performance with experience. The goal of the decision

process that chooses between the feasible allocations is to minimize

the total effect of the attack, measured in cumulative loss of

target value. The goal is pursued indirectly by considering the

more general problem of maintaining a strong defense posture, the

ability of the defense system to protect the targets from both

current and future loss.

The objectives of the research reported here are to develop an

automated decision process for real time allocation of defense

missiles to attacking ballistic missiles in general war and to

demonstrate the effectiveness of applying heuristic learning to seek

optimality in the process. The approach is to model and simulate a

missile defense environment and generate a decision procedure

featuring a self-modifying, heuristic decision function which

improves its performance with experience. The goal of the decision

process that chooses between the feasible allocations is to minimize

the total effect of the attack, measured in cumulative loss of

target value. The goal is pursued indirectly by considering the

more general problem of maintaining a strong defense posture, the

ability of the defense system to protect the targets from both

current and future loss.

The principles underlying a computer-based treatment method for

language acquisition in nonspeaking autistic children are described.

The main principle involves encouragement of exploratory learning

with minimum adult interference.

The first ten years of research in artificial intelligence and

related fields at Stanford University have yielded significant

results in computer vision and control of manipulators, speech

recognition, heuristic programming, representation theory,

mathematical theory of computation, and modeling of organic chemical

processes. This report summarizes the accomplishments and provides

bibliographies in each research area.

HAL, a new language for specification of manipulatory actions, is described. It is an attempt to improve upon previous efforts in this direction, in particular, APT and WAVE. The HAL system includes a source language with advanced features for describing individual motions of manipulators and complex series of motions making up an entire assembly and the runtime system necessary for execution of

programs.

A formal model for representing control in production systems is defined.

The formalism allows control to be directly specified independently of the

conflict resolution scheme, and thus allows the issues of control and

nondeterminism to be treated separately. Unlike previous approaches, it

allows control to be examined within a uniform and consistent framework.

It is shown that the formalism provides a basis for implementing control

constructs which, unlike existing schemes, retain all the properties

desired of a knowledge based system --- modularity, flexibility,

extensibility and explanatory capacity. Most importantly, it is shown

that these properties are not a function of the lack of control

constrains, but of the type of information allowed to establish these

constraints.

Within the formalism it is also possible to provide a meaningful notion of

the power of control constructs. This enables the types of control

required in production systems to be examined and the capacity of various

schemes to meet these requirements to be determined.

Schemes for improving system efficiency and resolving nondeterminism are

examined, and devices for representing such meta-level knowledge are

described. In particular, the objectification of control information is

shown to provide a better paradigm for problem solving and for talking

about problem solving. It is also shown that the notion of control

provides a basis for a theory of transformation of production systems, and

that this provides a uniform and consistent approach to problems involving

subgoal protection.

The formal structure of aesthetics systems is defined. Aesthetics systems

provide for the essential tasks of interpretation and evaluation in

aesthetic analyis. Kolmogorov's formulation of information theory is

applicable. An aesthetics system for a class of non-representational,

geometric paintings and its application to three actual paintings is

described in the Appendix.

The results in this paper contribute to the formulation of a semantic theory

of dynamic binding (fluid variables). The axioms and theorems are language

independent in that they don't talk about programs - i.e. syntactic objects -

but just about elements in certain domains. Firstly the equivalence (in the

circumstances where it's true) of "tying a knot" through the environment

(elaborated in the paper) and taking a least fixed point is shown. This is

central in proving the correctness of LISP "eval" type interpreters. Secondly

the relation which must hold between two environments if a program is to

have the same meaning in both is established. It is shown how the theory can

be applied to LISP to yield previously known facts.

Manipulator programs in a high level language consist of manipulation

procedures and object model declarations. As higher level languages

are developed, the procedures will shrink while the declarations will

grow. This trend makes it desirable to develop means for automating

the generation of these declarations. A system is proposed which

would permit users to specify certain object models interactively,

using the manipulator itself as a measuring tool in three dimensions.

A preliminary version of the system has been tested.

The report contains first a brief description of Preference Semantics, a system

of representation and analysis of the meaning structure of natural language. The

analysis algorithm which transforms phrases into semantic items called templates

has been considered in detail elsewhere, so this report concentrates on the

second phase of analysis, which binds templates together into a higher level

semantic block corresponding to an English paragraph, and which, in operation,

interlocks with the French generation procedure. During this phase, the semantic

relations between templates are extracted, pronouns are referred and those word

disambiguations are done that require the context of a whole paragraph. These

tasks require items called PARAPLATES which are attached to keywords such as

prepositions, subjunctions and relative pronouns. The system chooses the

representation which maximizes a carefully defined "semantic density".

A system for the generation of French sentences is described, based on the

generation of French sentences is described, based on the recursive evaluation

of procedural generation patterns called STEREOTYPES. The stereotypes are

semantically context sensitive, are attached to each sense of English words

and keywords and are carried into the representation by the analysis procedure.

The representation of the meaning of words, and the versatility of the

stereotype format, allow for fine meaning distinctions to appear in the French,

and for the construction of French differing radically from the English origin.

A notation is suggested for defining the syntax of a language in abstract form, specifying only its semantic constituents. A simple language is presented in this form and its semantic definition given

in terms of these constituents. Methods are then developed for translating this language, first into LISP code and from there to machine code, and for proving that the translation is correct.

A compiling algorithm is given which maps a class of Algol-like

programs into a class of machine language programs. The semantics,

i. e., the effect of execution, of each class is specified, and

recursion induction used to prove that program semantics is

preserved under the mapping defined by the compiling algorithm.

We describe an on-line program for algebraic simplification. The

program is written in LISP 1.5 for the Q-32 computer at System

Development Corporation in Santa Monica, California. The program

has in its entirety been written and debugged from a teletype

station at Stanford University.

We present here an axiomatic approach which enables one to prove by

formal methods that his program is "totally correct" (i.e., it

terminates and is logically correct -- does what it is supposed to

do). The approach is similar to Hoare's approach for proving that

a program is "partially correct" (i.e., that whenever it terminates

it produces correct results). Our extension to Hoare's method lies in

the possibility of proving correctness and termination at once, and

in the enlarged scope of properties that can be proved by it.

In this work we show that it is possible to express most properties

regularly observed in algorithms in terms of 'partial correctness'

(i.e., the property that the final results of the algorithm, if any,

satisfy some given input-output relation). This result is of special

interest since 'partial correctness' has already been formulated in

predicate calculus and in partial function logic for many classes of

algorithms.

A systematic method of identification of all possible graph isomers

consistent with a given empirical formula is described. The method,

embodied in a computer program, generates a complete list of isomers.

Duplicate structures are avoided prospectively.

We describe Microalgol, a trivial subset of Algol, by means of an interpreter. The notions of abstract syntax and of 'state of the computation' permit a compact description of both syntax and semantics. We advocate an extension of this technique as a general

way of describing programming language.