충남대학교 컴퓨터공학과 이성호 교수님의 "프로그래밍 언어 개론" 강의를 필기한 내용입니다.
다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.
재귀문 최적화
- 함수형 언어에서는 알고리즘적으로 최적화할 수 있는 방법이 많지 않다
- 대신 이런 최적화는 컴파일러에서 수행하므로 우리가 할 것은 컴파일러가 최적화를 잘 해줄 수 있는 방향으로 코드를 짜야 된다
- OCaml에서 변수는 불변하게 선언되는데 이것이 최적화에 아주 많은 도움이 된단다
Tail call optimization
- 함수가 하나 더 실행되어 callee가 하나 생성되면 이전의 caller를 지워버리는 기법
- 메모리를 추가적으로 먹지 않으므로 메모리 관리에 유용하다
방법
- 재귀를 호출할때 함수의 맨 끝에서 호출하면 된다
- 재귀의 경우 다시 돌아와야 되는 이유는 돌아온 이후에 코드가 더 있어서 작업을 더 해줘야 하기 때문
- 하지만 돌아온 이후에 할일이 없어 바로 caller가 종료되는 구조라면 굳이 돌아오지 않아도 된다
- 따라서 맘편하게 caller를 메모리에서 지워도 되므로 재귀호출시에 메모리를 더 먹지 않는다
- 이런식으로 굴러가게 하는 것을 tail call optimization이라고 하는 것
활용 - 누산기(Accumulator)이용
- 결과값을 다 더해야 하는 함수의 경우 재귀 호출 종료 후 더하는게 아니고 매개 변수 acc를 하나 추가해서 값을 누적하는 작업도 함수 내에서 수행하게 함
- 하지만 매개변수를 추가해야 되므로 함수의 구조가 바뀌게 된다
- 이것을 방지하는 방법은 구조가 바뀐 함수를 기존 구조의 함수로 포장지를 싸듯이 감싸는 것이다.
- 즉, 기존 구조의 함수 내에 매개변수가 추가된 함수를 local하게 넣어서 기존 구조 함수는 재귀적으로 실행되지 않고 안에 들어있는 함수가 재귀적으로 호출되어 tail call적으로 연산을 수행함
- 이렇게 되면 함수의 구조도 바뀌지 않고 메모리 사용도 현저히 줄어들므로 꿩먹고 알먹고 이다
- 이러한 구조를 wrapping한다