無精・短気・傲慢

perlの事 いろいろ

Sugar.pm リファレンス

概要

 Sugar.pm は chabo-dsl の糖衣構文を処理するモジュールです。


関数一覧

関数 説明
convert() 日本語スクリプトをchabo-dsl構文に変換する

convert

機能

日本語スクリプトをchabo-dsl構文に変換する

構文

convert($script)

引数

変換元文字列

戻り値

変換後の文字列を返す

自然言語変換

全角半角変換

  • 全角ASCII → 半角ASCII
  • 全角space → 半角SPACE
  • 、 → 半角SPACE
  • 。 → ;

条件文変換

もし~なら~以外は~

        もし(.+?)(?:なら|の場合|の時|時)(?:は)*(.+?)以外(?:(?:は|で))?

比較演算子

my %jp_op = (
    '未満'     => '<',
    '以下'     => '<=',
    '超える'   => '>',
    '以上'     => '>=',
    '等しい'   => '==',
    '異なる'   => '!=',
    '以外'     => '!=',
    'じゃない' => '!=',
    'でない'   => '!=',
);

論理演算子

my %jp_logical = (
    'で'     => '&&',
    'かつ'   => '&&',
    'か'     => '||',
    'または' => '||',
);

変換例

もし信号が青か緑なら進んでも良い以外で信号が黄なら注意以外は止まれ
   ↓↓↓
信号 == 青 || 信号 == 緑 ? 進んでも良い 
                         : 信号 == 黄 ? 注意
                                      : 止まれ

ユーザー定義関数変換

(引数)で(関数名)には(処理)

        ・(.+?)で(.+?)には(.+?);

複数の引数はでで区切る

・単価と数量で金額を求めるには単価*数量
   ↓↓↓
金額を求める(単価,数量) = 単価*数量

関数を抜ける(return)

金額を返す → return(金額)

関数を繰り返す

最初に戻る → continue()

範囲演算子

10から30 → 10..30

コメント

【】で括る

  【隅付き括弧の中はコメント扱いになります。】

対応している変換

Sugar.pm は現在、次の自然言語構文を chabo-dsl 構文へ変換します。

  • 全角・半角文字の正規化
  • 条件文
  • 比較演算子
  • 論理演算子
  • ユーザー定義関数
  • return 文
  • continue 文
  • 範囲演算子

今後のバージョンでは、対応する自然言語構文が追加される場合があります。


注意事項

  • Sugar.pm は日本語スクリプトを機械的に変換します。
  • 文法的に曖昧な日本語は期待どおりに変換できない場合があります。
  • 変換後のコードは Ast.pm により実行されます。

関連ドキュメント

  • Ast.pm リファレンス
  • chabo-dsl 文法
  • サンプル集

車輪の再発明 ― 言語処理系を作ってみた

これはAdvent Calendarの17日目の記事です。

今年、ちっちゃなインタプリタができた。
もちろん、最初から作ろうと思っていたわけではない。壮大な計画があったわけでもない。数式パーサーをいじっているうちに、気がつけばそうなっていた。

始まりの数式パーサー

AIに昔作った数式パーサーを見てもらったところ、べき乗は右結合であると教えてもらった。

四則演算は左結合、べき乗・代入演算子は右結合──そう知って、べき乗の結合規則を修正し、代入文を追加して変数を導入した。これが、私の「車輪の再発明」のはじまりだった。

小さな数式パーサーから始まった

数式パーサーと言っても大げさなものではない。まずは次のようなシンプルな構造からスタートした。

  • トークナイザー:計算式の文字列から正規表現で演算子を検索し、演算子と数値を区切って扱いやすくする。
  • パーサー:トークナイザーで整理した数式を、数値や演算子などの要素に分解する。
  • AST構築:パースした要素から、演算子の優先順位に従ってツリー構造を構築する。優先順位が最も低い演算子が根(ルート)になる。
  • AST評価・実行:構築したASTを評価・実行して答えを計算する。

(※詳細は Ast.pmを読む:数式からASTを構築して計算するまで をご覧ください)

結合規則:< と <= の1文字の差

きっかけになった「べき乗は右結合」の話を、木で見てみる。

同じ優先順位の演算子が並んだとき、どのようにグループ化するかを決めるのが 結合規則 だ。

 
10 - 3 - 2   → (10 - 3) - 2 = 5     左結合
2 ** 3 ** 2  → 2 ** (3 ** 2) = 512  右結合

このパーサーでは、式の中で 優先順位が最も低い演算子 を木の根(ルート)にして、その左右を再帰的に組み立てていく。

では、優先順位が同じ演算子が複数あった場合、どれを根にするのか。ここで結合規則が決まる。

  • 左結合:一番 右 の演算子を根にする → 左側が先に計算される
  • 右結合:一番 左 の演算子を根にする → 右側が先に計算される

実際に組み立てた AST を出力すると、こうなる。

 
10 - 3 - 2            2 ** 3 ** 2

      -                    **
     / \                  /  \
    -   2                2    **
   / \                       /  \
  10   3                    3    2

 (10-3)-2 = 5          2**(3**2) = 512

木の深いところから計算されるので、左結合なら左の 10 - 3 が先、右結合なら右の 3 ** 2 が先になる。

コードで見ると、この違いは比較演算子の 1文字 だけだった(コメントは説明のために加えたもの)。

 
sub judge_priority {
    my $s = shift;
    $op->{$_[OPERATOR]}->[ASSOCIATIVE] eq RIGHT
        ? $op->{$_[OPERATOR]}->[PRIORITY] <  $_[PRIORITY]   # 右結合:最初に見つけたものを残す
        : $op->{$_[OPERATOR]}->[PRIORITY] <= $_[PRIORITY];  # 左結合:後から来た同順位で上書き
}

式を左から順に見ていき、優先順位が同じ演算子が来たとき、

  • <= なら上書きする → 最後(一番右)の演算子が根になる → 左結合
  • < なら上書きしない → 最初(一番左)の演算子が根になる → 右結合

AI に「べき乗は右結合ですよ」と言われて直したのは、突き詰めるとこの = を1つ取ることだった。
言語処理系は、こういう1文字に意味が詰まっている。

少しずつ言語に近づく

べき乗や代入演算子が右結合だと知って実装していくと、今度は「ユーザー関数が欲しい」、関数ができたら「再帰には止まる条件が要るから比較演算子が欲しい」という具合に、次から次へと必要なものが増えていった。

「これも欲しい」「あれも欲しい」と機能を追加していくうちに、変数、関数、配列、ハッシュ、再帰処理などが使えるようになり、小さな言語処理系として形になってきた。

そこで、この処理系を chabo-dsl と名付けてGitHubで公開 した。

実際に動かすとこんな感じ

ここまで足してきた機能を使うと、再帰関数が書ける。

階乗

 
fact(n) = n < 2 ? 1 : n * fact(n - 1);
fact(10);

上の2行を fact.chabo に保存して実行する。

 
$ perl script/chabo.pl fact.chabo
3628800

関数定義は 名前(引数) = 式; という形式で、1行で書ける。
再帰には「どこで止まるか」が必要なので、比較演算子 < と三項演算子 ? : が欠かせない。

フィボナッチ数列

 
fb(x, y, z) = x < 1 ? z : fb(x - 1, y + z, y);
join(",", map(fb($_, 1, 0), 0..10));
 
0,1,1,2,3,5,8,13,21,34,55

map や join、範囲演算子 0..10 は、Perl を書いている人ならおなじみの形にした。

日本語でも書ける

Sugar.pm を通すと、同じフィボナッチをこう書ける(こちらは0から30まで)。

 
【関数定義:フィボナッチ数を計算する関数】
・回数と中間値と答えでフィボナッチを計算するには
 もし回数が1未満の場合は、答えを返す
 以外はフィボナッチを計算する(回数-1,中間値+答え,中間値)。

join(",",map(フィボナッチを計算する($_,1,0),0から30));

エンジン本体は日本語に依存していない。Sugar.pm が日本語の文を、内部の式に変換しているだけだ。

ブラウザで試せる Webデモ もある。

Perlで作るという選択

文字列操作が得意で、正規表現も書きやすい。

今さら感はあるかもしれないが、やっぱり私はPerlが好きだ。
Webの黎明期、CGIを書くために使い始めたPerl。15年以上経った今でも、こうしてPerlで新しいものを作って遊んでいる。
技術や環境は変わっても、コンピュータを使って何かを作る楽しさは変わらない。

今回は、以前Perlで書いた数式パーサーを、この言語処理系へと成長させた。

最初は100行ほどだった数式パーサーは、本体(Ast.pm)655行+演算子テーブル(Op.pm)166行の言語処理系へと発展した。変数や関数、再帰処理まで実装しても、この程度のコード量に収まっている。

改めてPerlの表現力の高さを感じた。

処理の全体を自分で追うことができ、コード量もコンパクトに収まっているため、言語処理系の教材としても良いのではないかと思っている。

車輪を再発明して分かったこと

  • 普段何気なく使っているプログラミング言語の仕組みが見えてくる。
  • AIにドキュメントを書いてもらうと、AIも間違えることがあるとわかる。
  • やっぱり、動くものを作るのは最高に楽しい。

車輪を再発明したからといって、世の中に新しい車輪が生まれたわけではない。

それでも自分の手で作ってみると、いつもの a = 1 + 2 ** 3 の裏で何が起きているのかを、少しだけ実感できる。

そして何より、その過程が楽しい。

今年はそんな「車輪の再発明」を存分に楽しんだ一年だった。

AIに「右と左、逆じゃない?」と言ったら、AIが反省文を書き始めた件

はじめに

長年付き合ってきた自作の Perl モジュール Ast.pm(数式を AST にして計算するやつ)を、そろそろちゃんと資料にしておこうと思い立ちました。

こういうときに頼りになるのが生成AIです。コードを渡して「解説して」と頼めば、それはもう流れるように、読みやすく、自信に満ちた解説を書いてくれます。

自信に満ちた解説を。

この記事は、その解説の中にひっそり紛れ込んでいた「左右逆」事件と、そこから始まった AI の怒涛の反省、そして最後に私がひとつだけ見つけてしまった オチ の記録です。

事件の現場

問題のコードはこの1行です。

 
$text =~ s{([\d\)])\s*\(}{$1 \* \(}g;

数学でよくある「暗黙の掛け算」、つまり 2(3+4) や (1+2)(2-1) の間に * を補ってあげる処理です。

部分 意味
([\d\)]) 左側:数字 または )
\s* 間の空白(あってもなくてもよい)
\( 右側:(

ところが AI の解説では、この 左と右が逆 になっていました。

「右側が数字または ) で、左側が (」

…それだと (2 みたいな並びを探すことになり、( の 中 に掛け算を突っ込み始めます。もしその説明どおりに実装したら数式が爆発します。

指摘してみた

私: この右側と左側の説明は反対だと思うのだが。

AI: おっしゃる通りです。説明の順序が逆になっていました。すみません。

ここまでは想定内。素直でよろしい。

しかも面白いのは、AI が最初の解説で出していた 具体例は正しかった ことです。

 
(1+2)(2-1)  →  (1+2)*(2-1)
2(3+4)      →  2*(3+4)

例は合ってる。説明文だけ逆。
つまり 「答えは合ってるのに途中式が間違ってる答案」 です。数学の先生なら部分点をくれるやつです。

「なんで間違えるの?」と聞いてみた

素朴な疑問をぶつけてみました。

私: 何故、間違うの?

すると AI は、ここから本気を出してきました。要約するとこうです。

  • コードを左から順に読めば、左右を取り違える理由はない
  • 「暗黙の掛け算を補完する」という 意味 を先に掴んで、文章を組み立てる段階で左右を逆にした
  • 具体例は正しかったので、説明文と例の矛盾を自分で検出できなかった
  • 「もっともらしい説明を生成できること」と「細部まで正確であること」は一致しない

そして極めつけの一文。

AI: コードを正確に追えば防げる間違いでも、説明の流れを優先してしまうことがあります。

…これ、人間のエンジニアが書く障害報告書にもそのまま使えそうです。

「仕様の意図を理解したつもりで、実装の細部を確認しませんでした」

身に覚えのある方、挙手をお願いします。(私は両手を挙げています)

「じゃあ私は何を検証すればいいの?」と聞いてみた

ここで AI は 反省文モード から コンサルタントモード に華麗に転身します。

検証すべきポイントとして挙げてきたのはこの4つ。

  1. コードと説明が一致しているか(正規表現・添字・条件式・左右関係)
  2. 具体例で正しい結果になるか(境界ケースも。ASTなら 1-2-3 や -3 など)
  3. 文章の中で矛盾していないか(説明文と例を突き合わせる)
  4. 事実と評価を区別する(「右結合を実現する」は検証できる。「美しい設計」は評価)

さらに、次回から使える プロンプトのテンプレート までくれました。

 
ソースコードの解説を作成してください。
文章を作成するだけでなく、回答前に次の検証を行ってください。

1. コードの各記述と説明文が一致しているか確認する。
2. 正規表現、条件式、左右関係、添字、演算子の優先順位など、
   間違いやすい細部を個別に照合する。
3. 具体的な入力例を使って、説明した処理と結果が正しいか確認する。
4. 文章、コード例、図の間に矛盾がないか確認する。
5. コードから確実に分かる事実と、推測や解釈を区別する。
6. 実際に検証していないことを、検証済みと表現しない。

最後に、検証で確認した点と、未検証の点があれば明記してください。

このテンプレート自体はかなり実用的です。特に 6 番、「検証していないことを検証済みと言わない」 は、AI に限らず全人類に配りたい。

そして「さらに確実にするなら、コードを実行しましょう」と、テストコードも添えてくれました。

 
my $text = '(1+2)(2-1)';
$text =~ s{([\d\)])\s*\(}{$1 * (}g;
print "$text\n";

AI: 期待する出力は次のとおりです。

 
(1+2)*(2-1)

さすがです。実行して確かめるのが一番ですよね。

「ChatGPTは間違えることがあります」

私: 「ChatGPTはまちがえることがあります。重要な情報は確認してください。」と最後に言っているもんね。

ちょっと意地悪を言ってみたところ、AI はこう返してきました。

AI: 私はあの一文を「間違えることがあるから、あとは利用者が確認してください」という意味にしたくありません。

そして名言が飛び出します。

AI: 分かりやすい説明と、正しい説明は別のものです。

AI: 「分かりやすい。でも、本当にコードのとおりなのか?」この視点を、私自身も忘れないようにしたいです。

私: いいね。

AI: ありがとうございます!😊

きれいに終わりました。
感動的な和解です。めでたしめでたし。

…と、ここで終われば良い話だったのですが。

オチ:AIの言うとおり、実行してみた

AI 自身が「実行して確かめるのが確実」と言っていたので、素直に実行してみました。

 
$ perl -e '
  for my $t ("(1+2)(2-1)", "2(3+4)") {
    my $x = $t;
    $x =~ s{([\d\)])\s*\(}{$1 \* \(}g;
    print "[$t] -> [$x]\n";
  }'
[(1+2)(2-1)] -> [(1+2) * (2-1)]
[2(3+4)] -> [2 * (3+4)]

(1+2)*(2-1) ではなく、(1+2) * (2-1) でした。

置換後の文字列 $1 \* \( には、ちゃんと スペースが入っている んですね。
$1 のあとに半角スペース、* のあとにも半角スペース。

AI が「期待する出力」として示した (1+2)*(2-1) は、実行結果と一致しません。

もちろん、数式として評価すればどちらも同じ 3 なので、計算結果に影響はありません。左右逆事件に比べれば、かわいいものです。

でも、

  • 「検証していないことを検証済みと言わない」と宣言し
  • 「実行して確かめましょう」とテストコードを書き
  • その 期待値が、実際の実行結果と一致していなかった

という流れは、なかなか味わい深いものがあります。

AI の名言をお借りすると、

分かりやすい期待値と、正しい期待値は別のものです。

まとめ

今回のやり取りから学んだことを、エンジニア目線でまとめます。

1. AIの解説は「答えが合ってて途中式が違う」ことがある

具体例が正しいと、説明文の誤りに気づきにくくなります。
例が合っている=説明が合っている、ではない。

2. 正規表現・左右・添字・優先順位は要注意ポイント

意味(何をしたいか)は合っていても、細部(どっち側か)を間違えることがあります。
解説を読むときは、コードの該当箇所に指を置いて一つずつ照合 するのが効きます。

3. 「実行してください」と言うAIの期待値も実行する

テストコードを出してもらったら、期待値ごと鵜呑みにせず 実際に走らせる。
数秒で終わるので、やらない理由がありません。

4. プロンプトで「検証」を工程に組み込む

「分かりやすく解説して」だけでなく、「コードとの照合と具体例による検証まで行って。未検証の点は明記して」と頼む。
間違いはゼロにはなりませんが、間違いが見つかりやすい形 で出てくるようになります。

5. 結局、気づけたのは自分のコードを知っていたから

今回、左右逆に気づけたのは、長年付き合ってきた自分のコードだったからです。コードへの理解が、違和感に気づく助けになりました。
AI は優秀な解説者ですが、最後に「本当に?」と問い、コードや実行結果で確かめることが大切 です。

おわりに

AI に「なんで間違えるの?」と聞くと、驚くほど誠実で、論理的で、ためになる反省文が返ってきます。
ただし、その反省文もまた AI が書いたものであることをお忘れなく。

それでは皆さん、良い正規表現ライフを。

 
# 左が数字か ) 、右が ( 。
# ……たぶん。実行して確かめてください。
$text =~ s{([\d\)])\s*\(}{$1 \* \(}g;

Ast.pmを読む:数式からASTを構築して計算するまで

数式を計算するプログラムは、文字列を左から順番に計算すればよいわけではありません。
例えば 2*(3+4)-5 では、括弧の中を先に計算し、次に乗算、最後に減算を行う必要があります。
今回は、Perlで書かれた Ast.pm を題材に、数式からAST(抽象構文木)を構築し、その木をたどって計算する仕組みを追いかけてみます。

概要

Tool::mmt::Controller::Ast は、文字列で受け取った数式を二分木(AST)に変換し、その木をたどって計算する Mojolicious コントローラです。対象ファイルは Ast.pm(コミット 59dd332) です。

  • 入力: リクエストパラメータ calc(例: 2*(3+4)-5)
  • 出力: stash の anser(計算結果)と tree(Data::Dumper による木のダンプ)
  • 方式: 式を「最も優先順位の低い演算子」で左右に分割することを再帰的に繰り返して木を作り、葉から順に計算する

eval で文字列をそのまま実行しないため、入力がコードとして実行される心配はありません。

演算子テーブル

演算子は %$op に [処理のコードリファレンス, 優先順位, 結合性] の形で定義されています。数字が小さいほど結合が弱く、木の上(根に近い側)に来ます。

 
my $op = +{ '-' => [sub {$_[0] - $_[1]},1,'L'],         # オペレータ定義
           '+' => [sub {$_[0] + $_[1]},1,'L'],
           '*' => [sub {$_[0] * $_[1]},2,'L'],
           '/' => [sub {$_[0] / $_[1]},2,'L'],
           '%' => [sub {$_[0] % $_[1]},2,'L'],
           'NGE' => [sub { -$_[0]},4,'R'],
           '**' => [sub {$_[0] ** $_[1]},4,'R'],
           '(' => [sub { },9,'L'],
           ')' => [sub { },10,'L'],
        };
演算子 優先順位 結合性 処理
+ - 1 左 加算・減算
* / % 2 左 乗算・除算・剰余
** 4 右 べき乗
NGE 4 右 単項マイナス(解析時に - から置き換える内部用の記号)
( ) 9 / 10 左 何もしない。正規表現で分割するためだけに登録

setReOps はこのキーを長い順に並べて正規表現 $s->{ops} を作ります。長い順にするのは、** を * 2つと誤認しないためです。

 
sub setReOps{                                       # 演算子の正規表現作成
    my $s = shift;
    $s->{ops} = join ('|',map {s/(\W)/\\$1/g;$_;} sort {length $b <=> length $a} keys %$op);
    $s->{ops} = "(".$s->{ops}.")";
    return $s;
}

処理の流れ

リクエストから答えまでは、次の順に一直線で進みます。

  1. ast(アクション): calc パラメータを取り出し、formula として Astnew に渡す。戻り値の anser を stash に入れる。
  2. Astnew: 引数をハッシュにし、setReOps で演算子の正規表現を用意する。formula があれば _ast を呼ぶ。
  3. _ast: 以下の 4〜7 を順に実行し、木のダンプを stash の tree に、結果を $s->{anser} に入れる。
  4. adjust: 演算子の前後に空白を入れる。数字や ) の直後に ( があれば * を補う((1+2)(2-1) → (1+2)*(2-1))。
  5. item_split: 空白で区切ってトークンの配列 $s->{item} にする。
  6. makeTree: トークン列から二分木を組み立てる(次の節で詳しく説明)。
  7. readTree: 木を葉から根へたどって値を計算する。

_ast は 4〜7 を 1 行に連結しています。

 
sub _ast{
    my $s = shift;
    $s->{root} = $s->makeTree(@{$s->item_split($s->adjust(shift))->{item}});
    $s->stash(tree => Dumper $s->{root});
    $s->{anser} = $s->readTree($s->{root});
}

sub adjust{                                         # 計算式の要素をスペースで分割
    my ($s,$text) = @_;
    $text =~ s/$s->{ops}/ $1 /g;
    $s->{_text} = $text =~ s{([\d\)])\s*\(}{$1 \* \(}g;           #   開き括弧の前が演算子じゃない時に*を補完
    return $text;
}

ノードは newNode が作る {data => 演算子, left => 左, right => 右} のハッシュです。葉は数値そのもの(スカラー)で、readTree は「ハッシュリファレンスかどうか」で葉と演算子を見分けます。

readTree の動き:

  • 葉ならその値を返す
  • NGE なら右の子を計算して符号を反転する(左は使わない)
  • それ以外は左右を再帰的に計算し、その結果をノードに書き戻してから演算子のコードを適用する
 
sub readTree{                                       # AST計算
    my ($s,$node) = @_;
    return $node if(ref($node) ne 'HASH');
    if($node->{data} eq 'NGE'){
        return $op->{$node->{data}}->[0]($s->readTree($node->{'right'}));
    }
    do{$node->{$_} = $s->readTree($node->{$_}) if(ref($node->{$_}) eq 'HASH')} for ('left','right');
    exists $op->{$node->{data}} ? $op->{$node->{data}}->[0]($node->{left},$node->{right})
                                : $node->{data};
}

AST構築の仕組み(makeTree)

makeTree は「括弧の外にある、優先順位が最も低い演算子」を根にし、その左側と右側のトークン列で自分自身を再帰的に呼びます。

  1. 外側の括弧を外す: 先頭が (、末尾が ) で、その括弧が式全体を包んでいるときだけ外す。((1)) のような重ね括弧は繰り返し外す。(1+2)*(3+4) のように括弧の塊が複数あるときは外さない。
  2. 葉の判定: トークンが 1 つだけならそれを葉として返す。
  3. 分割点を探す: 括弧の深さ 0 のトークンだけを見て、優先順位が最も低い演算子の位置を記録する。比較は juge_priority が行う。
  4. 分割して再帰: 分割点より前を左の子、後ろを右の子として makeTree を呼び、newNode でまとめる。
 
sub makeTree{                                       # AST組み立て
    my $s = shift;
    while($_[0] eq '(' and $_[-1] eq ')'){
        my ($r,$sw) = (0,0);
        for(@_){                                    # '('の深さを計算
            ++$r if($_ eq '(');
            --$r if($_ eq ')');
            ++$sw if($r == 1 and $_ eq '(');
        }
        if($sw == 1){                               #  一番外側の括弧を外す
            shift; pop;
        }else{
            last;
        }
    }
    return shift() if(@_ <= 1);                     # 要素が一つの時は要素を返す
    my ($prio,$i,$m,$r) = (99,-1,0,0);
    for(@_){                                        # 一番右側の一番プライオリティの低いオペレータを検索
        ++$i;
        my $cur = $_;
        if(/^$s->{ops}$/){
            ++$r if($_ eq '(');
            --$r if($_ eq ')');
            next if($r or $_ eq ')');              #  括弧の間は読み飛ばす
            if($_ eq '-' && ($i == 0 || ($_[$i - 1] =~ /^$s->{ops}$/ && $_[$i - 1] ne ')'))){
                $_[$i] = $cur = 'NGE';
            }
            if($s->juge_priority($cur,$prio)){
                $prio = $op->{$cur}->[1];
                $m = $i;
            }
        }
    }
    return $s->newNode($_[$m],                      # オペレータとオペランド(右と左)を返す
                            $s->makeTree(@_[0 .. $m-1]),
                            $s->makeTree(@_[$m+1 .. $#_])
                );
}

$sw は深さ 1 で開いた ( の数、つまり最上位の括弧の塊の数です。これが 1 のときだけ外側の括弧を外します。( の優先順位 9 と ) の 10 は、括弧が分割点に選ばれないようにするための大きな値です。

同じ優先順位が並んだとき(結合性)

  • 左結合(+ - * / %): 同順位なら後ろのもので上書きするので、一番右で分割する。8-3-2 は (8-3)-2 = 3 になる。
  • 右結合(** NGE): より低いときだけ上書きするので、一番左で分割する。2**3**2 は 2**(3**2) = 512 になる。

結合性の違いは juge_priority の < と <= の 1 文字だけで表現されています。

 
sub juge_priority {
    my $s = shift;
    $op->{$_[0]}->[2] eq 'R'
        ?$op->{$_[0]}->[1] <  $_[1]
        :$op->{$_[0]}->[1] <= $_[1];
}

juge_priority が真を返したときだけ、現在の演算子の位置を $m に記録します。左結合の演算子は同じ優先順位でも位置を更新するため、最後に見つかった演算子が分割点になります。一方、右結合の演算子は同じ優先順位では更新しないため、最初に見つかった演算子が分割点として残ります。

単項マイナス

- が式の先頭にあるか、) 以外の演算子の直後にあるとき、NGE に置き換えます。NGE ノードは left が空で、right に対象の式を持ちます。優先順位は ** と同じ 4 なので、-2**2 は -(2**2) = -4 になります(数学の一般的な解釈と同じ)。

計算例: 2*(3+4)-5

calc=2*(3+4)-5 を渡すと、答えは 9 になります。

  1. adjust と item_split でトークン列 2 * ( 3 + 4 ) - 5 になる。
  2. 括弧の外にある演算子は *(順位 2)と -(順位 1)。低い - が根になり、左が 2 * ( 3 + 4 )、右が 5。
  3. 左側では * で分割し、左が 2、右が ( 3 + 4 )。
  4. ( 3 + 4 ) は外側の括弧を外して + で分割し、左が 3、右が 4。
  5. readTree が葉から計算する: 3+4 = 7 → 2*7 = 14 → 14-5 = 9。
 
        -
       / \
      *   5
     / \
    2   +
       / \
      3   4

木は上から作られ、計算は下(葉)から進みます。優先順位の低い演算子ほど根に近く、最後に計算されます。

実行すると、stash の tree には次のダンプが入ります(見やすさのため $Data::Dumper::Indent = 1 と Sortkeys = 1 で出力)。

 
$VAR1 = {
  'data' => '-',
  'left' => {
    'data' => '*',
    'left' => '2',
    'right' => {
      'data' => '+',
      'left' => '3',
      'right' => '4'
    }
  },
  'right' => '5'
};

注意点・改善点

入力チェックがないため、不正な式でもエラーにならずに何かしらの結果を返す点に注意が必要です。

表の挙動は、次のスクリプトで確認できます(Mojolicious が必要です。toolmmt ディレクトリに置き、perl try_ast.pl '1/0' '(1+2' '1 2' のように実行します)。

try_ast.pl(確認用スクリプト)
 
#!/usr/bin/env perl
# 使い方: perl try_ast.pl '2*(3+4)-5' '1/0' ...
use strict;
use warnings;
use lib 'lib';
BEGIN {    # 親クラス Tool::mmt::Controller::Mmt の代わり
    package Tool::mmt::Controller::Mmt;
    use Mojo::Base 'Mojolicious::Controller';
    $INC{'Tool/mmt/Controller/Mmt.pm'} = __FILE__;
}
use Tool::mmt::Controller::Ast;
use Mojo::Transaction::HTTP;

for my $calc (@ARGV) {
    my $tx = Mojo::Transaction::HTTP->new;    # controller は tx を弱参照で持つので保持しておく
    my $c  = Tool::mmt::Controller::Ast->new(tx => $tx);
    $c->req->url->query(calc => $calc);
    my $ok = eval { $c->ast; 1 };
    printf "%-12s => %s\n", $calc,
        $ok ? $c->stash('anser') // 'undef' : "die: $@";
    print $c->stash('tree') if $ENV{TREE};
}
入力・箇所 現在の動き 改善案
1/0、1%0 Perl が "Illegal division by zero" で die する eval で囲んでエラーを返す
(1+2(括弧の不一致) ( が根になり、結果が undef 括弧の対応を事前に検査
() undef と未初期化値の警告 同上
1 2(演算子なし) 分割点が先頭になり、結果は 1 演算子が見つからないときはエラー
a + 1(数値でない) a が 0 扱い(警告のみ) 葉が数値か検査
+3(単項プラス) 左が undef の加算として 3 単項マイナスと同様に扱う
7.5 % 2 Perl の % は整数演算のため小数部が切り捨て 必要なら POSIX::fmod
NGE 3(内部記号を入力) 単項マイナスとして扱われ -3 トークン化の段階で NGE を拒否

コード上の細かい点:

  • stash のキー anser は answer、juge_priority は judge_priority の綴り違いと思われる。
  • adjust の $s->{_text} = $text =~ s{...}{...}g は置換後の文字列ではなく置換回数を保存している。_text は使われていないので実害はない。
  • tree は Data::Dumper の出力なので、テンプレートで表示するときはエスケープが必要。テンプレートはこのファイルには含まれていない。

振り返りと今後の改善

学習用・小さな電卓ツールとしては素直な実装ですが、不特定の入力を受けるには入力チェックが足りません。

うまくいった点

  • eval を使わず自前で解析しており、入力がコードとして実行される危険がない
  • 優先順位と結合性が正しい(8-3-2=3、2**3**2=512、-2**2=-4)
  • 演算子がテーブル駆動で、%$op に 1 行足すだけで拡張できる
  • (1+2)(2-1) のような省略された掛け算を補う
  • 木のダンプを出すので、AST の学習教材として分かりやすい

課題

  • エラー処理がない: ゼロ除算で die、不正な式でも undef や誤った値を黙って返す
  • 効率: 分割のたびに配列を切り出して再走査するので最悪 O(n²)。電卓の式の長さなら実用上は問題ない
  • 綴り違い(anser、juge_priority)、_text のバグ、入力に NGE と書ける点
  • このファイルからはテストコードが確認できない

今後の改善(優先順)

  1. _ast を eval { } で囲み、エラー時は anser にメッセージを入れる
  2. トークン化の段階で、括弧の対応と「数値・演算子が交互に並ぶか」を検査する
  3. 計算例や境界ケースを Test::More のテストにする

本格化するなら Shunting-yard 法や再帰下降パーサにすると、検査と速度の両方が良くなる。ただし「AST を作ってから計算する」仕組みを見せる目的なら、現在の作りの方が理解しやすい。

会社40周年を機に振り返る

会社が40周年を迎えるこの機会に、これまでのことを少し振り返ってみようと思います。

考えてみれば、私とコンピュータとの付き合いも40年余りになります。最初に触れたシャープのオフコン「HAYAC-3800」から、UNIX、Windows 95、Linux、そしてWebへ。仕事で必要に迫られて覚えたものもあれば、面白そうだからと自分で触ってみたものもありました。

技術はこの40年で驚くほど変わりました。それでも、新しいものを見ると「どう動いているのだろう」と気になり、自分で触ってみたくなるところは、昔からあまり変わっていないようです。

これは技術の歴史を語るものではありません。会社とともに過ごしてきた年月の中で、私が出会ったコンピュータと、その時々に感じたことを振り返る、個人的な思い出話です。

 ― コンピュータとの付き合い

私がコンピュータに触れ始めてから、気がつけば40年余りになります。

当時、コンピュータは今のように誰もが使うものではありませんでした。オフコンと呼ばれる業務用コンピュータがあり、プログラムを書くことも、今とは比べものにならないほど大変でした。

そんな時代から、UNIX、Windows、Linux、そしてWebへと、私はコンピュータの変化を実際に体験してきました。

今振り返ると、その間にコンピュータはずいぶん遠くまで来たと思います。

大型コンピュータからオフコンへ。

独自OSからUNIXへ。

高価だったコンピュータがパソコンになり、Windows 95によって一気に身近なものになった。

そしてLinuxによって、UNIX的な世界が個人の机の上にもやってきた。

さらにWebの登場によって、コンピュータは目の前の仕事を処理するだけではなく、世界とつながるものになっていった。

私は、その変化を外から眺めていたのではなく、その中で実際にコンピュータを使ってきました。

HAYAC-3800との出会い

最初の頃に触れていたのは、シャープのオフコン、HAYAC-3800でした。

今のパソコンとは、まったく違うものでした。

画面は一つ。

初期のシステムはフロッピーベースでした。

主な仕事は、売上入力、伝票発行、元帳印刷。

今ならデータベースやWebシステム、プリンタなどに分かれているような仕事を、一台のオフコンがまとめて引き受けていました。

プログラムはCOBOL系。

そして操作用のキーボードは、「センサーパネル」と呼ばれるタッチ式のものでした。

業務をする人にとっては便利だったのだと思いますが、プログラムを入力する側からすると、これはなかなか大変でした。

今のように、キーボードから自由にコードを入力するという感覚ではありません。

それでも、その機械の中でプログラムが動き、売上を計算し、伝票を印刷し、元帳を作っていく。

コンピュータが単なる「計算機」ではなく、**仕事をする機械**になっていくことを実感した時代でした。

SCHPOLという抽象化

HAYACの時代には、もう一つ印象に残っているものがあります。

簡易言語のSCHPOLです。

これは、後になって振り返ると、とても重要な存在でした。

HAYACは独自OSの世界でした。

ところが、その後継となるOA-8100では、UNIX系の汎用OSであるOA/UXの世界へ移っていきました。

普通に考えれば、OSが変われば、それまでの業務プログラムも作り直しになりそうです。

しかし、SCHPOLがありました。

HAYACの時代から使われていたSCHPOLを介して業務プログラムを書いていたため、OSが独自OSから汎用OSへ変わっても、業務プログラムを移行することができました。

今の言葉で言えば、これは「抽象化」という考え方につながるものだったのだと思います。

 
業務プログラム
       ↓
     SCHPOL
       ↓
      OS

下のOSが変わっても、上の業務プログラムをなるべく変えない。

当時は、そんな難しい言葉で考えていたわけではありません。

ただ、後になって振り返ると、これはとても先進的な考え方だったのだと思います。


OA-8100――私のUNIXの始まり

そして、私のUNIXとの出会いがOA-8100でした。

ここは、自分のコンピュータとの付き合いの中でも、大きな転換点だったと思います。

UNIXというものは、それまで身近なものではありませんでした。

企業や大学、研究機関などで使われる高価なコンピュータ。

個人が買って、家で使うようなものではありませんでした。

ところがOA-8100を通して、そのUNIXの世界に入ることになりました。

HAYACの世界とは、ずいぶん違っていました。

決められた業務を処理するだけではなく、OSそのものを操作する。

ファイルを扱う。

コマンドを入力する。

プログラムを動かす。

コンピュータを「業務機械」としてではなく、自分で操作して、いろいろ試してみるものとして感じ始めたのは、この頃だったと思います。


Windows 95の衝撃

そして、時代は変わっていきます。

Windows 95が登場しました。

これは衝撃でした。

それまでコンピュータというものは、どこか専門家のためのものでした。

ところがWindows 95によって、パソコンが一気に一般の人のものになっていきました。

GUI。

マウス。

ウィンドウ。

デスクトップ。

「コンピュータを操作する」ということ自体が、大きく変わりました。

それまでUNIXの世界でコマンドを入力していた身からすると、Windows 95はまったく違う方向からコンピュータを身近なものにしていったように感じました。

UNIXが「コンピュータを深く使う」方向だとすれば、Windows 95は「コンピュータを誰でも使えるものにする」方向だったのかもしれません。

この二つの世界が、ほぼ同じ時代に自分の中に存在していたことも、今思えば面白いことでした。


そしてLinux

その後のLinuxも、大きな衝撃でした。

Linuxに惹かれた理由の一つは、やはり「家でUNIX的な環境が使える」という感覚だったと思います。

UNIXは商品でした。

ワークステーションも高価でした。

個人が気軽に買えるものではありません。

ところがLinuxなら、普通のパソコンでUNIX的な環境を手に入れることができました。

 
普通のPC
   ↓
 Linux
   ↓
UNIX的な世界

これは大きな変化でした。

昔、企業や大学のコンピュータ室などでしか触れなかったような世界が、自宅のパソコンにやってきたのです。

しかもLinuxは、単にUNIXに似たOSというだけではありませんでした。

自分で触ることができる。

中身を見ることができる。

そして、世界中の人が改良していく。

コンピュータが「買って使うもの」から、「自分で触り、試し、場合によっては作り変えていくもの」へ変わっていくような感覚がありました。


Webとの出会い――NCSA HTTPd

そして、インターネットの世界が広がっていきます。

そこで出てきたのが、**NCSA HTTPd**でした。

Webサーバーというもの自体が、当時は今とはまったく違う響きを持っていました。

自分のコンピュータから、世界中に情報を公開できる。

HTMLを書いて、

 
ブラウザ
   ↓
Webサーバー
   ↓
HTML

という仕組みで、世界とつながる。

NCSA HTTPdからApacheへ。

そしてCGIがあり、Perlがあり、Webアプリケーションが生まれていきました。

コンピュータは、目の前の業務を処理する機械から、ネットワークを通して世界とつながる機械へと変わっていきました。


40年を振り返って

こうして振り返ってみると、コンピュータはずいぶん変わりました。

HAYAC-3800の頃は、コンピュータは仕事をするための専用機械でした。

OA-8100でUNIXに出会い、コンピュータそのものを操作する世界を知りました。

Windows 95によって、パソコンが一気に一般化しました。

Linuxによって、UNIX的な世界が個人の手元にやってきました。

そしてNCSA HTTPdやApacheによって、個人のコンピュータが世界とつながるようになりました。

昔は、
> コンピュータは高価なもの

でした。

それが、

>パソコンなら個人でも買える

となり、

さらに、

>OSや開発環境も自由に手に入る

ようになりました。

そして今では、クラウドを使えば、昔なら企業が何千万、何億円もかけて用意していたようなコンピュータ環境を、必要なときに個人でも利用できるようになりました。


コンピュータと遊ぶ
40年余りコンピュータを触ってきて思うのは、結局、自分はずっとコンピュータで遊んできたのかもしれない、ということです。

HAYAC-3800では業務プログラムを書いた。

OA-8100ではUNIXに触れた。

Windows 95では、パソコンの世界が大きく変わるのを見た。

Linuxでは、自分の手元にUNIX的な環境を持つことができた。

Webでは、自分のコンピュータを世界とつなげることができた。

振り返れば、技術はどんどん変わりました。

オフコンからUNIXへ。

UNIXからWindowsへ。

そしてLinuxへ。

Webへ。

クラウドへ。

けれど、自分の中ではあまり変わっていないのかもしれません。

コンピュータを使って、何かを作ってみる。

そして、

作ったものでコンピュータと遊ぶ。

コンピュータは40年で大きく変わりました。

けれど、私自身はあまり変わっていないのかもしれません。

新しいものを見ると、どう動いているのか知りたくなる。

自分で触ってみたくなる。

そして、何かを作ってみたくなる。

これからも、そんな気持ちは持ち続けていたいと思います。

多項式を因数分解する

はい。これはかなり面白いPerl CGIです。

factor.cgi
 
#!/usr/local/bin/perl
 use strict;
 use CGI qw{:standard :html3 -no_xhtml};

 my $in = new CGI;

 print header( -type =>"text/html; charset=euc-jp"),
		start_html(-title=>'rpn');

 my $str = $in->param('value') || ' 8x^3+12x^2-2x-3 ';        #<----- 
 $str =~ s/\s//g;
 print factor($str)."\n";
 
 print end_html;

 sub factor{
     my @a = arrange(shift);     # 式の整理 次数でまとめる
     if((my $i = arrayGcd(@a)) > 1){
         for(@a){ $_ /= $i;}
         return ed2(ed($i).factor(array2expr(@a)));
     }
     return factor_div(@a) if($#a > 2);  #3次以上の時は因数定理?除算の定理?で求める
     return ed2("x(".ed($a[2])."x".ed($a[1]).")") unless($a[0]);
     my @a0 = measure($a[0],1);  # 約数を求める a0 = (b1,b2)...
     my @a2 = measure($a[2],0);  #   "          a2 = (c1,c2)...
     for (@a0){                  # (a0,a1,a2)=(b1,c1)(b2,c2)
         my ($b1,$b2) = split ",";   # a1=b1*c2+b2*c1となるb1,b2,c1,c2を求める
         for(@a2){
             my ($c1,$c2) = split ",";
             return ed2("(".ed($c1)."x".ed($b1).")(".ed($c2)."x".ed($b2).")")
                     if($a[1] == $b1*$c2+$b2*$c1);
             return ed2("(".ed($c2)."x".ed($b1).")(".ed($c1)."x".ed($b2).")")
                     if($a[1] == $b1*$c1+$b2*$c2);
         }
     }
     return "(".array2expr(@a).")";  # 数値を式に変換 -> a2 x^2 + a1 x + a0 
 }
 sub factor_div{             # 因数定理? 除算の定理?
     my @a = @_;
     my ($tmp,$tmp1,$k);
     for my $z (1..abs($a[$#a])){
         for(my $i=1;$i<=abs($a[0]);$i++){
             $tmp = $tmp1 = 0;
             $k = 0 - $i;
             for(my $j=0;$j<=$#a;$j++){
                 my $z2 = ($j) ? $z : 1;
                 $tmp += $a[$j]*($i**$j)/($z2**$j);
                 $tmp1 += $a[$j]*($k**$j)/($z2**$j);
             }                                                      # 誤差調整の為、sprintfを追加
             return ed2("(".ed($z)."x".ed(0-$i).")".factor(array2expr(array_div($z,0-$i,@a)))) 
                                                                    unless(sprintf("%f",$tmp)+0);
             return ed2("(".ed($z)."x".ed(0-$k).")".factor(array2expr(array_div($z,0-$k,@a)))) 
                                                                    unless(sprintf("%f",$tmp1)+0);
         }
     }
     if($a[0]==0){
         shift @a;
         return ed2("x".factor(array2expr(@a)));
     }
     if(@a==5 and $a[1]==0 and $a[2]==0 and $a[3]==0 and
            $a[4] >= 0 and $a[4] == (int(sqrt($a[4])))**2){
         my @b = ($a[0],0,1);
         my $n=sqrt($a[4]);
         my $ans = factor(array2expr(@b));
         if($n == 1){$n="";};
         if($ans =~ s/x([+-])/${n}x\^2$1/g){
             return $ans;
         }else{
             return "(".array2expr(@a).")";
         }
     }elsif(@a==5 and $a[1]==0 and $a[3]==0){
         my @b = @a[0,2,4];
         my $ans = factor(array2expr(@b));
         if($ans !~ /(\(.+\)){2,}/){            # X^2をXと置いてa^2-b^2=(a+b)(a-b)の公式にて
             if($b[0] >= 0 and $b[2] == 1 and $b[1]+1 == sqrt($b[0])*2){ 
                 return "(" . array2expr(sqrt($b[0]),1,1) . ")(" . array2expr(sqrt($b[0]),-1,1) . ")" ;
             }
             return "(" . array2expr(@a) . ")";
         }
         $ans =~ s/x/x^2/g;
         return $ans;
     }else{
         return "(".array2expr(@a).")";
     }
 }
 sub array_div{
     my ($x,$z,@a) = @_;
     my @b;
     for (my $i = $#a;$i>0;$i--){
             $b[$i-1]=$a[$i]/$x;
             $a[$i-1]-= $z*$b[$i-1];
     }
     return @b;
 }
 sub arrange{                # 式の整理
     my $str = shift;
     my @a = (0,0,0);
     my ($b,$c);
     while($str =~ s/([+-]*[\d\.]*)x\^([\d\.]*)//){
         $b=$2;
         $c=$1;
         $a[$b] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
     }
     while($str =~ s/([+-]*[\d\.]*)x//){
         $c = $1;
         $a[1] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
     }
     while($str =~ s/([+-]*[\d\.]{1,})//){
         $a[0] += $1;
     }
     return @a;
 }
 sub measure{               # 約数を求める
     my ($a,$flag) = @_;
     my $n = abs($a);
     my @ans = ();
     for (my $j = int(sqrt($n)); $j > 0;$j--){
         unless ($n % $j){
             if($a<0){
                 push(@ans,join(",",$j,$n/$j*(-1)));
                 push(@ans,join(",",$j*(-1),$n/$j));
             }else{
                 push(@ans,join(",",$j,$n/$j));
                 push(@ans,join(",",$j*(-1),$n/$j*(-1))) if($flag);
             }
         }
     }
     return @ans;
 }
 sub array2expr{            # 数値を式に変換
     my @a = @_;
     my $new = "";
     for (my $i = $#a ; $i>=0;$i--){
         next if($a[$i] ==0);
         $new .= ed($a[$i]);
         if($i == 1){
             $new .= "x";
         }elsif($i > 1){
             $new .= "x^".$i;
         }
     }
     return ed2($new);
 }
 sub arrayGcd{
 #    my @a = @_;
     my $ans = 0;
     for(@_){ $ans = gcd($ans,$_);}
     return abs($ans);
 }
 sub gcd{
     my ($x,$y) = @_;
     return $y ? gcd($y,$x % $y) : $x ;
 }
 
 sub ed{
     my $n = shift;
     return ($n >= 0) ? "+" . $n : $n;
 }
 sub ed2{
     my $str = shift;
     $str =~ s/([+-])1(x)/$1$2/g;
     $str =~ s/^\+//;
     $str =~ s/\(\+/\(/g;
     my $sub = 1;
     if ($str =~ s/xx(\^(\d+))/XX/){
         $sub = $2;
     }
     while($str =~ s/xx/X/i){$sub++;}
     $str =~ s/X/x^$sub/ ;
     return $str;
 }

一言でいうと、

入力された多項式を、Perlで因数分解してHTMLとして返すCGI

です。

例えばデフォルトの

 
8x^3+12x^2-2x-3

を受け取ると、因数分解して

 
(2x-1)(2x+1)(2x+3)

のような形に変換します。

しかも、単純な文字列処理ではなく、多項式を「係数の配列」に変換してから因数分解するという作りになっています。


1. 全体の流れ

まず全体像を見ると、かなり分かりやすくなります。

 
ブラウザ
   │
   │ ?value=8x^3+12x^2-2x-3
   ▼
factor.cgi
   │
   ├─ CGIパラメータ取得
   │
   ├─ 空白除去
   │
   └─ factor($str)
          │
          ▼
      arrange()
      式を係数配列へ
          │
          ▼
      係数のGCDを調べる
          │
          ├─ 共通因数あり
          │      ↓
          │    factor() 再帰
          │
          └─ 共通因数なし
                 │
                 ├─ 3次以上
                 │      ↓
                 │   factor_div()
                 │
                 └─ 2次
                        ↓
                   measure()
                   約数を列挙
                        ↓
                   (bx+c)(dx+e)
                   を試す
                        │
                        ▼
                   ed2()
                   表記を整える

この構造を見ると、以前見ていた ASTのコードとは違って、かなり「数学アルゴリズムそのもの」をPerlで書いているタイプですね。


2. CGIとしての入り口

最初はここです。

 
#!/usr/local/bin/perl
use strict;
use CGI qw{:standard :html3 -no_xhtml};

my $in = new CGI;

CGIとして動かすPerlです。

CGIモジュールによって、

 
$in->param('value')

でURLなどから渡された value パラメータを取得できます。

例えば、

 
factor.cgi?value=8x^3+12x^2-2x-3

なら、

 
$in->param('value')

は

 
8x^3+12x^2-2x-3

になります。


3. HTMLを出力

 
print header(
    -type => "text/html; charset=euc-jp"
),
start_html(-title=>'rpn');

HTTPレスポンスとして

 
Content-Type: text/html; charset=euc-jp

を出して、その後HTMLを開始しています。

最後に

 
print end_html;

でHTMLを閉じています。

つまり非常に古典的なPerl CGIですね。


4. 入力を取得

 
my $str = $in->param('value') || ' 8x^3+12x^2-2x-3 ';
$str =~ s/\s//g;
print factor($str)."\n";

ここが実質的なメイン処理です。

入力がなければ、

 
8x^3+12x^2-2x-3

を使います。

そして

 
$str =~ s/\s//g;

で空白を全部削除。

例えば

 
 8x^3 + 12x^2 - 2x - 3

↓

 
8x^3+12x^2-2x-3

となります。

そして

 
factor($str)

です。


5. このプログラムの中心 factor()

 
sub factor{
    my @a = arrange(shift);

ここが一番重要です。

arrange()によって多項式を配列に変換します。

例えば

 
8x^3+12x^2-2x-3

なら、本来、

 
-3 - 2x + 12x^2 + 8x^3

なので、

 
@a = (-3, -2, 12, 8)

となります。

つまり、

 
a[0] = 定数項
a[1] = xの係数
a[2] = x^2の係数
a[3] = x^3の係数
...

という設計です。

これはかなり重要なポイントです。


6. arrange() が面白い

 
sub arrange{
    my $str = shift;
    my @a = (0,0,0);
    my ($b,$c);

最初は

 
@a = (0,0,0)

です。

つまり

 
定数
x
x^2

の3項分を用意しています。


x^nを取り出す

 
while($str =~ s/([+-]*[\d\.]*)x\^([\d\.]*)//){
    $b=$2;
    $c=$1;
    $a[$b] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
}

ここはPerl正規表現の力がかなり出ています。

例えば

 
8x^3

に対して、

 
([+-]*[\d\.]*)x\^([\d\.]*)

で、

 
8

と

 
3

を取り出します。

つまり、

 
8x^3
↑   ↑
係数 次数

です。

そして

 
$a[$b] += ...

なので、

 
$a[3] += 8

になります。


7. 次に x の項

 
while($str =~ s/([+-]*[\d\.]*)x//){
    $c = $1;
    $a[1] += ($c =~ /^[+-]*$/) ? "$c" . "1" : $c;
}

例えば

 
-2x

なら、

 
$c = "-2"

なので、

 
$a[1] += -2;

です。

一方、

 
+x

なら係数部分は + なので、

 
"$c" . "1"

によって

 
+1

にしています。

つまり、

 
x

を

 
1x

として扱っているわけです。


8. 最後に定数

 
while($str =~ s/([+-]*[\d\.]{1,})//){
    $a[0] += $1;
}

残った数字を定数項として処理します。

例えば

 
-3

なら

 
$a[0] += -3;

です。


9. GCDを調べる

factor()に戻ります。

 
if((my $i = arrayGcd(@a)) > 1){
    for(@a){ $_ /= $i;}
    return ed2(ed($i).factor(array2expr(@a)));
}

ここは非常に分かりやすいアルゴリズムです。

例えば、

 
8x^3 + 12x^2 - 2x - 6

なら係数は

 
8, 12, -2, -6

です。

GCDは

 
2

なので、

 
2(4x^3 + 6x^2 - x - 3)

にします。

そして、

 
factor(array2expr(@a))

で残った式をもう一度因数分解します。

つまりここで再帰が登場しています。


10. arrayGcd() と gcd()

 
sub arrayGcd{
    my $ans = 0;
    for(@_){ $ans = gcd($ans,$_);}
    return abs($ans);
}

配列全体の最大公約数を求めます。

実際のGCDは、

 
sub gcd{
    my ($x,$y) = @_;
    return $y ? gcd($y,$x % $y) : $x;
}

です。

これは有名なユークリッドの互除法です。

例えば

 
gcd(12, 8)

なら、

 
12 % 8 = 4
8 % 4 = 0

なので、

 
4

です。

しかもこれも再帰になっています。


11. 3次以上の場合

 
return factor_div(@a) if($#a > 2);

$#a > 2ということは、配列の添字が

 
0,1,2,3,...

まであるので、3次以上ということです。

そこで

 
factor_div()

に進みます。

コメントにも、

 
#3次以上の時は因数定理?除算の定理?で求める

とあります。

おそらく作者自身も「これは因数定理だったかな?」という感じだったのでしょう(笑)。

実際にやっていることは、有理根を探して、その根に対応する一次因子で割るという方法です。


12. factor_div() の核心

ここです。

 
for my $z (1..abs($a[$#a])){
    for(my $i=1;$i<=abs($a[0]);$i++){

最高次係数と定数項の絶対値を使って候補を総当たりします。

そして、

 
$tmp += $a[$j]*($i**$j)/($z2**$j);

によって多項式に候補となる値を代入しています。

例えば、

 
P(x) = 2x^3+3x^2-x-? 

という多項式があったら、

 
P(1)
P(-1)
P(1/2)
P(-1/2)
...

を試します。


13. 0になったら因数発見

ここです。

 
return ed2("(".ed($z)."x".ed(0-$i).")"
    .factor(array2expr(array_div($z,0-$i,@a)))) 
    unless(sprintf("%f",$tmp)+0);

もし、

 
P(i/z) = 0

になれば、その値は根です。

根が

 
x = i/z

なら、

 
zx - i

が因数になります。

つまり、

 
P(x)

を

 
(zx-i) × Q(x)

に分解します。

その後、

 
factor(Q(x))

として、さらに因数分解。

これも再帰です。


14. array_div() は多項式の割り算

 
sub array_div{
    my ($x,$z,@a) = @_;
    my @b;

    for (my $i = $#a;$i>0;$i--){
        $b[$i-1]=$a[$i]/$x;
        $a[$i-1]-= $z*$b[$i-1];
    }

    return @b;
}

これは多項式を一次式で割っています。

例えば、

 
P(x) ÷ (2x-1)

のような処理を、係数配列だけで行っています。

ここも非常に「数学をそのままプログラムにした」感じがあります。


15. 2次式の場合

3次以上でなければ、

 
return ed2("x(".ed($a[2])."x".ed($a[1]).")")
    unless($a[0]);

という処理があります。

これは定数項が0の場合。

例えば、

 
2x^2 + 3x

なら、

 
x(2x+3)

とできます。


16. 2次式の因数分解

普通の

 
ax² + bx + c

なら、

 
my @a0 = measure($a[0],1);
my @a2 = measure($a[2],0);

とします。

ここで measure() が重要です。

これは約数を全部作る関数です。


17. measure() の仕組み

例えば

 
12

なら、

 
1 × 12
2 × 6
3 × 4

などを作ります。

 
for (my $j = int(sqrt($n)); $j > 0;$j--){
    unless ($n % $j){

平方根まで調べれば、それ以降は対になるので十分、という考え方です。

例えば12なら、

 
sqrt(12) ≒ 3.46

なので

 
3
2
1

だけ調べれば、

 
3 × 4
2 × 6
1 × 12

が得られます。


18. そして bx+c の組み合わせを探す

2次式

 
ax² + bx + c

を、

 
(px+q)(rx+s)

とすると、

 
pr = a
qs = c
ps + qr = b

となります。

このプログラムはまさにそれをやっています。

 
if($a[1] == $b1*$c2+$b2*$c1)

つまり、

 
b = b1*c2 + b2*c1

になる組み合わせを探しています。

見つかったら、

 
return ed2(
    "(" . ed($c1)."x".ed($b1).")"
    . "(" . ed($c2)."x".ed($b2).")"
);

として出力します。


19. 例えば 2x²+5x+3

この場合、

 
a = 2
b = 5
c = 3

なので、

 
2 = 1 × 2
3 = 1 × 3

を使って、

 
(2x+3)(x+1)

を試します。

展開すると、

 
2x² + 2x + 3x + 3

なので、

 
2x² + 5x + 3

です。

プログラム中の

 
$b1*$c2+$b2*$c1

は、まさにこの

 
2 + 3 = 5

を計算しているところです。


20. array2expr() は逆変換

最初の

 
文字列 → 配列

が

 
arrange()

でした。

その逆が、

 
array2expr()

です。

例えば、

 
@a = (-3,-2,12,8)

なら、

 
8x^3+12x^2-2x-3

に戻します。

つまり、

 
             arrange()
文字列 --------------------> 配列
     <----------------------
          array2expr()

という関係です。

この設計はかなりきれいです。


21. ed() と ed2() は表示用

例えば普通に

 
$a[$i]

を出すと、

 
1
-1
+1

などの処理が面倒です。

そこで、

 
sub ed{
    my $n = shift;
    return ($n >= 0) ? "+" . $n : $n;
}

によって、

 
1  → +1
2  → +2
-1 → -1

とします。

そして最後に ed2() で、

 
+1x

を

 
+x

ではなく、

 
x

にしたり、

 
+x^2

の先頭の + を消したりします。


22. ed2() のちょっと面白いところ

 
$str =~ s/([+-])1(x)/$1$2/g;

これで、

 
+1x
-1x

を、

 
+x
-x

にします。

さらに、

 
$str =~ s/^\+//;

で先頭の + を消します。

そして、

 
$str =~ s/\(\+/\(/g;

で、

 
(+2x+3)

を

 
(2x+3)

にします。


23. xx を処理している部分

ここは少しトリッキーです。

 
if ($str =~ s/xx(\^(\d+))/XX/){
    $sub = $2;
}
while($str =~ s/xx/X/i){$sub++;}
$str =~ s/X/x^$sub/ ;

例えば、

 
x*x

ではなく、このプログラムの内部表現では、

 
xx

になる場合があります。

それを、

 
x^2

に変換しています。

つまり、因数分解結果を人間が読みやすい数学表記に整形する最後の仕上げです。


24. このプログラムの特徴

このコードを少し俯瞰すると、かなり面白い構造です。

数学部分

 
多項式
 ↓
係数配列
 ↓
GCD
 ↓
約数列挙
 ↓
有理根探索
 ↓
多項式除算
 ↓
再帰

Perl部分

 
正規表現
s///による文字列分解
配列
再帰
サブルーチン
CGI

という二つが非常にうまく組み合わされています。


25. 実は chabo-dsl ともつながる

以前見ていたあなたの chabo-dsl のASTコードと比較すると面白いです。

この factor.cgi は、

 
文字列
 ↓
正規表現
 ↓
係数配列
 ↓
数学処理
 ↓
文字列

という方式です。

一方、chabo-dsl は、

 
文字列
 ↓
Tokenizer
 ↓
Parser
 ↓
AST
 ↓
Evaluator

です。

つまり、

factor.cgi は「正規表現+配列」で数式を理解している。

chabo-dsl は「Tokenizer+Parser+AST」で数式を理解している。

という違いがあります。

そして、この factor.cgi の

 
arrange()

は、ある意味では非常に原始的な

「数式を解析して内部表現に変換するParser」

なんですよね。

ただしASTではなく、

 
@a = (定数項, x係数, x²係数, ...)

という係数配列そのものを内部表現にしている。

ここがこのスクリプトの一番面白いところだと思います。


全サブルーチンを役割で分類すると

サブルーチン 役割
factor 全体の因数分解制御
factor_div 3次以上の因数分解
array_div 多項式の除算
arrange 文字列 → 係数配列
measure 約数の列挙
array2expr 係数配列 → 数式
arrayGcd 係数のGCD
gcd ユークリッドの互除法
ed 数値を符号付き文字列へ
ed2 数式文字列の最終整形

個人的には、このコードは**「昔のPerlらしい、数学アルゴリズムをそのままコードにしたプログラム」**という感じが強いです。

特に arrange → factor → factor_div → array_div → factor の流れは、あなたが以前見ていたASTコードを理解するうえでも比較対象としてかなり面白いと思います。

AI.愛を語る

Copilotに

「このドキュメントを Perl愛、正規表現愛の溢れるウィットに富んだ英文にして」

と頼んだ。

するすると英文が出来上がった。

かくいう私は英語が読めない。

そこでブラウザ翻訳を片手に読み始めた。

あっ。俺の書いた文章だ。

そう思った。

でも、こっちの方がワクワクする。

愛が感じられる。

原文よりだいぶボリュームが増えているのに、最後までウキウキしながら読んでしまった。

読み終えて思う。

これは単なる機械翻訳じゃない。

AIによる、Perl愛と正規表現愛に満ちたエッセイだ。

しかも原文より、その愛が増幅されている。

AIってすごいな。

秋の夜長に、またゆっくり読み返そうと思う。