% Nb: This file must be passed through cweave before LaTeX-ing.
%    cweave +j Universal.w
%    latex Universal
% To create the Universal Java class:
%    ctangle +j Universal.w

\documentclass[12pt,a4paper]{cweb}
% \usepackage[hypertex]{hyperref}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{mathrsfs}
\usepackage{moreverb}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{program}{Program}

\usepackage{drop}
\font\largefont=yinitas

\addtolength{\textheight}{20mm}
\addtolength{\topmargin}{-10mm}

\newtheorem{definition}{Definition}
\newcommand{\norm}[1]{\Vert #1 \Vert}
\newcommand{\code}[1]{\langle #1 \rangle}
\newcommand{\Code}[1]{[#1]}
\newcommand{\vv}{|}
\def\Rule #1,#2,#3,#4{(#1,#2)(#3,#4)}

\def\defin{define} % As in webmac.tex
\def\C{\textsc{C}}
\def\Java{\textsc{Java}}
\def\D{\defin{define}} % macro definition

\newcommand{\BB}{\mathbb{B}}
\renewcommand{\S}{\mathbb{S}}

%\newcommand{\TL}{\mathscr{T}}
%\newcommand{\SL}{\mathscr{S}}
\newcommand{\TL}{\mathcal{T}}
\newcommand{\SL}{\mathcal{S}}

\newcommand{\action}{\operatorname{action}}
\newcommand{\transition}{\operatorname{transition}}

\newenvironment{preamble}{\begin{center}\begin{tabular}{|p{0.8\textwidth}|}%
\hline\\[-5pt]}%
{\\[3pt]\hline\end{tabular}\end{center}}

\catcode`\"=\active
\def"#1"{\ifmmode\mathtt{#1}\else\texttt{#1}\fi}

\def\CwebRankNoEject{1}

\title{A 2--stack machine for multiplying natural numbers}

\author{Timothy Murphy\\
\texttt{<tim@@maths.tcd.ie>}\\
School of Mathematics, Trinity College Dublin}

\date{\today}

\begin{document}

\maketitle

\tableofcontents

\begin{preamble}
\drop{W}{{\scshape e define}} a 2-stack machine
which implements the function
\[
\Code{m}\Code{n} \mapsto \Code{mn},
\]
where $\Code{m} = 1^m0$.
Our construction is expressed as a program
in the tiny language $\mathcal{S}$,
which we use for defining stack machines.
\end{preamble}

\newpage

@* Strategy.

We start by reading in the first number $m$
and storing it (as $01^m$) on the main stack (stack 0).

Then we enter the `main loop',
in which we read in the second number $n$ bit-by-bit.
As we read in each 1, we run through the main stack,
writing out $m$ 1's,
at the same time storing these 1's on the auxiliary stack (stack 1).
Then when the main stack is exhausted, 
we `rewind' $m$ from the auxiliary stack to the main stack,
and return to the main loop.

@(Multiplication.S@>=
@<Read first number onto main stack@>@;
Loop: @<Read in bit of second number;
    if it is 0, write it out and halt@>@;
  @<Pop 1's from main stack, write them 
    and push them onto auxiliary stack@>@;
  @<Rewind auxiliary stack onto main stack,
    and jumpto Loop@>@;

@* Reading first number onto main stack.

We start by pushing 0 onto stack 0,
to mark the bottom of the stack.
Then we read successive bits,
pushing them onto stack 0 as long as they are 1's.
When we meet a 0 we push it onto stack 1,
to mark the bottom of that stack,
and move on to the main loop.

At the end of this phase
stack 0 holds $01^m$ and stack 1 holds $0$.

@<Read first number ...@>=
put0;@+ push0;
read;@+ push0;@+ jump-2;
pop0;@+ push1;

@* Starting the cycle.

We read in a bit from the second number.

If it is 0 then we are done;
we write out 0 and halt.

If it is 1 then we enter the main cycle.

@<Read in bit ...@>=
read;@+ jump3;@+ write;@+ halt;

@* The main cycle.

We go through the $m$ 1's on stack 0,
writing out a 1 for each 1,
and also pushing a 1 onto stack 1.

When we meet a 0 (at the bottom of stack 0)
we push it onto stack 1 to mark the bottom of that stack.

@<Pop 1's ...@>=
pop0;@+ jump4;
push0;@+ put1;@+ jump4;
push1;@+ write;@+ jump-7;

@* Rewinding.

Next we `rewind' stack 1 onto stack 0.

@<Rewind ...@>=
pop1;@+ jump4;
push1;@+ put1;@+ jumpto Loop;
push0;@+ jump-6;

@* The whole program.

\verbatiminput{Multiplication.java}

@* Appendix: Literate programming.

This little program was written in "cweb",
Donald Knuth's implementation of his concept
of `literate programming'.

In brief, documentation and program
are combined in a single `web' file.
This can then be processed in two ways:
by "ctangle" to produce the program,
or by "cweave" to produce the documentation.

This document is based on the web file "Multiplication.w".
The actual program (in the language $\mathcal{S}$)
is produced by
\begin{verbatim}
    % ctangle Multiplication.w
\end{verbatim}

On the other hand, this document was produced by
\begin{verbatim}
    % cweave Multiplication.w
\end{verbatim}
producing the \LaTeX\ file |TuringMachine.tex| which can be processed 
in the usual way
\begin{verbatim}
    % latex Multiplication
    % xdvi Multiplication
    % dvips Multiplication
\end{verbatim}


\end{document}