# TokigunStudio Whitespace Implementation # explaination version (korean) # 참고: # - 이 코드에서는 내부적으로 공백, 탭, 개행문자를 다음과 같은 숫자로 해석한다. # 공백 = 0, 탭 = 1, 개행문자 = 2 # - 많이 쓰이는 내부 함수/변수들: # N: 숫자 인수 반환 / L: 레이블 id 반환 / M: 레이블을 문자열로 반환 # r: 스트림에서 한 문자를 읽어 숫자(0,1,2)로 반환 / j: ''.join -_-; / x: exit # U: 스택에서 pop (빈 스택이라면 0) / u: 스택에 숫자를 push # W: 스트림에서 현재 위치에 주어진 인자가 나타나면 스트림 포인터를 인자 뒤로 옮기고 참 반환 # 안 나타나면 스트림 포인터를 냅두고 None 반환 -_-; # N: StringIO 형태의 스트림에서 whitespace 숫자 인수를 읽어서 반환한다. def N(): # 초기화 p=[0] # 2가 나올 때까지 p에 계속 덧붙인다. while p[-1]<2:p+=[r()] # 결과 반환 return ( ((p[1]-1)%3-1)* # p[1](첫 문자)가 0이면 양수, 1이면 음수, 2이면 숫자 끝난 거니까 0 reduce(lambda x,y:x*2+y,p[2:-1],0)) # p[2]부터 p[-2]까지(p[-1]==2)는 이진수로 그대로 변환하면 됨. # 공백이 0이고 탭이 1이므로 있는 그대로 숫자를 변환할 수 있다. # L: StringIO 형태의 스트림에서 whitespace 레이블을 읽어서 tuple 형태로 반환한다. def L(): # 초기화 p=(0,) # 2가 나올 때까지 p에 계속 덧붙인다. while p[-1]<2:p=p+(r(),) # 결과 반환 (p[0]==0, p[-1]==2이므로 둘은 뺀다) return p[1:-1] # M: L에서 반환하는 레이블 tuple을 "인간이 읽을 만한 형태의" 문자열로 변환한다. # [규칙] 길이가 8의 배수면 그대로 문자열로 취급하고 아니면 그냥 label_17FF 같이 16진수 덧붙임 def M(l): # 일단 l에 해당하는 2진수를 구한다 v=reduce(lambda a,b:a*2+b,l,0L) # 길이가 8의 배수거나 숫자가 0이라면 (숫자가 0일 경우 빈 문자열이 나와서...) if 7&len(l)or v==0: # 레이블 값을 반환한다. # len(l)&3을 쓰는 이유는 같은 v 값을 갖지만 길이가 다른 레이블이 있을 수 있기 때문에... # (예를 들면 101012와 00101012라는 레이블은 같은 v 값 19를 갖는다) return'label%d_%s'%(len(l)&3,hex(v)[2:-1]) # 아니면 문자열로 출력 else: return j([ `chr(v>>k&255)`[1:-1] # (v>>k)&255는 뒤에서부터 k번 문자의 아스키 코드에 해당한다. for k in range(len(l)-8,-1,-8) # k = len(l)-8, len(l)-16, ..., 16, 8, 0 ]) # 모듈 들여 오기 from sys import* from StringIO import* # 사용하는 문자열들 초기화 (X: 명령이름, Y: 해당하는 문자들, Z: parameter 종류) # parameter 종류 -- 0: 인자 없음, 1: 숫자 인자, 2: 레이블 인자 X='push,dup,copy,swap,pop,slide,add,sub,mul,div,mod,store,retrieve,call,jmp,jz,jn,ret,halt,putchar,putint,getchar,getint'.split(',') Y='00,020,010,021,022,012,1000,1001,1002,1010,1011,110,111,201,202,210,211,212,222,1200,1201,1210,1211'.split(',') Z='10100000000002222000000' # v에 현재 파일 이름(argv[0]) 뺀 나머지 인자들을 넣음 v=argv[1:] # 실행할 동작의 종류 결정 (코드 실행 0, 컴파일 1, 디컴파일 2, 도움말 3) n,=(len(v)and # 인자가 하나 이상 있으면 [v[0][0]=='-' # 첫 인자가 -로 시작하면 and{'-c':1,'-d':2,'--':0}.get(v.pop(0),3) # -c/-d/--만 처리하고 나머지는 도움말로 돌림 # 그러면서 첫 인자를 빼 내기 때문에 결국 첫 인자는 항상 입력 파일이 된다. or 0] # 첫 인자가 -로 시작하지 않으면 코드 실행 모드 or[3]) # 인자가 안 들어 오면 도움말 출력 # 많이 쓰는 함수를 짧게 줄임 j=''.join x=exit # n>2(즉, n==3; 도움말)이거나, 나머지 mode인데도 인자 갯수가 안 맞으면 도움말 출력 if n>2 or[1,2,2][n]!=len(v): # 메시지 출력 (v에서는 프로그램 이름이 사라졌으나 argv엔 남아 있으므로 그걸 그대로 사용) print'TokigunStudio Whitespace 0.3 Implementation\n'\ 'by Kang Seonghoon \n\n'\ 'Usage: python %s \n'\ ' or: python %s [-c|-d] \n\n'\ 'no arg\texecute whitespace code.\n'\ '-c\tcompile whitespace assembly code.\n'\ '-d\tdecompile whitespace assembly code.\n'%(argv[0],argv[0]) x(0) # 그리고 종료 try: # s: 입력 파일 내용 s=file(v[0],'r').read() # f: (실행 모드가 아니면) 출력 파일 객체 f=n and file(v[1],'w') # v는 n==1,2일 때 메시지 출력하려 쓰는 리스트인데 그냥 넣으면 에러 나므로 튜플로 변환 v=tuple(v) except:print'cannot open file.';x(1) # 에러 나면 메시지 출력하고 죽음 # n==1(컴파일) 모드이면... if n==1: # 메시지 출력 print'compile %s to %s...'%v, # N: 숫자를 받아서 거기에 해당하는 whitespace 숫자 형태를 반환 N=lambda n:( n and # 숫자가 0이 아니라면: ('\t '[n>0]+ # 부호를 나타내는 첫 문자 N(abs(n)/2)[1:-1]+ # 여기서 whitespace 문자의 구성은 다음과 같음. # (부호 문자) (나머지 자리들) (이진수 마지막 자리) (개행문자) # 여기서 나머지 자리들(즉, abs(n/2))의 whitespace 표현은 # (부호 문자) (나머지 자리들) (개행문자) # 에 해당하므로 앞뒤 문자만 떼어 주면 그대로 사용할 수 있다. ' \t'[n%2]+ # 현재 숫자의 이진수 마지막 자리를 나타내는 문자 '\n') # 그리고 마지막 개행 문자 or'\n') # 숫자가 0일 경우 위 코드가 오동작하므로 그냥 개행문자 반환 # L: 문자열을 받아서 거기에 해당하는 whitespace 레이블 형태를 반환 L=lambda l:( j([ j([ ' \t'[ord(v)>>k&1] # 이진수 자리에 맞춰서 문자 채움 for k in range(7,-1,-1)]) # 자리값이 가장 큰 자리부터... for v in l])+ # l 안의 모든 문자 v에 대해서 반복 '\n') # 마지막 문자는 개행 문자 # 입력받은 파일을 줄로 나눠서 처리 for l in s.splitlines(): l=((';'in l # 줄 안에 ; 문자가 있으면 and l[:l.find(';')] # 그 문자 다음부터 모두 삭제함 (; 뒤는 모두 주석) or l) # 아니면 냅둔다. .split()) # 주석을 지운 후 공백 단위의 token으로 나눈다. (len(l)and':'==l[0][-1]and # l이 빈 줄이 아니고 첫 token이 :로 끝나면 (레이블) f.write('\n '+ # 레이블 명령을 쓰고 L(l.pop(0)[:-1]))) # 레이블 부분만 가져 와서(이 때 첫 token은 pop된다) # 맨 마지막 문자를 버리고 L 함수에 넘겨서 whitespace 표현으로 바꿔 출력 # 레이블을 뺀 token이 아직도 남아 있다면; if len(l): # 첫 token이 명령어이므로 해당하는 명령의 번호를 구한다. p=X.index(l[0].lower()) (p+1 and # p!=-1(명령어가 존재할 경우)이고 len(l)>(Z[p]>'0')and # 인자가 있을 경우 token 수가 2개 이상, 없으면 1개 이상이어야 함 # (인자가 있으면 int(Z[p]>'0')==1, 없으면 0임) f.write( j([' \t\n'[int(k)]for k in Y[p]])+ # 0/1/2로 구성된 명령어를 공백 문자로 바꿔서 출력 (Z[p]>'0'and # 인자가 있을 경우 (0,lambda a:N(int(a)),L) # 1: 숫자 인자, 2: 레이블 인자. 해당하는 함수를 테이블로 만듬 [int(Z[p])] # 테이블에서 필요한 함수를 뽑아 와서 (l[1]) # 호출 결과를 출력 or''))) # 아니면 더 이상 출력할 게 없으니 빈 문자열로... # 다 끝났으면 파일 핸들 닫고 메시지 출력 후 종료 f.close() print'done.' x(0) # 이 경우는 n==2(디컴파일) # 디컴파일과 실행은 코드 파싱 부분이 같기 때문에 일단 종료하지 않는다. elif n: # 메시지 출력 print'decompile %s to %s...'%v, # 스트림을 연다. s=StringIO( # 위치 관리 같은 걸 하기 귀찮아서 그냥 StringIO로... j([ {32:'0',9:'1',10:'2'}.get(ord(c),'') # 공백 문자만 따로 0/1/2로 저장하고 나머지는 무시 for c in s]) # 입력 파일 안의 모든 문자에 대해서 이 짓을 반복 ) # r: 현재 위치에서 문자를 하나 읽어서 그걸 숫자로 변환. # 예를 들어서 r()==1이면 현재 위치의 문자가 탭 문자라는 걸 의미한다. r=lambda:int(s.read(1)) # W: 스트림에서 문자열을 읽어서 주어진 문자열과 같다면 참을 반환하고 # 아니면 원래 위치(W가 사용될 때는 항상 초기 위치를 i에 저장한다)로 돌아 가고 None을 반환한다 W=lambda h:h==s.read(len(h))or s.seek(i,0) # c: 파싱 결과. (명령 번호, 인자) 튜플들의 리스트 c=[] # p: 레이블 이름(실제로는 튜플)이 키, 그게 가리키는 실제 c에서의 위치를 값으로 가지는 사전 p={} # 이 과정이 끝날 때는 리스트 마지막 내용이 None이므로 그걸 체크한다. while[None]!=c[-1:]: # 일단 현재 위치 저장 (W 함수에서 사용) i=s.tell() # 200('\n\40\40')으로 시작할 경우는 레이블이므로 따로 처리 # (실제로 레이블 명령은 X/Y/Z에 따로 들어 있지 않음) if W('200'): l=L() # 레이블을 읽는다 p[l]=len(c) # 레이블 사전에다가 현재 위치를 저장한다. n and f.write(M(l)+':\n') # 디컴파일 모드일 경우 레이블을 문자열로 바꿔서 출력한다. else: # 아니면 X/Y/Z에 따라서 처리한다. # 실제 명령과 비교해서 명령어 번호와 그 인자를 확인한다. # v가 None가 될 경우는 다음과 같은 경우이다: (모든 명령에 대해서 W 함수의 결과값이 None이 됨) # - 현재 위치에 있는 명령이 존재하지 않는 명령일 경우 # - 파일의 끝에 도달했을 경우 v=reduce( lambda a,b: # a: 예전 결과, b: 테스트할 명령어 번호 a or # 이미 찾았을 경우(못 찾으면 0 또는 None) 그냥 그대로 반환 W(Y[b]) and # 아직 못 찾았는데 지금 확인하는 명령이 나타났다면 # (아닐 경우에는 None and ...가 되어서 None이 반환됨) (b, # 명령어 번호를 넣고 (int,N,L) # 명령어에 따라 붙는 인자들을 처리할 함수들의 테이블 [int(Z[b])] # 명령어에 해당하는 인자 읽는 함수를 가져 와서 () # 호출 (인자가 없는 명령어들은 int() == 0이라는 걸 악용했음 :) ), range(23), # 이 짓거리를 23개의 모든 명령에 대해서 반복 0) # 처음에는 거짓으로 인식할 수 있는 값이 있으면 되니까... 간단하게 0으로; # 그 결과를 코드 리스트에 추가한다. (따라서 파싱이 끝날 때는 None이 항상 끝에 들어 있다) c+=[v] # 출력 (n and v and # 디컴파일 모드이면서 이 명령을 찾았다면 f.write( ' '+X[v[0]]+ # 명령을 출력하고 (indent는 레이블과 구별하려고 넣어 줬음) (Z[v[0]]>'0'and # 명령에 따라 붙는 인자가 있다면 인자도 출력 (' '+ # 일단 명령과 인자를 구별해야 하니 공백 출력 (0,str,M) # 사용할 함수 테이블 (숫자는 그냥 문자열로, 레이블은 튜플이므로 별도 처리) [int(Z[v[0]])] # 인자 종류에 맞는 함수를 가져 와서 (v[1])) # 호출하고 출력 or'')+ # 아니면 상관 없으니 빈 문자열 출력 '\n')) # 마지막 개행 문자 # 디컴파일 모드일 경우 이미 앞에서 출력이 끝났으므로 종료 if n: # 파일 핸들 닫고, 메시지 출력하고 종료 f.close() print'done.' x(0) # s: 스택 대용 리스트 (뒷쪽에 있을 수록 스택 꼭대기에 가까움) s=[] # h: 힙 영역 h={} # q: call/ret 명령이 사용하는 함수 호출 스택-_-; 이 역시 뒷쪽일 수록 꼭대기 q=[] # u: 스택 push 함수 u=s.append # U: 스택 pop 함수 (스택이 비어 있으면 0 반환) U=lambda:len(s)and s.pop() # i: 현재 실행중인 c 위에서의 위치 (instruction pointer), k: 이전 명령 번호 i=k=0 # 코드의 마지막은 None이므로 제거해 준다. c.pop() # 명령 포인터가 코드 끝에 오지 않고, 이전 명령(k)이 exit(18)가 아니라면... while i0): # copy N -- 스택의 N번째(N=1이라면 꼭대기) 숫자를 복사해서 스택에 넣는다. u(s[-v]) # N=1일 때가 꼭대기(-1)이고 N=2는 그 아래(-2)이고... 아무튼 가져 와서 push elif k==3: # swap -- 스택 꼭대기의 두 숫자를 교환한다. n=U();m=U() # 두 개를 순서대로 pop해서 u(n);u(m) # 거꾸로 push elif k==4: # pop -- 스택 꼭대기에 있는 숫자를 꺼내서 버린다. U() # 그냥 pop 해 주면 그 결과는 버려진다. elif k==5: # slide N -- 스택 꼭대기 바로 아래부터 N개의 숫자를 버린다. s[-v-1:-1]=[] # 스택 꼭대기 바로 아래(-2)부터 N개(마지막이 -N-1)에 해당하는 영역을 # 빈 리스트로 채우면 사라진다. elif k==6: # add -- 스택 꼭대기에 있는 두 숫자를 더한다. u(U()+U()) elif k==7: # sub -- 스택 꼭대기에 있는 두 숫자를 뺀다. # a, b 순서대로 pop했을 경우 b-a가 push된다. (다른 산술 연산도 동일) u(-U()+U()) # 파이썬의 연산자 처리 순서가 왼쪽부터이므로 따로 처리하지 않고 이렇게 했음. elif k==8: # mul -- 스택 꼭대기에 있는 두 숫자를 곱한다. u(U()*U()) elif k==9: # div -- 스택 꼭대기에 있는 두 숫자를 나눈다. (순서는 sub와 마찬가지) n=U();u(U()//n) # 이 경우 오차가 발생할 수 있기 때문에 sub와 같은 방법을 쓸 수 없다. elif k==10: # mod -- 스택 꼭대기에 있는 두 숫자를 나눠서 나머지를 push한다. n=U();u(U()%n) # 이 경우는 아예 두 인자를 거꾸로 쓸 수가 없다; elif k==11: # store -- 두 개의 숫자 a,b를 순서대로 pop하고, 힙 영역의 b 위치에 a를 저장한다. n=U() # 넣을 값을 먼저 pop하고 h[U()]=n # 주소를 pop한 후 힙 영역(실제로는 사전)에 집어 넣는다. elif k==12: # retrieve -- 스택 꼭대기에 있는 주소를 꺼내서 힙 영역에서 그 주소에 있는 숫자를 push한다. u(h.get(U(),0)) # 사전에 없는(즉 store하지 않은) 값은 0으로 가정한다. elif k==13: # call -- 서브 루틴을 호출한다. q+=[i] # 돌아 올 위치를 스택에 넣고 (앞에서 i+=1을 했기 때문에 이 위치는 call 명령 다음이다) i=p[v] # 레이블이 가리키는 실제 코드 위치로 코드 포인터를 옮긴다. elif k==14: # jmp -- 무조건 레이블이 가리키는 위치로 이동한다. i=p[v] elif k==15 and U()==0: # jz -- 스택에서 숫자를 꺼내서 0이면 레이블이 가리키는 위치로 이동한다. # 여기서는 그냥 if 문에 조건을 다는 걸로 해결했다-_-; i=p[v] elif k==16 and U()<0: # jn -- 스택에서 숫자를 꺼내서 음수이면 레이블이 가리키는 위치로 이동한다. i=p[v] elif k==17 and len(q): # ret -- 서브 루틴을 끝내고 원래 위치로 돌아 온다. i=q.pop() # (위에서 체크했듯이, 호출 스택에 숫자가 있으면) 돌아 올 위치로 명령 포인터를 이동한다. # (halt) -- 프로그램을 종료한다. (위에서 처리함) elif k==19: # putchar -- 스택에서 숫자를 꺼내서 거기에 해당하는(ASCII 문자 번호) 문자를 출력한다. stdout.write(chr(U())) elif k==20: # putint -- 스택에서 숫자를 꺼내서 그대로 출력한다. stdout.write(str(U())) elif k==21: # getchar -- 문자를 입력받아서, 힙 영역에 스택 꼭대기가 가리키는 주소에 # 해당하는 숫자를 저장한다. h[U()]=ord(stdin.read(1)) elif k==22: # getint -- 숫자를 입력받아서... 그 다음은 getchar와 같음 -_-; v='' # 처음 문자열은 빈 문자열. while( '0'+ # (이걸 더하는 이유는 ''.isdigit()가 False이기 때문에 -_-;) v[v[0:1]=='-':] # v에서 부호(첫 문자가 -일 경우)를 뺀 부분 ).isdigit(): # 이 숫자로만 구성되어 있을 때까지 반복한다. v+=stdin.read(1) # 뭐 계속 읽어서 v에 추가하고 검사하고 추가하고 검사하고 함 -_- h[U()]=int(v[:-1]+'0')/10 # 마지막 문자는 숫자가 아니므로 제거하고 숫자로 변환해서 힙 영역에 넣는다. # '0'을 덧붙이는 이유는 아예 숫자가 안 입력되었을 경우 그냥 int 호출하면 에러 나기 때문. # (앞에 붙이면 부호가 있는 경우 처리가 안 되어서 결국 뒤에 붙였음 -_-;;;;) # 덤: # 실제로 만들 때는 위의 프로그램을 작성한 후 불필요한 공백을 없앤 다음 compress했다. # compress하는 과정은 간단하다: 먼저 어떤 형식으로 코드를 짤 건지 템플릿을 만들고, 거기에 맞춰서 압축한다. # 처음에 계획했던 코드는 이랬다. # from string import*;d=replace;exec d(d(d(...(d('string','from','to'),'from','to'),...) # 그러나 다 만들고도 공간이 남는 덕분에-_- 코드는 다음과 같이 변경되었다. # from string import*;d=replace;R=d(d(d(...(d('string','from','to'),'from','to'),...);exec'additional_code' # 이렇게 만들고 나서 수식으로 어떤 것들을 압축해야 코드를 줄일 수 있는 지 계산해 볼 수 있다. # 어떤 문자열 'text'에 어떤 keyword가 n개 들어 있다 치자. 이걸 한 문자 X로 줄일 수 있다면, # 'text' == d('compressed_text','X','keyword') # 와 같은 관계가 성립한다. 따라서 len(keyword)짜리 문자열이 모두 1 길이의 문자열로 대체된다. # 이 사실을 가지고 식을 세우면 (len(keyword)-1)*n-(10+len(keyword)) byte를 절약할 수 있다. # 코드 양이 꽤 많았기 때문에 (c처럼 freeform으로 짤 수 있는 것도 아니고-_-;) compressor, 즉 # 저런 조건을 만족하는 부분 문자열 중 가장 효율적인 것들을 순차적으로 선택해서 사용하게 했다. # 그렇게 하고 나서 코드를 배열한 후, 남는 공간은 추가적인 코드로 채웠다. 이 코드는 다음과 같다. # from sys import* # if['--source']==argv[1:2]:print'# TokigunStudio Whitespace Implementation\n\n'+R # else:exec R # 뭐 어려운 건 아니기 때문에 설명은 생략하기로 한다. :) # 아무튼 템플릿에 이런 내용들을 끼워 맞추고 앞에 (쓸데없는) docstring을 넣어서 indentation을 해결했다. # 몇 가지 방법을 생각해 봤지만 실제로 쓸 수 있는 방법은 이런 것 밖에 없더란다. -_-;;; # # 전체적으로는 파이썬에 있는 문자열 이어 붙이기 기능(즉, "ab" "cd" == "abcd")을 많이 사용했다. # 필요에 따라서 \나 +를 적절히 사용하기도 했으며, 중간에는 raw-string을 쓰기도 한다. -_-; # 외곽선을 ""로 처리한 것은 의도적인 것이라 생각하면 되겠다. # 공개 후 수도 없이 뜯어 고쳤지만 아직도 맘에 안 드는 부분은 코이다. # 코 부분을 좀 잘 드러나게 하고 싶은데 그게 잘 안 된다. -_-;;; 역시 난 미술에 소질 같은 건 없는 것 같다; # 아무튼... 참 재밌는 짓이었다. 손이 너무 많이 가서 죽는 줄 알았다. -_- # 이 코드를 보면서 여러 사람들이 즐거워 했으면 하는 마음이다. 누구나 그러지 않는가 ;)