proglang-09-26-2019.md

Stack Frames - Programming Languages - Sep 26th, 2019

Table of Contents:

• [Review] Eq, Ord, Show for custom List type
• Stack Frames (Activation Records)
  • Call-by-reference vs Call-by-value
    • In Python
    • In Java
• HW 4 Intro

---

[Review] Eq, Ord, Show for custom List type

data List a = Cons a (List a) | Null

instance Eq a => Eq (List a) where
    Null == Null = True
    Null == (Cons val next) = False
    (Cons val next) == Null = False
    (Cons val1 next1) == (Cons val2 next2) =
        val1 == val2 && next1 == next2

-- to compare lists, compare items in the list sequentially
-- ex: aardvark < apple is TRUE because a < p
instance Ord a => (List a) where
    compare Null Null = EQ
    compare Null (Cons _ _) = GT
    compare (Cons _ _) Null = LT
    compare (Cons h1 t1) (Cons h2  t2) =
        case compare h1 h2 of
            EQ -> compare t1 t2
            x -> x

instance Show a => (List a) where
    show Null = "[]"
    show (Cons head tail) =
      let helper (Cons h Null) = show h ++ "]"
          helper (Cons h t) = show h ++ "," ++ helper t
          helper Null = "]"
        in "[" ++ helper (Cons head tail)

---

Stack Frames (Activation Records)

Let’s look at the following code:

void foo(){
	int y = 2;
	print("foo", y);
}
void bar() {
	int x = 1;
	foo();
	print("bar", x);
	foo();
}

Every time a function is called, a new Activation Record or Stack Frame is created for that function.

The stack frame contains:

• parameters
• local variables
  • memory is allocated for the local variables without values
• return address
  • where the program should return to after finishing completing the newly called function
• address of the previous stack frame

So in the code above, when bar calls foo, our program is initially in bar’s stack frame. It then creates a new stack frame for foo with the return address and address of the previous stack frame.

Call-by-reference vs Call-by-value

• Call-by-value
  • If a parameter is passed by-value, the parameter’s value is copied into a spot in the called function’s stack frame
• Call-by-reference
  • If a parameter is passed by-reference, the parameter’s address is put into a spot in the called function’s stack frame

Is python call-by-reference or call-by-value?

def foo(someint, somedict):
	someint += 1
	somedict["foo"] = "bar"

myint = 5
mydict = {}
foo(myint, mydict)
print(myint, mydict)

What does the above code print?

Answer:

5 {“foo”: “bar”}

def foo(someint, somedict):
	someint += 1
	somedict = {"foo": "bar"} # Line changed

myint = 5
mydict = {}
foo(myint, mydict)
print(myint, mydict)

What does the above code print when Line 3 is changed?

Answer:

5 {}

In Java

• Primitive types are call-by-value
• Compound types like classes are call-by-reference

HW 4 Intro

• Do an Eq instance for Tree
• Create a functor class
• Implement Insert, Lookup, and Remove for a BST
• Implement instance of Show for Tree
  • not just for BST (so don’t worry about repeated values)

#proglang-f19