|
[ Pobierz całość w formacie PDF ]
.e., storeentities, with which calculations can be done.It would be nice if we could referto a store entity from outside the store.This is the role of variable identifiers.A variable identifier is a textual name that refers to a store entity from outsidethe store.The mapping from variable identifiers to store entities is called anenvironment.The variable names in program source code are in fact variable identifiers.For example, Figure 2.9 has an identifier X (the capital letter X) that refers tothe store variable x1.This corresponds to the environment {X ’! x1}.To talkabout any identifier, we will use the notation x.The environment { x ’!x1}is the same as before, if x represents X.As we will see later, variable identifiersand their corresponding store entities are added to the environment by the localand declare statements.Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 2.2 The single-assignment store 47Inside the store"X" x1 123 nilFigure 2.11: A variable identifier referring to a valueInside the store"X" x1 personname age"George" x unbound2"Y"Figure 2.12: A partial value2.2.5 Value creation with identifiersOnce bound, a variable is indistinguishable from its value.Figure 2.10 shows whathappens when x1 is bound to [1 2 3] in Figure 2.9.With the variable identifierX, we can write the binding as X=[1 2 3].This is the text a programmer wouldwrite to express the binding.We can also use the notation x =[1 2 3] if wewant to be able to talk about any identifier.To make this notation legal in aprogram, x has to be replaced by an identifier.The equality sign = refers to the bind operation.After the bind completes,the identifier X still refers to x1, which is now bound to [1 2 3].This isindistinguishable from Figure 2.11, where Xrefers directly to[1 2 3].Followingthe links of bound variables to get the value is called dereferencing.It is invisibleto the programmer.2.2.6 Partial valuesA partial value is a data structure that may contain unbound variables.Fig-ure 2.12 shows the record person(name:"George" age:x2), referred to by theidentifier X.This is a partial value because it contains the unbound variable x2.The identifier Y refers to x2.Figure 2.13 shows the situation after x2 is boundto 25 (through the bind operation Y=25).Now x1 is a partial value with nounbound variables, which we call a complete value.A declarative variable canCopyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 48 Declarative Computation ModelInside the store"X" x1 personname age"George" x 252"Y"Figure 2.13: A partial value with no unbound variables, i.e., a complete valueInside the store"X" x1"Y" x2Figure 2.14: Two variables bound togetherbe bound to several partial values, as long as they are compatible with eachother.We say a set of partial values is compatible if the unbound variables inthem can be bound in such a way as to make them all equal.For example,person(age:25)and person(age:x)are compatible (because x can be boundto 25), but person(age:25)and person(age:26)are not.2.2.7 Variable-variable bindingVariables can be bound to variables.For example, consider two unbound variablesx1 and x2 referred to by the identifiers X and Y.After doing the bind X=Y, we getthe situation in Figure 2.14.The two variables x1 and x2 are equal to each other.The figure shows this by letting each variable refer to the other.We say that{x1, x2} form an equivalence set.4 We also write this as x1 = x2.Three variablesthat are bound together are written as x1 = x2 = x3 or {x1, x2, x3}.Drawn ina figure, these variables would form a circular chain.Whenever one variable inan equivalence set is bound, then all variables see the binding.Figure 2.15 showsthe result of doing X=[1 2 3].4From a formal viewpoint, the two variables form an equivalence class with respect to equal-ity.Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 2.2 The single-assignment store 49Inside the store"X" x11 2 3 nil"Y" x2Figure 2.15: The store after binding one of the variables2.2.8 Dataflow variablesIn the declarative model, creating a variable and binding it are done separately.What happens if we try to use the variable before it is bound? We call this avariable use error.Some languages create and bind variables in one step, so thatuse errors cannot occur.This is the case for functional programming languages.Other languages allow creating and binding to be separate.Then we have thefollowing possibilities when there is a use error:1.Execution continues and no error message is given.The variable s contentis undefined, i.e.it is garbage : whatever is found in memory.This iswhat C++ does.2.Execution continues and no error message is given.The variable is initial-ized to a default value when it is declared, e.g., to 0 for an integer.This iswhat Java does.3.Execution stops with an error message (or an exception is raised).This iswhat Prolog does for arithmetic operations.4.Execution waits until the variable is bound and then continues.These cases are listed in increasing order of niceness.The first case is very bad,since different executions of the same program can give different results.What smore, since the existence of the error is not signaled, the programmer is not evenaware when this happens.The second is somewhat better.If the program has ause error, then at least it will always give the same result, even if it is a wrongone.Again the programmer is not made aware of the error s existence.The third and fourth cases are reasonable in certain situations.In the third,a program with a use error will signal this fact, instead of silently continuing.This is reasonable in a sequential system, since there really is an error.It isunreasonable in a concurrent system, since the result becomes nondeterministic:depending on the timing, sometimes an error is signaled and sometimes not.Inthe fourth, the program will wait until the variable is bound, and then continue.This is unreasonable in a sequential system, since the program will wait forever.Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 50 Declarative Computation Models ::=skip Empty statement| s 1 s 2 Statement sequence| local x in s end Variable creation| x 1= x 2 Variable-variable binding| x = v Value creation| if x then s 1 else s 2 end Conditional| case x of pattern then s 1 else s 2 end Pattern matching| { x y 1.y n} Procedure applicationTable 2.1: The declarative kernel languageIt is reasonable in a concurrent system, where it could be part of normal operationthat some other thread binds the variable.5 The computation models of this bookuse the fourth case.Declarative variables that cause the program to wait until they are bound arecalled dataflow variables.The declarative model uses dataflow variables becausethey are tremendously useful in concurrent programming, i.e., for programs withactivities that run independently.If we do two concurrent operations, say A=23and B=A+1, then with the fourth solution this will always run correctly and givethe answer B=24.It doesn t matter whether A=23 is tried first or whether B=A+1is tried first.With the other solutions, there is no guarantee of this.This propertyof order-independence makes possible the declarative concurrency of Chapter 4.It is at the heart of why dataflow variables are a good idea.2.3 Kernel languageThe declarative model defines a simple kernel language.All programs in themodel can be expressed in this language.We first define the kernel languagesyntax and semantics.Then we explain how to build a full language on top ofthe kernel language.2.3.1 SyntaxThe kernel syntax is given in Tables 2.1 and 2.2.It is carefully designed to be asubset of the full language syntax, i.e
[ Pobierz całość w formacie PDF ]
zanotowane.pldoc.pisz.plpdf.pisz.plhanula1950.keep.pl
|