\( \newcommand\D{\mathrm{d}} \newcommand\E{\mathrm{e}} \newcommand\I{\mathrm{i}} \newcommand\bigOh{\mathcal{O}} \newcommand{\cat}[1]{\mathbf{#1}} \newcommand\curl{\vec{\nabla}\times} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} \)
UP | HOME

TAOCPMAC in LaTeX

Table of Contents

1. Introduction

This is just my translation of a bit of Knuth's taocpmac.tex into LaTeX. This is no exhaustive, but it should cover a lot.

I think Knuth's style is very personal, in the sense that he came to it after a lot of deliberation and reasoning about it. Therefore, I do not think it "translates" well: Knuth's macros and layout are suited for his writing style (which is idiosyncratic), and therefore does not translate well to other writing styles.

If you want to use his macros, I would seriously urge you to reconsider. Instead, you should consider asking yourself, "What principles led him to these decisions? How can I apply those principles to guide my typographical style?"

2. Page Layout

You can use either the geometry package, or just copy/paste what Knuth does. The textwidth is 29pc, the textheight is 45pc.

The paper dimensions are given by the \htrimsize and \vtrimsize dimensions (height of 9.25 inches, width of 6.375 inches). 

% taocpmac.tex original
% Page layout
\newdimen\pagewidth \newdimen\pageheight \newdimen\ruleht
\hsize=29pc  \vsize=45pc  \maxdepth=2.2pt  \parindent=19pt
\pagewidth=\hsize \pageheight=\vsize \ruleht=.5pt
\abovedisplayskip=6pt plus 3pt minus 1pt
\belowdisplayskip=6pt plus 3pt minus 1pt
\abovedisplayshortskip=0pt plus 3pt
\belowdisplayshortskip=4pt plus 3pt

The easiest way to reproduce this, I think, is something like: 

\usepackage[pagewidth=6.375in,
  pageheight=9.25in,
  textwidth=29pc,
  textheight=45pc]{geometry}

3. Chapter, Section, Subsection formatting

The tex macros for this is reproduced below: 

% taocpmac.tex original

\newif\iftitle \newif\ifdrop \newif\ifrunon
\def\titlepage{\global\titletrue\global\droptrue} % for pages without headlines
\def\lhead{} % running headline on lefthand pages (usually chapter name)
\def\rhead{} % running headline on righthand pages (usually section name)

  
% line 388 et seq.
\def\beginchapter#1: #2.
  {\vfill\eject
    \titlepage
    \leftline{\twelvess \spaceskip=10pt \def\\{\kern1pt}#1}
    \vskip 4pc
    \rightline{\titlefont #2}
    \def\\{}
    \ifx\rhead\omitrhead\else{\ninepoint\xdef\rhead{\uppercase{#2}}}\fi
    \vskip 2pc plus 1 pc minus 1 pc
  }

\def\starred{}
\def\starit{\def\starred{\llap{*}}}
\def\omitrhead{\omit}

\def\beginsection #1. #2.
  {\mark{\currentsection \noexpand\else #1}
    \ifrunon \runonfalse\vskip 1 cm plus 1 pc minus 5 pt
    \else \vfill\eject
      {\output{\setbox0=\box255}\null\vfill\eject} % set \topmark for sure
    \fi
    \tenpoint
    \leftline{\tenssbx\starred#1. \uppercase{#2}}
    \def\starred{}
    \mark{#1\noexpand\else #1}
    \def\currentsection{#1}
    {\ninepoint\xdef\rhead{\uppercase{#2}}}
    \nobreak\smallskip\noindent}

\def\beginsectionnonumber #1.
  {\ifrunon \runonfalse\vskip 1 cm plus 1 pc minus 5 pt
    \else \vfill\eject \fi
    \tenpoint
    \leftline{\tenssbx\starred\uppercase{#1}}
    \def\starred{}
    {\ninepoint\xdef\rhead{\uppercase{#1}}}
    \nobreak\smallskip\noindent}

\def\beginsubsection #1. #2.
  {\mark{\currentsection \noexpand\else #1}
    \bigbreak
    \tenpoint
    \leftline{\tenssbx\starred#1. #2}
    \def\starred{}
    \mark{#1\noexpand\else #1}
    \def\currentsection{#1}
    {\ninepoint\xdef\rhead{\uppercase{#2}}}
    \nobreak\smallskip\noindent}

\def\beginsubsubsection #1. #2.    % set page headers: 3.2.1.3
  {\mark{\currentsection \noexpand\else #1}
    \tenpoint
    \bigbreak
    \null
    \mark{#1\noexpand\else #1}
    \def\currentsection{#1}
    {\ninepoint\xdef\rhead{\uppercase{#2}}}
    \nobreak\vskip-\baselineskip
    \noindent{\bf\starred#1.\enspace #2.\xskip}\def\starred{}\ignorespaces}

\def\beginsubsubsectionprime #1.  % don't set page headers: 3.3.1B
  {\medbreak
    \null
    \tenpoint
    \nobreak\vskip-\baselineskip
    \noindent{\bf\starred#1.\xskip}\def\starred{}\ignorespaces}

A chapter has its chapter number ["CHAPTER 6"] be printed in 12-point sans serif flushed left, in all capital letters. Then 4pc vskip below it, flushed right, is the name of the chapter in title font (bold sans serif, in 14.4 point size). Finally, a vskip of 2pc plus 1pc minus 1pc separates the body text from the chapter section title.

Almost every section in The Art of Computer Programming starts at the top of a page. I don't know if this is by accident or by design, but since it's every section…that's too much to be a coincidence. (The only exception I found was section 6.1, but I may be mistaken!) Section formatting:

  • \vskip 1 cm plus 1 pc minus 5 pt before printing anything (unless on the top of the page)
  • 10 bold sans serif upper case font
  • \thesection. #1 is what is printed
  • \smallskip afterwards, with no indent

Subsections have similar formatting:

  • \bigbreak precedes the title
  • 10 bold sans serif font (not upper cases)
  • \thesubsection. #1 is what is printed
  • \nobreak\smallskip\noindent is then separating the text

Subsubsections are "runin".

  • a \bigbreak precedes a subsubsection
  • Then \textbf{\thesubsubsection.\enspace #1.\xskip}\ignorespaces prints the subsubsection number plus its title
  • Starred subsubsections do not have subsubsection numbers printed.

There are no levels of organization below subsubsections (there are no "subsubsubsections", or anything "smaller").

3.1. LaTeX Code using Titlesec

Using the titlesec package, we can format chapters, sections, subsections, and subsubsections to resemble their counterparts in The Art of Computer Programming as follows: 

\usepackage{titlesec}
\font\titlefont=cmssbx10 scaled\magstep2
\def\starred{}
\def\starit{\def\starred{\llap{*}}}
\usepackage{titlesec}
% "\large" is 12-point when the main font is 10-point
\titleformat{\chapter}[display]
            {\titlefont} % format
            {\large\sffamily\spaceskip=10pt\MakeUppercase{\chaptertitlename} \thechapter} % label
            {4pc} % sep 
            {\filleft\MakeUppercase} % before
\titleformat{name=\chapter,numberless}[display]
            {\titlefont} % format
            {} % label
            {4pc} % sep
            {\filleft} % before

% Use the fact that a normal space is computed using font dimensions
% see: https://tex.stackexchange.com/a/229642/14751
\titleformat{\section}%[block]
            {\bfseries\sffamily} % format
            {\starred\thesection.\def\starred{}} % label
            {2\fontdimen2\font plus\fontdimen3\font minus\fontdimen4\font} % sep
            {\MakeUppercase} % before

\titleformat{\subsection}%[block]
            {\bfseries\sffamily} % format
            {\starred\thesubsection.\def\starred{}} % label
            {2\fontdimen2\font plus\fontdimen3\font minus\fontdimen4\font} % sep
            {} % before

% Runin subsubsections, with a period added (if missing)
\makeatletter
\def\@addpunct#1{%
  \relax\ifhmode
    \ifnum\spacefactor>\@m \else#1\fi
  \fi}
\titleformat{\subsubsection}[runin]
            {\normalfont\bfseries} % format
            {\starred\thesubsubsection.\def\starred{}} % label
            {0.5em} % sep = \enspace
            {} % before
            [\@addpunct{.}]
\makeatother
\newskip\xskipamount
\xskipamount=7pt plus 3pt minus 4pt
\titlespacing*{\chapter}{0pt}{0pt}{2pc plus 1 pc minus 1 pc}
\titlespacing*{\section}{0pt}{1cm plus 1pc minus 5pt}{\smallskipamount}
\titlespacing*{\subsection}{0pt}{\bigskipamount}{\smallskipamount}
\titlespacing*{\subsubsection}{0pt}{\bigskipamount}{\xskipamount\ignorespaces}
\setcounter{secnumdepth}{3}

4. Algorithms

Knuth uses \slug as his \qedsymbol, so if you want to use some other symbol…you'll have to update these macros accordingly. 

% latex macros
% These macros are borrowed from TAOCPMAC.tex
\newcommand{\slug}{\hbox{\kern1.5pt\vrule width2.5pt height6pt depth1.5pt\kern1.5pt}}
\def\xskip{\hskip 7pt plus 3pt minus 4pt}
\newdimen\algindent
\newif\ifitempar \itempartrue % normally true unless briefly set false
\def\algindentset#1{\setbox0\hbox{{\bf #1.\kern.25em}}\algindent=\wd0\relax}
\def\algbegin #1 #2{\algindentset{#21}\alg #1 #2} % when steps all have 1 digit
\def\aalgbegin #1 #2{\algindentset{#211}\alg #1 #2} % when 10 or more steps
\def\alg#1(#2). {\medbreak % Usage: \algbegin Algorithm A (algname). This...
  \noindent{\bf#1}({\it#2\/}).\xskip\ignorespaces}
\def\algstep#1.{\ifitempar\smallskip\noindent\else\itempartrue
  \hskip-\parindent\fi
  \hbox to\algindent{\bf\hfil #1.\kern.25em}%
  \hangindent=\algindent\hangafter=1\ignorespaces}
% end of borrowed macros

% For Example, with less than 10 steps:
% \algbegin X (Multiplication). blah blah blah blah...
% \algstep X1. [{\it Do stuff\/}] blah blah blah
% \algstep X2. Terminate the algorithm.\quad\slug

Note that Knuth's only control structure is really jumping to other steps in the algorithm. It appears to me that the role algorithms play in TAOCP is little more than extended commentary on the MIXAL programs found in it.

5. MIXAL

The assembly code printed in the book is formatted using the \mixtwo, \mixthree, \mixfour, …, \mixsix macros. These are plain TeX tables, so the columns are separated by & and the end of line needs a \cr macro.

If I knew the LaTeX \begin{list}...\end{list} environment better, I might try translating it. I'm nervous about just translating this as a tabular, because I don't understand it's underlying mechanics well enough. But you could imagine something like a \begin{mixal}[4]...\end{mixal} environment taking an optional parameter for the number of columns, which would be nice.

A few explicit notes worth mentioning:

  • \underspecial is used to underline comments referencing steps in an associated algorithm; Knuth breaks the underlining when there is a "descender" (like the curly part of a lowercase "g" or "j" or "y")
  • \small is approximately LaTeX counterpart of \ninepoint
  • \mc is for medium caps (as opposed to \sc), and I honestly don't know why \mc is used for these logos instead of \sc or anything else (but after working with Times New Roman font for a while, \mc formatting of FORTRAN looks much nicer than \textsc{Fortran}…);
  • I have had great difficulty getting these macros to work nicely with page breaks in LaTeX, but perhaps I'm just an idiot
% taocpmac.tex lines 876 et seq.
\def\CEE/{{\mc C\spacefactor1000}}% the C programming language
\def\FORTRAN/{{\mc FORTRAN\spacefactor1000}}% ditto for the older guy
\def\ALGOL/{{\mc ALGOL\spacefactor1000}}
\def\COBOL/{{\mc COBOL\spacefactor1000}}
\def\MIX{{\tt MIX\spacefactor1000}}
\def\MMIX{{\tt MMIX\spacefactor1000}}
\def\mm{\kern-.2em\'{}\kern-.1em} % modifies a section number, for MMIX changes
\def\rA{\hbox{\rm rA}}
\def\rX{\hbox{\rm rX}}
\def\rAX{\hbox{\rm rAX}}
\def\rI{\hbox{\rm rI}}
\def\rJ{\hbox{\rm rJ}}

% to typeset assembly code, use:
%  \mixtwo   for opcode and address
%  \mixthree for location, opcode, and address
%  \mixfour  for line number, location, opcode, and address
%  \mixfive  for line number, location, opcode, address, count
%  \mixsix  for line number, location, opcode, address, count, squeezed tight
% (all variations allow optional comments at end of the line)
% put \\ after \cr to indicate a logical page break
% and end the whole thing with \endmix

% Say \let\ninepoint=\flexninepoint to allow slight baselineskip variations

\def\sdol{\global\catcode`\$=12 \global\catcode`\#=12}
\def\ndol{\global\catcode`\$=3  \global\catcode`\#=6}
\def\specialunder{\ifmmode\def\next{_}\else\chardef\next=`\_\fi\next}
{\catcode`\_=\active
  \gdef\underspecial{\catcode`\_\active \global\let_=\specialunder}}
\def\mixtwo{\begingroup\let\ttt=\tt \ninepoint
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \ttt\hbox to 2.5em{##\hfil}& % op
          \ttt##\hfil\quad&            % address
          \rm##\hfil\cr}               % comment
\def\mmixtwo{\begingroup\let\ttt=\tt\ninepoint \underspecial
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \ttt##\hfil\quad\sdol&       % op
          \ttt##\hfil\quad\ndol&       % expr
          \rm##\hfil\cr}               % comment
\def\mixthree{\begingroup\let\ttt=\tt\ninepoint
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \ttt##\enspace\hfil&         % loc
          \ttt\hbox to 2.5em{##\hfil}& % op
          \ttt##\hfil\quad&            % address
          \rm##\hfil\cr}               % comment
\def\mmixthree{\begingroup\let\ttt=\tt\ninepoint
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \ttt##\enspace\hfil&         % label
          \ttt##\hfil\ \sdol&          % op
          \ttt##\hfil\quad\ndol&       % expr
          \rm##\hfil\cr}               % comment
\def\mixfour{\begingroup\let\ttt=\tt\ninepoint
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \hfil\it##\quad&             % line
          \ttt##\enspace\hfil&         % loc
          \ttt\hbox to 2.5em{##\hfil}& % op
          \ttt##\hfil\quad&            % address
          \rm##\hfil\cr}               % comment
\def\mmixfour{\begingroup\let\ttt=\tt\ninepoint \underspecial
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \hfil\it##\quad\sdol&        % line
          \ttt##\enspace\hfil&         % label
          \ttt##\hfil\enspace&         % op
          \ttt##\hfil\quad\ndol&       % expr
          \rm##\hfil\cr}               % comment
\def\mixfive{\begingroup\let\ttt=\tt\ninepoint
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \hfil\it##\quad&             % line
          \ttt##\enspace\hfil&         % loc
          \ttt\hbox to 2.5em{##\hfil}& % op
          \ttt##\hfil\quad&            % address
          \hfil$ ##$\hfil\quad&        % frequency count
          \rm##\hfil\cr}               % comment
\def\mmixfive{\begingroup\let\ttt=\tt\ninepoint \underspecial
  \def\\{\noalign{\penalty-200}}
  \halign\bgroup
          \hfil\it##\quad\sdol&        % line
          \ttt##\enspace\hfil&         % label
          \ttt##\hfil\enspace&         % op
          \ttt##\hfil\quad\ndol&       % expr
          \hfil$ ##$\hfil\quad&        % frequency count
          \rm##\hfil\cr}               % comment
\newdimen\mixsqueeze % set this before each use of \mixsix
\def\mixsix{\begingroup\let\ttt=\tt\ninepoint %last field is flush right
  \def\\{\noalign{\penalty-200}}
  \halign to \hsize\bgroup
          \hfil\it##\quad&             % line
          \ttt##\enspace\hfil&         % loc
          \ttt\hbox to 2.5em{##\hfil}& % op
          \ttt##\hfil\quad&            % address
          \hskip-\mixsqueeze
          \hfil$ ##$\hfil\quad&        % frequency count
          \rm##\hidewidth\tabskip 0pt plus 1fil& % comment
          \medmuskip 1mu \relax \thickmuskip 3mu \relax
          \hfil##\tabskip0pt\cr}
\def\endmix{\egroup\endgroup}
\def\endmmix{\egroup\endgroup}

Last Updated 2024-06-12 Wed 09:54.