Section 1
Preview this deck
variable lifetime: static
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 14, 2020
Cards (83)
Section 1
(50 cards)
variable lifetime: static
bound before execution and never changes (global variables)
free union
no language support for type checking
major influences on language design
machine architecture and software development methodologies
locks-and-keys
pointer values are represented as key, address pairs, heap-dynamic variables are variable plus a cell for integer lock value, when allocated the lock value is in the lock cell and key cell, each dereference must compare the key and the lock
variable lifetime: stack dynamic
bound when elaborated (local variables)
primitive data types
not defined in terms of other data types
discriminated union
each union includes a type indicator called the discriminant to aid in type checking
coercion
automatic compiler-generated conversion of one type to another
cons vs. list vs. append
cons takes the first parameter and makes it the head of the second parameter (that should be a list) [note cons makes a dot pair if the second parameter is not a list], list takes any number of parameters and returns a list of those elements, append, takes the second parameter (either list or atom) and appends to the end of the first parameter (which must be a list)
function side effects
when a function changes a parameter or global variable
types of static type binding
explicit (stated in source code) and implicit (implied/ inferred by compiler)
major methods of implementing programming languages
compilation, pure interpretation, hybrid implementation
enumeration types
user-defined ordinal types with named constants
compare the 4 categories of arrays
static (subscript ranges & storage allocation are both static), fixed stack-dynamic (subscript ranges are statically bound but allocation is at elaboration time), fixed heap-dynamic (subscript binding is fixed after allocation but storage is dynamic), heap-dynamic (subscript ranges and storage allocation are both dynamic)
referential transparency
any two expressions in the program with the same value can be substituted for one another anywhere in the program without affecting the action of the program
union types
variables are allowed to store different type values at different times during execution
name type equivalence
two variables have equivalent types if they are in the same declaration or in declarations that use the same type name
tombstone
there is an extra heap cell as a pointer to the heap-dynamic variable, pointers only point to tombstones, when heap-dynamic variable is deallocated, the tombstone is set to null
let vs. let* vs. letrec
let uses the value immediately previous to the let environment, let uses the most recent value, even if within the current let environment, letrec is like let* but allows later bindings to be referenced by earlier bindings
stream set-up (generic)
(define (stream-name parameters) (letrec ([f (parameters if any) do-stuff-here (cons next-element (lambda ( ) (f parameters)))]) (lambda ( ) (f starting-parameters)))
reference counter
eager approach, reclamation is gradual/ continual, maintain a counter in every cell which stores the number of pointers currently pointing at the cell, reclaim cells when their count drops to zero, requires space, time, and is complicated with circularly connected cells
generational copiers
exploits the fact that some objects have long lives what others have long lives; keeps track of lifetimes and collects long lifetime objects less frequently
array slice
some subsection of an array
the prolog interpreter process
start at the beginning of the database; left-to-right and depth-first search using stack and backtracking
elliptical reference
allows leaving out record names as long as the reference is unambiguous
compare the 3 string length types
static (determined at compile time), limited dynamic (buffer), dynamic (unbounded)
fully-qualified reference
must include all record names
dangling pointer
pointer points to a heap-dynamic variable that has been deallocated
associative arrays
unordered collection of elements indexed by keys
stream
infinite sequence of values generated as needed via thunks
heterogeneous array
elements might not be of the same type
most important criteria for evaluating programming languages
readability, writability, reliability, cost
memory leak
allocated heap-dynamic variable is no longer accessible to the user program
ordinal types
range of possible values can be easily associated with the set of positive integers
rectangular array
rows have same number of elements, columns have same number of elements, number of rows != number of columns
stop-and-copy
lazy approach, splits heap memory in half, all new allocations go into the active half, at collection time recursively follow all live pointers and copy all discovered structures to other half which becomes the active half, the inactive half now only contains garbage that is reclaimed en masse
variable lifetime: implicit heap dynamic
dynamic allocation and deallocation implicitly via assignment statements (happens during execution)
thunk
parameter-less function wrapped around a first-order function to delay its evaluation
jagged array
rows have varying number of elements
variable lifetime: explicit heap dynamic
allocated and deallocated explicitly by the programmer (happens during execution)
4 categories of variable lifetimes
static, stack dynamic, explicit heap dynamic, implicit heap dynamic
mark-and-sweep
lazy approach, recursively follow all live pointers, marking all discovered structures as useful, then sweep over the entire heap and reclaim any structures not marked as useful and turn off marks in preparation for next time
strong typing
type errors always detected whether at compile time or run time
row major order vs. column major order
determines if stored as array of rows or as array of columns
r-value vs. l-value
l-value is the memory address, r-value is the value stored at that memory address
returning values other than true/ false in prolog
add another parameter to carry back the result
structure type equivalence
two variables have equivalent types if their types have identical structures
static scope vs. dynamic scope
in static scoping, the subprogram can view variables at the same level or above, but not variables within other subprograms; in dynamic scoping, can view all variables in above calling sequence
variable scope in Prolog
the clause in which it appears; on the LHS implied for-all; on the RHS implied there-exists
what is returned by ( cdar '( (A B) C D ) )
(B)
Section 2
(33 cards)