.. highlight:: scheme


****************
Scheme Libraries
****************

Variants
========

Since Scheme is a functional programming language, its style is very different
from other languages supported in WebMapReduce. For this reason, two different
libraries are available: one that focuses on making mappers and reducers purely
functional, and another that mimics the iterative styles of other languages.

Iterative
=========

The iterative version of the Scheme library for WebMapReduce is more similar to
other languages. For performance reasons, it uses :dfn:`streams`, special
variants of lists, to expose values to the reducer.

The mapper and reducer must have these signatures:

(mapper key value)
   Maps the pair composed of *key* and *value*. The return value is
   ignored—output should be sent through the **wmr-emit** function.

(reducer key value-stream)
   Reduces the values in *value-stream* associated with the given *key*.
   *value-stream* has the type :dfn:`stream` as defined in `SRFI 41`_. Streams
   can generally be treated like lists, except they require different primitives:
   For example, rather than **car** and **cdr**, use **stream-car** and
   **stream-cdr**. See the text of SRFI 41 for more functions available to
   operate on streams.
   
   Both *key* and the elements of *value-stream* are strings. As with **mapper**,
   the return value is ignored. Use **wmr-emit** for output.

.. _SRFI 41: http://srfi.schemers.org/srfi-41/srfi-41.html

API
---

In addition to standard R6RS scheme, SRFIs 1 (lists), 13 (strings), and 41
(streams), and any other modules included by default in MZScheme, WebMapReduce
provides the following procedure:

(wmr-emit key value \[display-func])
   Output a pair composed of *key* and *value*. Both arguments can be of any
   type, and will be converted to strings and output using the procedure
   *display-func*. If *display-func* is not specified (which is the typical
   use), **display** will be used. Its primary purpose is to allow the use of
   **write**, which enables values to be easily converted from strings back to
   their original types.

Example Usage
-------------

::

   (define mapper
     (lambda (key val)
       (emit-words (string-tokenize key))))
   
   (define emit-words
     (lambda (words)
       (if (null? words) #f
           (begin
            (wmr-emit (car words) "1")
            (emit-words (cdr words))))))

::

   (define reducer
     (lambda (key vals)
       (wmr-emit key (reduce-values 0 vals))))
   
   (define reduce-values
     (lambda (sum vals)
       (if (stream-null? vals) sum
           (reduce-values (+ sum (string->number (stream-car vals)))
                          (stream-cdr vals)))))

Functional
==========

.. warning:: This documentation is outdated. The "Scheme (functional)" library
   now has a slightly different API. The new version will be documented and
   the old version will be re-added before the final 2.0 release.

.. todo:: Update

The functional variant of the Scheme library is much different than those in
other languages. It is patterned after the system described in the paper
*Infusing Parallelism into Introductory Computer Science Curriculum using
MapReduce* [#cite-Johnson]_\ , (albeit with the significant difference that the
job is started through a web interface, rather than using a function within a
scheme interpreter).

Unlike most other languages in WebMapReduce, the types of the intermediate keys
and values *are preserved* (rather than converted to strings) between the map
and reduce phases. In other words, if the values returned by your mapper are
numbers, the values fed to your reducer will be also.

The mapper and reducer must have these signatures:

(mapper pair)
   Maps the key-value pair (a list in the format ``(key value)``) and returns
   the result as a list of key-value pairs like the following::
   
      ((key-1 val-1) (key-2 val-2) ...)
   
   It is of course possible to return ``'()`` for no result.

(reducer next-value accumulator)
   Reduces (accumulates) the two arguments, where *next-value* is the next value
   to reduce and *accumulator* is the result of the previous application of
   **reducer** (if any). The library applies this function to every value for a
   given key, so that the resulting value is equivalent to::
   
      (fold reducer '() values)
   
   Where *values* is the list of the values associated with the key. In other
   words, where the values associated with the key are ``(val-1 val-2 ... val-n)``,
   the resulting value would be::
   
      (reducer val-n ... (reducer val-2 val-1) ... )

.. rubric:: Footnotes

.. [#cite-Johnson] Matthew Johnson, et al., UC Berkeley, 2008.
   http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-34.html

API
---

In addition to standard R6RS scheme, SRFIs 1 (lists) and 13 (strings), and any
other modules included by default in MZScheme, WebMapReduce provides the
following procedures, intended for compatibility with Berkeley's implementation
of map-reduce in Scheme:

(kv-key pair)
    Returns the key portion of the given key-value pair.
    Equivalent to ``(car pair)``.

(kv-value pair)
    Returns the value portion of the given key-value pair.
    Equivalent to ``(cadr pair)``.

(make-kv-pair key value)
    Returns a new key-value pair made from the given
    ``key`` and ``value``. Equivalent to
    ``(list key value)``.

Example Usage
-------------

::

   (define mapper
     (lambda (pair)
       (map-words (string-tokenize (car pair)))))
   
   (define map-words
     (lambda (words)
       (if (null? words) '()
           (cons (list (car words) 1)
                 (map-words (cdr words))))))

::

   (define reducer
     (lambda (next-value accumulator)
       (+ next-value accumulator)))
   
   ;; or equivalently:
   (define reducer +)