#935: Minor documentation bug, odd defn of fibn.
------------------------------+---------------------------------------------
Reporter: tmcooper | Owner:
Type: bug | Status: closed
Priority: normal | Milestone:
Component: Documentation | Version: 6.6
Severity: minor | Resolution: fixed
Keywords: | Difficulty: Easy (1 hr)
Architecture: Multiple | Os: Multiple
------------------------------+---------------------------------------------
Changes (by simonmar):
* resolution: => fixed
* status: new => closed
Old description:
> On this page: http://haskell.org/ghc/docs/6.6/html/users_guide/lang-
> parallel.html
> the function fibn is defined. I assume fibn is meant to give the
> fibonacci sequence, but it doesn't. The problem is the term 'n1 + n2 +
> 1' in the function definition. It should be just 'n1 + n2'. This change
> needs to be made in two places on this page, and additionally, an
> occurence of 'n2 + n1 + 1' needs to be changed to 'n2 + n1'.
>
> In case it is helpful, here is the corrected html.
>
> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
> "http://www.w3.org/TR/html4/loose.dtd";>
> <html><head><meta http-equiv="Content-Type" content="text/html; charset
> =ISO-8859-1"><title>7.15. Parallel Haskell</title><link rel="stylesheet"
> href="lang-parallel_files/fptools.css" type="text/css"><meta
> name="generator" content="DocBook XSL Stylesheets V1.68.1"><link
> rel="start"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/index.html";
> title="The Glorious Glasgow Haskell Compilation System User's Guide,
> Version 6.6"><link rel="up"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/ghc-language-
> features.html" title="Chapter 7. GHC Language Features"><link
> rel="prev"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/monomorphism.html";
> title="7.14. Control over monomorphism"><link rel="next"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/ffi.html";
> title="Chapter 8.
> Foreign function interface (FFI)
> "></head>
> <body alink="#0000ff" bgcolor="white" link="#0000ff" text="black"
> vlink="#840084"><div class="navheader"><table summary="Navigation header"
> width="100%"><tbody><tr><th colspan="3" align="center">7.15. Parallel
> Haskell</th></tr><tr><td align="left" width="20%"><a accesskey="p"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/monomorphism.html";>Prev</a> </td><th
> align="center" width="60%">Chapter 7. GHC Language Features</th><td
> align="right" width="20%"> <a accesskey="n"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/ffi.html";>Next</a></td></tr></tbody></table><hr></div><div
> class="sect1" lang="en"><div class="titlepage"><div><div><h2
> class="title" style="clear: both;"><a name="lang-
> parallel"></a>7.15. Parallel Haskell</h2></div></div></div><a
> class="indexterm" name="id3181622"></a><p>There are two implementations
> of Parallel Haskell: SMP paralellism
> <a class="indexterm" name="id3181636"></a>
> which is built-in to GHC (see <a
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/sec-using-
> smp.html" title="4.12. Using SMP parallelism">Section 4.12,
> “Using SMP parallelism”</a>) and
> supports running Parallel Haskell programs on a single multiprocessor
> machine, and
> Glasgow Parallel Haskell<a class="indexterm" name="id3181653"></a>
> (GPH) which supports running Parallel Haskell
> programs on both clusters of machines or single multiprocessors. GPH
> is
> developed and distributed
> separately from GHC (see <a
> href="http://www.cee.hw.ac.uk/%7Edsg/gph/"; target="_top">The
> GPH Page</a>).</p><p>Ordinary single-threaded Haskell programs will
> not benefit from
> enabling SMP parallelism alone. You must expose parallelism to the
> compiler in one of the following two ways.</p><div class="sect2"
> lang="en"><div class="titlepage"><div><div><h3 class="title"><a
> name="id3181681"></a>7.15.1. Running Concurrent Haskell programs in
> parallel</h3></div></div></div><p>The first possibility is to use
> concurrent threads to structure your
> program, and make sure
> that you spread computation amongst the threads. The runtime will
> schedule the running Haskell threads among the available OS
> threads, running as many in parallel as you specified with the
> <code class="option">-N</code> RTS option.</p></div><div
> class="sect2" lang="en"><div class="titlepage"><div><div><h3
> class="title"><a name="id3181704"></a>7.15.2. Annotating pure code for
> parallelism</h3></div></div></div><p>The simplest mechanism for
> extracting parallelism from pure code is
> to use the <code class="literal">par</code> combinator, which is
> closely related to (and often used
> with) <code class="literal">seq</code>. Both of these are
> available from <a
> href="http://haskell.org/ghc/docs/6.6/html/libraries/base/Control-
> Parallel.html" target="_top"><code
> class="literal">Control.Parallel</code></a>:</p><pre
> class="programlisting">infixr 0 `par`
> infixr 1 `seq`
>
> par :: a -> b -> b
> seq :: a -> b -> b</pre><p>The expression <code class="literal">(x
> `par` y)</code>
> <span class="emphasis"><em>sparks</em></span> the evaluation of
> <code class="literal">x</code>
> (to weak head normal form) and returns <code
> class="literal">y</code>. Sparks are
> queued for execution in FIFO order, but are not executed
> immediately. If
> the runtime detects that there is an idle CPU, then it may convert
> a
> spark into a real thread, and run the new thread on the idle CPU.
> In
> this way the available parallelism is spread amongst the real
> CPUs.</p><p>For example, consider the following parallel version of
> our old
> nemesis, <code class="function">nfib</code>:</p><pre
> class="programlisting">import Control.Parallel
>
> nfib :: Int -> Int
> nfib n | n <= 1 = 1
> | otherwise = par n1 (seq n2 (n1 + n2))
> where n1 = nfib (n-1)
> n2 = nfib (n-2)</pre><p>For values of <code
> class="varname">n</code> greater than 1, we use
> <code class="function">par</code> to spark a thread to evaluate
> <code class="literal">nfib (n-1)</code>,
> and then we use <code class="function">seq</code> to force the
> parent thread to evaluate <code class="literal">nfib (n-2)</code>
> before going on
> to add together these two subexpressions. In this divide-and-
> conquer
> approach, we only spark a new thread for one branch of the
> computation
> (leaving the parent to evaluate the other branch). Also, we must
> use
> <code class="function">seq</code> to ensure that the parent will
> evaluate
> <code class="varname">n2</code> <span
> class="emphasis"><em>before</em></span> <code class="varname">n1</code>
> in the expression <code class="literal">(n1 + n2)</code>. It is
> not sufficient
> to reorder the expression as <code class="literal">(n2 +
> n1)</code>, because
> the compiler may not generate code to evaluate the addends from
> left to
> right.</p><p>When using <code class="literal">par</code>, the
> general rule of thumb is that
> the sparked computation should be required at a later time, but not
> too
> soon. Also, the sparked computation should not be too small,
> otherwise
> the cost of forking it in parallel will be too large relative to
> the
> amount of parallelism gained. Getting these factors right is
> tricky in
> practice.</p><p>More sophisticated combinators for expressing
> parallelism are
> available from the <a
> href="http://haskell.org/ghc/docs/6.6/html/libraries/base/Control-
> Parallel-Strategies.html" target="_top"><code
> class="literal">Control.Parallel.Strategies</code></a> module.
> This module builds functionality around <code
> class="literal">par</code>,
> expressing more elaborate patterns of parallel computation, such as
> parallel <code class="literal">map</code>.</p></div></div><div
> class="navfooter"><hr><table summary="Navigation footer"
> width="100%"><tbody><tr><td align="left" width="40%"><a accesskey="p"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/monomorphism.html";>Prev</a> </td><td
> align="center" width="20%"><a accesskey="u"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/ghc-language-
> features.html">Up</a></td><td align="right" width="40%"> <a
> accesskey="n"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/ffi.html";>Next</a></td></tr><tr><td
> align="left" valign="top" width="40%">7.14. Control over
> monomorphism </td><td align="center" width="20%"><a accesskey="h"
> href="http://haskell.org/ghc/docs/6.6/html/users_guide/index.html";>Home</a></td><td
> align="right" valign="top" width="40%"> Chapter 8.
> Foreign function interface (FFI)
> </td></tr></tbody></table></div></body></html>
New description:
On this page: http://haskell.org/ghc/docs/6.6/html/users_guide/lang-
parallel.html
the function fibn is defined. I assume fibn is meant to give the
fibonacci sequence, but it doesn't. The problem is the term 'n1 + n2 + 1'
in the function definition. It should be just 'n1 + n2'. This change
needs to be made in two places on this page, and additionally, an
occurence of 'n2 + n1 + 1' needs to be changed to 'n2 + n1'.
In case it is helpful, here is the corrected html.
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd";>
<html><head><meta http-equiv="Content-Type" content="text/html; charset
=ISO-8859-1"><title>7.15. Parallel Haskell</title><link rel="stylesheet"
href="lang-parallel_files/fptools.css" type="text/css"><meta
name="generator" content="DocBook XSL Stylesheets V1.68.1"><link
rel="start"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/index.html";
title="The Glorious Glasgow Haskell Compilation System User's Guide,
Version 6.6"><link rel="up"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/ghc-language-
features.html" title="Chapter 7. GHC Language Features"><link rel="prev"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/monomorphism.html";
title="7.14. Control over monomorphism"><link rel="next"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/ffi.html";
title="Chapter 8.
Foreign function interface (FFI)
"></head>
<body alink="#0000ff" bgcolor="white" link="#0000ff" text="black"
vlink="#840084"><div class="navheader"><table summary="Navigation header"
width="100%"><tbody><tr><th colspan="3" align="center">7.15. Parallel
Haskell</th></tr><tr><td align="left" width="20%"><a accesskey="p"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/monomorphism.html";>Prev</a>
</td><th align="center" width="60%">Chapter 7. GHC Language
Features</th><td align="right" width="20%"> <a accesskey="n"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/ffi.html";>Next</a></td></tr></tbody></table><hr></div><div
class="sect1" lang="en"><div class="titlepage"><div><div><h2 class="title"
style="clear: both;"><a name="lang-parallel"></a>7.15. Parallel
Haskell</h2></div></div></div><a class="indexterm"
name="id3181622"></a><p>There are two implementations of Parallel Haskell:
SMP paralellism
<a class="indexterm" name="id3181636"></a>
which is built-in to GHC (see <a
href="http://haskell.org/ghc/docs/6.6/html/users_guide/sec-using-smp.html";
title="4.12. Using SMP parallelism">Section 4.12, “Using SMP
parallelism”</a>) and
supports running Parallel Haskell programs on a single multiprocessor
machine, and
Glasgow Parallel Haskell<a class="indexterm" name="id3181653"></a>
(GPH) which supports running Parallel Haskell
programs on both clusters of machines or single multiprocessors. GPH
is
developed and distributed
separately from GHC (see <a href="http://www.cee.hw.ac.uk/%7Edsg/gph/";
target="_top">The
GPH Page</a>).</p><p>Ordinary single-threaded Haskell programs will
not benefit from
enabling SMP parallelism alone. You must expose parallelism to the
compiler in one of the following two ways.</p><div class="sect2"
lang="en"><div class="titlepage"><div><div><h3 class="title"><a
name="id3181681"></a>7.15.1. Running Concurrent Haskell programs in
parallel</h3></div></div></div><p>The first possibility is to use
concurrent threads to structure your
program, and make sure
that you spread computation amongst the threads. The runtime will
schedule the running Haskell threads among the available OS
threads, running as many in parallel as you specified with the
<code class="option">-N</code> RTS option.</p></div><div
class="sect2" lang="en"><div class="titlepage"><div><div><h3
class="title"><a name="id3181704"></a>7.15.2. Annotating pure code for
parallelism</h3></div></div></div><p>The simplest mechanism for extracting
parallelism from pure code is
to use the <code class="literal">par</code> combinator, which is
closely related to (and often used
with) <code class="literal">seq</code>. Both of these are available
from <a href="http://haskell.org/ghc/docs/6.6/html/libraries/base/Control-
Parallel.html" target="_top"><code
class="literal">Control.Parallel</code></a>:</p><pre
class="programlisting">infixr 0 `par`
infixr 1 `seq`
par :: a -> b -> b
seq :: a -> b -> b</pre><p>The expression <code class="literal">(x
`par` y)</code>
<span class="emphasis"><em>sparks</em></span> the evaluation of
<code class="literal">x</code>
(to weak head normal form) and returns <code
class="literal">y</code>. Sparks are
queued for execution in FIFO order, but are not executed
immediately. If
the runtime detects that there is an idle CPU, then it may convert a
spark into a real thread, and run the new thread on the idle CPU.
In
this way the available parallelism is spread amongst the real
CPUs.</p><p>For example, consider the following parallel version of
our old
nemesis, <code class="function">nfib</code>:</p><pre
class="programlisting">import Control.Parallel
nfib :: Int -> Int
nfib n | n <= 1 = 1
| otherwise = par n1 (seq n2 (n1 + n2))
where n1 = nfib (n-1)
n2 = nfib (n-2)</pre><p>For values of <code
class="varname">n</code> greater than 1, we use
<code class="function">par</code> to spark a thread to evaluate
<code class="literal">nfib (n-1)</code>,
and then we use <code class="function">seq</code> to force the
parent thread to evaluate <code class="literal">nfib (n-2)</code>
before going on
to add together these two subexpressions. In this divide-and-
conquer
approach, we only spark a new thread for one branch of the
computation
(leaving the parent to evaluate the other branch). Also, we must
use
<code class="function">seq</code> to ensure that the parent will
evaluate
<code class="varname">n2</code> <span
class="emphasis"><em>before</em></span> <code class="varname">n1</code>
in the expression <code class="literal">(n1 + n2)</code>. It is not
sufficient
to reorder the expression as <code class="literal">(n2 + n1)</code>,
because
the compiler may not generate code to evaluate the addends from left
to
right.</p><p>When using <code class="literal">par</code>, the
general rule of thumb is that
the sparked computation should be required at a later time, but not
too
soon. Also, the sparked computation should not be too small,
otherwise
the cost of forking it in parallel will be too large relative to the
amount of parallelism gained. Getting these factors right is tricky
in
practice.</p><p>More sophisticated combinators for expressing
parallelism are
available from the <a
href="http://haskell.org/ghc/docs/6.6/html/libraries/base/Control-
Parallel-Strategies.html" target="_top"><code
class="literal">Control.Parallel.Strategies</code></a> module.
This module builds functionality around <code
class="literal">par</code>,
expressing more elaborate patterns of parallel computation, such as
parallel <code class="literal">map</code>.</p></div></div><div
class="navfooter"><hr><table summary="Navigation footer"
width="100%"><tbody><tr><td align="left" width="40%"><a accesskey="p"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/monomorphism.html";>Prev</a>
</td><td align="center" width="20%"><a accesskey="u"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/ghc-language-
features.html">Up</a></td><td align="right" width="40%"> <a accesskey="n"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/ffi.html";>Next</a></td></tr><tr><td
align="left" valign="top" width="40%">7.14. Control over monomorphism
</td><td align="center" width="20%"><a accesskey="h"
href="http://haskell.org/ghc/docs/6.6/html/users_guide/index.html";>Home</a></td><td
align="right" valign="top" width="40%"> Chapter 8.
Foreign function interface (FFI)
</td></tr></tbody></table></div></body></html>
Comment:
Fixed; thanks.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/935>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
