적은 코드로 간단하고 깔끔하게 수학문제를 잘 풀어낼 수 있다. loop를 사용하는 것보다 더 간결하다. 하지만 재귀는 논리를 이해하기 어렵고 그러나 가끔 stack overflow이슈를 일으킨다.
- S-표현식 (S-expression): S-표현식은 Lisp와 Scheme과 같은 프로그래밍 언어에서 사용되는 표현 방법입니다. 일반적으로는 괄호로 둘러싸인 리스트로 표현되며, 함수와 인자들을 나타내는 구조를 가집니다.
예시: (add 2 3)은 "2와 3을 더한다"라는 의미를 가지는 S-표현식입니다.
- RCFAE (Recursive, Combinatory, and Functional Arithmetic Expression): RCFAE는 수학적인 표현식을 나타내는 언어입니다. 이 언어는 재귀적, 조합적 및 함수적인 특징을 가지며, 수학적 계산을 표현합니다.
예시: (add (lit 2) (lit 3))은 "2와 3을 더한다"를 나타내는 RCFAE 표현식입니다.
-
따라서 "s-exp->RCFAE"는 S-표현식을 RCFAE 표현식으로 변환하는 과정이라고 볼 수 있습니다. 이는 일반적으로 프로그래밍 언어나 문법 변환 관련 작업에서 사용되는 용어일 것입니다.
-
<num>: 이는 숫자를 나타냅니다. 예를 들어, 1, 2, 3 등의 정수가 될 수 있습니다.
-
{+ <RCFAE> <RCFAE>}: 이는 두 개의 RCFAE 표현식을 더하는 연산을 나타냅니다. 예를 들어, {+ 2 3}은 "2와 3을 더한다"를 나타냅니다.
-
{- <RCFAE> <RCFAE>}: 이는 두 개의 RCFAE 표현식을 뺄셈하는 연산을 나타냅니다.
-
{* <RCFAE> <RCFAE>}: 이는 두 개의 RCFAE 표현식을 곱하는 연산을 나타냅니다.
-
<id>: 이는 식별자(변수 이름)를 나타냅니다.
-
{fun {<id>} <RCFAE>}: 이는 함수를 정의하는 구문입니다. <id>는 함수의 매개변수 이름이 되고, <RCFAE>는 함수의 몸체를 나타냅니다.
-
{<RCFAE> <RCFAE>}: 이는 함수 호출을 나타냅니다. 첫 번째 <RCFAE>는 함수 자체를 나타내고, 두 번째 <RCFAE>는 함수에 전달되는 인자입니다.
-
{if0 <RCFAE> <RCFAE> <RCFAE>}: 이는 조건문을 나타냅니다. 첫 번째 <RCFAE>는 조건식, 두 번째 <RCFAE>는 조건이 0일 때 실행되는 부분, 세 번째 <RCFAE>는 조건이 0이 아닐 때 실행되는 부분입니다.
-
{rec {<id> <RCFAE>} <RCFAE>}: 이는 재귀 함수를 정의하는 구문입니다. <id>는 재귀 함수의 이름이 되고, 두 번째 <RCFAE>는 재귀 함수의 몸체를 나타내며, 세 번째 <RCFAE>는 재귀 함수를 호출하는 부분입니다.
{rec {fac {fun {n}
{if0 n
1
{* n {fac {- n 1}}}}}}
{fac 10}
이 코드는 rec으로 시작하여 재귀 함수를 정의하고 있습니다. 이 함수는 fac라는 이름을 가지며, 인자로 n을 받습니다. 함수의 몸체는 조건문을 사용하여 팩토리얼을 계산하고 있습니다.
그리고 이렇게 정의된 fac 함수를 호출하고 있습니다. {fac 10}은 n에 10을 전달하여 팩토리얼을 계산하라는 의미입니다.
{with {fac {fun {n}
{if0 n
1
{* n {fac {- n 1}}}}}}
{fac 10}
메시지 해석:
"⇒ free identifier 'fac'!": "⇒"는 '다음에 주어진 조건에 따라 결과가 나온다'는 의미를 가지며, 여기서는 '오류 메시지가 나온다'는 의미입니다.
"free identifier 'fac'"는 "자유 식별자 'fac'"를 의미합니다. 이 부분은 'fac'라는 변수나 함수가 이전에 정의되지 않았다는 것을 나타냅니다.
"Doesn't work: with does not support recursive definitions.": with 구문 내에서 변수를 재귀적으로 정의할 수 없다는 것을 나타냅니다.
"Still, at the point what we call fac, obviously we have a binding id fac for fac…": 여기서는 "우리가 'fac'라고 부르는 지점에서 분명히 'fac'에 대한 바인딩이 있다"는 의미입니다. 이 부분은 'fac'라는 변수가 여전히 정의되어 있다는 것을 언급하고 있습니다.
"… so pass {fac 10} as an argument!": "… 그래서 {fac 10}을 인자로 전달하십시오!"라는 의미입니다. 이 부분은 'fac'를 호출할 때 인자로 전달하라는 것을 나타냅니다.
결론:
이 오류 메시지는 with 구문 내에서 재귀적으로 변수를 정의하려고 했기 때문에 발생한 것입니다. with 구문은 재귀적인 정의를 지원하지 않습니다. 따라서 이를 해결하기 위해서는 'fac'를 미리 정의하고 이를 with 구문으로 감싸거나, with 구문 안에서 'fac'를 호출할 때 인자로 전달해야 합니다.
{with {facX {fun {facY n}
{if0 n
1
{* n {facY facY {- n 1}}}}}
{facX facX 10}}이렇게 하면 free identifier이슈를 피할 수 있다.
{with {fac
{fun {n}
{with {facX {fun {facY n}
{if0 n
1
{* n {facY facY {- n 1}}}}}}
{facX facX n}}}}
{fac 10}}여기서 with 구문이 사용되는 이유는 변수의 범위(scope)와 관련이 있습니다. with 구문은 특정 표현식의 실행 범위를 한정하여 변수를 정의하고 사용할 수 있게 합니다.
변수 fac는 함수를 정의할 때와 호출할 때 두 번 사용되고 있습니다. 첫 번째 fac는 전체 함수의 이름으로 사용되며, 두 번째 fac는 내부적으로 사용되는 재귀 함수의 이름입니다.
구체적으로 이해하기 위해 코드를 단계별로 분석해보겠습니다.
-
with 구문을 사용하여 fac이라는 변수를 정의합니다.
-
fac은 재귀적으로 팩토리얼을 계산하는 함수입니다. 함수 내부에서 facX라는 변수를 정의하여 내부에서 사용합니다.
-
facX는 또 다른 함수를 정의하고 있습니다. 이 함수는 facY라는 변수를 사용하여 재귀적으로 팩토리얼을 계산합니다.
-
{facX facX n} 부분은 facX 함수를 호출하고 있습니다. 이때 facX 함수 자체를 인자로 넘겨줍니다. 이렇게 하면 내부에서 facX를 facY로 사용할 수 있게 됩니다.
이 구조를 통해 재귀적으로 팩토리얼을 계산할 수 있습니다. with 구문을 사용하여 변수의 범위를 제한하고, 내부적으로 필요한 함수들을 정의하여 사용할 수 있게 되었습니다.
{with {f {fun {x y z} {+ z {+ y x}}}}
{f 1 2 3 }}
⇒ Rewrite this using a function only with one parameter?
{with {f {fun {x}
{fun {y}
{fun {z}
{+ z {+ y x}}}}}}
{{f 1} 2} 3}
{with {fac
{with {facX
{fun {facY}
{with {fac {facY facY}}
{fun {n}
{if0 n
1
{* n {fac {- n 1}}}}}}}}
{facX facX}}}
{fac 10}
-
문제의 원인: facX 함수 내에서 {fac {facY facY}} 부분이 문제입니다. 이 부분은 facY 함수를 두 번 호출하는데, 이는 무한 루프로 이어질 수 있습니다.
-
facY 함수는 facY 함수를 호출합니다. 이렇게 되면 facY 함수가 계속해서 자기 자신을 호출하게 되어 무한 루프가 발생합니다.
-
해결 방법: 이러한 무한 루프를 방지하려면 재귀 호출을 제어해야 합니다. 일반적으로 재귀 함수에서는 종료 조건을 명시하여 재귀 호출을 중단시킵니다. 이를테면, if0를 사용하여 n이 0일 때 종료하도록 할 수 있습니다.
-
또는 함수를 호출할 때, 적절한 인자를 전달하여 무한 재귀를 피할 수 있습니다. 예를 들어, facX를 호출할 때 어떤 값을 전달하면 됩니다.
전체 코드를 수정하면 다음과 같을 것입니다:
;전
{with {fac
{with {facX
{fun {facY}
{with {fac {facY facY}}
{fun {n} -
{if0 n
1
{* n {fac {- n 1}}}}}}}}
{facX facX}}}
{fac 10}
;후
{with {fac
{with {facX
{fun {facY}
{with {fac {fun {n} -> 수정된 부분
{if0 n
1
{* n {fac {- n 1}}}}}}
{fun {n} -> 수정된 부분
{fac {facY facY} n}}}}}} -> 수정된 부분
{fac 10}
