Exam 2

Question 1

scope

Answer 1

visibility of names in source program

Question 2

storage

Answer 2

memory space associated with names

Question 3

lifetime

Answer 3

the time interval a variable is allocated with memory

Question 4

static (lexical) scope

Answer 4

scopes can be determined by the compiler, all bindings for identifiers can be resolved by examining the program

Question 5

let

Answer 5

scope of a variable declared in expression is the body

Question 6

let*

Answer 6

scope of a variable declared in expression is body and other expressions following

Question 7

letrec

Answer 7

variable does not need to be defined first for it to be in scope (allows for recursive definitions)

Question 8

symbol table

Answer 8

table of names and their bindings

Question 9

single scope

Answer 9

a dictionary or hash map

Question 10

nested scope

Answer 10

a tree of symbol tables; each scope has one symbol table, each symbol table may have a parent

Question 11

Name collision in symbol table

Answer 11

To find a binding:

1. start from table of current scope
2. Go up until name is found
3. Fail if no table contains the name

Question 12

Static Scoping

Answer 12

bindings determined by lexical structure, local renaming principle

Question 13

Dynamic scoping

Answer 13

bindings depend on flow of control

always use most recent, active binding, names important, meaning of a variable can change

Question 14

scope vs. lifetime

Answer 14

scope = visibility of a binding/name
lifetime = creation/destruction of storage

Question 15

global variable

Answer 15

static area, visible in entire program

Question 16

local variable

Answer 16

stack, visible in a function

Question 17

when are scope and lifetime not the same?

Answer 17

heap allocated memory, functions returned as values

Question 18

shallow binding

Answer 18

subroutine is passed as a parameter, binding happens when subroutine is called

Question 19

deep binding

Answer 19

when a subroutine is passed as a parameter, when the reference is created

Question 20

function closure

Answer 20

for deep binding; contains a pointer to function and current symbol table

Question 21

What type of binding is implemented for dynamic scoping

Answer 21

both shallow and deep; shallow has a higher cost at run time

Question 22

What type of binding is implemented for static scoping?

Answer 22

Deep binding; shallow binding has never been implemented

Question 23

alias

Answer 23

two variables point to the same memory location

Question 24

overloading

Answer 24

uses the number or type of parameters to distinguish functions

Question 25

coercion

Answer 25

the process by which a compiler automatically converts a value of one type to value of another type

Question 26

coercion vs. overloading

Answer 26

coercion converts parameters to fit function def; overloading allows compiler to pick function implementation that fits

Question 27

polymorphism

Answer 27

function with multiple forms/uses

Question 28

parametric polymorphism

Answer 28

function with aset of types

Question 29

subtype polymorphism

Answer 29

function with one type, and it's refinements

Question 30

Hows does the compiled code locate a variable used in a function at run time?

Answer 30

Start address = base addr (of scope) + offset (in the scope)

Question 31

code section

Answer 31

read only, stores source code

Question 32

data section

Answer 32

static data, stack, heap

Question 33

stack pointer register

Answer 33

esp

Question 34

frame pointer register

Answer 34

ebp

Question 35

frame layout

Answer 35

``` args temporaries local vars bookkeeping return addr ```

Question 36

bookkeeping in stack frame

Answer 36

reference to the stack frame of the caller

Question 37

static link

Answer 37

a pointer to the frame of enclosing function

Question 38

dynamic link

Answer 38

pointer to the previous frame in the current execution

Question 39

Example type errors

Answer 39

float addition on two ints, assign a string to float, pass int to func expecting string

Question 40

type meanings

Answer 40

denotational: a set of values constructive: set of primitive types, type constructors, abstraction: an interface (set of operations)

Question 41

Why types?

Answer 41

identify/prevent type errors, documentation, support optimization, program organization/abstraction

Question 42

Constructed types

Answer 42

products, unions, arrays, lists

Question 43

type system

Answer 43

type equilence, type compatibility, type safety

Question 44

strongly typed

Answer 44

all type errors caught by type checking

Question 45

weakly typed

Answer 45

type checking my miss type errors

Question 46

static typing

Answer 46

type checking happens at compile time

Question 47

dynamic typing

Answer 47

type checking happens at run time

Question 48

type inference

Answer 48

the type-checker infers types for variables

Question 49

example of type error in c

Answer 49

union U {int a; float p} u; float x = 1.0; u.a = 1; x = x + u.p;

Question 50

records and structures

Answer 50

laid out contiguously, possible holes for alignment, compilers may re-arrange fields o minimize holes

Question 51

discriminated union type

Answer 51

a combination of a tag (like an enum) and a payload per possibility (like a union)

Question 52

sum type

Answer 52

alternation of types

Question 53

product types

Answer 53

concatenation of types

Question 54

c array

Answer 54

static/stack/heap allocated size statically/dynamically determined bound not checked

Question 55

java array

Answer 55

heap allocated size dynamically determined array size is part of stored data (dope vector) array bounds checked

Question 56

Row major address calculation

Answer 56

[10][100] | A[i][j] = 4(i*100+j)

Question 57

Column major address calculation

Answer 57

[10][100] | A[i][j] = 4(j*10+i)

Question 58

dangling reference

Answer 58

pointer to a deallocated address

Question 59

tombstones

Answer 59

each ehap variable is given another memory location (tombstone); tombstone points to the heap variable; all pointers to var point to tombstone

Question 60

locks and keys

Answer 60

when heap var allocated: allocate storage; allocate an int which holds a lock value; return a pari of key value and address; key value = lock value

Question 61

references

Answer 61

restricted pointers - cannot be used as value or operated in anyway

Question 62

Caller Save vs. Callee Save Separation of responsibility

Answer 62

Caller assumes callee will not destroy callee saves | Callee assumes nothing is value in caller saves

Question 63

What needs to be done before P calls Q

Answer 63

Save current frame pointer, save caller-save registers, changing stack and frame pointers, save return addr, change prog counter, pass params

Question 64

What needs to be done before Q returns to P

Answer 64

Restoring saved registers | Deallocating stack space of Q, restore program counter, pass return vals

Question 65

Program Counter

Answer 65

Always points to the instruction following the one being executed, can be modified by jump, call, return

Question 66

Typical calling sequence for caller

Answer 66

save registers, computes values of params, move them to stack or registers, switch control to callee

Question 67

Typical calling seq for callee prologue

Answer 67

allocate frame (change sp), saves previous frame pointer and sets new one, saves registers that might be overwritten in the callee

Question 68

Typical Calling Sequence Callee Epilogue

Answer 68

Moves return val into stack or register, restore callee-saves registers, restore fp and sp, transfer control to caller

Question 69

Call-by-value

Answer 69

args evaluated to values, memory or registers allocated for args on AR, arg values copied into AR, AR destroyed when callee returns

Question 70

Call by Value Characteristics

Answer 70

Formal and Actual Parameters have separate memory: their values may diverge; actual parameters may not directly be changed in callee, args can be complex expressions

Question 71

Call by Value Performance

Answer 71

Can pass in pointer to avoid copying cost

Question 72

Call by Reference Calling Mechanism

Answer 72

Args are evaluated to their values; memory or registers allocated for args on AR, arg address stored in AR

Question 73

Call by reference characteristics

Answer 73

formal parameter is an alias of actual parameter

Question 74

Call by reference performance

Answer 74

avoids the cost of memory copy

Question 75

Call by Value Return

Answer 75

Before callee returns, AR values copied back to actual arguments

Question 76

Call by Name (Lazy Evaluation)

Answer 76

Arguments ARE NOT EVALUATED TO THEIR VALUES

Question 77

Return Values

Answer 77

Fix size and size (callee stores values in callers AR) determined at run time (callee stores results in heap)

Question 78

Callee is more nested

Answer 78

When func f1 calls f2 and n(f1) < n(f2) (callee more nested), f1 must be the immediate lexical ancestor of f2

Question 79

Caller is more nested

Answer 79

When f1 calls f2 and n(f1) >= n(f2) caller is more nested, f1 must be defined in some function f3, and f2 is immediately defined in f3