Lecture 7-8: Mutation and State

목차

Learning Objectives

- Explain how pointers work and how memory can be interpreted in different ways

- Explain the differences between pass-by-reference and pass-by-value

- Explain the differences between pure and impure languages

- Understand the concept of stores and as an model for memory

- Explain different methods to solve the problem of garbage

- Implement a definitional interpreter with support for mutation using stores

 

 

Fixed-Point Combinators

Fixed-point combinators allow for recursive definitions (when there is no direct support for recursion)

Fixed-point combinators apply tricks similar to "self"

 

A fixed-point combinator  is a higher-order function (i.e. a function which takes a function as argument) that returns some fixed point (a value that is mapped to itself) of its argument function.

 

 

Z Combinator

 

This is a function that calculates the factorial of a number.

If you apply it to a function, then it wil ltake the function, put it infront and give us the first argument again and z combinator applied to the function.

Keep putting function at the front and give it as a input the z combinator again

The purpose of the Z combinator is to take a function f and return its fixed point, that is, a value x such that f(x)=x.

 

 

 

We first put P into the Z combinator and then we call recursive function with the value of 3.

 

 

(Z P)를 f에 대입. 그리고 x에 3을 대입.

 

 

 

Z combinator is a lazy Y combinator by delaying evaluation through wrapping things in functions.

 

 

State Encapsulation

Functions Encapsulate State

 

When not using objects for counter, these methods can only increment, and not reset.

Multiple functions with function "objects":

- List of functions

- A function with an argument that determines the function

 

Javascript에서는 list of function을 반환시키는 방식으로 구현할 수 있다.

 

 

 

 

Variables

Variables in Paret

(set  n  e)

Lookup n in the environment

Then evaluate e to a value v

Set the value of n to v

Return v

 

 

==> NumV(2)

 

 

Sequential Composition 

(seq  e1  e2)

First evaluate e1 to a value, then evaluate e2 to a value

Return the result of evaluating e2

Seq is sequential composition: do one thing and do another thing

 

Difference between let and set => you cannot change the variable that has not been defined

let = definition, set = modifying existing variable

 

 

How to define this:

 

How to use counters:

→ ((head c)) : 괄호 두개인 이유: call (head c). 마찬가지로 ( (head   (tail  c) ) )인 이유도: call (head  (tail  c))

 

종합하면:

 

 

Variables

0 is returned, not 1 because of pass by value.

Pass by value: we are passing a copy of the value, so we create a new variable n with the same value as i, so i remains unchanged.

→ Pass by reference

 

 

Memory

C

C is pass-by-value

When you pass something to a function, a copy is made

 

Java

Java is pass-by-reference (except for primitives)

Behind the scenes, java is passing pointers

 

 

Boxes

Boxes: memory locations as first-class values

Boxes represent the concept of a pointer into mutable memory found in many programming languages

Boxes allow for pass-by-reference behavior

Boxes behave as objects (with getters and setters in Java)

 

(box  0)

Allocate a box (memory location), store 0 in that location and return a pointer to the location

 

(setbox  e  1)  → setter

Evaluate e to a box (memory location pointer), store 1 in the location pointed to and return the value of 1

 

(unbox  e)  → getter

Evaluate e to a box (memory location pointer), look up the value stored at that location and return the value

 

 

Implementing Counter

기존:

 

Box 사용한 방식:

 

 

 

 

 

Recursion with Boxes

Recursion is the act of self-reference.

 

Cyclic datum: store cell that refers to itself

 

→ Construct a box b with value 0.

→ Set b to be itself and call getter on it as much as we want because it's going to return itself

 

Cyclic function: 

 

Use the self-referential function trick to define letrec, i.e. recursive let bindings

 

 

 

letrec

Letrec bindings can refer to themselves → proper recursion support

Letrec bindings can refer to each other, like methods in Java

Letrec allows for forward referencing

 

Let → crashes (x does not resolve)

Letrec → 1

 

 

 

Letrec General Implementation Plan

Implement as syntactic sugar

Add all names to environment with some dummy value

→ Closures need to use this environment

Then update values to their real values

 

 

 

Mutable Environments

If we replace binding with a new binding in an environment, no mutation effect

 

 

Updating the Environment

Problems:

- Easy to make mistakes with mutable case classes

- var 사용하는거는 our definitional interpreter relies on the working objects in Scala

- Hard to derive the correct meaning for our language from that

 

→ Use Stores

 

 

Stores

Rather than putting values directly in the environment, we put memory locations

Environment with pointers to cells in the store

 

 

Semantics

 

Set: 

We need to interpret e to get a new store, and look up the location in the environment and we need to update our store with our location being the new value.

 

 

 

 

Letrec using Mutable Environments

Letrec Implementation

Add all names to environment with some dummy value

- Closures need to use this environment

Then update values to their real values

 

여기서 Undefined = dummy value

 

 

Side Effects

We have to care about order because we may get different results due to stores?

 

Pure Language

Impure Language

 

 

Memory Management

Garbage includes data (...) which will not be used in any future computation by the system, or by a program running on it.

 

 

C: Do it Yourself (Programmer deals with memory)

 

Forget to clean up? → Memory leak

Cleaned up too soon? → Crash / Garbage values

Cleaned up twice? → Random bugs elsewhere in your code

 

 

Java: Garbage Collection

Clean it up automatically

Different strategies/approaches

 

Detection Strategies for Unreferenced Memory

Reference Counting

Each memory cell is associated with a counter indicating who is referecing that cell.

When counter is 0, the cell can be garbage-collected.

 

Pro: Simple

Con: Expensive: reference counters take up memory, memory updates need to update reference counts

 

 

Mark-and-Sweep

Once in a while, the entire store is traversed, starting from an initial set of "live" pointers.

Traversal only follows live pointers, and marks each pointer being traversed.

At the end, unmarked memory is garbage collected.

 

Pro: Relatively simple, no memory overhead, no memory update pentaly

Con: Expensive to traverse entire store

 

 

Rust: Ownership

Everything has an owner

Ownership can be moved

Things can be borrowed

Owner out of scope → Everything cleaned up

 

Rust: Moving

 

Example 1:

You create a boxed integer a using Box::new(5). This allocates memory and a becomes the owner of that memory. When you subsequently assign a to b (let b = a;), Rust performs a move operation. A move in Rust transfers ownership from one variable to another. After the move, b becomes the new owner of the boxed integer, and a is no longer valid for use. When you try to access a after the move, Rust detects that a no longer owns the box and prevents you from using it.

 

Example 2:

You create a boxed integer a with the value 5. You call the function foo and pass a as an argument. This passes ownership of the box from main to foo. Inside foo, the box a becomes the owner of the boxed integer. When foo returns, the box a goes out of scope and gets destroyed. This is because foo owns the box within its scope, and ownership transfers back to main once foo finishes executing. After foo returns, you try to access a again in main, but it's no longer valid because it doesn't own the box anymore. 

 

 

Rust: Borrowing

 

You create a boxed integer a containing the value 5. Then you pass a reference to a (&a) to the function foo. The foo function takes a reference to an i32 (&i32) as its argument. This means it's borrowing the value rather than taking ownership of it. When you call foo(&a), you're passing a reference to the boxed integer a. This allows foo to access the value stored in the box without taking ownership of it. Inside foo, you have access to the value of a via the reference a. However, since foo only borrows a, it cannot modify or deallocate a. This ensures that a remains valid and unchanged after the function call. After the call to foo, you try to use a again in main. Since foo only borrowed a and didn't take ownership of it, a is still valid and accessible in main. 

 

Rust: Ownership

- Always a single owner

- Borrowing allows others

- Borrow of deleted value is compile error

Compiler guarantees absence of memory leaks