memo - social-snippet/social-snippet GitHub Wiki

========================================================== ソーシャルなスニペットシステム "Social Snippet"

Hiroyuki Sano (The University of Aizu, Computer Science and Engineering)

概要

% % I. Social Snippet とは %

Social Snippet は各種開発環境から横断的に利用することができるスニペットシステムです。主に ACM-ICPC (以下 ICPC) などのプログラミングコンテストで出題される問題を解くために活用することを想定して開発しています。

""" ACM-ICPC とは、ACMという計算機学会が主催する、International Collegiate Programming Contest (国際大学対抗プログラミングコンテスト)という名前のプログラミングコンテストです。同じ大学で３人一組のチームを作り、チームでプログラミングと問題解決の能力を競う大会です。全世界で毎年3万人以上が参加する大会に成長しています。 """ (ICPCについて、http://icpc.iisf.or.jp/acm-icpc/ より引用）

プログラミングコンテストで解答となるソースコードを提出するときは、 1つの問題に対して1つのソースファイルを提出するという形式が一般的です。また、プログラムを実行して採点するような形式のプログラミングコンテストでは、標準ライブラリ以外のライブラリファイルの使用は認められていません。

そのため、競技者は各自で用意したライブラリをコピーしたり直接書き写すことによって1つのソースファイルにまとめる必要があります。

Social Snippet はスニペットとして断片的なテキストをまとめることで、誰でもライブラリを配布することができるシステムです。GitHubを使って作成したライブラリを検索・共有することができます。

% % II. オープンソース・ソフトウェアとしての Social Snippet の目標 %

ICPCは1977年から毎年開催されている歴史のあるプログラミングコンテストで、限られた時間内に、与えられた問題に対して解答となるアルゴリズムを設計し、それをプログラムとして実装するスピードや技術を競います。先に書いた通り、ICPCだけでも世界中から毎年 3万人以上の学生が参加しており、その競技人口は現在も増加傾向にあります。

ICPCのようなプログラミングコンテストは一般的に"Competitive Programming"と呼ばれ、日本では "競技プログラミング" という名前で親しまれています。プログラミングコンテストで役に立つアルゴリズムやデータ構造について解説した "プログラミングコンテストチャレンジブック" という書籍は1万部を超える売れ行きとなっています。

また、国内企業が採用活動の一環としてICPCのようなプログラミングコンテストを主催したり、選考過程でコンテストの成績を評価することも増えてきています。しかし、残念なことに、コンテストで培ったアルゴリズムの技術や知識をOSSの世界でも活用しようとする空気や風潮はまだありません。

プログラミングコンテストで良い成績を収めた人が、良いソフトウェアを作れるとは思っていません。でも、アルゴリズムに関する知識や技術はOSSにおいても役に立つはずです。むしろOSSで開発されているライブラリのようなソフトウェアこそ、アルゴリズム実装の知見を活かすことで、多くの人に恩恵を与えるような改善ができる余地があるのではないでしょうか。

私は、プログラミングコンテストの参加者が身につけた技術を活用できる場としてOSSの世界に興味を持ってもらうために、OSSの側からアプローチできるのではないかという考えから、Social Snippet というプロジェクトに取り組んでいます。

いわゆるバザール方式のソフトウェア開発における「集合知によるソフトウェアの改善」というのはOSSの中で最も素晴らしい文化だと思っています。このような考え方をプログラミングコンテストの世界へ持ち込んで普及させることが私の目標です。

反対に、プログラミングコンテストの参加者がOSSの世界へ進むための取っ掛かりとして、この Social Snippet というオープンソース・ソフトウェアを育てることで、OSSをさらに促進し発展させることができたらと思っています。

開発背景

Social Snippet を開発するに至った背景について。

% % I. プログラミングコンテストとの出会いについて %

私は2009年に開催された "パソコン甲子園" という高校生を対象としたプログラミングコンテストへの参加を契機に "Codeforces" や "Google Code Jam" などオンラインで定期的に開催されているプログラミングコンテストにしばしば参加しています。

これまでに私がプログラミングコンテストに参加した回数は250回を超えており、練習で解いた問題を含めると1400問以上のアルゴリズム実装に関する問題を解きました。

私が高校生のときにパソコン甲子園に参加したのは、自分で立ち上げた同好会に何か活動実績を残すのが目的でしたが、運良く予選を通過することができたため全国大会に向けて練習をする必要がありました。

それから、ある掲示板サイトで "TopCoder" という海外のプログラミングコンテストがオンラインで頻繁に開催されているという情報を得て、練習のために過去問を解いてみることにしました。

英語で書かれた問題文を読み解き、自分の解釈を元に解答の方針を立て、解答となるソースコードを書いて提出し、その結果について正解か不正解かを自動的に判定してもらえるのは、プログラミングの練習というよりも英文読解の練習において非常に有効であると感じられました。なぜならプログラミング言語という世界共通の言語を通して、自分の解釈の良し悪しを判断することができるからです。

当時は "Win32" や "DirectX" などの API を利用した Windows アプリケーションのプログラミングに興味があり、ドキュメントである "MSDN" をよく読んでいました。しかし、日本語に翻訳されていないコンテンツに当たったときに、英文で書かれている情報が読めなかったため、英文読解力をつけたいという気持ちを強く持っていました。そのため、海外のプログラミングコンテストの問題を解き、英語の学習につなげることが、大会以降もプログラミングコンテストに参加し続ける強い動機となりました。

% % II. プログラミングコンテストにおけるライブラリ事情とその問題点 %

% A. 国内のプログラミングコンテスト・ライブラリ事情

プログラミングコンテストで解答を提出するときは、1つの問題に対して解答となる1つのソースファイルを提出するという形式が一般的です。また、プログラムを実行して採点するような形式のプログラミングコンテストでは、一般的に標準ライブラリ以外のライブラリファイルの使用は認められていません。そのため、競技者は各自が用意したライブラリをコピーしたり直接書き写すことによって1つのソースファイルにまとめる必要があります。

プログラミングコンテストにおける「ライブラリ」は、テンプレートもしくはスニペットのように断片的なテキスト形式として利用できる必要があり、一般的なプログラミングにおけるライブラリと比べると、その在り方が限定されているのが特徴です。

日本国内におけるプログラミングコンテスト用のライブラリとして有名なものに "Spaghetti Source" があります。これは "ICPC" という大学対抗のプログラミングコンテストで出題される問題を解くために必要な各種アルゴリズムを C++ で実装したソースコードを公開しているウェブサイトで、個人が公開しています。

ICPC では、競技中にインターネット上の情報を参考にして問題を解くことは禁止されていますが、書籍や印刷物を持ち込んで閲覧することは許可されているため、参加者は大会で使用するライブラリを事前に紙に印刷して持ち込んでいます。例年、一部の参加者が大会終了後に各自のライブラリをインターネット上で公開しています。

2009年に発売された "プログラミングコンテストチャレンジブック" という書籍はプログラミングコンテストで使用する典型的なアルゴリズム実装を例題付きで分かり易くまとめあげたもので、広く話題となりプログラミングコンテストの知名度を高めました。この書籍もライブラリとして活用している人を多く見かけます。

% B. 問題点 - テスト手法

上記のライブラリは、いずれも断片的なソースコードのみを公開しているため、テストが十分になされているのか分からず、信頼性を十分に保証できていません。

これらのライブラリをテストするための手法としては、オンラインジャッジと呼ばれるプログラミングコンテスト練習用のシステムを使い、それらのライブラリを利用する問題を解いてソースコードを送信し、正解と判定されるかどうかを確認するという古典的方法があります。例えば、前述した Spaghetti Source では、検証に利用した問題のリストが記載されています。

アルゴリズム実装におけるテストは、テストケースを考える部分に難しさがあります。そのため、オンラインジャッジにある問題集をアルゴリズム実装の信頼性を測るために利用するのは、問題に不備がある場合を考慮し、複数の問題を使って多角的にテストを行うことができれば十分に信頼できる適切な方法だと思います。

しかし、実際はそのようにコードを再利用することを考えずに問題を解くため、大抵の場合は問題を解き直す手間が発生してしまいます。

% C. 問題点 - ライブラリのオープンソースプロジェクト化

個人や少人数によって開発されているプログラミングコンテスト用のライブラリは上記を含め多数ありますが、オープンソースプロジェクトとしてコミュニティにより継続的に改善がなされているものはありません。

その要因として「ライブラリを配布するための基盤」が存在しないことが挙げられます。例えば開発者がライブラリを公開し、ユーザーがそれをダウンロードして各自の環境で利用することができるような仕組みが整備されていません。

これはプログラミングコンテストのライブラリ事情が特殊であり、テキスト形式の断片的なソースコードとして配布する必要があること、そしてユーザーごとに異なる環境でも利用できる形式としてファイルをシステムに展開することが難しいことに起因していると考えています。