PLC Flashcards
Learn PLC
In terms of variables, what is aliasing
Aliasing is the name given when two variables point to the same location in memory, it is something we aim to avoid
What are the 6 attributes of variables
+ Name
+ Address (L-Value)
+ Value (R-Value)
+ Type
+ Extent
+ Scope
What does the “Extent” of a variable refer to?
The extent of a variable is also known as the lifetime
It refers to the amount of time in the programs execution in which the variable will be assigned a meaningful value
What is a binding
Binding is the name given to associating attributes with variables. i.e.
+ Binding type
+ Binding address
+ Binding scope
What are the two types of binding and what is the difference
Static Binding - Where variables are bound during compile time and do not change during execution
Dynamic binding - Where variables are bound for the first time during execution OR when the binding can change during runtime
What is the name given to the process of binding a variable to its address
Allocation
What process does Deallocation refer to
Deallocation refers to the process of unbinding a variable from an address
This is largely dynamic as it cannot be done at compile time
What is the difference between static allocation and dynamic allocation
Static allocation refers to binding an address to a variable at compile time
Dynamic allocation refers to binding an address to a variable at runtime
What are the four kinds of variables
+ Static Variables
+ Stack Dynamic Variables
+ Explicit Heap Dynamic Variables
+ Implicit Head Dynamic Variables
What is a Static Variable
Static variables are bound to memory at initialisation time, and are also known as global variables.
In Java these are referred to by their class
What is a
Stack Dynamic Variable
Stack Dynamic Variables are allocated when some declaration is executed, they are then deallocated when that procedural block returns
What “kind” of variables are local variables
Stack Dynamic variables
What is an Explicit Heap Dynamic Variable
These are nameless, abstract memory locations. They are allocated and deallocated explicitly by the programmer with commands such as malloc or new
What is an Implicit Heap Dynamic Variable
This is a form of variable where memory is allocated from the heap when the variable is assigned to a value.
They are deallocated and reallocated when the need to be re-assigned
What is static type binding
Static type binding is the name given when a variable is assigned a type at compile time
What is Dynamic type binding
Dynamic type binding occurs when the variable is assigned a type at runtime
It is commonly used in scripting languages
What are the two types of static type binding
+ Type Declaration - this is the most common approach and is where the variable is given an explicit type when its introduced
+ Type Inference - this approach does not require explicit typing, instead, it works out the type from the usage of the variable or from following naming conventions
What is the extent of a Static variable
The whole program
What is the extent of Stack Dynamic Variables
A particular stack frame or procedure call
What is the extent of Explicit heap dynamic variables
Explicit allocation to explicit deallocation (malloc to free)
What is the extent of Implicit Heap Dynamic Variables
Implicit allocation to implicit deallocation, meaning variables may persist in memory even once the addresses have been freed
What does Lexical Scope refer to
Lexical Scope is refers to when the scope of variables is aligned to statically determined areas of the code file such as class definitions or the method body
What does Dynamic Scope refer to
Dynamic scope is determined at runtime by control flow, variables are only made to be meaningful within the context of the current call stack, aka when its been used before.
What is a recursive descent parser
Recursive decent parse build parse trees from the root down, this makes them good for LL Grammars, as it reads Left to Right and forms Leftmost derivations
What are the two common types of parsers
+ Top-down, or recursive descent parsers
+ Bottom-up
What is a bottom-up parser
Bottom-up parsers build the parse tree from the leaves up, this makes them good for LR parsers as they read the rightmost derivation.
This makes them more complicated but they can handle a wider range of grammars than LL grammars can
What is a LL Grammar
A LL grammar is a CFG which parces the input Left to Right and forms Leftmost derivations
What is a LR Grammar
A LR Grammar is a CFG which parses the input Left to Right and forms Rightmost derivations
When implementing a LR Parser with shift-reduce parsing, what does shifting do
Shift reads the next input token producing a new single node parse subtree
When implementing a LR Parser with shift-reduce parsing, what does shifting do
Reduce applies a completed grammar rule to join subtrees to make a larger subtree
When do ambiguity’s arise when parsing a grammar
Ambiguities arise when it is possible for the grammar to Shift AND it is possible for the grammar to reduce, this can be avoided by specifying precedence, or by layering non terminal operations
What is precedence when parsing a grammar
Precedence is a method specifying the associativity of operators and removing ambiguity
What are the 4 approaches to typing and which are oposites
Strongly Typed & Weakly Typed
Static Typed & Dynamic Typed
What does it mean for a language to be Strongly Typed
The language checks the use of data to prevent program errors such as accessing private data, corrupting memory or crashing the machine
What does it mean for a language to be Weakly Typed
This means that the language does not always prevent errors but uses types for other compilation purposes such as memory layout
What does it mean for a language to use Static typing
If a language is statically typed the typed checking is performed at compile time
What does it mean for a language to use Dynamic typing
Dynamic typing means that type checking is delayed until run time
What does Γ represent when performing type derivation
Γ, or gamma, represents the type of environment. A type environment is the set of assumptions we have made about the free variables in the expression E
What is a free variable
A free variable is a variable which is not locally declared or parsed as a parameter
For example, in let (x: Int) = 8 in x + y, y would be a free variable
What is the syntax to enlarge the type environment Γ, to include that a variable x is of type T
Γ,x: T ⊢
What does it mean for a set of inference rules “S” to be called syntax directed for an inductive relation “R”
A set of inference rules are called syntax directed if, when a program holds in R, there is a unique rule in “S” which justifies it.
This rule should be determinable by the syntactic operator at the root of the program when it is represented as an AST
What is the property tested with the inversion lemma
The inversion lemma states that we should be able to read the type rules from the bottom up, infering the types of subprograms from the type of the whole program
What does Implicit Type Annotation refer to
Implicit type annotation refers to when a language can infer the type of property’s and variables from their usage
When making use of Implicit Type Annotation, what stage replaces type checking
Type Inference
What does the process of unification refer to
Unification refers to the process of substituting type variables such that all constraints hold,
i.e. taking a -> b -> c and making it a -> b -> c
When performing type inference, what process is done before unification
Solving of constraints on the variables
What is the purpose of structured types
To catch programming errors which are results of data being parsed to a function call in a different format to what the function is expecting.
What is the purpose of a destructor
A destructor takes tuples as input and returns their projection, aka - an element from a specific position
What are the destructors for the List Structure
Head and tail
What are three varieties of polymorphism, and what is the one we need to know
+ Parametric Polymorphism - a very rich topic
+ Subtype Polymorphism - The type we need to know
+ Ad Hoc Polymorphism - Cleaver naming schemes
What two forms of subtyping are there ( for allowing sub type polymorphism)
+ Structural Subtyping
+ Nominal Subtyping
What does subsumption describe
Subsumption describes that, if T is a subtype of U then every value of type T can also be considered a value of type T
What relation is T <: U
It is the subtype relation
How are types distinguished with nominal subtyping, what is a good thing about this
By their names - even if they have the same structure
A good thing about this is that when types are conceptually different the distinction is enforced even when they have the same type
What does it mean for a subtype to be reflective
That a type can subtype itself T <: T
What does it mean for a subtype to be transitive
That if a type T is subtype of U, and type U is a subtype of V, type T must be a subtype of V
~~~
T <: U U <: V
———————- SubTrans
T <: V
~~~
What do structural subtype systems rely on to define the subtyping
Structural subtype systems rely solely on the structure of types to define the subtyping relation
What does depth subtyping for records allow
For a given record to be a depth subtype of another, for each value in the record it must be a subtype of the value of the same position in the supertype
What does Width subtyping for records allow
Width subtyping of records allows for extra fields to exist in subtype records
What does Permutation subtyping of records allow
Permutation subtyping allows fields in a subtype record to be reordered
What does the Curry-Howard correspondence describe
The Curry-Howard correspondence states that there is an isomorphism between the space of natural deduction proofs and simply typed lambda terms
Why do we need formal semantics for programs instead of just reasoning about the compiled code
Because compilers are not easy to use to reason about behaviour
They also may contain bugs, produce hard to understand low level code as well as optimisations
What are some of the advantages of formal semantics
+ They could take the form of logic or other mathematical language
+ They don’t need to worry about the efficiency of execution
+ They can act as reference implementations
+ They can be built in compositional ways which reflect high level structure
What are the three common approaches to giving semantics for programs
+ Denotational Semantics - this approach advocates mapping every program to some point in its domain
+ Operational Semantics - these use relational approaches to specify the behaviour of programs
+ Axiomatic Semantics - These take the approach that the meaning of a program is just what properties you can prove of it using a formal logic
What are the two main criticisms of denotational semantics
+ They don’t give clear account of how the program should execute, instead they give precise account of what values should be calculated
+ There is allot of junk in the model which makes it too big
For big step semantics, what binary relation is considered,
The relation between program E and what it evaluates to
What does E⇓V mean for Big Step semantics
Program E evaluates to value V
What is a disavantage of big step semantics
It doesn’t account for the effects of non-terminating programs very easily
What does “Type Safety = Preservation + Progress” mean
It means that by repeatedly applying progress, then preservation, we can guarantee that the program will never reach an error state
What does “Signal and Wait” do, and what is the other name for it ( ______ communication)
Signal and wait is the name given to the paradigm of synchronisation where one thread sends a signal to another thread and cannot be scheduled to do anything further until the signal is received
This is also called synchronous communication
What is another name for the “Signal and Continue” synchronisation paradigm, and what is a brief summary
Asynchronous communication, where threads that are sending and threads which are receiving do not need to rendezvous on a signal
What does CCS stand for
The Calculus of Communicating Systems
What does nil refer to in CCS
Nil refers to a inert process (one which has terminated)
What does a!P refer to (CCS)
a!P refers to sending a signal on a channel named a and then continuing execution as P
What does a?P refer to (CCS)
Reciving a signal on channel a and then continuing execution as P
What does τ in CCS refer to for a process P
It refers to the process P taking an internal computation step
What does P||P represent in CCS
P||P represents two concurrent processes, and thread spawing
What does P\a do in CCS
P\a is a restriction operation meaning that no communication on channel “a” originating inside of P can be seen
What are X and rec X . P used for
X and rex X . P are used for recursive behaviour
What does rec X . a! b? X describe
A process which repeatedly sends a signal on a and then receives a signal on b
What does adding a!nil to the CCS grammar do
Adding this forbids the continuation of the process after a send signal
This converts the CCS grammar to be asynchronous
Why can semantics become complex for concurrency
Because the order of executions cannot be accurately predicted and thus a tree of behaviours must be made
What does LTS stand for and what components make it up
Labelled Transition System
+ X - the set of states
+ Σ is an alphabet of actions
+ L ⊆ X x Σ x X (The set of legal transitions)
What three aspects of concurrency make reasoning about it different to reasoning about sequential computation
Communication - Processes communicate with each other
Synchronisation - Processes must sometimes synchronise their actions to ensure atomicity
Nondeterminism - What can be observed about a program changes from one run to the next
What are the two kinds of non-determinism
Internal, where the machine chooses, and it is resolved by the scheduler
External, where the environment chooses, this is suitable for interactive systems such as vending machines
What are the two requirements for state y in a transition system to be able to simulate state x
Whenever x can do some action, becoming x’ in the process, y can reply with the same action, becoming y’ in the process
This y’ must be able to do everything x’ can do
What condition must a binary relation R on states L satisfy for it to be called a simulation on L
Whenever x R y and x ->^a x' for some state x' then there exists a state y' such that y ->^a y' and (x',y')\in R
For simulation, what does ≤ denote
≤ denotes the largst simulation on an LTS. This is the union of all simulations on L
What are the three steps for the simulation game, The game starts at position (x,y)
1) The demon picks a move starting from x, they choose x ->^a x’ say
2) You must start from y and choose a matching move to y’ say, so that y ->^a y’
3) The game goes back to Step 1, changing the position to (x’, y’)
When does the player loses the simulation game
If the player can’t make a move
What is a Bisimulation
A bisimulation is a simulation which goes both ways - the relation and its reverse are both simulations
What do we write if there is a bisimulation containing (x,y)
x ~ y
What are the 4 steps for the bisimulation game starting from (x,y)
1) The demon pick weather to play from x or from y
2) The demon picks to move from their chosen start state
3) You the player must start from the other start state and make a matching move
4) The game goes back to Step 1, changing the position to (x’,y’) where (x’, y’) are the states reached by both
What is the finest, reasonable, equivalence, and what other equivalences does it imply
Bisimulation is the finest, and it implies simulation equivalence which implies trace equivalence
What are the cause’s of race conditions
Race conditions are caused when two or more threads are simultaneously trying to write or read and write from shared memory
What must a process do before it enters the critical region with petersons algorithm
Mark itself as interested
Wait for other processes to not be interested, and the turn to be its
It can now enter
What does CAS stand for
Compare and Set
What can CAS primitives be used for
CAS primitives can be used for programming fine-grained concurrent algorithms
What does fine graned concurrency refer to
Systems with more locking of small blocks of code
What does Coarse-grained concurrency refer to
Systems with fewer locks over large blocks of code
