[Lua]50行のコードの解釈器は、lambada calculusを実証するために使用されます.
18543 ワード
うん、経過を書きに来ました.
よく知っています.Belleve牛を使ってjavascriptで簡潔なlisp解凍器を書きました.
=>
私も一つ書きたいですが、luaで書いたら、どれぐらい簡単ですか?
=>
去勢したscheme解凍器を書きました.lambada/ifの二つのspecial formと+-=printのいくつかの過程を含みます.60行のコードです.
=>
もっと簡素化できますか?例えばifを抜きにしますか?
=>
検索、うん、lamda calculusが手伝ってくれます.
=>
wiki上のlamda calculusの「Enccoding datatypes」の部分を読みます.
=>
schemeスクリプトを書き換えて、Y-combinatorで再帰を実現して、church numeralで数字を表して、church numeralの上の基本的な論理、演算、関係演算を実現して、最後にこれらの基本的な演算でfor-eachとfib過程を書きます.
=>
解釈器からキーワードifを除去し、処理+-=、printを書き換えてchurch numeralを印刷できるようにします.
=>
さらに、単独パラメータプロセスとしてLambadaを実装し、マルチパラメータlambankdaの声明と呼び出しがシンタックス飴になりました.したがって、すべてのプロセスはfully curriedです.haskellと同じです.
=>
schemeシナリオはfibonacciを印刷するためにもっと多くのことをする必要がありますが、しかし、解凍器はこの門去勢schemeのためにlambandキーワードを提供しただけです.結果として、匿名プロセスという基本的要素だけをサポートする言語において、強力な計算能力をどのように実現するかを実証した.もちろん、このすべてを完成するのはラmbada calculus理論によるものです.過程も結果もとても面白いです.
schemeコードは、lamdaのこのspecial formと基本プロセスprintのみをサポートします.
luaインタプリタコード:
ドライバ:
結果:
ソースはここですhttps://github.com/PublicScan/LambdaCalculus/tree/c4a64b162b7049a6d278c86aaaa4a7c0750d7fa7
よく知っています.Belleve牛を使ってjavascriptで簡潔なlisp解凍器を書きました.
=>
私も一つ書きたいですが、luaで書いたら、どれぐらい簡単ですか?
=>
去勢したscheme解凍器を書きました.lambada/ifの二つのspecial formと+-=printのいくつかの過程を含みます.60行のコードです.
=>
もっと簡素化できますか?例えばifを抜きにしますか?
=>
検索、うん、lamda calculusが手伝ってくれます.
=>
wiki上のlamda calculusの「Enccoding datatypes」の部分を読みます.
=>
schemeスクリプトを書き換えて、Y-combinatorで再帰を実現して、church numeralで数字を表して、church numeralの上の基本的な論理、演算、関係演算を実現して、最後にこれらの基本的な演算でfor-eachとfib過程を書きます.
=>
解釈器からキーワードifを除去し、処理+-=、printを書き換えてchurch numeralを印刷できるようにします.
=>
さらに、単独パラメータプロセスとしてLambadaを実装し、マルチパラメータlambankdaの声明と呼び出しがシンタックス飴になりました.したがって、すべてのプロセスはfully curriedです.haskellと同じです.
=>
schemeシナリオはfibonacciを印刷するためにもっと多くのことをする必要がありますが、しかし、解凍器はこの門去勢schemeのためにlambandキーワードを提供しただけです.結果として、匿名プロセスという基本的要素だけをサポートする言語において、強力な計算能力をどのように実現するかを実証した.もちろん、このすべてを完成するのはラmbada calculus理論によるものです.過程も結果もとても面白いです.
schemeコードは、lamdaのこのspecial formと基本プロセスprintのみをサポートします.
1 ((lambda (zero one add mul pow sub1 true false and or)
2 ((lambda (sub not zero? two Y)
3 ((lambda (less-equal? equal? three four)
4 ;------------------------------
5 ((lambda (for-each fib)
6 (for-each (lambda (i) (print (fib zero one zero i))) zero (mul four four))
7 )
8 (Y
9 (lambda (self)
10 (lambda (f i n)
11 (f i)
12 (((equal? i n)
13 (lambda () i)
14 (lambda () (self f (add i one) n))))
15 )
16 ))
17 (Y
18 (lambda (self)
19 (lambda (a b i n)
20 (((equal? i n)
21 (lambda () a)
22 (lambda () (self b (add a b) (add i one) n))))
23 )
24 ))
25 )
26 ;------------------------------
27 )
28 (lambda (m n) (zero? (sub m n)))
29 (lambda (m n) (and (zero? (sub m n)) (zero? (sub n m))))
30 (add two one)
31 (add two two)
32 ))
33 (lambda (m n) (n sub1 m))
34 (lambda (a) (a false true))
35 (lambda (n) (n (lambda (x) false) true))
36 (add one one)
37 (lambda (f)
38 ((lambda (g) (g g))
39 (lambda (g) (f (lambda (a) ((g g) a))))))
40 ))
41 (lambda (f x) x)
42 (lambda (f x) (f x))
43 (lambda (m n f x) (m f (n f x)))
44 (lambda (m n f) (m (n f)))
45 (lambda (e b) (e b))
46 (lambda (n f x)
47 (((n
48 (lambda (g h) (h (g f))))
49 (lambda (u) x))
50 (lambda (u) u)))
51 (lambda (a b) a)
52 (lambda (a b) b)
53 (lambda (a b) (a b a))
54 (lambda (a b) (a a b))
55 )luaインタプリタコード:
1 function S_parse(s)
2 s = string.gsub(s, ';[^
]+
', '')
3 s = string.gsub(s, '%s+', ',')
4 s = string.gsub(s, '[%(%)]', {['(']='{',[')']='}'})
5 s = string.gsub(s, '[^{},%d][^{},]*', '"%1"')
6 return assert(loadstring(string.format("return {%s}", s)))()[1]
7 end
8 function S_lookupVar(vm, env, name)
9 while env do
10 if env[name] then return env[name] end
11 env = env[vm]
12 end
13 end
14 function S_createLambda(vm, env, argIdx, expArgs, expBody)
15 return function(arg)
16 local newEnv = {[vm]=env, [expArgs[argIdx]]=arg}
17 if argIdx == #expArgs then
18 for i = 3, #expBody - 1 do S_interpret(vm, newEnv, expBody[i]) end
19 return S_interpret(vm, newEnv, expBody[#expBody])
20 else
21 return S_createLambda(vm, newEnv, argIdx + 1, expArgs, expBody)
22 end
23 end
24 end
25 function S_interpret(vm, env, exp)
26 if type(exp) == 'string' then
27 return S_lookupVar(vm, env, exp)
28 elseif exp[1] == 'lambda' then
29 return S_createLambda(vm, env, 1, #exp[2] > 0 and exp[2] or {'_'}, exp)
30 else
31 local p = S_interpret(vm, env, exp[1])
32 for i = 2, math.max(#exp, 2) do
33 p = p(exp[i] and S_interpret(vm, env, exp[i]) or nil)
34 end
35 return p
36 end
37 end
38 function S_createVM()
39 return {
40 G = {
41 ['print'] = function(n) print(n(function(i) return i + 1 end)(0)) end,
42 },
43 }
44 end
45 function S_eval(vm, s)
46 return S_interpret(vm, vm.G, S_parse(s))
47 end
48
49 S_eval(S_createVM(), io.read('*a'))ドライバ:
1 #! /bin/bash
2 cat script.rkt | lua main.lua結果:
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987ソースはここですhttps://github.com/PublicScan/LambdaCalculus/tree/c4a64b162b7049a6d278c86aaaa4a7c0750d7fa7