Flashcards
Comparative Programming
Cards in this deck (41)
- 1What is meant by alpha-equivalence?Two or more functions represent the same computation
- 2When is it appropriate to use alpha-conversion?When reducing an application of two or more lambda terms of which one has bounded variables with the same name as some of the free variables in the other
- 3What is the main computation rule?beta-reduction which indicates how to find the result of a function for a given argument.
- 4How do you identify a redex?When there is a lambda term applied to another lambda term. In other words:
(\x.M)N - 5What is a closed lambda term?A term which does not contain any free variables.
- 6How do you reduce a lambda term to its weak head normal form?By stopping reduction when there are no redexes left which are not contained in an abstraction.
- 7What is meant by a normalisable?A term which can be reduced to a normal form.
- 8What type of normal form do all functional languages use?Weak head normal form because some lambda terms do not terminate.
- 9Which lambda term does not have a normal form?(λx.xx) (λ x.xx)
- 10What does confluence imply?Unicity of normal form
- 11When should a * be used in a reduction graph?When a term has two reduction sequences which both reduce to the same term. For example
λx.x (λx.x(λx.x))
OR
I (I I) - 12What is a tail-recursive function?One which uses an accumulator
- 13Why are tail-recursive functions sometimes used?Because they tend to require less memory resources and they do not require a stack. This also helps avoid stack overflow problems. As a result, they can be less computationally expensive for some functions.
- 14What is meant by (weak) normalisation?There exist a sequence of reductions which terminates. E.g. 42 applied to infinity. If call by value is used then it will never terminate, but if call by name is used then it will after 1 reduction.
- 15What is meant by strong normalisation?All reduction sequences terminate.
- 16Is the lambda calculus normalising or strongly normalising?It is neither
- 17When does Java use call-by-value and when does it use call-by-name?It uses call-by-value when evaluating primitive types and call-by-name when evaluation object types.
- 18What is lazy evaluation?When arguments are evaluated at most one time.
- 19What is the main benefit of call-by-value?Duplication of work is avoided. For example: square (3+4) would reduce to 7 * 7 in call-by-value. In call-by-name it would reduce to (3+4)*(3+4) which would result in 3+4 being evaluated twice.
- 20What is meant by a linear lambda term?Every argument is used just once.
- 21Which λ term does not have a type and why?λx.xx because it uses self-application.
- 22Which λ term has a normal form but does not have a type? Explain answer.(λx.x) (λx.xx). This has a normal form because of the identity function, however, because it reduces to λx.xx it does not have a type because the term uses self-application.
- 23Which λ term has a normal form and a type? Explain answer.(λx.x) (λx.x). This has a normal form because it reduces to λx.x which is the identity function and therefore has type
x -> x - 24With the λ term Y, what property must it have for it to be non-normalisable?If a beta reduction of the term Y results in a sub-term which is the same as Y. For instance, let Y = (λx.xx) (λx.xx). With each reduction step, the new sub-term will be λ(x.xx) (λx.xx).
- 25Write the Y combinator as a λ termλ f.(λ x.f(xx)) (λ x.f(xx))
- 26Give a λ term which is infinitely recursive(λ x.xx) (λ x.xx)
- 27What are the built in data types of Haskell?1) Integer
2) Double
3) Bool
4) Char - 28What is ad-hoc polymorphism?It is another term for function or method overloading.
- 29What is a disjoint union type?A way of representing several alternative types. For example, if we want an array of integers or booleans, we can define a type IntOrBool and create an array of this type.
- 30What are the main differences between the pure and simply typed lambda calculus?In the simply typed lambda calculus, terms are constrained. Also, it is strongly normalising unlike the pure lambda calculus. Therefore, all programs will terminate no matter which reduction strategy is used. In other words, if a term is non-linear such as: λ x.xx, then it is considered not to have a type
- 31What makes imperative languages different?The salient feature of imperative languages is that they use a memory that is updated by the program
- 32What is dynamic lookup?When a message is sent to an object, the method executed is determined by the object implementation. Different objects can respond differently to the same message. The response is not based on the static property of the variable or pointer.
- 33What is abstraction?Implementation details are hidden inside a program unit and exposed via a specific interface. Usually a set of public methods manipulate private data.
- 34Explain subtypingIf an object A has all the functionality of another object B, we can use A in place of B in contexts expecting A. Subtyping means that the subtype has at least as much functionality as the base type.
- 35Explain inheritanceReuse definition of one type of object when defining another object.
- 36What is a product type?
- 37What is a disjoint union type? Also known as sum type or union type.When a type can be one or another thing. For example:
data IntOrBool = I Int | B Bool - 38What is the difference between a product type and disjoint union type?A product type can be composed of several other types whereas a disjoint union type can only be one thing or another.
Think of product as AND and disjoint union as OR. - 39How can a disjoint union type be represented in a product type?If you want to represent IntOrBool in a product type you can create a type with 3 components. The first can be an Int, the second can be a Bool and the third can be another Bool or Int which will indicate the component to look at (i.e., the first Int component or the second Bool component).
- 40What is the disadvantage of using a product type to represent a disjoint union type?Too much space is consumed. For example the (Int, Bool, Bool) approach uses up 3 data types when a disjoint union would only use 1.
- 41How do you make a disjoint union type in C?union intOrChar {int x; char y; };
Information
- Description
- Flashcards on Comparative Programming, created by zenos pavlakou on 12/01/2019.
- Created by
- zenos pavlakou
- Views
- 8
- Rating