Haridi Seif, Van Roy Peter Concepts, Techniques, and Models of Compute rProgramming

[ Pobierz całość w formacie PDF ]
.Twoof them, X and Z, are also formal parameters.The third, Y, is not a formalparameter.It has to be defined by the environment where the procedure isdeclared.The procedure value itself must have a mapping from Y to the store.Otherwise, we could not call the procedure since Y would be a kind of danglingreference.Let us see what happens in the general case.A procedure expression is writtenas:Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.2.4 Kernel language semantics 67proc { $ y 1.y n} s endThe statement s can have free variable identifiers.Each free identifer is either aformal parameter or not.The first kind are defined anew each time the procedureis called.They form a subset of the formal parameters { y 1,., y n}.The secondkind are defined once and for all when the procedure is declared.We call themthe external references of the procedure.Let us write them as { z 1,., z k}.Then the procedure value is a pair:( proc { $ y 1.y n} s end, CE )Here CE (the contextual environment) is E|{ z ,., z n}, where E is the environ-1ment when the procedure is declared.This pair is put in the store just like anyother value.Because it contains an environment as well as a procedure definition, a pro-cedure value is often called a closure or a lexically-scoped closure.This is becauseit closes (i.e., packages up) the environment at procedure definition time.Thisis also called environment capture.When the procedure is called, the contextu-al environment is used to construct the environment of the executing procedurebody.2.4.4 Suspendable statementsThere are three statements remaining in the kernel language:s ::=.| if x then s 1 else s 2 end| case x of pattern then s 1 else s 2 end| { x y 1.y n}What should happen with these statements if x is unbound? From the discussionin Section 2.2.8, we know what should happen.The statements should simplywait until x is bound.We say that they are suspendable statements.They havean activation condition, which is a condition that must be true for executionto continue.The condition is that E( x ) must be determined, i.e., bound to anumber, record, or procedure.In the declarative model of this chapter, once a statement suspends it willnever continue, because there is no other execution that could make the activationcondition true.The program simply stops executing.In Chapter 4, when weintroduce concurrent programming, we will have executions with more than onesemantic stack.A suspended stack ST can become runnable again if another stackdoes an operation that makes ST s activation condition true.In that chapter weshall see that communication from one stack to another through the activationcondition is the basis of dataflow execution.For now, let us stick with just onesemantic stack.Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.68 Declarative Computation ModelConditional (the if statement)The semantic statement is:(if x then s 1 else s 2 end, E)Execution consists of the following actions:" If the activation condition is true (E( x ) is determined), then do the fol-lowing actions: If E( x ) is not a boolean (true or false) then raise an error condi-tion. If E( x ) is true, then push ( s 1, E) on the stack. If E( x ) is false, then push ( s 2, E) on the stack." If the activation condition is false, then execution does not continue.Theexecution state is kept as is.We say that execution suspends.The stop canbe temporary.If some other activity in the system makes the activationcondition true, then execution can resume.Procedure applicationThe semantic statement is:({ x y 1.y n}, E)Execution consists of the following actions:" If the activation condition is true (E( x ) is determined), then do the fol-lowing actions: If E( x ) is not a procedure value or is a procedure with a number ofarguments different from n, then raise an error condition. If E( x ) has the form (proc { $ z 1.z n} s end, CE) then push( s , CE + { z 1 �! E( y 1),., z n �! E( y n)}) on the stack." If the activation condition is false, then suspend execution.Pattern matching (the case statement)The semantic statement is:(case x of lit ( feat 1: x 1.feat n: x n) then s 1 else s 2 end, E)(Here lit and feat are synonyms for literal and feature.) Execution consistsof the following actions:Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.2.4 Kernel language semantics 69" If the activation condition is true (E( x ) is determined), then do the fol-lowing actions: If the label of E( x ) is lit and its arity is [ feat 1 � � � feat n], thenpush ( s 1, E + { x 1 �! E( x ).feat 1,., x n �! E( x ).feat n}) onthe stack. Otherwise push ( s 2, E) on the stack." If the activation condition is false, then suspend execution.2.4.5 Basic concepts revisitedNow that we have seen the kernel semantics, let us look again at the examples ofSection 2.4.1 to see exactly what they are doing.We look at three examples; wesuggest you do the others as exercises.Variable identifiers and static scopingWe saw before that the following statement s displays first 2 and then 1:��local X in��X=1�� local X in�� X=2s a" s 1 a"{Browse X}�� ó��end�� s 2 a" {Browse X}��ó�endThe same identifier X first refers to 2 and then refers to 1.We can understandbetter what happens by executing s in our abstract machine.1.The initial execution state is:( [( s , �)], � )Both the environment and the store are empty (E = � and � = �).2.After executing the outermost local statement and the binding X=1, weget:( [( s 1 s 2, {X�! x})],{x =1} )The identifier X refers to the store variable x, which is bound to 1.Thenext statement to be executed is the sequential composition s 1 s 2.3.After executing the sequential composition, we get:Copyright � 2001-3 by P.Van Roy and S.Haridi.All rights reserved.70 Declarative Computation Model( [( s 1, {X �! x}), ( s 2, {X�! x})],{x =1} )Each of the statements s 1 and s 2 has its own environment.At this point,the two environments have identical values.4.Let us start executing s 1.The first statement in s 1 is alocalstatement.Executing it gives:( [(X=2 {Browse X}, {X �! x }), ( s 2, {X �! x})],{x , x =1} )This creates the new variable x and calculates the new environment {X �!x} + {X �! x }, which is {X �! x }.The second mapping of X overrides thefirst.5.After the binding X=2 we get:( [({Browse X}, {X �! x }), ({Browse X}, {X �! x})],{x =2, x =1} )(Remember that s 2 is a Browse.) Now we see why the two Browse callsdisplay different values.It is because they have different environments.Theinner local statement is given its own environment, in which X refers toanother variable.This does not affect the outer local statement, whichkeeps its environment no matter what happens in any other instruction [ Pobierz całość w formacie PDF ]