[이준희]

오늘, 과제에 대해 토론한 결과로 볼때, 다음의 코드는 tail-recursive로 판단하고 이에 따른 처리를 해줘야 할 것입니다.

[이준희]

결국은 IF를 할때 무조건 Unit을 리턴하기 때문에 발생한 문제라고 볼 수도 있을 것 같은데(그렇지 않으면 굳이 result에 대입해서 리턴할 필요가 없으므로), 이번 숙제는 차치하고 추후에 K-와 K--의 정의에서 IF의 리턴값은 좀 수정하면 안될까요? ^^;;;

[이준희]

비슷한 예로,

[장민석]

끝재귀 함수의 정의에 따르면 위에서 드신 예 세 개 모두 끝재귀가 아니라고 생각합니다. 함수 f가 바디 안에서 f를 콜하고 리턴되는 순간 바로 또다시 리턴되는 게 아니라 VAR 같은 명령을 수행하지 않습니까.

즉 끝재귀함수 여부는 리턴값에 추가적인 조작이 있느냐 없느냐가 아니라 추가적인 명령을 수행하느냐 아니냐를 기준으로 판단되어야할 것 같습니다.


아...if문이 함수 바디 전체를 감싼 경우는 좀 애매하네요. 이런 건 끝재귀로 봐야하는 건지...

[이준희]

저도 거기에 의문을 가지고 오늘 수업에 들어갔지만, IF문의 특성때문에 result를 이용하여 대신 리턴하는 것도 tail-recursive로 봐야한다는게 오늘 논의된 내용 아니었나요?

또한, hw4.pdf 내용대로라면 IF문으로 전체를 감싸고, 결국 unit을 리턴하는 경우에 대해서도 tail-recursive로 봐야지요. IF문의 특성때문에 '할 일이 없지 않은 - Unit을 리턴해야하는' 것이지, 본디 프로그램의 의도는 tail-recursive한 프로그램을 작성한 것이니까요. IF문의 경우는 따라서 '추후에 할 일이 없는'것으로 보고 작성해야 옳을 듯 한데요.

hw4.pdf파일의 예가 우리의 K--에서는 두 가지로 해석될 수 있기에(result에 대입하여 리턴하는 것을 일반적인 프로그래밍 언어의 문법으로 표현한 것이냐, 아니면 순수 K-- 문법으로 표현한 것이냐) 이런 질문을 올리는 것인데, 오늘 수업에서 한 얘기대로라면 둘다 tail-recursive로 보는게 옳지 않나요?

제가 잘못 이해한거라면 낭패구요;;

[장민석]

아 오늘 관련 논의를 제가 제대로 캐치하지 못했어요. 어제 밤에 잠을 못자고 들어가서 멍하게 있었거든요;;

그런 내용이었다면, 좀 의문스러운 점이 있네요.

우선 재귀함수들 중에 끝재귀만 골라서 작업하는 건, Sm5 기준으로 생각할 때, C의 내용이 사실상 empty이기 때문에 (C,E)를 저장하는 건 무의미하기 때문이잖아요. 그래서 불필요한 비용을 줄인다는 의미에서 끝재귀를 없애는 거죠.

하지만 말씀하신 케이스가 전부 끝재귀라면, 끝재귀 판단하는 것도 사실상 불가능할 뿐더러, call이 실행되고도 뭔가 할일이(sm5차원에서) 남아있는 것이므로 K스택 오퍼레이션의 불필요한 비용을 줄인다는 것도 말이 안 되는 것 같은데요.

[이준희]

불가능할것 같아도, 이리저리 생각해보니 복잡할 뿐이지 가능하긴 하겠더라구요.

단지, 우리가 짤 수 있는 끝재귀 함수의 종류는 굉장히 많은데 그것들 모두를 정확히 판단해내도록 만들기가 어렵기 때문에, 어느 정도까지를 끝재귀 함수로 판단하고 처리하느냐는 범위의 문제일 것 같습니다.

sound와 complete를 각기 어느 정도 만족하느냐에 따라서, 제가 예로 든 함수들을 Sm5x에서 끝재귀로 처리할수도 있고, 그렇지 않을수도 있겠죠. 매우 sound하려면 그냥 IF문에서 unit을 리턴하는 처리 해주는것도 몽땅 '할 일이 있는' 것으로 판단하여 끝재귀가 아니라 일반 함수로 처리할 수도 있겠고(당연히 처리할 수 있는 끝재귀 함수의 종류는 매우 좁아지는...), 그렇지 않을수도 있겠죠...

그래서, 이번 과제에서는 어느 정도까지 적정 범위로 보느냐를 묻는게 제 질문의 핵심입니다.

[이준]

제가 고민을 해보았는데요...
아무래도... 아까 고민했던 것은요..(형이 맨 첨에 올린 예제)
아무래도 끝재귀가 아닌거 같아요..+_+;

result := call f(x)

라고 하는 구문은 잘 생각해 보면 call f(x)한 뒤에 할일이 없는게
아니자나요..;; 의미상으로야 k-의 리턴값을 잘 정해주기 위해서
( if내에 call을 넣어놓구 끝내버리면 리턴값이 Unit이니까.. )
하는 일이라고는 하지만 어찌되었던 call 이후에 일을 하자나요..
assign은 결국 call의 결과를 기다린 뒤 하는 일이죠..
게다가 seq까지 있으니 call뒤에 많은 일을 한다고 봐야죠..

장민석님의 말처럼 위 세개는 테일이 아닌듯;;
그리고 수업시간에 형이랑교수님이랑 하는 얘기를 정확히 파악하지
못하긴 했는데 대략 if가 unit을 리턴하는거 때문에 형이
정상적인 tail recursive라면 if에 쌓여있지 않겠느냐 하는거 아니었나요?

if에 call이 쌓여있어서 엄하게 리턴값이 unit이 된다는 사항과,
if문이 unit을 리턴하기때문에 result란 놈을 assign하는 사항과는
차이가 있는거 같아요.. 안그럴까요? 다른분들은 어떻게 생각하시는지
궁금합니다~ 같이 살아요 +_+

[이준희]

그러니까 내 말은....

위에 언급한 세 예제는, 의미상으로는 끝재귀지. 함수 자체로 볼때, 분명 재귀호출 후 값을 리턴하는 것 외에는 하는 일이 없거든. hw4.pdf에서의 설명도 '하는 일 없이 값을 리턴하는'이라고 되어있잖아. Sm5에서 명령어가 쌓이느냐 그렇지 않느냐와는 별개로, 끝재귀 함수라는게 Sm5x를 위해서 정의된 것이 아니라 일반적인 프로그래밍 언어와 관련된 한 가지 토픽이라는 점에서 볼때 저런 함수들을 '끝재귀가 아니다'라고 하는건 뭔가 아쉽지 않아?

단지... 우리의 Sm5x가 이런 끝재귀를 과연 complete하게 잡아낼 수 있느냐인데, 여기에 대해선 깊게 생각해보지 않아서 모르겠지만 아마 불가능할것 같아(halting problem과 연계시켜 생각해봐야겠지). 그렇다곤 해도, 세 예제 가운데 첫번째 경우 정도도 잡아주지 못하면 실제 Sm5x 프로그램 가운데(정확히는 K--프로그램이 되겠지만) 끝재귀를 이용해 속도와 메모리 사용량에 이득을 볼 수 있는 케이스는 매우 적어지고, 특수한 케이스를 제외하면 거의 쓸모없는 프로그램들이 되지 않을까?

그래서, 첫번째 경우도 Sm5x에서 처리해주자...라고 결정한다면, 두번째나 세번째 경우도 잡아줘야 하느냐, 그렇지 않느냐가 이제 문제가 되는거지. 안하기로 맘먹으면 편하게 구현할 수 있는데(어디까지나 상대적으로 ), 그러자니 뭔가 좀 찝찝하고...

사실, K--에서 인자를 두개 받는게 전혀 불가능한것은 아니므로(레코드가 있으니), 잘 생각하면 아까 수업시간에 교수님께서 말씀해주신 끝재귀 factorial(사실은 permitation이지만)도 끝재귀로서 처리해줄 수 있을것 같아. 단지, 위의 세가지 예제보다 좀더 복잡한 구현을 통해서 해결할 수 있겠지.

어쨌든, 난 그냥 어디까지 구현해야 하느냐가 알고 싶을 뿐이야

[이준희]

그리고........ 만일 저 위의 예제를 모두 끝재귀로 판단해내고 잘 처리만 해준다면, result에 대입한다든가, IF에서 unit을 리턴한다든가 하는 '불필요한' 과정들을 쌓지 않게끔 할 수 있기 때문에(Sm5x쪽에서 어떻게 처리할지를 잘 생각해보면, 저런것들을 하나도 하지 않아도 된다는 것을 알 수 있습니다) 확실히 속도와 메모리에 이점이 있을겁니다.

물론 trans는 그만큼 복잡해지지만, 어차피 Sm5x 프로그램의 수행을 최적화하는 것이지 번역 과정을 최적화하는 것은 아니니...

[박종석]

제 생각에 우리가 하고자 하는 끝 재귀는 어떠한 형식이 있는것 같습니다.

factorial을 끝재귀로 하지 않는 것과 마찬가지로 (약간만 변경하면 끝재귀가 가능합니다.) 아래와 같은 함수도 끝재귀가 아니라고 생각합니다.

fac2(x) = if x < 0 then 1 else 1 * fac2(x-1)

이 함수는 분명 의미상으로는 끝재귀지만 형식상 끝재귀에 어긋남니다.

교수님이 끝재귀가 아닌것을 끝재귀로 만드는게 아니라 끝재귀인것을 효과적으로 하라고 하셨던 것으로 기억하는데요,

때문에 제생각으로는
f(x) =
if x < 0 then
r = 1
else
r = f(x)
end;
r
딱 이형식만 갖춘것이 끝재귀라 생각합니다.
여기서 변경되면 위의 fac2처럼 모양은 끝재귀가 아니고 의미만 끝재귀인것으로 바뀐다고 생각됩니다.

[이준]

저도 비슷한 생각입니다. 무언가 tail에 대한 확실한 정의가 필요할 듯 합니다.
기본적으로 수업시간에 이야기 하였던

[신종호]

[이준희]

후우..... 대강 첫번째 케이스는 TR로 인식하고 수행하도록 하는데 성공했는데...

...........2차 딜레이 OTL

..................버그 있으면 어쩌지 OTL

..........................2번째나 3번째도 하려고 맘먹으면 할수는 있는데 코드가 엄청 복잡해질 것 같...Orz
_________________
...

[이준희]

...........어려울줄 알았더니, 3번째 케이스는 의외로 간단하군요(...)