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.
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:
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.
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:
(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)))))
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.
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:
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.
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) ... )
Footnotes
| [1] | Matthew Johnson, et al., UC Berkeley, 2008. http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-34.html |
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:
(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 +)