問い合わせ言語で使う論理演算子と基本述語

2年以上も前に、「CatyのJSONストレージとクエリ言語」という記事でCatyの問い合わせ言語とMongoDBの問い合わせ言語を比較したことがありました。また最近、MongoDBを触ったりしています。MongoDBの問い合わせ言語を整理するために、問い合わせ式をラムダ式で書いたりしていたのですが、「JavaScriptに近いラムダ計算系」の方法でJavaScriptに翻訳したものを晒します。

MongoDBの問い合わせ演算子と同じ名前でないものもありますが、対応関係はだいたい見当が付くでしょう。最後のほうの「複合データ構造への述語適用」の部分は説明なしだとちょっと分かりにくいかも。

[追記]説明してない「複合データ構造への述語適用」のArrayCloseとObjectCloseが間違っていたので修正しました。まったくいらんことをしてましたね。

function ArrayClose(x, parr){
  return ArrayOpen(x, isUndefined, parr);
}

function ObjectClose(x, pobj){
  return ObjectOpen(x, isUndefined, pobj);
}

ついでに、引数変数のネーミングについて述べておきます。

1. p, qなどは述語（predicate）です。評価された後はブール値と考えてかまいません。
2. prも述語ですが、これはブール値というよりは1変数関数として考えています。
3. arrはデータの配列。
4. parrは述語の配列。評価された後はブール値の配列と考えてかまいません。

[/追記]

MongoDBには、他に、$mod, $regex, $type, $size なんて演算子もあります。

// queryOps.js (query operations) -*- coding: utf-8 -*-

/*== 無条件 ==*/

function any(x) {
  return true;
}

/*== 論理結合子 ==*/

function _and(x, y) {
  return x && y;
}

function _or(x, y) {
  return x || y;
}

function and(parr) {
  return Fold(parr, true, _and);
}

function or(parr) {
  return Fold(parr, false, _or);
}

function not(p) {
  return !p;
};

function nor(parr) {
  return not(or(parr));
}

/*== 限量子 ==*/

function every(arr, pr) {
  return and(EachItem(arr, function(i, v){return pr(v);}));
}

function some(arr, pr) {
  return or(EachItem(arr, function(i, v){return pr(v);}));
}


/*== 値の比較 ==*/

function eq(x, y){
  return x === y;
};

function lt(x, y) {
  return x < y;
}

function gt(x, y) {
  return lt(y, x);
}

function neq(x, y) {
  return not(eq(x, y));
}

function lte(x, y) {
  return not(gt(x, y));
}

function gte(x, y) {
  return not(lt(x, y));
}


/*== 定義／未定義 ==*/

function isUndefined(x) {
  return  or([eq(x, undefined), eq(x, null)]);
}

function isDefined(x) {
  return not(isUndefined(x));
}


/*== 集合に関する述語 ==*/

function isIn(x, arr){
  return some(arr, function(v){return eq(v, x);});
}

function has(arr, x){
  return isIn(x, arr);
}

function includes(arr1, arr2){
  return  every(arr2, function(e){return isIn(e, arr1);});
}

function isNotIn(x, arr) {
  return not(isIn(x, arr));
}

function hasNot(arr, x) {
  return not(has(arr, x));
}

function isIncluded(arr1, arr2){
  return  includes(arr2, arr1);
}

/*== パスによるアクセス先への述語適用 ==*/

function _extract(x, path) {
  var arr = path.split('.');
  var result = x;
  var p;
  for (var i = 0; i < arr.length; i++) {
    if (result === undefined) break;
    p = arr[i];
    console.debug(p);
    result = result[p];
  }
  return result;
}

function Member(x, path, pr) {
  return pr(_extract(x, path));
}

/*== 複合データ構造への述語適用 ==*/

function ArrayOpen(x, q, parr){
  var result = [];
  for (var i = 0; i < x.length; i++) {
    if (i < parr.length) {
      result.push(Apply(parr[i], [x[i]]));
    } else {
      result.push(Apply(q, [x[i]]));
    }
  }
  return and(result);
}

function ArrayClose(x, parr){
  return ArrayOpen(x, isUndefined, parr);
}

function ObjectOpen(x, q, pobj){

  var result = [];
  for (var p in x) {
    if (pobj.hasOwnProperty(p)) {
      result.push(Apply(pobj[p], [x[p]]));
    } else {
      result.push(Apply(q, [x[p]]));
    }
  }
  return and(result);
}

function ObjectClose(x, pobj){
  return ObjectOpen(x, isUndefined, pobj);
}

論理演算子／基本述語たちの相互関係を見るために、手作業でコールグラフを作りました。黒い矢印がcall（依存性）です（重要性が薄いものは省略している）。赤の両矢印は互いに否定になっているもの、青い両矢印は引数を交換している関係を示します。

原寸大