LoginSignup
2

More than 3 years have passed since last update.

ポールグレアムのアキュムレータジェネレータをJ言語で解く

Last updated at Posted at 2015-12-12

アキュムレータジェネレータについて

技術野郎の復讐という記事の付録で、Paul Graham氏は「アキュムレータジェネレータ」というプログラミングパズルを出しています。

  • 好きなプログラミング言語で、数n(intにかぎらず一般の数)を受け取り、関数を返す関数fooを定義すること。
  • fooの返す関数は「数iを受け取り、niを足して代入し書き換え、それを返す」という物。

プログラミング言語のパワフルさを測るためのもので、氏のLisp方言であるArcでは次のように解けるそうです。

accgen.arc
(def foo (n) [++ n _])

JavaScriptではこうでしょうか。

accgen.js
foo = n => i => n += i

設問からしてもう変数のない純粋な言語や関数からクロージャを返せない言語は対象外です。J言語はクロージャが作れません。関数を返す関数はJ言語で一応書くことはできますが、ローカル変数は消えてしまうため毎回nを忘れてしまいます。

accgen-expanded.ijs
NB.# 冒頭のJavaScriptの直訳
foo =: adverb define
  n =. m
  monad : 'n =. n + y'
)

ただ、多少条件を緩めるような段落があるのでこれに甘えます。

OO言語では、一つだけメソッドを持つクラスを定義して メソッドが参照する変数をクラスのフィールドに置き換えれば、 制限はあるものの、 クロージャ(定義されたスコープ内の変数を参照できる関数)を模倣することはできる。
そうすることは、レキシカルスコープを完全にサポートする言語ではコンパイラが やってくれるような作業をプログラマが自分でやるようなものだし、 複数の関数が同一の変数を参照する場合なんかは使えないけれど、 この例のような簡単な場合は十分だ。
-- Paul Graham 技術野郎の復讐

J言語での解答

一応、Jも一行で解くことはできます(J言語の公式Wikiの記事より)。

accgen.ijs
foo =: 1 : '(a[n__a=.m[a=.18!:3$~0)&(4 :''n__x=.n__x+y'')'

標準のエイリアスを使ってわずかに読みやすくし、改行してコメントを入れると次のようになります(信じ難いことに、この言語のコメントはNB.で始まります)。

accgen-expanded.ijs
foo =: adverb define               NB.# 副詞 foo を定義
  a =. cocreate $~ 0               NB.# 新ロケールを生成、その名前をローカル変数 a に代入
  n__a =. m                        NB.# a の指すロケールに属す変数 n に左辺を代入
  a & (dyad : 'n__x =. n__x + y')  NB.# 左辺の指すロケールに属す変数 n に右辺を加算する無名の二項動詞を作り、その左辺をaとした単項動詞を返す
)

こう定義したfooは、次のように呼び出せます。

REPL
   acc =: 4 foo NB.

   acc 0
   a
(<,'0')&(4 : 'n__x=.n__x+y')
4
   acc 3
7
   acc 1
8
   acc 0
8

クロージャがない

「用語はよくわからないけど、無名関数みたいな物を作れるのならロケールがどうとかややこしいことをする必要があるのだろうか?」と思うかもしれませんが、J言語は無名関数が作れるだけでクロージャは作れません1。次のようにしてもエラーになります。

ご存知のように、J言語はオブジェクト指向言語ですから、オブジェクトを作ってメンバ変数として持つことはできます。とはいえ、Jのオブジェクト指向はちょっと変わっているので、全く引用どおりの方法という訳ではありません。JavaScriptで訳すと次のようになります。

hoge.js
var foo = (m) => {
  var a = {}
  a.n = m
  return ((x, y) => x.n += y).bind(void 0, a)
)

オブジェクト(にあたる匿名ロケールという物)をその場で作り、それを&(Bond)演算子で作った二項動詞に結びつけています。

しくみ

Jの代入演算子には、=.=:の二種類があります。前者はローカル用、後者はグローバル用です。クロージャは作れないのでグローバル変数を使うことになります。上の解法では、匿名のロケールaを生成して、その中のグローバル変数n__aを書き換えています。

(書きかけ)

リンク


  1. 多分実装する気がないだけだと思います 

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2