%% $Id: FRS-exam.tex,v 1.6 1995/10/03 15:42:28 kris Exp $
%% Exam for FRS course.

\documentclass[a4paper,oneside,12pt]{article}

\usepackage{amsmath}
\usepackage[all]{xy}
\usepackage{qsymbols}

\def\MYNAME{Kristoffer H. Rose}

\title{Fundamental Reduction Systems\\Examination}
\author{Teacher: \MYNAME}
\date{Tuesday, December 13, 1994, 14$^{\textup{00}}$--16$^{\textup{00}}$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Q&A...

\newtheorem{Q}{\llap{$\blacktriangleright$\quad}Question}

\newtheorem{Def}{Definition}

\makeatletter

\begingroup \catcode`\|=0 \catcode`\<=1 \catcode`\>=2
 |catcode`|\=12 |gdef|otherescape<\>
 |catcode`|%=12 |gdef|othercomment<%>|endgroup

\count@=\time \divide\count@ by 60\relax
\count@@=\count@ \multiply\count@@ by -60 \advance\count@@ by \time
\edef\now{\number\count@:\ifnum 10>\count@@ 0\fi \number\count@@}

\newwrite\answ@
\immediate\openout\answ@=\jobname.ans
\def\IW@#1{\immediate\write\answ@{#1}}
\IW@{\othercomment\space\jobname.ans: \today, \now.}

\def\A#1{%
  \IW@{\otherescape paragraph*{\string\llap{$`(:-)$\quad}Answer to Question
      \@currentlabel:}}%
  \IW@{\othercomment}
  {\DN@{#1}\DNii@##1:->##2<:{{\IW@{##2}}}\expandafter\nextii@\meaning\next@<:}%
  \IW@{}}

\def\Answers{\clearpage \immediate\closeout\answ@
  {\footnotesize \input\jobname.ans }}

\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Logic circuits!

\newcommand{\circuit}[2][]{\vcenter{\def\next{#1}%
  \if\notempty{#1}\def\next{\xycompileto{#1}}\else\def\next{\xycompile}\fi
  \expandafter\xy\next{\xygraph{~{<2pc,0pc>:}#2}}\endxy}}

\newgraphescape{n}#1#2{[]!{+0="#2"*=<10pt>{};p!#1**{},"#2"
    -/4pt/*!E\cir<2pt>{}
    .{-/12pt/*=<24pt>{}*\frm{}="X@@" !E+/^7pt/="#2a", "X@@"!E+/_7pt/="#2b",
      "X@@"*\cirhalf{#1},
      "X@@"-/^12pt/;p-/12pt/**\dir{-};p+/_24pt/**\dir{-};p+/_12pt/**\dir{-},
      "X@@"}}}

\newgraphescape{i}#1#2{[]!{+0="#2"*=<10pt>{};p!#1**{},"#2"
    -/4pt/*!E\cir<2pt>{}
    +0;p-/:a(-30)24pt/**\dir{-}="X2"
    ;p-/:a(-60)24pt/="X1"**\dir{-};?(.5),="#2a",p-/:a(-60)24pt/**\dir{-},
    "#2"."#2a"."X1"."X2"}}

\newgraphescape{a}#1#2{[]!{+0="#2"*=<10pt>{};p!#1**{},"#2"
    .{-/12pt/*=<24pt>{}*\frm{}="X@@" !E+/^7pt/="#2a", "X@@"!E+/_7pt/="#2b",
      "X@@"*\cirhalf{#1},
      "X@@"-/^12pt/;p-/12pt/**\dir{-};p+/_24pt/**\dir{-};p+/_12pt/**\dir{-},
      "X@@"}}}

\newgraphescape{b}#1{[]!{*[o]{\notingraph`(#1)}}="#1"}

\makeatletter
\let\notingraph=\ingraph@false
\def\cirhalf#1{\csname cirhalf@#1\endcsname}
\def\cirhalf@R{\cir{r_l}}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Misc.

\newqsymbol{`*}{\mathbin{\pmb\bindnasrepma}}
\newqsymbol{`+}{\mathop{\bullet}}
\mathcode`\*="2202

\newcommand\bl{\dir{*}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle

\noindent The questions of this exam investigate the properties of some
actual term rewrite systems meant to be useful in electronics. There
are~\ref{lastQ} questions (marked with a~$\blacktriangleright$ in the left
margin) on~\pageref{end} pages.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip\noindent%
It is possible to model ´{electronic circuits} with reduction systems.  In
such a circuit, a number of logic-valued inputs are passed into a number of
interconnected logic `gates' that combine them in various ways to form some
logic-valued outputs.  We will denote logic values as $1$ and $0$ (for `true'
and `false'), and will only consider one kind of logic gate, namely $`*$ (for
`inverted and'), usually called `nand' and depicted
\begin{equation}
  \circuit[nand]{ []!nR1("1a"([l]x-?), "1b"([l]y-?)) - [r]z }
  \qquad
  \textup{with truth table}
  \qquad{\small
    \begin{array}[c]{|cc|c|}
      \hline x & y & z \\ \hline
      0 & 0 & 1 \\[-2pt]
      0 & 1 & 1 \\[-2pt]
      1 & 0 & 1 \\[-2pt]
      1 & 1 & 0 \\ \hline      
    \end{array}}\quad\hbox{(nand)}\label{nand}
\end{equation}
implementing the logic function $z = {x`*y} \stackrel{\textup{def}}{=}
{`!(x`^y)}$.

\begin{Def}\label{Nand}%
  The term rewrite system ´{Nand} is intended to model the function of all
  possible nand-gate circuits with a single ouput.  The terms are
  \begin{equation}
    t ~::=~ t`*t ~\mid~ 1 ~\mid~ 0	\label{nand-t}
  \end{equation}
  and the rules
  \begin{align}
    1`*1 &"->" 0			\label{nand-11}\\
    0`*x &"->" 1			\label{nand-0x}\\
    x`*0 &"->" 1			\label{nand-x0}
  \end{align}
\end{Def}

\begin{Q}\label{nand-nf}
  What are the normal forms?  \A{$0$ and $1$.}
\end{Q}

\begin{Q}\label{nand-inverter}\label{nand-and}
  Nand-gates can be used to model several other gates.  Verify by reduction
  in the ´{Nand} system that each of the circuits given below in the left
  column behaves as the gate pictured in the middle with truth table to the
  right:
  \begin{alignat}2
    \circuit[inv]{ !nR1 ( "1a"([ll]x-?) , "1b"([l]1-?) ) - [r]z }
    &`= \circuit[nand-inv]{ []!iR1("1a"([l]x-?)) - [r]z }
    &\quad&\hbox{\small$
      \begin{array}[c]{|c|c|}
        \hline x & z \\ \hline
        0 & 1 \\[-2pt]
        1 & 0 \\ \hline
      \end{array}$}\quad\hbox{(inverter)} \label{inverter}
    \\
    \notag\\
    \circuit[and]{ !iR2("2a"([l]!nR1 ("1a"([l]x-?), "1b"([l]y-?)) - ?)) - [r]z}
    &`= \circuit[nand-and]{ !aR1("1a"([l]x-?), "1b"([l]y-?)) - [r]z}
    &&\hbox{\small$
      \begin{array}[c]{|cc|c|}
        \hline x & y & z \\ \hline
        0 & 0 & 0 \\[-2pt]
        0 & 1 & 0 \\[-2pt]
        1 & 0 & 0 \\[-2pt]
        1 & 1 & 1 \\ \hline
      \end{array}$}\quad\hbox{(and)}\label{and}
  \end{alignat}
  \A{This one is the easy one: The inverter circuit~\eqref{nand-inverter}
    corresponds to the term $x`*1$ which clearly reduces to $`!x$ in a single
    step. The and circuit~\eqref{nand-and} corresponds to the term
    $(x`*y)`*1$ which reduces to $x`^y$ in two reductions for each possible
    $x$ and $y$.}
\end{Q}

\begin{Q}\label{nand-bounded}
  Show that ´{Nand} is bounded.  \A{The easiest method is based on the
    insight that each reduction eliminates a gate, and that all gates where
    the inputs are $0$ or $1$ can be reduced by one of the rules.  Thus in
    the worst case the number of reductions is equal to the number of gates,
    \textit{i.e.}, $`L(x) = \#\textup{gates}(x)$.}
\end{Q}

\begin{Q}\label{nand-complete}
  Show that ´{Nand} is complete (\textit{i.e.}, noetherian (SN) and confluent
  (CR)).  \A{´{Nand} is obviously SN since it is bounded.  It is easy to show
    it LC by observing that the only critical pair reduces as ${0`*0} "->" 1$
    with both \eqref{nand-0x} and \eqref{nand-x0}.}
\end{Q}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

When building real circuits it is possible to connect a wire to more than one
input and this is not captured by ´{Nand}.  We will repair this by adding
`branching wire' components like
\begin{displaymath}
  \circuit{~{(0,.5)::}
    []-[r]!bA -[r]*=0{`+} ( -[uu]-[r], -[u]*=0{`+}-[r], -[d]*=0{`+}-[r],
                            -[dd]-[r]) [r]*!/d3pt/{\vdots} }
\end{displaymath}
where crossing wires are connected when marked with $`+$.  We will only
consider combinatoric circuits (without feed-back, \textit{i.e.}, loops).
Note that any such circuit corresponds to a ´{Nand}-circuit (without
branching) by making a copy of the subcircuit generating the branched signal
for each wire it is connected to.

\begin{Def}\label{NandC}%
  The term rewrite system ´{NandC} is intended to model all combinatoric
  nand-gate circuits with a single ouput.  The terms are as ´{Nand} with the
  addition of
  \begin{equation}
    t ~::=~ `(a)(t,t) ~\mid~ a\label{nandc-t}
  \end{equation}
  where $a,b$ range over special `branch constants' $A,B,\dots$ of which we
  use as many as needed for each circuit, with the new rules
  \begin{align}
    `(a)(u,x`*y) &"->" `(a)(u,x)~`*~`(a)(u,y) \label{nandc-*}\\
    `(a)(x,a) &"->" x \label{nandc-aa}\\
    `(a)(x,b) &"->" b \qquad \textup{if}~a\not=b \label{nandc-ab}\\
    `(a)(x,0) &"->" 0 \label{nandc-a0}\\
    `(a)(x,1) &"->" 1 \label{nandc-a1}
  \end{align}
  The new term $`(a)(x,y)$ should be read `the output of $x$ is available as
  input $a$ in~$y$'.
\end{Def}

\begin{Q}\label{nandc-nf}
  What are the normal forms and what do they mean in circuit concepts?
  \A{$0$ and $1$, as before.  All the possible branch letters $A,B,\dots$
    corresponding to undefined branches.  $1`*x$ and $x`*1$ when $x$ is a
    normal form different from $0$ and $1$ corresponding to a gate that is
    not stable because it depends on an undefined branch.}
\end{Q}

\begin{Q}\label{nandc-xor}
  Write the ´{NandC}-term corresponding to the following circuit below to the
  left and verify that it implements the `exclusive or' function with truth
  table to the right:
  \begin{equation}
    \circuit[xor]{
      []x - [rr]!bA
      "x"[d]y - [r]!bB
      "x"[d(2)r(6)]!nR1 ( "1a"[l!{"A";p+D}]*=0{`+} ([rr]!iR{1I}-"1a",?-"1Ia")
                          "1b"[l!{"B";p+D}]*=0{`+} - "1b" )
      "x"[d(4)r(6)]!nR2 ( "A"-[d!{"2a";p+/r/}] - "2a" ,
                          "B"-[d!{"2b";p+/r/}] ([rrr]!iR{2I}-"2b", ?-"2Ia") )
      "x"[d(3)r(8)]!nR3 ( "1"-[r</1ex/]-[d!{"3a";p+/r/}]-"3a" ,
                          "2"-[r</1ex/]-[u!{"3b";p+/r/}]-"3b" ) - [r]z }
    \qquad\hbox{\small$
      \begin{array}[c]{|cc|c|}
        \hline x & y & z \\ \hline
        0 & 0 & 0 \\[-2pt]
        0 & 1 & 1 \\[-2pt]
        1 & 0 & 1 \\[-2pt]
        1 & 1 & 0 \\ \hline
      \end{array}$}\quad\hbox{(xor)}\label{xor}
  \end{equation}
  \A{The circuit can be represented by the following term where we use $¯x$
    as an abbreviation for $x`*1$: $`+(A)(x,`(B)(y,(¯A`*B)`*(A`*¯B)))$ which
    reduces (using only the new ´{NandC}-specific reductions) to
    $(¯x`*y)`*(x`*¯y)$ for any logic values of $x$ and $y$.  It is easy to
    verify that this term satisfies the xor truth table.}
\end{Q}

\begin{Q}\label{nandc-bounded}
  Show that ´{NandC} is SN.  \A{The easiest way is by simplification ordering
    (using Kruskal's tree theorem as described on p.21 of Klop's paper) with
    the `weights' ${0,1,A,B,\dots}"|->"1$, ${`*}"|->"2$, and
    ${`(A),`(B),\dots}"|->"3$.}
\end{Q}

\begin{Q}\label{nandc-critical}
  Show that ´{NandC} is complete. \A{First we find the overlaps; in each case
    $a$ can be any branch point $A,B,\dots$:
    \begin{gather*}
      0`*0 \quad\textup{by \eqref{nand-0x}, \eqref{nand-x0} (as before)}\\
      `(a)(u,\b{1`*1})\quad\textup{by \eqref{nandc-*}, \b{\eqref{nand-11}}}\\
      `(a)(u,\b{0`*x})\quad\textup{by \eqref{nandc-*}, \b{\eqref{nand-0x}}}\\
      `(a)(u,\b{x`*0})\quad\textup{by \eqref{nandc-*}, \b{\eqref{nand-x0}}}
    \end{gather*}}
\end{Q}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One application is to find a way to measure the ´{speed} of circuits in the
form of the ´{delay} from the inputs are stable until the output is stable.
We'll assume that all gates use one time unit to stabilise their output after
their inputs are stable and that wires have no delay, so the three circuits
we have investigated so far have delay 1 (inverter), 2 (and), and 3 (xor).

\begin{Q}\label{delay}
  Design a reduction strategy for one of the systems such that the number of
  strategy steps that it uses corresponds to the delay of `real' circuits.
  Verify your system by checking for the three circuits above.  ´{Hints}:
  Think about what properties of a circuit this depends on and that `many
  step strategies' use fewer steps than ordinary reduction.  \A{It is
    sufficient to use ´{Nand} because the delay only depends on the number of
    gates from the inputs to the output.  Furthermore, we should reduce `as
    fast as possible' from the inputs to the output thus some kind of
    parallel reduction is needed.  It should be outermost because `disjoint'
    gates stabilise independently which means that there may be longer paths
    than the delay when there is redundant circuitry, \textit{i.e.}, the
    circuit $x`*(1`*y)$ stabilises in a single unit for $x=0$.}
\end{Q}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Another application is to measure the ´{power consumption} of circuits.  We
will simplify the problem by asuming that only gates that ´{change state} use
any power.

\begin{Q}\label{power}
  Devise a method to measure the power consumption of circuits.  ´{Hint}: It
  is alright to change the rewrite system to represent additional
  information.  \A{The easiest way is to measure the `cost of the output' by
    annotating all terms with a cost number and then look at the final output
    to see the total cost.  The critical point to get right is the branching
    rule: the cost of generating the signal that is branced should only be
    counted once.}
\end{Q}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Q}[difficult]\label{feedback}
  Discuss how one might define a rewrite system that describes feed-back in
  circuits, and how such circuits correspond to simple ´{Nand}-circuits?
  \A{Several techniques can be used here and it is still open what is best.
    One method is to have `pervasive branches', \textit{i.e.}, replace
    rule~\eqref{nandc-aa} with
    \begin{equation}\tag{$\ref{nandc-aa}'$}
      `(a)(x,a) "->" `(a)(x,x)
    \end{equation}
    Such circuits correspond to infinite (though regular) ´{Nand}-circuits.}
\label{lastQ}\end{Q}

\paragraph*{End of the exercises.} \copyright\ 1994 \MYNAME\ (solutions
available).\label{end}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\Answers

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

$Log: FRS-exam.tex,v $
Revision 1.6  1995/10/03  15:42:28  kris
Modified to not use t.sty as an Xy-pic sample...

Revision 1.5  1995/02/07  23:12:46  kris
Second round.

Revision 1.4  1994/12/23  14:19:51  kris
Løsninger sendt til studenterbedømmerne.

Revision 1.3  1994/12/13  16:07:57  kris
Includes the two announced corrections.

Revision 1.2  1994/12/13  11:44:16  kris
This is what they get.

Revision 1.1  1994/12/12  09:15:43  kris
Initial revision
