Chapter 01

関数型と簡易処理系

TAKIZAWA Yozo
TAKIZAWA Yozo
2021.12.07に更新

関数型プログラミングの概要

関数型プログラミングとは,数学で扱う関数と同じ考え方でプログラムを構成・実行するプログラミングパラダイムです.たとえば,手続き型など他のプログラミングパラダイムではお馴染みのはずの代入が関数型には存在しません.変数は存在しますが,数学と同じく,あくまで値の代わりに用いる名前としての役割のみであり,値を格納(代入)する入れ物という役割は想定されていません.関数型における値は,組み合わされた水路を流れる水のみのイメージ,他の多くのパラダイムでは,それに加えて,水を溜めたり取り出したりする場所が水路のあちこちにあるイメージでしょうか.

関数型における値の扱いのメリットは,どのような値がどれくらいやりとりされるかのみを意識すれば良いことで,どこかの場所(メモリ領域)に現在どのような値がどれくらい蓄積され,また,変化しているかを意識する必要がないことです.これは参照透過性と呼ばれています.代入の考え方のあるプログラミングパラダイムでは,同じ処理を行っても,どこかの場所(変数名が指し示すメモリ領域)にある値によって結果が変わってしまうことが多くなり,不具合が発生した際に,今現在の処理に原因があるのか,その処理を行う前の別の処理やメモリ領域に不具合があるのかの区別がつきにくくなります.

デメリットは,値を蓄積・更新する場所がなく,あらゆる値が常になんらかの処理の対象となっていることから,それらの値を必要に応じて一次的に保管し続ける必要があり,メモリ領域の使用効率がとても悪くなることです.『貯水場』がなく,『水路』それ自体が一時的な貯水場所の役割を果たしつつ,常に水が動いたり合流・分配したりしていると捉えれば,その効率の悪さが容易に想像できます.

このため,関数型プログラミングのパラダイムを導入した実用的な言語処理系では,ガーベージコレクションと呼ばれる,不要となったメモリ領域の開放・再利用の仕組みが必須となっています.

本書で用いるプログラミング言語

本書で用いるプログラミング言語は筆者が独自に仕様を定めたもので,関数型プログラミング(functional programming)にかけてfpLISPと呼んでいるLISP系の言語です.関数型に特化した,とても小さい仕様ということもあり,処理系(インタプリタ)は様々なプログラミング言語で比較的容易に実装可能です.開発リポジトリは次の場所にあります.

https://github.com/ytaki0801/fpLISP/
独自の言語仕様および処理系を用いている理由は,実用的なプログラミング言語では他のパラダイムも容易に導入できてしまい,関数型パラダイムに基づく記述表現か否かの区別がつきにくいためです.純関数型プログラミング言語と呼ばれる言語の処理系も同様で,実用性のある言語処理系はどうしてもマルチパラダイムを導入する必要があり,また,処理系によっては,関数型パラダイムの導入を必要最小限に留める必要さえあります(実用的なプログラミング言語に関しては,付録の『他言語との対応』を併せて御参照下さい).

本書で用いるfpLISPは極めて仕様が小さく,明らかに非実用的であるものの,関数型パラダイムの実態をプログラムコードからある程度類推できるようにしています[1].本書の紹介文にもありますように,本書読了後は,他の実用的なプログラミング言語でのパラダイム活用に移行することを想定しています.

サンプルコードの実行方法

ここでは,JavaScriptで実装し,HTMLファイルを通してWebブラウザで利用できる簡易処理系を使用してサンプルコードを実行する方法を示します[2].まず,前節で紹介したリポジトリのJavaScriptディレクトリより,fpLISP.jsfpLISP.htmlを取得します.

両者が同じフォルダ(ディレクトリ)にあることを確認したのち,fpLISP.htmlをWebブラウザで表示させます.

既に記述されているサンプルコードを実行(評価)するには『eval』のボタンをクリックします.評価結果が『Result:』の右側に表示されます.

『clear』ボタンをクリックすると,テキスト領域内の記述コードが全て消去されます(評価結果は消去されません).

テキスト領域内に新たに入力して『eval』ボタンをクリックすると,入力したプログラムコードがあらためて評価されます.注意してほしいのは,最後には必ず空行を入れることと,評価はひとつのまとまったにしか行われないことです.

練習問題

次のfpLISPのコードを実行・評価した結果(『Result:』の右側に表示)を解答して下さい.

fpLISP
(((lambda (u) (u u))
  (lambda (u)
    (lambda (x r)
      (if (eq x 0) r
          ((u u) (- x 1) (cons x r))))))
 10)
脚注
  1. 本書で扱うパラダイムは,正確には『型なしラムダ計算に基づくラムダ式を用いた関数型プログラミング』で,参照透過性を主軸に置いたパラダイムよりも制約があるものとなっています. ↩︎

  2. 次のURLからも利用可能です.http://ytaki0801.github.io/fpLISP.html ↩︎