게시판 인덱스

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

5-2질문입니다.

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



가입: 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    주제: 인용과 함께 답변

저도 형찬님과 같은 의문을 가지고 있습니다.
이부분에 대해 조교님께서 빨리 답변 해주시면 좋겠습니다. Shocked
위로
사용자 정보 보기 비밀 메시지 보내기
오학주



가입: 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형이 나올 뿐입니다. 그래서 타입이 맞지 않다고 말씀하시는 의미가 잘 이해가 되지 않습니다. 제가 무언가 착각하고 있는 것인지요.


형찬님 말이 맞습니다. 의도했던 바는 결과값이 버려지기 때문에 실용성이 없는 프로그램이라 값을 누적시킴으로써 좀더 실용성 있는(?) 예제를 보여주려던 것인데 표현이 서툴렀습니다. Embarassed
위로
사용자 정보 보기 비밀 메시지 보내기 글 올린이의 웹사이트 방문
오학주



가입: 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을 리턴하므로 끝재귀호출 처리를 할 수 있을 것 같습니다. 제가 잘못 생각하고 있는 건가요? Confused
위로
사용자 정보 보기 비밀 메시지 보내기 글 올린이의 웹사이트 방문
안형찬
손님





올리기올려짐: 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    주제: 두번째 답 올리신 것을 못보았네요. 인용과 함께 답변

두번째 글도 올라온 줄 모르고 첫번째 올리신 답변만 보고 답글을 달아버리고 말았습니다 Shocked

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: 두번째 답 올리신 것을 못보았네요. 인용과 함께 답변

안 형찬 씀:
두번째 글도 올라온 줄 모르고 첫번째 올리신 답변만 보고 답글을 달아버리고 말았습니다 Shocked

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를 호출해 준다거나)...
제가 좀 더 생각해 보아야 할 부분인 것 같습니다. 감사합니다.
위로
이전 글 표시:   
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 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