Notes - Imperative Programming HT23, Abstract data types
Flashcards
What comments should you decorate the top of traits/interfaces for abstract data types with?
-
state, what the abstract data type stores -
init, the state of the abstract data type on initialisation
What comments should you decorate the methods in a trait for an abstract data type with?
-
pre, what is required before the method is called -
post, how the state is updated after the the method is called, and what is returned
If you have an abstract data type with some state $S$, what would the post condition look like for an operation which does not modify the state?
What is the difference between the abstract state and the concrete state when implementing an abstract data type?
- Concrete state, what is actually being stored on the machine
- Abstract state, what is being represented by the concrete state
When implementing an abstract datatype, we need to ensure that the pre and post conditions of each method in the trait are satisfied. These pre conditions and post conditions are written in terms of some abstract state $S$. What notation is used for reasoning about the relationship between the concrete state of the specific implementation and abstract state?
the abstraction function, takes a concrete state and returns the abstract state.
If a method in a trait defining an abstract datatype has the pre and post conditions
\[\begin{aligned}
&\text{pre: } \mathbf{pre}(a) \\\\
&\text{post: returns res s.t. } \mathbf{post}(a_0, a, \text{res}) \\\\
\end{aligned}\]
what should the pre and post conditions for the concrete implementation look like?
Why might “representational invariant” be a better name than datatype invariant?
It carries across the fact that the fact that the invariant is a property of the concrete implementation rather than of the abstract datatype.
What should be the abstract state for a priority queue?
A bag/multiset.