게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

5-2번 질문입니다.

 
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.310 Programming Languages (Fall 2005)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
임연섭



가입: 2005년 10월 5일
올린 글: 9

올리기올려짐: 2005년11월5일 17:41    주제: 5-2번 질문입니다. 인용과 함께 답변

K--의 재귀호출을 SM5x로 번역할 때 함수호출비용이 줄어들도록 하는 것이다

이 말의 의미가 어떠한 재귀호출을 하더라도 호출비용을 줄이도록

번역하게 하라는건가요?(끝재귀는 줄일 수 있다. 이 말이 그럼

모든 재귀호출을 끝재귀 같은 형태로 바꿔서 줄여라 이런 해석인건지.. ㅜ.ㅜ)

문제가 잘 이해가 안되네요.. ㅜ.ㅜ

끝재귀를 만나면 스택에 쌓이는걸 줄이도록 하라는 것인지요?

과제가 너무 어려워요.. ㅜ.ㅜ
위로
사용자 정보 보기 비밀 메시지 보내기
오학주



가입: 2005년 9월 5일
올린 글: 118

올리기올려짐: 2005년11월5일 18:46    주제: 인용과 함께 답변

끝재귀호출(tail-recursion)의 경우에만 비용을 줄일 수 있으면 됩니다.
예를 들어 다음과 같은 프로그램은 stack overflow없이 영원히 돌 수 있어야 합니다.
코드:

let procedure f (x) = call f(x)
in call f(1)
end
위로
사용자 정보 보기 비밀 메시지 보내기 글 올린이의 웹사이트 방문
고우종



가입: 2005년 9월 28일
올린 글: 5

올리기올려짐: 2005년11월6일 18:54    주제: 인용과 함께 답변

오학주 씀:
끝재귀호출(tail-recursion)의 경우에만 비용을 줄일 수 있으면 됩니다.
예를 들어 다음과 같은 프로그램은 stack overflow없이 영원히 돌 수 있어야 합니다.
코드:

let procedure f (x) = call f(x)
in call f(1)
end


현재 SM5 의 함수 호출은 호출시 메모리 M에 인자를 위한 공간을 할당하지만 return 시 다시 거둬들이지는 않고 있습니다. 따라서 GC를 구현하지 않으면 위와 같은 프로그램을 현재의 정의에서는 무한히 돌릴 수 없습니다.

물론 그래도 SM5x가 SM5보다 더 느리게 메모리 한계에 도달할 것 같습니다만 그 차이를 구별할만한 테스트는 어떻게 해야 될지...
위로
사용자 정보 보기 비밀 메시지 보내기 MSN 메신저
서상원



가입: 2005년 9월 27일
올린 글: 33

올리기올려짐: 2005년11월6일 20:22    주제: 인용과 함께 답변

끝재귀호출인 경우 "비용을 줄여서" 영원히 돌 수 있도록 하면 됩니다.
위의 코드는 비용을 줄이지 않으면 GC가 있어도 무한히 돌 수 없습니다.
위로
사용자 정보 보기 비밀 메시지 보내기
고우종



가입: 2005년 9월 28일
올린 글: 5

올리기올려짐: 2005년11월6일 20:30    주제: 인용과 함께 답변

끝재귀호출의 비용을 줄인 SM5x라 하여도 기본적으로 인자에 대한 메모리는 할당하므로 위 프로그램은 재귀호출의 비용이 0이라 하여도 인자 크기의 메모리 공간이 점점 줄어들어 결국에 한계에 다다르게 됩니다. 다시 말하자면 조교님 글대로 끝재귀호출 최적화가 되어있다면 무한히 돌아도 K의 overflow는 발생하지 않지만 현재 인자가 할당되는 M의 모든 공간이 소비되면 결국 프로그램이 죽게됩니다.

현재 인자를 void로 주는 함수 정의나 호출이 정의 상에 없으므로 위 프로그램을 무한히 돌리는 건 다른 수정없이 SM5x만을 가지고는 힘듭니다.

기본적으로 끝재귀호출의 비용을 줄인다는 건 호출할 때의 오버헤드도 있지만 리턴될 때의 오버헤드를 줄이는 것이 포인트이기 때문에 (그래서 끝재귀호출이란 특이한 케이스에 대하여 생각하는 겁니다.) 위 프로그램처럼 호출만 하고 리턴하지는 않는 프로그램의 경우 끝재귀호출 최적화가 의미가 있는지 의문이 듭니다.
위로
사용자 정보 보기 비밀 메시지 보내기 MSN 메신저
서상원



가입: 2005년 9월 27일
올린 글: 33

올리기올려짐: 2005년11월6일 21:58    주제: 인용과 함께 답변

sm5에 새로운 명령어를 추가할 수 있다는 사실을 잊으신건 아닌지요?

K--의 call 의미를 따르면 메모리를 계속 소진하겠지만, 변형해서 최적화하겠다는 거니까 sm5x의 끝재귀호출에서도 그 의미를 유지할 필요는 없겠지요.
위로
사용자 정보 보기 비밀 메시지 보내기
고우종



가입: 2005년 9월 28일
올린 글: 5

올리기올려짐: 2005년11월6일 22:57    주제: 인용과 함께 답변

물론 SM5를 수정해도 되는 것은 아주 잘 알고 있습니다.
하지만 문제를 보면 교수님께서는 "함수 호출 비용"을 K에 쌓이는 현상으로 정의하셨고 이 현상을 줄이라고 하셨습니다.

하지만 위 프로그램을 무한히 돌리는 문제는 "함수 호출 비용"뿐만 아니라 다른 부분의 semantic까지 바꾸어야 풀 수 있는 문제입니다.
물론 이 문제가 불가능하다는 것이 아닙니다. 모든 recursive 함수는 iterative로 변환할 수 있고, iterative를 무한히 돌리는 것은 그다지 어려운 일이 아닙니다. 게다가 현재 의미상 정 불가능하다면 SM5를 전부 뜯어고쳐서 아예 새로운 언어를 만들어버리면 되겠지요. Wink

하지만 제가 묻고 싶은 것이 과연 저 프로그램을 무한히 돌리는 것이 끝재귀함수 최적화와 동치인 문제인가 입니다. 끝재귀 함수 최적화가 저 문제의 부분 집합은 될 수 있겠지만 끝재귀 함수 최적화가 이루어지지 않았다면 위 프로그램이 무한히 돌지 않는다고 생각하기는 힘들 것 같은데 제 생각이 틀렸는지요?

문제대로 "함수 호출 비용"만을 줄였다면 얼마든지 위 프로그램이 무한히 돌지 않을 수 있습니다. 제 첫번째 문제 제기는 이러한 생각에서 제기한 것입니다. 단순히 저 프로그램을 무한히 돌리는 게 불가능하다는 말이 아닙니다.
위로
사용자 정보 보기 비밀 메시지 보내기 MSN 메신저
서상원



가입: 2005년 9월 27일
올린 글: 33

올리기올려짐: 2005년11월6일 23:28    주제: 인용과 함께 답변

교수님께서 그렇게 언급하셨기 때문에 K에 쌓이는 현상만 해결해도 문제를 푼 것으로 볼 수 있을 것 같습니다. (제가 재첨할 건 아니지만 Wink)

말씀하신 것처럼 K에 쌓이는 현상만 해결한다면 위 프로그램은 무한히 돌지 않을 수 있습니다. 다만 보통 끝재귀를 최적화했다고 하면 위와 같은 프로그램이 무한히 돌기 때문에 다른 뜻 없이 말씀하셨을 겁니다.
하지만 recursive 함수를 iterative로 바꾸려면 사용자 스택등을 이용해서 관리해줘야하지 않나요? 스택에 쌓이는 iterative를 어떻게 무한히 돌릴 수 있는지 모르겠군요. 동치인지는 모르겠으나 끝재귀를 최적화하지 않고 무한히 돌릴 수 있는 방법을 전 모르겠군요. Sad

현재 의미 정의를 뜯어 고치지 않고 새로운 의미를 가지는 명령어를 추가하면 됩니다. 다른 부분의 의미가 변한다고 생각하실 필요가 없습니다.
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.310 Programming Languages (Fall 2005) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay