Programming langauge help

profilecrazybob3
pl-chapter10.ppt
Home>Computer Science homework help>Programming langauge help

Chapter 10

Implementing Subprograms

*

Chapter 10 Topics

The General Semantics of Calls and Returns

Implementing “Simple” Subprograms

Implementing Subprograms with Stack-Dynamic Local Variables

Nested Subprograms

Blocks

Implementing Dynamic Scoping

*

The General Semantics
of Calls and Returns

Definition:

The subprogram linkage of a language is the collection of operations performed during a subprogram call and return.

A subprogram call has numerous actions associated with it:

  • Parameter passing methods
  • Static local variables
  • Execution status of calling program
  • Transfer of control
  • Subprogram nesting

*

Implementing “Simple” Subprograms
Call Semantics

1. Save the execution status of the caller

2. Carry out the parameter-passing process

3. Pass the return address to the callee

4. Transfer control to the callee

*

Implementing “Simple” Subprograms
Return Semantics

1. If out-mode parameters are used, move the final values of those parameters to their corresponding actual parameters

2. If there is a functional return value, store it where the caller can get it

3. Restore the execution status of the caller

4. Transfer control back to the caller

*

Implementing “Simple” Subprograms Parts

Two separate parts:

  • the actual code (which never changes), and
  • the non-code part (local variables and data that can change)

The format, or layout, of the non-code part of an executing subprogram is called an activation record

An activation record instance is a concrete example of an activation record (the collection of data for a particular subprogram activation)

*

An Activation Record for “Simple” Subprograms

*

Code and Activation Records of a Program with “Simple” Subprograms

*

Implementing Subprograms with Stack-Dynamic Local Variables

Requires a more complex activation record

The compiler must generate code to perform implicit allocation and de-allocation of local variables

Recursion must be supported:

this adds the possibility of multiple

simultaneous activations of a subprogram.

*

Typical Activation Record for a Language with Stack-Dynamic Local Variables

*

Implementing Subprograms with Stack-Dynamic Local Variables Activation Record

  • The activation record format is static, but its size may be dynamic

  • The dynamic link points to the top of an instance of the activation record of the caller

  • An activation record instance is dynamically created when a subprogram is called

  • Run-time stack

*

An Example
C Function

void sub(float total,

int part)

{

int list[4];

float sum;

…

}

*

An Example Without Recursion

void A(int x) {

int y;

...

C(y);

...

}

void B(float r) {

int s, t;

...

A(s);

...

}

main calls B

B calls A

A calls C

void C(int q) {

...

}

void main() {

float p;

...

B(p);

...

}

*

An Example Without Recursion

*

Dynamic Chain and Local Offset

  • The collection of dynamic links in the stack at a given time is called the dynamic chain, or call chain

  • Local variables can be accessed by their offset from the beginning of the activation record. This offset is called the local_offset

  • The local_offset of a local variable can be determined by the compiler at compile time

*

An Example With Recursion

  • The activation record used in the previous example supports recursion, e.g.

int factorial (int n) {

<-----------------------------1

if (n <= 1) return 1;

else return (n * factorial(n - 1));

<-----------------------------2

}

void main() {

int value;

value = factorial(3);

<-----------------------------3

}

*

Activation Record for factorial

*

Stack for factorial

*

Stack for factorial

*

Stack for factorial

*

Stack for factorial

*

Stack for factorial

*

Stack for factorial

*

Stack for factorial

*

Stack for factorial

*

Nested Subprograms

Some non-C-based static-scoped languages (e.g., Fortran 95, Ada, JavaScript) use stack-dynamic local variables and allow subprograms to be nested

All variables that can be non-locally accessed reside in some ARI in the stack

The process of locating a non-local reference:

  • Find the correct ARI
  • Determine the correct offset in that ARI

*

Locating a Non-local Reference

Finding the offset is easy!

Finding the correct ARI is more complex:

Static semantic rules guarantee:

all non-local variables that are in scope

have been allocated in some ARI that is

on the stack when the reference is made

*

Static Scoping

A static chain is a chain of static links that connects certain ARIs

The static link in an ARI for subprogram A points to one of the ARIs of A's static parent

The static chain from an ARI connects it to all of its static ancestors

*

Example Pascal Program

Call sequence for MAIN_2

MAIN_2 calls BIGSUB

BIGSUB calls SUB2

SUB2 calls SUB3

SUB3 calls SUB1

program MAIN_2;

var X : integer;

procedure BIGSUB;

var A, B, C : integer;

procedure SUB1;

var A, D : integer;

begin { SUB1 }

A := B + C; <-------------1

end; { SUB1 }

procedure SUB2(X : integer);

var B, E : integer;

procedure SUB3;

var C, E : integer;

begin { SUB3 }

SUB1;

E := B + A: <----------2

end; { SUB3 }

begin { SUB2 }

SUB3;

A := D + E; <-------------3

end; { SUB2 }

begin { BIGSUB }

SUB2(7);

end; { BIGSUB }

begin

BIGSUB;

end; { MAIN_2 }

*

program MAIN_2;

var X : integer;

procedure BIGSUB;

var A, B, C : integer;

procedure SUB1;

var A, D : integer;

begin { SUB1 }

A := B + C; <-------------1

end; { SUB1 }

procedure SUB2(X : integer);

var B, E : integer;

procedure SUB3;

var C, E : integer;

begin { SUB3 }

SUB1;

E := B + A: <----------2

end; { SUB3 }

begin { SUB2 }

SUB3;

A := D + E; <-------------3

end; { SUB2 }

begin { BIGSUB }

SUB2(7);

end; { BIGSUB }

begin

BIGSUB;

end; { MAIN_2 }

*

Displays

  • An alternative to static chains

  • A “run-time descriptor” for static chains

  • Static links are stored in a single array called a display

  • The contents of the display at any given time is a list of addresses of the accessible activation record instances

*

Blocks

A block is a user-specified local scope for variables

An example in C: {

int temp;

temp = list [upper];

list [upper] = list [lower];

list [lower] = temp

}

The lifetime of temp in the above example begins when control enters the block

Advantage: the local variable temp cannot interfere with any other variable with the same name

*

Implementing Blocks

Two Methods

1. Treat blocks as parameter-less subprograms that are always called from the same location

  • Every block has an activation record
  • An ARI is created every time the block is executed

2. Since the maximum storage required for a block can be statically determined, this amount of space can be allocated after the local variables in the activation record

*

Implementing Blocks

void main() {

int x, y, z;

while (...) {

int a, b, c;

...

while (...) {

int d, e;

...

}

}

while (...) {

int f, g;

...

}

...

}

*

Implementing Dynamic Scoping

  • Deep Access: non-local references are found by searching the activation record instances on the dynamic chain

  • Shallow Access: put locals in a central place
  • One stack for each variable name
  • Central table with an entry for each variable name

*

Using Shallow Access to Implement Dynamic Scoping

*

Summary

  • Subprogram linkage semantics require many actions
  • Simple subprograms have relatively basic actions
  • Stack-dynamic languages are more complex
  • Subprograms with stack-dynamic local variables and nested subprograms have two components
  • actual code
  • activation record instances (ARIs)
  • An ARI contain formal parameters, local variables, and more
  • Access to non-local variables depends on scope
  • In static-scoped languages with nested subprograms, static chains are used
  • In dynamic-scoped languages, dynamic chains or a central variable table method is used

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*