Brainscape's Knowledge GenomeTM

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


See full index

Programming languages > 2.0 Declarative computation model > Flashcards

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.

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

What is a programming model?

A

Programming techniques and principles used to write programs in the language of the computation model.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

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

What is imperative programming?

A

Stateful programming

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

What is language syntax?

A

What are legal programs, programs that can be executed.

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

What is language grammars?

A

Rules on how to make statements (‘sentences’) out of tokens (‘words’).

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

What is a statement?

A

Sequence of tokens

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

What is a token?

A

Sequence of characters

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

What is a tokenizer?

A

A lexical analyser.

Program that takes a sequence of characters and returns a sequence of tokens.

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

What is a parser?

A

A program that takes a sequence of tokens and returns a parse tree.

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

What is a parse tree?

A

Shows the structure of statements.

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

What is the Extended Backus-Naur form (EBNF)?

A

Notation for defining grammar.

Uses terminal- and non-terminal symbols.

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

What is a terminal symbol?

A

Tokens

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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>

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

What is a formal language?

A

Set of all possible statements generated by a grammar.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

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

What is context-sensitive grammar?

A

Grammar containing nonterminals whose use depends on the context where it is used.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

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

How can partial definitions of nonterminals be written?

A

Using ‘…’

<expression> ::= <variable> | <int> | ...
</int></variable></expression>

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

Define the nonterminal <statement> using EBNF, a keyword and a string</statement>

A

<statement> ::= skip | <exp> '=' <exp>

skip: Keyword, does not need quotes as we know that it is a keyword

'=': add string in between nonterminals using quote
</exp></exp></statement>

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

What does [] mean in EBNF?

A

Whatever is within the brackets can occur zero or one time.

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

What does {…}+ mean in EBNF?

A

{} must contain minimum 1 expression

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

What is the semantics of a language?

A

What a program does when it executes the language.

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

What is the kernel language approach used for?

A

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.

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

What is the difference between a practical language and a kernel language?

A

Practical language provides abstractions for the programmer.

Kernel language contains minimalset of intuitive concepts.
Easy to reason in.
Has formal semantics

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

What is the four approaches to language semantics?

A

Operational

Axiomatic

Denotational

logical

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

What is an operational semantic?

A

Shows how statements execute in terms of an abstract machine

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

What is an axiomatic semantic?

A

Defines semantics as the relation between the input state and the output state, meaning, the situation before and after executing a statement.

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

What is an denotational semantic?

A

The semantics defines a statement as a function over an abstract domain.

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

What is an logical semantic?

A

Defines a statement as a model of a logical theory.

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

What is a linguistic abstraction?

A

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)

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

How are linguistic abstractions defined?

A
  1. Define a new grammatical construct
  2. Define its translation into the kernel language

Some examples:
fun, lazy, for, class

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

What is syntactic sugar?

A

Shortcut notation for frequently used idioms. This notation is part of the language syntax, and is defined by grammar.

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

What is the difference between syntactic sugar and linguistic abstraction?

A

Syntactic sugar does not extend the language, just shortens the program size.

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

How is syntactic sugar used when introducing local variables in e.g. if statements?

A

else
Local L in
…
end
end

else L in
…
end

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

What is an alternative to translation, when defining language semantics?

A

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.

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

What are the datastructures used in declarative models?

A

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.

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

What is a value store?

A

A store where all variables are bound to values.

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

What are declarative variables?

A

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}

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

What are some benefits of using single assignment stores and not value stored?

A

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.

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

What is a variable identifier?

A

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’

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

How are variable identifiers and their corresponding store entities added to the environment?

A

Using declare and local.

47
Q

What is a partial value?

A

Datastructures that may contain unbound variables.

48
Q

When are partial values compatible?

A

When they can be bound in a way that they become equal?

person(age: 25) and person(age: x) are compatible.

49
Q

What is an equivalence set?

A

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
Q

What is a variable-use error?

A

When variables are used before they are bound.

51
Q

What languages create and bind variables in one step, to avoid variable-use errors?

A

Functional programming languages.

52
Q

What are dataflow variables?

A

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
Q

What is the syntax of kernel language?

A

Page 49 and 50

54
Q

What are the three types of value expressions in the declarative kernel language?

A

Numbers, records and procedures.

55
Q

What is a type, or datatype, in the declarative kernel language?

A

Set of values together with a set of operations on those values.

e.g. integers or records.

56
Q

What are abstract data types?

A

Types that are defined by the program.

57
Q

What is static typing?

A

All variable types are known at compile time

58
Q

What is dynamic typing?

A

The variable type is known when the variable is bound.

59
Q

How is the declarative model typed?

A

Dynamically typed

60
Q

What is the atom data type?

A

symbolic constant, used as a single element in calculation.
Start with lowercase letter, or single quoted characters.

thisIsAnAtom
this is an atom

61
Q

What is a record?

A

label followed by a set of pairs.
These pairs contain a variable identifier and a feature.

features: integer, atom or boolean

62
Q

What is a tuple?

A

Record whose features(identifiers?) are consecutive integers starting at 1.

person(1: x1 2:x2) and person(x1 x2) are the same

63
Q

What is a list?

A

Either atom nil or tuple:
‘|’(H T)

label: ‘|’
T: Either bound or unbound

64
Q

What is a string?

A

A list of character codes (Ascii codes).

“E=mc2” = [69 61 109 99 94 50]

65
Q

What does $ mean when dealing with procedures?

A

$ replaces the variable identifier.

The procedure is anonymous, meaning it is created without being bound to an identifier.

proc {$ x1 x2} <s> end</s>

66
Q

How is procedures bound to indentifiers?

A

proc {<x> <y>1 <y>2 <y>3} <s> end</s></y></y></y></x>

<x>: The variable identifier
</x>

67
Q

What operations have integers and floats?

A

float: +, -, *, /

Integers: +, -, *, /, mod, div (integer division)

68
Q

What are the operations available to records?

A

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
Q

What does {IsProcedure P} do?

A

Returns true if P is a procedure.

70
Q

What does the keyword local do?

A

Creates a variable in the store, and sets up a identifier to refer to this variable.

71
Q

What does ? mean in front of a procedure input variable?

A

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

What are free identifiers?

A

Identifiers that are not defined in the current statement.

73
Q

What is static and dynamic scoping?

A

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
Q

How are procedures scoped?

A

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
Q

What is a procedural abstraction?

A

Any statement can be made into a procedure by putting it within a procedural definition.

76
Q

What is dataflow behaviour?

A

When unbound variables are used, the program will wait until they become bound. Execution can continue when this happens.

77
Q

What is a semantic statement?

A

A pair (<s>, E)</s>

<s>: Statement
E: Environment
</s>

78
Q

What is execution state?

A

The pair (ST, ohm)

ST: Stack of semantic statements
ohm: Single assignment store

79
Q

What is a computation?

A

Sequence of execution states starting from an initial state

(ST2, ohm2) -> (ST2, ohm2) -> (ST3, ohm3)

80
Q

What is a computational step?

A

A single transition in a computation

81
Q

What are the 3 runtime states on a Semantic stack?

A

Runnable:ST can do a computational step

Terminated: ST is empty

Suspended: ST is not empty, but cannot do any computational steps

82
Q

What does E(<x>) mean?</x>

A

Retrieves the store entity that is related to the variable identifier <x></x>

83
Q

What 2 operations can be done to environments?

A

Adjunction: Defines a new environment by adding a mapping to an existing one
E + {<x> -> x1}
This is a new environment that contains E and the mapping {<x> -> x1}.
The new mapping of <x> will override any mappings of identifier <x> if it exists in E.</x></x></x></x>

Restriction: Defines an environment E’ that is a subset of an existing one.
E|{<x>1, <x>2, ..., <x>n}
The new environment only contain the identifiers of the ones mentioned in the set.
This holds true for all identifiers in E':
E'(<x>) = E(<x>)</x></x></x></x></x>

84
Q

How is the skip statement executed?

A

Semantic statement: (skip, E)
When poped from stack - execution completes

85
Q

How is sequential composition executed?

A

Semantic statement: (<s1> <s2>, E)</s2></s1>

Push: (<s1>, E)
Push: (<s2>, E)</s2></s1>

86
Q

How are variable declaration executed?

A

Semantic statement:
(local <x> in <s> end, E)</s></x>

Create a new store variable x
E’ is E + {<x> -> x}
push (<s>, E')</s></x>

87
Q

What is the difference between a bound identifier occurence and a bound variable?

A

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
Q

What are external references of a procedure?

A

Free variables thay are not parameters, defined once and for all when the procedure is declared.

89
Q

What is the semantic statement of procedures?

A

(proc {$ $ <y1>...<yn>} <s> end, CE)</s></yn></y1>

Within <s>, there can be external references: <z1>...<zn></zn></z1></s>

CE: Contextual environment
CE = E|{<z1>...<zn>}</zn></z1>

E is the environment when the procedure is declared.

90
Q

What is activation conditions

A

Must be true for a statement to be able to continue execution?

91
Q

What type of statements have activation conditions?

A

Suspendable statements

examples in kernel language:
if<x> then <s> else <s2> end</s2></s></x>

case <x> of <pattern> then <s1> else <s2> end</s2></s1></pattern></x>

{<x> <y1> ...<yn>`}</yn></y1></x>

E(<x>) must be bound for these to execute</x>

92
Q

How are conditional statements executed?

A

Semantic statement:
(if<x> then <s> else <s2> end, E)</s2></s></x>

Activation condition: E(<x>) is bound</x>

Execution:
- If E(<x>) is not bool, raise error condition
- If E(<x>) is true, push (<s1>, E) on stack
- If E(<x>) is false, push (<s2>, E) on stack
- If activation condition is false - execution does not continue</s2></x></s1></x></x>

93
Q

What is tail recursion?

A

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
Q

What does the active memory consist of?

A

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
Q

What are the three states of a memory block?

A

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
Q

What are two errors that can occur during memory management?

A

Dangling reference: block is reclaimed when it is still reachable.

Memory leak: Exhaust memory

97
Q

What is garbage collection?

A

Automatic reclaiming

98
Q

How are variables bound immediately when declared?

A

local <pattern>=<expression> in <statement> end</statement></expression></pattern>

pattern: Any partial value

99
Q

What is an expression?

A

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: 1111
Statement: A=1111

100
Q

What does # and | mean in a pattern?

A
101
Q

What does andthen and orthen do?

A

<expression1> andthen <expression2>
translates to:
if <expression1> then <expression2> else false ens
<expression2> is not evaluated if <expression1> is false

<expression1> orthen <expression2>
translates to:
if <expression1> then true else <expression2> end
<expression2> is not evaluated if <expression1> is true
</expression1></expression2></expression2></expression1></expression2></expression1></expression1></expression2></expression2></expression1></expression2></expression1>

102
Q

What is a nesting marker?

A

$: 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
Q

What is the difference between a procedure and a function?

A

Function is declared using the keyword fun.

A function must end in an expression.

104
Q

How is functions translated into procedures?

A

fun {F x1 x2} <statement> <expression> end</expression></statement>

proc {F x1 x2 ?R} <statement> R=<expression> end</expression></statement>

Whenever an execution sequence ends in a statement in a procedure, the corresponding sequence ends in an expression in a function.

105
Q

Define the Map function

A

fun {Map List F}
case List of nil then nil
[] H|T then
{F H} | {Map T F}
end
end

106
Q

What does declare do?

A

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
Q

What does {Browse X} do?

A

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
Q

What does the try statement do?

A

Creates an exception-catching context and an exception handler

109
Q

What does the raise statement do?

A

Jumps to the boundary of the inner-most exception-catching context and invokes the handler there.

110
Q

What is the syntax of try statements?

A

try <s> catch <x> then <s1> end</s1></x></s>

if <s> raises an exception, execution of <s> is aborted and all elements relating to <s> is poped from the stack.</s></s></s>

<s1> then starts executing, and it is passed a reference to the exception <x>..
</x></s1>

111
Q

What does the catch statement do?

A

It is a marker on the semantic stack that defines the boundary of the exception-catching context.

catch <x> then <s> end</s></x>

112
Q

How are try-catch statements executed?

A

try <s> catch <x> then <s1> end</s1></x></s>

Push (catch <x> then <s1> end, E) to stack
Push (<s>, E) on stack</s></s1></x>

113
Q

How does a raise statement execute?

A

(raise <x> end, E)</x>

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 <x> then <s1> end ,E_c) is found</s1></x>

Push (<s>, {y -> E(<x>)} + E_c) on the stack</x></s>

114
Q

What does a finally clause do?

A

Is always executed, regardless of if an exception was raised or not.

try <s> catch <x> then <s2> finally <s3> end</s3></s2></x></s>

115
Q

How can pattern matching be used in try-catch statements?

A

try <s>
catch <p1> then <s1>
[] <p2> then <s2>
[] <p3> then <s3>
end</s3></p3></s2></p2></s1></p1></s>

Programming languages (11 decks)

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