1、ce the middle of the twentieth century, we express the algorithms we conceive using formal languages: programming languages. Computer scientists are not the only ones who use formal languages. Op- tometrists, for example, prescribe eyeglasses using very technical expressions, such as “OD: -1.25 (-0.
2、50) 180OS: -1.00 (-0.25) 180”, in which the parenthe- ses are essential. Many such formal languages have been created throughout history: musical notation, algebraic notation, etc. In particular, such languages have long been used to control machines, such as looms and cathedral chimes. However, unt
3、il the appearance of programming languages, those languages were only of limited importance: they were restricted to specialised fi elds with only a few specialists and written texts of those languages remained relatively scarce. This situation has changed with the appearance of programming lan- gua
4、ges, which have a wider range of applications than the prescription of eye- glasses or the control of a loom, are used by large communities, and have allowed the creation of programs of many hundreds of thousands of lines. The appearance of programming languages has allowed the creation of ar- tifi
5、cial objects, programs, of a complexity incomparable to anything that has come before, such as steam engines or radios. These programs have, in return, allowed the creation of other complex objects, such as integrated circuits made of millions of transistors, or mathematical proofs that are hundreds
6、 of thou- sands of pages long. It is very surprising that we have succeeded in writing such complex programs in languages comprising such a small number of con- structs assignment, loops, etc. that is to say in languages barely more sophisticated than the language of prescription eyeglasses. viiiPre
7、face Programs written in these programming languages have the novelty of not only being understandable by humans, which brings them closer to the scores used by organists, but also readable by machines, which brings them closer to the punch cards used in Barbarie organs. The appearance of programmin
8、g languages has therefore profoundly im- pacted our relationship with language, complexity, and machines. This book is an introduction to the principles of programming languages. It uses the Java language for support. It is intended for students who already have some experience with computer program
9、ming. It is assumed that they have learned some programming empirically, in a single programming language, other than Java. The fi rst objective of this book will then be to learn the fundamentals of the Java programming language. However, knowing a single programming language is not suffi cient to
10、be a good programmer. For this, you must not only know several languages, but be able to easily learn new ones. This requires that you understand universal concepts like functions or cells, which exist in one form or another in all programming languages. This can only be done by comparing two or mor
11、e languages. In this book, two comparison languages have been chosen: Caml and C. Therefore, the goal is not for the students to learn three programming languages simultaneously, but that with the comparison with Caml and C, they can learn the principles around which programming languages are create
12、d. This understanding will allow them to develop, if they wish, a real competence in Caml or in C, or in any other programming language. Another objective of this book is for the students to begin acquiring the tools which permit them to precisely defi ne the meaning of the program. This precision i
13、s, indeed, the only means to clearly understand what happens when a program is executed, and to reason in situations where complexity defi es intuition. The idea is to describe the meaning of a statement by a function operating on a set of states. However, our expectations of this objective remain m
14、odest: students wishing to pursue this goal will have to do so elsewhere. The fi nal objective of this course is to learn basic algorithms for lists and trees. Here too, our expectations remain modest: students wishing to pursue this will also have to look elsewhere. Contents 1.Imperative Core .1 1.
15、1Five Constructs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1.1Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 1.1.2Variable Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 1.1.3Seque
16、nce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 1.1.4Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.1.5Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.2Inpu
17、t and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.2.1Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.2.2Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.3Th
18、e Semantics of the Imperative Core. . . . . . . . . . . . . . . . . . . . . . .8 1.3.1The Concept of a State . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 1.3.2Decomposition of the State . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.3.3A Visual Representation of a State . . . .
19、 . . . . . . . . . . . . . . . 10 1.3.4The Value of Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.5Execution of Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.Functions . 19 2.1The Concept of Functions . . . . . . . . . . . . . . . . . . . . . .
20、. . . . . . . . . . . 19 2.1.1Avoiding Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.2Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.3Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21、. . . . 22 2.1.4The return Construct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.5Functions and Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.6Global Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.7The Main Prog
22、ram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 ix xContents 2.1.8Global Variables Hidden by Local Variables. . . . . . . . . . . . 27 2.1.9Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2The Semantics of Functions . . . . . .
23、. . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1The Value of Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.2Execution of Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.3Order of Evaluation . . . . . . . . . . . . . . . . . . . . . .
24、 . . . . . . . . . . 34 2.2.4Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.5C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3Expressions as Statements . . . . . . . . . . . . . . . . . . .
25、. . . . . . . . . . . . . . 37 2.4Passing Arguments by Value and Reference . . . . . . . . . . . . . . . . . . 37 2.4.1Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.2Caml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26、 . . . . . . . . 40 2.4.3C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.4.4Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.Recursion. 47 3.1Calling a Function from Inside the Body of that Function . . . . . 47 3.2 Recursive Defi nitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.1 Recursive Defi nitions and Circular Defi nitions. . . . . . . . . . 48 3.2.2 Recursive Defi nitions and Defi
