So-net無料ブログ作成

Lua の配列の複製 [Lua]

Lua のテーブルは mutable なデータ型なので、例えば関数にテーブルを渡して関数の中でテーブルの書き換え操作とかを行うと、呼び出し側からみてもテーブルの内容が変わってしまったりします。

これが困る場合もあるのでどうにかならないかということを前からぼんやり思っていて、一つにはテーブルをコンスセルとみなすリスト構造とその操作用関数を定義してやればいいというのがありますが、これはちょっと面倒くさい。

もう一つは呼び出し側か関数側かどちらかでテーブルの複製を行えばよい。しかしこれは標準ライブラリにありません。こういうコードを書く必要がでてきます。

local new = {}
for k,v in ipairs(old) do
  new[k] = v
end

勿論これを関数にしておけばいいのですが、もっと手元にあるものだけで「手軽」にやる方法はないかと思っていました。

ところが今ふと思いついたのですが、こうすればよいだけです。わりとあっけない話でした。

{unpack(old)}

確かめてみます。

> old = {1,2,3}
> new1 = old
> new2 = {unpack(old)}
> new1[1] = 4
> new2[1] = 5
> print(table.concat(old, ","))
4,2,3
> print(table.concat(new1, ","))
4,2,3
> print(table.concat(new2, ","))
5,2,3

制限として浅いコピーであること、配列としてのテーブルのみに使えることがありますが、贅沢を言わない場面では重宝しそうです。


Lua でクロージャによる超軽量並行プロセス [Lua]

半年前の話題ですが、ブックマークの整理で「クロージャによる超軽量並行プロセスの簡単実装法」 [1] が出てきたので Lua で写経してみました。

まず安直な翻訳。

function new()
  return { senders = {}, receivers = {} }
end

function send(channel, ...)
  if #channel.receivers == 0 then
    table.insert(channel.senders, {...}) -- push
  else
    local process = table.remove(channel.receivers, 1) -- shift
    process(...)
  end
end

function receive(channel, process)
  if #channel.senders == 0 then
    table.insert(channel.receivers, process) -- push
  else
    local message = table.remove(channel.senders, 1) -- shift
    process(unpack(message))
  end
end

--[[ フィボナッチサーバ

fibc = new()

function fib()
  receive(fibc, function(n, repc)
    fib()
    if n <= 1 then
      send(repc, n)
    else
      local repc1 = new()
      local repc2 = new()
      send(fibc, n-1, repc1)
      send(fibc, n-2, repc2)
      receive(repc1, function(rep1)
        receive(repc2, function(rep2)
          send(repc, rep1+rep2)
        end)
      end)
    end
  end)
end

fib()

r = new()
send(fibc, 10, r)
receive(r, function(x) print(10, x) end)

--]]

ちょっとオブジェクト指向にした。

Channel = {}
Channel.__index = Channel

function Channel:send(...)
  if #self.receivers == 0 then
    table.insert(self.senders, {...}) -- push
  else
    local process = table.remove(self.receivers, 1) -- shift
    process(...)
  end
end

function Channel:receive(process)
  if #self.senders == 0 then
    table.insert(self.receivers, process) -- push
  else
    local message = table.remove(self.senders, 1) -- shift
    process(unpack(message))
  end
end

function Channel:new()
  local o = { senders = {}, receivers = {} }
  setmetatable(o, self)
  return o
end

こういう fib 関数の end に閉じ括弧がついたりつかなかったりというのを見ると Ruby や Scala のシンタクスは上手いこと考えてあるなあと思いますね。

追記: いくつか local 付け忘れてたのを修正。よく忘れる。

他の言語による実装一覧

* Ruby

- http://jijixi.azito.com/cgi-bin/diary/index.rb?date=20070614#p02
- http://jijixi.azito.com/cgi-bin/diary/index.rb?date=20070615#p01
- http://d.hatena.ne.jp/rubyco/20070615/cur
- http://d.hatena.ne.jp/ytakamiya/20070615#1181897876

* Scheme

- http://d.hatena.ne.jp/ishikawash/20070703/1183476554

* JavaScript

- http://d.hatena.ne.jp/sukesam/20070615/1181839050

* Smalltalk

- http://d.hatena.ne.jp/sumim/20070618/p1
- http://d.hatena.ne.jp/sumim/20070618/p2
- http://d.hatena.ne.jp/sumim/20070619/p1

[1] http://itpro.nikkeibp.co.jp/article/COLUMN/20070612/274231/


入門 Lua プログラミング [Lua]

「入門 Lua プログラミング」を買ったので少し目を通しました。良い入門書なのですが、読んでいてちょっと気になった部分がありました。

「データの入っている最大のインデックス値は、table.getn(テーブル名)という関数で求めることができます」(p.25)

「え、それは…」と思って、読み進めると p.61 にちゃんと Lua 5.1 では # 演算子が推奨で getn は非推奨ということの記載があるのですが、では何で getn を先に紹介するのかははっきりと書いていません。

また generic for はp.99あたりで紹介されるのですが、それが出てきた後もサンプルプログラムのコーディングスタイルとしては一貫して for idx = 1, table.getn(t) do ... end なんですね。その一方で「Lua のバージョン4では、次のようにして標準関数の定義を追加してください」というのがあったりします。

思うに、多分著者の方は「適宜の事前定義を行えば Lua 4.0 以降で最大限互換性のあるコーディングスタイル」を採りたいという立場なんだと思います。

それはそれで見識だと思うのですが(ただ2007年に出版する入門者向けの本で本当に必要な立場か?というと疑問は残りますが)、そういうことはもうちょっと注意深く説明してくれないと、これを使って Lua を学習する人の間で必要じゃない場面で古い書き方をするようなスタイルが広まってしまわないかとちょっと心配に思いました。


Lua で小町算 [Lua]

「LL魂ブログ:キミならどう書く 2.0 - 2007 - その 2」 [1] より。Lua で挑戦。
これは言語に eval 相当があれば超有利でコルーチンがあればかなり柔軟に書ける種類の問題かなあと思った。

続きを読む


Lua で with-output-to-string [Lua]

「Gauche クックブック」というサイトの記事 [1] のコード例で初めて知って面白いと思ったのが、Gauche には with-output-to-string というフォームがあって(Scheme 全般にあるのかとか Common Lisp にもあるのかは調べていない)、これでコードを囲むだけでその中身のコードで標準出力に出力しようとした文字列を全部バッファに溜めて文字列として返してくれるらしい。
要は一種のストリングバッファなのだけど、こういう書き方ができるのは自然ですばらしいと思った。これを Lua でやりたい。

Lua の print や io.stdout:write はそのままでは単に標準出力に文字を出すしかできないので、これらを一時的に取り替えて代わりにバッファに溜めるようにする。高階関数としても実装できるのかもしれないけど Metalua のマクロを使ってみた。

require "std"

-{block:

  function with_output_to_string_builder(x)
    local block = unpack(x)
    return +{
      function ()
        local buffer = {} -- string buffer

        -- back up original print and io
        local _print = print
        local _io = io

        -- our new print
        print = function(...)
          buffer[#buffer+1] = table.concat(table.imap(|x| tostring(x), {...}), "\t")
          buffer[#buffer+1] = "\n"
        end

        -- our new io.stdout and io.write
        io = {
          stdout = {
            write = function(self, ...)
              for i,v in ipairs{...} do
                buffer[#buffer+1] = tostring(v)
              end
            end
          },
          write = function(...)
              io.output:write(...)
          end,
        }
        io.output = io.stdout
        setmetatable(io.stdout, {__index = _io.stdout})
        setmetatable(io, {__index = _io})

        -- do the work
        -{block}

        -- restore original print and io
        print = _print
        io = _io

        return table.concat(buffer)
      end ()
    }
  end

  mlp.lexer:add{"with_output_to_string"}
  mlp.expr:add{
    "with_output_to_string", mlp.block, "end",
    builder = with_output_to_string_builder
  }
}

これを使うと以下のような書き方で、

local s = with_output_to_string
  print("hello", "world")

  io.write("howdy, ", "world\n")

  io.output = io.open("/dev/null")
  io.write("this message will be discarded")

  io.output = io.stdout
  io.write("howdy, ", "again\n")

  io.stdout:write("good", "bye\n")
end

変数 s には "hello\tworld\nhowdy, world\nhowdy, again\ngoodbye\n" が入る。

文字列を繰り返す関数は(Lua には string.rep があるが)以下のように書ける。

function myrep(str, n)
  return with_output_to_string
    for i=1,n do
      io.write(str)
    end
  end
end

グローバルな print 関数などを直接交換するので既存の関数の中で print などを使っていてもバッファに入る。

function f()
  print("foo")
end

print(string.upper(with_output_to_string f() end)) --> FOO

ただし C による拡張の中で標準出力に出しているようなものは当然入らないだろう。
あとコルーチンの中で with_output_to_string を使ってその中で yield したような場合不都合が起きそう。

[1] http://d.hatena.ne.jp/rui314/20070416/p1


Metalua を試してみる [Lua]

Metalua [1] は Lua を拡張してマクロ機能をつけたもの。ここでいうマクロは構文木をいじるほうのマクロで、OCaml に対する Camlp4 のような存在と思えばよい。

* インストールするまで

Linux では Lua が入った環境で普通に make すればいい…はずなのだが、玄箱に入れるところでまずつまづいた。
Metalua は独自に Lua のバイトコードを生成するようなのだが、Lua のバイトコードというのはエンディアン依存で、Metalua の出力するバイトコードはリトルエンディアンのみらしい。玄箱は PPC でビッグエンディアンだからうまく動かない。

これを解決するには Lua のほうでエンディアン対応してあげるしかなくて、Lua のメーリングリストにそういうパッチ [2] があった。これを適用したら玄箱でも動くようになった。

* Metalua 付属の構文拡張

Metalua では自分で構文拡張を作らない状態でも以下のような構文拡張がなされている。

匿名関数を書くのに function といちいち書かずに Ruby 風に書ける。

table.sort(grades, function(a, b) return a.grade < b.grade end) -- Lua
table.sort(grades, |a,b| a.grade < b.grade) --Metalua

バッククォート記号を使うことで任意の関数を中置演算子として使える。これは Haskell 風。

function plus (x, y)
  return x + y
end

print (2 `plus` 3) --> 5

こうした構文拡張以外にも割といろいろあって、table モジュールに関数型言語風の高階関数が追加されてたりして地味に便利そう。

* クォーテーションとアンチクォーテーション

Metalua で構文拡張をするには代数データ型(これも Metalua 付属の拡張のひとつ)を駆使して手で構文木を書く方法とクォーテーションを使う方法がある。勿論手書きはしたくないので後者を取り上げる。

print("Hello World!") に相当する構文木はクォーテーションを使って以下のように書ける。+{...} が Camlp4 でいう <:xxx< ... >> に相当すると思えばよい。

+{expr: print("Hello World!") }

コロンの手前は式をクォートするときは expr、ステートメントをクォートするときは stat、複数の式の場合は block と書く。expr の場合にのみ省略できる。

アンチクォートさせたい場合は以下のように書く。この例だと print 関数の引数の位置に msg 変数の構文木が挿入される。-{...} が Camlp4 でいう $...$ に近い。

+{expr: print(-{msg}) }

-{...} はソース上に構文木を展開する使い方もできる。以下は Hello World 二つ分のプログラムにコンパイルされる。

-{ +{ print ("Hello World!") } }
print(-{ +{ "Hello World!" } })

実行結果と逆アセンブル結果は以下のとおり。

KURO-BOX% mlc b.lua
Compiling b.lua...
...Wrote b.luac.
KURO-BOX% lua b.luac
Hello World!
Hello World!
KURO-BOX% luac -l b.luac

main <?:0,42> (7 instructions, 28 bytes at 0x1002b820)
0+ params, 2 slots, 0 upvalues, 0 locals, 2 constants, 0 functions
        1       [-]     GETGLOBAL       0 -1    ; print
        2       [-]     LOADK           1 -2    ; "Hello World!"
        3       [-]     CALL            0 2 1
        4       [2]     GETGLOBAL       0 -1    ; print
        5       [2]     LOADK           1 -2    ; "Hello World!"
        6       [-]     CALL            0 2 1
        7       [2]     RETURN          0 1

動作としては -{...} はコンパイル時に実行され、その値が構文木とみなされるということのようだ。以下のような例だとコンパイル時に Hello World が出るけど、実行時には出ない。

-{stat: print("Hello World!") }
KURO-BOX% mlc c.lua
Compiling c.lua...
Hello World!
...Wrote c.luac.
KURO-BOX% lua c.luac
KURO-BOX% 

構文木以外を返すとコンパイルできない。

-{stat: return 777}
KURO-BOX% mlc d.lua
Compiling d.lua...
lua: compiler/compile.lua:678: attempt to index local 'ast' (a number value)

* Metalua パーサ

Metalua では gg という汎用のパーサモジュールがあって、それを使って mlp という Metalua 構文解析用のパーサが作られているようだ。これは Camlp4 でいう Grammar モジュールと Pcaml モジュールの関係のようなものだと思う。

* 構文拡張を作る

コンパイル時に実行される -{...} の中で mlp モジュールを使ってパーサの動きを変えてやるというのが自分で構文拡張を作るときのやり方のようだ。本来はちゃんと詳しく仕様を理解すべきなんだけどとりあえずは見よう見まねで unless ステートメントを作成してみた。(単純なんだけどうまくいかないときのエラーが意味不明ですごい時間かかった)

-{block:

  local function unless_builder (x)
    local expr, block = unpack (x)
    return +{stat:
      if not(-{expr}) then
        -{block}
      end
    }
  end

  mlp.lexer:add{"unless"}
  mlp.stat:add{
    "unless", mlp.expr, "then", mlp.block, "end",
    builder = unless_builder
  }

}

unless 1 == 1 then
  print("not 1 == 1")
end

unless 1 == 2 then
  print("not 1 == 2")
end
--> "not 1 == 2"

[1] http://metalua.luaforge.net/
[2] http://lua-users.org/lists/lua-l/2006-02/msg00507.html


Lua で HTML パーサ [Lua]

Lua だけで書かれた HTML パーサ(ツリーに変換したい)というので(意外にも)適当なものを見つけることができなかったので自分で作ってみた。これは

<html><body>
<p>
  Click <a href="http://example.com/">here!</a>
<p>
  Hello
</p>
</body></html>

のような HTML を Lua のテーブルで

{
  _tag = "#document",
  _attr = {},
  {
    _tag = "html",
    _attr = {},
    {
      _tag = "body",
      _attr = {},
      "\n",
      {
        _tag = "p",
        _attr = {},
        "\n  Click ",
        {
          _tag = "a",
          _attr = {href = "http://example.com/"}
          "here!",
        },
        "\n",
      },
      {
        _tag = "p",
        _attr = {},
        "\n  Hello\n",
      },
      "\n",
    }
  }
}

のような形に変換する。(ところで Lua はテーブルのプリティプリンタがビルトインされていないのが不便だ)
以下がコード。

module(..., package.seeall)

entity = {
  nbsp = " ",
  lt = "<",
  gt = ">",
  quot = "\"",
  amp = "&",
}

-- keep unknown entity as is
setmetatable(entity, {
  __index = function (t, key)
    return "&" .. key .. ";"
  end
})

block = {
  "address",
  "blockquote",
  "center",
  "dir", "div", "dl",
  "fieldset", "form",
  "h1", "h2", "h3", "h4", "h5", "h6", "hr", 
  "isindex",
  "menu",
  "noframes",
  "ol",
  "p",
  "pre",
  "table",
  "ul",
}

inline = {
  "a", "abbr", "acronym", "applet",
  "b", "basefont", "bdo", "big", "br", "button",
  "cite", "code",
  "dfn",
  "em",
  "font",
  "i", "iframe", "img", "input",
  "kbd",
  "label",
  "map",
  "object",
  "q",
  "s", "samp", "select", "small", "span", "strike", "strong", "sub", "sup",
  "textarea", "tt",
  "u",
  "var",
}

tags = {
  a = { empty = false },
  abbr = {empty = false} ,
  acronym = {empty = false} ,
  address = {empty = false} ,
  applet = {empty = false} ,
  area = {empty = true} ,
  b = {empty = false} ,
  base = {empty = true} ,
  basefont = {empty = true} ,
  bdo = {empty = false} ,
  big = {empty = false} ,
  blockquote = {empty = false} ,
  body = { empty = false, },
  br = {empty = true} ,
  button = {empty = false} ,
  caption = {empty = false} ,
  center = {empty = false} ,
  cite = {empty = false} ,
  code = {empty = false} ,
  col = {empty = true} ,
  colgroup = {
    empty = false,
    optional_end = true,
    child = {"col",},
  },
  dd = {empty = false} ,
  del = {empty = false} ,
  dfn = {empty = false} ,
  dir = {empty = false} ,
  div = {empty = false} ,
  dl = {empty = false} ,
  dt = {
    empty = false,
    optional_end = true,
    child = {
      inline,
      "del",
      "ins",
      "noscript",
      "script",
    },
  },
  em = {empty = false} ,
  fieldset = {empty = false} ,
  font = {empty = false} ,
  form = {empty = false} ,
  frame = {empty = true} ,
  frameset = {empty = false} ,
  h1 = {empty = false} ,
  h2 = {empty = false} ,
  h3 = {empty = false} ,
  h4 = {empty = false} ,
  h5 = {empty = false} ,
  h6 = {empty = false} ,
  head = {empty = false} ,
  hr = {empty = true} ,
  html = {empty = false} ,
  i = {empty = false} ,
  iframe = {empty = false} ,
  img = {empty = true} ,
  input = {empty = true} ,
  ins = {empty = false} ,
  isindex = {empty = true} ,
  kbd = {empty = false} ,
  label = {empty = false} ,
  legend = {empty = false} ,
  li = {
    empty = false,
    optional_end = true,
    child = {
      inline,
      block,
      "del",
      "ins",
      "noscript",
      "script",
    },
  },
  link = {empty = true} ,
  map = {empty = false} ,
  menu = {empty = false} ,
  meta = {empty = true} ,
  noframes = {empty = false} ,
  noscript = {empty = false} ,
  object = {empty = false} ,
  ol = {empty = false} ,
  optgroup = {empty = false} ,
  option = {
    empty = false,
    optional_end = true,
    child = {},
  },
  p = {
    empty = false,
    optional_end = true,
    child = {
      inline,
      "del",
      "ins",
      "noscript",
      "script",
    },
  } ,
  param = {empty = true} ,
  pre = {empty = false} ,
  q = {empty = false} ,
  s =  {empty = false} ,
  samp = {empty = false} ,
  script = {empty = false} ,
  select = {empty = false} ,
  small = {empty = false} ,
  span = {empty = false} ,
  strike = {empty = false} ,
  strong = {empty = false} ,
  style = {empty = false} ,
  sub = {empty = false} ,
  sup = {empty = false} ,
  table = {empty = false} ,
  tbody = {empty = false} ,
  td = {
    empty = false,
    optional_end = true,
    child = {
      inline,
      block,
      "del",
      "ins",
      "noscript",
      "script",
    },
  },
  textarea = {empty = false} ,
  tfoot = {
    empty = false,
    optional_end = true,
    child = {"tr",},
  },
  th = {
    empty = false,
    optional_end = true,
    child = {
      inline,
      block,
      "del",
      "ins",
      "noscript",
      "script",
    },
  },
  thead = {
    empty = false,
    optional_end = true,
    child = {"tr",},
  },
  title = {empty = false} ,
  tr = {
    empty = false,
    optional_end = true,
    child = {
      "td", "th",
    },
  },
  tt = {empty = false} ,
  u = {empty = false} ,
  ul = {empty = false} ,
  var = {empty = false} ,
}

setmetatable(tags, {
  __index = function (t, key)
    return {empty = false}
  end
})

-- string buffer implementation
function newbuf ()
  local buf = {
    _buf = {},
    clear =   function (self) self._buf = {}; return self end,
    content = function (self) return table.concat(self._buf) end,
    append =  function (self, s)
      self._buf[#(self._buf) + 1] = s
      return self
    end,
    set =     function (self, s) self._buf = {s}; return self end,
  }
  return buf
end

-- unescape character entities
function unescape (s)
  function entity2string (e)
    return entity[e]
  end
  return s.gsub(s, "&(#?%w+);", entity2string)
end

-- iterator factory
function makeiter (f)
  local co = coroutine.create(f)
  return function ()
    local code, res = coroutine.resume(co)
    return res
  end
end

-- constructors for token
function Tag (s) 
  return string.find(s, "^</") and
    {type = "End",   value = s} or
    {type = "Start", value = s}
end

function Text (s)
  local unescaped = unescape(s) 
  return {type = "Text", value = unescaped} 
end

-- lexer: text mode
function text (f, buf)
  local c = f:read(1)
  if c == "<" then
    if buf:content() ~= "" then coroutine.yield(Text(buf:content())) end
    buf:set(c)
    return tag(f, buf)
  elseif c then
    buf:append(c)
    return text(f, buf)
  else
    if buf:content() ~= "" then coroutine.yield(Text(buf:content())) end
  end
end

-- lexer: tag mode
function tag (f, buf)
  local c = f:read(1)
  if c == ">" then
    coroutine.yield(Tag(buf:append(c):content()))
    buf:clear()
    return text(f, buf)
  elseif c then
    buf:append(c)
    return tag(f, buf)
  else
    if buf:content() ~= "" then coroutine.yield(Tag(buf:content())) end
  end
end

function parse_starttag(tag)
  local tagname = string.match(tag, "<%s*(%w+)")
  local elem = {_attr = {}}
  elem._tag = tagname
  for key, _, val in string.gmatch(tag, "(%w+)%s*=%s*([\"'])(.-)%2", i) do
    local unescaped = unescape(val)
    elem._attr[key] = unescaped
  end
  return elem
end

function parse_endtag(tag)
  local tagname = string.match(tag, "<%s*/%s*(%w+)")
  return tagname
end

-- find last element that satisfies given predicate
function rfind(t, pred)
  local length = #t
  for i=length,1,-1 do
    if pred(t[i]) then
      return i, t[i]
    end
  end
end

function flatten(t, acc)
  acc = acc or {}
  for i,v in ipairs(t) do
    if type(v) == "table" then
      flatten(v, acc)
    else
      acc[#acc + 1] = v
    end
  end
  return acc
end

function optional_end_p(elem)
  if tags[elem._tag].optional_end then
    return true
  else
    return false
  end
end

function valid_child_p(child, parent)
  local schema = tags[parent._tag].child
  if not schema then return true end

  for i,v in ipairs(flatten(schema)) do
    if v == child._tag then
      return true
    end
  end

  return false
end

-- tree builder
function parse(f)
  local root = {_tag = "#document", _attr = {}}
  local stack = {root}
  for i in makeiter(function () return text(f, newbuf()) end) do
    if i.type == "Start" then
      local new = parse_starttag(i.value)
      local top = stack[#stack]

      while
        top._tag ~= "#document" and 
        optional_end_p(top) and
        not valid_child_p(new, top)
      do
        stack[#stack] = nil 
        top = stack[#stack]
      end

      top[#top+1] = new -- appendchild
      if not tags[new._tag].empty then 
        stack[#stack+1] = new -- push
      end
    elseif i.type == "End" then
      local tag = parse_endtag(i.value)
      local openingpos = rfind(stack, function(v) 
          if v._tag == tag then
            return true
          else
            return false
          end
        end)
      if openingpos then
        local length = #stack
        for j=length,openingpos,-1 do
          table.remove(stack, j)
        end
      end
    else -- Text
      local top = stack[#stack]
      top[#top+1] = i.value
    end
  end
  return root
end

これを html.lua として保存して

require "html" -- モジュール読み込み

function printnode(n, indent)
  if type(n) == "table" then
    print(string.rep(" ", indent)..n._tag.." {")
    for k,v in pairs(n._attr) do
      print(string.rep(" ", indent+2)..k.."="..v)
    end
    for i,v in ipairs(n) do
      printnode(v, indent + 2)
    end
    print(string.rep(" ", indent).."}")
  elseif type(n) == "string" then
    print(string.rep(" ", indent).."\""..string.gsub(n, "\n", " ").."\"")
  end
end

root = html.parse(io.stdin) -- ここで使っている
printnode(root, 0)

のようにして使う。

どれだけタグの知識を持たせて不正な HTML に対処するかって所が凝りどころなんだろうとは思うんだけど、いまのところはインラインの中にブロックが来てたりしてもそのまま子要素にしてしまうような感じ。
ただし終了タグがマッチしていない場合はマッチするものまで探して(parse 関数の End トークンの分岐の openingpos 変数)中間を全て閉じる。

2007-05-12追記:
LuaForge に登録、リリースしました。
http://luaforge.net/projects/html/


Higher-Order Lua [Lua]

先日書いた記事 [1] で Higher-Order Perl のテクニックは多分 Lua, Python, Ruby, JavaScript みたいな主要な動的言語でもつかえそうだというようなことを書きましたが、実際 Higher-Order JavaScript [2] (これはそういえば聞いたことがあった)と Higher-Order Ruby [2] という試みは始めている人がいました。

それで引用符つきの "Higher Order Lua" で検索してみたら引っかからなかったので着手してみることにしました。掲載されているのはまだ最初のほうのごく僅かなものだけです。

http://nul.jp/2007/hol/

世界の Lua ユーザにも読んでもらえるように基本英語で行く予定です。ちなみに Higher Order Python もまだないみたいなので早い者勝ち(?)だと思います。

[1] http://blog.so-net.ne.jp/rainyday/2007-02-04
[2] http://interglacial.com/hoj/
[3] http://blog.grayproductions.net/articles/category/higher-order-ruby


HTML をトークナイズする [Lua]

ちょっと必要があって Lua で書いたコード。標準入力から HTML を受け取ってタグとテキストの部分に分けたトークンのストリームにする。前半の string buffer と makeiter は基本的に Programming in Lua に出てくるのをアレンジしたものです。

-- a (singleton) string buffer implementation
buf = {
  _buf = {},
  clear =   function (self) self._buf = {} return self end,
  content = function (self) return table.concat(self._buf) end,
  append =  function (self, s) self._buf[#(self._buf) + 1] = s; return self end,
  set =     function (self, s) self._buf = {s}; return self end,
}

-- iterator factory
function makeiter (f)
  local co = coroutine.create(f)
  return function ()
    local code, res = coroutine.resume(co)
    return res
  end
end

function Tag (s) return {type = "Tag", value = s} end
function Text (s) return {type = "Text", value = s} end

-- text mode
function text ()
  local c = io.read(1)
  if c == "<" then
    if buf:content() ~= "" then coroutine.yield(Text(buf:content())) end
    buf:set(c)
    return tag()
  elseif c then
    buf:append(c)
    return text()
  else
    if buf:content() ~= "" then coroutine.yield(Text(buf:content())) end
  end
end

-- tag mode
function tag ()
  local c = io.read(1)
  if c == ">" then
    coroutine.yield(Tag(buf:append(c):content()))
    buf:clear()
    return text()
  elseif c then
    buf:append(c)
    return tag()
  else
    if buf:content() ~= "" then coroutine.yield(Tag(buf:content())) end
  end
end

--[[
for i in makeiter(text) do
  print(i.type .. ": " .. string.gsub(i.value, "\n", " "))
end
--]]

どうということもないコードですが、末尾呼び出しが出てきたりコルーチンを使っていたりするので、両方を同じように書けるスクリプト言語は意外に限定されるかもしれません。ちなみに Lua で末尾呼び出しになっているかどうかを調べるには luac -l でバイトコードのアセンブリ出力を見ると TAILCALL というそのものずばりのオペコードが出てくるので大変分かりやすいです。

ここでは基本的には延々と末尾呼び出しをして(つまりループをして)トークンになったところで yield しているので(さらに makeiter でイテレータ化しているので)ブロックコメント内のような使い方が出来ます。使うと例えばこんな結果を出力します。

Tag: <html>
Text:
Tag: <body>
Text:
Tag: <p>
Text: blah blah
Tag: </p>
...

これだと開始タグと終了タグの区別が付かないので不便ですが、そういう場合でなおかつ元のコードに手をつけたくない場合でも以下のようなラッパーを書けば同じように使うことが出来ます。

function startend ()
  for i in makeiter(text) do
    if i.type == "Tag" then
      coroutine.yield(
        string.find(i.value, "^</")
        and {type = "End", value = i.value}
        or {type = "Start", value = i.value}
      )
    else
      coroutine.yield(i)
    end
  end
end

--[[
for i in makeiter(startend) do
  print(i.type .. ": " .. string.gsub(i.value, "\n", " "))
end
--]]

コルーチンって便利という話でした。


The Evolution of Lua [Lua]

"The Evolution of Lua" [1] という作者らによる Lua の一代記みたいなものを読んだ。

読み始めてみたら結構長かったけど、その中で興味深かったのは lexical scoping を導入するに至るまでの話で、私は以前 Tcl (今でも基本的に動的スコープの言語)に lexical scoping を導入するとしたらどんな形が一番自然だろうかと妄想したことがあって、Lua 3.1 で導入され(てその後もっと本格的な仕様に置き換わった)た upvalue のアイデアというのはそのとき思いついたものに近い。Tcler's Wiki を見ると pure-Tcl で lexical scoping を模倣しようとしている試みがいくつかあるけど、それらも基本的には自由変数の frozen copy を取っておくもので Lua 3.1 の upvalue に相当すると思う。

[1] http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/hopl.pdf