(* Content-type: application/mathematica *)

(*** Wolfram Notebook File ***)
(* http://www.wolfram.com/nb *)

(* CreatedBy='Mathematica 7.0' *)

(*CacheID: 234*)
(* Internal cache information:
NotebookFileLineBreakTest
NotebookFileLineBreakTest
NotebookDataPosition[       145,          7]
NotebookDataLength[     13825,        466]
NotebookOptionsPosition[     11379,        377]
NotebookOutlinePosition[     11775,        394]
CellTagsIndexPosition[     11732,        391]
WindowFrame->Normal*)

(* Beginning of Notebook Content *)
Notebook[{

Cell[CellGroupData[{
Cell["Data Types", "Title",
 CellChangeTimes->{{3.500856049421875*^9, 3.50085605490625*^9}},
 TextAlignment->Center],

Cell["http://cis.k.hosei.ac.jp/~yukita", "Subsubtitle",
 CellChangeTimes->{{3.50085607659375*^9, 3.500856106390625*^9}},
 TextAlignment->Center],

Cell[BoxData[
 RowBox[{"Off", "[", 
  RowBox[{"General", "::", "spell1"}], "]"}]], "Input",
 CellChangeTimes->{{3.50085301*^9, 3.500853013828125*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"push", "[", 
   RowBox[{"{", 
    RowBox[{"x_", ",", "s_"}], "}"}], "]"}], ":=", "\[IndentingNewLine]", 
  RowBox[{"Prepend", "[", 
   RowBox[{"s", ",", "x"}], "]"}]}]], "Input",
 CellChangeTimes->{{3.5008517451875*^9, 3.50085174553125*^9}, {
   3.500851783859375*^9, 3.500851795546875*^9}, {3.50085183790625*^9, 
   3.5008518695*^9}, 3.50085294553125*^9, {3.50085576040625*^9, 
   3.500855763390625*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"pop", "[", "s_", "]"}], ":=", 
  RowBox[{"{", 
   RowBox[{
    RowBox[{"First", "[", "s", "]"}], ",", 
    RowBox[{"Rest", "[", "s", "]"}]}], "}"}]}]], "Input",
 CellChangeTimes->{{3.5008528416875*^9, 3.50085288396875*^9}, {
  3.50085311940625*^9, 3.50085312115625*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"stack", "=", 
  RowBox[{"push", "[", 
   RowBox[{"{", 
    RowBox[{"0", ",", 
     RowBox[{"{", "}"}]}], "}"}], "]"}]}]], "Input",
 CellChangeTimes->{{3.500852919640625*^9, 3.500852927046875*^9}, {
  3.500852968328125*^9, 3.50085297640625*^9}, {3.500855785328125*^9, 
  3.500855787765625*^9}}],

Cell[BoxData[
 RowBox[{"{", "0", "}"}]], "Output",
 CellChangeTimes->{{3.500852928203125*^9, 3.500852949484375*^9}, 
   3.500852979859375*^9, 3.500853128765625*^9, 3.500855788703125*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"stack", "=", 
  RowBox[{"push", "[", 
   RowBox[{"{", 
    RowBox[{"1", ",", "stack"}], "}"}], "]"}]}]], "Input",
 CellChangeTimes->{{3.50085296078125*^9, 3.500852961203125*^9}, {
  3.500853030609375*^9, 3.500853040859375*^9}, {3.50085579884375*^9, 
  3.50085580184375*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"1", ",", "0"}], "}"}]], "Output",
 CellChangeTimes->{3.500853042*^9, 3.5008531310625*^9, 3.500855802734375*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"stack", "=", 
  RowBox[{"push", "[", 
   RowBox[{"{", 
    RowBox[{"2", ",", "stack"}], "}"}], "]"}]}]], "Input",
 CellChangeTimes->{{3.500853066453125*^9, 3.500853079*^9}, {
  3.50085580596875*^9, 3.50085580840625*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"2", ",", "1", ",", "0"}], "}"}]], "Output",
 CellChangeTimes->{3.50085307971875*^9, 3.50085313378125*^9, 
  3.500855809109375*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{"val", ",", "stack"}], "}"}], "=", 
  RowBox[{"pop", "[", "stack", "]"}]}]], "Input",
 CellChangeTimes->{{3.50085308496875*^9, 3.500853101984375*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"2", ",", 
   RowBox[{"{", 
    RowBox[{"1", ",", "0"}], "}"}]}], "}"}]], "Output",
 CellChangeTimes->{3.500853107703125*^9, 3.50085314096875*^9, 
  3.5008558186875*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData["stack"], "Input",
 CellChangeTimes->{{3.5008531454375*^9, 3.500853146125*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"1", ",", "0"}], "}"}]], "Output",
 CellChangeTimes->{3.500853147234375*^9, 3.500855822109375*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{"val", ",", "stack"}], "}"}], "=", 
  RowBox[{"pop", "[", "stack", "]"}]}]], "Input",
 CellChangeTimes->{{3.50085315090625*^9, 3.5008531571875*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"1", ",", 
   RowBox[{"{", "0", "}"}]}], "}"}]], "Output",
 CellChangeTimes->{3.50085315771875*^9, 3.50085582803125*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{"val", ",", "stack"}], "}"}], "=", 
  RowBox[{"pop", "[", "stack", "]"}]}]], "Input",
 CellChangeTimes->{{3.50085316328125*^9, 3.500853171203125*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"0", ",", 
   RowBox[{"{", "}"}]}], "}"}]], "Output",
 CellChangeTimes->{3.500853171796875*^9, 3.5008558311875*^9}]
}, Open  ]],

Cell["In the next step, we expect the stack underflow error.", "Text",
 CellChangeTimes->{{3.500853194546875*^9, 3.500853220984375*^9}, {
  3.500853363484375*^9, 3.50085337775*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"{", 
   RowBox[{"val", ",", "stack"}], "}"}], "=", 
  RowBox[{"pop", "[", "stack", "]"}]}]], "Input",
 CellChangeTimes->{{3.500853178671875*^9, 3.500853185875*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"First", "::", "\<\"first\"\>"}], 
  RowBox[{
  ":", " "}], "\<\"\[NoBreak]\\!\\(\\*StyleBox[\\!\\({}\\), \\\"MT\\\"]\\)\
\[NoBreak]\\!\\(\\*StyleBox[\\\"\\\\\\\"\:306e\:9577\:3055\:306f\:30bc\:30ed\
\:3067\:6700\:521d\:306e\:8981\:7d20\:306f\:5b58\:5728\:3057\:307e\:305b\:3093\
\:ff0e\\\\\\\"\\\", \\\"MT\\\"]\\) \
\\!\\(\\*ButtonBox[\\\"\[RightSkeleton]\\\", ButtonStyle->\\\"Link\\\", \
ButtonFrame->None, ButtonData:>\\\"paclet:ref/message/First/first\\\", \
ButtonNote -> \\\"First::first\\\"]\\)\"\>"}]], "Message", "MSG",
 CellChangeTimes->{3.500853186765625*^9, 3.500855835*^9}],

Cell[BoxData[
 RowBox[{
  RowBox[{"Rest", "::", "\<\"norest\"\>"}], 
  RowBox[{
  ":", " "}], "\<\"\\!\\(\\*StyleBox[\\\"\\\\\\\"\:9577\:3055\:30bc\:30ed\
\:306e\:6b8b\:308a\:306e\:5f0f\\\\\\\"\\\", \
\\\"MT\\\"]\\)\[NoBreak]\\!\\(\\*StyleBox[\\!\\({}\\), \\\"MT\\\"]\\)\
\[NoBreak]\\!\\(\\*StyleBox[\\\"\\\\\\\"\:3092\:53d6\:308b\:3053\:3068\:304c\
\:3067\:304d\:307e\:305b\:3093\:ff0e\\\\\\\"\\\", \\\"MT\\\"]\\) \
\\!\\(\\*ButtonBox[\\\"\[RightSkeleton]\\\", ButtonStyle->\\\"Link\\\", \
ButtonFrame->None, ButtonData:>\\\"paclet:ref/message/Rest/norest\\\", \
ButtonNote -> \\\"Rest::norest\\\"]\\)\"\>"}]], "Message", "MSG",
 CellChangeTimes->{3.500853186765625*^9, 3.500855835015625*^9}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{
   RowBox[{"First", "[", 
    RowBox[{"{", "}"}], "]"}], ",", 
   RowBox[{"Rest", "[", 
    RowBox[{"{", "}"}], "]"}]}], "}"}]], "Output",
 CellChangeTimes->{3.500853186890625*^9, 3.50085583503125*^9}]
}, Open  ]],

Cell["To avoid this, we should refine our definition of stack.", "Text",
 CellChangeTimes->{{3.50085323515625*^9, 3.5008532644375*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{"pop", "[", "s_", "]"}], ":=", 
  RowBox[{"If", "[", 
   RowBox[{
    RowBox[{"s", "\[Equal]", 
     RowBox[{"{", "}"}]}], ",", "ast", ",", 
    RowBox[{"{", 
     RowBox[{
      RowBox[{"First", "[", "s", "]"}], ",", 
      RowBox[{"Rest", "[", "s", "]"}]}], "}"}]}], "]"}]}]], "Input",
 CellChangeTimes->{{3.5008534685625*^9, 3.500853526734375*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"stack", "=", 
  RowBox[{"Fold", "[", 
   RowBox[{
    RowBox[{
     RowBox[{"push", "[", 
      RowBox[{"{", 
       RowBox[{"#2", ",", "#1"}], "}"}], "]"}], "&"}], ",", 
    RowBox[{"{", "}"}], ",", 
    RowBox[{"Range", "[", "5", "]"}]}], "]"}]}]], "Input",
 CellChangeTimes->{{3.500853783390625*^9, 3.5008537926875*^9}, {
  3.500853860609375*^9, 3.500853908859375*^9}, {3.5008540215*^9, 
  3.500854032421875*^9}, {3.50085587728125*^9, 3.5008558810625*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"5", ",", "4", ",", "3", ",", "2", ",", "1"}], "}"}]], "Output",
 CellChangeTimes->{3.500853910859375*^9, 3.50085403296875*^9, 
  3.50085410075*^9, 3.500855883921875*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"stack", "=", 
  RowBox[{"Nest", "[", 
   RowBox[{
    RowBox[{
     RowBox[{"Part", "[", 
      RowBox[{
       RowBox[{"pop", "[", "#", "]"}], ",", "2"}], "]"}], "&"}], ",", "stack",
     ",", "5"}], "]"}]}]], "Input",
 CellChangeTimes->{{3.500853927875*^9, 3.500853999421875*^9}, {
  3.500854037421875*^9, 3.500854038375*^9}, {3.500854096484375*^9, 
  3.5008540980625*^9}}],

Cell[BoxData[
 RowBox[{"{", "}"}]], "Output",
 CellChangeTimes->{3.500854001640625*^9, 3.50085403915625*^9, 
  3.500854103328125*^9, 3.500855908*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{"pop", "[", "stack", "]"}]], "Input",
 CellChangeTimes->{{3.500854106640625*^9, 3.500854109515625*^9}}],

Cell[BoxData["ast"], "Output",
 CellChangeTimes->{3.500854110203125*^9, 3.500855911796875*^9}]
}, Open  ]],

Cell["For symmetry, we supplement the previous definition with.", "Text",
 CellChangeTimes->{{3.500855219296875*^9, 3.50085524453125*^9}, {
  3.500855356265625*^9, 3.50085537946875*^9}}],

Cell[BoxData[
 RowBox[{
  RowBox[{
   RowBox[{"push", "[", "ast", "]"}], "=", 
   RowBox[{"{", "}"}]}], ";"}]], "Input",
 CellChangeTimes->{{3.50085525625*^9, 3.50085527021875*^9}, {
  3.500855325578125*^9, 3.500855350015625*^9}}],

Cell["Let us check Axiom 1 and 2 in the presentation slide.", "Text",
 CellChangeTimes->{{3.500854217265625*^9, 3.500854235609375*^9}}],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"Composition", "[", 
   RowBox[{"pop", ",", "push"}], "]"}], "[", "ast", "]"}]], "Input",
 CellChangeTimes->{{3.500855162640625*^9, 3.500855195875*^9}, {
   3.500855421359375*^9, 3.5008554225*^9}, 3.500855484640625*^9}],

Cell[BoxData["ast"], "Output",
 CellChangeTimes->{3.500855423078125*^9, 3.50085548565625*^9, 
  3.500855926140625*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"Composition", "[", 
   RowBox[{"pop", ",", "push"}], "]"}], "[", 
  RowBox[{"{", 
   RowBox[{"100", ",", 
    RowBox[{"Range", "[", "10", "]"}]}], "}"}], "]"}]], "Input",
 CellChangeTimes->{{3.500855519109375*^9, 3.500855542234375*^9}, {
  3.50085557728125*^9, 3.50085559309375*^9}, {3.500855946765625*^9, 
  3.500855949828125*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{"100", ",", 
   RowBox[{"{", 
    RowBox[{
    "1", ",", "2", ",", "3", ",", "4", ",", "5", ",", "6", ",", "7", ",", "8",
      ",", "9", ",", "10"}], "}"}]}], "}"}]], "Output",
 CellChangeTimes->{
  3.500855543296875*^9, 3.5008556024375*^9, {3.50085593575*^9, 
   3.5008559508125*^9}}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"Composition", "[", 
   RowBox[{"push", ",", "pop"}], "]"}], "[", 
  RowBox[{"Range", "[", "10", "]"}], "]"}]], "Input",
 CellChangeTimes->{{3.50085565428125*^9, 3.500855697953125*^9}}],

Cell[BoxData[
 RowBox[{"{", 
  RowBox[{
  "1", ",", "2", ",", "3", ",", "4", ",", "5", ",", "6", ",", "7", ",", "8", 
   ",", "9", ",", "10"}], "}"}]], "Output",
 CellChangeTimes->{{3.500855683046875*^9, 3.50085569928125*^9}, 
   3.5008559648125*^9}]
}, Open  ]],

Cell[CellGroupData[{

Cell[BoxData[
 RowBox[{
  RowBox[{"Composition", "[", 
   RowBox[{"push", ",", "pop"}], "]"}], "[", 
  RowBox[{"{", "}"}], "]"}]], "Input",
 CellChangeTimes->{{3.50085598946875*^9, 3.50085601184375*^9}}],

Cell[BoxData[
 RowBox[{"{", "}"}]], "Output",
 CellChangeTimes->{3.500856012453125*^9}]
}, Open  ]]
}, Open  ]]
},
ScreenStyleEnvironment->"Presentation",
WindowSize->{615, 750},
WindowMargins->{{202, Automatic}, {Automatic, 17}},
FrontEndVersion->"7.0 for Microsoft Windows (32-bit) (2009\:5e744\:670823\
\:65e5)",
StyleDefinitions->"Default.nb"
]
(* End of Notebook Content *)

(* Internal cache information *)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[567, 22, 116, 2, 144, "Title"],
Cell[686, 26, 144, 2, 51, "Subsubtitle"],
Cell[833, 30, 150, 3, 50, "Input"],
Cell[986, 35, 440, 10, 85, "Input"],
Cell[1429, 47, 305, 8, 50, "Input"],
Cell[CellGroupData[{
Cell[1759, 59, 317, 8, 50, "Input"],
Cell[2079, 69, 186, 3, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[2302, 77, 298, 7, 50, "Input"],
Cell[2603, 86, 151, 3, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[2791, 94, 244, 6, 50, "Input"],
Cell[3038, 102, 170, 4, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[3245, 111, 201, 5, 50, "Input"],
Cell[3449, 118, 208, 6, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[3694, 129, 92, 1, 50, "Input"],
Cell[3789, 132, 137, 3, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[3963, 140, 199, 5, 50, "Input"],
Cell[4165, 147, 159, 4, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[4361, 156, 201, 5, 50, "Input"],
Cell[4565, 163, 154, 4, 73, "Output"]
}, Open  ]],
Cell[4734, 170, 181, 2, 47, "Text"],
Cell[CellGroupData[{
Cell[4940, 176, 199, 5, 50, "Input"],
Cell[5142, 183, 621, 11, 38, "Message"],
Cell[5766, 196, 693, 12, 38, "Message"],
Cell[6462, 210, 241, 7, 73, "Output"]
}, Open  ]],
Cell[6718, 220, 135, 1, 79, "Text"],
Cell[6856, 223, 385, 11, 85, "Input"],
Cell[CellGroupData[{
Cell[7266, 238, 483, 12, 85, "Input"],
Cell[7752, 252, 209, 4, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[7998, 261, 399, 11, 85, "Input"],
Cell[8400, 274, 149, 3, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[8586, 282, 126, 2, 50, "Input"],
Cell[8715, 286, 94, 1, 73, "Output"]
}, Open  ]],
Cell[8824, 290, 186, 2, 79, "Text"],
Cell[9013, 294, 230, 6, 50, "Input"],
Cell[9246, 302, 135, 1, 47, "Text"],
Cell[CellGroupData[{
Cell[9406, 307, 253, 5, 50, "Input"],
Cell[9662, 314, 118, 2, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[9817, 321, 367, 9, 85, "Input"],
Cell[10187, 332, 325, 9, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[10549, 346, 219, 5, 50, "Input"],
Cell[10771, 353, 250, 6, 73, "Output"]
}, Open  ]],
Cell[CellGroupData[{
Cell[11058, 364, 203, 5, 50, "Input"],
Cell[11264, 371, 87, 2, 73, "Output"]
}, Open  ]]
}, Open  ]]
}
]
*)

(* End of internal cache information *)