%%
%% $Id$
%%
\authorrunning{Pape}
\titlerunning{\TeX{} Paragraph Layout for Lively-Kernel}
\title{Bringing \TeX's Paragraph Layout Algorithm to the Lively Kernel}
\subtitle{Seminar Web-based Development Environments}
\author{Tobias~Pape}
\institute{%
  Hasso-Plattner-Institut, Potsdam\\
  \email{\{firstname.lastname\}@student.hpi.uni-potsdam.de}
}
\maketitle

\def\sepping{\penalty-10000\vskip-.5\baselineskip\hrule\penalty-10000\vskip.5\baselineskip}
\newcommand{\morph}[1]{{\lstinline{#1}}\xspace}
\newcommand{\function}[1]{{\lstinline|#1|}\xspace}
\newcommand\lk{Lively Kernel\xspace}
\acrodef{KPA}{Knuth-Plass algorithm}

\bibliographystyle{splncs03}
\begin{abstract}
  The \lk as a web-based system uses a simple line breaking algorithm
  to lay out its text. This class of algorithms is prone to unpleasant
  output. More sophisticated algorithms exist, \eg, as used in \TeX,
  but are harder to understand. Visualizing the algorithm in a
  \emph{lively} manner may facilitate its understanding. Integrating
  the algorithm into the \lk provides the basis for \emph{lively}
  visualizing it.
  \begin{todolist}{Abstract}
  \item to overcome poor line breaking
  \item want to use non-greed lb algos
  \item hard to grok, eg kpa
  \item lively visualization and experience of algo
  \end{todolist}
\end{abstract}


\section{Why \TeX? A Motivation}
\label{sec:why-tex-motivation}

The \lk is a web-based development- and runtime-environment that is
self-sustaining and focused on collaboration~\cite{1482376}. Its user
interface is an implementation of the Morphic
system~\cite{Maloney:1995ec,Maloney:1995xw}. The notion of a morph
conveys the principle of objects that know how to represent themselves
graphically. This also holds for text to be used and displayed in the
\lk.

However, like in most web-based systems, the text layout algorithm
used is a rather simple, straight-forward one. Under many
circumstances the output is undesirable; unfortunate combinations of
words used in the text and the width of the text to be created may
lead to visual holes in the text. By the nature of this class of
algorithms, avoiding such cases is
hard~\cite{Knuth+1982:Breaking-paragr}. However, more sophisticated
algorithms exist that migitate this problem. \Eg, the algorithm
used by the \TeX\ typesetting system treats paragraphs as whole
entities and avoids jagged lines most of the time. On the contrary,
such algorithms are more complex than the straight-forward ones and
often are harder to understand.

To make complex algorithms more conceivable, algorithm visualization
may be employed. Yet, most visualization techniques do not cope for
the \emph{process} nature of algorithms and try to visualize dynamic
facts statically, \eg, with flow charts~\cite{953350}. With the \lk,
however a system exists that provides means to build more
\emph{lively} applications, visualizations, in this case. That said,
the most natural way to convey facts or processes in the \lk is to
actually implement them in the \lk and present them interactively. 
Thus, the aim of this work is to provide the \lk an implementation of
\TeX\ paragraph layout algorithm and then present its mechanism using
the algorithm itself.


\subsection{Notes on Synonyms}
\label{sec:notes-synonyms}

\begin{todolist}{Synonyms}
\item line (logical) vs line (physical)
\item paragraph vs. list of lines
\item Line breaking
\item paragraph breaking
\item breaking paragraphs into lines
\end{todolist}

In order to describe paragraph layouting or, more precise, line
breaking, two viewpoints exist that may introduce confusion. A
\emph{line} of text can either denote a \emph{physical} line, \ie, a
line with a certain physical width, a product of line breaking; or a
\emph{logical} line, \ie, a conceptual line of text to be
broken into parts. Conversely, two viewpoints on \emph{paragraphs}
exist: the \emph{physical} paragraph is a collection of physical
lines---line breaking already has been applied; the \emph{logical}
paragraph correlates with the \emph{logical} line: a text string not
yet broken into physical lines.

To avoid confusion, the word ``line'' will denote the \emph{physical}
line unless stated otherwise.


\subsection*{Paper Organization}
\label{sec:paper-organization}


\begin{todolist}{orga}
\item concepts
\item implementation
\item related work
\end{todolist}

Following this section, \autoref{sec:laying-out-paragr} covers the
concept of paragraph layouting via line breaking with special respect
to the algorithms of the \lk and \TeX. Then in
\autoref{sec:impl-lively-kern}, the base implementation of the newly
used algorithm is described as well as its integration into the \lk.
Then, in \autoref{sec:related-work} related work is given followed by
a summary and an outlook in \autoref{sec:wrap-up}.


\section{Laying Out Paragraphs, Conceptually}
\label{sec:laying-out-paragr}

The process of paragraph layouting mainly comprises line breaking, \ie,
at which points in a logical paragraph to introduce the start of a new
physical line.\footnote{This has changed during the introduction of computers
into typesetting, where the former predominant task of \emph{spacing
out} has diminished in importance~\cite{Knuth+1982:Breaking-paragr}.} As
pointed out earlier, different approaches exists to achieve this. In
the following, first the current approach used in the \lk is
described. Then, the approach used by \TeX, the \ac{KPA}, is outlined
briefly. \\\textit{N.B.:\/} Like most line breaking algorithms, both
algorithms use the \emph{text width} or \emph{composition width} as
dominant restriction: no single line determined by the algorithm shall
be wider than the composition width specified by the user.

\subsection{Text in the Lively Kernel}
\label{sec:text-lively-kernel}
\begin{todolist}{Textmorph}
\item as simple as knuth states: hit the wall and break
\item Text morph
\item text lines
\item text words
\item Chunk stream
\item Measurement
\end{todolist}

The main facility to show text in the \lk is the \morph{TextMorph}.
This morph is a simple rectangular morph that holds a
string\footnote{Text morphs may hold rich text, however, this
  is not covered here.} to be rendered. Upon rendering of the morph,
line breaking is carried out by walking all \emph{text words} of
the string and collecting them in a \emph{text line}. The walking
mechanism is supported by a so called \emph{chunk stream} that yields
consecutive text words.

\paragraph{Text words}
\label{sec:text-words}
\begin{figure}
  \centering
  \includegraphics[width=.8\linewidth]{LivelyText}  
  \caption{Text rendering in the \lk: A string is split into text
    words that are arranged in text lines of a maximum width.}
  \label{fig:lively-text}
\end{figure}

\lk text words are wrappers for non-space text strings that can be
rendered to a \lk canvas, \eg, \textsc{svg}. Text words are created
lazily by a chunk stream during parsing of the input string. Also,
text words are responsible for determining their own width by querying
the \lk font for the width of the word's characters. A text word has an
associated `raw' element that can be directly drawn by the underlying
rendering mechanism, \eg, \textsc{svg} as above.  As an example, 
for the string in \autoref{fig:lively-text} 13 text words would be
created, each knowing about its width and an associcated `raw'
\textsc{svg} element.


\paragraph{The chunk stream}
\label{sec:chunk-stream}

For line breaking, the text words of a string belonging to a text
morph are processed sequentially. To do that the text string has to be
broken up into text words, and these have to be returned one after
another. The operations are carried out by the chunk stream:
\begin{enumerate}
\item Collect characters form the current position in the text string until
\item a space-denoting character is read.
\item Then form a text word form the collected characters,
\item determine its width and
\item return the text word.
\item Store the new position in the text string for the next iteration.
\end{enumerate}


\paragraph{Text lines and line breaking}
\label{sec:text-lines}

Just before rendering the text morph, the aforementioned chunk stream
is processed and text lines are formed. Each text line is responsible
for the rendering of the text word it contains. 

The actual line breaking happens when the text lines are to be filled
with text words. As mentioned above, a certain limit for the text
lines width exists: the composition width. A text line is formed
through the following process: 
\begin{enumerate}
\item The chunk stream is queried for the next text word.
\item The new word's width is added to the current line width.
\item If the composition width is overshot, end the line and put the
  word at the beginning of a new line;
\item If not, add the text word to the current line and add the  width for a space.
\item Do this until the chunk stream is empty.
\end{enumerate}

Note that the process listed under \emph{Chunk stream} is actually
performed here during the first step, hence, this sequence essentially
makes up the arrow in \autoref{fig:lively-text}.

After these steps, a text morph contains an array of text lines
comprising renderable text words. The algorithm's straight-forward
manner accounts for its \emph{first fit} classification, according to
Knuth~\cite[p. 78]{Knuth1999:Digital-typogra}. This contrasts the
\TeX\ paragraph layout algorithm which is described next.

\subsection{The \acl*{KPA}}
\label{sec:knuth-plass-algor}
\begin{todolist}{Tex}
\item \ac{KPA} non-greedy Line break algo
\item Optimization problem over whole paragraph
\item cf. greedy (e.g. lively) consider one line at a time
\item --> no actual notion of paragraph
\end{todolist}


The \TeX\ typesetting system employs an algorithm for line breaking
conceived by Knuth and Plass in 1982~\cite{Knuth+1982:Breaking-paragr}
which treats the paragraph it operates on as a whole. Like the \lk 
line breaking algorithm, the \ac{KPA} does not operate directly on
text strings but \emph{nodes} which have similarities to \lk text
words. However, unlike in \lk the \ac{KPA} nodes may stand for more
than \emph{text not containing white spaces}. These nodes are
generated by the \TeX\ language parser, yet, this process is not of
interest here. 

The nodes that resemble \lk text words best are \emph{boxes}; they
have a certain width and \emph{material}, mostly pure text content.
The implicit spacing in the \lk line breaking process contrasts with
explicit nodes that carry space information in the \ac{KPA}:
\emph{glues} have a certain width as well as information in how far
this width may changed (called \emph{shrink- and stretchability}).
Last, an invisible node in the \ac{KPA} has no correspondant in the
\lk: the \emph{penalty} node conveys the additional cost of a line
break at a certain point in the text string.

\paragraph{Line breaking with the \ac{KPA}}
\label{sec:line-breaking-kpa}

\begin{figure}
  \centering
  \includegraphics[width=.8\linewidth]{KPA1}%
  \sepping
  \includegraphics[width=.8\linewidth]{KPA2}
  \caption{Simplified intermediate result of the \ac{KPA}. Above: Five possible
breakpoints were found. The cost of the lines each breakpoint creates
is given. Below: Additional to the previous, the \emph{accumulated
cost} from the beginning of the paragraph is given. The highlit
sequence denotes the sequence of chosen breakpoints.}
\label{fig:kpa}
\end{figure}


Given a list of pre-arranged nodes, the \ac{KPA} tries to find the
best sequence of line breaks by maximizing the `pleasantness' of the
line breaks. To achieve this, the \ac{KPA} uses a quantification of
how bad a line break may look: the \emph{badness}. Considering the
upper part of \autoref{fig:kpa}, there are two possible breakpoints
for the line that would start with ``can span several\ldots;'' one
before and one right after the ``I.'' However, the former breakpoint
would cause the white space in that line so much to be shrunken to fit
the desired width that a \emph{badness value} of 810 is allocated to
it. For the latter one, not so much white space has to be shrunken,
hence, the value is lower: 700.

To generalize, given two possible breakpoints in a text string and a
composition width. Then the \emph{badness of a line} formed by these
breakpoints is obtained from the ratio all the white space in that
line has to be shrunken or stretched to make the line width equal to
the composition width. For more in-depth badness calculation
formul\ae\ and how the value of penalty nodes contribute to it, refer
to the original algorithm paper~\cite{Knuth+1982:Breaking-paragr}.


The main method of the \ac{KPA} is to (a) find all important
\emph{possible} line breaks, (b) calculate their badness and, (c)
choose that sequence of breakpoints among the possible ones that has
the least overall badness values. To ease this process, the \ac{KPA}
employs a mathematical technique called \emph{dynamic
  programming}~\cite{Bellman1957:Dynamic-program}. Essentially, this
conveys the constant accumulation of badness values from the start of
the paragraph up to the current possible breakpoint. In
\autoref{fig:kpa} these accumulated values are given in the lower part
beneath the individual badness values. Once these values and their
accumulation have been calculated, it is possible to \emph{walk back}
the path of least value. In the example, this means starting from the
end of the paragraph and choosing the path to the breakpoints
before or after the ``I.'' As the breakpoint after the ``I'' has an
accumulated value of 1560, which is less than 1620 for the other one,
the breakpoint before the ``I'' would be chosen. This continues until
the start of the paragraph is reached. The found sequence of
breakpoints now results in actual lines and line breaks.

\ParSep

\noindent
Comparing the \lk- and the \ac{KPA}-approach, it is evident that the
former is a \emph{line centric}, the latter a \emph{paragraph centric}
algorithm. Additionally, the latter seems to inhibit more complexity
and, hence, may need more time to be understood and to be consequently
implemented.


\section{Implementation in the Lively Kernel}
\label{sec:impl-lively-kern}

The \ac{KPA} is more complex than the default \lk line breaking
algorithm and visualizing it may ease understanding it. The \lk
provides a programming environment that fosters interactivity and
\emph{liveliness}. However, to provide these attributes to a
visualization of the \ac{KPA}, the algorithm itself has to be
implemented in the \lk. As the base language in the \lk is JavaScript,
the TypeSet implementation of the \ac{KPA} has used as
foundation; it is described in the following. Then, its integration
into the \lk and the actual visualization of the \ac{KPA} are shown.

\subsection{The \ac{KPA} in the Web: TypeSet}
\label{sec:kpa-web:-typeset}

\begin{todolist}{TypeSet}
\item Application of \ac{KPA}
\item canvas
\end{todolist}

TypeSet by Bram Stein is an application of the \ac{KPA} to the
\textsc{html}\oldstylenums{5} canvas using
JavaScript~\cite{Stein2009:TypeSet}. It is intended as a first step
towards a library of various line breaking algorithms for the
\textsc{html}\oldstylenums{5} canvas element. The implementation
covers the whole algorithm as in~\cite{Knuth+1982:Breaking-paragr},
nevertheless, the simplified version mentioned there was not used and
the as well mentioned extensions are yet to be implemented except one:
A proof of concept for integration of hyphenation exist.\footnote{\url{http://www.bramstein.com/projects/typeset/flatland/}}

Written in JavaScript, TypeSet makes use of a few extensions to the
JavaScript standard library, namely extensions to \lstinline|Object|
and \lstinline|Array| and an implementation of a linked list. In order
to interact with the \textsc{html} page TypeSet is used in, it uses
the jQuery library\footnote{\url{http://jquery.com/}}. The data
structures needed by the \ac{KPA} are implemented as simple
constructor functions returning slim objects. This especially includes
boxes, glues, and penalties but also holds for breakpoints.

As pointed out in \autoref{sec:knuth-plass-algor}, the \ac{KPA} does not
operate directly on text strings but rather on a list of nodes. To
provide the algorithm with this list, TypeSet implements a set of
\emph{formatters} that turn a text string into a list of nodes
according to the desired formatting; centered, justified, and
flush-left formatters are included. To perform the transformation, the
text string is split at white space characters and all remaining
sub-strings are turned into box-nodes, unconditionally interleaved by node-sequences
that denote a space in the respective formatter. Hence, line break
characters, tabulator characters and others are treated all the same.
After transformation, the TypeSet implementation works like the \TeX\ implementation.


\subsection{Integration with the \lk}
\label{sec:integration}

\begin{todolist}{ContextJS}
\item lively ecosystem
\item extension may inflict other ``worlds''
\item ``overlay'' of functionality
\item ContextJS
\item Define \TeX\ rendering as behavioral deviation from standard rendering
\item Context: direct user request
\end{todolist}

Whilst a full implementation of the \ac{KPA} in
JavaScript---TypeSet---is available, integrating it into the \lk
requires adoption.

\paragraph{The Class system}
\label{sec:class-system}

The \lk provides a class system similar to that of
Smalltalk~\cite{273}, contrasting the prototype style of pure
JavaScript. In order to consistently use TypeSet in the \lk, its
object construtor style is to be transformed into the class style of
the \lk. Additionally, as no linked list implementation was available
in the \lk, a port of the TypeSet linked list version is used. It is
needed to maintain the list of breakpoints in the main part of the
\ac{KPA}.

The \lk provides a namespacing system into which the TypeSet
implementation has been integrated; the \lstinline|projects.TeX|
namespace is reserved for it while under development.

\paragraph{Hooking into text morphs}
\label{sec:hooking-into-text}

The \lk provides an \emph{ecosystem} of objects that can all be
interacted with at runtime. \lk Worlds, normally \textsc{html} files,
are such ecosystems---combining the kernel of Lively with specific
applications. For end user applications it would be natural to
bootstrap a \lk World and extend it with application code.
Nevertheless, introducing a different paragraph layout algorithm into
the \lk involves changes within the core parts, the \lk itself, which
text morphs are part of. Now, deliberately changing core logic of any
system may result in unexpected behavior, hence, isolation mechanisms
are required. It would be possible to bootstrap a \lk World and work
on a copy of the core part without affecting other Worlds, still,
reintegrating these changes would be troublesome.

To overcome these issues, a facility for context oriented
programming in the \lk, ContextJS, is used~\cite{1562118}. That way,
using the \ac{KPA} instead of the default \lk line breaking algorithm
can be seen as a behavioral deviation which can be layered over the
default implementation. In this case, the context to activate the layer
of \ac{KPA} behavior is \emph{explicit user request}; Text morphs that shall
use \ac{KPA} line breaking have to have the layer activated for
themselves.

\begin{lstlisting}[label=lst:hooking,float,caption={Slightly simplified form of the ContextJS layer used to enable TypeSet line breaking in the \lk}]
createLayer("TeXLayer");
layerClass(TeXLayer, TextMorph, {
  assureNet: function() {
   this.net = new projects.TeX.TeX.NodeNet(this.textString);
  },
  composeLines: function(proceed, initialStartIndex, initalTopLeft, compositionWidth, font, testEarlyEnd) {
    this.assureNet();
    return this.net.composeLines(initialStartIndex, initalTopLeft, compositionWidth, font, testEarlyEnd);
  },
  renderText: function(proceed, t, w) {
    var result;
    withLayers([TeXLayer], function(){ result = proceed(t,w); });
    return result;
  },
  resetRendering: function(proceed) {
    delete this.net;
    proceed();
  },
})
\end{lstlisting}

When text is to be rendered in the \lk, a text morph is responsible
for its text string to be mapped to renderable objects
(cf.~\autoref{sec:text-lively-kernel}). Hence, the behavioral
deviation just mentioned has to affect the \morph{TextMorph} class.
The key entry point for line breaking is the function
\function{composeLines()} of \morph{TextMorph}. Replacing this
function by the TypeSet implementation plus the initialization of the
node list (currently called \emph{net}) is nearly everything needed to
integrate the new behavior. Find a simple version of this integration
code in \autoref{lst:hooking}. Note that this listing includes two
more functions to ensure that the layer containing the required
behavior is activated.



Using this layer, the TypeSet implementation of the \ac{KPA} can
easily be used in any text morph throughout the \lk without affecting
other text morphs using the default implementation.

\paragraph{Text morph \textsc{api}}
\label{sec:text-morph-textscapi}

%\enlargethispage{-3\baselineskip}
The \lk is a highly interactive system. Therefore, the text morph of
the \lk includes numerous functions providing \emph{editing} behavior
as well as positioning functions to help the \lk interpret user events
such as mouse moves or mouse clicks. Incidentally, all these
\textsc{api} functions are implemented in the class
\lstinline|TextLine| that implement the functionality described in
\autoref{sec:text-lines}. To recapitulate: the \lk line breaking
algorithm turns a text string into \emph{text lines} of renderable
objects. While producing renderable object with the TypeSet
implementation would be possible without the notion of a text line, it
seemed reasonable to introduce a text line class specific to the
\ac{KPA} implementation to provide the required \textsc{api}
functions: \lstinline|projects.TeX.TeX.Line|. Except for the
\function{render()} function, all functions implement the \textsc{api}
needed for interaction.

\ParSep

\noindent
Given the implementation just introduced it is possible to have text
morphs in the \lk use the \ac{KPA} for line breaking. However,
\emph{visualizing} the algorithm is missing at this point. Note that
whilst all displaying capabilities necessary are provided, editing of
the text is not currently possible.


\subsection{Visualizing the \ac{KPA}}
\label{sec:visualizing-kpa}

\begin{todolist}{Vis layers}
\item Context: user requests visualization of kpa
\item Layer: Visualize Boxes
\item Layer: Visualize Tolerance
\item Layer: Visualize Spaces
\end{todolist}

\begin{figure}
  \centering
  \vbox{%
  \includegraphics[width=.6\linewidth]{Demo2}%
  \sepping%
  \includegraphics[width=.6\linewidth]{Demo1}%
  }
  \caption{The slider application: dragging the slider changes the
    amount of text to be processed. Left: the \ac{KPA}, right: the
    default algorithm.}
\label{fig:interaction-plain}
\end{figure}

Line breaking is a process where, mostly, elements of a text string
are processed in an ordered manner. Is is thus possible to emulate the
stream of text that is processed by varying the text string's length.
A demo application has been implemented that allows to choose the
length of the text using a slider (see~\autoref{fig:interaction-plain}).
From the upper to the lower part, the slider has been dragged to the
right, effectively augmenting the text to be rendered.
That way, it is possible to monitor the behavior of both algorithms
available. Moreover, one key property of the \ac{KPA} can directly
experienced: adding words to the end of a text can affect the line
breaking of \emph{previous} lines. This will never happen in
traditional algorithms. This application forms the presentation basis
for the implemented visualizations.

\begin{figure}
  \centering
  \includegraphics[height=6\baselineskip]{Demo3}%
  \hfil
  \includegraphics[height=6\baselineskip]{Demo4}
  \caption{Example visualization of aspects of the \ac{KPA}. Left: \emph{box}
nodes are highlit by black rectangles around the text; \emph{glue}
nodes are denotet as orange rectangles. Right:  The number next to
each line denotes the \emph{stretch ratio} applied to that line.}
  \label{fig:example-vis}
\end{figure}

Visualizing the \ac{KPA} is a temporal application, \ie, not every
time the \ac{KPA} is used for a text morph its visualization is
desirable. Additionally, there are different aspects of the algorithm
to be visualized that are not of the same interest every time. Seeing
that, several ContextJS layers have been implemented, each visualizing
a specific algorithm aspect individually. For example, in
\autoref{fig:example-vis}, the left part visualized the \emph{box}
nodes (black rectangles around the text) and the \emph{glue} nodes
(orange rectangles) of the text portion processed by the \ac{KPA}. The
right part, however, visualized the \emph{stretch ratio} applied to
each line (cf.~\cite{Knuth+1982:Breaking-paragr}).


\begin{figure}
  \centering
  \includegraphics[width=.55\linewidth]{Full}
  \caption{All visualization layers impemented have been applied to
    the text; different aspects of the \ac{KPA} are, thus, visualized
    simultaneously.}
  \label{fig:full}
\end{figure}

These layers can be combined easily. Hence, a general visualization as
in \autoref{fig:full} can be built up. In the figure mentioned, the
following visualization layers are used:

\begin{enumerate}
\item \lstinline|TeXBoxVisualizationLayer| Highlighting boxes and
  glues, cf. the left part of \autoref{fig:example-vis}.
\item \lstinline|TeXRatioVisualizationLayer| Putting the stretch
  ratio of each line beside it, cf. the right part of \autoref{fig:example-vis}.
\item \lstinline|TeXToleranceVisualizationLayer| Displaying the
  currently used \emph{tolerance value} at the top left of the text.
  In \autoref{fig:full}, it is the 2 in the upper left. Note that the
  tolerance value determines what stretch ratio is considered
  acceptable for lines at all.
\end{enumerate}

All these layers can be activated, individually or all at once, while
using the slider application mentioned above. That way, the change of
the individual status and values used or produced during the line
breaking algorithm can be monitored easily by just dragging the
slider---a \emph{lively} visualization of the \ac{KPA}.

\section{Related Work}
\label{sec:related-work}

\begin{todolist}{related}
\item 
  \begin{itemize}
  \item kpa: here
  \item extended kpa by han teh than
  \item hz-programm: non-public
  \item InDesign: non-public, yet kpa-based
  \end{itemize}
\item impl \begin{itemize}
  \item \TeX
  \item typeset
  \item xml-fop ??
  \end{itemize}
\item {Legibility in the web}\begin{itemize}
  \item hyphenator
  \item hyph+typeset
  \end{itemize}
\end{todolist}

Line breaking has to be done in nearly every text-displaying
application. However, especially text related programs have to deal
with line breaking. Incidentally, non-trivial algorithms like the
\ac{KPA} are employed in several applications. \TeX\ and all related
systems make use of the \ac{KPA} or extensions thereof, \eg,
by~\cite{Thanh2000:Micro-typograph}---whether with or without
accompanying hyphenation algorithm. A related algorithm is used in the
(unpublished) \emph{hz-program} by Herman Zapf. The \textsc{dtp}
program InDesign by Adobe is known to be loosely based on the \ac{KPA}
and makes use of the \emph{hz-program}.

Besides the reference implementation for the \ac{KPA}, \TeX, other
implementations exist. TypeSet~\cite{Stein2009:TypeSet} was used as
basis for the \lk implementation presented here. The algorithm is also
implemented by the Apache FOP (XML-Formatting Objects processor).


\section{Wrap Up: Outlook and Summary}
\label{sec:wrap-up}

While directly editing text using the \ac{KPA} is not yet possible;
the roundtrip `use the default algorithm for editing and the \ac{KPA}
for displaying' seems natural---the \ac{KPA} was invented with only
displaying text in mind, not editing. Tool support automating this
roundtrip is to be implemented. For the visualization, more aspects of
the algorithm can be made visual, \eg, the stretch and shrink values
of certain nodes or how the possible breakpoints are acutally
connected.

By means of the work presented, the goal set has been achieved. Using
TypeSet, an implementation of the paragraph layout algorithm used by
\TeX, the \acl{KPA}, has been integrated into the \lk and can
optionally be used everywhere replacing the default algorithm. Also,
three basic visualizations for different aspects of the algorithm are
provided. Together with the simple slider application, this makes a
good starting point for explaining or exploring the \ac{KPA}---while
actually using the algorithm itself.


% \nocite{*}
\bibliography{references}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "Pape_2010_WDE_TeXParagraphLayout"
%%% End: 
