40 (196) [14][20][27] 1 true 1 IO erase LLP B,C B C LLPAM LLP LLPAM B&C B & C B;C 2 LLP LLP Prolog B=>C C<=B B C!B! B LLP Prolog ( forall(x,b) x.b ) (

Size: px

Start display at page:

Download "40 (196) [14][20][27] 1 true 1 IO erase LLP B,C B C LLPAM LLP LLPAM B&C B & C B;C 2 LLP LLP Prolog B=>C C<=B B C!B! B LLP Prolog ( forall(x,b) x.b ) ("

まいえたかぎ
5 years ago
Views:

1 (195) 39 LLP LLPAM LLP Prolog LLPAM LO [2], ACL [15], Lolli [13], Lygon [9], Forum LLP IO [17], LLP [3] [4] [14] [20] [21] [24] [26] [27] TLLP [25] WAM LLPAM Lolli 1 LLP 2 Prolog J.-Y. Girard (resource- Miller [16] conscious logic) [7][8] LO, Lygon, Forum An Abstract Machine for a Compiler System of a Linear Logic Programming Language. Mutsunori Banbara,, Nara National College of Technology. Lolli LLP Kyoung-Sun Kang, ( ), Department of Computer Engineering, Division of Electronic and Computer Engineering, Pusan University of Foreign Studies. Naoyuki Tamura,, Department of Computer and Systems Engineering, Kobe [6] [9] [13] [14] [20] IO University., Vol.18, No.1(2001), pp [ ] Prolog ( ) 1 hodas/research/lolli/ 2

2 40 (196) [14][20][27] 1 true 1 IO erase LLP B,C B C LLPAM LLP LLPAM B&C B & C B;C 2 LLP LLP Prolog B=>C C<=B B C!B! B LLP Prolog ( forall(x,b) x.b ) ( ) S G S G R G R x.r G G S R G R G S G S G R G R S R G G R 0 R G ( ) LLP R G Prolog LLP (A ) LLP LLP -<> :- => R ::= A R 1 & R 2 G R G R x.r G ::= 1 A G 1 G 2 G 1 & G 2 G 1 G 2! G R G R G R 1 ( ) G LLP ( ) A C (A ) 3 ( B-<>C B C B C 3 4 Lolli ML P Q 1 C:-B B C B C P Q! P Q ) [14] LLP R ::= A R 1&R 2 G-<>R G=>R forall(x,r) G ::= true erase A G 1,G 2 G 1 &G 2 G 1 ;G 2!G R-<>G R=>G <= :-, ;, &,,, -<>, =>,! :- 2 C ::= A. A:-G.

3 (197) Vol. 18 No. 1 Jan C Prolog S 1 & & S m A x.a A:-G x.(g A) A G 1,G 2 S A G LLP Prolog LLP Lolli Lolli 2.3 LLP 2.2 LLP LLP Prolog (A m 1) R ::= S 1 & & S m S ::= A G A x.s Prolog ( z G LLP ) G R (! G) R G (R 1 & R 2 ) (G R 1 ) &(G R 2 ) G 1 (G 2 R) (G 1 G 2) R G x.r z.(g R[z/x]) x.(r 1 & R 2) ( x.r 1) &( x.r 2) (R 1 & R 2 ) & R 3 R 1 &(R 2 & R 3 ) R-<>G R r(1) LLP?- r(1) -<> true. R G R G S x.a x.(g A) Prolog (R 1 R 2 ) G R 1 (R 2 G) LLP Prolog ( ) Prolog Prolog LLP R-<>G R G r(1) r(x)?- r(1) -<> r(x). X=1 r(1) R G-<>A ( A:-G) S 1 & & S m G S 1 S m 1

4 42 (198)?- (r(x) :- write(x)) -<> r(1). R 1,R 2 r(2). % r(1) r(2)?- r(1) => r(x). X=1, Y=2 X=2, Y=1 G 1,G 2 Prolog G 1,G 2?- (r(1), r(2)) -<> (r(x), r(y)). G 1 &G 2 Prolog G 1,G 2?- r(1) -<> r(2) -<> (r(x), r(y)). R=>G 0 X=1 X=Y=1, Z=2 X=Y=2, Z=1 X=2 r(x) r(y)?- r(1) => r(2) => (r(x), r(x)). R 1 &R 2?- (r(1), r(2)) -<> ((r(x)&r(y)), r(z)). r(1) & r(2)!g G r(1) r(2) X=1 X=2 X=1, Y=2?- (r(1) & r(2)) -<> r(x). => erase Prolog assert p(x) :- q(x) assert r?- forall(x, (p(x) :- q(x))) => r. r LLP assert LLP result(zs) r(x) X r(x) assert reverse(xs, Zs) :- result(zs) -<> rev(xs, []).?- r(x) => (r(1), r(y)). rev([], Ys) :- result(ys). rev([x Xs], Ys) :- rev(xs, [X Ys]). r(1) X=1 r(y) Y X=1 X=2 G 1 G 2 G 1 G 2?- r(1) => r(2) -<> (!r(x), r(y)). erase erase?- (r(1), r(2), r(3)) -<> (r(x), erase) reverse([1,2,3], X) result(x) rev([1,2,3], []) Prolog A LLP rev([],[3,2,1]) result(x) X [3,2,1] Prolog (rev 3 )

5 (199) Vol. 18 No. 1 Jan reverse(xs, Zs) :- rev(xs, [] Zs). path :- rev([], Zs, Zs). (a -<> b) -<> rev([x Xs], Ys, Zs) :- rev(xs, [X Ys], Zs). (b -<> c) -<> (c -<> a) -<> 2. 2 (c -<> d) -<> (d -<> b) -<> a -<> (d, erase) 2 ; (a -<> d) -<> path :- (a -<> b) -<> % a -> b (b -<> c) -<> % b -> c (c -<> a) -<> % c -> a (c -<> d) -<> % c -> d 2. 3 (d -<> b) -<> % d -> b a -<> (d, erase). % a d path 6 forall(x, (test(x) :- X>=2)) (d, erase) d filter([1,2,3], Z) c -<> d c b -<> c a -<> b a erase test(x) :- X>=2 path :- ((a -<> b) & (a -<> d)) -<> (b -<> c) -<> (c -<> a) -<> (c -<> d) -<> (d -<> b) -<> a -<> (d, erase) N- Prolog 1 queen(8,q) [3] result(q) place(8,8) ( solve ;) a -<> place(8,8) c(1),..., c(8), u(2),..., u(16), b a-<> d d(-7),..., d(7) solve(8,[]) (b -<> c) -<> (c -<> a) -<> (c -<> d) -<> (d -<> b) -<> a -<> (d, erase). choose([1,2,3], 2, Z) assert filter([1,2,3], Z) assert % Zs Xs Y choose(xs, Y, Zs) :- forall(x, (test(x) :- X>=Y)) => filter(xs, Zs). filter([], []). (a -<> b) & (a -<> d) filter([x Xs], [X Zs]) :- test(x),!, filter(xs, Zs). a -<> b a -<> d filter([_ Xs], Zs) :- filter(xs, Zs). result(q) Q c, u, d

6 44 (200) queens(n,q) :- result(q)-<> place(n,n). place(1,n) :- c(1)-<>u(2)-<>d(0)-<> solve(n,[]). place(i,n) :- I > 1, I1 is I-1, U1 is 2*I, U2 is 2*I-1, D1 is I-1, D2 is 1-I, c(i)-<>u(u1)-<>u(u2)-<>d(d1)-<>d(d2)-<> place(i1,n). solve(0,q) :- result(q), erase. solve(i,q) :- I > 0, c(j), U is I+J, u(u), D is I-J, d(d), I1 is I-1, solve(i1,[j Q]). queens(n,q) :- gen(1,n,js), N2 is 2*N-1, gen(2,n2,us), D0 is 1-N, gen(d0,n2,ds), sol(n,js,us,ds,q). sol(0,_,_,_,[]). sol(i,js0,us0,ds0,[j Q]) :- I > 0, del(j,js0,js), U is I+J, del(u,us0,us), D is I-J, del(d,ds0,ds), I1 is I-1, sol(i1,js,us,ds,q). del(x,[x Xs],Xs). del(x,[y Ys],[Y Zs]) :- del(x,ys,zs). gen(_,0,[]). gen(i,n,[i Ns]) :- N>0, I1 is I+1, N1 is N-1, gen(i1,n1,ns). 1 Lolli N 2 Prolog N solve I c(j), J u(i+j), d(i-j) I 1 ( 3 ) 2 Prolog N- ( [5] ) LLP D=I-J ( N ) [11], [13], [22] Lolli LLP SML IO BIBD LLP 4 IO LLP (Prolog ) 3 LLP LLP Hodas Miller IO G ( ) G IO [10][12][13] ( ) ML Prolog IO 4 Lolli prove(g, I, O) G I U=I+J 16 8 forall (:- <=) -7

7 (201) Vol. 18 No. 1 Jan :- op(1060, xfy, (&) ). :- op( 950, xfy, (-<>)). :- op( 950, xfy, (=>) ). :- op( 900, fy, (!) ). prove(g) :- I = [], O = [], prove(g, I, O). prove(true, I, I) :-!. prove(erase, I, O) :-!, subcontext(o, I). prove((g1,g2), I, O) :-!, prove(g1, I, M), prove(g2, M, O). prove((g1&g2), I, O) :-!, prove(g1, I, O), prove(g2, I, O). prove((g1;g2), I, O) :-!, (prove(g1, I, O) ; prove(g2, I, O)). prove(!g, I, I) :-!, prove(g, I, I). prove((r -<> G), I, O) :-!, prove(g, [R I], [1 O]). prove((r => G), I, O) :-!, prove(g, [!R I], [!R O]). prove(a, I, O) :- pick(i, O, A). % A is an atomic formula prove(a, I, O) :- pick(i, M, (G -<> A)), % A is an atomic formula prove(g, M, O). subcontext([], [] ). subcontext([1 O], [R I]) :- \+ (R =!(_)), subcontext(o, I). subcontext([r O], [R I]) :- subcontext(o, I). pick(i, I, S) :- rule(s). pick([r I], [1 I], S) :- \+ (R =!(_)), pick_s(r, S). pick([!r I], [!R I], S) :- pick_s(r, S). pick([r I], [R O], S) :- pick(i, O, S). pick_s((r1&r2), S) :-!, (pick_s(r1, S) ; pick_s(r2, S)). pick_s(s, S). rule( append([], Zs, Zs) ). rule(( append(xs, Ys, Zs) -<> append([x Xs], Ys, [X Zs]) )). 4 IO LLP (Prolog ) O 2 Prolog N- G 1 G 2 1 LLP prove((g 1 G 2 )), I, O) : prove((g1,g2), I, O) :-!, prove(g1, I, M), prove(g2, M, O). I G 1 Hodas IO M G 2 G 2 G 1 sol(i,js,us,ds,q) Js, Us, Ds c, u, d 1. : LLP Prolog pick(i,o,a) Prolog I A LLP S

8 46 (202) G 1 2. : pick(i,o,a) & O I IO 1 O IO IO IOL ( ) LLP IOL 1 IO 2 ( ) G 1 & G IO IO [27] 4 prove((g 1 & G 2 ), I, O) : prove((g1&g2), I, O) :-!, prove(g1, I, O), prove(g2, I, O). G 1 G 2 I R G 1 l R, l I G 1 l = 0 I l 0 G 1 O G 2 IO IO IOL L,U I {G} O G 2 G 1 L ( G 1 G 2 1 U )

9 (203) Vol. 18 No. 1 Jan L,U I {1} I (1) subcontext U,L (O, I) L,U I { } O ( ) L,U I {G 1 } M L,U M {G 2 } O L,U I {G 1 G 2 } O ( ) L,U 1 I {G 1 } M change U 1,L+1 (M, N) L+1,U N {G 2 } O thinable L+1 (O) L,U I {G 1 & G 2 } O (&) L,U I {G i } O L,U I {G 1 G 2 } O ( i) L+1,U I {G} O L,U I {! G} O (!) L,U [ R, L I] {G} [ R, U O] L,U I {R G} O ( ) L,U [ R, 0 I] {G} [ R, 0 O] L,U I {R G} O ( ) pick L,U (I, O, A) L,U I {A} O (BC 1) pick L,U (I, M, G A) L,U I {A} O L,U M {G} O (BC 2 ) 5 IO IOL 1 G I, O G 1 r 1,..., r k L,U 1 I {G 1} M M r 1,..., r k L,U I {G} O I L N r 1,..., r k L + 1 ( 0) L+1,U N {G 2 } O G 2 U ( 0 ) r 1,..., r k G 1 & G 2 G 1 U thinable L+1(O) r 1,..., r k L,U I {G 1 & G 2} O (&) 1. G 1 U U 1 G 1 2. U 1 G 1 subcontext U,L([s 1,..., s n], [r 1,..., r n]) L L + 1 U s i = r i s i = R, U (2) G 2 4. G 2 G 1 pick L,U ([r 1,..., r n ], [s 1,..., s n ], S) (1) r i = S 1 & & S m, L S k = S L + 1 s i = S 1 & & S m, U s j = r j IO IOL S 1 & & S m, 0 S k = S s j = 5 U 1 change U 1,L+1 (M, N) G 1 G 2 (&) I change l,l ([r 1,..., r n ], [s 1,..., s n ]) G 2 5 subcontext, pick, change, thinable i = 1, 2,..., n (1) r i = R, L s i = r i (j i) (2) r i = r j (1 j n)

10 48 (204) i = 1, 2,..., n (1) r i = R, l out_of_scope s i = R, l (2) s i = r i ( thinable l ([r 1,..., r n]) r i = R, l l l true R 3.2 R IO pred ( ) code ( ) 1 ( ) p(1) record s n level : ; : ( ); : ( ); ); : ; : out_of_scope : ( pred code end S 1 & & S m S i S i s S 1 n S 1 & & S m m false) R G R G false p(x) X 1 level IO R G L R G r1 : 1; 0 r2 : 2; r1 S 1 & & S m S i r2 s n

11 (205) Vol. 18 No. 1 Jan CLO p(x 1,..., X n ) X 1 n ( "%$!-$ ) p/n r1 S 1! #"%$%&'!() r2 X 1 p/n r1 6 p(x 1,..., X n ) X 1 p/n r1 A1 X 1 p/n r2 Y.(q(X, Y ) p(f(x), Y )) 3.3 LLP LLPAM Prolog 6 WAM [1][23] ( ) LLPAM CLO WAM WAM S [1] 3 P mode read X. Y.(q(X, Y ) p(f(x), Y )) p(f(x), Y ):-q(x, Y ) unify_variable get_structure f/1, A1 unify_variable A1 execute q/2 WAM get structure f/1, A1 A1 f/1 unify_value A3 STR mode write A1 f/1 STR WAM S mode read WAM unify variable A1 read Miller Na- S A1 write dathur n* + #"$,& () P X Y.(q(X, Y ) p(f(x), Y )) unify_variable A3 X A3 unify_variable A3 get_structure f/1, A1 put_value A3, A1 execute q/2

12 50 (206) λprolog [18][19] λprolog D G D R2 : 2 D G LLP D G R RES L LLP D G U IO λprolog LLP λprolog R1 R2 4 LLPAM LLPAM LLPAM LLP 4.2 G 1 G 2 IO IO IOL G 1 G 2 Prolog WAM G 1 G WAM CODE, HEAP, TRAIL, PDL LLPAM SYMBOL, RES, HASH G 1 G 2 G 1 SYMBOL G 1 record pname : ; arity : ; code : ; r1 : 1; r2 : 2 end code G 1 LLPAM mid_with r1 end_with r2 RES HASH U WAM P, CP, S, H, HB, E, B, B0, TR out_of_scope L+1 R : R1 : 1 ( ) RES L,U I {G 1} M I M L,U M {G 2 } O M O G 2 G G 1 & G 2 G 1 & G 2 begin_with begin_with mid_with G 2 RES U (change ) L U L : ( 1) U : ( 1)

13 (207) Vol. 18 No. 1 Jan end_with RES L RES L out_of_scope out_of_scope (thinable )U L IO IOL [14] (&) begin_with 4.6 R G L,U 1 mid_with R S 1 & & S m change U 1,L+1 (M, N) L+1,U N {G 2} O L L + 1 R G U 1 U 1. R ( ) end_with thinable L+1 (O) 4.4! G! G 3. G begin_bang G end_bang R G begin_bang L end bang L 4.5 S i ) top begin_imp Y i S 1 S m mid_imp m top G top Hodas I {G 1 } M U U 1 R G R G Y i 2. R S i RES (R m ) 4. R 5. R out_of_scope true R G G R R RES out_of_scope R G (... end_imp Y i

14 52 (208) out_of_scope true begin_imp Y i R Y i mid_imp m RES R m R 1 S A G s R m A p/n S X 1, n m end_imp Y i RES Y i L L: unify_variable A n+1 Y i unify_variable A n+2 n m Y i Y i + m 1 (unify_variable A n+m ) out_of_scope true G false Y i 4.7 R G R G ( A n+1 S i ) A G begin_exp_imp Y i S 1... S m mid_exp_imp m G end_exp_imp Y i 3. begin_exp_imp Y i begin_imp Y i mid_exp_imp m mid_imp m end_exp_imp Y i false Y i 4.8 S..., X m S... A A 1 A n unify_variable A:-G S 1. put A A i 2. A j L X 1,..., X m put_closure L, n, A i ( L n) HEAP Y i n m A i mode Y i Y i + m 1 write

15 (209) Vol. 18 No. 1 Jan A i := CLO, H ; HEAP[H] := L; H := H + 1; HEAP[H] := n; H := H + 1; mode := write; add_res A i, A j (b) S ( A i A j ) RES (c) S RES[R].level := L; RES[R].out_of_scope := false; 1 call p/n ( RES[R].pred := A i ; RES[R].code := A j ; execute p/n) 2 3 A i R ; R := R + 1; p/n try_resource L s n mid_imp WAM try L R1 add_exp_res A i, A j A i A j R1, R2 RES R1, R2 RES[R].level := 0; RES[R].out_of_scope := false; BP R1, R2 L RES[R].pred := A i ; RES[R].code := A j ; A i trust_resource L R ; L R := R + 1; s n mid_exp_imp B B 4.9 LLP p/n A i ( RES A i ) p/n 1. 2 R1 R2 2. R1 R2 p/n S (a) S out_of_scope 3. p/n R2 restore_resource retry_resource_else L L P pickup_resource p/n, A i, L R1 (R1 R2) R1 ( R2) L

16 54 (210) p/n: pickup_resource p/n, A n+1, L try_resource L 1 L 0: restore_resource pickup_resource p/n, A n+1, L 2 retry_resource_else L 0 L 1: consume A n+1, A n+2 execute_closure A n+2 L 2: trust_resource L L : p/n 7 p/n LLPAM found := false; while R1 nil found do begin r := car(r1); R1 := cdr(r1); found := RES[r].pred = p/n RES[r].out_of_scope RES[r].level = 0 L; end; while R2 nil found do begin r := car(r2); R2 := cdr(r2); found := RES[r].pred = p/n RES[r].out_of_scope RES[r].level = 0 L; end; if found then A i := r else P := L; p/n pickup_resource ( L ) try_resource (R1, R2 ) consume execute_closure restore_resource pickup_resource trust_resource retry_resource_else R1, R2 consume execute_closure L 0 restore_resource ( 8 ) consume A i, A j R1, R2 A i A i U 4.10 WAM A i LLPAM R, L, U A j execute_closure A i A i A i = CLO,c S c + 2 mode add_res, add_exp_res read HEAP[c] p/n 7 consume, mid_with

17 (211) Vol. 18 No. 1 Jan p/n: pickup_resource p/n, A n+1, fail if_no_resource L 1 try_resource L 1 end_imp, end_exp_imp L 0: restore_resource out_of_scope pickup_resource p/n, A n+1, L 2 if_no_resource L 3 retry_resource_else L 0 L 1: consume A n+1, A n+2 execute_closure A 4.11 n+2 L 2: trust_resource fail WAM L 3: trust_resource L 1 LLPAM 8 p/n LLPAM ( ) G 1 & G 2,! G, R G, R G end_with, end_bang LLP call LLPAM LLP (R 1 R 2 R n) G ( R 1 (R 2 (R n G) )) begin_imp, end_imp n Y n end_imp Y i n end_imp Y i,n ( Y i ) if_no_resource L begin_imp Y i R 1 mid_imp m 1 R 2 p/n ( 7) mid_imp m 2... R n trust_resource mid_imp m n G end_imp Y i, n R1 R2 L p/n 8 pickup_resource if_no_resource 4.12 LLPAM 2. 1 reverse LLPAM m i R i 9 rev WAM LLP 2. 3 choose test 10

18 56 (212) 2 N N-Queens SICStus (msec) LLP (msec) 8 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (5 5) SICStus (msec) LLP (msec) Knight Tour Prolog SICStus (msec) LLP (msec) SWI (msec) boyer browse cal chat parser ham poly queens 8 ( ) queens 10 ( ) queens 16 ( ) zebra boyer LLP LLPAM LLPAM (C ) ( WAM ) 2 Prolog N- SICStus Prolog ( 3.7.1, ) 1 Lolli N- 2 N- LLP (

19 (213) Vol. 18 No. 1 Jan % reverse(xs,zs) :- result(zs) -<> rev(xs,[]). reverse/2: % choose(xs,y,zs) choose/3: allocate 1 % Y1 allocate 1 begin_imp Y1 begin_exp_imp Y1 put_structure result/1, A3 % A3 = result(zs) unify_value A2 put_structure test/1, A4 unify_variable A6 put_closure L, 1, A4 % put_closure L, 1, A5 unify_value A2 % Zs unify_value A2 add_res A3, A4 mid_imp 1 put_constant [] /0, A2 call rev/2 % rev(xs,[]) add_exp_res A4, A5 mid_exp_imp 1 put_value A3, A2 call filter/2 end_imp Y1 deallocate proceed end_exp_imp Y1 deallocate proceed % Y1 % A4 = test(_) % % Y % % filter(xs,zs) % result(zs) % forall(x, (test(x) :- X>=Y)) L: unify_value A1 % Zs A1 L: unify_variable A2 % Y proceed execute >= /2 % X>=Y 9 reverse LLPAM test/1: pickup_resource test/1, A2, fail if_no_resource L1 0.43) try_resource L1 LLPAM L0: restore_resource pickup_resource test/1, A2, L2 if_no_resource L3 2 N 8 14 retry_resource_else L0 L1: consume A2, A3 ( ) N 15, 20, 25 execute_closure A3 ( ) N L2: trust_resource fail 8 3 N L3: trust_resource L1 10 choose test LLPAM 5 5 ( ( 4 ) SICStus Prolog ) ( 3.7.1, ) LLP boyer ( ) LLP SICStus Prolog 2.71 (switch_on_structure switch_on_constant ) boyer LLP SICStus Prolog 1.86 LLP SWI- 10% Prolog( 3.2.6) 2 30% LLPAM LLPAM Prolog ( ) Prolog MMX Pentium 266MHz 128M

20 58 (214) Linux OS 6 Lolli LLP x.g LLP Prolog λprolog ( [18]) Lolli LLP LLPAM (higher-order quantification, unification of λ-term) LLPAM Prolog WAM (Warren Abstract Machine) LLPAM LLP IO Lolli λprolog [ 1 ] Aït-Kaci, H.: Warren s Abstract Machine, The MIT Press, ( documents/wam.html). [ 2 ] Andreoli, J.-M. and Pareschi, R.: Linear Objects: Logical Processes with Built-In Inheritance, New Generation Computing, Vol. 9(1991), pp N- Prolog LLP [ 3 ] Banbara, M. and Tamura, N.: Compiling Resources in a Linear Logic Programming Language, SICStus Prolog Proceedings of Post-JICSLP 98 Workshop on Parallelism and Implementation Technology for Logic LLP N 8 3 N Programming Languages, June 1998, pp [ 4 ] Banbara, M. and Tamura, N.: Translating a Linear Logic Programming Language into Java, Pro- LLP ceedings of ICLP 99 Workshop on Parallelism and Implementation Technology for (Constraint) Logic LLPAM Programming Languages, November 1999, pp. 19 Hodas [14] 39. [ 5 ] Bratko, I.: Prolog programming for artificial intelligence, Addison-Wesley, A R 1 & R 2 G R G R x.r [ 6 ] Cervesato, I., Hodas, J. S., and Pfenning, F.: Efficient resource management for linear logic proof search, Proceedings of the 1996 International Workshop on Extensions of Logic Programming, Springer-Verlag LNAI 1050, March 1996, pp [14] [ 7 ] Girard, J.-Y.: Linear Logic, Theoretical Computer Science, Vol. 50(1987), pp [ 8 ] Girard, J.-Y.: Linear Logic: Its Syntax and Semantics, Advances in Linear Logic(Girard, J.-Y., Lafont, Y., and Regnier, L.(eds.)), Cambridge U- niversity Press, 1995, pp Proceedings of the Workshop on Linear Logic, Ithaca, New York, June 1993.

21 (215) Vol. 18 No. 1 Jan [ 9 ] Harland, J. and Winikoff, M.: Implementing the Linear Logic Programming Language Lygon, Proceedings of the 1995 International Logic Programming Symposium(Lloyd, J.(ed.)), Portland, Oregon, 1995, pp [10] Hodas, J. S.: Lolli: An Extension of λprolog with Linear Context Management, Workshop on the λprolog Programming Language(Miller, D.(ed.)), Philadelphia, Pennsylvania, August 1992, pp [11] Hodas, J. S.: Specifying Filler-Gap Dependency Parsers in a Linear-Logic Programming Language, Proceedings of the Joint International Conference and Symposium on Logic Programming(Apt, K.(ed.)), Washington, DC, November 1992, p- p [12] Hodas, J. S.: Logic Programming in Intuitionistic Linear Logic: Theory, Design and Implementation, PhD Thesis, University of Pennsylvania, Department of Computer and Information Science, [13] Hodas, J. S. and Miller, D.: Logic Programming in a Fragment of Intuitionistic Linear Logic, Information and Computation, Vol. 110,No. 2(1994), p- p Extended abstract in the Proceedings of the Sixth Annual Symposium on Logic in Computer Science, Amsterdam, July 15 18, [14] Hodas, J. S., Watkins, K., Tamura, N., and Kang, K.-S.: Efficient Implementation of a Linear Logic Programming Language, Proceedings of the 1998 International Conference and Symposium on Logic Programming, June 1998, pp [15] Kobayashi, N. and Yonezawa, A.: ACL A Concurrent Linear Logic Programming Paradigm, Proceedings of the 1993 International Logic Programming Symposium(Miller, D.(ed.)), Vancouver, Canada, MIT Press, October 1993, pp [16] Miller, D., Nadathur, G., Pfenning, F., and Scedrov, A.: Uniform proofs as a foundation for logic programming, Annals of Pure and Applied Logic, Vol. 51(1991), pp [17] Miller, D.: A Multiple-Conclusion Specification Logic, Theoretical Computer Science, Vol. 165,No. 1(1996), pp [18] Nadathur, G., Jayaraman, B., and Kwon, K.: Scoping Constructs in Logic Programming: Implementation Problems and their Solution, Journal of Logic Programming, Vol. 25(2)(1995), pp [19] Nadathur, G. and Miller, D.: An Overview of λprolog, Logic Programming: Proceedings of the Fifth International Conference and Symposium, Volume 1(Kowalski, R. A. and Bowen, K. A.(eds.)), Cambridge, Massachusetts, MIT Press, August 1988, pp [20] Tamura, N. and Kaneda, Y.: Extension of WAM for a linear logic programming language, Second Fuji International Workshop on Functional and Logic Programming(Ida, T., Ohori, A., and Takeichi, M.(eds.)), World Scientific, Nov. 1996, pp [21] Tamura, N. and Kaneda, Y.: A WAM model for a linear logic programming language, Proceedings of the 9th Symposium on Industrial Applications of Prolog (INAP 96), Oct. 1996, pp (in Japanese). [22] Tamura, N. and Kaneda, Y.: A Compiler System of a Linear Logic Programming Language, Proceedings of the IASTED International Conference Artificial Intelligence and Soft Computing, July 1997, pp [23] Warren, D. H. D.: An abstract Prolog instruction set, Technical Report Technical Note 309, SRI International, Menlo Park, CA, Oct [24], :, No. 7, , pp [25],,,, :, :, Vol. 41,No. SIG 4 (PRO 7)(2000), pp [26],, : Java, :, Vol. 40,No. SIG 10 (PRO 5)(1999), pp [27],, :,, Vol. 18,No. 0(2001), pp

shift/reset [13] 2 shift / reset shift reset k call/cc reset shift k shift (...) k 1 + shift(fun k -> 2 * (k 3)) k 2 * (1 + 3) 8 reset shift reset (..

shift/reset [13] 2 shift / reset shift reset k call/cc reset shift k shift (...) k 1 + shift(fun k -> 2 * (k 3)) k 2 * (1 + 3) 8 reset shift reset (.. arisa@pllab.is.ocha.ac.jp asai@is.ocha.ac.jp shift / reset CPS shift / reset CPS CPS 1 [3, 5] goto try/catch raise call/cc [17] control/prompt [8], shift/reset [5] control/prompt, shift/reset call/cc (continuationpassing