a interesting Parallel Programing Problem: asciify-string

[Xah Lee]

here's a interesting problem that we are discussing at comp.lang.lisp.

〈Parallel Programing Problem: asciify-string〉
http://xahlee.org/comp/parallel_programing_exercise_asciify-string.html

here's the plain text. Code example is emacs lisp, but the problem is
general.

for a bit python relevancy… is there any python compiler that's
parallel-algorithm aware?

-----------------------------------------------
Parallel Programing Problem: asciify-string

Here's a interesting parallel programing problem.

Problem Description

The task is to change this function so it's parallelable. (code
example in emacs lisp)

(defun asciify-string (inputStr)
"Make Unicode string into equivalent ASCII ones."
(setq inputStr (replace-regexp-in-string "á\\|à\\|â\\|ä" "a"
inputStr))
(setq inputStr (replace-regexp-in-string "é\\|è\\|ê\\|ë" "e"
inputStr))
(setq inputStr (replace-regexp-in-string "í\\|ì\\|î\\|ï" "i"
inputStr))
(setq inputStr (replace-regexp-in-string "ó\\|ò\\|ô\\|ö" "o"
inputStr))
(setq inputStr (replace-regexp-in-string "ú\\|ù\\|û\\|ü" "u"
inputStr))
inputStr
)

Here's a more general description of the problem.

You are given a Unicode text file that's a few peta bytes. For certain
characters in the file, they need to be changed to different char.
(For example of practical application, see: IDN homograph attack â—‡
Duplicate characters in Unicode.)

One easy solution is to simply use regex, as the above sample code, to
search thru the file sequentially, and perform the transfrom of a
particular set of chars, then repeat for each char chat needs to be
changed.

But your task is to use a algorithm parallelizable. That is, in a
parallel-algorithm aware language (e.g. Fortress), the compiler will
automatically span the computation to multiple processors.

Refer to Guy Steele's video talk if you haven't seen already. See: Guy
Steele on Parallel Programing.
Solution Suggestions

A better way to write it for parallel programing, is to map a char-
transform function to each char in the string. Here's a pseudo-code in
lisp by Helmut Eller:

(defun asciify-char (c)
(case c
((? ? ? ?) ?a)
((? ? ? ?) ?e)
((? ? ? ?) ?i)
((? ? ? ?) ?o)
((? ? ? ?) ?u)
(t c)))

(defun asciify-string (string) (map 'string #'asciify-string string))

One problem with this is that the function “asciify-char†itself is
sequential, and not 100% parallelizable. (we might assume here that
there are billions of chars in Unicode that needs to be transformed)

It would be a interesting small project, if someone actually use a
parallel-algorithm-aware language to work on this problem, and report
on the break-point of file-size of parallel-algorithm vs sequential-
algorithm.

Anyone would try it? Perhaps in Fortress, Erlang, Ease, Alice, X10, or
other? Is the Clojure parallel aware?

Xah