Nemerleでコンパイル時に迷路を解いてみた

故*1Nemerleのマクロは非常に強力で、コンパイル時でも実行時に行えるあらゆる事(計算はもちろんのこと、入出力、ネットワークIO、GUIなど)を行えるので、それを利用してコンパイル時に例の迷路を解くマクロを書いてみた。このマクロは、入力として迷路を表現してテキストを受け取り、迷路を解くのに成功した場合は、経路を書きこんだ迷路の文字列を結果として返し、解けない迷路の場合は、This maze cannot be solvedと表示し、コンパイルエラーにする。

using System;
using System.Console;
using System.IO.File;
using Nemerle.Collections;
using Nemerle.Imperative;
using Nemerle.Compiler;

macro SolveMaze(inputFile : string){
  def maze = ReadAllLines(inputFile);
  def h = maze.Length;
  def w = maze[0].Length;
  def q = Queue();
  def v = array(h);
  def d = [(1, 0), (-1, 0), (0, 1), (0, -1)];
  for(mutable i = 0; i < h; i = i + 1) {
    v[i] = array(w);
  }
  mutable s = None();
  for(mutable y = 0; y < h; y = y + 1) {
    for(mutable x = 0; x < w; x = x + 1) {
      when(maze[y][x] == 'S') s = Some(x, y);
    }
  }
  match(s) {
  | None => Message.Error("S is not found"); <[ ("" : string) ]>
  | Some((sx, sy)) => 
    q.Add([(sx, sy)]);
    mutable path = null;
    def Loop() {
      when(q.IsEmpty) Message.Error("This maze cannot be solved");
      path = q.Take();
      def (x, y) = path.Head;
      when(maze[y][x] == 'G') return;
      when((!v[y][x]) && maze[y][x] != '*') {
        v[y][x] = true;
        d.Iter(fun(_){ 
        | (dx, dy) => q.Add((x + dx, y + dy)::path);
        });
      }
      Loop();
    }
    Loop();
    def result = System.Text.StringBuilder();
    for(mutable y = 0; y < h; y = y + 1) {
      for(mutable x = 0; x < w; x = x + 1) {
        def e = maze[y][x];
        if(e == 'S' || e == 'G' || !path.Contains((x, y))) {
          Write(e);
          _ = result.Append(e);
        }else {
          Write("$");
          _ = result.Append("$");
        }
      }
      WriteLine("");
      _ = result.Append("\n");
    }
    WriteLine("compiled successfully");
    <[ $(result.ToString(): string) ]>
  }
}

解法は単なるBFS+αであり、特筆すべき点は無いが、ローカル変数の型が一切宣言されていない点に注意して欲しい。ローカル変数の宣言の際に、型宣言を省略できる事自体は、元々型推論が強力な静的型付けの関数型言語(ML,OCaml,Haskellなど)にとどまらず、静的型付けOOP言語(C#,Scala,Nice,Fantomなど)でもよく見られるようになって来ているが、Nemerleの場合、それに加えて、

  def v = array(h);

のように、宣言時にはvの具体的な型がわからない(配列であることはわかるが、何の配列であるかは宣言時にはわからない)場合でも、多くの場合型宣言が必要無い*2。

このマクロをコンパイルするには、以下のようにコマンドラインから入力する(maze.nはこのマクロを含むファイルのファイル名)。

ncc -r:Nemerle.Macros.dll -t:dll maze.n -o maze.dll

このマクロを使うには、たとえば、次のようなプログラムを書き、

using System.Console;
WriteLine(SolveMaze("input.txt"));

以下のようにコマンドラインから入力する。

>ncc -r:maze.dll use_maze.n -o solve_maze.exe

すると、迷路が解けた場合には、以下のように表示され、コンパイルが成功する。

**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************
compiled successfully

さらに、できたsolve_maze.exeを実行してみると、先ほどの迷路の解がそのまま表示される。

**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

input.txtの中身が、解けない迷路、たとえば以下のような迷路の場合、

**************************
*S* *                    *
*** *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

以下のように表示され、コンパイルは失敗する。

use_maze.n:2:11:2:20: e[01;31merrore[0m: This maze cannot be solved
confused by earlier errors bailing out

*1:一応、今でもダウンロードできるが、もはやアップデートされることは無いだろうという意味で少し早計だったようだ。今は別の人がメンテしてるみたいで、ひょっとしたらまだこれから更新されるのかもしれない。

*2:変数の宣言時にはわからない型情報は、変数が実際に使われている箇所の情報を基に推論される