메아리 저널

<lifthrasiir>

IRC의 좋은 점은 실시간 대화와 비실시간 대화를 섞을 수 있다는 거고

<lifthrasiir>

안 좋은 점은 사람들이 거기서 거기다... orz

<lifthrasiir>

크아앗ㅊㅁ열팟마팔엿ㅏ!!!

<d****>

lifthrasiir, 열팟 마팔엿!

<lifthrasiir>

어제 밤새도록 삽질하고 끝내 미팅까지 날리는 수모를 겪게 만든 삽질이

<lifthrasiir>

어처구니 없이 해결되었어!

<d*********>

''?

<k****>

미팅을 안하셨으니

<k****>

좋은거군요

<d*********>

ㅋㅋㅋㅋㅋ

<lifthrasiir>

k****, 아니죠 follow-up을 해야죠 -_-

<lifthrasiir>

뭐 저는 미팅에 부담을 가지는 사람은 아니지만 (연구실 한정)

<k****>

(가지는 사람)

<d*********>

(여자랑은.. )

<lifthrasiir>

회사에서의 미팅은 귀찮죠

<lifthrasiir>

...

<lifthrasiir>

어쨌든

<lifthrasiir>

AST node랑 runtime type이랑 섞이면서 굉장히 미친듯이 꼬이는 문제를

<lifthrasiir>

잡았습니다.

<k****>

ㅊㅋ

<lifthrasiir>

...AST node 어딘가에 runtime type으로 변환해 주는 게 있더군요

<d*********>

ㅋㅋㅋ

<lifthrasiir>

없는 줄 알았는데 disambiguation 과정에서 만들어 줌

<lifthrasiir>

이걸 내가 몰랐다니

<d*********>

열심히 찾으려고 했는데 원래 다 있는거죠.

<d*********>

-.-;;

<lifthrasiir>

꼭 그런 거는 아닌데

<lifthrasiir>

정말... 안 보이는 곳에 박혀 있어서

<d*********>

lifthrasiir: 원래 이상형은 정말 안보이는곳에 박혀 있는법이죠 (응?)

<lifthrasiir>

정확히 말하면 Type이 있고 (AST node) FType이 있는데 (runtime type)

<lifthrasiir>

평소에는 FType만 가지고 놀면 참 좋겠는데 generic type에 인자를 끼워 넣으려면 Type을 써야 함

<lifthrasiir>

근데 trait type 같은 건... Type을 제대로 만들어야 하잖아요?

<lifthrasiir>

예를 들어서 어떤 api(module의 개념) A에 있는 T라는 타입을 api B의 X[\...\]에서 쓸 경우

<d*********>

흠

<lifthrasiir>

근데 api A가 B에서는 안 보일 경우

<lifthrasiir>

api name을 다 갖다 집어 넣어야 하는데 이게 안 보임

<d*********>

-.-;;;;

<lifthrasiir>

아무리 뒤져 봐도 X[\...\]에 대응하는 declaration node에서 "X"를 반환하는 건 있는데 "B"를 반환하는 건 없음;

<lifthrasiir>

그래서 뭔가 더 없나 하고 AST node dump를 떠 봤는데

<lifthrasiir>

SelfType이라는 게 보이는 거에요 (기본적으로 이건 declaration에서 self라는 키워드의 타입을 결정하는...)

<lifthrasiir>

거기에 api name도 반환하는 게 있어서 옳다구나 하고 쓰려다가

<lifthrasiir>

잠시 위화감이 들어서 출력을 다시 읽어 보니 selfType이 반환하는 값 자체가 Type임

<lifthrasiir>

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

<lifthrasiir>

시발 나 뭐 한 거야

<d*********>

ㅋㅋ

IRC #langdev 채널에서:

<sanxiyn> GPL인 경우 무엇이 소스인가는
<sanxiyn> 꽤 명백해서
<sanxiyn> The "source code" for a work means the preferred form
          of the work for making modifications to it.
<sanxiyn> 니가 고칠 때 쓰는 게 소스임

<lifthrasiir>

아무도 안 보는 것 같으니 주절거려야지

<lifthrasiir>

그래서 이를테면 {3 -> 4, 4 -> 6, (7,9,11,13,…,37) -> 5} 같은 류의 set을 efficient하게 관리하려면

<lifthrasiir>

일단 self.map[나머지, modulo] 같은 걸 만들고

<lifthrasiir>

따라서 (3)은 map[0,1]에 들어 가고 (1,5,9)는 map[1,4]에 들어 가고

<lifthrasiir>

이제 map의 각 원소는 sorted set/map이 들어 가는데

<lifthrasiir>

예를 들어 (1,5,9)를 삽입하려면 binary search 해서 1보다 작거나 같은 가장 큰 key를 찾고

<lifthrasiir>

그 키의 bound를 확인하고

<lifthrasiir>

솔직히 sorted list 쓰긴 싫은데 적절한 자료구조가 파이썬에 없는 관계로 일단 대강 삽니다-_- O(n) 싫어

<lifthrasiir>

skip list나 balancing BST 구현 찾아 봤는데 있어도 GPL이고 코드가 너무 더러움

<lifthrasiir>

그래서 하여튼

<lifthrasiir>

sorted map의 key는 (start//modulo, end//modulo)고

<**>

대인간토끼노이드가 정보를 읊기 시작했다!

<**>

근데 무슨 소린지 모르겠다..

<lifthrasiir>

(end는 저장 전에 적절히 normalize되어야 하고 start는 inclusive end는 exclusive)

<lifthrasiir>

논문 관련해서 정리 중…

<**>

..ㄹ

<lifthrasiir>

만약 (A,B) interval이 이미 있는데 (A’,B’) interval을 추가해야 하고 그게 (A,B)에 완전히 포함되면 세 개로 잘라야 하며

<lifthrasiir>

-> (A,A’) (A’,B’) (B’,B)

<lifthrasiir>

아 짜증나…

<lifthrasiir>

-infinity와 infinity는 None으로 표시하고

<lifthrasiir>

그럼 updated set, possibly_updated set (합쳐서 updated map으로 할 수도 있는데 뭔가 꼬인다), used set, possibly_used set (마찬가지), values “dict” (이건 range를 쓸 수가 없으므로)

<lifthrasiir>

…라고 생각했는데 updated set은 다 map으로 합쳐야지 나중에 trace를 할 수 있구나

<lifthrasiir>

뭐 좋아 그러면 하나의 monolithic map을 써도 되겠지

<lifthrasiir>

namedtuple로 updated? possibly_updated? last_updated_by? used? possibly_used? last_used_by? 뭐 이렇게 하면 되려나

<lifthrasiir>

그럼 analyzer는 한 노드씩 순서대로 훑어가며

<lifthrasiir>

만약 이 노드가 해당 memory cell이나 memory range를 참조하면 — used(및 필요하다면 certainly_used)를 세팅하고

<lifthrasiir>

변경하면 used는 다 날리고 updated(및 필요하다면 certainly_updatd)를 세팅하고

<lifthrasiir>

안 좋구나…

<lifthrasiir>

아니 그보다 certainness가 필요한가

<lifthrasiir>

업데이트 되었다면 업데이트 된거지 무슨 certain한 게 필요한가여 우적우적

<lifthrasiir>

이라고 하면 array analysis할 때가 좀 불안한데

<lifthrasiir>

자 생각해 봅시다 그래서 array analysis를 하게 되면 뭐가 문제인가요

<lifthrasiir>

실제 예제를 quote하면

<lifthrasiir>

{13}-=1, {16}+=1, {17}-=1, {18}+=1, While[{17}!=0; {18}-=1, @1], SeekMemory[{18+k}!=0]

<lifthrasiir>

이런 코드가 있다면

<lifthrasiir>

While을 실행하는 순간 memory set에는 {18:}-=1이라는 정보가 들어 가야 하는데 말이죠

<lifthrasiir>

-=1이 되었는지 안 되었는지 내가 어떻게 알아 걍 쓰는 거지

<lifthrasiir>

그러니 {18:}.updated = true로 설정하는데

<lifthrasiir>

문제는 이 다음이니 While문이 끝나고 나서 memory pointer 위치는 불분명하고

<lifthrasiir>

(원래보다 “뒤”로 갔음만 알 수 있음)

<lifthrasiir>

만약 While[{17}!=0; {18}-=1, @3] 처럼 stride가 1이 아니라면 +3k만큼 이동했으리라고 짐작은 가능하겠지만 하튼

<lifthrasiir>

만약 앞의 while에서 +3k만큼 이동했는데 그 뒤에서 +2k씩 오가면서 다른 변경을 행하고 있으면

<lifthrasiir>

(3p+2q)에 대응하는 모든 숫자가 변경의 대상이 될 수 있는데 실질적으로는 이건 +k’와 똑같으니

<lifthrasiir>

처음에 {18::3}이라고 생각하고 있던 건 사실 {18::1}로 변경되고 (i.e. gcd(3,2))

<lifthrasiir>

이 뒤의 코드는 미궁으로 빠지… 아 시발 이러면 SeekMemory의 존재의 미가 없잖아

<lifthrasiir>

조금 더 그럴듯한 예제를 들어 보자

<lifthrasiir>

{12}=0, While[{13}!=0; {13}-=1, SeekMemory[{11-k}!=0], {8}+=1, SeekMemory[{12+k}!=0]]

<lifthrasiir>

그럼 처음에는 {12}가 0으로 설정되고

<lifthrasiir>

While 문 안에서 {13}이 변경되는데

<lifthrasiir>

만약 memory state의 values 안에서 {13}을 참조하는 다른 변수가 있으면

<lifthrasiir>

{13} = old {13} - 1이니까 old {13} = {13} + 1로 처리해서 withmemory로 모두 갈아 엎고 (i.e. values와 함께 values_ref 같은 reference set도 저장해야 한다)

<lifthrasiir>

현재 offset이 @p라고 치자고요

<lifthrasiir>

그럼 SeekMemory 첫번째 거 돌고 나면 @p-k 위치가 될 것이고

<lifthrasiir>

그 상태에서 {11}은 당연히 0인데

<lifthrasiir>

…어라 이거 반대 아닌가

<lifthrasiir>

아시발 답이 안 나와여

<lifthrasiir>

이와 별개로 condition propagation 하려면 cond에다가도 withmemory를 붙여야 하는구나

<lifthrasiir>

{3}+4!=0 normalizes into {3}!=-4

<lifthrasiir>

{3}*4!=7 normalizes into Always (당연히…)

<lifthrasiir>

{3}//9==6 normalizes into 54<={3}<63…아 잠시만

<lifthrasiir>

…condition propagation을 먼저 손댈까

<lifthrasiir>

이제 뭐하자는 건지 모르겠군

<lifthrasiir>

**: 아직도 보시나요 (?)

<**>

‘ㅅ’;

<**>

방금 다시 봤습니당

<lifthrasiir>

아 시발 이 코드는 왜 마이너스가 먼저고 플러스가 뒤냐…

<lifthrasiir>

악 에러나는 코드…가 아니잖아.

<lifthrasiir>

다른 코드를 들어 보면

<lifthrasiir>

{152}-=1, While[{152}!=0; {152}-=1, {154}+=1, SeekMemory[{154+k}!=0], {154}=2, SeekMemory[{154-k}!=0], @1], {154}+=1

<lifthrasiir>

인데 중간에 들어 있는 SeekMemory 두 개는 사실 굉장히 많이 쓰이는 idiom이란 말이여.

<lifthrasiir>

그러니까 array header에 포인터가 있을 때 저 멀리 가서 값을 고치고 다시 돌아 오는 코드인데

<lifthrasiir>

이게 돌아오는 걸 어떻게 증명할 것인가?

<lifthrasiir>

생각해 봅시다. 편의상 {153}에 0이 들어 있다는 게 “알려져” 있다고 해 보면,

<lifthrasiir>

SeekMemory가 한바탕 휩쓸고 지나간 뒤 포인터는 @p+k가 되고

<lifthrasiir>

이 시점에서 “상대적”인 메모리 상태는 {154-k}==0을 가리켜야 하는데

<lifthrasiir>

과연 이걸 일반적인 pass가 처리할 수 있는가?

<lifthrasiir>

-k 값을 애초에 알 수 없으니 어디서 offset을 알 것인지가 애매해지는데

<lifthrasiir>

그럼 이렇게 생각해 보자: memory state는 항상 global하다고 가정하고, pointer 값을 in terms of SeekMemory로 지정한다.

<lifthrasiir>

그러니까 SeekMemory[{154+k}!=0]은 사실은 SeekMemory[{154+k_42}!=0]이고 어쩌구

<lifthrasiir>

그러면 현재 위치는 @k_42이고 k_42 is known to be >= 0.

<lifthrasiir>

({154}가 처음에 -1이었으면 0일 수도 있지 뭐)

<lifthrasiir>

아 시발 이러면 레퍼런스가 꼬이지

<lifthrasiir>

뭐 일단 그렇다고 치고 (“LoopCountOf(…)” 함수 같은 거라고 가정해 보세)

<lifthrasiir>

아… 이것도 뭔가 아닌 것 같아

<lifthrasiir>

요컨대 definitively 현재 위치의 “범위”를 알 수 있어야 하는데

<lifthrasiir>

저 경우에는 >=0이라는 정보 밖에 없고 (아 물론 이것도 쓸 수 있긴 함…)

<lifthrasiir>

만약 {154:208:1} != 0이고 {208} = 0이라는 게 state에 들어 있었다면

<lifthrasiir>

현재 위치의 범위는 >=0이고 <54일 것이니 ({p+154}==0이어야 하므로)

<lifthrasiir>

그럼 이걸 가지고 현재 위치를 어느 정도까지 추적할 수 있느냐가 관건인데

<lifthrasiir>

아까 전에 썼던 코드로 돌아 가면:

<lifthrasiir>

{12}=0, While[{13}!=0; {13}-=1, SeekMemory[{11-k}!=0], {8}+=1, SeekMemory[{12+k}!=0]]

<lifthrasiir>

그럼 첫번째 SeekMemory의 결과로 p <= 0이며

<lifthrasiir>

우리는 {12}=0인 건 알고 있죠

<lifthrasiir>

따라서 처음 SeekMemory[{11-k}!=0]이 하는 짓은: {11::-1}을 used로 마크하고, 현재 위치의 범위를 (-inf,0]으로 재조정

<lifthrasiir>

그 다음 {8}+=1이 하는 짓은: 현재 위치를 볼 때 {8}의 실제 위치는 {8::-1}이겠지 뭐

<lifthrasiir>

그러니까 {8::-1}을 updated로 마크하고

<lifthrasiir>

마지막 SeekMemory[{12+k}!=0]은 앞의 정보에 기반해서 현재 위치를 재조정하려고 하는데

<lifthrasiir>

(-inf,0] + {12} == (-inf,12]니깐 {12::-1}를 used로 마크하고 현재 위치는 (-inf,0]이 됨

<lifthrasiir>

(왜냐하면 {12}는 확실히 0이니까 p가 0이면 무조건 멈춰야 하니깐)

<lifthrasiir>

자 그러면 여기에 “{11:p:-1}은 모조리 0이 아니다”라는 조건을 어떻게 넣을까요

<lifthrasiir>

시발 peephole optimizer라고 넣어야 해?

<*****>

peehole optimizer

<lifthrasiir>

違います。

<lifthrasiir>

“아닌 값”을 위한 set이 따로 있어야 하나

<lifthrasiir>

메모리 졸라 많이도 쳐 먹겠군

<lifthrasiir>

그럼… 결론이 난 건가

<lifthrasiir>

만약 메모리 오프셋이 확실히 결정 안 되는 상황에 빠지면 그 때는 방법 없습니다 local memory state를 써야죠

<lifthrasiir>

일단 루프(정확히는 complex node)에 처리가 시작될 때 처리 전의 memory state를 저장하고

<lifthrasiir>

작업하던 중 p가 결정 안 되는 상황이 되면 i) 지금까지 처리하던 것은 다 버려야 하고(…in-place editing이 안 되겠네 ㅅㅂ)

<lifthrasiir>

ii) local memory state 쓰는 방법으로 재처리

<lifthrasiir>

아… 더럽다

<lifthrasiir>

지금 코드라고 그렇게 깨끗한 것도 아니건만

<lifthrasiir>

오케이 오늘은 이걸로 자자

아 망했어요.