Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Comp Science > PLC > Flashcards

PLC Flashcards

Learn PLC

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
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
Q

What are the two common types of parsers

A

+ Top-down, or recursive descent parsers
+ Bottom-up

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

What is a bottom-up parser

A

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

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

What is a LL Grammar

A

A LL grammar is a CFG which parces the input Left to Right and forms Leftmost derivations

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

What is a LR Grammar

A

A LR Grammar is a CFG which parses the input Left to Right and forms Rightmost derivations

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

When implementing a LR Parser with shift-reduce parsing, what does shifting do

A

Shift reads the next input token producing a new single node parse subtree

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

When implementing a LR Parser with shift-reduce parsing, what does shifting do

A

Reduce applies a completed grammar rule to join subtrees to make a larger subtree

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

When do ambiguity’s arise when parsing a grammar

A

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

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

What is precedence when parsing a grammar

A

Precedence is a method specifying the associativity of operators and removing ambiguity

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

What are the 4 approaches to typing and which are oposites

A

Strongly Typed & Weakly Typed
Static Typed & Dynamic Typed

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

What does it mean for a language to be Strongly Typed

A

The language checks the use of data to prevent program errors such as accessing private data, corrupting memory or crashing the machine

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

What does it mean for a language to be Weakly Typed

A

This means that the language does not always prevent errors but uses types for other compilation purposes such as memory layout

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

What does it mean for a language to use Static typing

A

If a language is statically typed the typed checking is performed at compile time

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

What does it mean for a language to use Dynamic typing

A

Dynamic typing means that type checking is delayed until run time

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

What does Γ represent when performing type derivation

A

Γ, 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

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

What is a free variable

A

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

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

What is the syntax to enlarge the type environment Γ, to include that a variable x is of type T

A

Γ,x: T ⊢

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

What does it mean for a set of inference rules “S” to be called syntax directed for an inductive relation “R”

A

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
Q

What is the property tested with the inversion lemma

A

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
Q

What does Implicit Type Annotation refer to

A

Implicit type annotation refers to when a language can infer the type of property’s and variables from their usage

44
Q

When making use of Implicit Type Annotation, what stage replaces type checking

A

Type Inference

45
Q

What does the process of unification refer to

A

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
Q

When performing type inference, what process is done before unification

A

Solving of constraints on the variables

47
Q

What is the purpose of structured types

A

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
Q

What is the purpose of a destructor

A

A destructor takes tuples as input and returns their projection, aka - an element from a specific position

49
Q

What are the destructors for the List Structure

A

Head and tail

50
Q

What are three varieties of polymorphism, and what is the one we need to know

A

+ Parametric Polymorphism - a very rich topic
+ Subtype Polymorphism - The type we need to know
+ Ad Hoc Polymorphism - Cleaver naming schemes

51
Q

What two forms of subtyping are there ( for allowing sub type polymorphism)

A

+ Structural Subtyping
+ Nominal Subtyping

52
Q

What does subsumption describe

A

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
Q

What relation is T <: U

A

It is the subtype relation

54
Q

How are types distinguished with nominal subtyping, what is a good thing about this

A

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
Q

What does it mean for a subtype to be reflective

A

That a type can subtype itself T <: T

56
Q

What does it mean for a subtype to be transitive

A

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
Q

What do structural subtype systems rely on to define the subtyping

A

Structural subtype systems rely solely on the structure of types to define the subtyping relation

58
Q

What does depth subtyping for records allow

A

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
Q

What does Width subtyping for records allow

A

Width subtyping of records allows for extra fields to exist in subtype records

60
Q

What does Permutation subtyping of records allow

A

Permutation subtyping allows fields in a subtype record to be reordered

61
Q

What does the Curry-Howard correspondence describe

A

The Curry-Howard correspondence states that there is an isomorphism between the space of natural deduction proofs and simply typed lambda terms

62
Q

Why do we need formal semantics for programs instead of just reasoning about the compiled code

A

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
Q

What are some of the advantages of formal semantics

A

+ 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
Q

What are the three common approaches to giving semantics for programs

A

+ 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
Q

What are the two main criticisms of denotational semantics

A

+ 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
Q

For big step semantics, what binary relation is considered,

A

The relation between program E and what it evaluates to

67
Q

What does E⇓V mean for Big Step semantics

A

Program E evaluates to value V

68
Q

What is a disavantage of big step semantics

A

It doesn’t account for the effects of non-terminating programs very easily

69
Q

What does “Type Safety = Preservation + Progress” mean

A

It means that by repeatedly applying progress, then preservation, we can guarantee that the program will never reach an error state

70
Q

What does “Signal and Wait” do, and what is the other name for it ( ______ communication)

A

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
Q

What is another name for the “Signal and Continue” synchronisation paradigm, and what is a brief summary

A

Asynchronous communication, where threads that are sending and threads which are receiving do not need to rendezvous on a signal

72
Q

What does CCS stand for

A

The Calculus of Communicating Systems

73
Q

What does nil refer to in CCS

A

Nil refers to a inert process (one which has terminated)

74
Q

What does a!P refer to (CCS)

A

a!P refers to sending a signal on a channel named a and then continuing execution as P

75
Q

What does a?P refer to (CCS)

A

Reciving a signal on channel a and then continuing execution as P

76
Q

What does τ in CCS refer to for a process P

A

It refers to the process P taking an internal computation step

77
Q

What does P||P represent in CCS

A

P||P represents two concurrent processes, and thread spawing

78
Q

What does P\a do in CCS

A

P\a is a restriction operation meaning that no communication on channel “a” originating inside of P can be seen

79
Q

What are X and rec X . P used for

A

X and rex X . P are used for recursive behaviour

80
Q

What does rec X . a! b? X describe

A

A process which repeatedly sends a signal on a and then receives a signal on b

81
Q

What does adding a!nil to the CCS grammar do

A

Adding this forbids the continuation of the process after a send signal

This converts the CCS grammar to be asynchronous

82
Q

Why can semantics become complex for concurrency

A

Because the order of executions cannot be accurately predicted and thus a tree of behaviours must be made

83
Q

What does LTS stand for and what components make it up

A

Labelled Transition System
+ X - the set of states
+ Σ is an alphabet of actions
+ L ⊆ X x Σ x X (The set of legal transitions)

84
Q

What three aspects of concurrency make reasoning about it different to reasoning about sequential computation

A

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
Q

What are the two kinds of non-determinism

A

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
Q

What are the two requirements for state y in a transition system to be able to simulate state x

A

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
Q

What condition must a binary relation R on states L satisfy for it to be called a simulation on L

A

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
Q

For simulation, what does ≤ denote

A

≤ denotes the largst simulation on an LTS. This is the union of all simulations on L

89
Q

What are the three steps for the simulation game, The game starts at position (x,y)

A

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
Q

When does the player loses the simulation game

A

If the player can’t make a move

91
Q

What is a Bisimulation

A

A bisimulation is a simulation which goes both ways - the relation and its reverse are both simulations

92
Q

What do we write if there is a bisimulation containing (x,y)

A

x ~ y

93
Q

What are the 4 steps for the bisimulation game starting from (x,y)

A

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
Q

What is the finest, reasonable, equivalence, and what other equivalences does it imply

A

Bisimulation is the finest, and it implies simulation equivalence which implies trace equivalence

95
Q

What are the cause’s of race conditions

A

Race conditions are caused when two or more threads are simultaneously trying to write or read and write from shared memory

96
Q

What must a process do before it enters the critical region with petersons algorithm

A

Mark itself as interested
Wait for other processes to not be interested, and the turn to be its
It can now enter

97
Q

What does CAS stand for

A

Compare and Set

98
Q

What can CAS primitives be used for

A

CAS primitives can be used for programming fine-grained concurrent algorithms

99
Q

What does fine graned concurrency refer to

A

Systems with more locking of small blocks of code

100
Q

What does Coarse-grained concurrency refer to

A

Systems with fewer locks over large blocks of code

101
Q
A

Comp Science (7 decks)

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