最近寒いですね。昨晩は御殿場のうえのほうで雪が降って、ノーマルタイヤなのに道凍ってたらどうしようかなぁと。ちょっと悩んだけど、結局高速道路で帰った。((((;゜Д゜)))ガクガクブルブル
さて、これはチャーチ数で2^2=4、2^4=16を計算し、「w」を16個出力します。(grass.elのぺえじから)
((;゜Д゜))((;゜Д゜))(((;゜Д゜)))(((;゜Д゜)))((;゜Д゜))(((;゜Д゜)))(((;゜Д゜)))(((;゜Д゜)))((;゜Д゜))(;゜Д゜)((;゜Д゜))(((;゜Д゜)))(((;゜Д゜)))((;゜Д゜))((;゜Д゜))(((;゜Д゜)))((;゜Д゜))((;゜Д゜))((;゜Д゜))(((;゜Д゜)))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))(((;゜Д゜)))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))((;゜Д゜))
$ ./gkbr.py church.gkbr
wwwwwwwwwwwwwwww
最近計算論を読んでいて、型なしラムダ計算の実装としてgrassを追っかけていたら思いついたので書いてみた。
Python実装のデバッグ出力には大変世話になった。先人のコードが読めるというのは素晴らしい。
あと数式でラムダ計算を眺めると外から見た感じになって理解を深めるのに良いですな。
計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)でもこの本は難しい。2章までは読んだけど、3章はわからん。
#!/usr/bin/env python
# -*- encoding:utf-8 -*-
"""
gkbr.py - Gkbr interpreter
2010-11-19
- Modified by kzfm
---- Original Grass --
grass.py - Grass interpreter
http://www.blue.sky.or.jp/grass/
Copyright (C) 2008 NISHIO Hirokazu. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in
the documentation and/or other materials provided with the
distribution.
THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
History:
2008-06-06
- Tlanslated to python by NISHIO
2007-10-02
- Follow the latest changes of the definition of Grass.
- by UENO Katsuhiro
2007-09-20
- First version by UENO Katsuhiro.
"""
from copy import deepcopy
import sys
import re
import codecs
RELEASE = 0
ONLY_RETURN = 40
DEBUG = 50
DEBUG2 = 60
LOGLEVEL = RELEASE
NUMERICAL_OUTPUT = False
def log(level, *msg):
if level <= LOGLEVEL:
print "\t".join(map(str, msg))
def Struct(*keys):
class _Struct(object):
def __init__(self, *values):
self.__dict__.update(zip(keys, values))
return _Struct
Machine = Struct("code", "env", "dump")
class Value(object):
def __repr__(self):
return self.__class__.__name__
class Insn(object):
pass
class App(Insn):
def __init__(self, m, n):
self.m = m
self.n = n
def eval(self, m):
f, v = m.env[-self.m], m.env[-self.n]
f.app(m, v)
def __repr__(self):
return "App(%(m)d, %(n)d)" % self.__dict__
class Abs(Insn):
def __init__(self, body):
self.body = body
def eval(self, m):
m.env.append(Fn(self.body, deepcopy(m.env)))
def __repr__(self):
return "Abs(%s)" % self.body
class Fn(Value):
count = 0
name = ""
def __init__(self, code, env):
self.code, self.env = code, env
Fn.count += 1
self.count = Fn.count
def app(self, m, arg):
m.dump.append((m.code, m.env))
m.code, m.env = deepcopy(self.code), deepcopy(self.env)
m.env.append(arg)
def __repr__(self):
if self.name:
return self.name
return "Fn%d" % self.count
ChurchTrue = Fn([Abs([App(3,2)])], [Fn([],[])])
ChurchTrue.name = "CTrue"
ChurchFalse = Fn([Abs([])], [])
ChurchFalse.name = "CFalse"
class CharFn(Value):
def __init__(self, char_code):
self.char_code = char_code
def app(self, m, arg):
if self.char_code == arg.char_code:
ret = ChurchTrue
else:
ret = ChurchFalse
m.env.append(ret)
def __repr__(self):
return "Char(%s)" % self.char_code
class Succ(Value):
def app(self, m, arg):
m.env.append(CharFn((arg.char_code + 1) & 255))
class Out(Value):
def app(self, m, arg):
if NUMERICAL_OUTPUT:
sys.stdout.write("%d(%c)" % (arg.char_code, arg.char_code))
else:
sys.stdout.write(chr(arg.char_code))
m.env.append(arg)
class In(Value):
def app(self, m, arg):
ch = sys.stdin.read(1)
if ch == "":
ret = arg
else:
ret = CharFn(ord(ch))
m.env.append(ret)
def eval(m):
while True:
if not m.code:
if not m.dump: break
ret = m.env[-1]
m.code, m.env = m.dump.pop()
m.env.append(ret)
log(ONLY_RETURN, m.env)
else:
insn = m.code.pop(0)
insn.eval(m)
return m.env[0]
InitialEnv = [In(), CharFn(ord("w")), Succ(), Out()]
InitialDump = [[[], []], [[App(1, 1)], []]]
def start(code):
return eval(Machine(code, deepcopy(InitialEnv), deepcopy(InitialDump)))
def parse(src):
code = []
src = src.replace(u'(((;゜Д゜)))','W').replace(u'((;゜Д゜))','w').replace(u'(;゜Д゜)','v')
src = re.subn("[^w]*", "", src, 1)[0]
src = re.sub("[^wWv]", "", src)
for s in re.split("v+", src):
if not s: continue
a = re.findall(r"w+|W+", s)
a = map(len, a)
arity = 0
if s[0] in "w":
arity = a.pop(0)
if len(a) % 2 != 0: raise RuntimeError("parse error at app")
body = []
for i in range(0, len(a) - 1, 2):
body.append(App(a[i], a[i+1]))
for i in range(arity):
body = [Abs(body)]
code += body
return code
def run(src):
start(parse(src))
def run_stdin():
sys.stdin = codecs.getreader('utf_8')(sys.stdin)
src = sys.stdin.read()
run(src)
def run_from_file():
with codecs.open(sys.argv[1], 'r','utf_8') as f:
run(f.read())
if __name__ == "__main__":
if len(sys.argv) > 1:
run_from_file()
else:
run_stdin()