KTUGFaq

KTUG FAQ

"Tail recursion"에 댓글 더하기

로그인:
비밀번호:
가입
A man who fishes for marlin in ponds will put his money in Etruscan bonds.
FrontPage › LittleTree/ReadingTeXbook/2006-03
Mar 29, 2006
Tail recursion
Submitted by 작은나무 @ 03-29 [12:14 pm]
219쪽: 다음과 같은 매크로 정의가 있다고 합시다.
\def\foo{어쩌구 저쩌구 ... \bar ... 저쩌구 어쩌구}
즉 매크로 \foo의 replacement text 안에 다른 매크로 \bar가 있는 경우입니다. 이 경우, 아마도 TeX은 \foo 매크로를 전개하다가 \bar 매크로를 만나는 순간 \bar 매크로의 전개를 마친 다음, 남아 있는 \foo 매크로를 계속 전개하기 위해서 \foo 매크로의 replacement text 내의 \bar 매크로 다음의 토큰 위치를 기억해 두어야 할 것입니다. 만약에 \bar 매크로 역시 그의 replacement text 안에 다른 매크로가 있다면, \foo 와 마찬가지로 메모리의 어딘가에 계속 전개할 토큰의 위치를 적어두어야 할 것입니다.

그런데, 문제는 위의 예에서 \bar가 \foo인 경우입니다. 즉, 아래와 같은 경우인데,
\def\foo{어쩌구 저쩌구 ... \foo ... 저쩌구 어쩌구}
이러한 경우를 recursion 이라고 합니다. 우리말로 '재귀'라고 합니다. 간단히 말해서 어떤 것을 정의하는데, 그 정의에 어떤 것 즉 자기 자신이 이용된는 것입니다. 예를 들어 GNU 모두 아시죠? 이 GNU의 정의가 GNU is Not Unix의 약자라고 합니다. GNU를 정의하는데 GNU가 사용되었기 때문에 이 역시 recursion 이라고 할 수 있습니다. (온통 재귀로 이루어진, 재귀가 생명인 컴퓨터 프로그래밍 언어 Lisp과 그 lisp으로 모든 것을 다 할 수 있는 emacs, 그리고 이 emacs를 만든 스톨만, 스톨만이 깊이 관여하고 있는 GNU. 이 모두가 GNU의 재귀적 정의를 갖게 된 것과 무관하지 않을 것입니다. :) 제 추측입니다.)

위의 \foo와 같은 매크로를 전개할때 마다, TeX은 replacement text 내의 \foo 다음의 토큰 위치를 기억하기 메모리를 계속 사용할 것입니다. 아마도 컴퓨터 프로그래밍에서 자주 사용되는 스택이라는 것을 이용할 것같은데, \foo가 전개될때마다 스택에는 \foo의 다음 토큰 위치를 기억하기 위해서 그 메모리 번지가 많이 쌓일 것입니다. 스택의 의미를 몰라도 그저 컴퓨터의 메모리를 많이 사용한다고 이해하면 될 것입니다. 컴퓨터의 메모리 또한 컴퓨터의 자원이고, 컴퓨터가 자원을 많이 사용한다는 의미는 시간과 자원 측면에서 그리 효율적이지 못합니다.

하지만, 같은 recursive 매크로라도 다음과 같은 경우는 어떨까요?
\def\foo{어쩌구 저쩌구 ... \foo}
위의 재귀와 다른 점은 replacement text내의 \foo 다음에 아무런 토큰도 없다는 점입니다. 이러한 재귀의 장점은 TeX이 \foo 다음의 위치를 기억할 필요가 없다는 점입니다. 왜냐하면 \foo의 전개를 마치고 그 다음을 계속 전개하기 위해서 그 위치로 왔지만, 전개할 것이 없기 때문입니다. 따라서 이경우는 스택에 다음에 전개할 토큰의 위치를 기억할 필요도 없습니다.!!! 이러한 경우 처럼 재귀 호출이 맨 마지막에 있다고 해서 "tail recursion" 이라고 합니다. 우리말로 '꼬리재귀'라고도 합니다. 이제 TeXbook에 이 tail recursion을 설명하면서 하는 말,
..., and the memory does not fill up during a long loop. ...
을 이해할 수 있을 것입니다.

또한 TeXbyTopic 이라는 책의 11.8.3 Tail recursion에 나와있는 다음과 같은 말도 쉽게 이해할 수 있을 것입니다.
In general this 'stack build-up' is a necessary evil, but it can be prevented if the nested macro call is the last token in the replacement text of the original macro. After the last token no further tokens need to be considered, so one might as well clear the top item from the input stack before a new one is put there. This is what TeX does.
어렵게만 보이던 TeXbyTopic 이라는 책이 만만해 보입니다. 신납니다. :)

이제 아주 인상깊은 매크로 \loop ... \repeat를 이해할 수 있을 것입니다.
\def\loop#1\repeat{\def\body{#1}\iterate} \def\iterate{\body\let\next=\iterate\else\let\next=\relax\fi\next}
TeX을 공부하면서 저 매크로를 보고 이해하는 순간은 아주 감동적이었습니다. 수학자들이 흔히 말하는 것 처럼 "아름답습니다."

마지막으로 저~~~ 아래에서 언급한 Knuth의 어록을 마지막으로 이번 독후감을 마치겠습니다. :) 위의 설명에서 처럼 recursion은 매우 엘레강스하고 간단하지만 컴퓨터 입장에서 보면 그리 효율적이지 못합니다. 스택이라는 메모리를 사용해야되고, 위치를 저장해야되고... 그리고 대개 재귀적으로 정의된 문제는 반복적(iterate)으로 해결할 수 있습니다. 하지만, 프로그래밍을 하다보면 가끔 recursion을 사용합니다. 그 간단 명료함에 반해서 이지요. 같은 맥락으로 Knuth도 말했지요?

"... aesthetics are more important than efficiency"

글은 재미있게 읽었는데 인상깊은 매크로는 이해가 안되는 군요 OTL -- hermian 2006-03-29 12:37:09

노현정 아나운서가 이렇게 말했을 것입니다. "hermian님, 공부하세요" ;) -- 작은나무 2006-03-29 14:13:19

도움이 될까 해서... 1부터 100까지 한줄씩 출력하기:
\let\endgraph\par
\count255=0
\loop
  \advance\count255 by1
  \the\count255 \endgraph
  \ifnum\count255<100 \repeat
-- DohyunKim 2006-03-29 14:48:52

저도 몇 줄 기여. 이 기사의 내용에 알맞게... ^^ ;;
\let\endgraph\par

\newcount\n\newcount\i
\def\scatterline#1{\n=#1 \i=0 \putline}
\def\putline{%
	\ifnum\n>0 \else \multiply\n by-1 \fi
	\advance\i by1
	\number\i \endgraph
	\ifnum\i<\n \let\next=\putline
	\else\let\next=\relax\fi\next}

\scatterline{-100}

I have scattered to \number\n line by line.

\scatterline{10}

\bye
-- Karnes 2006-03-30 03:25:20

"요즈음 공부하세요"가 유행인가 보네요. 회사에서도 듣고 ㅜㅜ. 경문사의 "TeX 입문"을 샀는데 볼만하네요. 언제 보려나... 맨날 회사일에 쪼들려 사는 인생. 에헤라~ 다음에 KTUG모임있음 작은나무님 한번 뵙고싶네요 ㅎㅎ -- hermian 2006-03-30 10:03:11
이름:

서명하지 않기
 

^
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2006-06-06 22:54:57
Processing time 1.4617 sec