QUOTE

아포스트로피 하나가 평가를 막습니다

Scheme 인터프리터 EVAL은 함수를 적용하기 전에 매개변수를 언제나 먼저 평가합니다. 리스트를 데이터로 넘기려면 평가를 막아야 합니다. QUOTE는 받은 것을 평가하지 않고 그대로 돌려줍니다.

인터프리터는 1강에서 본, 소스를 해석해 그 자리에서 실행하는 프로그램입니다.

CAR · CDR · CONS

첫 칸을 떼고, 나머지를 남기고, 앞에 붙입니다

5강에서 본 리스트 함수 셋입니다. CAR는 첫 요소를, CDR는 첫 요소를 뺀 나머지를 돌려줍니다. CONS는 요소 하나를 리스트 앞에 붙입니다. 리스트를 첫 칸과 나머지로 나누는 것이 재귀의 재료입니다.

재귀로 훑기

첫 칸만 보고, 나머지는 다시 맡깁니다

리스트에 어떤 원자가 들어 있는지 알아보는 함수 member를 생각해 봅니다. 첫 요소와 같으면 참입니다. 다르면 나머지 리스트에서 같은 일을 다시 합니다. 리스트가 비면 거짓입니다.

A, B, C와 찾는 원자 C는 예시입니다.

member

세 갈래가 그대로 코드가 됩니다

(member atm a_list)는 원자 atm이 리스트 a_list에 있으면 #T, 없으면 #F를 돌려줍니다. 마지막 갈래에서 member가 자기 자신을 부릅니다. 반복문은 어디에도 없습니다.

NULL?은 빈 리스트인지, EQ?는 두 원자가 같은지 묻는 함수입니다.

호출이 펼쳐진다

아래로 펼쳐졌다가 답이 위로 돌아옵니다

(member 'C '(A B C))를 평가하면 호출이 세 번 일어납니다. 부를 때마다 리스트가 한 칸씩 짧아지고, 셋째 호출에서 #T가 나옵니다. 그 값이 그대로 위로 돌아와 전체의 답이 됩니다.

②와 ③은 앞 장에서 본 갈래의 번호입니다.

스택

돌아와서 할 일이 남으면 칸이 쌓입니다

재귀는 호출마다 스택(함수가 불리면 쌓이고 끝나면 걷히는 칸)에 자리를 잡습니다. 부른 함수가 돌아온 뒤에 곱셈 같은 할 일이 남아 있으면, 그때까지 칸을 지켜야 해서 스택이 쌓입니다.

2편에서 본 팩토리얼 fact로 든 예시입니다. ?는 아직 돌아오지 않은 값입니다.

꼬리 재귀

꼬리 재귀는 한 칸에서 값만 바뀌며 돕니다

재귀 호출이 함수의 마지막 연산이면 꼬리 재귀(tail recursion)입니다. member가 그렇습니다. 돌아와서 할 일이 없으니 컴파일러(소스를 기계어로 번역하는 프로그램)가 자동으로 반복으로 바꿀 수 있고, 그러면 더 빠릅니다. Scheme은 한 걸음 더 나아가, 언어 정의가 모든 꼬리 재귀를 반복으로 바꾸도록 요구합니다.