summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/program/program-demo.tex
diff options
context:
space:
mode:
Diffstat (limited to 'macros/latex/contrib/program/program-demo.tex')
-rw-r--r--macros/latex/contrib/program/program-demo.tex325
1 files changed, 325 insertions, 0 deletions
diff --git a/macros/latex/contrib/program/program-demo.tex b/macros/latex/contrib/program/program-demo.tex
new file mode 100644
index 0000000000..af7c3bcbe8
--- /dev/null
+++ b/macros/latex/contrib/program/program-demo.tex
@@ -0,0 +1,325 @@
+\documentclass{article}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{newlfont}
+\usepackage{program}
+\setlength{\parskip}{1ex}
+
+% Number algorithms separately:
+%\newtheorem{algorithm}{Algorithm}
+
+% Number algorithms within sections:
+\newtheorem{algorithm}{Algorithm}[section]
+
+% For "floating" algorithms, use:
+% \begin{figure}
+% \begin{program}
+% ...
+% \end{program}
+% \end{figure}
+
+% To use |foo_bar| in headings, set _ to be active.
+% Not done by default as this clashes with \includegraphics
+% if filenames have _ characters in them:
+
+\catcode`\_\active
+
+\begin{document}
+\title{A demonstration of the {\tt program} environment}
+\author{Martin Ward\\
+\tt{martin@gkc.org.uk}}
+\maketitle
+
+\tableofcontents
+
+\section{Example with |first_set| and $|first_set|$.}
+
+
+The {\tt program} style defines two environments, {\tt program} and {\tt
+programbox} for typesetting programs and algorithms. Within the program
+environment:
+\begin{enumerate}
+ \item Newlines are significant;
+ \item Each line is in math mode, so for example spaces in the input
+file are not significant;
+ \item The command \verb:\\: within a line causes an extra
+linebreak in the output;
+ \item The indentation of each line is calculated automatically;
+ \item To cause extra indentation, use the commands \verb:\tab: to
+set a new tab, and \verb:\untab: to remove it (see the examples below);
+ \item Vertical bars are used to delimit long variable names with
+underscores (and other unusual characters).
+\end{enumerate}
+
+\verb:testing | in verbatim:
+
+\begin{verbatim}
+testing | and @ in verbatim
+\end{verbatim}
+
+
+Here is a small program:
+\( |first_set|:= \set{x | x^2 + y_1 > 0 } \)
+It shows how to typeset mathematics as part of a program. Since each line is
+typeset in maths mode, all spacing is done automatically. The set brackets
+expand automatically, for example in this program (which also demonstrates the
+\verb:\tab: and \verb:\untab: commands):
+\begin{program}
+t := \set{x | \displaystyle\frac{x}{y} = z};
+t := t \setminus u;
+z := a \tab {} + b + c + d
+ {} + e + f + g
+ {} + h + i + j; \untab
+\IF x = 0 \THEN y :=0 \FI
+\end{program}
+
+You can use |variable_names| in text or math mode: $|variable_name|^2 = 2$.
+Names can have |odd_characters:!@#$%^&*:;_like_this!|.
+
+Note that \verb:\(: and \verb:\): are redefined to typeset a program in
+a minipage. (This is useful in running text, or to keep a short program all on
+one page). There is some notation for sequences: \( \seq{x_1,x_2,\dots,x_n} \)
+and for universal and existential quantifiers: $ \Forall x. \Exists y. y>x $
+(yes, I use these in my programs!)
+
+I often use bold letters to represent program fragments, formulas etc. so
+I have set up commands \S{}, \R{} etc. for the most common ones. The
+commands have one argument (a subscript, eg \S1, \S2, \S{23}) or a
+sequence of ``prime'' characters: \S', \S''''' etc. If you want both a
+subscript and one or more primes, then you must use maths mode, eg $\S2'$
+Consider the difference between typing \verb:``\S2'': which gives ``\S2'' and
+\verb:``$\S2''$'': which gives ``$\S2''$''. Outside maths mode, \verb:\S:
+assumes any primes after a subscript are either closing quotes or apostrophes.
+
+Here are two program examples with different indentation styles. Note that
+all indentation is calculated automatically in either style:
+
+\noindent
+% programbox keeps the program on one page - like parbox
+\begin{programbox}
+\IF \T1
+ \THEN \IF \T2
+ \THEN \IF \T3
+ \THEN \S4
+ \ELSE \S3
+ \FI
+ \ELSE \S2
+ \FI
+ \ELSE \S1
+\FI;
+% Blank lines are ignored, so you need a ~ on the line
+% to get a blank line in the output:
+~
+\IF \T1 \THEN \IF \T2 \THEN \IF \T3 \THEN \S4
+ \ELSE \S3 \FI
+ \ELSE \S2 \FI
+ \ELSE \S1 \FI;
+\end{programbox}
+
+Note that \keyword{then} and \keyword{else} should be at the {\em start} of
+a line (as in the examples above), not at the end. This is so that you can
+line them up in short \keyword{if} statements, for example:
+\begin{program}
+\IF x=1 \THEN |a_long_procedure_name|(|arg1|, |arg2|, \dots)
+ \ELSE |another_long_procedure_name|(|arg1|, |arg2|, \dots) \FI
+\end{program}
+If the test is long, then you probably want an extra linebreak:
+\begin{program}
+\IF |a_long_boolean_function_name?|(|arg1|, |arg2|, \dots)
+ \THEN |a_long_procedure_name|(|arg1|, |arg2|, \dots)
+ \ELSE |another_long_procedure_name|(|arg1|, |arg2|, \dots) \FI
+\end{program}
+Compare this with the following (which has linebreaks in the ``wrong'' places):
+\begin{program}
+\IF |a_long_boolean_function_name?|(|arg1|, |arg2|, \dots) \THEN
+ |a_long_procedure_name|(|arg1|, |arg2|, \dots)
+ \ELSE
+ |another_long_procedure_name|(|arg1|, |arg2|, \dots) \FI
+\end{program}
+
+
+
+Just to show that {\tt\origbar} still works normally to indicate the
+placing of vertical lines) in the preamble of a tabular
+(or array) environment:
+
+\begin{tabular}{|r|l|} \hline
+\bf Statement & \bf Conditions \\
+\hline
+\S1 & \B1 \\
+\S2 & \B2 \\
+\hline
+\end{tabular}
+
+\section{Procedures and Functions}
+
+Turning on line numbering here. Also using the algoritm enviroment to number
+the algorithms within the sections.
+\NumberProgramstrue
+\begin{algorithm}
+\begin{program}
+\label{one}%
+\mbox{A fast exponentiation function:} \\ % You can use \mbox for comments
+\BEGIN %
+ \FOR i:=1 \TO 10 \STEP 1 \DO
+ |print|(|expt|(2,i)); \\ |newline|() \OD
+\WHERE
+\FUNCT |expt|(x,n) \BODY
+ \EXP z:=1;
+ \WHILE n \neq 0 \DO
+ \WHILE |even|(n) \DO
+ n:=n/2; x:=x*x \OD; \label{foo}
+ n:=n-1; z:=z*x \OD;
+ z \ENDEXP \ENDFUNCT
+\END\label{last}
+\end{program}
+\end{algorithm}
+First line is line~\ref{one}, last is line~\ref{last}.
+Line~\ref{foo} is what makes this function fast!
+
+\begin{algorithm}
+\begin{program}
+\mbox{A fast exponentiation procedure:}
+\BEGIN %
+ \FOR i:=1 \TO 10 \STEP 1 \DO
+ |expt|(2,i); \\ |newline|() \OD %
+\rcomment{This text will be set flush to the right margin}
+\WHERE
+\PROC |expt|(x,n) \BODY
+ z:=1;
+ \DO \IF n=0 \THEN \EXIT \FI;
+ \DO \IF |odd|(n) \THEN \EXIT \FI;
+\COMMENT{This is a comment statement};
+ n:=n/2; x:=x*x \OD;
+ \{ n>0 \};
+ n:=n-1; z:=z*x \OD;
+ |print|(z) \ENDPROC
+\END
+\end{program}
+\end{algorithm}
+
+\noindent An action system equivalent to a \keyword{while} loop:
+\[
+\( \ACTIONS A:
+ A \EQ \IF \B{} \THEN \S{}; \CALL A
+ \ELSE \CALL Z \FI \QE
+ \ENDACTIONS \)
+\EQT
+\( \WHILE \B{} \DO \S{} \OD \)
+\]
+Note the use of \verb:\(: and \verb:\): to enclose the two program boxes.
+Turning off line numbers here.
+\NumberProgramsfalse
+
+\noindent Dijkstra conditionals and loops:
+\begin{program}
+\IF x = 1 \AR y:=y+1
+\BAR x = 2 \AR y:=y^2
+\utdots
+\BAR x = n \AR y:=\displaystyle\sum_{i=1}^n y_i \FI
+
+\DO 2 \origbar x \AND x>0 \AR x:= x/2
+\BAR \NOT 2 \origbar x \AR x:= \modbar{x+3} \OD
+\end{program}
+
+\noindent Loops with multiple \keyword{exit}s:
+\begin{program}
+\DO \DO \IF \B1 \THEN \EXIT \FI;
+ \S1;
+ \IF \B2 \THEN \EXIT(2) \FI \OD;
+ \IF \B1 \THEN \EXIT \FI \OD
+\end{program}
+
+\noindent I hope you get the idea!
+
+\section{A Reverse Engineering Example}
+
+Here's the original program:
+\begin{algorithm}
+\begin{program}
+ \VAR \seq{m := 0, p := 0, |last| := `` ''};
+ \ACTIONS |prog|:
+|prog| \ACTIONEQ %
+ \seq{|line| := `` '', m := 0, i := 1};
+ \CALL |inhere| \ENDACTION
+l \ACTIONEQ %
+ i := i+1;
+ \IF (i=(n+1)) \THEN \CALL |alldone| \FI ;
+ m := 1;
+ \IF |item|[i] \neq |last|
+ \THEN |write|(|line|); |line| := `` ''; m := 0;
+ \CALL |inhere| \FI ;
+ \CALL |more| \ENDACTION
+|inhere| \ACTIONEQ %
+ p := |number|[i]; |line| := |item|[i];
+ |line| := |line| \concat `` '' \concat p;
+ \CALL |more| \ENDACTION
+|more| \ACTIONEQ %
+ \IF (m=1) \THEN p := |number|[i];
+ |line| := |line| \concat ``, '' \concat p \FI ;
+ |last| := |item|[i];
+ \CALL l \ENDACTION
+|alldone| \ACTIONEQ |write|(|line|); \CALL Z \ENDACTION \ENDACTIONS \END
+\end{program}
+\end{algorithm}
+
+And here's the transformed and corrected version:
+\begin{algorithm}
+\begin{program}
+\seq{|line| := `` '', i := 1};
+\WHILE i \neq n+1 \DO
+ |line| := |item|[i] \concat `` '' \concat |number|[i];
+ i := i+1;
+ \WHILE i \neq n+1 \AND |item|[i] = |item|[i-1] \DO
+ |line| := |line| \concat ``, '' \concat |number|[i]);
+ i := i+1 \OD ;
+ |write|(|line|) \OD
+\end{program}
+\end{algorithm}
+
+Below are the same programs in a bold serif style with underlined keywords, using the command
+\verb:\bfvariables::
+\bfvariables
+\begin{program}
+ \VAR \seq{m := 0, p := 0, |last| := `` ''};
+ \ACTIONS |prog|:
+|prog| \ACTIONEQ %
+ \seq{|line| := `` '', m := 0, i := 1};
+ \CALL |inhere| \ENDACTION
+l \ACTIONEQ %
+ i := i+1;
+ \IF (i=(n+1)) \THEN \CALL |alldone| \FI ;
+ m := 1;
+ \IF |item|[i] \neq |last|
+ \THEN |write|(|line|); |line| := `` ''; m := 0;
+ \CALL |inhere| \FI ;
+ \CALL |more| \ENDACTION
+|inhere| \ACTIONEQ %
+ p := |number|[i]; |line| := |item|[i];
+ |line| := |line| \concat `` '' \concat p;
+ \CALL |more| \ENDACTION
+|more| \ACTIONEQ %
+ \IF (m=1) \THEN p := |number|[i];
+ |line| := |line| \concat ``, '' \concat p \FI ;
+ |last| := |item|[i];
+ \CALL l \ENDACTION
+|alldone| \ACTIONEQ |write|(|line|); \CALL Z \ENDACTION \ENDACTIONS \END
+\end{program}
+
+\begin{program}
+\seq{|line|:=`` '', i:=1};
+\WHILE i \neq n+1 \DO
+ |line| := |item|[i] \concat `` '' \concat |number|[i];
+ i := i+1;
+ \WHILE i \neq n+1 \AND |item|[i] = |item|[i-1] \DO
+ |line| := |line| \concat ``, '' \concat |number|[i]);
+ i := i+1 \OD ;
+ |write|(|line|) \OD
+\end{program}
+
+In my opinion, the \verb:\sfvariables: style looks much better.
+The \verb:\bfvariables: style was the default, but this was changed with version 3.3.11.
+
+
+\end{document}
+