Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Comp Science > PLC > Flashcards

PLC Flashcards

Learn PLC

1
Q

In terms of variables, what is aliasing

A

Aliasing is the name given when two variables point to the same location in memory, it is something we aim to avoid

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 6 attributes of variables

A

+ Name
+ Address (L-Value)
+ Value (R-Value)
+ Type
+ Extent
+ Scope

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does the “Extent” of a variable refer to?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a binding

A

Binding is the name given to associating attributes with variables. i.e.
+ Binding type
+ Binding address
+ Binding scope

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the two types of binding and what is the difference

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the name given to the process of binding a variable to its address

A

Allocation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What process does Deallocation refer to

A

Deallocation refers to the process of unbinding a variable from an address

This is largely dynamic as it cannot be done at compile time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the difference between static allocation and dynamic allocation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the four kinds of variables

A

+ Static Variables
+ Stack Dynamic Variables
+ Explicit Heap Dynamic Variables
+ Implicit Head Dynamic Variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a Static Variable

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a
Stack Dynamic Variable

A

Stack Dynamic Variables are allocated when some declaration is executed, they are then deallocated when that procedural block returns

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What “kind” of variables are local variables

A

Stack Dynamic variables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is an Explicit Heap Dynamic Variable

A

These are nameless, abstract memory locations. They are allocated and deallocated explicitly by the programmer with commands such as malloc or new

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is an Implicit Heap Dynamic Variable

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is static type binding

A

Static type binding is the name given when a variable is assigned a type at compile time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is Dynamic type binding

A

Dynamic type binding occurs when the variable is assigned a type at runtime

It is commonly used in scripting languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are the two types of static type binding

A

+ 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the extent of a Static variable

A

The whole program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the extent of Stack Dynamic Variables

A

A particular stack frame or procedure call

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the extent of Explicit heap dynamic variables

A

Explicit allocation to explicit deallocation (malloc to free)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the extent of Implicit Heap Dynamic Variables

A

Implicit allocation to implicit deallocation, meaning variables may persist in memory even once the addresses have been freed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What does Lexical Scope refer to

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What does Dynamic Scope refer to

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is a recursive descent parser

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What are the two common types of parsers
+ Top-down, or recursive descent parsers + Bottom-up
26
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
27
What is a LL Grammar
A LL grammar is a CFG which parces the input Left to Right and forms Leftmost derivations
28
What is a LR Grammar
A LR Grammar is a CFG which parses the input Left to Right and forms Rightmost derivations
29
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
30
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
31
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
32
What is precedence when parsing a grammar
Precedence is a method specifying the associativity of operators and removing ambiguity
33
What are the 4 approaches to typing and which are oposites
Strongly Typed & Weakly Typed Static Typed & Dynamic Typed
34
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
35
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
36
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
37
What does it mean for a language to use Dynamic typing
Dynamic typing means that type checking is delayed until run time
38
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
39
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
40
What is the syntax to enlarge the type environment Γ, to include that a variable x is of type T
Γ,x: T ⊢
41
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
42
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
43
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
44
When making use of Implicit Type Annotation, what stage replaces type checking
Type Inference
45
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
46
When performing type inference, what process is done before unification
Solving of constraints on the variables
47
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.
48
What is the purpose of a destructor
A destructor takes tuples as input and returns their projection, aka - an element from a specific position
49
What are the destructors for the List Structure
Head and tail
50
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
51
What two forms of subtyping are there ( for allowing sub type polymorphism)
+ Structural Subtyping + Nominal Subtyping
52
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
53
What relation is T <: U
It is the subtype relation
54
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
55
What does it mean for a subtype to be reflective
That a type can subtype itself `T <: T`
56
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 ```
57
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
58
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
59
What does Width subtyping for records allow
Width subtyping of records allows for extra fields to exist in subtype records
60
What does Permutation subtyping of records allow
Permutation subtyping allows fields in a subtype record to be reordered
61
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
62
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
63
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
64
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
65
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
66
For big step semantics, what binary relation is considered,
The relation between program E and what it evaluates to
67
What does E⇓V mean for Big Step semantics
Program E evaluates to value V
68
What is a disavantage of big step semantics
It doesn't account for the effects of non-terminating programs very easily
69
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
70
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
71
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
72
What does CCS stand for
The Calculus of Communicating Systems
73
What does nil refer to in CCS
Nil refers to a inert process (one which has terminated)
74
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
75
What does a?P refer to (CCS)
Reciving a signal on channel a and then continuing execution as P
76
What does τ in CCS refer to for a process P
It refers to the process P taking an internal computation step
77
What does P||P represent in CCS
P||P represents two concurrent processes, and thread spawing
78
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
79
What are X and rec X . P used for
X and rex X . P are used for recursive behaviour
80
What does `rec X . a! b? X` describe
A process which repeatedly sends a signal on `a` and then receives a signal on `b`
81
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
82
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
83
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)
84
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
85
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
86
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
87
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`
88
For simulation, what does ≤ denote
≤ denotes the largst simulation on an LTS. This is the union of all simulations on L
89
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')
90
When does the player loses the simulation game
If the player can't make a move
91
What is a Bisimulation
A bisimulation is a simulation which goes both ways - the relation and its reverse are both simulations
92
What do we write if there is a bisimulation containing (x,y)
x ~ y
93
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
94
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
95
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
96
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
97
What does CAS stand for
Compare and Set
98
What can CAS primitives be used for
CAS primitives can be used for programming fine-grained concurrent algorithms
99
What does fine graned concurrency refer to
Systems with more locking of small blocks of code
100
What does Coarse-grained concurrency refer to
Systems with fewer locks over large blocks of code
101

Comp Science (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions