このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

PFTL: 純関数型テンプレート言語、発端とToy言語

雑記／備忘

テレンス・パー（Terence Parr）の論文 "Enforcing Model-View Separation in Template Engines" (http://www.cs.usfca.edu/~parrt/papers/mvc.templates.pdf) と彼が設計したテンプレート言語／エンジン StringTemplate (http://www.stringtemplate.org/) に強い刺激と示唆を受けました。テレンス・パーの主張にはもう全面的に賛成です。が、StringTemplate は僕の要求に合わないところがあるので、テレンス・パーの方針と精神に従いながら、自分なりにテンプレート言語の仕様を考えることにしました。まー要するに、テンプレート言語を、機能制限された純関数型言語と考え、テンプレートエンジンはその実行系と考えりゃいい、ってことです。

まず、考えを整理するために小さな純関数型言語を提示して、その純関数型言語を足がかりにしてテンプレート言語の仕様を考えることにします。このエントリーの見出しに含まれるPFTLは、Purely Functional Toy Language と Purely Functional Template Language の両方の意味があります。まずは、Toy Language から。続きがたぶんあると思います。

PFToyLのデータ型、式、2つの抽象

PFToyLは：

  1. 基本データ型（スカラー型）はinteger, string, boolean。リテラル表記は常識的なもの。
  2. 複合データ型として配列を持つ。リテラル表記は [x1, ..., xn]
  3. 整数（integer）の足し算「+」と掛け算「*」ができる。
  4. 文字列（string）の連結「++」ができる。
  5. 大域変数（読み取り専用）がある。

このくらいにしておきましょう。演算子「+」「*」「++」は、見やすいように中置記法で使いますが、組み込み関数として扱い、2 + 3 は +(2, 3) と同じだとします。

次はPFToyLの式の例です。

  • 32
  • "Hello, world.\n"
  • true
  • [32, "Hello, world.\n"] （配列の要素の型は一定でなくてもよい）
  • 3*2 + 7
  • "Hello, " ++ whom （whomは変数名）
  • a*x + b （a, x, b は変数名））

これじゃさすがに貧弱すぎるので、制御構造としてifとforeach（map関数）、局所的束縛を作るletを導入します。次もPFToyLの式だとします。foreachの結果は配列である点に注意してください。

  • (let a = 3, b = 7; a*x + b)
  • (if morning; "Good morning" ; default)
  • (foreach a in numbers; a*2)

次に抽象（アブストラクション）ですが、関数とマクロを作る2種類の抽象があるとします。

  • fun(x)(let a = 3, b = 7; a*x + b)
  • fun(morning, default)(if morning; "Good morning" ; default)
  • macro(numbers)(foreach a in numbers; a*2)

funで抽象された式 fun(x)(let a=3, b=7; a*x + b) に対して実引数 x = 2 を渡して評価すると値 13 が返ります。一方、macro(numbers)(foreach a in numbers; a*2) に実引数 numbers = [3, 1, -5] を渡して展開すると式 (foreach a in [3, 1, -5]; a*2) が返ります。後でPFToyLをテンプレート言語に発展させたいので、最初からマクロを入れておくのです。

引数渡しは常に名前付き

このToy Languageの特徴は、関数／マクロへの引数渡しが名前付きパラメータ方式なことです。つまり、f(2, 3) のような呼び出しではなくて f(x = 2, y = 3) の形を使います。引数の順序を気にする必要はありませんが、必ず名前を指定しなくてはなりません。

fun式（例：fun(x, y)(x + y)）もmacro式（例：macro(whom)("Hello, " ++ whom ++ ".\n")）も呼び出すことができますが、呼び出し形式は次のようです。

  • (fun(x, y)(x + y))(x = 2, y = 3)
  • (macro(whom)("Hello, " ++ whom ++ ".\n"))(whom = "Universe")

引数が1つしかないときでも名前を添えるのはバカバカしいですが、それがルールです。

fun式もmacro式もラムダ式と似てますが、通常のラムダ計算と全然違ってしまうのは、アルファ変換ができなくなることです。例えば、(fun(x, y)(x + y))(x = 2, y = 3) は正しい呼び出しですが、fun式をアルファ変換した (fun(z, w)(z + w))(x = 2, y = 3) は正しい呼び出しにはなりません。関数の利用者に無断で束縛変数をリネームすることができないのです。

評価と展開

評価と展開の様子を見るために、Apply, Subst, Eval, Expand という4つの関数を導入します。ただし、これらの関数はPFToyLのなかに含まれる関数ではなくて、PTFoyLの処理系を構成する関数です -- そのことを強調するために大文字から始まる名前を採用しています。

まず、Applyは、PFToyL関数を表現するfun式と引数並び（名前付きパラメータ並び）から、PFToyL関数の戻り値を求める処理系関数です。例えば：

  • Apply('fun(x, y)(x + y)', (x = 2, y = 3)) ⇒ 5

式を単なるデータとして扱うことを強調したいときは、式をシングルクォートで囲むことにします。記号「⇒」は、左側の処理結果が右のようになることです。

マクロに対して同じ働きをする処理系関数をSubstとします。例えば：

  • Subst('macro(x, y)(x + y)', (x = 2, y = 3)) ⇒ '2 + 3'

ここで、⇒の右側は、5 という値ではなくて、式 '2 + 3' です。マクロを呼んでも、行われるのは式の変形（変数の置換）で、計算は実行されません。

Substの場合は、式から式を生み出すだけなので、macro式の本体に自由変数が残っていても問題ありません。

  • Subst('macro(x, y)(a*x + b*y)', (x = 2, y = 3)) ⇒ 'a*2 + b*3'

しかし、Applyはそうはいきません。

  • Apply('fun(x, y)(a*x + b*y)', (x = 2, y = 3)) ⇒ ？？

そこで、Applyの第3引数に変数環境（variable environment; 環境変数じゃないよ!）を指定することにします。変数環境*1とは、(a = -1, b = 5)のような形で、見た目は引数並びと同じです。並び内の順序はどうでもいいので、{a = -1, b = 5} と書いたほうがふさわしいでしょうが、いきがかり上丸括弧とします。変数環境が自由変数に対する値の束縛を提供します。変数の値（値は、整数か文字列か定数の配列）が引数にも変数環境にも見つからないなら、Applyのエラーとなります。

  • Apply('fun(x, y)(a*x + b*y)', (x = 2, y = 3), (a = -1, b = 5)) ⇒ 13
  • Apply('fun(x, y)(a*x + b*y)', (x = 2, y = 3), (a = 4)) ⇒ エラー

Evalは、式eと変数環境Vを引数にとり「変数環境Vのもとでの式eの値」を計算します。具体的に書けば：

  1. eがリテラルとのとき、Eval(e, V) ⇒ e'、ここで、e'はeの値
  2. eが変数で、変数eがVにあるとき、Eval(e, V) ⇒ (Vにおけるeの値)
  3. eが、組み込み関数（演算子）fとその引数a1, a2 からなるとき、Eval(f(a1, a2), V) ⇒ f'(Eval(a1, V), Eval(a2, V))、ここで、f'はfの実体となる関数
  4. eが、fun式fとその引数a1, ..., an からなるとき、Eval(f(a1, ..., an), V) ⇒ Apply(f, (Eval(a1), ..., Eval(an), V)

配列、let式、if式、foreach式も同じように定義できます（メンドーになったので書くの止めた ;^^)。与えられた式に対して、そこに含まれる変数の値が変数環境V内で見つからなかったり、macro式が残っているとEvalはエラーになります。

SubstとExpandは、ApplyとEvalに対応する操作ですが、値の計算をするわけではなくて、式を式として変形します。Subst, Expandの詳しい説明も次の機会にします。

オモチャ言語のオモチャ実装

リテラル、変数、組み込み関数、fun式、それと配列までの評価をErlangで書いてみました。構文エラーするとランタイムエラーを発生させるので、全然実用性がありませんが、構文的に正しい式（を表現するErlangターム）を与えれば評価します。PFToyLの式をどのようなErlangデータで表現してるかは、次のとおりです。

  1. integerリテラル：Erlangの整数（integer）そのもの
  2. stringリテラル： Erlangの文字列（string）そのもの（ただしErlangの文字列はリストのこと）
  3. booleanリテラル： Erlangのブーリアン（boolean）そのもの
  4. 配列： {array, List} という形のタプル、単なるリストでは文字列と区別が付かない。
  5. 変数： Erlangのアトム（atom）
  6. fun式： {fun_, Params, Body} という形のタプル。Paramsは変数（アトム）のリスト。funという綴りはErlangの予約語で使えないので、fun_にしています。
  7. macro式： {macro, Params, Body} という形のタプル
  8. 関数呼び出し： {funcall, Fun, Args} という形のタプル。Argsは実引数のリスト
  9. マクロ呼び出し： {macrocall, Macro, Args} という形のタプル

以下にErlangコード：

[追記 date="後日"]
下のコードから引用：

merge_envs(Env1, Env2) ->
  % 手抜き、proplists:lookup/2 を使うなら、これでもいい。

あっ、いくらなんでも手抜き過ぎた。これは引数順序に全面依存してるから、名前付きパラメータのチェックにはなってませんねーー。次のタイミングで修正版を提示するでしょうが、差し替えはしないことにします。アホやった記念にそのまま残します。

[追記の追記]いや、そこじゃねーよ。問題のダメ関数は：

check_args(Params, Args) ->
  Zipped = lists:zip(Params, Args),
  lists:foreach(fun({Var, {Var, _Val}}) -> ok end, Zipped).

コッチでんがな。[/追記の追記]
[/追記]

%% -*- coding: utf-8 -*-

%% @doc オモチャの純関数型言語
-module(pftoyl).

-export([apply/3, eval/2]).
-compile(export_all).

%%% 型定義

%% @type expr() = term()
%% @type value() = integer() | string() | bool() | {arry, [value()]}
%% @type var() = atom()
%% @type args() = [{var(), expr()}]
%% @type value_args() = [{var(), value()}]
%% @type env() = [{var(), value()}]

%%% 式の構成要素に対応するレコードと
%%% その型定義

%% @type array() = #array{list = [expr()]}
-record(array, {list}).
%% @type fun() = #func_{params = [var()], body = expr()}
-record(fun_, {params, body}). % funは予約語なので使えない
%% @type macro() = #macro{params = [var()], body = expr()}
-record(macro, {params, body}).
%% @type funcall() = #funcall{fun_ = fun(), args = args()}
-record(funcall, {fun_, args}).
%% @type macrocall() = #macrocall{macro = macro(), args = args()}
-record(macrocall, {macro, args}).

%%% 構成要素の種類を判別するErlangマクロ

-define(is_integer(X), is_integer(X)).
-define(is_string(X), is_list(X)).
-define(is_boolean(X), is_boolean(X)).
-define(is_array(X), is_record(X, array)).
-define(is_var(X), is_atom(X)).
-define(is_fun(X), is_record(X, fun_)).
-define(is_macro(X), is_record(X, macro)).
-define(is_funcall(X), is_record(X, funcall)).
-define(is_macrocall(X), is_record(X, macrocall)).


%% @doc 関数と評価済み引数から値を計算する.
%% @spec (fun(), value_args(), env()) -> value()
apply(Fun, ValArgs, Vars) when ?is_fun(Fun) ->
  #fun_{params = Params, body = Body} = Fun,
  check_args(Params, ValArgs),
  NewVars = merge_envs(ValArgs, Vars),
  eval(Body, NewVars).

%% @doc 式を評価する.
%% @spec (Expr::expr(), Vars::env()) -> value()
eval(Expr = Int, _Vars) when ?is_integer(Expr) ->
  Int;
eval(Expr = Str, _Vars) when ?is_string(Expr) ->
  Str;
eval(Expr = Bool, _Vars) when ?is_boolean(Expr) ->
  Bool;
eval(Expr = Var, Vars) when ?is_var(Expr) ->
  get_value(Var, Vars);
eval(Expr = Arr, Vars) when ?is_array(Expr) ->
  #array{list = List} = Arr,
  NewList = lists:map(
    fun(Elm) ->
        eval(Elm, Vars)
    end,
    List),
  #array{list = NewList};
eval({'+', Arg1, Arg2}, Vars) ->
  eval(Arg1, Vars) + eval(Arg2, Vars);
eval({'*', Arg1, Arg2}, Vars) ->
  eval(Arg1, Vars) * eval(Arg2, Vars);
eval({'++', Arg1, Arg2}, Vars) ->
  eval(Arg1, Vars) ++ eval(Arg2, Vars);
eval(Expr = Funcall, Vars) when ?is_funcall(Expr) ->
  #funcall{fun_ = Fun, args = Args} = Funcall,
  % 引数を全部評価しておく
  ValArgs = lists:map(
    fun({Var, Arg}) ->
        {Var, eval(Arg, Vars)}
    end,
    Args),
  ?MODULE:apply(Fun, ValArgs, Vars).

%%% 補助的関数

%% @doc 変数環境から変数の値を取り出す.
%% @spec (var(), env()) -> value()
get_value(V, Vars) ->
  case proplists:lookup(V, Vars) of
    {V, Val} ->
      Val
  end.

%% @doc 2つの環境をマージする
%% @spec (env(), env()) -> env()
merge_envs(Env1, Env2) ->
  % 手抜き、proplists:lookup/2 を使うなら、これでもいい。
  Env1 ++ Env2. 

%% @doc 仮引数（Params）と実引数（Args）の対応をチェックする.
%% 対応が不正なときはエラー。
%% @spec ([var()], args()) -> ok
check_args(Params, Args) ->
  Zipped = lists:zip(Params, Args),
  lists:foreach(fun({Var, {Var, _Val}}) -> ok end, Zipped).

%%% サンプルの式

%% @doc fun(x, y)(x + y) 関数
%% @spec () -> expr()
sample_1() ->
   {fun_, [x, y], {'+', x, y}}.

%% @doc a*x + 3 環境に a, x が必要.
%% @spec () -> expr()
sample_2() ->
  {'+', {'*', a, x}, 3}.

%% @doc (fun(x, y)(x + y))(x = 2, y = 3*5) 環境不要.
%% @spec () -> expr()
sample_3() ->
  {funcall, 
   {fun_, [x, y], {'+', x, y}}, 
   [{x, 2}, {y, {'*', 3, 5}}]}.

%% @doc (fun(x, y)(a*x + b*y))(x = 2, y = 3)
%% 環境に a, b が必要.
%% @spec () -> expr()
sample_4() ->
  {funcall,
   {fun_, [x, y],
    {'+', {'*', a, x}, {'*', b, y}}},
   [{x, 2}, {y, 3}]}.
   
%% @doc (fun(whom)("Hello, " ++ whom ++ endline))(whom = "world")
%% 環境に endline が必要.
%% @spec () -> expr()
sample_5() ->
  {funcall, 
   {fun_, [whom], 
    {'++', "Hello, ",
     {'++', whom, endline}}},
   [{whom, "world"}]}.

%% @doc [a, b, a + b, a*b]
%% 環境に a, b が必要.
%% @spec () -> expr()
sample_6() ->
  {array,
   [a, b, {'+', a, b}, {'*', a, b}]}.

*1:環境の代わりに束縛（bindings）とか値割り当て（valuation）とも言います。