Commits

Anonymous committed 5f1e987

first commit

  • Participants

Comments (0)

Files changed (9)

+# Makefile for Sphinx documentation
+#
+
+# You can set these variables from the command line.
+SPHINXOPTS    =
+SPHINXBUILD   = sphinx-build
+PAPER         =
+BUILDDIR      = build
+
+# Internal variables.
+PAPEROPT_a4     = -D latex_paper_size=a4
+PAPEROPT_letter = -D latex_paper_size=letter
+ALLSPHINXOPTS   = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) source
+
+.PHONY: help clean html dirhtml singlehtml pickle json htmlhelp qthelp devhelp epub latex latexpdf text man changes linkcheck doctest
+
+help:
+	@echo "Please use \`make <target>' where <target> is one of"
+	@echo "  html       to make standalone HTML files"
+	@echo "  dirhtml    to make HTML files named index.html in directories"
+	@echo "  singlehtml to make a single large HTML file"
+	@echo "  pickle     to make pickle files"
+	@echo "  json       to make JSON files"
+	@echo "  htmlhelp   to make HTML files and a HTML help project"
+	@echo "  qthelp     to make HTML files and a qthelp project"
+	@echo "  devhelp    to make HTML files and a Devhelp project"
+	@echo "  epub       to make an epub"
+	@echo "  latex      to make LaTeX files, you can set PAPER=a4 or PAPER=letter"
+	@echo "  latexpdf   to make LaTeX files and run them through pdflatex"
+	@echo "  text       to make text files"
+	@echo "  man        to make manual pages"
+	@echo "  changes    to make an overview of all changed/added/deprecated items"
+	@echo "  linkcheck  to check all external links for integrity"
+	@echo "  doctest    to run all doctests embedded in the documentation (if enabled)"
+
+clean:
+	-rm -rf $(BUILDDIR)/*
+
+html:
+	$(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html
+	@echo
+	@echo "Build finished. The HTML pages are in $(BUILDDIR)/html."
+
+dirhtml:
+	$(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml
+	@echo
+	@echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml."
+
+singlehtml:
+	$(SPHINXBUILD) -b singlehtml $(ALLSPHINXOPTS) $(BUILDDIR)/singlehtml
+	@echo
+	@echo "Build finished. The HTML page is in $(BUILDDIR)/singlehtml."
+
+pickle:
+	$(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle
+	@echo
+	@echo "Build finished; now you can process the pickle files."
+
+json:
+	$(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json
+	@echo
+	@echo "Build finished; now you can process the JSON files."
+
+htmlhelp:
+	$(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp
+	@echo
+	@echo "Build finished; now you can run HTML Help Workshop with the" \
+	      ".hhp project file in $(BUILDDIR)/htmlhelp."
+
+qthelp:
+	$(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp
+	@echo
+	@echo "Build finished; now you can run "qcollectiongenerator" with the" \
+	      ".qhcp project file in $(BUILDDIR)/qthelp, like this:"
+	@echo "# qcollectiongenerator $(BUILDDIR)/qthelp/COPTYourownCoOPerativeThread.qhcp"
+	@echo "To view the help file:"
+	@echo "# assistant -collectionFile $(BUILDDIR)/qthelp/COPTYourownCoOPerativeThread.qhc"
+
+devhelp:
+	$(SPHINXBUILD) -b devhelp $(ALLSPHINXOPTS) $(BUILDDIR)/devhelp
+	@echo
+	@echo "Build finished."
+	@echo "To view the help file:"
+	@echo "# mkdir -p $$HOME/.local/share/devhelp/COPTYourownCoOPerativeThread"
+	@echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/COPTYourownCoOPerativeThread"
+	@echo "# devhelp"
+
+epub:
+	$(SPHINXBUILD) -b epub $(ALLSPHINXOPTS) $(BUILDDIR)/epub
+	@echo
+	@echo "Build finished. The epub file is in $(BUILDDIR)/epub."
+
+latex:
+	$(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
+	@echo
+	@echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex."
+	@echo "Run \`make' in that directory to run these through (pdf)latex" \
+	      "(use \`make latexpdf' here to do that automatically)."
+
+latexpdf:
+	$(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex
+	@echo "Running LaTeX files through pdflatex..."
+	make -C $(BUILDDIR)/latex all-pdf
+	@echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex."
+
+text:
+	$(SPHINXBUILD) -b text $(ALLSPHINXOPTS) $(BUILDDIR)/text
+	@echo
+	@echo "Build finished. The text files are in $(BUILDDIR)/text."
+
+man:
+	$(SPHINXBUILD) -b man $(ALLSPHINXOPTS) $(BUILDDIR)/man
+	@echo
+	@echo "Build finished. The manual pages are in $(BUILDDIR)/man."
+
+changes:
+	$(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes
+	@echo
+	@echo "The overview file is in $(BUILDDIR)/changes."
+
+linkcheck:
+	$(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck
+	@echo
+	@echo "Link check complete; look for any errors in the above output " \
+	      "or in $(BUILDDIR)/linkcheck/output.txt."
+
+doctest:
+	$(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest
+	@echo "Testing of doctests in the sources finished, look at the " \
+	      "results in $(BUILDDIR)/doctest/output.txt."
+@ECHO OFF
+
+REM Command file for Sphinx documentation
+
+if "%SPHINXBUILD%" == "" (
+	set SPHINXBUILD=sphinx-build
+)
+set BUILDDIR=build
+set ALLSPHINXOPTS=-d %BUILDDIR%/doctrees %SPHINXOPTS% source
+if NOT "%PAPER%" == "" (
+	set ALLSPHINXOPTS=-D latex_paper_size=%PAPER% %ALLSPHINXOPTS%
+)
+
+if "%1" == "" goto help
+
+if "%1" == "help" (
+	:help
+	echo.Please use `make ^<target^>` where ^<target^> is one of
+	echo.  html       to make standalone HTML files
+	echo.  dirhtml    to make HTML files named index.html in directories
+	echo.  singlehtml to make a single large HTML file
+	echo.  pickle     to make pickle files
+	echo.  json       to make JSON files
+	echo.  htmlhelp   to make HTML files and a HTML help project
+	echo.  qthelp     to make HTML files and a qthelp project
+	echo.  devhelp    to make HTML files and a Devhelp project
+	echo.  epub       to make an epub
+	echo.  latex      to make LaTeX files, you can set PAPER=a4 or PAPER=letter
+	echo.  text       to make text files
+	echo.  man        to make manual pages
+	echo.  changes    to make an overview over all changed/added/deprecated items
+	echo.  linkcheck  to check all external links for integrity
+	echo.  doctest    to run all doctests embedded in the documentation if enabled
+	goto end
+)
+
+if "%1" == "clean" (
+	for /d %%i in (%BUILDDIR%\*) do rmdir /q /s %%i
+	del /q /s %BUILDDIR%\*
+	goto end
+)
+
+if "%1" == "html" (
+	%SPHINXBUILD% -b html %ALLSPHINXOPTS% %BUILDDIR%/html
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished. The HTML pages are in %BUILDDIR%/html.
+	goto end
+)
+
+if "%1" == "dirhtml" (
+	%SPHINXBUILD% -b dirhtml %ALLSPHINXOPTS% %BUILDDIR%/dirhtml
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished. The HTML pages are in %BUILDDIR%/dirhtml.
+	goto end
+)
+
+if "%1" == "singlehtml" (
+	%SPHINXBUILD% -b singlehtml %ALLSPHINXOPTS% %BUILDDIR%/singlehtml
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished. The HTML pages are in %BUILDDIR%/singlehtml.
+	goto end
+)
+
+if "%1" == "pickle" (
+	%SPHINXBUILD% -b pickle %ALLSPHINXOPTS% %BUILDDIR%/pickle
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished; now you can process the pickle files.
+	goto end
+)
+
+if "%1" == "json" (
+	%SPHINXBUILD% -b json %ALLSPHINXOPTS% %BUILDDIR%/json
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished; now you can process the JSON files.
+	goto end
+)
+
+if "%1" == "htmlhelp" (
+	%SPHINXBUILD% -b htmlhelp %ALLSPHINXOPTS% %BUILDDIR%/htmlhelp
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished; now you can run HTML Help Workshop with the ^
+.hhp project file in %BUILDDIR%/htmlhelp.
+	goto end
+)
+
+if "%1" == "qthelp" (
+	%SPHINXBUILD% -b qthelp %ALLSPHINXOPTS% %BUILDDIR%/qthelp
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished; now you can run "qcollectiongenerator" with the ^
+.qhcp project file in %BUILDDIR%/qthelp, like this:
+	echo.^> qcollectiongenerator %BUILDDIR%\qthelp\COPTYourownCoOPerativeThread.qhcp
+	echo.To view the help file:
+	echo.^> assistant -collectionFile %BUILDDIR%\qthelp\COPTYourownCoOPerativeThread.ghc
+	goto end
+)
+
+if "%1" == "devhelp" (
+	%SPHINXBUILD% -b devhelp %ALLSPHINXOPTS% %BUILDDIR%/devhelp
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished.
+	goto end
+)
+
+if "%1" == "epub" (
+	%SPHINXBUILD% -b epub %ALLSPHINXOPTS% %BUILDDIR%/epub
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished. The epub file is in %BUILDDIR%/epub.
+	goto end
+)
+
+if "%1" == "latex" (
+	%SPHINXBUILD% -b latex %ALLSPHINXOPTS% %BUILDDIR%/latex
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished; the LaTeX files are in %BUILDDIR%/latex.
+	goto end
+)
+
+if "%1" == "text" (
+	%SPHINXBUILD% -b text %ALLSPHINXOPTS% %BUILDDIR%/text
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished. The text files are in %BUILDDIR%/text.
+	goto end
+)
+
+if "%1" == "man" (
+	%SPHINXBUILD% -b man %ALLSPHINXOPTS% %BUILDDIR%/man
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Build finished. The manual pages are in %BUILDDIR%/man.
+	goto end
+)
+
+if "%1" == "changes" (
+	%SPHINXBUILD% -b changes %ALLSPHINXOPTS% %BUILDDIR%/changes
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.The overview file is in %BUILDDIR%/changes.
+	goto end
+)
+
+if "%1" == "linkcheck" (
+	%SPHINXBUILD% -b linkcheck %ALLSPHINXOPTS% %BUILDDIR%/linkcheck
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Link check complete; look for any errors in the above output ^
+or in %BUILDDIR%/linkcheck/output.txt.
+	goto end
+)
+
+if "%1" == "doctest" (
+	%SPHINXBUILD% -b doctest %ALLSPHINXOPTS% %BUILDDIR%/doctest
+	if errorlevel 1 exit /b 1
+	echo.
+	echo.Testing of doctests in the sources finished, look at the ^
+results in %BUILDDIR%/doctest/output.txt.
+	goto end
+)
+
+:end

File source/conf.py

+# -*- coding: utf-8 -*-
+#
+# COPT: Your own CoOPerative Thread documentation build configuration file, created by
+# sphinx-quickstart on Thu Feb 10 14:51:59 2011.
+#
+# This file is execfile()d with the current directory set to its containing dir.
+#
+# Note that not all possible configuration values are present in this
+# autogenerated file.
+#
+# All configuration values have a default; values that are commented out
+# serve to show the default.
+
+import sys, os
+
+# If extensions (or modules to document with autodoc) are in another directory,
+# add these directories to sys.path here. If the directory is relative to the
+# documentation root, use os.path.abspath to make it absolute, like shown here.
+#sys.path.insert(0, os.path.abspath('.'))
+
+# -- General configuration -----------------------------------------------------
+
+# If your documentation needs a minimal Sphinx version, state it here.
+#needs_sphinx = '1.0'
+
+# Add any Sphinx extension module names here, as strings. They can be extensions
+# coming with Sphinx (named 'sphinx.ext.*') or your custom ones.
+extensions = []
+
+# Add any paths that contain templates here, relative to this directory.
+templates_path = ['_templates']
+
+# The suffix of source filenames.
+source_suffix = '.rst'
+
+# The encoding of source files.
+#source_encoding = 'utf-8-sig'
+
+# The master toctree document.
+master_doc = 'index'
+
+# General information about the project.
+project = u'COPT: Your own CoOPerative Thread'
+copyright = u'2011, Jun Furuse'
+
+# The version info for the project you're documenting, acts as replacement for
+# |version| and |release|, also used in various other places throughout the
+# built documents.
+#
+# The short X.Y version.
+version = '0.1'
+# The full version, including alpha/beta/rc tags.
+release = '0.1'
+
+# The language for content autogenerated by Sphinx. Refer to documentation
+# for a list of supported languages.
+#language = None
+
+# There are two options for replacing |today|: either, you set today to some
+# non-false value, then it is used:
+#today = ''
+# Else, today_fmt is used as the format for a strftime call.
+#today_fmt = '%B %d, %Y'
+
+# List of patterns, relative to source directory, that match files and
+# directories to ignore when looking for source files.
+exclude_patterns = []
+
+# The reST default role (used for this markup: `text`) to use for all documents.
+#default_role = None
+
+# If true, '()' will be appended to :func: etc. cross-reference text.
+#add_function_parentheses = True
+
+# If true, the current module name will be prepended to all description
+# unit titles (such as .. function::).
+#add_module_names = True
+
+# If true, sectionauthor and moduleauthor directives will be shown in the
+# output. They are ignored by default.
+#show_authors = False
+
+# The name of the Pygments (syntax highlighting) style to use.
+pygments_style = 'sphinx'
+
+# A list of ignored prefixes for module index sorting.
+#modindex_common_prefix = []
+
+
+# -- Options for HTML output ---------------------------------------------------
+
+# The theme to use for HTML and HTML Help pages.  See the documentation for
+# a list of builtin themes.
+html_theme = 'sphinxdoc'
+
+# Theme options are theme-specific and customize the look and feel of a theme
+# further.  For a list of options available for each theme, see the
+# documentation.
+#html_theme_options = {}
+
+# Add any paths that contain custom themes here, relative to this directory.
+#html_theme_path = []
+
+# The name for this set of Sphinx documents.  If None, it defaults to
+# "<project> v<release> documentation".
+#html_title = None
+
+# A shorter title for the navigation bar.  Default is the same as html_title.
+#html_short_title = None
+
+# The name of an image file (relative to this directory) to place at the top
+# of the sidebar.
+#html_logo = None
+
+# The name of an image file (within the static path) to use as favicon of the
+# docs.  This file should be a Windows icon file (.ico) being 16x16 or 32x32
+# pixels large.
+#html_favicon = None
+
+# Add any paths that contain custom static files (such as style sheets) here,
+# relative to this directory. They are copied after the builtin static files,
+# so a file named "default.css" will overwrite the builtin "default.css".
+html_static_path = ['_static']
+
+# If not '', a 'Last updated on:' timestamp is inserted at every page bottom,
+# using the given strftime format.
+#html_last_updated_fmt = '%b %d, %Y'
+
+# If true, SmartyPants will be used to convert quotes and dashes to
+# typographically correct entities.
+#html_use_smartypants = True
+
+# Custom sidebar templates, maps document names to template names.
+#html_sidebars = {}
+
+# Additional templates that should be rendered to pages, maps page names to
+# template names.
+#html_additional_pages = {}
+
+# If false, no module index is generated.
+#html_domain_indices = True
+
+# If false, no index is generated.
+#html_use_index = True
+
+# If true, the index is split into individual pages for each letter.
+#html_split_index = False
+
+# If true, links to the reST sources are added to the pages.
+#html_show_sourcelink = True
+
+# If true, "Created using Sphinx" is shown in the HTML footer. Default is True.
+#html_show_sphinx = True
+
+# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True.
+#html_show_copyright = True
+
+# If true, an OpenSearch description file will be output, and all pages will
+# contain a <link> tag referring to it.  The value of this option must be the
+# base URL from which the finished HTML is served.
+#html_use_opensearch = ''
+
+# This is the file name suffix for HTML files (e.g. ".xhtml").
+#html_file_suffix = None
+
+# Output file base name for HTML help builder.
+htmlhelp_basename = 'COPTYourownCoOPerativeThreaddoc'
+
+
+# -- Options for LaTeX output --------------------------------------------------
+
+# The paper size ('letter' or 'a4').
+#latex_paper_size = 'letter'
+
+# The font size ('10pt', '11pt' or '12pt').
+#latex_font_size = '10pt'
+
+# Grouping the document tree into LaTeX files. List of tuples
+# (source start file, target name, title, author, documentclass [howto/manual]).
+latex_documents = [
+  ('index', 'COPTYourownCoOPerativeThread.tex', u'COPT: Your own CoOPerative Thread Documentation',
+   u'Jun Furuse', 'manual'),
+]
+
+# The name of an image file (relative to this directory) to place at the top of
+# the title page.
+#latex_logo = None
+
+# For "manual" documents, if this is true, then toplevel headings are parts,
+# not chapters.
+#latex_use_parts = False
+
+# If true, show page references after internal links.
+#latex_show_pagerefs = False
+
+# If true, show URL addresses after external links.
+#latex_show_urls = False
+
+# Additional stuff for the LaTeX preamble.
+#latex_preamble = ''
+
+# Documents to append as an appendix to all manuals.
+#latex_appendices = []
+
+# If false, no module index is generated.
+#latex_domain_indices = True
+
+
+# -- Options for manual page output --------------------------------------------
+
+# One entry per manual page. List of tuples
+# (source start file, name, description, authors, manual section).
+man_pages = [
+    ('index', 'coptyourowncooperativethread', u'COPT: Your own CoOPerative Thread Documentation',
+     [u'Jun Furuse'], 1)
+]

File source/contents.rst

+.. -*- coding: utf-8 -*-
+
+=============================
+ Originally Planned Contents
+=============================
+
+- Cooperative Thread
+- Polling by select
+- Continuation
+- Scheduler
+- Monadic interface
+- Exception
+- Time-outs
+
+- Thunk
+- Ready thunk queue
+- Timed thunk heap
+- First scheduler
+- On-FD thunk table
+- Full scheduler
+- Deferred by monadic API
+- Advanced topics
+- On-FD with time-out
+- Exception handling
+- Non-IO deferred
+- Threaded deferred

File source/doubly_linked_list.rst

+.. -*- coding: utf-8 -*-
+
+====================
+ Doubly Linked list
+====================
+
+これは今のところ Copt では使いませんが、これくらいはまず腕試しで実装できてほしいかな、というモジュール。
+
+Copt の下準備としていくつかデータ構造を定義しとかないといけません。
+別に必須では無く、基本ライブラリにあるデータ構造を使っても良いのですが、計算量が違うので性能が出なかったりします。
+また、他のライブラリに既にあるものを使ってくれても構いません。
+でも、まあこれくらい自分で書けなければ、先に進んでも困ってしまうだけのような気がしますので、出来れば頑張って実装してみてください。
+
+双方向リストを定義してください。
+
+参考: http://en.wikipedia.org/wiki/Doubly-linked_list
+
+定義すべきシグナチャは `S` で与えられていますので、モジュール `Z` の定義を埋めてください。
+正しく実装されていれば、最後の `Test` と `Do_test` モジュールを使って `Z` の正しさを(一部)テストします。
+エラーが出なければ完成と思ってよいでしょう。計算量のチェックはしていませんが、、、
+
+ヒント:
+- 基本は Wikipedia の説明の通りに実装する
+- Null の代わりに option 型を使う。Null check の代わりにパターンマッチを使います。
+- `length` が O(1) なので、長さ情報を持っておく必要がある
+- `[ `Already_removed | `Ok ]` は polymorphic variant の型。普通の variant と同じように使えるが、事前の型定義を必要としない。
+- iter や fold には labeled argument を使っています。引数の順番が入れ替えられるので便利です。不慣れなら使う必要はありません。
+- モジュールを良く知らない人は、とりあえずあまり気にせずに穴埋め問題的に Z の中で S の型を持つプログラムを書いていけばよいです。
+- 贅沢に改行して大体 150行位かな?
+- ポインタの張り替え忘れに注意。そういう意味ではやっぱり purely functional data structure の方がいいですねえ。
+- `node` は自分がどの `t` に属しているか、もしくは削除されてしまったか知っています。そのため、 `remove` には `t` は必要ありません。
+- ポインタの比較には physical equality `(==)` `(!=)` を使うのを忘れずに! Structural equality `(=)` `(<>)` では無限ループに陥ってしまいます。
+
+
+.. code-block:: ocaml
+
+   (* doubly linked list *)
+   
+   module type S = sig
+   
+     type 'a t
+       (** The type of the dllist *)
+   
+     type 'a node
+       (** The type of the dllist node *)
+   
+     val create : unit -> 'a t
+       (** Create an empty dllist *)
+   
+     val length : 'a t -> int
+       (** O(1). The length of the dllist *)
+   
+     val is_empty : 'a t -> bool
+   
+     val list : 'a node -> 'a t option
+       (** [list node] returns [Some t] if [node] is an element of [t].
+           If [node] is removed, it returns [None]. *)
+   
+     val is_removed : 'a node -> bool
+   
+     val value : 'a node -> 'a
+       (** Get the value from the node *)
+   
+     val add : 'a t -> 'a -> 'a node
+       (** O(1). [add t v] adds [v] to dllist [t] and returns the newly created
+           node for [v]. The node is used to remove the value from [t] in constant
+           time.
+       *)
+   
+     val remove : 'a node -> [ `Already_removed | `Ok ]
+       (** O(1). [remove node] removes [node] from the dllist it belongs to.
+           Successful removal returns [`Ok]. If the node is already removed,
+           [remove node] returns [`Already_removed]. *)
+   
+     val hd : 'a t -> 'a node option
+       (** [hd t] returns the first node of the dllist [t]. *)
+   
+     val iter : f:('a node -> unit) -> 'a t -> unit
+       (** Iteration over the nodes of a dllist from the top to the bottom *)
+   
+     val fold : f:('a -> 'b node -> 'a) -> init:'a -> 'b t -> 'a
+       (** Folding the nodes of a dllist from the top to the bottom *)
+   
+     val fold_rev : f:('a -> 'b node -> 'a) -> init:'a -> 'b t -> 'a
+       (** Folding the nodes of a dllist from the bottom to top *)
+   
+     (** list <=> dllist conversion functions *)
+     val to_nodes : 'a t -> 'a node list
+     val to_list : 'a t -> 'a list
+     val of_list : 'a list -> 'a t
+   
+     val invariant : 'a t -> unit
+       (** Invariant checks *)
+   
+   end
+   
+   module Z = struct
+     (** Implement Z by yourself !!! *)
+   end
+   
+   module Test(Z:S) = struct
+   
+     open Z
+   
+     (* to_list . of_list must be idempotent *)
+     let () =
+       let ints =
+         let rec ints acc = function
+           | 0 -> acc
+           | n -> ints (n::acc) (n-1)
+         in
+         ints [] 10000
+       in
+       let t = of_list ints in
+       invariant t;
+       assert (to_list (of_list ints) = ints)
+     ;;
+   
+   
+     (* random add/removal test *)
+     let () =
+       let t = create () in
+       (* get a random element of a list, one path *)
+       let random_in_list = function
+         | [] -> None
+         | x::xs ->
+             let rec random_in_list len cand = function
+               | [] -> cand
+               | x::xs ->
+                   (* cand survives : len/(len+1) *)
+                   (* x overrides : 1/(len+1) *)
+                   let cand =
+                     if Random.int (len+1) = 0 then x
+                     else cand
+                   in
+                   random_in_list (len+1) cand xs
+             in
+             Some (random_in_list 1 x xs)
+       in
+   
+       let rec loop added rev_current = function
+         | 10000 -> rev_current
+         | n ->
+             invariant t;
+             if Random.int 3 = 0 then begin
+               let rev_current =
+                 match random_in_list added with
+                 | None -> rev_current
+                 | Some node ->
+                     let removed = is_removed node in
+                     match removed, remove node with
+                     | true, `Already_removed -> rev_current
+                     | false, `Ok ->
+                         List.filter (fun x -> x != node) rev_current
+                     | _ -> assert false
+               in
+               loop added rev_current n
+             end else
+               let node = add t n in
+               loop (node :: added) (node :: rev_current) (n+1)
+       in
+       let rev_current = loop [] [] 0 in
+       invariant t;
+       assert (to_list t = List.rev_map value rev_current);
+       (* remove all the elements remaining *)
+       let rec f rev_current =
+         match random_in_list rev_current with
+         | None -> assert (is_empty t)
+         | Some node ->
+             assert (remove node = `Ok);
+             invariant t;
+             f (List.filter (fun x -> x != node) rev_current)
+       in
+       f rev_current
+     ;;
+   
+     (* misc test *)
+     let () =
+       let t = create () in
+       assert (is_empty t);
+   
+       let ints = [1;2;3;4;5;6;7;8;9;10] in
+       let t = of_list ints in
+   
+       let s = ref [] in
+       iter t ~f:(fun node -> s := value node :: !s);
+       assert (List.rev ints = !s);
+   
+       assert (55 = fold t ~init:0 ~f:(fun acc node -> acc + value node));
+       assert (ints = fold_rev t ~init:[] ~f:(fun acc node -> value node :: acc))
+     ;;
+   end
+   
+   module Do_test = Test(Z)
+   

File source/index.rst

+.. -*- coding: utf-8 -*-
+.. COPT: Your own CoOPerative Thread documentation master file, created by
+   sphinx-quickstart on Thu Feb 10 14:51:59 2011.
+   You can adapt this file completely to your liking, but it should at least
+   contain the root `toctree` directive.
+
+COPT: Your own CoOPerative Thread
+=================================
+
+Contents:
+
+.. toctree::
+   :maxdepth: 2
+
+   contents
+   doubly_linked_list
+   what_is_copt
+   thunk
+   timed_heap
+   
+      
+   
+   
+
+Indices and tables
+==================
+
+* :ref:`genindex`
+* :ref:`modindex`
+* :ref:`search`
+

File source/thunk.rst

+.. -*- coding: utf-8 -*-
+
+=======
+ Thunk
+=======
+
+Thunk
+=====
+
+関数型言語で協調スレッドを実装するのは結構簡単で、 **Thunk** と言う物を使います。Thunk は lazy evaluation でよく使われる言葉ですが、「未だ実行されていない計算」の事です。協調スレッドの奥底ではこの Thunk を作ったり、消費(実際に実行)したりして、並行性を実装します。
+
+.. code-block:: ocaml
+
+   module Thunk : sig
+     type t = unit -> unit
+     val run : t -> unit
+   end = struct
+     type t = unit -> unit
+     let run t = t ()
+   end
+
+簡単ですね。 `Thunk.t` は `unit -> unit` という関数の型を持ち、それを実行するには `Thunk.run` を使いますが、引数 ``()`` を渡すだけです。シグナチャで `type t` の実装を隠蔽してもいいんですが、あまりに簡単だし、いいでしょう。
+
+Ready queue
+===========
+
+Copt では実行待ち状態にあるスレッドは `Thunk.t` の形でプールに溜めておき、実行可能な状態になったらプールから取り出し、 `Thunk.run` で実行します。この待ちスレッドプールを Ready queue と呼びましょう。
+
+.. code-block:: ocaml
+
+   module Ready : sig
+     type t
+     val create : unit -> t
+     val add : t -> Thunk.t -> unit
+     val take : t -> Thunk.t option (* None if the queue is empty *)
+   end = struct
+   (* 自分で実装してね *)
+   end
+
+実装と言っても、スタンダードライブラリにある Queue モジュールをちょっと使うだけです。
+
+協調スレッドのスケジューラはこの Ready queue に実行準備の整った Thunk を足していき、実行時には queue から Thunk を取り出して `Thunk.run` で走らせます。Queue にしたのは、先に加えられた仕事は先に実行された方が一般的なスケジューリングとして良いからです。Thunk 間に優先順位をつけて高優先順位の Thunk は早めに選ばれる、といった、より凝ったスケジューリングのためには、単に Queue ではなく、もっと複雑なデータ構造が必要になるでしょう。
+
+The first Scheduler
+===================
+
+では最初のスケジューラを実装してみましょう。あまりに簡単なので大したことはできませんが、この `Scheduler` を改良して、最終的に面白い協調スレッドライブラリを作っていきます:
+
+.. code-block:: ocaml
+
+   module Scheduler : sig
+     type t
+     val create : unit -> t
+     val add : t -> Thunk.t -> unit
+     val run : t -> unit
+   end = struct
+     (* 自分で実装してね *)
+   end
+   
+`Scheduler.t` は当然内部に `Ready.t` を持ちます、というか、現時点では ``type t = Ready.t`` でよろしい。 `Scheduler.add` は `Ready.add` と同じです。 `Scheduler.run` は、
+
+- Ready queue から thunk を取ってくる。なければ終了
+- Thunk を走らせる
+- Thunk の実行が終わったら初めに戻る
+
+というループです。
+
+Scheduler を使う
+================
+
+`Scheduler` が出来たら、早速遊んでみましょう:
+
+.. code-block:: ocaml
+
+   let t = Scheduler.create ()
+   
+   let cntr = ref 0
+   
+   let rec incrementer () =
+     incr cntr;
+     Scheduler.add t incrementer
+   ;;
+   
+   let rec fizzbuzzer () =
+     begin match !cntr with
+     | ...
+     end;
+     Scheduler.add t fizzbuzzer
+   ;;
+   
+   let () =
+     Scheduler.add t incrementer;
+     Scheduler.add t fizzbuzzer;
+     Scheduler.run t
+   ;;
+   
+こんな感じです。ポイントは
+
+- 各スレッドでは、スレッド切り替えを行って欲しいところで、Scheduler.add を使ってその先の実行を別のスレッドとして登録し、一旦終了する。
+- 初期に走らせたいスレッドを Scheduler.add で全部準備する。
+- 準備が整ったら、 Scheduler.run () でスレッドを走らせる。
+
+これだけです。
+
+うまくいっていれば、 `incrementer` と `fizzbuzzer` の作った thunk が交互に実行されるはずです。
+
+Scheduler.t の隠蔽
+==================
+
+上の例を見れば、スケジューラは `Scheduler.create ()` で一度作られてから、常に同じ物を使っているのが判ると思います。同じ物をわざわざ Scheduler module の関数にいちいち渡すのは面倒ですね。なので、Scheduler モジュールに手を加えて、スケジューラをモジュール Scheduler 内のグローバル変数に定義してしまって、その上で外からは見えないように隠蔽してしまいましょう。上の実装にちょちょいと手を入れるだけです:
+
+.. code-block:: ocaml
+
+   module Scheduler : sig
+     val add : Thunk.t -> unit
+     val run : unit -> unit
+   end = struct
+     type t = ...
+     let create () = ...
+     let t = create ()
+     let add thunk = ...
+     let run () = ...
+   end
+   
+スケジューラは Scheduler モジュール内で ``let t = create ()`` として定義されていますが、シグナチャで隠蔽されているので外からは見えません。 `add` と `run` 関数はこの `t` を使うように改造すると、引数が一つづつ減りますね。この改良版 Scheduler を使うとさっきの Fizzbuzz の例が少し簡単になります:
+
+.. code-block:: ocaml
+
+   let cntr = ref 0
+   
+   let rec incrementer () =
+     incr cntr;
+     Scheduler.add incrementer
+   ;;
+   
+   let rec fizzbuzzer () =
+     begin match !cntr with
+     | ...
+     end;
+     Scheduler.add fizzbuzzer
+   ;;
+   
+   let () =
+     Scheduler.add incrementer;
+     Scheduler.add fizzbuzzer;
+     Scheduler.run ()
+   ;;
+   
+現時点では Ready queue とそれをスケジュールする簡単な Scheduler しかありませんから、入出力や時間を使ったもっと面白い協調スレッドプログラムは書けません。それでも、この実装を元にしてだんだんと使えるものにしていきますのでお楽しみに。

File source/timed_heap.rst

+.. -*- coding: utf-8 -*-
+
+============
+ Timed heap
+============
+
+さて、初めてのスケジューラはうまく動いたでしょうか。動いたといっても、 `incrementer` と `fizzbuzzer` が交互に動くだけで、さほど面白い物ではなかったかもしれません。でも、ここからは時間によるスケジューリングを考えます。これが入るとグッと楽しいことができるようになりますし、仕上げであるファイル入出力に関したスケジューリングの下準備にもなります。
+
+時間によるスケジューリングでは、何時何分にこの協調スレッドを動かせ、とスケジューラに指示を行います。時間の型を time とすると(実際は float です)、未実行のスレッドは Thunk.t で表せますから、 time * Thunk.t の組 (timed thunk と呼びましょうか。) をスケジューラは管理しなければなりません。そのためのコンテナ型が必要になります。すぐに実行可能な Thunk.t を貯めておくデータ型はキューでした。では timed thunk のコンテナには何が良いでしょう?キューではありません。
+
+Heap
+====
+
+スケジューラが、この timed thunk のコンテナにどうアクセスから実行可能な thunk を取り出すかが鍵になります。例えば、ある時刻 t にスケジューラが行うべき事は何でしょうか。そうです、もし `t` より前の時刻の timed thunk があれば、それを実行する様にスケジュールしなければいけませんね。そのためには、timed thunk のコンテナは、ある時刻 t を与えたときに、それより前の時刻を持つ timed thunk を簡単に(少ない計算量で)取り出せる様なデータ構造であることが望ましい事がわかります。そのためには timed thunk が内部で時刻順にソートされているようなコンテナ構造が欲しくなります。Heap (ヒープ)が正にそのようなコンテナ構造を提供します:
+
+- Binary heap: http://en.wikipedia.org/wiki/Binary_heap
+
+ウィキペディアや他の大抵の情報で解説されているヒープの実装方法はあまり関数型な物ではありませんが、heap は純粋関数的な実装が可能です。Chris Okasaki の Purely functional data structures 等を参考にしてください。(本の方がお勧めですけれども、彼のD論の68ページ、6.2.2 Binomial Heaps でも良いです。) OCaml での実装(そしてあなたにこれを埋めて欲しいのですが)はこんな感じになります:
+
+.. code-block:: ocaml
+
+   module Make(O : sig
+     type t
+     val compare : t -> t -> int
+   end) : sig
+   
+     type t
+     val invariant : t -> unit
+       (** invariant check function *)
+     val empty : t
+     val merge : t -> t -> t
+     val add : t -> O.t -> t
+       (** O(log(n)) *)
+     val peek_min : t -> O.t option
+       (** O(1) : [peek_min t] returns [None] if [t] is empty.
+           Otherwise, returns the minimum element of [t] *)
+     val take_min : t -> (O.t * t) option
+       (** O(1) : [take_min t] returns [None] if [t] is empty.
+           Otherwise, returns the minimum element of [t] and the heap without the minimum element. *)
+   
+     val to_list : t -> O.t list
+     val of_list : O.t list -> t
+   end = struct
+   
+   (* Implement by yourself *)
+   
+   end
+   
+- ファンクタを使っています。ファンクタ Make に元になるデータ型とその大小比較関数を引数として渡すことで、その型と大小関係を利用したヒープのモジュールを生成できます。例えば、
+  
+  .. code-block:: ocaml
+
+  	 module Int_heap = Make(struct type t = int let compare x y = compare (x : int) y end)
+
+  とすると整数を要素に持つヒープを作れます。 ``struct ... end`` の中ではファンクタ引数であるモジュール O を仮定して型や関数を定義していきます。
+
+- Purely functional なデータ構造なので、双方向リストを実装したときのような mutable な要素はありません。アルゴリズムさえ理解すればバグも少なく素直に実装を書くことができるでしょう。
+
+次のテストが通ればオッケーでしょう。多分。
+
+.. code-block:: ocaml
+
+   let test () =
+     let compare x y = compare (x:int) y in
+     let module H = Make(struct type t = int let compare = compare end) in
+     let module L = struct
+       (* implementation by list. very slow *)
+       type t = int list
+       let add (t:t) x = List.sort compare (x::t)
+       let peek_min = function
+         | x::_xs -> Some x
+         | _ -> None
+       let take_min = function
+         | x::xs -> Some (x,xs)
+         | _ -> None
+       let of_list l = List.sort compare l
+       let to_list l = l
+     end in
+     let rec loop h l = function
+       | 0 ->
+           assert (H.to_list h = L.to_list l)
+       | n ->
+           match Random.int 3 with
+           | 0 ->
+               assert (H.peek_min h = L.peek_min l);
+               begin match H.take_min h, L.take_min l with
+               | None, None -> ()
+               | Some (x,h), Some (y,l) ->
+                   assert (x = y);
+                   loop h l (n-1)
+               | _ -> assert false
+               end
+           | _ ->
+               let r = Random.int 1000 in
+               let h = H.add h r in
+               let l = L.add l r in
+               loop h l (n - 1)
+     in
+     let list =
+       let rec iter acc = function
+         | 0 -> acc
+         | n -> iter (Random.int 1000 :: acc) (n - 1)
+       in
+       iter [] 1000
+     in
+     let h = H.of_list list in
+     let l = L.of_list list in
+     assert (H.to_list h = L.to_list l);
+     loop h l 10000
+   ;;
+
+   let () = test (); prerr_endline "Heap test passed"
+
+Timed heap
+==========
+
+.. code-block:: ocaml
+
+   type time = float
+   
+   module Timed : sig
+     type t
+     val add : t -> time -> Thunk.t -> unit
+     val get_expired : t -> time -> (time * Thunk.t) list
+     val next_expiration : t -> time option
+   end = struct
+     (* Write it yourself! *)
+   end
+   
+Timed scheduler loop
+====================
+
+Ready queue の他に Timed heap も必要になる
+
+- Timed heap から現在の時刻より前に実行されることになっている Thunk を get_expired で取り出し、Ready queue に加える
+- Ready queue に Thunk があれば run する。
+- Ready queue が空であれば、Timed.next_expiration を使って次の Timed thunk が実行される時間を取り出す
+- もし Timed thunk も無ければ、全ての Thunk が実行終了しているので、スケジューラループも終了する
+- 次の Timed thunk 実行時間まで待ち、初めに戻る
+
+Unix
+====
+
+- 現在時間の取得 `Unix.gettimeofday ()`
+- ``sec`` 秒待つ ``ignore (Unix.select [] [] [] sec)``
+- リンク方法 
+
+  .. code-block:: bash
+
+     $ ocamlc unix.cma copt.ml / ocamlopt unix.cmxa
+
+Extend your example
+===================
+
+- incrementer and fizzbuzzer call themselves with 1.0 second
+- add another timed thunk to print "Tick" once 10 seconds
+

File source/what_is_copt.rst

+.. -*- coding: utf-8 -*-
+
+=================================
+ Cooperative thread の概念の説明
+=================================
+
+これすごい草稿なんで、というか、現時点はパスしてほしい。
+
+非常に簡単な並列プログラムを考えます
+
+- カウンタを増やし続けるループ
+- カウンタを読んで FizzBuzz するループ
+
+もちろん普通はこの二つの事は一つのループに入れて実行しますね。例えば:
+
+.. code-block:: ocaml
+
+   let cntr = ref 0
+   let rec fizzbuzz () =
+     incr cntr;
+     Printf.eprintf "%d\n"
+       (match !cntr mod 3, !cntr mod 5 with
+       | 0, 0 -> "FizzBuzz"
+       | 0, _ -> "Fizz"
+       | _, 0 -> "Buzz"
+       | _ -> string_of_int !cntr);
+     fizzbuzz ()
+   let () = fizzbuzz ()
+   ;;
+
+が、仕事によっては並行して行わせたいということがあります。その為に `thread` を使いますね。
+
+.. code-block:: ocaml
+
+   (* このプログラムは安全ではありません。念のため *)
+   let cntr = ref 0
+
+   let rec incrementer () =
+     incr cntr;
+     Thread.yield (); (* 本質的には必要ありませんが、スレッドの切り替えをスムーズにするときに使います *)
+     incrementer ()
+   ;;
+
+   let rec fizzbuzzer () =
+     Printf.eprintf "%d\n"
+       (match !cntr mod 3, !cntr mod 5 with
+       | 0, 0 -> "FizzBuzz"
+       | 0, _ -> "Fizz"
+       | _, 0 -> "Buzz"
+       | _ -> string_of_int !cntr);
+     Thread.yield ();
+     fizzbuzz ()
+   ;;
+
+   let () =
+     let th1 = Thread.create incrementer () in
+     let th2 = Thread.create fizzbuzzer () in
+     Thread.join th1 th2
+   ;;
+
+このプログラムはカウンタをひたすら増やしていく `incrementer` とカウンタの中身を見て `fizzbuzz` 言う `fizzbuzzer` の二つのスレッドを作成し、同時に走らせます。コンパイルには、 `fizzbuzz.ml` と言う名前で保存して、
+
+.. code-block:: bash
+   
+   $ ocamlopt -thread unix.cmxa threads.cmxa fizzbuzz.ml
+
+とすると ``a.out`` が出来ますので、試してみてください。
+
+さて、スレッドによる並行計算と言いますが、実は何かが同時に並行に行われているわけではありません。(マルチコアの CPU でも乗っていて、スレッド実行がマルチコアに対応していない限り。) CPU は一時に一つのスレッドの実行しか行いません。実行されるスレッドをごく短時間で切り替えることで、あたかも並列にスレッドが実行されているように見える、というのが並列スレッドの本当のところですね。
+
+じゃあ、並行プログラムはスレッドでトドメを刺すかと言うと、そうでもありません。たとえば、上のプログラムは間違っています。リファレンス cntr が提供する状態は二つのスレッドで共有されており、云々。困ったことにこの例では lock を掛けなくてもプログラムがクラッシュしないので、良い例ではありません。
+
+で、ほんとは lock を掛け忘れていてクラッシュする OCaml プログラムを例に使いたいんだけど、、、上手く書けない。
+
+そこで、ロックを掛けなくても並行に計算する方法として、協調スレッドと言う物がこのごろ流行っています。(実を言うと昔の Mac OS はこの協調スレッドのような物でして、別に新しい物でもなんでもないのですが、、、)
+
+Copt ではこの協調スレッドライブラリを自分で組んでみよう、という企画なのです。
+
+協調スレッドでは POSIX スレッドは(ほとんど)使いません。スレッドの実行の管理はプログラム自身が持っているスケジューラによって行います。POSIX スレッドは使いませんから、各協調スレッドの実行切り替えは言語外の仕組みで自動的に行われるわけではありません。各協調スレッドが、そろそろ俺実行飽きたから他のヤツに実行を移してよ、と明示的に宣言して初めてスレッド切り替えが行われます。
+
+協調スレッドの利点と欠点を挙げておきます:
+
+- ロックなどの忘れやすい、そしてバグフィックスしにくい機構を必要としない
+- 明示的にスレッドを切り替える必要がある: スレッドで無限ループしてしまうと、他の協調スレッドに実行が移りません
+
+後者は昔の Mac OS で良く起こっていました…アプリが死ぬと全体が死ぬことが良くあった。
+
+なんか適当なメモになっていますが、、、いつか直すことはあるのか知らん
+
+で、OCaml で協調スレッドです。
+
+先ほどの fizzbuzz の例を持ってきます:
+
+.. code-block:: ocaml
+
+   let cntr = ref 0
+
+   let rec incrementer () =
+     incr cntr;
+     incrementer ()
+   ;;
+
+   let rec fizzbuzzer () =
+     Printf.eprintf "%s\n"
+       (match !cntr mod 3, !cntr mod 5 with
+       | 0, 0 -> "FizzBuzz"
+       | 0, _ -> "Fizz"
+       | _, 0 -> "Buzz"
+       | _ -> string_of_int !cntr);
+     fizzbuzz ()
+   ;;
+
+この二つの関数の実行を並列に行いたい。もちろんこのままでは並列に動きません。両方とも無限ループですので、どちらかを初めに実行するともう片方は永遠に実行されない。なので、この無限ループを細かい仕事の列に代えてやる必要があります。
+
+