이전 주제 보기 :: 다음 주제 보기 |
글쓴이 |
메시지 |
안형찬
가입: 2005년 10월 22일 올린 글: 12
|
올려짐: 2005년11월8일 3:58 주제: 5-2질문입니다. |
|
|
문제에는
procedure f(x) = if x<0 then 1 else f(x-1)
에서, 재귀호출 f(x-1)이 끝난 후에 할일은 아무것도 없다고 하였습니다만, 우리의 K-- semantics는 if의 '값'이 unit이 되도록 정의하고 있습니다. 따라서 f(x-1) 호출이 끝난 후 스택을 pop하고 (pop된 값과 상관없이, if의 평가값으로서) unit값을 넣는 할일이 있는 것 같습니다.
* 이 경우라면 f(x)가 어차피 파라미터에 상관없이 unit을 리턴하므로 f(x-1)을 호출한 리턴값을 pop하고 unit을 push하는 것을 한꺼번에 없애는 방식으로 tail-recursion처리가 가능할 것 처럼도 보이지만, 일반적으로는 이렇게 할 수 있을지 의문입니다. 예를 들면 다음과 같은 경우에 c(x)는 리턴값이 항상 unit입니다.
procedure a(x) = x
procedure b(x) = if x < 0 then a(x) else b(x-1)
procedure c(x) = if x < 100 then b(x) else c(x-1) |
|
위로 |
|
|
한재호
가입: 2005년 10월 27일 올린 글: 14
|
올려짐: 2005년11월8일 18:41 주제: |
|
|
저도 형찬님과 같은 의문을 가지고 있습니다.
이부분에 대해 조교님께서 빨리 답변 해주시면 좋겠습니다. |
|
위로 |
|
|
오학주
가입: 2005년 9월 5일 올린 글: 118
|
올려짐: 2005년11월8일 19:30 주제: |
|
|
코드: |
procedure f(x) = if x < 0 then 1 else f(x-1)
|
먼저 위의 코드는 타입이 맞지 않음을 알려드립니다.
if의 리턴값은 unit이므로 f(x-1)의 리턴값은 unit일텐데, then 파트에서 정수를 리턴하니까요.
위의 함수를 다음과 같이 레코드와 포인터를 이용하여 표현해 봅시다.
코드: |
procedure f(x) = if x.fst < 0 then (x.snd+0) = 1
else f({fst:=x.fst-1, snd:=x.snd})
|
이 경우는 K-의 if가 항상 unit을 리턴하므로 함수 f도 항상 unit을 리턴하게되고 스택에 unit을 계속 쌓을 필요가 없습니다.
따라서 이 경우는 tail-recursion으로 변환 할 수 있겠지요. |
|
위로 |
|
|
안형찬 손님
|
올려짐: 2005년11월8일 19:48 주제: |
|
|
오학주 씀: | 코드: |
procedure f(x) = if x < 0 then 1 else f(x-1)
|
먼저 위의 코드는 타입이 맞지 않음을 알려드립니다.
if의 리턴값은 unit이므로 f(x-1)의 리턴값은 unit일텐데, then 파트에서 정수를 리턴하니까요.
|
이 코드는 문제지에서 베껴온 것입니다만, K--의 semantics는 if의 then절과 else절의 type에 관해서는 어떠한 제한도 두고있지 않습니다. 다만, 결과와 관계없이(결과를 '버리'고) unit형이 나올 뿐입니다. 그래서 타입이 맞지 않다고 말씀하시는 의미가 잘 이해가 되지 않습니다. 제가 무언가 착각하고 있는 것인지요. |
|
위로 |
|
|
오학주
가입: 2005년 9월 5일 올린 글: 118
|
올려짐: 2005년11월8일 20:30 주제: |
|
|
Anonymous 씀: | 오학주 씀: | 코드: |
procedure f(x) = if x < 0 then 1 else f(x-1)
|
먼저 위의 코드는 타입이 맞지 않음을 알려드립니다.
if의 리턴값은 unit이므로 f(x-1)의 리턴값은 unit일텐데, then 파트에서 정수를 리턴하니까요.
|
이 코드는 문제지에서 베껴온 것입니다만, K--의 semantics는 if의 then절과 else절의 type에 관해서는 어떠한 제한도 두고있지 않습니다. 다만, 결과와 관계없이(결과를 '버리'고) unit형이 나올 뿐입니다. 그래서 타입이 맞지 않다고 말씀하시는 의미가 잘 이해가 되지 않습니다. 제가 무언가 착각하고 있는 것인지요. |
형찬님 말이 맞습니다. 의도했던 바는 결과값이 버려지기 때문에 실용성이 없는 프로그램이라 값을 누적시킴으로써 좀더 실용성 있는(?) 예제를 보여주려던 것인데 표현이 서툴렀습니다. |
|
위로 |
|
|
오학주
가입: 2005년 9월 5일 올린 글: 118
|
올려짐: 2005년11월8일 20:32 주제: Re: 5-2질문입니다. |
|
|
안형찬 씀: | 문제에는
* 이 경우라면 f(x)가 어차피 파라미터에 상관없이 unit을 리턴하므로 f(x-1)을 호출한 리턴값을 pop하고 unit을 push하는 것을 한꺼번에 없애는 방식으로 tail-recursion처리가 가능할 것 처럼도 보이지만, 일반적으로는 이렇게 할 수 있을지 의문입니다. 예를 들면 다음과 같은 경우에 c(x)는 리턴값이 항상 unit입니다.
procedure a(x) = x
procedure b(x) = if x < 0 then a(x) else b(x-1)
procedure c(x) = if x < 100 then b(x) else c(x-1) |
제가 보기에는 위의 c(x)의 경우도 then 파트와 else 파트에서 항상 unit을 리턴하므로 끝재귀호출 처리를 할 수 있을 것 같습니다. 제가 잘못 생각하고 있는 건가요? |
|
위로 |
|
|
안형찬 손님
|
올려짐: 2005년11월8일 20:39 주제: 그렇다면.. |
|
|
그렇다면 제가 원래 드리려던 질문입니다만, 문제에 주어진 것과 같은 코드는 call뒤에 할 일(stack을 비우고 unit에 해당하는 값을 push하는)이 있는 것 같은데 그래도 tail-recusion으로 처리하여야 합니까?
SM5를 심하게 건드리는 이상한 방법을 사용하지 않는 한, IF의 then(else) clause의 마지막 문장에서의 함수 call이 tail-recursion으로 처리될 수 있는 방법이 잘 상상이 가지 않습니다. 제 생각이 짧을 뿐으로 실은 어떤 방법이 있는 것인지, 아니면 2번에 대해서 IF의 semantics를 달리 생각해야 하는 것인지, 어떤 것인지 궁금합니다.
감사합니다. |
|
위로 |
|
|
안형찬 손님
|
올려짐: 2005년11월8일 20:50 주제: 두번째 답 올리신 것을 못보았네요. |
|
|
두번째 글도 올라온 줄 모르고 첫번째 올리신 답변만 보고 답글을 달아버리고 말았습니다
let procedure f(x) = if x < 0 then 1 else call f(x-1) end in
let procedure g(x) = call f(x); x in
let procedure h(x) = if x < 100 then call g(x) else call g(x-1) end in
과 같은 경우에 h(x)는 항상 unit이 리턴되지만, g(x)는 항상 정수가 리턴되므로 h(x)에서는 tail recursion은 쓸 수 없습니다. 하지만 tail recursion이 가능한
let procedure f(x) = if x < 0 then 1 else call f(x-1) end in
let procedure g(x) = call f(x) in
let procedure h(x) = if x < 100 then call g(x) else call g(x-1) end in
이 코드와 첫번째 코드와 같은 코드를 '항상' 감별할 수 있는 방법이 있습니까? 심지어
let procedure f(x) = let a := 0 in if x > 10 then 1 else false end; a end
와 같은 코드는 파라미터에 따라 리턴형이 달라지기까지 합니다만, 프로그램 실행 중의 type을 알아내는 문제와 점점 가까워져서 풀리지 않는 것이 아닌가 (물론 이걸로는 reduction방향이 반대라서 풀리지 않는다는 수학적 보장은 전혀 없습니다만) 두렵습니다. |
|
위로 |
|
|
오학주
가입: 2005년 9월 5일 올린 글: 118
|
올려짐: 2005년11월8일 21:00 주제: Re: 두번째 답 올리신 것을 못보았네요. |
|
|
안 형찬 씀: | 두번째 글도 올라온 줄 모르고 첫번째 올리신 답변만 보고 답글을 달아버리고 말았습니다
let procedure f(x) = if x < 0 then 1 else call f(x-1) end in
let procedure g(x) = call f(x); x in
let procedure h(x) = if x < 100 then call g(x) else call g(x-1) end in
과 같은 경우에 h(x)는 항상 unit이 리턴되지만, g(x)는 항상 정수가 리턴되므로 h(x)에서는 tail recursion은 쓸 수 없습니다. 하지만 tail recursion이 가능한
let procedure f(x) = if x < 0 then 1 else call f(x-1) end in
let procedure g(x) = call f(x) in
let procedure h(x) = if x < 100 then call g(x) else call g(x-1) end in
이 코드와 첫번째 코드와 같은 코드를 '항상' 감별할 수 있는 방법이 있습니까? 심지어
let procedure f(x) = let a := 0 in if x > 10 then 1 else false end; a end
와 같은 코드는 파라미터에 따라 리턴형이 달라지기까지 합니다만, 프로그램 실행 중의 type을 알아내는 문제와 점점 가까워져서 풀리지 않는 것이 아닌가 (물론 이걸로는 reduction방향이 반대라서 풀리지 않는다는 수학적 보장은 전혀 없습니다만) 두렵습니다. |
보여주신 코드의 h(x)는 재귀함수가 아니지 않나요? |
|
위로 |
|
|
안형찬 손님
|
올려짐: 2005년11월8일 21:22 주제: |
|
|
재귀함수로 바꾸려면 바꿀수는 있겠습니다만(f의 선두에 한번에 리턴될 파라미터로 h를 호출해 준다거나)...
제가 좀 더 생각해 보아야 할 부분인 것 같습니다. 감사합니다. |
|
위로 |
|
|
|