Understanding State, Mutability, and Heaps in Programming

Slide Note
Embed
Share

Explore the concepts of (im)mutability, imperative vs. functional programming, referential transparency, and challenges for strict immutability in programming. Learn about the differences between imperative and functional languages, the benefits of referential transparency, and the challenges of maintaining strict immutability in modern systems. Dive into examples and illustrations to enhance your understanding of these important programming principles.


Uploaded on Nov 25, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. State (Im)Mutability and Heaps

  2. Imperative vs Functional programming So far we ve had two core languages, Calc and FL. Calc is Imperative and FL is Functional. What s the difference?

  3. Imperative vs Functional programming So far we ve had two core languages, Calc and FL. Calc is Imperative and FL is Functional. What s the difference? Mutability

  4. Example // typescript let y = 1 function f (x) { let z = x * y y = 5 return z }

  5. Example // typescript let y = 1 function f (x) { let z = x * y y = 5 return z } // F# let y = 1 let f (x) = let z = x * y y <- 5 z

  6. Referential Transparency Functions are functions. Same arguments equals same outputs. let x = function f (x) { return x * 2 } Great for reasoning! let z = f(x) let a = f(x)

  7. Referential Transparency (Optimization) Can replace redundant computations with single computation let x = let x = function f (x) { return x * 2 } function f (x) { return x * 2 } = let z = f(x) let a = f(x) let z = f(x) let a = z

  8. Referential Transparency (Concurrency/Parallelization) Can reorder computation arbitrarily (up to data dependencies) function f (x) { } function g (x) { } function f (x) { } function g (x) { } = let x = let x = let z = f(x) let a = g(x) let a = g(x) let z = f(x)

  9. Challenges for Strict Immutability Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally.

  10. Counter Example

  11. Challenges for Strict Immutability Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what?

  12. Challenges for Strict Immutability Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what? Threading! Copying is a performance hit.

  13. Challenges for Strict Immutability Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what? Threading! Copying is a performance hit. The outside world: modern programs interact with the world , such as filesystems, databases, distributed systems other computers, or even physical actuation in robotics. We can t copy the universe!

  14. Example (Revisited) // typescript let y = 1 function f (x) { let z = x * y y = 5 return z } // F# let y = 1 let f (x) = let z = x * y y = 5 z

  15. In practice Modern functional programming language incorporate mutability. // typescript let y = 1 function f (x) { let z = x * y y = 5 return z } // F# let y = 1 let f (x) = let z = x * y y = 5 z // F# let mutable y = 1 let f (x) = let z = x * y y <- 5 z

  16. In practice Many modern languages enable both imperative and functional programming within the same language. // typescript let y = 1 function f (x) { let z = x * y y = 5 return z } // F# let y = 1 let f (x) = let z = x * y y = 5 z // typescript const y = 1 function f (x) { let z = x * y y = 5 return z } // F# let mutable y = 1 let f (x) = let z = x * y y <- 5 z

  17. In practice. Functional programming is a growing trend https://google.github.io/styleguide/cppguide.html#Use_of_const

  18. Example Many modern languages enable both imperative and functional programming within the same language. (e.g., Typescript, Python F#, C#, C++, Rust) But each typically has a default, i.e., can you modify the variable of an unadorned variable declaration? If yes, default imperative (read, mutable). If no, default functional (read, immutable). Though, subtleties abound. Mutable by default (Typescript, Python, C#, C++) Selective Immutability: `const`, `freeze`, `frozenset` Immutable by Default (lambda calculus, OCaml, F#, Rust, Haskell) Selective Mutability: `ref` (OCaml , `mutable` (OCaml), `mut` (Rust),

  19. Mutability Today add state to FL, giving us something more powerful than Calc (because we ll also have first-class functions) Take a look at Calc. Take a look at FL with call by value and let. Add mutable state to FL (Attempt #1 and fail) Add mutable state to FL

  20. Calc (Simplified)

  21. Calc Example

  22. FL with Closures

  23. Warmup Example of FL

  24. Back to our sequential example

  25. Next line!

  26. First-Order Functions Why are these extra environments hanging around? Closures

  27. First-Order Functions (Example)

  28. First-Order Functions (Example)

  29. First-Order Functions (Example)

  30. First-Order Functions (Example) Closures close over the unbound variables of a function and provide their values.

  31. Mutable State + First-Class Functions Calc and FL with closures in some way, look similar. But letdoesn t do the trick. f only receives a copy of the value of y. And let y = 5 only changes/shadows the local copy. // Typescript let y = 1 function f (x) { let z = x * y y = 5 return z } let v1 = f(2) let v2 = f(2) // FL let y = 1 in let f (x) = let z = x * y in let y = 5 z in let v1 = f(2) in let v2 = f(2) in v1 =2, v2 = 10 v1 =2, v2 = 2

  32. The Problem // typescript function Counter() { let curr = 0 function f () { let old = curr curr += 1 return old } return f } When calling c, Counter has already returned. Where is curr stored? In some sense currdoesn t really exist any more, without consideration of f, it only lasts for the call to Counter. let c = Counter() console.log(c()) console.log(c()) console.log(c()) But then how does this code work?

  33. Answer: References If closures, are going to be copied, then we need a way to have two copies point to the data and for that thing to last for all calls: references! // F# let y = ref 1 let f (x) = let z = x * !y y := 5 z // F# let mutable y = 1 let f (x) = let z = x * y y <- 5 z A reference is pointer to a value allocated in the heap. When we copy to create our closure, we copy the pointer, and not just the value itself. And we ll have data in the heap last forever.

  34. References and Heaps A heap is a program structure organized over machine memory that enables one to store data at a location. Heap Environment let x = ref 1 let y = ref 10 let z = ref 42 {x : 100, y: 256, z : 128} 128 100 256 1 42 10 {100 : 1, 128: 42, 256 : 10} Heap lasts for the duration of the program execution. For now, assume data is allocated and never freed, so we can assume that there is an infinite number of locations to store data.

  35. Answer: References ref <exp> - stores the value of an expression into the heap, returns a location. !y reference reads the value at the reference stored by y y := 5.Stores the result of an expression into the reference stored by y // F# let y = ref 1 let f (x) = let z = x * !y y := 5 z // F# let mutable y = 1 let f (x) = let z = x * y y <- 5 z

  36. References Semantics

  37. FL++: References // FL++ let y = ref 1 in let f = fun x -> let z = x * !y in x := 5 ; z in let v1 = f(2) in let v2 = f(2) in v1 = 2 and v2 = 10

  38. A last detail: Call-by-Value vs Call-by-Name We made a very subtle change at the outset of using using call-by-value instead of call-by-name. Why? let x = ref 0 in x := !x + 1 ; !x

  39. A last detail: Call-by-Value vs Call-by-Name We made a very subtle change at the outset of using using call-by-value instead of call-by-name. Why? With call-by-value, we evaluate x first before executing the rest of the program. With call-by-name, we substitute the definition of x into it s uses and evaluate there. let x = ref 0 in x := !x + 1 ; !x (ref 0) <- !(ref 0) + 1 ; !(ref 0) Call-by-value: 1, Call-by name: 0 Substitution (also lazy evaluation) doesn t play well with mutability or, generally, effects.

  40. FL++: References // FL++ let x = ref 1 in let f = fun y -> let z = !x * y in x := 5 ; z in let v1 = f(2) in let v2 = f(2) in v1 = 2 and v2 = 10

  41. Conclusion Many modern languages enable both imperative and functional programming within the same language. (e.g., Typescript, Python F#, C#, C++, Rust) But each typically has a default, i.e., can you modify the variable of an unadorned variable declaration? If yes, default imperative (read, mutable). If no, default functional (read, immutable). Though, subtleties abound. Mutable by default (Typescript, Python, C#, C++) Selective Immutability: `const`, `freeze`, `frozenset` Immutable by Default (lambda calculus, OCaml, F#, Rust, Haskell) Selective Mutability: `ref` (OCaml , `mutable` (OCaml), `mut` (Rust),

  42. Why the blend? Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what? Threading! Copying is a performance hit. The outside world: modern programs interact with the world , such as filesystems, databases, distributed systems other computers, or even physical actuation in robotics. We can t copy the universe!

  43. Why the blend? Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what? Threading! Copying is a performance hit. The outside world: modern programs interact with the world , such as filesystems, databases, distributed systems other computers, or even physical actuation in robotics. We can t copy the universe! or References!

  44. Why the blend? Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what? Threading! Copying is a performance hit. The outside world: modern programs interact with the world , such as filesystems, databases, distributed systems other computers, or even physical actuation in robotics. We can t copy the universe! or References! References!

  45. Data Structures A mutable list // F# type MyList = {value : int; ref : MyList}; Not entirely complete though. How do I specify the end of a list? Or an empty list? ref only lets us create real data. Need something like None in Python, to communicate an empty reference, or some better way to specify a distinguished end. We ll revisit in Data Abstraction.

  46. Why the blend? Mutability is unavoidable in modern systems Coding: many programming patterns to organize program data that is a bit cumbersome to code functionally. Threading! Data Structures: if we d like to update a record or list, then what? Threading! Copying is a performance hit. The outside world: modern programs interact with the world , such as filesystems, databases, distributed systems other computers, or even physical actuation in robotics. We can t copy the universe! or References! or References! In the next lectures we ll talk about the outside world (notice how we dropped print , it s mutable state)

More Related Content