CookieJar Abstract Data Type
H. Conrad Cunningham
27 April 2022
Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of April 2022 is a recent version of Firefox from Mozilla.
The CookieJar problem corresponds (more or less) to exercises 4 and 5 on page 33 of Dale and Walker [1]. The exercise is to define and implement an abstract data type (ADT) for cookie jars, with operations for manipulating the jar and its contents.
As defined in the Dale and Walker textbook, the CookieJar ADT has the following operations:
Create
PutIn(CookieJar,CookieType)
cookieType
into the cookieJar
Eat(CookieJar,CookieType)
cookieType
from the cookieJar
IsIn(CookieJar,CookieType)
cookieType
IsEmpty(CookieJar)
Note: In a concrete implementation for this ADT, we use names for types, operations (i.e., functions or procedures), and variables that are more idiomatic for the language than the above names.
TODO: Give reference/link to the Data Abstraction document.
In (more or less) the notation of Dale and Walker [1], we can specify an axiomatic semantics specification for the CookieJar ADT as follows.
structure CookieJar (of CookieType)
interface
Create -> CookieJar
IsEmpty(CookieJar) -> Boolean
PutIn(CookieJar,CookieType) -> CookieJar
IsIn(CookieJar,CookieType) -> Boolean
Eat(CookieJar,CookieType) -> CookieJar
end
axioms for all Cookie1 and Cookie2 in CookieType,
Jar in CookieJar, let
IsEmpty(Create) = True
IsEmpty(PutIn(Jar,Cookie1)) = False
IsIn(Create,Cookie1) = False
IsIn(PutIn(Jar,Cookie2),Cookie1) =
IF Cookie1 = Cookie2
THEN True
ELSE IsIn(Jar,Cookie1)
END IF
Eat(Create,Cookie1) = Error
Eat(PutIn(Jar,Cookie2),Cookie1) =
IF Cookie1 = Cookie2
THEN Jar
ELSE PutIn(Eat(Jar,Cookie1),Cookie2)
END IF
end
end CookieJar
The source code files for an implementation of this ADT give a constructive semantics for that implementation. We give these semantics specifications as plain text in program comments in the source code files. The following document summarizes this notation:
In the case of the CookieJar ADT, it is convenient to use a bag to describe the ADT’s semantics.
We define the interface to a family of immutable CookJar ADTs using a Scala trait. The ADT operations use a method-chaining functional style.
We express the constructive semantics in source code comments using the plain-text specification notation described above. We use a bag to represent the abstract model for the ADT’s state, invariants to give the details of the data representation, and precondition and postcondition contracts to specify the behavior of the operations.
The trait is defined in the following Scala source file:
Given this trait, we define three different implementations of the ADT, each of which uses a different representation for CookieJar’s “bag”.
In addition, we give a simple Blackbox test script for the above implementations in the source file:
We define the interface to a family of mutable CookJar ADTs using a Scala trait. The ADT operations use a traditional object-oriented style.
We express the constructive semantics in source code comments using the plain-text specification notation described above. We use a bag to represent the abstract model for the ADT’s state, invariants to give the details of the data representation, and precondition and postcondition contracts to specify the behavior of the operations.
The trait is defined in the following Scala source file:
We define five different implementations, each of which uses a different representation for CookieJar’s “bag”.
In addition, we give a simple Blackbox test script for the above implementations in the source file:
We designed a family of Python ADTs similar to the Scala mutable ADTs above.
We define the interface to a family of mutable CookJar ADTs using a Python 3.7+ abstract class and optional type annotations. The ADT operations use a traditional object-oriented style.
We express the constructive semantics in source code comments using the plain-text specification notation described above. We use a bag to represent the abstract model for the ADT’s state, invariants to give the details of the data representation, and precondition and postcondition contracts to specify the behavior of the operations.
The abstract class for the “standard” mutable CookieJar ADT is defined in the following Python 3.7+ source file:
As above, we define two different implementations, each of which uses
a different representation for CookieJar’s “bag”. These extend the
abstract class and are implemented using the @dataclass
decorator. They are also annotated with the optional types.
In addition, we give a simple Blackbox test script for the above implementations in the source file:
We define the interface to a family of (an extended) mutable CookJar ADTs using a Python 3.7+ abstract class with optional type annotations. The ADT operations use a traditional object-oriented style.
We express the constructive semantics in source code comments using the plain-text specification notation described above. We use a bag to represent the abstract model for the ADT’s state, invariants to give the details of the data representation, and precondition and postcondition contracts to specify the behavior of the operations.
These ADTs extend the ADTs above by adding two other simple accessor methods. We use these in refining the semantics of other operations.
The abstract class for the “extended” mutable CookieJar ADT is defined in the following Python 3.7+ source file:
As with the “standard” ADTs, we define two different implementations,
each of which uses a different representation for CookieJar’s “bag”.
These extend the abstract class and are implemented using the
@dataclass
decorator. They are also annotated with the
optional types.
In addition, we give a simple Blackbox test script for the above implementations in the source file:
The first implementation I did of this ADT was a simple object-oriented Ruby program in 2006. It implements a mutable ADT using a Ruby dynamic array as its representation.
Note: These old programs and solutions follow the Dale and Walker book more closely and may not use the same specification notation as the other solutions.
In my graduate Special Topics class on Ruby and Software Development (Engr 692) in Fall 2006, I assigned exercises 4 and 5 on page 33 of the Dale and Walker [1] to my students. In addition to the specification, they were to develop a simple implementation in Ruby. The Ruby implementation is my solution to that exercise.
I developed several solutions in other languages over the years when I have used the program as an example and/or an exercise.
I retired from the full-time faculty in May 2019. As one of my post-retirement projects, I am continuing work on possible textbooks based on the course materials I had developed during my three decades as a faculty member. In January 2022, I began refining the existing content, integrating separately developed materials together, reformatting the documents, constructing a unified bibliography (e.g., using citeproc), and improving my build workflow and use of Pandoc. I adapted this index page from a portion of my Spring 2019 CSci 555 course notes.
I maintain this chapter as text in Pandoc’s dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed.