1 files changed, 0 insertions, 695 deletions

diff --git a/gem/ltn012.tex b/gem/ltn012.tex
deleted file mode 100644
index 8027ecc..0000000
--- a/gem/ltn012.tex
+++ /dev/null
@@ -1,695 +0,0 @@
-\documentclass[10pt]{article}
-\usepackage{fancyvrb}
-\usepackage{url}
-\DefineVerbatimEnvironment{lua}{Verbatim}{fontsize=\small,commandchars=\@\#\%}
-\DefineVerbatimEnvironment{C}{Verbatim}{fontsize=\small,commandchars=\@\#\%}
-\DefineVerbatimEnvironment{mime}{Verbatim}{fontsize=\small,commandchars=\$\#\%}
-\newcommand{\stick}[1]{\vbox{\setlength{\parskip}{0pt}#1}}
-\newcommand{\bl}{\ensuremath{\mathtt{\backslash}}}
-\newcommand{\CR}{\texttt{CR}}
-\newcommand{\LF}{\texttt{LF}}
-\newcommand{\CRLF}{\texttt{CR~LF}}
-\newcommand{\nil}{\texttt{nil}}
-
-\title{Filters, sources, sinks, and pumps\\
-      {\large or Functional programming for the rest of us}}
-\author{Diego Nehab}
-
-\begin{document}
-
-\maketitle
-
-\begin{abstract}
-Certain data processing operations can be implemented in the
-form of filters. A filter is a function that can process
-data received in consecutive invocations, returning partial
-results each time it is called.  Examples of operations that
-can be implemented as filters include the end-of-line
-normalization for text, Base64 and Quoted-Printable transfer
-content encodings, the breaking of text into lines, SMTP
-dot-stuffing, and there are many others.  Filters become
-even more powerful when we allow them to be chained together
-to create composite filters. In this context, filters can be
-seen as the internal links in a chain of data transformations.
-Sources and sinks are the corresponding end points in these
-chains. A source is a function that produces data, chunk by
-chunk, and a sink is a function that takes data, chunk by
-chunk. Finally, pumps are procedures that actively drive
-data from a source to a sink, and indirectly through all 
-intervening filters.  In this article, we describe the design of an
-elegant interface for filters, sources, sinks, chains, and
-pumps, and we illustrate each step with concrete examples. 
-\end{abstract}
-
-\section{Introduction}
-
-Within the realm of networking applications, we are often
-required to apply transformations to streams of data. Examples
-include the end-of-line normalization for text, Base64 and
-Quoted-Printable transfer content encodings, breaking text
-into lines with a maximum number of columns, SMTP
-dot-stuffing, \texttt{gzip} compression, HTTP chunked
-transfer coding, and the list goes on.
-
-Many complex tasks require a combination of two or more such
-transformations, and therefore a general mechanism for
-promoting reuse is desirable. In the process of designing
-\texttt{LuaSocket~2.0}, we repeatedly faced this problem.
-The solution we reached proved to be very general and
-convenient. It is based on the concepts of filters, sources,
-sinks, and pumps, which we introduce below. 
-
-\emph{Filters} are functions that can be repeatedly invoked
-with chunks of input, successively returning processed
-chunks of output. Naturally, the result of
-concatenating all the output chunks must be the same as the
-result of applying the filter to the concatenation of all
-input chunks. In fancier language, filters \emph{commute}
-with the concatenation operator. More importantly, filters
-must handle input data correctly no matter how the stream
-has been split into chunks. 
-
-A \emph{chain} is a function that transparently combines the
-effect of one or more filters. The interface of a chain is
-indistinguishable from the interface of its component
-filters.  This  allows a chained filter to be used wherever
-an atomic filter is accepted. In particular, chains can be
-themselves chained to create arbitrarily complex operations.
-
-Filters can be seen as internal nodes in a network through
-which data will flow, potentially being transformed many
-times along the way.  Chains connect these nodes together.
-The initial and final nodes of the network are
-\emph{sources} and \emph{sinks}, respectively.  Less
-abstractly, a source is a function that produces new chunks
-of data every time it is invoked.  Conversely, sinks are
-functions that give a final destination to the chunks of
-data they receive in sucessive calls.  Naturally, sources
-and sinks can also be chained with filters to produce
-filtered sources and sinks.
-
-Finally, filters, chains, sources, and sinks are all passive
-entities: they must be repeatedly invoked in order for
-anything to happen.  \emph{Pumps} provide the driving force
-that pushes data through the network, from a source to a
-sink, and indirectly through all intervening filters.
-
-In the following sections, we start with a simplified
-interface, which we later refine. The evolution we present
-is not contrived: it recreates the steps we ourselves
-followed as we consolidated our understanding of these
-concepts within our application domain. 
-
-\subsection{A simple example}
-
-The end-of-line normalization of text is a good
-example to motivate our initial filter interface. 
-Assume we are given text in an unknown end-of-line
-convention (including possibly mixed conventions) out of the
-commonly found Unix (\LF), Mac OS (\CR), and
-DOS (\CRLF) conventions. We would like to be able to 
-use the folowing code to normalize the end-of-line markers: 
-\begin{quote}
-\begin{lua}
-@stick#
-local CRLF = "\013\010"
-local input = source.chain(source.file(io.stdin), normalize(CRLF))
-local output = sink.file(io.stdout)
-pump.all(input, output)
-%
-\end{lua}
-\end{quote}
-
-This program should read data from the standard input stream
-and normalize the end-of-line markers to the canonic
-\CRLF\ marker, as defined by the MIME standard. 
-Finally, the normalized text should be sent to the standard output
-stream.  We use a \emph{file source} that produces data from
-standard input, and chain it with a filter that normalizes
-the data. The pump then repeatedly obtains data from the
-source, and passes it to the \emph{file sink}, which sends
-it to the standard output.
-
-In the code above, the \texttt{normalize} \emph{factory} is a
-function that creates our normalization filter, which 
-replaces any end-of-line marker with the canonic marker. 
-The initial filter interface is
-trivial: a filter function receives a chunk of input data,
-and returns a chunk of processed data.  When there are no
-more input data left, the caller notifies the filter by invoking
-it with a \nil\ chunk. The filter responds by returning
-the final chunk of processed data (which could of course be
-the empty string).
-
-Although the interface is extremely simple, the
-implementation is not so obvious. A normalization filter
-respecting this interface needs to keep some kind of context
-between calls. This is because a chunk boundary may lie between 
-the \CR\ and \LF\ characters marking the end of a single line. This
-need for contextual storage motivates the use of
-factories: each time the factory is invoked, it returns a
-filter with its own context so that we can have several
-independent filters being used at the same time.  For
-efficiency reasons, we must avoid the obvious solution of 
-concatenating all the input into the context before
-producing any output chunks. 
-
-To that end, we break the implementation into two parts:
-a low-level filter, and a factory of high-level filters. The
-low-level filter is implemented in C and does not maintain
-any context between function calls. The high-level filter
-factory, implemented in Lua, creates and returns a
-high-level filter that maintains whatever context the low-level
-filter needs, but isolates the user from its internal
-details. That way, we take advantage of C's efficiency to
-perform the hard work, and take advantage of Lua's
-simplicity for the bookkeeping.
-
-\subsection{The Lua part of the filter}
-
-Below is the complete implementation of the factory of high-level
-end-of-line normalization filters:
-\begin{quote}
-\begin{lua}
-@stick#
-function filter.cycle(lowlevel, context, extra)
-  return function(chunk)
-    local ret
-    ret, context = lowlevel(context, chunk, extra)
-    return ret
-  end
-end
-%
-
-@stick#
-function normalize(marker)
-  return filter.cycle(eol, 0, marker)
-end
-%
-\end{lua}
-\end{quote}
-
-The \texttt{normalize} factory simply calls a more generic
-factory, the \texttt{cycle}~factory, passing the low-level
-filter~\texttt{eol}. The \texttt{cycle}~factory receives a
-low-level filter, an initial context, and an extra
-parameter, and returns a new high-level filter.  Each time
-the high-level filer is passed a new chunk, it invokes the
-low-level filter with the previous context, the new chunk,
-and the extra argument.  It is the low-level filter that
-does all the work, producing the chunk of processed data and
-a new context. The high-level filter then replaces its
-internal context, and returns the processed chunk of data to
-the user.  Notice that we take advantage of Lua's lexical
-scoping to store the context in a closure between function
-calls.  
-
-\subsection{The C part of the filter}
-
-As for the low-level filter, we must first accept
-that there is no perfect solution to the end-of-line marker
-normalization problem. The difficulty comes from an
-inherent ambiguity in the definition of empty lines within
-mixed input. However, the following solution works well for
-any consistent input, as well as for non-empty lines in
-mixed input. It also does a reasonable job with empty lines
-and serves as a good example of how to implement a low-level
-filter.
-
-The idea is to consider both \CR\ and~\LF\ as end-of-line
-\emph{candidates}.  We issue a single break if any candidate
-is seen alone, or if it is followed by a different
-candidate.  In other words, \CR~\CR~and \LF~\LF\ each issue
-two end-of-line markers, whereas \CR~\LF~and \LF~\CR\ issue
-only one marker each.  It is easy to see that this method
-correctly handles the most common end-of-line conventions.
-
-With this in mind, we divide the low-level filter into two
-simple functions.  The inner function~\texttt{pushchar} performs the
-normalization itself. It takes each input character in turn,
-deciding what to output and how to modify the context. The
-context tells if the last processed character was an
-end-of-line candidate, and if so, which candidate it was.
-For efficiency, we use Lua's auxiliary library's buffer
-interface: 
-\begin{quote}
-\begin{C}
-@stick#
-@#define candidate(c) (c == CR || c == LF)
-static int pushchar(int c, int last, const char *marker, 
-    luaL_Buffer *buffer) {
-  if (candidate(c)) {
-    if (candidate(last)) {
-      if (c == last) 
-        luaL_addstring(buffer, marker);
-      return 0;
-    } else {
-      luaL_addstring(buffer, marker);
-      return c;
-    }
-  } else {
-    luaL_pushchar(buffer, c);
-    return 0;
-  }
-}
-%
-\end{C}
-\end{quote}
-
-The outer function~\texttt{eol} simply interfaces with Lua.
-It receives the context and input chunk (as well as an
-optional custom end-of-line marker), and returns the
-transformed output chunk and the new context.
-Notice that if the input chunk is \nil, the operation
-is considered to be finished. In that case, the loop will
-not execute a single time and the context is reset to the
-initial state.  This allows the filter to be reused many
-times: 
-\begin{quote}
-\begin{C}
-@stick#
-static int eol(lua_State *L) {
-  int context = luaL_checkint(L, 1);
-  size_t isize = 0;
-  const char *input = luaL_optlstring(L, 2, NULL, &isize);
-  const char *last = input + isize;
-  const char *marker = luaL_optstring(L, 3, CRLF);
-  luaL_Buffer buffer;
-  luaL_buffinit(L, &buffer);
-  if (!input) {
-    lua_pushnil(L);
-    lua_pushnumber(L, 0);
-    return 2;
-  }
-  while (input < last)
-    context = pushchar(*input++, context, marker, &buffer);
-  luaL_pushresult(&buffer);
-  lua_pushnumber(L, context);
-  return 2;
-}
-%
-\end{C}
-\end{quote}
-
-When designing filters, the challenging part is usually 
-deciding what to store in the context. For line breaking, for
-instance, it could be the number of bytes that still fit in the
-current line.  For Base64 encoding, it could be a string
-with the bytes that remain after the division of the input
-into 3-byte atoms. The MIME module in the \texttt{LuaSocket}
-distribution has many other examples. 
-
-\section{Filter chains}
-
-Chains greatly increase the power of filters.  For example,
-according to the standard for Quoted-Printable encoding,
-text should be normalized to a canonic end-of-line marker
-prior to encoding.  After encoding, the resulting text must
-be broken into lines of no more than 76 characters, with the
-use of soft line breaks (a line terminated by the \texttt{=}
-sign).  To help specifying complex transformations like
-this, we define a chain factory that creates a composite
-filter from one or more filters.  A chained filter passes
-data through all its components, and can be used wherever a
-primitive filter is accepted.
-
-The chaining factory is very simple. The auxiliary
-function~\texttt{chainpair} chains two filters together,
-taking special care if the chunk is the last.  This is
-because the final \nil\ chunk notification has to be
-pushed through both filters in turn:  
-\begin{quote}
-\begin{lua}
-@stick#
-local function chainpair(f1, f2)
-  return function(chunk)
-    local ret = f2(f1(chunk))
-    if chunk then return ret
-    else return ret .. f2() end
-  end
-end
-%
-
-@stick#
-function filter.chain(...)
-  local f = select(1, ...) 
-  for i = 2, select('@#', ...) do
-    f = chainpair(f, select(i, ...))
-  end
-  return f
-end
-%
-\end{lua}
-\end{quote}
-
-Thanks to the chain factory, we can
-define the Quoted-Printable conversion as such:
-\begin{quote}
-\begin{lua}
-@stick#
-local qp = filter.chain(normalize(CRLF), encode("quoted-printable"), 
-  wrap("quoted-printable"))
-local input = source.chain(source.file(io.stdin), qp)
-local output = sink.file(io.stdout)
-pump.all(input, output)
-%
-\end{lua}
-\end{quote}
-
-\section{Sources, sinks, and pumps}
-
-The filters we introduced so far act as the internal nodes
-in a network of transformations. Information flows from node
-to node (or rather from one filter to the next) and is
-transformed along the way. Chaining filters together is our
-way to connect nodes in this network. As the starting point
-for the network, we need a source node that produces the
-data. In the end of the network, we need a sink node that
-gives a final destination to the data.
-
-\subsection{Sources}
-
-A source returns the next chunk of data each time it is
-invoked. When there is no more data, it simply returns~\nil.  
-In the event of an error, the source can inform the
-caller by returning \nil\ followed by the error message.
-
-Below are two simple source factories. The \texttt{empty} source
-returns no data, possibly returning an associated error
-message. The \texttt{file} source yields the contents of a file 
-in a chunk by chunk fashion:
-\begin{quote}
-\begin{lua}
-@stick#
-function source.empty(err)
-  return function()
-    return nil, err
-  end
-end
-%
-
-@stick#
-function source.file(handle, io_err)
-  if handle then 
-    return function()
-      local chunk = handle:read(2048)
-      if not chunk then handle:close() end
-      return chunk
-    end
-  else return source.empty(io_err or "unable to open file") end
-end
-%
-\end{lua}
-\end{quote}
-
-\subsection{Filtered sources}
-
-A filtered source passes its data through the
-associated filter before returning it to the caller. 
-Filtered sources are useful when working with
-functions that get their input data from a source (such as
-the pumps in our examples). By chaining a source with one or
-more filters, such functions can be transparently provided
-with filtered data, with no need to change their interfaces. 
-Here is a factory that does the job:
-\begin{quote}
-\begin{lua}
-@stick#
-function source.chain(src, f)
-  return function()
-    if not src then 
-      return nil 
-    end
-    local chunk, err = src()
-    if not chunk then 
-      src = nil
-      return f(nil)
-    else 
-      return f(chunk) 
-    end
-  end
-end
-%
-\end{lua}
-\end{quote}
-
-\subsection{Sinks}
-
-Just as we defined an interface for a source of data, we can
-also define an interface for a data destination.  We call
-any function respecting this interface a sink. In our first
-example, we used a file sink connected to the standard
-output. 
-
-Sinks receive consecutive chunks of data, until the end of
-data is signaled by a \nil\ input chunk. A sink can be
-notified of an error with an optional extra argument that
-contains the error message, following a \nil\ chunk.  
-If a sink detects an error itself, and
-wishes not to be called again, it can return \nil,
-followed by an error message. A return value that
-is not \nil\ means the sink will accept more data.
-
-Below are two useful sink factories. 
-The table factory creates a sink that stores
-individual chunks into an array. The data can later be
-efficiently concatenated into a single string with Lua's
-\texttt{table.concat} library function. The \texttt{null} sink 
-simply discards the chunks it receives:
-\begin{quote}
-\begin{lua}
-@stick#
-function sink.table(t)
-  t = t or {}
-  local f = function(chunk, err)
-    if chunk then table.insert(t, chunk) end
-    return 1
-  end
-  return f, t
-end
-%
-
-@stick#
-local function null()
-  return 1
-end
-
-function sink.null()
-  return null
-end
-%
-\end{lua}
-\end{quote}
-
-Naturally, filtered sinks are just as useful as filtered
-sources. A filtered sink passes each chunk it receives
-through the associated filter before handing it down to the
-original sink.  In the following example, we use a source
-that reads from the standard input.  The input chunks are
-sent to a table sink, which has been coupled with a
-normalization filter.  The filtered chunks are then
-concatenated from the output array, and finally sent to
-standard out:
-\begin{quote}
-\begin{lua}
-@stick#
-local input = source.file(io.stdin)
-local output, t = sink.table()
-output = sink.chain(normalize(CRLF), output)
-pump.all(input, output)
-io.write(table.concat(t))
-%
-\end{lua}
-\end{quote}
-
-\subsection{Pumps}
-
-Although not on purpose, our interface for sources is
-compatible with Lua iterators. That is, a source can be
-neatly used in conjunction with \texttt{for} loops.  Using
-our file source as an iterator, we can write the following
-code:
-\begin{quote}
-\begin{lua}
-@stick#
-for chunk in source.file(io.stdin) do
-  io.write(chunk)
-end
-%
-\end{lua}
-\end{quote}
-
-Loops like this will always be present because everything 
-we designed so far is passive. Sources, sinks, filters: none
-of them can do anything on their own. The operation of
-pumping all data a source can provide into a sink is so
-common that it deserves its own function:
-\begin{quote}
-\begin{lua}
-@stick#
-function pump.step(src, snk)
-  local chunk, src_err = src()
-  local ret, snk_err = snk(chunk, src_err)
-  if chunk and ret then return 1
-  else return nil, src_err or snk_err end
-end
-%
-
-@stick#
-function pump.all(src, snk, step)
-    step = step or pump.step
-    while true do
-        local ret, err = step(src, snk)
-        if not ret then
-            if err then return nil, err
-            else return 1 end
-        end 
-    end
-end
-%
-\end{lua}
-\end{quote}
-
-The \texttt{pump.step} function moves one chunk of data from
-the source to the sink. The \texttt{pump.all} function takes
-an optional \texttt{step} function and uses it to pump all the
-data from the source to the sink. 
-Here is an example that uses the Base64 and the
-line wrapping filters from the \texttt{LuaSocket}
-distribution.  The program reads a binary file from
-disk and stores it in another file, after encoding it to the
-Base64 transfer content encoding:
-\begin{quote}
-\begin{lua}
-@stick#
-local input = source.chain(
-  source.file(io.open("input.bin", "rb")), 
-  encode("base64"))
-local output = sink.chain(
-  wrap(76),
-  sink.file(io.open("output.b64", "w")))
-pump.all(input, output)
-%
-\end{lua}
-\end{quote}
-
-The way we split the filters here is not intuitive, on
-purpose.  Alternatively, we could have chained the Base64
-encode filter and the line-wrap filter together, and then
-chain the resulting filter with either the file source or
-the file sink. It doesn't really matter. 
-
-\section{Exploding filters}
-
-Our current filter interface has one serious shortcoming.
-Consider for example a \texttt{gzip} decompression filter.
-During decompression, a small input chunk can be exploded
-into a huge amount of data. To address this problem, we
-decided to change the filter interface and allow exploding
-filters to return large quantities of output data in a chunk
-by chunk manner. 
-
-More specifically, after passing each chunk of input to
-a filter, and collecting the first chunk of output, the
-user must now loop to receive other chunks from the filter until no
-filtered data is left. Within these secondary calls, the
-caller passes an empty string to the filter. The filter
-responds with an empty string when it is ready for the next
-input chunk. In the end, after the user passes a
-\nil\ chunk notifying the filter that there is no
-more input data, the filter might still have to produce too
-much output data to return in a single chunk. The user has
-to loop again, now passing \nil\ to the filter each time,
-until the filter itself returns \nil\ to notify the
-user it is finally done.
-
-Fortunately, it is very easy to modify a filter to respect
-the new interface. In fact, the end-of-line translation
-filter we presented earlier already conforms to it.  The
-complexity is encapsulated within the chaining functions,
-which must now include a loop. Since these functions only
-have to be written once, the user is rarely affected.
-Interestingly, the modifications do not have a measurable
-negative impact in the performance of filters that do
-not need the added flexibility. On the other hand, for a
-small price in complexity, the changes make exploding
-filters practical.
-
-\section{A complex example}
-
-The LTN12 module in the \texttt{LuaSocket} distribution
-implements all the ideas we have described. The MIME
-and SMTP modules are tightly integrated with LTN12, 
-and can be used to showcase the expressive power of filters,
-sources, sinks, and pumps. Below is an example 
-of how a user would proceed to define and send a
-multipart message, with attachments, using \texttt{LuaSocket}:
-\begin{quote}
-\begin{mime}
-local smtp = require"socket.smtp"
-local mime = require"mime"
-local ltn12 = require"ltn12"
-
-local message = smtp.message{
-  headers = {
-    from = "Sicrano <sicrano@example.com>",
-    to = "Fulano <fulano@example.com>",
-    subject = "A message with an attachment"},
-  body = {
-    preamble = "Hope you can see the attachment" .. CRLF,
-    [1] = {
-      body = "Here is our logo" .. CRLF},
-    [2] = {
-      headers = {
-        ["content-type"] = 'image/png; name="luasocket.png"',
-        ["content-disposition"] = 
-          'attachment; filename="luasocket.png"',
-        ["content-description"] = 'LuaSocket logo',
-        ["content-transfer-encoding"] = "BASE64"},
-      body = ltn12.source.chain(
-        ltn12.source.file(io.open("luasocket.png", "rb")),
-        ltn12.filter.chain(
-          mime.encode("base64"),
-          mime.wrap()))}}}
-
-assert(smtp.send{
-  rcpt = "<fulano@example.com>",
-  from = "<sicrano@example.com>",
-  source = message})
-\end{mime}
-\end{quote}
-
-The \texttt{smtp.message} function receives a table
-describing the message, and returns a source. The
-\texttt{smtp.send} function takes this source, chains it with the
-SMTP dot-stuffing filter, connects a socket sink
-with the server, and simply pumps the data. The message is never 
-assembled in memory.  Everything is produced on demand, 
-transformed in small pieces, and sent to the server in chunks, 
-including the file attachment which is loaded from disk and 
-encoded on the fly. It just works.
-
-\section{Conclusions}
-
-In this article, we introduced the concepts of filters,
-sources, sinks, and pumps to the Lua language. These are
-useful tools for stream processing in general. Sources provide
-a simple abstraction for data acquisition. Sinks provide an
-abstraction for final data destinations. Filters define an
-interface for data transformations.  The chaining of
-filters, sources and sinks provides an elegant way to create
-arbitrarily complex data transformations from simpler
-components. Pumps simply push the data through.  
-
-\section{Acknowledgements}
-
-The concepts described in this text are the result of  long
-discussions with David Burgess. A version of this text has
-been released on-line as the Lua Technical Note 012, hence
-the name of the corresponding LuaSocket module, LTN12.  Wim
-Couwenberg contributed to the implementation of the module,
-and Adrian Sietsma was the first to notice the
-correspondence between sources and Lua iterators. 
-
-
-\end{document}