Re: OOP experiments in Mathematica- The Stack
- To: mathgroup at smc.vnet.net
- Subject: [mg38659] Re: OOP experiments in Mathematica- The Stack
- From: "Steve S. Shaw" <steve at shawstudio.com>
- Date: Fri, 3 Jan 2003 00:16:44 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
A series of OOP experiments in Mathematica.
msg#2 - The Stack, part#4: two simple Mathematica implementations of a
stack.
Finally :-)
This message contains a "Notebook" expression.
Select all the text after the "------" lines of dashes,
then copy / paste that into a Mathematica notebook.
The result should be my original notebook, complete with output.
The NEXT message (part#5) has a plain-text version of the input lines,
for your perusal, if Mathematica is not handy.
Important features of the Mathematica code:
1. TWO different implementations are shown.
One appends to the end of a list, the other prepends to the start of a list.
The same tests are run with each, to show that the results are identical.
2. Mathematica's symbolic nature allows "result1" to be shown as an
expression containing "top"s, "push"s, etc.
Perhaps some mathematician can tell me how to use the axioms shown to
"reduce" this expression,
without any "implementation" of the functions themselves.
The axioms should reduce result1 to "x4".
3. Note the deliberate "errors", and how they spit out Error messages via my
definition of "assert".
Presumably, this should instead be using an "Exception" mechanism.
If Mathematica has such a mechanism.
As it stands, I let the Mathematica code keep running, so each error message
is followed by the Kernel's complaint and output.
4. No "inheritance" is required by this example. Hence I simply used a head
"STACK" to identify a stack.
This will not be a sufficient solution for examples after this one.
5. This mimics an OOP solution to implementing a stack.
(Minus the lack of inheritance.)
Therefore, it is a PROCEDURAL (or STATE-FUL) implementation,
not a PURE FUNCTIONAL (or side-effect-free) implementation.
That is, the functions manipulate the state of an object - the list
representing a stack.
No doubt Mathematica could do some elegant pure functional implementation of
this specification.
Anyone want to take a stab at doing such?
As I understand it, this would mean that instead of modifying the existing
list, a new list would be constructed at each step. But wouldn't that be
horribly inefficient for large problems?
-----------------------------------------------------------------
Notebook[{
Cell[BoxData[
\(\(\( (*\
Quiet\ the\ warnings\ about\ similarly\ spelled\ \
\(\(variables\)\(.\)\)\ *) \)\(\n\)\(Off[General::spell]; \ \ \ Off[
General::spell1];\)\)\)], "Input"],
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\ AXIOMS\) - \
True\ for\ all\ stacks . \ \
--*) \)\(\[IndentingNewLine]\)\(\(axiom1[] :=
empty[\ new[]\ ];\)\[IndentingNewLine]
\(axiom2[\ s_STACK, \
x_\ ] := \(! empty[\
push[\ s, \ x\ ]\ ]\);\)\[IndentingNewLine]
\(axiom3[\ s_STACK, \
x_\ ] := \((top[\ push[\ s, x\ ]\ ] ==
x)\);\)\[IndentingNewLine]
\(axiom4[\ s_STACK, \
x_\ ] := \((drop[\ push[\ s, x\ ]\ ] ==
s)\);\)\[IndentingNewLine]
\(allAxioms[\ s_STACK, \
x_\ ] := \((\[IndentingNewLine]axiom1[]\ && \
axiom2[\ s, x\ ]\ && \
axiom3[\ s, x\ ]\ && \ \ axiom4[\ s,
x\ ])\);\)\)\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\
an\)\ example\ of\ stack\ \(usage\ --\)*) \)\(\
\[IndentingNewLine]\)\(\(s1 = new[];\)\[IndentingNewLine]
\(s2 =
push[\ push[\ push[\ s1, x1\ ], x2],
x3\ ];\)\[IndentingNewLine]
\(s3 = drop[\ s2\ ];\)\[IndentingNewLine]
\(s4 = new[];\)\[IndentingNewLine]
\(s5 = push[\ push[\ s4, x4\ ], x5\ ];\)\[IndentingNewLine]
\(s6 = drop[\ s5\ ];\)\[IndentingNewLine]
\(v1 = top[\ s6\ ];\)\[IndentingNewLine]
\(s7 = push[\ s3, v1\ ];\)\[IndentingNewLine]
\(s8 = push[\ s7, x6\ ];\)\[IndentingNewLine]
\(s9 = drop[\ s8\ ];\)\[IndentingNewLine]
\(s10 = push[\ s9, x7\ ];\)\[IndentingNewLine]
\(s11 = drop[\ s10\ ];\)\[IndentingNewLine]
\(result1 = top[\ s11\ ];\)\[IndentingNewLine]
result1\[IndentingNewLine] (*\
MUST\ BE\ TRUE\ for\ any\ implementation\ of\ STACK\ \
*) \[IndentingNewLine]
\(stackVerify = \((result1 \[Equal] x4)\);\)\)\)\)], "Input"],
Cell[BoxData[
\(top[
drop[push[
drop[push[
push[drop[push[push[push[new[], x1], x2], x3]],
top[drop[push[push[new[], x4], x5]]]], x6]],
x7]]]\)], "Output"]
}, Open ]],
Cell[BoxData[
\(\(\( (*\
TBD\ - \
throw\ exception?\[IndentingNewLine]Unless\ "\<test\>"\ is\ \
True, \ report\ \(\(error\)\(.\)\)\[IndentingNewLine]*) \)\(\
\[IndentingNewLine]\)\(assert[\ test_, message_\ ] :=
If[\ \(! TrueQ[\
test\ ]\), \[IndentingNewLine]"\<***Error: \>" <>
ToString[\ message\ ] // Print\ ];\)\)\)], "Input"],
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\ "\<Prepend\>"\)\ Implementation\ of\ \
\(Stack\ --\)*) \)\(\[IndentingNewLine]\)\(\(Clear[\ empty, \ top, \
new, \ push, \
drop\ ];\)\[IndentingNewLine] (*\(--\ \(Queries\ --\)\)\
*) \[IndentingNewLine]
\(empty[\
s_STACK\ ] := \((Length[\ s\ ] \[Equal]
0)\);\)\[IndentingNewLine]
\(top[\
s_STACK\ ] := \((\[IndentingNewLine]assert[\ \(! empty[\
s\ ]\), "\<stack.top- empty\>"\ ]; \
\[IndentingNewLine]First[\
s\ ]\[IndentingNewLine])\);\)\[IndentingNewLine] (*\(--\ \
\(Changes\ --\)\)*) \[IndentingNewLine]
\(new[] := STACK[];\)\[IndentingNewLine]
\(push[\ s_STACK, x_\ ] :=
Prepend[\ s, x\ ];\)\[IndentingNewLine]
\(drop[\
s_STACK\ ] := \((\[IndentingNewLine]assert[\ \(! empty[\
s\ ]\), "\<stack.drop- empty\>"\ ]; \
\[IndentingNewLine]Drop[\ s,
1\ ]\[IndentingNewLine])\);\)\)\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(s1\), "\[IndentingNewLine]",
\(s2\), "\[IndentingNewLine]",
\(result1\), "\[IndentingNewLine]",
\(\(assert[\
stackVerify, "\<Bad Stack Implementation\>"\ ];\)\), "\
\[IndentingNewLine]",
\(allAxioms[\ new[], \ xx\ ]\), "\[IndentingNewLine]",
\(allAxioms[\ s1, \ xx\ ]\), "\[IndentingNewLine]",
\(allAxioms[\ s11, \ xx\ ]\)}], "Input"],
Cell[BoxData[
\(STACK[]\)], "Output"],
Cell[BoxData[
\(STACK[x3, x2, x1]\)], "Output"],
Cell[BoxData[
\(x4\)], "Output"],
Cell[BoxData[
\(True\)], "Output"],
Cell[BoxData[
\(True\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(\(\( (*\
Deliberate\ errors\ *) \)\(\[IndentingNewLine]\)\(top[\
s1\ ]\[IndentingNewLine]
drop[\ s1\ ]\)\)\)], "Input"],
Cell[BoxData[
\("***Error: stack.top- empty"\)], "Print"],
Cell[BoxData[
\(First::"first" \(\(:\)\(\ \)\)
"\!\(STACK[]\) has a length of zero and no first element."\)], \
"Message"],
Cell[BoxData[
\(First[STACK[]]\)], "Output"],
Cell[BoxData[
\("***Error: stack.drop- empty"\)], "Print"],
Cell[BoxData[
\(Drop::"drop" \(\(:\)\(\ \)\)
"Cannot drop positions \!\(1\) through \!\(1\) in \
\!\(STACK[]\)."\)], "Message"],
Cell[BoxData[
\(Drop[STACK[], 1]\)], "Output"]
}, Open ]],
Cell[BoxData[
\(\(\( (*\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\(===\)\
\(===\)\(===\)\(===\)\(===\)\(===\)\(\[Equal]\)*) \)\(\
\[IndentingNewLine]\)\( (*\(--\ "\<Append\>"\)\ Implementation\ of\ \
\(Stack\ --\)*) \)\(\[IndentingNewLine]\)\(\(Clear[\ empty, \ top, \
new, \ push, \
drop\ ];\)\[IndentingNewLine] (*\(--\ \(Queries\ --\)\)\
*) \[IndentingNewLine]
\(empty[\
s_STACK\ ] := \((Length[\ s\ ] \[Equal]
0)\);\)\[IndentingNewLine]
\(top[\
s_STACK\ ] := \((\[IndentingNewLine]assert[\ \(! empty[\
s\ ]\), "\<stack.top- empty\>"\ ]; \
\[IndentingNewLine]Last[\
s\ ]\[IndentingNewLine])\);\)\[IndentingNewLine] (*\(--\ \
\(Changes\ --\)\)*) \[IndentingNewLine]
\(new[] := STACK[];\)\[IndentingNewLine]
\(push[\ s_STACK, x_\ ] := Append[\ s, x\ ];\)\[IndentingNewLine]
\(drop[\
s_STACK\ ] := \((\[IndentingNewLine]assert[\ \(! empty[\
s\ ]\), "\<stack.drop- empty\>"\ ]; \
\[IndentingNewLine]Drop[\
s, \(-1\)\ ]\[IndentingNewLine])\);\)\)\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(s1\), "\[IndentingNewLine]",
\(s2\), "\[IndentingNewLine]",
\(result1\), "\[IndentingNewLine]",
\(\(assert[\
stackVerify, "\<Bad Stack Implementation\>"\ ];\)\), "\
\[IndentingNewLine]",
\(allAxioms[\ new[], \ xx\ ]\), "\[IndentingNewLine]",
\(allAxioms[\ s1, \ xx\ ]\), "\[IndentingNewLine]",
\(allAxioms[\ s11, \ xx\ ]\)}], "Input"],
Cell[BoxData[
\(STACK[]\)], "Output"],
Cell[BoxData[
\(STACK[x1, x2, x3]\)], "Output"],
Cell[BoxData[
\(x4\)], "Output"],
Cell[BoxData[
\(True\)], "Output"],
Cell[BoxData[
\(True\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(\(\( (*\
Deliberate\ errors\ *) \)\(\[IndentingNewLine]\)\(top[\
s1\ ]\[IndentingNewLine]
drop[\ s1\ ]\)\)\)], "Input"],
Cell[BoxData[
\("***Error: stack.top- empty"\)], "Print"],
Cell[BoxData[
\(Last::"nolast" \(\(:\)\(\ \)\)
"\!\(STACK[]\) has a length of zero and no last element."\)], \
"Message"],
Cell[BoxData[
\(Last[STACK[]]\)], "Output"],
Cell[BoxData[
\("***Error: stack.drop- empty"\)], "Print"],
Cell[BoxData[
\(Drop::"drop" \(\(:\)\(\ \)\)
"Cannot drop positions \!\(-1\) through \!\(-1\) in \!\(STACK[]\
\)."\)], "Message"],
Cell[BoxData[
\(Drop[STACK[], \(-1\)]\)], "Output"]
}, Open ]]
},
FrontEndVersion->"4.2 for Microsoft Windows",
ScreenRectangle->{{0, 1280}, {0, 979}},
WindowSize->{550, 740},
WindowMargins->{{13, Automatic}, {Automatic, 6}}
]