2.0 Declarative computation model Flashcards
1
Q
What is a computation model?
A
formal system that defines a language and how expressions and statements of the language are executed by an abstract machine.
2
Q
What is a programming model?
A
Programming techniques and principles used to write programs in the language of the computation model.
3
Q
What is declarative programming?
A
Stateless programming
Evaluating functions over partial data structures.
Programming with functions, complete values, deterministic logic.
Can be made concurrent.
4
Q
What is imperative programming?
A
Stateful programming
5
Q
What is language syntax?
A
What are legal programs, programs that can be executed.
6
Q
What is language grammars?
A
Rules on how to make statements (‘sentences’) out of tokens (‘words’).
7
Q
What is a statement?
A
Sequence of tokens
8
Q
What is a token?
A
Sequence of characters
9
Q
What is a tokenizer?
A
A lexical analyser.
Program that takes a sequence of characters and returns a sequence of tokens.
10
Q
What is a parser?
A
A program that takes a sequence of tokens and returns a parse tree.
11
Q
What is a parse tree?
A
Shows the structure of statements.
12
Q
What is the Extended Backus-Naur form (EBNF)?
A
Notation for defining grammar.
Uses terminal- and non-terminal symbols.
13
Q
What is a terminal symbol?
A
Tokens
14
Q
What is a non-terminal symbol?
A
Sequence of tokens.
Defined by a grammar rule, that show how to expand it into tokens.
15
Q
Give an example of representing the nonterminal <digit> in EBNF</digit>
A
<digit> ::= 1|2|3|4|5|6|7|8|9|0
The nonterminal <digit> can be any of the ten tokens.
|: means or
</digit></digit>
16
Q
How can an integer be represented using EBNF?
A
<int> ::= <digit> {<digit>}
An integer is a digit followed by any number of digits.
<digit>: Nonterminal
{...}: Means repeat whatever is inside, any number of times, including none.
</digit></digit></digit></int>
17
Q
What is a formal language?
A
Set of all possible statements generated by a grammar.
18
Q
What are context free grammars?
A
The expansion of a nonterminal is always the same no matter where it is used.
Nonterminals can only use already-declared variables.
For example, context free grammars does not allow using variables that is declared before they are used - this is a context dependency.
Can be ambiguous: There can be several parse trees corresponding to a given token sequence. This can cause different results depending on how an expression is evaluated.
Example: 23+4 can give trees representing (23) + 4, and 2 * (3+4)
19
Q
What is context-sensitive grammar?
A
Grammar containing nonterminals whose use depends on the context where it is used.
20
Q
How are the grammars of most practival programming languages defined?
A
Two parts, as a context free grammar, supplemented with a set of extra conditions composed by the language.
21
Q
What does it mean to disambiguate a grammar?
A
Add extra conditions to grammars, that restrict the parser so that only one parse tree is possible.
22
Q
What is a precedence condition?
A
A condition for expressions with multiple operators, e.g. (2+3*4).
Each operator is given a precedence level. The higher the level, the deeper into the parse tree they are put (away from the root).
When an operator is deeper in the pipeline than another, we say it binds tighter than the other operator.
23
Q
What is a Associativity condition?
A
A condition for expressions with multiples of the same operators, e.g. (2-3-4).
Because all the operator would get the same precedence level, we add an associativity condition to be able to disambiguate them.
An associativity condition defines whether the leftmost or the rightmost operator binds tighter.
(2-3-4)
left: (2-3) - 4
right: 2- (3-4)
24
Q
How can partial definitions of nonterminals be written?
A
Using ‘…’
<expression> ::= <variable> | <int> | ...
</int></variable></expression>
25
Define the nonterminal using EBNF, a keyword and a string
26
What does [] mean in EBNF?
Whatever is within the brackets can occur zero or one time.
27
What does {...}+ mean in EBNF?
{} must contain minimum 1 expression
28
What is the semantics of a language?
What a program does when it executes the language.
29
What is the kernel language approach used for?
Defining the semantics of a program.
Define a kernel language, and combine with the data structures it manipulates forms the kernel computation model.
Define a translation scheme from a programming language to the kernel language. Each grammatical construct in the programming language is translated into kernel language. Translation is done by using linguistic abstraction and syntactic sugar.
NB: Each computation model has its own kernel language. These kernel languages builds on the kernel language of the models predecessor by adding concepts.
The declarative kernel language is an example of a kernel language.
30
What is the difference between a practical language and a kernel language?
Practical language provides abstractions for the programmer.
Kernel language contains minimalset of intuitive concepts.
Easy to reason in.
Has formal semantics
31
What is the four approaches to language semantics?
Operational
Axiomatic
Denotational
logical
32
What is an operational semantic?
Shows how statements execute in terms of an abstract machine
33
What is an axiomatic semantic?
Defines semantics as the relation between the input state and the output state, meaning, the situation before and after executing a statement.
34
What is an denotational semantic?
The semantics defines a statement as a function over an abstract domain.
35
What is an logical semantic?
Defines a statement as a model of a logical theory.
36
What is a linguistic abstraction?
Constructs that are both an abstraction and an addition to the language syntax.
Used when we need to extend a language (for example defining loops in a declarative language)
37
How are linguistic abstractions defined?
1. Define a new grammatical construct
2. Define its translation into the kernel language
Some examples:
fun, lazy, for, class
38
What is syntactic sugar?
Shortcut notation for frequently used idioms. This notation is part of the language syntax, and is defined by grammar.
39
What is the difference between syntactic sugar and linguistic abstraction?
Syntactic sugar does not extend the language, just shortens the program size.
40
How is syntactic sugar used when introducing local variables in e.g. if statements?
else
Local L in
...
end
end
else L in
...
end
41
What is an alternative to translation, when defining language semantics?
Interpreter approach.
An interpreter is written in language L1 and accepts programs written in language L2 and executes them.
The semantics is defined by giving an interpreter for the language.
In this case, new language features are created by extending the interpreter.
42
What are the datastructures used in declarative models?
A single assignment store: A set of variables initially unbound, and can be bound to one value.
Store:
{x1=1, x2=[2 4 5 6], x3}
x1 and x2 are bound, x3 is unbound.
43
What is a value store?
A store where all variables are bound to values.
43
What are declarative variables?
Variables in a single assignment store.
Also called dataflow variables.
Once bound, it stays bound throughout program execution, and is indistinguishable from its value.
This means that the expression a+b is the same as doing 11+23 if the store contains:
{a=11, b=23}
44
What are some benefits of using single assignment stores and not value stored?
Can store procedure returns in unbound input variables.
Declarative concurrency requires use of unbound variables.
Needed for relational- and constraint programming.
Efficiency - used in tail recursion.
45
What is a variable identifier?
Textual name that refers to a store-variable and can be used from outside the store.
Mapping from variable identifiers to store entities is called an environment.
store:
{x1: 100}
environment:
{X -> x1}
in statement: 'X'
46
How are variable identifiers and their corresponding store entities added to the environment?
Using declare and local.
47
What is a partial value?
Datastructures that may contain unbound variables.
48
When are partial values compatible?
When they can be bound in a way that they become equal?
person(age: 25) and person(age: x) are compatible.
49
What is an equivalence set?
When variables are bound to each other, and therefore become equal:
X = Y
In store:
{x1 = x2}
Whenever one variable in the set is bound, the other variables in the set sees this binding.
50
What is a variable-use error?
When variables are used before they are bound.
51
What languages create and bind variables in one step, to avoid variable-use errors?
Functional programming languages.
52
What are dataflow variables?
Declarative variables that causes the program to wait until they are bound.
A=23
B = A + 1
These can run in any order by threads, because B will wait on A regardless of order of execution.
53
What is the syntax of kernel language?
Page 49 and 50
54
What are the three types of value expressions in the declarative kernel language?
Numbers, records and procedures.
55
What is a type, or datatype, in the declarative kernel language?
Set of values together with a set of operations on those values.
e.g. integers or records.
56
What are abstract data types?
Types that are defined by the program.
57
What is static typing?
All variable types are known at compile time
58
What is dynamic typing?
The variable type is known when the variable is bound.
59
How is the declarative model typed?
Dynamically typed
60
What is the atom data type?
symbolic constant, used as a single element in calculation.
Start with lowercase letter, or single quoted characters.
thisIsAnAtom
`this is an atom`
61
What is a record?
label followed by a set of pairs.
These pairs contain a variable identifier and a feature.
features: integer, atom or boolean
62
What is a tuple?
Record whose features(identifiers?) are consecutive integers starting at 1.
person(1: x1 2:x2) and person(x1 x2) are the same
63
What is a list?
Either atom nil or tuple:
'|'(H T)
label: '|'
T: Either bound or unbound
64
What is a string?
A list of character codes (Ascii codes).
"E=mc2" = [69 61 109 99 94 50]
65
What does $ mean when dealing with procedures?
$ replaces the variable identifier.
The procedure is anonymous, meaning it is created without being bound to an identifier.
proc {$ x1 x2} end
66
How is procedures bound to indentifiers?
proc { 1 2 3} end
: The variable identifier
67
What operations have integers and floats?
float: +, -, *, /
Integers: +, -, *, /, mod, div (integer division)
68
What are the operations available to records?
Arity, Label, .
X = person(age: 26 name: "Jade")
{Arity X} = {age name}, returns integer features first, then atom features. age and name are atoms
{Label X} = person
X.age = 26
69
What does {IsProcedure P} do?
Returns true if P is a procedure.
70
What does the keyword local do?
Creates a variable in the store, and sets up a identifier to refer to this variable.
71
What does ? mean in front of a procedure input variable?
{proc P A B ?C}
C will contain the return value. On proc call, the C is unbound and will be bound within the proc.
Procedures uses call by reference to output results.
72
What are free identifiers?
Identifiers that are not defined in the current statement.
73
What is static and dynamic scoping?
Static: The identifiers used in statements take the values of the variable when the statement was created
Dynamic: The variable of an identifier is the most-recent declaration seen during execution leading up to a statement.
74
How are procedures scoped?
Procedures are statically scoped.
proc {P X ?Z}
if X < Y then Z=X else Z=Y end
end
Y is not bound by the statement, meaning it is a free variable.
When a program uses static scoping, Y will be the value it was when proc was defined
local Y in
Y = 10
proc {P X ?Z}
if X < Y then Z=X else Z=Y end
end
local Y=15 in
{P X ?Z}
end
end
When running P, the value of Y is 10, even when it is run in the statement defining Y to be 15. This is because this binding of Y did not exist when the procedure was created.
75
What is a procedural abstraction?
Any statement can be made into a procedure by putting it within a procedural definition.
76
What is dataflow behaviour?
When unbound variables are used, the program will wait until they become bound. Execution can continue when this happens.
77
What is a semantic statement?
A pair (, E)
: Statement
E: Environment
78
What is execution state?
The pair (ST, ohm)
ST: Stack of semantic statements
ohm: Single assignment store
79
What is a computation?
Sequence of execution states starting from an initial state
(ST2, ohm2) -> (ST2, ohm2) -> (ST3, ohm3)
80
What is a computational step?
A single transition in a computation
81
What are the 3 runtime states on a Semantic stack?
Runnable:ST can do a computational step
Terminated: ST is empty
Suspended: ST is not empty, but cannot do any computational steps
82
What does E() mean?
Retrieves the store entity that is related to the variable identifier
83
What 2 operations can be done to environments?
Adjunction: Defines a new environment by adding a mapping to an existing one
E + { -> x1}
This is a new environment that contains E and the mapping { -> x1}.
The new mapping of will override any mappings of identifier if it exists in E.
Restriction: Defines an environment E' that is a subset of an existing one.
E|{1, 2, ..., n}
The new environment only contain the identifiers of the ones mentioned in the set.
This holds true for all identifiers in E':
E'() = E()
84
How is the skip statement executed?
Semantic statement: (skip, E)
When poped from stack - execution completes
85
How is sequential composition executed?
Semantic statement: ( , E)
Push: (, E)
Push: (, E)
86
How are variable declaration executed?
Semantic statement:
(local in end, E)
Create a new store variable x
E' is E + { -> x}
push (, E')
87
What is the difference between a bound identifier occurence and a bound variable?
A bound identifier is a textual occurence of a variable name that occurs inside a construct that declares it (proc or local).
A bound variable is a dataflow variable that is bound to a partial value.
88
What are external references of a procedure?
Free variables thay are not parameters, defined once and for all when the procedure is declared.
89
What is the semantic statement of procedures?
(proc {$ $ ...} end, CE)
Within , there can be external references: ...
CE: Contextual environment
CE = E|{...}
E is the environment when the procedure is declared.
90
What is activation conditions
Must be true for a statement to be able to continue execution?
91
What type of statements have activation conditions?
Suspendable statements
examples in kernel language:
if then else end
case of then else end
`{` ...`}
E() must be bound for these to execute
92
How are conditional statements executed?
Semantic statement:
(if then else end, E)
Activation condition: E() is bound
Execution:
- If E() is not bool, raise error condition
- If E() is true, push (, E) on stack
- If E() is false, push (, E) on stack
- If activation condition is false - execution does not continue
93
What is tail recursion?
A procedure with a recursive call as the last call within the statement body.
Executes with a constant stack size.This property is call tail call optimization.
94
What does the active memory consist of?
Semantic stack and the reachable part of the store.
Reachable part of store: Referenced by a statement on the stack, or by another reachable part.
95
What are the three states of a memory block?
active: block allocated by memory
inactive: not reachable, but the program does not know this. If this memory is not reclaimed by system it will cause a leak.
free: deallocated, program sees that it does not need the block anymore
96
What are two errors that can occur during memory management?
Dangling reference: block is reclaimed when it is still reachable.
Memory leak: Exhaust memory
97
What is garbage collection?
Automatic reclaiming
98
How are variables bound immediately when declared?
local = in end
pattern: Any partial value
99
What is an expression?
Syntactic sugar for a sequence of operations that returns a value.
A statement is a sequence of operations that does not return a value.
Expression: 11*11
Statement: A=11*11
100
What does # and | mean in a pattern?
101
What does andthen and orthen do?
102
What is a nesting marker?
$: turns any statement into an expression
The value of the expression is what is at the position of the marker.
Statement: {P x1 x2 x3}
Expression: {P x1 $ x3} with value x2
local X in {Obj get(x)} {Browse X} end
can be written as:
{Browse {Obj get($)}}
Avoids the need to declare and bind the value X before printing it.
103
What is the difference between a procedure and a function?
Function is declared using the keyword fun.
A function must end in an expression.
104
How is functions translated into procedures?
fun {F x1 x2} end
proc {F x1 x2 ?R} R= end
Whenever an execution sequence ends in a statement in a procedure, the corresponding sequence ends in an expression in a function.
105
Define the Map function
fun {Map List F}
case List of nil then nil
[] H|T then
{F H} | {Map T F}
end
end
106
What does declare do?
Adds new mappings to the global environment.
declare X Y
Creates 2 new variables in the store, x1 and x2.
Creates mappings from x1 to X and x2 to Y. These mappings are in the global environment, making the variables global.
If a bound variable identifier is declare a second time, it will map to a new variable in the store, and the previous mapping to the bound variable is lost.
declare X // {X -> x1}
X = 25 // {X -> x1 (bound)}
declare X // {X -> x2}
107
What does {Browse X} do?
If X is bound, it displays the value of the store variable identified by X.
If X is unbound, it displays the variable identifier (X).
108
What does the try statement do?
Creates an exception-catching context and an exception handler
109
What does the raise statement do?
Jumps to the boundary of the inner-most exception-catching context and invokes the handler there.
110
What is the syntax of try statements?
try catch then end
if raises an exception, execution of is aborted and all elements relating to is poped from the stack.
then starts executing, and it is passed a reference to the exception ..
111
What does the catch statement do?
It is a marker on the semantic stack that defines the boundary of the exception-catching context.
catch then end
112
How are try-catch statements executed?
try catch then end
Push (catch then end, E) to stack
Push (, E) on stack
113
How does a raise statement execute?
(raise end, E)
Pop elements off the stack looking for a catch statement.
If the catch is not found, and the stack is empty, stop execution with an "Uncaught exception" error.
When (catch then end ,E_c) is found
Push (, {y -> E()} + E_c) on the stack
114
What does a finally clause do?
Is always executed, regardless of if an exception was raised or not.
try catch then finally end
115
How can pattern matching be used in try-catch statements?
try
catch then
[] then
[] then
end
