다음과 같은 Sequence를 이행한다고 생각해보자. 어느 순간, 수학적으로 문제가 발생한다. Interpreter는 Substitution을 한 번의 with 를 수행할 때마다 시행되어야 한다. 이것은 전체적으로 느려지는 결과를 나타내게 된다. 만약 프로그램의 크기가 N이라고 한다면 각각의 Substitution을 더하게 되면 시간 복잡도는 O(n^2)가 된다. 굉장히 알고리즘적으로 좋지 않음을 알 수 있을 것이다.
그렇다면 어떻게 연산량을 줄일 수 있을까? 여기서 Deferred Substitution 개념이 나오게 된다. 구체적으로 살펴보자. 초기에 Substitution이 발생하지 않으면 저장 공간은 비어있는 상태가 된다. 매순간 우리가 Substituion을 하게 될 때 우리는 저장공간을 하나 더 늘리게 되고 Identifier의 이름과 값을 기록하거나 Substitution을 해야 하는 표현들을 기록해야 할 것이다. 계속해서 실제적으로 Substitution을 수행하지 않은 채로 진행하게 되는 것이다.
이러한 방법은 초반에 배웠던 Key Invariant라는 개념(Interpreter가 만나게 되는 모든 identifier를 Substitution에 의해 대체하게 되는 기능을 의미)을 무시하게 된다. 왜냐하면 더 이상 Substitution을 사용하지 않기 때문이다. 우리는 Interpretation을 하는 동안 Bound Identifier를 만나게 될 것이다.
함수 이름은 "Deferred Substituion"을 의미한다. 이는 2개의 형식적인 구조를 띄는 데, 첫 번째로 비어 있을 때는 mySub, 두 번째로, 비어 있지 않는 경우 aSub라는 구조로 표현한다. 후자의 경우 3번째 field가 나타내는 DefrdSub에 대하여 저장공간의 나머지를 참조하게 된다.
Interpreter는 Expression을 해석하기 위하여 추가적인 저장 공간을 사용하게 된다. 그러므로 다음과 같은 수식을 따르게 된다.
또한 이를 적용하기 위해서 저장 공간에서 Identifier의 Value를 참조하기 위한 Look up 함수가 필요하다.
이는 이전 DefrdSub의 3번째 파라미터로 사용된 DefrdSub의 Value를 찾기 위한 함수로 보인다. Empty의 경우 Error 메시지를 출력하게 되고 Empty의 경우가 아니라면 Bound-name과 DefrdSub 함수에서 받았던 Identifer의 이름과 동일한 경우 Binding Identifier와 Bound Identifier의 파라미터 이름이 동일한 경우이다. 그렇기 때문에 bound-value를 반환하게 되고 만약 동일하지 않다면 rest-ds에 대하여 look-up 함수를 적용하여 다시 값을 참조하게 된다.
with, identifier, application 라는 3개의 절이 바뀌게 된다. Application은 저장 공간의 Identifier의 Value를 참조하는 Look-up의 기능을 수행하게 된다. "with"의 기능은 Identifier의 범위에 있는 현재의 DS의 Value를 해석하는 것이다. 마지막으로 Application의 기능은 비슷하게, 함수의 Body를 해석하는 것인데 범위는 함수를 정의할 때 사용되는 파라미터로부터 함수를 호출할 때 실제로 사용하는 값을 적용하는 것으로 사실 Function call에 해당한다고 할 수 있다.
다음과 같은 표현을 list of function Definition으로 변경을 해보자.
이를 변경하면 다음과 같다.
f라는 함수의 이름을 가지고 p라는 파라미터가 존재하며 n이라는 Actual Parameter의 값을 반환하게 된다. 다음 보여지는 식과 동일한 기능을 수행한다.
위의 보이는 식은 5 라는 값을 Return 할 것이다. 이것이 과연 정확한 정답일까? 가능한 답은 맞지만 이는 몇몇 언어에 적용되는 Interpreter일 것이다. 하지만 우리는 해당 질문에 답을 얻기 위한 더 정확한 방법을 갖고 있다.
Interpreter를 구현하는 것은 Substitution을 좀 더 효율적으로 구현하기 위한 방법임을 기억해야 한다. 우리는 이 기능이 구현하면서 프로그램의 의미가 변경되는 것을 원치 않는다. "Referenece Implementation"은 명백하게 Substitution 기능을 수행한다. 만약 프로그램이 진짜로 가지고 있는 Value를 알기를 원한다면 우리는 어떻게 구현되어 있는 지를 살펴볼 필요가 있다.
Substituion을 기반으로 하는 Interpreter는 이 프로그램에서 어떤 기능을 하는가? 이 프로그램은 Unbound Identifier를 가지고 있다. (N이라고 지정하자) 그렇다면 우리는 Deferred Substituion을 버그로 간주해야 한다.
만약 이 새로운 Interpreter가 Substitution 대신 버그라고 한다면, 해당 프로그램이 어떤 기능을 수행해야 하는지 생각해 볼 필요가 있다.