Guest User

Untitled

a guest
Oct 19th, 2017
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 15.74 KB | None | 0 0
  1. l="("
  2. def S(s):
  3. if s[0]!=l:return s
  4. if s[1]=="\":g=s.find('.');return"(\ %s. %s)"%(s[3:g],S(s[g+2:-1]))
  5. i=2;c=s[1]==l
  6. while c:c+=(s[i]==l)-(s[i]==')');i+=1
  7. t=S(s[1:i])
  8. z=s[i+1:-1]
  9. if l!=t[0]:return"(%s %s)"%(t,S(z))
  10. g=t.find('.')
  11. t=S(t[g+2:-1]).replace(t[3:g],z)
  12. if t!=s:t=S(t)
  13. return t
  14. print S(raw_input())
  15.  
  16. atom(x){
  17. return m[x]>>5==3;
  18. }
  19.  
  20. #include<stdio.h>
  21. #include<string.h>
  22. #define X m[x]
  23. #define R return
  24. char*n,*m;int u,w,d;C(x,y){w=n-m;n+=sprintf(n,y?"(%s %s)":"(%s)",&X,m+y)+1;R w;}T(x){R X>>5==3;}
  25. L(x){R X==92;}O(x,j){w=n-m;memcpy(n,&X,j);n+=j;*n++=0;R w;}E(x){X==' '?++x:0;R
  26. X==41?0:L(x)?O(x,4):P(x);}P(x){d=0,w=x;do{X==40?d++:X==41?d--:0;++x;}while(d>0);R
  27. O(w,x-w);}D(x){u=E(x+1);R u?E(x+1+strlen(m+u)):0;}V(x){int a=E(x+1),b=D(x);R
  28. T(x)|T(a)?x:L(a)?C(a,V(b)):L(E(a+1))?V(S(V(b),E(a+3),D(a))):V(C(V(a),b?V(b):0));}S(w,y,x){R
  29. T(x)?(X==m[y]?w:x):C(L(w+1)?E(x+1):S(w,y,E(x+1)),D(x)?S(w,y,D(x)):0);}
  30. Y(char*s){n+=strlen(s=strcpy(n,s))+1;printf("%sn%snn",s,m+V(s-m));n=m+1;}
  31.  
  32. char*s[]={
  33. "((\ a. a) (b))",
  34. "((\ x. x) (\ y. (\ z. z)))",
  35. "(\ x. ((\ y. y) x))",
  36. "(((\ x. (\ y. x)) (\ a. a)) (\ b. b))",
  37. "((\ x. (\ y. y)) (\ a. a))",
  38. "(((\ x. (\ y. y)) (\ a. a)) (\ b. b))",
  39. "((\x. (x x)) (\x. (x x)))",0};
  40. #include<unistd.h>
  41. main(){char**k;n=m=sbrk(4096);*n++=0;for(k=s;*k;k++)Y(*k);R 0;}
  42.  
  43. #include<stdio.h>
  44. #include<string.h>
  45. #define K(j) strncpy(n,m+x,j);n+=j;goto N;
  46. #define R return
  47. #define X m[x]
  48. #define L =='\'
  49. char*m,*n;T(x){R islower(X);}V(x){int a=E(x+1);R
  50. T(x)?x:T(a)?x:m[a]L?C(a,V(D(x))):m[E(a+1)]L?V(S(V(D(x)),E(a+3),D(a))):V(C(V(a),D(x)?V(D(x)):0));}
  51. C(x,y){char*t=n;sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y);n+=strlen(n)+1;R
  52. t-m;}Y(char*s){char*t=strcpy(n,s);n+=strlen(n)+1;printf("%s=>%sn",s,m+V(t-m));n=m+1;}S(x,y,z){R
  53. T(z)?(m[z]==m[y]?x:z):C(m[z+1]L?E(z+1):S(x,y,E(z+1)),D(z)?S(x,y,D(z)):0);}D(x){R
  54. E(x+1)?E(x+strlen(m+E(x+1))+1):0;}E(x){char*t=n,d=0;if(X==' ')++x;if(T(x)){K(1)}if(X
  55. L){K(4)}do{d=X?(X=='('?d+1:(X==')'?d-1:d)):0;*n++=m[x++];}while(d);N:*n++=0;R t-m;}
  56.  
  57. char*samp[]={
  58. "a","a","b","b",
  59. "((\ a. a) (b))", "(b)",
  60. "((\ x. x) (\ y. (\ z. z)))", "(\ y. (\ z. z))",
  61. "(\ x. ((\ y. y) x))", "(\ x. x)",
  62. "(((\ x. (\ y. x)) (\ a. a)) (\ b. b))", "(\ a. a)",
  63. "((\ x. (\ y. y)) (\ a. a))", "(\ y. y)",
  64. "(((\ x. (\ y. y)) (\ a. a)) (\ b. b))", "(\ b. b)",
  65. "((\x. (x x)) (\x. (x x)))", "undef",
  66. NULL};
  67. #include<unistd.h>
  68.  
  69. unsigned sz;
  70. #include<signal.h>
  71. void fix(x){signal(SIGSEGV,fix);brk(m+(sz*=2));}
  72. main(){
  73. char**t;
  74. signal(SIGSEGV,fix);
  75. m=n=sbrk(sz=10*getpagesize());
  76. *n++=0;
  77. for(t=samp;*t;t+=2){
  78. Y(*t);
  79. printf("s.b. => %snn", t[1]);
  80. }
  81. return 0;
  82. }
  83.  
  84. #include<stdio.h>
  85. #include<string.h>
  86. char*m,*n; //memory_base, memory_next
  87. atom(x){ // x is an atom if it is a cursor to a lowercase alpha char.
  88. return x?(islower(m[x])?m[x]:0):0;
  89. }
  90. eq(x,y){ // x and y are equal if they are both atoms, the same atom.
  91. return x&&y&&atom(x)==atom(y);
  92. }
  93. cell(x){ // return a copy of the list-string by cursor, by parsing
  94. char*t=n,d=0;
  95. if(!x||!m[x])
  96. return 0;
  97. if(m[x]==' ')
  98. ++x;
  99. if(atom(x)){
  100. *n++=m[x];
  101. *n++=0;
  102. return(n-m)-2;
  103. }
  104. if(m[x]=='\'){ // our lambda symbol
  105. memcpy(n,m+x,4);
  106. n+=4;
  107. *n++=0;
  108. return(n-m)-5;
  109. }
  110. do{ // um ...
  111. d=m[x]?(m[x]=='('?d+1:(m[x]==')'?d-1:d)):0;
  112. *n++=m[x++];
  113. }while(d);
  114. *n++=0;
  115. return t-m;
  116. }
  117. car(x){ // return (copy of) first element
  118. return x?cell(x+1):0;
  119. }
  120. cdr(x){ // return (copy of) rest of list
  121. return car(x)?cell(x+strlen(m+car(x))+1):0;
  122. }
  123. cons(x,y){ // return new list containing first x and rest y
  124. char*t=n;
  125. return x?(sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y),n+=strlen(n)+1,t-m):0;
  126. }
  127. subst(x,y,z){ // substitute x for z in y
  128. if(!x||!y||!z)
  129. return 0;
  130. return atom(z)? (eq(z,y)?x:z):
  131. cons(m[z+1]=='\'?car(z):
  132. subst(x,y,car(z)),cdr(z)?subst(x,y,cdr(z)):0);
  133. }
  134. eval(x){ // evaluate a lambda expression
  135. int a;
  136. return atom(x)?x:
  137. atom(a=car(x))?x:
  138. m[a]=='\'?cons(a,eval(cdr(x))):
  139. m[car(a)]=='\'?eval(subst(eval(cdr(x)),cell(a+3),cdr(a))):
  140. eval( cons(eval(a),cdr(x)?eval(cdr(x)):0));
  141. }
  142. try(char*s){ // handler
  143. char*t=strcpy(n,s);
  144. n+=strlen(n)+1;
  145. printf("input: %sn", s);
  146. printf("eval => %sn", m+eval(t-m));
  147. n=m+1;
  148. }
  149.  
  150. 00000000 18 18 18 18 18 18 44 45 1a 10 18 18 45 7f fb cf |......DE....E...|
  151. 00000010 f0 b9 fe 00 78 7f 0b 6f cf f8 7f c0 0b 9f de 7e |....x..o.......~|
  152. 00000020 f2 cf e1 b0 bf e1 ff 0e 6f 79 ff d3 40 f3 a4 46 |........oy..@..F|
  153. 00000030 87 34 0a a8 d0 80 2b 0b ff 78 16 ff fe 16 fc 2d |.4....+..x.....-|
  154. 00000040 ff ff fc ab ff 06 55 1a 00 58 57 ef 81 15 bf bf |......U..XW.....|
  155. 00000050 0b 6f 02 fd 60 7e 16 f7 3d 11 7f 3f 00 df fb c0 |.o..`~..=..?....|
  156. 00000060 bf f9 7e f8 85 5f e0 60 df 70 b7 ff ff e5 5f f0 |..~.._.`.p...._.|
  157. 00000070 30 30 6f dd 80 5b b3 41 be 85 bf ff ca a3 42 0a |00o..[.A......B.|
  158. 00000080 c2 bc c0 37 83 00 c0 3c 2b ff 9f f5 10 22 bc 03 |...7...<+...."..|
  159. 00000090 3d f0 71 95 f6 57 d0 60 18 05 df ef c0 30 0b bf |=.q..W.`.....0..|
  160. 000000a0 7f 01 9a c1 70 2e 80 5b ff e7 c2 df fe e1 15 55 |....p..[.......U|
  161. 000000b0 75 55 41 82 0a 20 28 29 5c 61 |uUA.. ()a|
  162. 000000ba
  163.  
  164. cc -O2 -DM=0x100000 -m32 -std=c99 uni.c -o uni
  165. echo -n "010000011100111001110100000011100111010" > threetwo.blc
  166. cat symbolic.Blc threetwo.blc | ./uni
  167. (a b a (a (a b))) (a b a (a b))
  168. a (b c b (b c)) ((b c b (b c)) ((b c b (b c)) a))
  169. a b (c d c (c d)) ((c d c (c d)) a) ((c d c (c d)) ((c d c (c d)) a) b)
  170. a b (c (d e d (d e)) a ((d e d (d e)) a c)) ((c d c (c d)) ((c d c (c d)) a) b)
  171. a b (c d c (c d)) a ((c d c (c d)) a ((c d c (c d)) ((c d c (c d)) a) b))
  172. a b (c a (a c)) ((c d c (c d)) a ((c d c (c d)) ((c d c (c d)) a) b))
  173. a b a (a ((c d c (c d)) a ((c d c (c d)) ((c d c (c d)) a) b)))
  174. a b a (a ((c a (a c)) ((c d c (c d)) ((c d c (c d)) a) b)))
  175. a b a (a (a (a ((c d c (c d)) ((c d c (c d)) a) b))))
  176. a b a (a (a (a ((c (d e d (d e)) a ((d e d (d e)) a c)) b))))
  177. a b a (a (a (a ((c d c (c d)) a ((c d c (c d)) a b)))))
  178. a b a (a (a (a ((c a (a c)) ((c d c (c d)) a b)))))
  179. a b a (a (a (a (a (a ((c d c (c d)) a b))))))
  180. a b a (a (a (a (a (a ((c a (a c)) b))))))
  181. a b a (a (a (a (a (a (a (a b)))))))
  182.  
  183. @10\@10\@10\@10\@10\@10@@@@@@1010@\@10\@10@@@@1111111111101
  184. 1110@11111110@@110@11111110\\@1110@1111110@@101101111110@111111110@111
  185. 111110\\@@110@111111011110@11111011110@@10@1111110@10110@@111111110@111
  186. 111110@110@101111011110@1111111111010@1010\@1110@11010@@@1010@110@1010
  187. @@@@@@1010@\\@@@10@@111111111011110\@@101111111111111110@@101111110
  188. @@10111111111111111111111110@@@@1111111110\110@@@@@1010\\@@10@@@1111101
  189. 11110\@@@@10111111101111110@@1011011110\@@11111010110\@111110@@1011110
  190. 1110@111010101011111110@111110\@101111111111011110\@@11111111110@@11111
  191. 011111010@@@@11111110\@10\1101111101110@@1011111111111111111111110@@@@1
  192. 11111110\@10\@10\11011111101110110\@@101110110@1010\11011111010@@1011
  193. 111111111111110@@@@@1010@\@@@10@@@1110@10\@1011110\110\@10\@1110
  194. @@@11111111110@111111110101010\@@@@1110\@10@1110111110\1110110@@@1111
  195. 0110@@@1111010\110\@10\@@1101111111101111110\@10\@@1101111110111111
  196. 10\110@1010110\101110\@@11010\@@1011111111111110@11110@@1011111111111
  197. 101110@@@@@@@@@11010101010101010\110\10\101010\1010\1010@@@110110
  198. @
  199.  
  200. f=->u,r{r.chars.take_while{|c|u+=c==?(?1:c==?)?-1:0;u>0}*''}
  201. l=->x{x=~/^((*)(\ (w+). (.*)/&&(b,v,r=$1,$2,$3;e=f[1,r];(e==s=l[e])?b==''?x:(s=f[2,r];(x==y=b.chop+e.gsub(v,s[2+e.size..-1])+r[1+s.size..-1])?x:l[y]):(b+'(\ '+v+'. '+s+r[e.size..-1]))||x}
  202.  
  203. puts l["((\ x. (\ y. x)) (\ a. a))"] # <= ( y. ( a. a))
  204.  
  205. L=(.0==\)
  206. A=->it.forEach?&&it.0!=\
  207. V=(.toFixed?)
  208. S=(a,b,t=-1,l=0)->|L a=>[\,S(a.1,b,t,l+1)];|A a=>(map (->S(a[it],b,t,l)),[0 1]);|a==l+-1=>S(b,0,l+-1,0)||a|l-1<a=>a+t;|_=>a
  209. R=(a)->|L a=>[\,R a.1]|(A a)&&(L a.0)=>R(S(R(a.0),R(a.1)).1)|_=>a
  210.  
  211. a = [\,[\,[1 [1 0]]]]
  212. b = [\,[\,[1 [1 [1 0]]]]]
  213. console.log R [a, b]
  214. # outputs ["\",["\",[1,[1,[1,[1,[1,[1,[1,[1,[1,0]]]]]]]]]]]
  215.  
  216. # Just type checking
  217. λ = 100
  218. isλ = (.0==λ)
  219. isA = -> it.forEach? && it.0!=λ
  220. isV = (.toFixed?)
  221.  
  222. # Performs substitutions in trees
  223. # a: trees to perform substitution in
  224. # b: substitute bound variables by this, if != void
  225. # f: add this value to all unbound variables
  226. # l: internal (depth)
  227. S = (a,b,t=-1,l=0) ->
  228. switch
  229. | isλ a => [λ, (S a.1, b, t, l+1)]
  230. | isA a => [(S a.0, b, t, l), (S a.1, b, t, l)]
  231. | a == l - 1 => (S b, 0, (l - 1), 0) || a
  232. | l - 1 < a < 100 => a + t
  233. | _ => a
  234.  
  235. # Performs the beta-reduction
  236. R = (a) ->
  237. switch
  238. | (isλ a) => [λ,R a.1]
  239. | (isA a) && (isλ a.0) => R(S(R(a.0),R(a.1)).1)
  240. | _ => a
  241.  
  242. # Test
  243. a = [λ,[λ,[1 [1 0]]]]
  244. b = [λ,[λ,[1 [1 [1 0]]]]]
  245. console.log show R [a, b]
  246.  
  247. (=
  248. f[is cons?&car._'λ]n[if
  249. atom._ _
  250. f._ `(λ,_.1,n:_.2)(=
  251. c n:_.0
  252. e _)(if
  253. f.c(n:deep-map[if(is
  254. c.1 _)e.1
  255. _]c.2)(map n
  256. _))]λ[n:read:rem #._])
  257.  
  258. data T=A[Char]|B[Char]T|C T T
  259. (!)=(++)
  260. s(A a)=a
  261. s(B a b)="(λ "!a!". "!s b!")"
  262. s(C a b)='(':s a!" "!s b!")"
  263. e d(A a)=maybe(A a)id(lookup a d)
  264. e d(B a b)=B a.e d$b
  265. e d(C a b)=f d(e d a)(e d b)
  266. f d(B x s)q=e((x,q):d)s
  267. f d p q=C p q
  268. d=tail
  269. p('(':'λ':s)=let(A c,t)=p(d s);(b,u)=p(d.d$t);in(B c b,d u)
  270. p('(':s)=let(a,t)=p s;(b,u)=p(d t)in(C a b,d u)
  271. p(c:s)|elem c" .)"=(A "",c:s)|1<2=let((A w),t)=p s in(A(c:w),t)
  272. r=s.e[].fst.p
  273. main=do l<-getLine;putStrLn$r l
  274.  
  275. data Expression = Literal String
  276. | Lambda String Expression
  277. | Apply Expression Expression
  278. deriving Show
  279.  
  280. type Context = [(String, Expression)]
  281.  
  282. show' :: Expression -> String
  283. show' (Literal a) = a
  284. show' (Lambda x e) = "(λ " ++ x ++ ". " ++ show' e ++ ")"
  285. show' (Apply e1 e2) = "(" ++ show' e1 ++ " " ++ show' e2 ++ ")"
  286.  
  287. eval :: Context -> Expression -> Expression
  288. eval context e@(Literal a) = maybe e id (lookup a context)
  289. eval context (Lambda x e) = Lambda x (eval context e)
  290. eval context (Apply e1 e2) = apply context (eval context e1) (eval context e2)
  291.  
  292. apply :: Context -> Expression -> Expression -> Expression
  293. apply context (Lambda x e) e2 = eval ((x, e2):context) e
  294. apply context e1 e2 = Apply e1 e2
  295.  
  296. parse :: String -> (Expression, String)
  297. parse ('(':'λ':s) = let
  298. (Literal a, s') = parse (tail s)
  299. (e, s'') = parse (drop 2 s')
  300. in (Lambda a e, tail s'')
  301.  
  302. parse ('(':s) = let
  303. (e1, s') = parse s
  304. (e2, s'') = parse (tail s')
  305. in (Apply e1 e2, tail s'')
  306.  
  307. parse (c:s) | elem c " .)" = (Literal "", c:s)
  308. | otherwise = let ((Literal a), s') = parse s
  309. in (Literal (c:a), s')
  310.  
  311. run :: String -> String
  312. run = show' . eval [] . fst . parse
  313. main = do
  314. line <- getLine
  315. putStrLn$ run line
  316.  
  317. #define F for
  318. #define R return
  319. #define E if(i>=M||j>=M)R-1;
  320. enum{O='(',C,M=3999};signed char Q[M],D[M],t[M],Z,v,*o=Q,*d=D,*T;int m,n,s,c,w,x,y;K(i,j,k){!Z&&(Z=t[O]=1)+(t[C]=-1);E;if(!o[i]){d[j]=0;R 0;}if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!='\'){d[j++]=o[i++];R K(i,j,i);}F(i+=2,y=w=0;i<M&&o[i]&&c;++i)c+=t[o[i]],!w&&c==1?w=i:0,!y&&o[i]=='.'?y=i+2:0;E;if(c){F(;d[j++]=o[i++];)E;R 0;}F(c=y;c<w;++c)if(o[c]=='\')F(n=0,m=w+2;m<i;++m){if(o[m]==o[c+2]){F(x=0;o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[c+2+x];++x);if(o[c+2+x]!='.'||isalpha(o[m+x]))continue;if(v>'Z')R-1;F(n=c+2;n<w;++n)if(o[n]==o[m]){F(x=0; o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[n+x];++x);if(o[m+x]=='.'&&!isalpha(o[n+x]))F(;--x>=0;) o[n+x]=v;}++v;}}F(c=y;c<w&&j<M;++c){F(x=0;o[c+x]&&o[c+x]==o[k+4+x]&&isalpha(o[c+x]); ++x);if(o[k+4+x]=='.'&&!isalpha(o[c+x])){F(m=w+2;m<i-1&&j<M;++m)d[j++]=o[m];c+=x-1;}else d[j++]=o[c];}E;Z=2;R K(i,j,i);}char*L(char*a){F(s=n=0;n<M&&(o[n]=a[n]);++n);if(n==M)R 0;v='A';F(;++s<M;){Z=0;n=K(0,0,0);if(Z==2&&n!=-1)T=d,d=o,o=T;else break;}R n==-1||s>=M?0:d;}
  321.  
  322. #define P printf
  323. main()
  324. {char *r[]={ "((\ abc. (\ b. (abc (abc (abc b))))) (\ cc. (\ dd. (cc (cc dd)))))",
  325. "((\ fa. (\ abc. (fa abc))) (\ yy. (\ abc. yy)))",
  326. "((\ x. x) z)",
  327. "((\ x. x) (\ y. (\ z. z)))",
  328. "(\ x. ((\ y. y) x))",
  329. "((\ x. (\ y. x)) (\ a. a))",
  330. "(((\ x. (\ y. x)) (\ a. a)) (\ b. b))",
  331. "((\ x. (\ y. y)) (\ a. a))",
  332. "(((\ x. (\ y. y)) (\ a. a)) (\ b. b))",
  333. "((\ x. (x x)) (\ x. (x x)))",
  334. "(((\ x. (\ y. x)) (\ a. a)) ((\ x. (x x)) (\ x. (x x))))",
  335. 0}, *p;
  336. int w;
  337.  
  338. for(w=0; r[w] ;++w)
  339. {p=L(r[w]);
  340. P("o=%s d=%sn", r[w], p==0?"Error ":p);
  341. }
  342. R 0;
  343. }
  344.  
  345. /*1.039*/
  346.  
  347. (function f(a){return a[0]?(a=a.map(f),1===a[0][0]?f(function d(b,a,e,c){return b[0]?1===b[0]?[1,d(b[1],a,e,c+1)]:2===b[0]?b[1]===c-1?d(a,0,c-1,0)||b:c-1<b[1]?[2,b[1]+e]:b:[d(b[0],a,e,c),d(b[1],a,e,c)]:b}(a[0],a[1],-1,0)[1]):a):a})
  348.  
  349. zero = [1,[1,[2,0]]]; // λλ0
  350. succ = [1,[1,[1,[[2,1],[[[2,2],[2,1]],[2,0]]]]]]; // λλλ(1 ((2 1) 0))
  351. console.log(JSON.stringify(reduce([succ,[succ,[succ,zero]]]))); // 0+1+1+1
  352. // Output: [1,[1,[[2,1],[[2,1],[[2,1],[2,0]]]]]] = λλ(1(1(1 0))) = number 3
  353.  
  354. #define R return
  355. #define E if(i>=M||j>=M)R-1;
  356. #define H d[j++]
  357. enum{O=40,C,M=3999};signed char Q[M],D[M],t[M],Z,*o=Q,*d=D,*T;int m,n,s,c,w;K(i,j,k){!Z&&(Z=t[O]=1)+(t[C]=-1);E;if(!o[i]){H=0;R 0;}if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!=92){H=o[i++];R K(i,j,i);}for(i+=2,w=0;i<M&&o[i]&&c;++i)c+=t[o[i]],!w&&c==1?w=i:0;E;if(c){for(;H=o[i++];)E;R 0;}for(c=k+7,n=j;c<w&&j<M;++c)if(o[c]==o[k+4]){if(o[c+1]==46){d[n++]=o[k++];R K(k,n,k);}for(m=w+2;m<i-1&&j<M;)H=o[m++];}else H=o[c];E;Z=2;R K(i,j,i);}char*L(char*a){for(s=n=0;n<M&&(o[n]=a[n]);++n);if(n==M)R 0;for(;++s<M;){Z=0;if((n=K(0,0,0))!=-1&&Z==2)T=d,d=o,o=T;else break;}R n==-1||s>=M?0:d;}
  358.  
  359. #define P printf
  360.  
  361. main()
  362. {char *r[]={ "((\ x. x) z)",
  363. "((\ x. x) (\ y. (\ z. z)))",
  364. "(\ x. ((\ y. y) x))",
  365. "((\ x. (\ y. x)) (\ a. a))",
  366. "(((\ x. (\ y. x)) (\ a. a)) (\ b. b))",
  367. "((\ x. (\ y. y)) (\ a. a))",
  368. "(((\ x. (\ y. y)) (\ a. a)) (\ b. b))",
  369. "((\ x. (x x)) (\ x. (x x)))",
  370. "(((\ x. (\ y. x)) (\ a. a)) ((\ x. (x x)) (\ x. (x x))))",
  371. "((\ a. (\ b. (a (a (a b))))) (\ c. (\ d. (c (c d)))))",
  372. "((\ f. (\ x. (f x))) (\ y. (\ x. y)))",
  373. 0}, *y;
  374. int w;
  375.  
  376. for(w=0; r[w] ;++w)
  377. {y=L(r[w]);
  378. P("o=%s d=%sn", r[w], y==0?"Error ":y);
  379. }
  380. R 0;
  381. }
  382.  
  383. /*
  384. 637
  385. o=(( x. x) z) d=z
  386. o=(( x. x) ( y. ( z. z))) d=( y. ( z. z))
  387. o=( x. (( y. y) x)) d=( x. x)
  388. o=(( x. ( y. x)) ( a. a)) d=( y. ( a. a))
  389. o=((( x. ( y. x)) ( a. a)) ( b. b)) d=( a. a)
  390. o=(( x. ( y. y)) ( a. a)) d=( y. y)
  391. o=((( x. ( y. y)) ( a. a)) ( b. b)) d=( b. b)
  392. o=(( x. (x x)) ( x. (x x))) d=Error
  393. o=((( x. ( y. x)) ( a. a)) (( x. (x x)) ( x. (x x)))) d=( a. a)
  394. o=(( a. ( b. (a (a (a b))))) ( c. ( d. (c (c d))))) d=( b. ( d. (b (b (b (b (b (b (b (b d))))))))))
  395. o=(( f. ( x. (f x))) ( y. ( x. y))) d=( x. ( x. x))
  396. */
  397.  
  398. #define R return
  399. #define E if(i>=M||j>=M)R-1;
  400. #define H d[j++]
  401. enum{O=40,C,M=3999}; // assume ascii
  402. signed char Q[M],D[M],t[M],Z,*o=Q,*d=D,*T;
  403. int m,n,s,c,w;
  404.  
  405. K(i,j,k)
  406. {!Z&&(Z=t[O]=1)+(t[C]=-1); //inizializza tabelle
  407.  
  408. E;if(!o[i]){H=0;R 0;}
  409. if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!=92)
  410. {H=o[i++]; R K(i,j,i);}
  411. for(i+=2,w=0;i<M&&o[i]&&c;++i)
  412. c+=t[o[i]],!w&&c==1?w=i:0;
  413. E;
  414. if(c){for(;H=o[i++];)E;R 0;}
  415. // 01234567w12 i
  416. // ((/ x. x) z)
  417. // x w z
  418. // o[k+4]..o[k+5]; o[k+7]..o[w]; o[w+2]..o[i-1]
  419.  
  420. // sostituzione
  421. // sostituisce a x z in w e lo scrive in d
  422. for(c=k+7,n=j;c<w&&j<M;++c)
  423. if(o[c]==o[k+4])
  424. {if(o[c+1]==46) // non puo' sostituire una variabile dove c'e' lambda
  425. {d[n++]=o[k++]; R K(k,n,k);}
  426. for(m=w+2;m<i-1&&j<M;++m)
  427. H=o[m];
  428. }
  429. else H=o[c];
  430. E;
  431. Z=2;
  432. R K(i,j,i);
  433. }
  434.  
  435. char*L(char*a)
  436. {for(s=n=0;n<M&&(o[n]=a[n]);++n);
  437. if(n==M)R 0;
  438. for(;++s<M;)
  439. {Z=0;
  440. n=K(0,0,0);
  441. // if(Z==2)printf("n=%d>%sn", n, d);
  442. if(Z==2&&n!=-1)T=d,d=o,o=T;
  443. else break;
  444. }
  445. R n==-1||s>=M?0:d;
  446. }
Add Comment
Please, Sign In to add comment