Garbage Collection 3

What is unreachable

Unreachable = safe to free

• mark and swap
• 2-space collector
• Generational Collector

In-degree is 0

• Reference counting
• safe to free
• unreachable

when dodes GC happen

• first three -> an allocation when out of memory
• for reference counting -> when references change/variables go out of scope

How does ref counting deal with cycle?

• Don’t tell programmers not to make cycles
• give the programmer more tools
• fall back to a different GC

Parametria Polymorphism/Generics

• many shapes of a type based on a parameter you specify
• E.G. ArrayList in Java Listof in TR

(define (id x)
    x)
(+ (id 5) (id 7))
(string-append (id "hello") (id "world"))

we can not have type system with this code because the type of id and x is entirely dependant on the input!

In racket this can work however by adding

(: id (All (T) (T->T)))

Subtyping

We say that A is a subtype of B, written A<:B, to mean that any term of type A can safely be used in a context where a term of type B is expected.

E.G. if I have a subtype of animal that is dog and I pass the dog into the function that takes an animal it should accept the dog.

Natural <: Integer <: Real (define (use-list [lst : (Listof Integer)]) …)

(define (use-vect [v : (Vector Integer)]) …)

Both of them integers are okay, reals are not.

Lists in TR are covariant

• if A <: B then (Listof A)<:(Listof B)
• EX: function that takes a list of exprC and passed lis of NumC’s

Vectors in TR are invariant

• A <: B you dont have (Listof A)<:(Listof B)
• EX: vector of numV can not have any Value
• ArrayList in Hava are invariant
• this problem only exists if its mutable

If we want A1->A2<:B1->B2 then B1<:A1 & A2<:B2

• Contravarient in input type
  • input type is bigger than the one we want
• Coveriant in there output type
  • output type is smaller or a subtype of what we want