Programming Languages Flashcards
1
Q
What is a value?
A
A value is an expression that cannot be simplified any further.
2
Q
What is the term for:
an expression that cannot be simplified any further.
A
Value
3
Q
What term describes:
the types of all preceding bindings in the file.
A
static environment
4
Q
what term describes
the value of all preceding bindings in the file.
A
dynamic environment
5
Q
Give a rough definition of the static environment.
A
The static environment is roughly the types of all preceding bindings in the file.
6
Q
Give a rough definition of the dynamic environment.
A
The dynamic environment is roughly the value of all preceding bindings in the file.
7
Q
What is the term for “how an expression or statement is written”?
A
syntax
8
Q
stack data structure containing a element for each function that hasn’t finished executing.
A
call stack
9
Q
What is the term for “how an expression or statement is interpreted (i.e. how it is evaluated and type checked)”?
A
semantics
10
Q
describes a function call when there are no more pending computation after it is evaluated.
A
Tail call
11
Q
Describes the position of an expression e, when there are no pending computations after e is evaluated.
A
tail position
12
Q
What are the questions we ask when we encounter a new language construct?
A
- What is the syntax?
- What are the type checking rules?
- what are the evaluation rules?
13
Q
What is a “call stack”?
A
stack data structure containing a “stack frames” for each function that hasn’t finished executing.
14
Q
used to refer to a sub-type of an algebraic type.
A
variant
15
Q
In the context of algebraic-types, what does the term “carries” mean?
A
describe when a variant wraps one or more value.
16
Q
within the context of compound types, this is a piece of information that distinguishes one variant of a “one-of” type from the others.
A
tag
17
Q
a function with free variables that have been closed (or bound) by an environment.
A
closure
18
Q
A variable used within a function body that is neither a local variable or a function parameter.
A
free variable
19
Q
What is a “stack frame”?
A
A data structure containing information about a function invocation.
20
Q
What is a “tail call”?
A
A function call that occurs in “tail position”.
21
Q
What is “tail position”?
A
Describes the position of an expression e, when there are no pending computations after e is evaluated.
22
Q
How many kinds of compound types are there?
A
There are 3 types.
23
Q
List the types of compound types.
A
- sum-types or “each-of” type
- algebraic-types or “one-of” type
- self-referential type
24
Q
what is a variant in the context of “compound types”?
A
A variant refers to a sub-type of an algebraic type.
25
What is the term used to describe when a variant wraps one or more value.
the variant "carries" one or more values.
26
in the context of the "client/implementer" idom, this is a construct that hides the implementation of a solution, while providing the client with information on how to use the solution.
abstraction boundary
27
In the context of compound types, what is a "tag"?
within the context of compound types, this is a piece of information that distinguishes one variant of a "one-of" type from the others.
28
What is a closure?
a function with free variables that have been closed (or bound) by an environment.
## Footnote
- A function/expression must be closed before it can be evaluated.
- pairing an open function with an environment that binds the functions free variables, provides the information needed to evaluated the function (i.e. closes the function)
- with lexical scoping, functions are closed by the current lexical environment.
29
What is a "free variable"?
A variable used within a function body that is neither a local variable or a function parameter.
30
What is "parametric polymorphism"?
describes the property of a function/datatype when it can accept one or more type parameters.
31
describes the property of a function/data type when it accepts one or more type parameters.
parametric polymorphism
32
In the context of parametric polymorphism, what does the term "instantiated" mean?
In the context of parametric polymorphism, this is when a type parameter is reduced into a more concrete type (e.g. the type parameter 'a becomes int)
33
What is the "client-implementer" idiom?
Describes a method to separate the knowledge of traversing a complex data structure/problem space, from that of operating on the different components of of the data structure.
34
What is a "closed function"?
A function that does not reference any free variables.
35
Define "scope" as it relates to name bindings.
The environment in which a binding is valid.
36
What is "lexical scope"?
A scope which is determined by the lexical position of the binding. In other words, the environment in which the binding is valid is the current environment at the point in the file where the binding was defined.
37
How could mutually recursive functions be defined in a context where the underlying language does not provide support for mutual recursion?
1. define function-1 to accept an argument that matches function-2's signature.
2. Then define function-2 to call function-1, passing itself as an argument.
38
What is an abstraction boundary?
construct that hides the implementation of a solution, while providing the client with information on how to use the solution.
39
What is an invariant?
guarantee to functions/expression on the implementation side of the abstraction boundary.
40
What is a property?
guarantee to functions/expressions on the client side of the abstraction boundary.
41
Polymorphic type
a type that can be instantiated by multiple concrete types.
42
# What is the definition of:
Parameter passing strategy
defines the `binding strategy` and `evaluation order` of a function call.
## Footnote
[see article](https://en.wikipedia.org/wiki/Evaluation_strategy)
43
# What is the term for:
defines the `binding strategy` and `evaluation order` of a function call.
parameter passing strategy
44
# What is the definition of:
binding strategy
| within the context of parameter passing strategy
defines the type of values bound to a functions parameters.
| In other words, is the parameter given a reference or a copy of a value.
45
# What is the term for:
the strategy used to defines the type of values passed to a function for each parameter.
| Within the context of parameter pasing strategy
binding strategy
46
# What is the definition of:
evaluation order
| Within the context of parameter pasing strategy
defines whether the parameters of a expression or function call are evaluated, and if so in what order.
| is the first parameter evaluated first, or the last parameter?
47
# What is the term for:
the strategy that defines whether the parameters of a expression or function call are evaluated, and if so in what order.
| Within the context of parameter passing strategy
Evaluation order
48
# What is the definition of:
strict evaluation order
| within the context of parameter passing strategy
describes an evaluation order that results in strict functions.
49
# What is the term for:
describes an evaluation order that results in strict functions.
| within the context of parameter passing strategy
strict evaluation order
| AKA "applicative order", "greedy evaluation", or "eager evaluation"
50
# What is the definition of:
Strict function
a function is `strict` if it never terminates whenever applied to a non-terminating expression.
## Footnote
a non-terminating expression is an expression that does not terminate, either because it throws an error, loops infinately, etc.
51
# fill in the blank:
a function `f` is said to be ____ if `f` applied to an non-terminating expression results in `f` not terminating.
strict function
52
# What is the definition of:
Non-strict Evaluation order
| within the context of evaluation strategy
describes An evaluation order that results in non-strict functions.
| some or none of the arguments can be fully or even partially evaluated
53
# What is the term for:
describes an evaluation order that results in non-strict functions
| withing the context of evaluation strategy
non-strict evaluation order
54
# What is the definition of:
normal-order evaluation
| within the context of evaluation strategy
an evaluation strategy that first applies functions, then evaluates arguments.
## Footnote
[see this article](https://sookocheff.com/post/fp/evaluating-lambda-expressions/#normal-order-evaluation)
55
# what is the term for:
an evaluation strategy that reduces an expression to `normal form` by applying functions before evaluating the arguments.
normal-order evaluation
## Footnote
[see this article](https://sookocheff.com/post/fp/evaluating-lambda-expressions/#lazy-evaluation)
56
# what is the definition of:
applicative-order evaluation
an evaluation strategy that reduces an expression to `normal form` by evaluating function arguments before applying the function.
## Footnote
this has the effect of making functions strict.
57
# What is the term for:
an evaluation strategy that reduces an expression to `normal form` by evaluating function arguments before applying the function.
applicative-order evaluation
## Footnote
[see article](https://sookocheff.com/post/fp/evaluating-lambda-expressions/#applicative-order-evaluation)
58
lazy evaluation
describes a form of normal-order evaluation strategy that prevents repeated evaluation of a "function invocation" by memoizing the result after the first evaluation.
## Footnote
[see article](https://sookocheff.com/post/fp/evaluating-lambda-expressions/#lazy-evaluation)
59
normal form
an expression that has no more function applications.
## Footnote
[see article](https://sookocheff.com/post/fp/evaluating-lambda-expressions/)
60
# What is the evaluation order and binding strategy for:
call-by-value
**evaluation-order:** applicative-order
**binding-strategy:** parameters bound to a value.
## Footnote
Call-by-value is an applicative-order evaluation strategy that binds functions parameters to a value (resulting from the complete evaluation of the arguments.)
61
# What is the evaluation order and binding strategy for:
call-by-reference
**evaluation-order:** applicative-order
**binding-strategy:** parameters bound to `implicit reference` to a variable used by the caller.
## Footnote
call-by-reference is a applicative-order evaluation strategy that binds function parameters to an implicit reference to a variable.
The function defines a parameter that takes a variable. When the function is called, the function can modify the contents of the variable, meaning the caller would be able to see the modification.
62
# What is the evaluation order and binding strategy for:
call-by-sharing
**evaluation-order:** applicative-order
**binding-strategy:** parameters bound to a boxed-value.
| boxed-value is a value wrapped in an object to allow using as reference
## Footnote
call-by-sharing is a applicative-order evaluation strategy where the value is implemented as a reference, and the parameters are bound to the values.
this means that any modification made to the value is observable by the caller, but the callee cannot modify the content of any of the callers variables.
Think javascript objects, and functions.
63
# What is the evaluation order and binding strategy for:
call-by-name
**evaluation-order:** normal-order
**binding-strategy:** parameters bound to an implicit thunk wrapping the expression
## Footnote
call-by-name is a normal-order evaluation strategy that binds the parameters to a thunk.
64
# What is the evaluation order and binding strategy for:
call-by-need
**evaluation-order:** normal-order
**binding-strategy:** parameters bound to an implicit memoized-thunk wrapping the expression
## Footnote
call-by-name is a normal-order evaluation strategy that binds the parameters to a memoized-thunk.
65
what is the main disadvantage of call-by-name?
When a parameter is only needed once, call-by-name is ideal. However, if the parameter is needed in multiple locations:
1. the wrapped expression is evaluated multiple times. This is undesireable because of possible performance implications.
2. any side-effects in the wrapped expression will also be executed multiple times. This is undesireable because it could cause duplicate data in storage, unneeded network a calls etc.
66
# What is the definition of:
interpreter
| within the context of language implementation
a program that evaluates a source-language program and produces a value in the same source-language.
67
# What is the term for
a program that evaluates a source-language program and produce a value in the same source-language.
| within the context of language implementation
interpreter
68
# what is the definition of:
compiler
| within the context of language implementation
a program that takes a source-language program and produces an equivalent target-language program.
69
# what is the term for:
a program that converts a source-language program into an equivalent target-language program.
| within the context of language implementation.
compiler
70
# what is the term for:
the language used to implement the interpreter/compiler.
| within the context of language implementation
meta-language
71
# what is the definition of:
meta-language
| within the context of language implementation
the language used to implement the compiler/interpreter.
72
# define:
static checking
| within the context of language implementation
anything done to reject successfully parsed programs before they run.
73
# what is the term for
checks made to reject successfully parsed programs before they run.
static checking
74
# define
soundness
| within the context of language design
a property of a type-system that means it will never allow a program that does something the language declares should not occur.
| no false negatives.
## Footnote
lets say you have a shuttle to marse. A lot of people don't want the ship to take off (damn eco-terrorists). The organization in charge declares publicly that it will never be possible for a bomber to be on the ship at take-off.
The walls around the ship are absolute, so no one can pass except through the gates. The guards at the gate (type-checker) has a list of properties that would constitute a bomber. The guards must ask themselves for each person "is this person gonna blow up the ship"? if the answer is positive, they kick him out. If the answer is negative they allow him.
**The security system (i.e. the static-checker) is said to be sound if, the checks at the gate are 100% effective at identifying a bomber.** Notice that while they may be effective at identifying bombers, they may also mistake an engineer as a bomber, since they may have some of the same characteristics. This is a question of correctness.
75
# what is the term for
a property of a type system such that, given a property X that the language has declared should never exist in a running program, it never allows any program that has the property X.
| every program with property X, will always be flagged
soundness
76
# define
correctness
| within the context of language design
a property of a type-system such that, it will never reject a program that never does something the language has declared should not occur.
| no false positives
## Footnote
given a sound security system as described in soundness card. Whenever a person is identified who match the criteria of a bomber, the guards at the gate have an additional checklist, that enumerates the properties that would identity an engineer, or mechanic etc.
The security system (i.e. type-check) is said to be correct if, it never rejects persons who could/would never blow up the shuttle under any circumstance, even if they share properties with potential bombers (i.e. engineers, mechanics, miners, bomb experts etc.)
77
# what is the term for
a property of a type system such that it would never reject a program that would never under any circumstance do something the language has declared would never occur.
| within the context of language design
correctness
78
how many rules are their to class-based object oriented programming
5
79
what are the rules to class-based OOP
1. all values (i.e. the result of evaluating expressions) are references to objects.
2. given an object, code (i.e. clients) communicate with it by sending messages (i.e. calling methods) on it.
3. each object has its own private state that can only be directly accessed from within methods of the object.
4. every object is an instance of a class.
5. an objects behaviour is determined by its class.
80
# explain:
method call semantics
| within the context of Ruby programming
Given a method call e0.m(e1, e2, ... en):
1. evaluate e0 - en to objects
2. searches for and calls the method m, passing the results of e1-en as arguments.
81
# What is the definition for:
message send
| within the context OOP
describes when a *client* calls a method on an object.
82
what is *client* code
| within the context of OOP
an code that interacts with an object is a client of that object.
83
# what is a
reciever
| within the context of OOP
the reciever is the object "recieving the message" sent by the client code. In other words the object on which a method is called.
84
# what is the definition of:
instance variable
a variable that belongs to an instance-object and is only valid within methods called on that object.
85
# what is the definition of
class variable
a variable that belongs to a class that is only visible by instances of that class.
| class variable modification by any instance is visible by all instances
86
# what is
class constant
| within the context of OOP
like a class variable, belongs to a class, but is visible by any object of any class.
87
# what is
public method
a method who's client can be any object of any class.
88
# what is
protected method
a method who's client can only be instances of the recievers class or sub-class.
89
# what is
private method
a method who's clients can only be methods of the recieving object.
90
# what is
duck typing
refers to the idea that the client only needs the object to be able to handle a given message, not that the object be instance of a given class.
## Footnote
it can be a dog, but since I only need the sound of a duck, as long as that dog can quack i can use it.
