CanProgrammingBeLiberatedfromthevonNeumannStyle_bemadeof和from资源-CSDN文库

编程中体现的冯式风格

需积分: 10 109 浏览量 2009-05-14 14:49:26 上传评论 1 收藏 2.87MB PDF 举报

资源推荐

资源详情

资源评论

197 7 ACM Turing Award Lecture

The 1977 ACM Turing Award was presented to John Backus

at the ACM Annual Conference in Seattle, October 17. In intro-

ducing the recipient, Jean E. Sammet, Chairman of the Awards

Committee, made the following comments and read a portion of

the final citation. The full announcement is in the September

1977 issue of

Communications,

page 681.

"Probably there is nobody in the room who has not heard of

Fortran and most of you have probably used it at least once, or at

least looked over the shoulder of someone who was writing a For.

tran program. There are probably almost as many people who

have heard the letters BNF but don't necessarily know what they

stand for. Well, the B is for Backus, and the other letters are

explained in the formal citation. These two contributions, in my

opinion, are among the half dozen most important technical

contributions to the computer field and both were made by John

Backus (which in the Fortran case also involved some col-

leagues). It is for these contributions that he is receiving this

year's Turing award.

The short form of his citation is for 'profound, influential,

and lasting contributions to the design of practical high-level

programming systems, notably through his work on Fortran, and

for seminal publication of formal procedures for the specifica-

tions of programming languages.'

The most significant part of the full citation is as follows:

'... Backus headed a small IBM group in New York City

during the early 1950s. The earliest product of this group's

efforts was a high-level language for scientific and technical corn-

putations called Fortran. This same group designed the first

system to translate Fortran programs into machine language.

They employed novel optimizing techniques to generate fast

machine-language programs. Many other compilers for the lan-

guage were developed, first on IBM machines, and later on virtu-

ally every make of computer. Fortran was adopted as a U.S.

national standard in 1966.

During the latter part of the 1950s, Backus served on the

international committees which developed Algol 58 and a later

version, Algol 60. The language Algol, and its derivative com-

pilers, received broad acceptance in Europe as a means for de-

veloping programs and as a formal means of publishing the

algorithms on which the programs are based.

In 1959, Backus presented a paper at the UNESCO confer-

ence in Paris on the syntax and semantics of a proposed inter-

national algebraic language. In this paper, he was the first to

employ a formal technique for specifying the syntax of program-

ming languages. The formal notation became known as BNF-

standing for "Backus Normal Form," or "Backus Naur Form" to

recognize the further contributions by Peter Naur of Denmark.

Thus, Backus has contributed strongly both to the pragmatic

world of problem-solving on computers and to the theoretical

world existing at the interface between artificial languages and

computational linguistics. Fortran remains one of the most

widely used programming languages in the world. Almost all

programming languages are now described with some type of

formal syntactic definition.' "

Can Programming Be Liberated from the von

Neumann Style? A

Functional

Style and Its

Algebra of Programs

John Backus

IBM Research Laboratory, San Jose

General permission to

make fair

use in teaching or research of all

or part of this material is granted to individual readers and to nonprofit

libraries acting for them provided that ACM's copyright notice is

given

and that

reference is made to the publication, to its date of issue, and

to the fact that reprinting privileges were granted by permission of

the

Association for Computing Machinery. To otherwise reprint a

figure,

table, other substantial excerpt, or

the entire work requires

specific

permission as does republication, or systematic or multiple reproduc-

tion.

Author's address: 91 Saint Germain Ave., San Francisco, CA

94114.

613

Conventional programming languages are growing

ever more enormous, but not stronger. Inherent defects

at the most basic level cause them to be both fat and

weak: their primitive word-at-a-time style of program-

ming inherited from their common ancestor--the von

Neumann computer, their close coupling of semantics to

state transitions, their division of programming into a

world of expressions and a world of statements, their

inability to effectively use powerful combining forms for

building new programs from existing ones, and their lack

of useful mathematical properties for reasoning about

programs.

An alternative functional style of programming is

founded on the use of combining forms for creating

programs. Functional programs deal with structured

data, are often nonrepetitive and nonrecursive, are hier-

archically constructed, do not name their arguments, and

do not require the complex machinery of procedure

declarations to become generally applicable. Combining

forms can use high level programs to build still higher

level ones in a style not possible in conventional lan-

guages.

Communications August 1978

of Volume 2 i

the ACM Number 8

Associated with the functional style of programming

is an algebra of programs whose variables range over

programs and whose operations are combining forms.

This algebra can be used to transform programs and to

solve equations whose "unknowns" are programs in much

the same way one transforms equations in high school

algebra. These transformations are given by algebraic

laws and are carried out in the same language in which

programs are written. Combining forms are chosen not

only for their programming power but also for the power

of their associated algebraic laws. General theorems of

the algebra give the detailed behavior and termination

conditions for large classes of programs.

A new class of computing systems uses the functional

programming style both in its programming language and

in its state transition rules. Unlike von Neumann lan-

guages, these systems have semantics loosely coupled to

states--only one state transition occurs per major com-

putation.

Key Words and Phrases: functional programming,

algebra of programs, combining forms, functional forms,

programming languages, von Neumann computers, yon

Neumann languages, models of computing systems, ap-

plicative computing systems, applicative state transition

systems, program transformation, program correctness,

program termination, metacomposition

CR Categories: 4.20, 4.29, 5.20, 5.24, 5.26

Introduction

grams, and no conventional language even begins to

meet that need. In fact, conventional languages create

unnecessary confusion in the way we think about pro-

grams.

For twenty years programming languages have been

steadily progressing toward their present condition of

obesity; as a result, the study and invention of program-

ming languages has lost much of its excitement. Instead,

it is now the province of those who prefer to work with

thick compendia of details rather than wrestle with new

ideas. Discussions about programming languages often

resemble medieval debates about the number of angels

that can dance on the head of a pin instead of exciting

contests between fundamentally differing concepts.

Many creative computer scientists have retreated

from inventing languages to inventing tools for describ-

ing them. Unfortunately, they have been largely content

to apply their elegant new tools to studying the warts

and moles of existing languages. After examining the

appalling type structure of conventional languages, using

the elegant tools developed by Dana Scott, it is surprising

that so many of us remain passively content with that

structure instead of energetically searching for new ones.

The purpose of this article is twofold; first, to suggest

that basic defects in the framework of conventional

languages make their expressive weakness and their

cancerous growth inevitable, and second, to suggest some

alternate avenues of exploration toward the design of

new kinds of languages.

I deeply appreciate the honor of the ACM invitation

to give the 1977 Turing Lecture and to publish this

account of it with the details promised in the lecture.

Readers wishing to see a summary of this paper should

turn to Section 16, the last section.

1. Conventional Programming Languages: Fat and

Flabby

Programming languages appear to be in trouble.

Each successive language incorporates, with a little

cleaning up, all the features of its predecessors plus a few

more. Some languages have manuals exceeding 500

pages; others cram a complex description into shorter

manuals by using dense formalisms. The Department of

Defense has current plans for a committee-designed

language standard that could require a manual as long

as 1,000 pages. Each new language claims new and

fashionable features, such as strong typing or structured

control statements, but the plain fact is that few lan-

guages make programming sufficiently cheaper or more

reliable to justify the cost of producing and learning to

use them.

Since large increases in size bring only small increases

in power, smaller, more elegant languages such as Pascal

continue to be popular. But there is a desperate need for

a powerful methodology to help us think about pro-

614

2. Models of Computing Systems

Underlying every programming language is a model

of a computing system that its programs control. Some

models are pure abstractions, some are represented by

hardware, and others by compiling or interpretive pro-

grams. Before we examine conventional languages more

closely, it is useful to make a brief survey of existing

models as an introduction to the current universe of

alternatives. Existing models may be crudely classified

by the criteria outlined below.

2.1 Criteria for Models

2.1.1 Foundations. Is there an elegant and concise

mathematical description of the model? Is it useful in

proving helpful facts about the behavior of the model?

Or is the model so complex that its description is bulky

and of little mathematical use?

2.1.2 History sensitivity. Does the model include a

notion of storage, so that one program can save infor-

mation that can affect the behavior of a later program?

That is, is the model history sensitive?

2.1.3 Type of semantics. Does a program successively

transform states (which are not programs) until a termi-

nal state is reached (state-transition semantics)? Are

states simple or complex? Or can a "program" be suc-

cessively reduced to simpler "programs" to yield a final

Communications August 1978

of Volume 21

the ACM Number 8

"normal form program," which is the result (reduction

semantics)?

2.1.4 Clarity and conceptual usefulness of programs.

• Are programs of the model clear expressions of a process

or computation? Do they embody concepts that help us

to formulate and reason about processes?

2.2 Classification of Models

Using the above criteria we can crudely characterize

three classes of models for computing systems--simple

operational models, applicative models, and von Neu-

mann models.

2.2.1 Simple operational models. Examples: Turing

machines, various automata.

Foundations:

concise and

useful.

History sensitivity:

have storage, are history sen-

sitive.

Semantics:

state transition with very simple states.

Program clarity:

programs unclear and conceptually not

helpful.

2.2.2 Applicative models. Examples: Church's

lambda calculus [5], Curry's system of combinators [6],

pure Lisp [17], functional programming systems de-

scribed in this paper.

Foundations:

concise and useful.

History sensitivity:

no storage, not history sensitive.

Se-

mantics:

reduction semantics, no states.

Program clarity:

programs can be clear and conceptually useful.

2.2.3 Von Neumann models. Examples: von Neu-

mann computers, conventional programming languages.

Foundations:

complex, bulky, not useful.

History sensitiv-

ity:

have storage, are history sensitive.

Semantics:

state

transition with complex states.

Program clarity:

programs

can be moderately clear, are not very useful conceptually.

The above classification is admittedly crude and

debatable. Some recent models may not fit easily into

any of these categories. For example, the data-flow

languages developed by Arvind and Gostelow [1], Den-

nis [7], Kosinski [13], and others partly fit the class of

simple operational models, but their programs are clearer

than those of earlier models in the class and it is perhaps

possible to argue that some have reduction semantics. In

any event, this classification will serve as a crude map of

the territory to be discussed. We shall be concerned only

with applicative and von Neumann models.

3. Von Neumann Computers

In order to understand the problems of conventional

programming languages, we must first examine their

intellectual parent, the von Neumann computer. What is

avon Neumann computer? When von Neumann and

others conceived it over thirty years ago, it was an

elegant, practical, and unifying idea that simplified a

number of engineering and programming problems that

existed then. Although the conditions that produced its

architecture have changed radically, we nevertheless still

identify the notion of "computer" with this thirty year

old concept.

In its simplest form avon Neumann computer has

615

three parts: a central processing unit (or CPU), a store,

and a connecting tube that can transmit a single word

between the CPU and the store (and send an address to

the store). I propose to call this tube the

yon Neumann

bottleneck.

The task of a program is to change the

contents of the store in some major way; when one

considers that this task must be accomplished entirely by

pumping single words back and forth through the von

Neumann bottleneck, the reason for its name becomes

clear.

Ironically, a large part of the traffic in the bottleneck

is not useful data but merely names of data, as well as

operations and data used only to compute such names.

Before a word can be sent through the tube its address

must be in the CPU; hence it must either be sent through

the tube from the store or be generated by some CPU

operation. If the address is sent from the store, then

its

address must either have been sent from the store or

generated in the CPU, and so on. If, on the other hand,

the address is generated in the CPU, it must be generated

either by a fixed rule (e.g., "add 1 to the program

counter") or by an instruction that was sent through the

tube, in which case

its

address must have been sent ...

and so on.

Surely there must be a less primitive way of making

big changes in the store than by pushing vast numbers

of words back and forth through the von Neumann

bottleneck. Not only is this tube a literal bottleneck for

the data traffic of a problem, but, more importantly, it is

an intellectual bottleneck that has kept us tied to word-

at-a-time thinking instead of encouraging us to think in

terms of the larger conceptual units of the task at hand.

Thus programming is basically planning and detailing

the enormous traffic of words through the von Neumann

bottleneck, and much of that traffic concerns not signif-

icant data itself but where to find it.

4. Von Neumann Languages

Conventional programming languages are basically

high level, complex versions of the von Neumann com-

puter. Our thirty year old belief that there is only one

kind of computer is the basis of our belief that there is

only one kind of programming language, the conven-

tional--von Neumann--language. The differences be-

tween Fortran and Algol 68, although considerable, are

less significant than the fact that both are based on the

programming style of the von Neumann computer. Al-

though I refer to conventional languages as "von Neu-

mann languages" to take note of their origin and style,

I do not, of course, blame the great mathematician for

their complexity. In fact, some might say that I bear

some responsibility for that problem.

Von Neumann programming languages use variables

to imitate the computer's storage cells; control statements

elaborate its jump and test instructions; and assignment

statements imitate its fetching, storing, and arithmetic.

Communications August 1978

of Volume 21

the ACM Number 8

The assignment statement is the von Neumann bottle-

neck of programming languages and keeps us thinking

in word-at-a-time terms in much the same way the

computer's bottleneck does.

Consider a typical program; at its center are a number

of assignment statements containing some subscripted

variables. Each assignment statement produces a one-

word result. The program must cause these statements to

be executed many times, while altering subscript values,

in order to make the desired overall change in the store,

since it must be done one word at a time. The program-

mer is thus concerned with the flow of words through

the assignment bottleneck as he designs the nest of

control statements to cause the necessary repetitions.

Moreover, the assignment statement splits program-

ming into two worlds. The first world comprises the right

sides of assignment statements. This is an orderly world

of expressions, a world that has useful algebraic proper-

ties (except that those properties are often destroyed by

side effects). It is the world in which most useful com-

putation takes place.

The second world of conventional programming lan-

guages is the world of statements. The primary statement

in that world is the assignment statement itself. All the

other statements of the language exist in order to make

it possible to perform a computation that must be based

on this primitive construct: the assignment statement.

This world of statements is a disorderly one, with few

useful mathematical properties. Structured programming

can be seen as a modest effort to introduce some order

into this chaotic world, but it accomplishes little in

attacking the fundamental problems created by the

word-at-a-time von Neumann style of programming,

with its primitive use of loops, subscripts, and branching

flow of control.

Our fixation on yon Neumann languages has contin-

ued the primacy of the von Neumann computer, and our

dependency on it has made non-von Neumann languages

uneconomical and has limited their development. The

absence of full scale, effective programming styles

founded on non-von Neumann principles has deprived

designers of an intellectual foundation for new computer

architectures. (For a brief discussion of that topic, see

Section 15.)

Applicative computing systems' lack of storage and

history sensitivity is the basic reason they have not

provided a foundation for computer design. Moreover,

most applicative systems employ the substitution opera-

tion of the lambda calculus as their basic operation. This

operation is one of virtually unlimited power, but its

complete and efficient realization presents great difficul-

ties to the machine designer. Furthermore, in an effort

to introduce storage and to improve their efficiency on

von Neumann computers, applicative systems have

tended to become engulfed in a large von Neumann

system. For example, pure Lisp is often buried in large

extensions with many von Neumann features. The re-

suiting complex systems offer little guidance to the ma-

chine designer.

616

5. Comparison of von Neumann and Functional

Programs

To get a more detailed picture of some of the defects

of von Neumann languages, let us compare a conven-

tional program for inner product with a functional one

written in a simple language to be detailed further on.

5.1 A von Neumann Program for Inner Product

c.-~-0

for

i .~ I step 1 until n do

c .--- c + ali]xbIi]

Several properties of this program are worth noting:

a) Its statements operate on an invisible "state" ac-

cording to complex rules.

b) It is not hierarchical. Except for the right side of

the assignment statement, it does not construct complex

entities from simpler ones. (Larger programs, however,

often do.)

c) It is dynamic and repetitive. One must mentally

execute it to understand it.

d) It computes word-at-a-time by repetition (of the

assignment) and by modification (of variable i).

e) Part of the data, n, is in the program; thus it lacks

generality and works only for vectors of length n.

f) It names its arguments; it can only be used for

vectors a and b. To become general, it requires a proce-

dure declaration. These involve complex issues (e.g., call-

by-name versus call-by-value).

g) Its "housekeeping" operations are represented by

symbols in scattered places (in the for statement and the

subscripts in the assignment). This makes it impossible

to consolidate housekeeping operations, the most com-

mon of all, into single, powerful, widely useful operators.

Thus in programming those operations one must always

start again at square one, writing "for i .--- ..." and

"for j := ..." followed by assignment statements sprin-

kled with i's and j's.

5.2 A Functional Program for Inner Product

Def Innerproduct

- (Insert +)o(ApplyToAll x)oTranspose

Or, in abbreviated form:

Def IP - (/+)o(ax)oTrans.

Composition (o), Insert (/), and ApplyToAll (a) are

functional forms that combine existing functions to form

new ones. Thus fog is the function obtained by applying

first g and then fi and c~f is the function obtained by

applyingf to every member of the argument. If we write

f:x for the result of applying f to the object x, then we

can explain each step in evaluating Innerproduct applied

to the pair of vectors <<1, 2, 3>, <6, 5, 4>> as follows:

IP:<< i,2,3>, <6,5,4>> =

Definition of IP ~ (/+)o(ax)oTrans: << 1,2,3>, <6,5,4>>

Effect of composition, o ~ (/+):((ax):(Trans:

<<1,2,3>, <6,5,4>>))

Communications August 1978

of Volume 21

the ACM Number 8

Applying Transpose

Effect of ApplyToAll, a

Applying ×

Effect of Insert, /

Applying +

Applying + again

(/+):((ax): <<1,6>, <2,5>, <3,4>>)

(/+): <x: <1,6>, x: <2,5>, x: <3,4>>

(/+): <6,10,12>

+: <6, +: <lO,12>>

+: <6,22>

Let us compare the properties of this program with

those of the von Neumann program.

a) It operates only on its arguments. There are no

hidden states or complex transition rules. There are only

two kinds of rules, one for applying a function to its

argument, the other for obtaining the function denoted

by a functional form such as composition,

fog,

ApplyToAll, af, when one knows the functions f and g,

the

parameters

of the forms.

b) It is hierarchical, being built from three simpler

functions (+, x, Trans) and three functional forms fog,

a f, and/f.

c) It is static and nonrepetitive, in the sense that its

structure is helpful in understanding it without mentally

executing it. For example, if one understands the action

of the forms

fog

and af, and of the functions x and

Trans, then one understands the action of ax and of

(c~x)oTrans, and so on.

d) It operates on whole conceptual units, not words;

it has three steps; no step is repee, ted.

e) It incorporates no data; it is completely general; it

works for any pair of conformable vectors.

f) It does not name its arguments; it can be applied to

any pair of vectors without any procedure declaration or

complex substitution rules.

g) It employs housekeeping forms and functions that

are generally useful in many other programs; in fact,

only + and x are not concerned with housekeeping.

These forms and functions can combine with others to

create higher level housekeeping operators.

Section 14 sketches a kind of system designed to

make the above functional style of programming avail-

able in a history-sensitive system with a simple frame-

work, but much work remains to be done before the

above applicative style can become the basis for elegant

and practical programming languages. For the present,

the above comparison exhibits a number of serious flaws

in yon Neumann programming languages and can serve

as a starting point in an effort to account for their present

fat and flabby condition.

6. Language Frameworks versus Changeable Parts

Let us distinguish two parts of a programming lan-

guage. First,

its framework

which gives the overall rules

of the system, and second, its

changeable parts,

whose

existence is anticipated by the framework but whose

particular behavior is not specified by it. For example,

the for statement, and almost all other statements, are

part of Algol's framework but library functions and user-

defined procedures are changeable parts. Thus the

framework of a language describes its fixed features and

617

provides a general environment for its changeable fea-

tures.

Now suppose a language had a small framework

which could accommodate a great variety of powerful

features entirely as changeable parts. Then such a frame-

work could support many different features and styles

without being changed itself. In contrast to this pleasant

possibility, von Neumann languages always seem to have

an immense framework and very limited changeable

parts. What causes this to happen? The answer concerns

two problems of von Neumann languages.

The first problem results from the von Neumann

style of word-at-a-time programming, which requires

that words flow back and forth to the state, just like the

flow through the von Neumann bottleneck. Thus avon

Neumann language must have a semantics closely cou-

pled to the state, in which every detail of a computation

changes the state. The consequence of this semantics

closely coupled to states is that every detail of every

feature must be built into the state and its transition

rules.

Thus every feature of avon Neumann language must

be spelled out in stupefying detail in its framework.

Furthermore, many complex features are needed to prop

up the basically weak word-at-a-time style. The result is

the inevitable rigid and enormous framework of avon

Neumann language.

7. Changeable Parts and Combining Forms

The second problem of von Neumann languages is

that their changeable parts have so little expressive

power. Their gargantuan size is eloquent proof of this;

after all, if the designer knew that all those complicated

features, which he now builds into the framework, could

be added later on as changeable parts, he would not be

so eager to build them into the framework.

Perhaps the most important element in providing

powerful changeable parts in a language is the availabil-

ity of combining forms that can be generally used to

build new procedures from old ones. Von Neumarm

languages provide only primitive combining forms, and

the von Neumann framework presents obstacles to their

full use.

One obstacle to the use of combining forms is the

split between the expression world and the statement

world in von Neumann languages. Functional forms

naturally belong to the world of expressions; but no

matter how powerful they are they can only build expres-

sions that produce a one-word result. And it is in the

statement world that these one-word results must be

combined into the overall result. Combining single words

is not what we really should be thinking about, but it is

a large part of programming any task in von Neumann

languages. To help assemble the overall result from

single words these languages provide some primitive

combining forms in the statement world--the for, while,

and if-then-else statements--but the split between the

Communications August 1978

of Volume 21

the ACM Number 8

剩余28页未读，继续阅读

评论收藏

内容反馈

wide288

粉丝: 609
资源: 25

Can Programming Be Liberated from the von Neumann Style

所有程序员都应该去读的十篇论文.zip

iphone5s拆解图解

Fabber, A., & Mazlish, E. Liberated Parents, Liberated Child. New York, N. Y.: Grosset and Dunlap, 1974, 238 pp., [dollar]7.95

Sulzer, B., & Mayer, GR 学校人员行为矫正程序。 Hindsdale, Ill.: Dryden Press, 1972, 316 pp., [dollar]6.95 (paper)

Sulzer, B., & Mayer, G. R. Behavior modification procedures for school personnel. Hindsdale, Ill.: Dryden Press, 1972, 316 pp., [dollar]6.95 (paper)

The Liberated Students' Movement site.-开源

liberated:使用 webhook 构建的音乐生活方式博客

Fabber, A. 和 Mazlish, E. 解放了父母，解放了孩子。 纽约州纽约市：Grosset 和 Dunlap，1974 年，238 页，[美元]7.95

liberated_data:从其出版物中解放出来的数据集合

nm-prototype:3 周内为 Liberated Pixel Cup 2012 打造的原型角色扮演游戏

Quantum-orbit theory of low-energy above-threshold ionization on and off axis

Polymorphable-开源

第十五届蓝桥杯大赛软件赛省赛C++B组题目

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

编译器（gcc、g++）

Qt5.9 C++开发指南.pdf 及示例源码

Qt （高仿Visio）流程图组件开发，源码分享

mingw-w64-install.exe

Qt、QCustomPlot、实时波形绘制、实时曲线绘制

C/C++中文帮助文档

GitKrakenSetup-6.5.1 版本，包括win和linux

2023蓝桥杯C++A组省赛真题

QT7.0.2，2022.05最新版本，包含openssl1.1.1和WebEngine等

基于eNSP模拟企业网的实现（代码＋毕业设计＋论文）

C++面试八股文深度总结

PUBG吃鸡罗技鼠标宏

PCAN-Explorer 5 安装包，无需licence

最新资源

Fabber, A. 和 Mazlish, E. 解放了父母，解放了孩子。纽约州纽约市：Grosset 和 Dunlap，1974 年，238 页，[美元]7.95