4. Scheme Libraries

4.1. 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.

4.2. Iterative

The iterative version of the Scheme library for WebMapReduce is more similar to other languages. For performance reasons, it uses 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 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.

4.2.1. 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.

4.2.2. Example Usage

(define mapper
  (lambda (key val)
    (emit-words (string-tokenize key))))

(define emit-words
  (lambda (words)
    (if (null? words) #f
         (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)))))

4.3. Functional


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.

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 [1], (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) ... )


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

4.3.1. 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).

4.3.2. 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 +)

Table Of Contents

Previous topic

3. Python Libraries

Next topic

5. C++ Library

This Page