[seongtae_jeong]

안녕하세요.
exercise 6-1에서 재귀호출을 구현하는 것에 관해 질문이 있습니다.

재귀호출의 depth에 상한이 정해져 있는지가 궁금합니다.

현재의 SM5 스펙으로는 command 안에서의 jump가 불가능하므로 recursion depth가 커질수록 command의 길이도 길어질 수밖에 없다고 생각습니다.
따라서 depth의 상한이 없도록 구현하려면 command가 무한히 길어져야 하는데 이는 불가능합니다.
이 때문에 recursion depth의 상한을 가정하고 구현해도 되는지가 궁금해졌습니다.

또한 비슷한 논리를 while/for loop에도 적용하면 loop을 도는 횟수의 상한이 있어야 할 것 같은데, 여기에서도 상한을 가정해도 되는지 궁금합니다.

[이재호]

안녕하세요,

제가 질문을 제대로 이해했다면, 학생분께서는 미리 함수 호수 횟수를 읽은 후 번역을 하려고 하는 것 같습니다.
test5.k-- 같은 경우 코드를 10회 반복하는 방식으로 말입니다.
하지만 test5.k--처럼 10이 주어지는 것이 아니라 계산의 결과로 나온 값이라면, 해당 방식은 작동하지 않을 것입니다.

"jump가 불가능하므로 recursion depth가 커질수록 command의 길이도 길어질 수밖에 없"지 않습니다.
K-- 코드가 유한하다면 번역된 SM5 코드도 유한하도록 번역할 수 있습니다.

이와 별도로, 재귀 호출의 깊이나 반복문의 횟수는 적당한 값에 대해서만 테스트합니다.

감사합니다.

조교 드림


TA 이재호
e-mail: jhlee@ropas.snu.ac.kr

[seongtae_jeong]

답변 감사드립니다.

다만 미리 함수 호출 횟수를 알고 나서 번역을 해야겠다고 생각한 것은 아닙니다.
말씀해주신 대로 횟수를 실행 전에 미리 알지 못하는 경우가 많기 때문입니다.
대신 만약 호출 횟수의 상한이 있다면 그만큼 호출해도 문제가 없도록 미리 환경을 만들어둘 수 있다고 생각했습니다.
(호출 횟수를 미리 아는 것과 비슷한 맥락이기는 합니다.)

이런 생각을 한 것은, CALL 명령을 사용했을 때 env를 보존하는 것이 불가능하다고 생각했기 때문입니다.
CALL 명령은 env에 저장되어 있던 proc (x, C', E')를 불러오는 것인데, 이 proc은 PUSH (x, C') 명령을 통해서만 만들 수 있습니다.
그런데 이때 E' 안에는 proc (x, C', E')가 똑같이 들어 있을 수 없습니다.
그 E'는 proc이 만들어지기도 전의 env이기 때문입니다.
함수를 만들고 env에 추가하는 과정을 여러 번 반복할 수는 있겠지만, 이 과정을 무한히 반복할 수 없는 이상 완전한 재귀함수를 구현할 수는 없다는 생각이었습니다.

혹시 이런 생각에 어떤 오류가 있는지 알려주실 수 있을까요?

감사합니다.

[이재호]

안녕하세요,

우선 CALL 명령은 env가 아니라 stack에서 (x, C', E')을 꺼내오는 명령어입니다.

말씀주신 것처럼 E' 안에 (x, C', E')이 그대로 들어있을 수는 없겠습니다. 모든 기계 장치 자체의 크기는 유한하기 때문입니다.
그런데 K에서도 재귀함수를 구현하신 것처럼, 유한한 장치만으로 무한히 진행하는 코드를 작성할 수 있습니다.

무한 사이클이 있는 그래프를 C 같은 언어에서 구현할 수 있다는 점을 생각하시면 좋을 것 같습니다.

감사합니다.

조교 드림


TA 이재호
e-mail: jhlee@ropas.snu.ac.kr