Common Lispを書きながら、Cで考えているとき

Common LispでリストをO(N×M)で処理する実装を改善するため、C言語の配列インデックス操作に切り替えて考えた。
Common Lispは、declareやarefを使えばC言語的な発想をそのままLispのコードに翻訳できる。
抽象的な解法と具体的なチューニングを往復することで、アルゴリズムと実装の両方への理解が深まる。
言語ごとに育つ固有の思考モード（Cならメモリ、Lispならリストへのたたみこみ）を積み重ねることで、言語を超えて使える知識が生まれる。

1. Common Lispで抽象と具体を行き来する

最近、競技プログラミングの問題をCommon Lispで解いています。
ただ、Lispを書きながらも、自然と頭の中ではC言語のような考え方でコンピュータを扱うときがあります。

たとえば、Lispでリストの各要素の出現頻度を数える関数を書きました。

(defun frequency-list (lst M)
  (loop for n from 1 to M
        collect (count n lst)))Code language: Lisp (lisp)

意図は明確なのですが、countが内部でリストを毎回走査するので、全体としてO(N×M)の計算になります¹。
NもMも大きくなると、これが致命的になります。

そこで、配列のメモリ割り当てを見直したり、コンパイラに型ヒントを渡したり、という工夫が必要になります。

そういうときに、頭の中では C言語で処理を考えます

void frequency_array(int *lst, int N, int *v, int M) {
    memset(v, 0, sizeof(int) * (M + 1));
    for (int i = 0; i < N; i++) {
        v[lst[i]]++;
    }
}Code language: Arduino (arduino)

配列を一度走査して、インデックスに直接カウントを積むので、O(N)で済みます。

1.1. Common LispはC言語的にも書ける

この考え方を Lisp に翻訳すると、

(defun frequency-vector (lst M)
  (let ((v (make-array (1+ M) 
                       :element-type 'fixnum 
                       :initial-element 0)))
    (loop for a in lst
          do (incf (aref v a)))
    v))Code language: Lisp (lisp)

配列にarefで直接アクセスして、値を更新しています。
「Cで考えて、Lispに翻訳する」のをさらに進めると、にコンパイラに型情報を渡すこともできます。

(defun frequency-vector (lst M)
  (declare (type fixnum M))
  (let ((v (make-array (1+ M) 
                       :element-type 'fixnum 
                       :initial-element 0)))
    (loop for a fixnum in lst
          do (incf (aref v a)))
    v))Code language: Lisp (lisp)

Common Lispが面白いのは、一つの言語の中で抽象と具体を行き来できるところです。

declareはCommon LispのANSI仕様に含まれる正式な機能です²。
C言語的な考え方で、型のサイズを意識して書けるわけです。

1.2. 抽象化と具象化のマルチパラダイム

Common Lispは、Lisp系言語の中で C++ に似ていると思います³。
それは、いろんなコンセプトを取り入れる「マルチパラダイム」です。

C++は、いわゆる「純粋なC言語」ではありません。
C言語にオブジェクト指向の考え方を加えただけでなく、テンプレートによる関数型的なジェネリックプログラミングまでも含まれています。

Common Lisp も、Schemeのようにミニマルな美しさを哲学にしている「純粋なLisp」と対比すると「煩雑」と言えます。
しかし、その「煩雑さ」によって、手続き的な考え方や、計算機の具体的な実装も自然に記述できる強みも生まれます。

1.3. 参照透過な関数とパフォーマンス

関数は、いつ実行しても同じ結果になるように設計すると読みやすく、正しさも確認しやすいです。
これを、参照透過性といい、多くの設計では、このような関数を組み合わせることで、簡潔に問題を解くことができます。

ただ、簡潔な記述の裏で、毎回新しいリストを作っていたり、同じ計算を何度もしていたりすることもあります。
抽象的なアルゴリズムが同じでも、隠れた走査が積み重なって実質的に別のオーダーになっています。
そこで、どこを純粋に保ってどこを妥協するかの判断が、設計の腕の見せ所になります。

これは、抽象的なアルゴリズムと具体的な実装、その両方を知らないと判断できません。

ハードウェアがどれだけ速くなっても、O(n^2) O(n^3) のアルゴリズムはnが少し増えるだけで追いつかなくなります。
特に、競技プログラミングは制限時間と入力サイズがあり、「このアルゴリズムで通るか」を定量的に考える必要があります。

抽象的に解けたと思っても時間切れ。
具体的なチューニングをしても突破できなくて、また抽象的な解法の見直しに戻る。

その往復が問題を深く理解するプロセスになっているのかもしれません。

2. 言語固有の思考法と言語を超える知識

プログラミング言語を学ぶとき、知識には二種類あります。

一つは、言語を超えて通用する知識です。
配列のインデックスがどう動くか、再帰がスタックをどう消費するか、計算量のオーダーが何を意味するか。
これはLispで書いていても、Cで書いていても、本質的には同じことです。

もう一つは、その言語で自然な思考のモードです。
たとえば、C言語は、使っていると必然的に「メモリのレイアウトを意識する」ようになります⁴。
あるいは、Lispを書くと「リストを畳み込む」という発想が自然に出てくるし、Rubyなら「オブジェクトへのメッセージ」と返り値という考え方。
Haskellを触ると「副作用とは何か」を型として考えるようになる。

これらは、それぞれの言語が強制する思考の型を体験することで生まれ、それを積み重ねることで、どの言語でも通用する知識が生まれます⁵。

Cを深く使わなければ「Cで考える」という引き出しはできません。
その引き出しができて初めて、Lispの中でCの思考を借りられます。

新しい言語を学ぶことは、新しい思考のモードを一つ獲得することです。
それは後から別の文脈で使える道具になります。

2.1. 言語を学ぶ楽しさ

最近、Common Lispで競技プログラミングに挑戦して、改めてこういう発見の楽しさに気づきます。

新しい言語に触れることは、観光に似ています。
見える景色が変わります。
実際に問題を解こうとするから「Cで考えていた」という発見が生まれる。

一つの言語に習熟することと、複数のパラダイムを持つことは、目指すものが違います。
どちらも必要で、後者は前者を積み重ねることでしか得られません。

新しい世界を知ることは楽しい。
その体験が、自分の中に新しい思考の引き出しを作ります。

Common LispのHyperSpec（公式仕様）によると、countはシーケンスを線形に走査します。loopでM回繰り返すと、合計でN×M回の要素アクセスが発生します。 – CLHS: Function COUNT
fixnumはハードウェアがネイティブに扱える整数型で、少なくとも16ビット符号付き整数の範囲を保証します。declareでこの型情報をコンパイラに伝えることで、ボックス化された汎用整数ではなくネイティブ演算を使ったコードが生成されます。Common LispのANSI標準は1994年に確定して以来、更新されていません。 – CLHS: Declaration TYPE
SchemeはGuy L. Steele Jr.とGerald Jay Sussmanが1975年にMITで設計したLisp方言で、ミニマルな仕様を哲学として持ちます。Common Lispは1981年にARPAの主導で複数のLisp実装を統合するために設計が始まり、1994年にANSI標準として確定しました。興味深いことに、Schemeを設計したSteele自身がCommon LispのANSI標準化委員会（X3J13）の委員長を務めています。 – Guy L. Steele Jr. – Wikipedia
プログラミング言語が思考に影響を与えるという考え方は、言語相対性仮説（Sapir-Whorf仮説）のプログラミング言語版として議論されることがあります。自然言語の分野では「言語が思考を制約する」という強い主張は退けられていますが、プログラミング言語については「使う言語が問題の解き方に影響する」という弱い形での相対性は広く受け入れられています。 – Linguistic relativity and programming languages
「ある言語を知らなければ、知らないことすら気づかない概念がある」という観点は、プログラマのEdsger Dijkstraも言及しています。また、”A language that doesn’t affect the way you think about programming is not worth knowing.”（プログラミングへの考え方を変えない言語は学ぶ価値がない）というAlan Perlisの格言がこの考えをよく表しています。 – Linguistic relativity and programming languages