root/lang/python/grass/grass.py

Revision 13336, 9.3 kB (checked in by nishio, 9 years ago)

/lang/python/grass remove duplicated +128 func

Line 
1# -*- coding: cp932 -*-
2"""
3 grass.py - Grass interpreter
4 http://www.blue.sky.or.jp/grass/
5
6 Copyright (C) 2008 NISHIO Hirokazu. All rights reserved.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions
10 are met:
11 1. Redistributions of source code must retain the above copyright
12    notice, this list of conditions and the following disclaimer.
13 2. Redistributions in binary form must reproduce the above copyright
14    notice, this list of conditions and the following disclaimer in
15    the documentation and/or other materials provided with the
16    distribution.
17
18 THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
19 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
20 THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
22 BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
25 BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
27 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
28 IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 History:
31
32 2008-06-06
33   - Tlanslated to python by NISHIO
34 2007-10-02
35   - Follow the latest changes of the definition of Grass.
36   - by UENO Katsuhiro
37 2007-09-20
38   - First version by UENO Katsuhiro.
39
40
41TESTS
42>>> run("wWWwwww")
43w
44
45>>> run('''wwWWwv \
46    wwwwWWWwwWwwWWWWWWwwwwWwwv \
47    wWWwwwWwwwwWwwwwwwWwwwwwwwww''')
48ww
49
50>>> run("wWWWwwwwWWWw") # x
51x
52
53"""
54from copy import deepcopy
55import sys
56import re
57
58RELEASE = 0
59ONLY_RETURN = 40
60DEBUG = 50
61DEBUG2 = 60
62LOGLEVEL = RELEASE
63NUMERICAL_OUTPUT = False
64def log(level, *msg):
65    if level <= LOGLEVEL:
66        print "\t".join(map(str, msg))
67
68def Struct(*keys):
69    class _Struct(object):
70        def __init__(self, *values):
71            self.__dict__.update(zip(keys, values))
72    return _Struct
73
74Machine = Struct("code", "env", "dump")
75
76   
77class Value(object):
78    def __repr__(self):
79        return self.__class__.__name__
80
81class Insn(object):
82    pass
83
84class App(Insn):
85    def __init__(self, m, n):
86        self.m = m
87        self.n = n
88
89    def eval(self, m):
90        f, v = m.env[-self.m], m.env[-self.n]
91        log(DEBUG2, "Application:\n\tfunc:%s\n\targ:%s\n" %
92            (f, v))
93        f.app(m, v)
94
95    def __repr__(self):
96        return "App(%(m)d, %(n)d)" % self.__dict__
97
98
99class Abs(Insn):
100    def __init__(self, body):
101        self.body = body
102
103    def eval(self, m):
104        m.env.append(Fn(self.body, deepcopy(m.env)))
105
106    def __repr__(self):
107        return "Abs(%s)" % self.body
108
109class Fn(Value):
110    count = 0
111    name = ""
112    def __init__(self, code, env):
113        self.code, self.env = code, env
114        Fn.count += 1
115        self.count = Fn.count
116        log(DEBUG2, "Fn%d:\n\tcode:%s\n\tenv:%s\n" %
117            (self.count, self.code, self.env))
118       
119    def app(self, m, arg):
120        m.dump.append((m.code, m.env))
121        m.code, m.env = deepcopy(self.code), deepcopy(self.env)
122        m.env.append(arg)
123
124    def __repr__(self):
125        if self.name:
126            return self.name
127        return "Fn%d" % self.count
128
129ChurchTrue  = Fn([Abs([App(3,2)])], [Fn([],[])])
130ChurchTrue.name = "CTrue"
131ChurchFalse = Fn([Abs([])], [])
132ChurchFalse.name = "CFalse"
133
134class CharFn(Value):
135    def __init__(self, char_code):
136        self.char_code = char_code
137
138    def app(self, m, arg):
139        if self.char_code == arg.char_code:
140            ret = ChurchTrue
141        else:
142            ret = ChurchFalse
143        m.env.append(ret)
144
145    def __repr__(self):
146        return "Char(%s)" % self.char_code
147
148class Succ(Value):
149    def app(self, m, arg):
150        m.env.append(CharFn((arg.char_code + 1) & 255))
151
152class Out(Value):
153    def app(self, m, arg):
154        if NUMERICAL_OUTPUT:
155            sys.stdout.write("%d(%c)" % (arg.char_code, arg.char_code))
156        else:
157            sys.stdout.write(chr(arg.char_code))
158        m.env.append(arg)
159
160
161class In(Value):
162    def app(self, m, arg):
163        ch = sys.stdin.read(1)
164        if ch == "":
165            ret = arg
166        else:
167            ret = CharFn(ord(ch))
168        m.env.append(ret)
169
170def eval(m):
171    while True:
172        log(DEBUG, "code:", m.code)
173        log(DEBUG, "env:", m.env)
174        log(DEBUG, "dump:", m.dump)
175        log(DEBUG)
176       
177        if not m.code:
178            if not m.dump: break
179            ret = m.env[-1]
180            m.code, m.env = m.dump.pop()
181            m.env.append(ret)
182            log(ONLY_RETURN, m.env)
183        else:
184            insn = m.code.pop(0)
185            insn.eval(m)
186
187    return m.env[0]
188
189InitialEnv = [In(), CharFn(ord("w")), Succ(), Out()]
190InitialDump = [[[], []], [[App(1, 1)], []]]
191
192def start(code):
193    return eval(Machine(code, deepcopy(InitialEnv), deepcopy(InitialDump)))
194
195def parse(src):
196    code = []
197    src = re.subn("[^w��]*", "", src, 1)[0]
198    src = re.sub("[^w��W�vv��]", "", src)
199    for s in re.split("[v��]+", src):
200        if not s: continue
201        a = re.findall(r"[w��]+|[W�v]+", s)
202        a = map(len, a)
203        arity = 0
204        if s[0] in "w��":
205            arity = a.pop(0)
206        if len(a) % 2 != 0: raise RuntimeError("parse error at app")
207        body = []
208
209        for i in range(0, len(a) - 1, 2):
210            body.append(App(a[i], a[i+1]))
211
212        for i in range(arity):
213            body = [Abs(body)]
214
215        code += body
216
217    return code
218
219def run(src):
220    start(parse(src))
221
222
223## coding utilities
224env = ["In", "w", "Succ", "Out"]
225
226def ws(name, env=env):
227    return "w" * find_last(env, name)
228
229def Ws(name, env=env):
230    return "W" * find_last(env, name)
231
232def find_last(xs, x):
233    for i in range(len(xs)):
234        if xs[-1-i] == x:
235            return i + 1
236
237def make_func(name, body):
238    """
239    build function body
240    body format:
241    [("resultname", "funcname", "argname"), ...]
242    for example
243    [("arg+1", "Succ", "arg1"), ("arg+2", "Succ", "arg1")]
244
245    >>> print make_func("+2", [\
246            ("tmp", "Succ", "arg1"),\
247            ("result", "Succ", "tmp"),\
248            ])
249    wWWWwWWWWwv
250    <BLANKLINE>
251    >>> print make_func("+4", [\
252            ("tmp", "+2", "arg1"),\
253            ("result", "+2", "tmp"),\
254            ])
255    wWWwWWWwv
256    <BLANKLINE>
257    """
258    myenv = deepcopy(env)
259    myenv.append("arg1")
260    result = "w"
261    for (fn, f, a) in body:
262        result += Ws(f, myenv)
263        result += ws(a, myenv)
264        myenv.append(fn)
265    env.append(name)
266    return result + "v\n"
267
268def build_helloworld():
269    code = (
270        make_func("+2", [
271            ("tmp", "Succ", "arg1"),
272            ("result", "Succ", "tmp"),
273            ])+
274        make_func("+4", [
275            ("tmp", "+2", "arg1"),
276            ("result", "+2", "tmp"),
277            ])+
278        make_func("+8", [
279            ("tmp", "+4", "arg1"),
280            ("result", "+4", "tmp"),
281            ])+
282        make_func("+16", [
283            ("tmp", "+8", "arg1"),
284            ("result", "+8", "tmp"),
285            ])+
286        make_func("+32", [
287            ("tmp", "+16", "arg1"),
288            ("result", "+16", "tmp"),
289            ])+
290        make_func("+64", [
291            ("tmp", "+32", "arg1"),
292            ("result", "+32", "tmp"),
293            ])+
294        make_func("+128", [
295            ("tmp", "+64", "arg1"),
296            ("result", "+64", "tmp"),
297            ])+
298        make_func("print", [
299            ("128w", "+128", "w"),
300            ("...+32w", "+32", "128w"),
301            ("...+64w", "+64", "...+32w"),
302            ("...+16w", "+16", "...+64w"),
303            ("...+1w", "Succ", "...+16w"),
304            ("l", "+4", "...+1w"),
305            ("tmp", "+2", "...+1w"),
306            ("r", "+8", "tmp"),
307           
308            ("o", "+8", "...+16w"),
309
310            ("tmp", "+8", "...+64w"),
311            ("tmp", "+4", "tmp"),
312            ("e", "+2", "tmp"),
313            ("d", "Succ", "tmp"),
314
315            ("tmp", "Succ", "...+32w"),
316            (" ", "+8", "tmp"),
317            ("tmp", "+16", "tmp"),
318            (",", "+4", "tmp"),
319            ("tmp", "+2", "...+32w"),
320            ("!", "+8", "tmp"),
321
322            ("tmp", "Succ", "128w"),
323            ("tmp", "+64", "tmp"),
324            ("H", "+16", "tmp"),
325            ("tmp", "Out", "H"),
326            ("tmp", "Out", "e"),
327            ("tmp", "Out", "l"),
328            ("tmp", "Out", "l"),
329            ("tmp", "Out", "o"),
330            ("tmp", "Out", ","),
331            ("tmp", "Out", " "),
332            ("tmp", "Out", "w"),
333            ("tmp", "Out", "o"),
334            ("tmp", "Out", "r"),
335            ("tmp", "Out", "l"),
336            ("tmp", "Out", "d"),
337            ("tmp", "Out", "!"),
338            ])
339    )
340    import textwrap
341    for line in textwrap.wrap(code):
342        print line
343    run(code)
344
345def _test():
346    import doctest
347    reload(doctest)
348    doctest.testmod()
349    print "ok."
350
351def run_stdin():
352    src = sys.stdin.read()
353    run(src)
354   
355if __name__ == "__main__":
356    #_test()
357    run_stdin()   
358    #build_helloworld()
Note: See TracBrowser for help on using the browser.