OOP experiments in Mathematica- The Stack
- To: mathgroup at smc.vnet.net
- Subject: [mg38656] OOP experiments in Mathematica- The Stack
- From: "Steve S. Shaw" <steve at shawstudio.com>
- Date: Fri, 3 Jan 2003 00:15:51 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
A series of OOP experiments in Mathematica.
msg#2 - The Stack, part#1: Mathematics of a stack.
Having listed Goals and References in msg#1,
(post 4 of thread "Re: Re: OOP in Mathematica" on 30-Dec-2002),
now consider one small example using OOP.
-----------------------------------------------------------------
----- A classic programming task - a stack -----
-----------------------------------------------------------------
Mathematics of a stack, based on:
[Meyer-97] Ch. 6. Abstract data types.
sec. 6.1-6.4 gives an "abstract data type" prescription for a stack.
- - - - -
Brief explanation of syntax:
* "STACK" -- type names are all-capitals.
* "ANY" -- like "Object" in Java
* "new() -> STACK" -- function named 'new' takes no parameters,
and returns a stack.
* "push( STACK, ANY ) -> STACK" -- function named 'push',
takes two parameters: (a stack) and (any object), and returns a
stack.
NOTE: this doesn't explain what push does, it just declares what object
types come in and out of the function. This is a pure-functional
(no-side-effect) mathematical specification - so any change is shown by
creating a new object, rather than modifying an existing object.
In the OO languages, for a "mutable" type "Stack",
"STACK in and STACK out" will be turned into a single STACK that is changing
state.
The actual behavior of the functions is determined implicitly from the
axioms that come later.
* "drop( STACK ) -> STACK
drop( s ) require not empty( s )" -- function named 'drop',
takes a stack and returns a stack. This will become an action that
changes the state of a stack.
The "require" part is a condition - this function must only be called
with a non-empty stack.
-----------------------------------
--- Mathematics of a stack ---
For any "x" of type "ANY" and "s" of type "STACK"...
Type:
STACK
Type-signatures of FUNCTIONS with PRECONDITIONS:
* new() -> STACK
* isEmpty( STACK ) -> BOOLEAN
* push( STACK, ANY ) -> STACK
* top( STACK ) -> ANY
top( s ) require not isEmpty( s )
* drop( STACK ) -> STACK
drop( s ) require not isEmpty( s )
Axioms:
A1. isEmpty( new() ) = True
A2. isEmpty( push( s, x ) ) = False
A3. top( push( s, x ) ) = x
A4. drop( push( s, x ) ) = s
-----------------------------------
Informally, this is saying:
A1. "new()" creates an empty stack.
A2. After "push", a stack is not empty.
A3. "push( s, x )" causes 'x' to now be "top" of stack.
A4. "push" followed by "drop" returns the stack as it was before the push.
Combining these axioms, produces all the desired behavior of a stack.
For example:
top( push( new(), x1 ) ) = x1
top( push( push( new(), x1 ), x2 ) = x2
top( drop( push( push( new(), x1 ), x2 ) ) ) ) = x1
Because PRECONDITIONS are specified,
we can also discover ILLEGAL operations on a stack:
top( new() )
=> ERROR "top( s ) require not isEmpty( s )"
drop( drop( push ( new(), x1 ) ) )
=> ERROR "drop( s ) require not isEmpty( s )"
NOTE: wondering where "pop()" is?
That is a compound action.
"pop( s )" is equivalent to:
" temp = top( s )
drop( s )
return temp"
-----------------------------------------------------------------
Here is that mathematical spec, as it might be shown in Mathematica:
NOTE: Since this example doesn't involve "inheritance", it can be modeled
using a simple type. That is, by having the "head" of an expression be
"STACK".
NOTE: "conditions" aren't yet shown.
(*-- Functions of a stack --*)
new[]
isEmpty[ s_STACK ]
push[ s_STACK, x_ ]
top[ s_STACK ]
drop[ s_STACK ]
(*-- Axioms of a stack. True for any s & x. --*)
axiom1[]:=isEmpty[ new[] ];
axiom2[ s_STACK, x_ ]:=!isEmpty[ push[ s, x ] ];
axiom3[ s_STACK, x_ ]:=(top[ push[ s,x ] ]==x);
axiom4[ s_STACK, x_ ]:=(drop[ push[ s,x ] ]==s);
allAxioms[ s_STACK, x_ ]:=(
axiom1[] && axiom2[ s,x ] && axiom3[ s,x ] && axiom4[ s,x ]);
-----------------------------------------------------------------
What's Next:
Showing implementations in Eiffel, then Java.
Then finally, Mathematica implementations.
(The above Mathematica code isn't an implementation,
as I don't show definitions for the 5 "functions of a stack".
The idea is that many different implementations should be possible.
But all a client should know, is what I have shown above.
Plus the "pre-conditions", that I haven't yet shown in Mathematica.
)
Since I am coming from an OO background, I may not be showing the most
"natural" Mathematica implementations. Though in this simple case (before
getting into "inheritance"), hopefully I will be close to the mark.
-- Steve S. Shaw (ToolmakerSteve)