CSc 520 — Principles of Programming Languages27 : Control Structures — ProceduresChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergMarch 31, 20081 Procedures as Control Abstractions• A procedure is a collection of computation (expressions, statements, etc).that we can give a name.• A call-site is a location where a caller invokes a procedur e, the callee.• The caller waits for the callee to finish executing, at which time controls to the point after the call-site.• Most procedures are parameterized. The values passed to the procedure are called actual parameters.• The actual parameters are mapped to formal parameters, which hold the actual values within theprocedure.2 Procedures as Control Abstractions. . .• Some procedures (called functions) return a value. In some languages, a function can return multiplevalues.• Most languages use a call-stack on which actual parameters and local variables are stored.• Different languages have different rules as to how parameters should be passed to a procedure.3 Questions• How do we deal with recursion? Every new recursive call should get its own set of local variables.• How do we pass parameters to a procedure?– Call-by-Value or Call-by-Reference?– In registers or on the stack?• How do we allocate/access local and global variables?• How do we access non-local variables? (A variable is non-local in a procedure P if it is declared inprocedure that statically encloses P.)1• How do we pass large structured parameters (arrays and records)?Case Study — Pascal4 Pascal ProceduresPROCEDURE Name (list of formals);CONST (* Constant declarations *)TYPE (* Type declarations *)VAR (* Variable declarations *)(* Procedure and function definitions *)BEGIN(* procedure body *)END;• Note the similarity with the program structure.• Note that procedures can b e nested.• Note the semicolon after the end.5 Pascal Procedures. . .• Formal parameters look like this:procedure name (formal1:type1; formal2:type2;...);or like thisprocedure name (formal1,formal2...:type1; ...);• By default, arguments are passed by value. var indicates that they are passed by reference:procedure name (var formal1:type1; ...);6 Pascal Procedures. . .• Functions are similar to procedures but return values:function func1 (formals);beginfunc1 := 99;end;• To return a value assign it to the function name.27 Pascal Procedures. . .• Procedures can be nes ted:procedure A ();procedure B();begin...end;begin...end;• Names declared in an outer procedure are visible to nested procedures unless the name is redeclared.8 Pascal Procedures. . .• Procedures can be recursive. The forward declaration is used to handle mutually recursive procedures:procedure foo (); forward;procedure bar ();beginfoo();end;procedure foo();beginbar();end;3Case Study — Ada9 Ada — Subprogram Declarationsprocedure Traverse_Tree;procedure Increment(X : in out Integer);procedure Right_Indent(Margin : out Line_Size);procedure Switch(From, To : in out Link);function Random return Probability;function Min_Cell(X : Link) return Cell;function Next_Frame(K : Positive) return Frame;function Dot_Product(Left, Right : Vector)return Real;10 Ada — Subprogram Declarationsfunction "*"(Left, Right : Matrix) return Matrix;• Examples of in parameters with default expressions:procedure Print_Header(Pages : in Natural;Header : in Line :=(1 .. Line’Last => ’ ’);Center : in Boolean := True);11 Ada — Subprogram Bodies-- Example of procedure body:procedure Push(E : in Element_Type;S : in out Stack) isbeginif S.Index = S.Size thenraise Stack_Overflow;elseS.Index := S.Index + 1;S.Space(S.Index) := E;end if;end Push;12 Ada — Procedure CallTraverse_Tree;Print_Header(128, Title, True);4Switch(From => X, To => Next);Print_Header(128, Header => Title,Center => True);Print_Header(Header=>Title,Center=>True, Pages=>128);--Examples of function calls:Dot_Product(U, V)Clock13 Ada — Procedure Call-- Procedures with default expressions:procedure Activate(Process : in Process_Name;After : in Process_Name:=No_Process;Wait : in Duration := 0.0;Prior : in Boolean := False);procedure Pair(Left, Right :in Person_Name:=new Person);14 Ada — Procedure Call. . .-- Examples of their calls:Activate(X);Activate(X, After => Y);Activate(X, Wait => 60.0, Prior => True);Activate(X, Y, 10.0, False);Pair;Pair(Left => new Person, Right => new Person);15 Ada — Overloaded Callsprocedure Put(X : in Integer);procedure Put(X : in String);procedure Set(Tint : in Color);procedure Set(Signal : in Light);-- Examples of their calls:Put(28);Put("no possible ambiguity here");Set(Tint=>Red); -- Set(Red) is ambiguous.Set(Signal=>Red); -- Red can denote eitherSet(Color’(Red)); -- a Color or a Light516 Ada — Userdefined Operatorsfunction "+" (Left,Right:Matrix) return Matrix;function "+" (Left,Right:Vector) return Vector;-- assuming that A, B, and C are of-- the type Vector the following two-- statements are equivalent:A := B + C;A := "+"(B, C);17 Readings and References• Read Scott, pp. 117–123, 428–43318 Summary• Each procedure call pushes a new activation record on the run-time stack. The AR contains localvariables, actual parameters, a static (access) link, a dynamic (control) link, the return address, savedregisters, etc.• The frame pointer (FP) (which is usually kept in a register) points to a fixed place in the topmostactivation record. Each local variable and actual parameter is at a fixed offset from FP.19 Summary. . .• The dynamic link is used to restore the FP when a procedure call returns.• The static link is used to access non-local variables, i.e. local variables which are declared within aprocedure which statically encloses the current
View Full Document