기능 해제
Defunctionalization프로그래밍 언어에서 기능 해제는 고차 함수를 제거하고 단일 1차 적용 함수로 대체하는 컴파일 시간 변환입니다.이 기술은 존 C에 의해 처음 기술되었다. 레이놀즈는 1972년 "고차 프로그래밍 언어를 위한 정의 통역자"라는 논문을 발표했다.레이놀즈의 관찰은 주어진 프로그램이 많은 함수 추상화만을 포함하고 있기 때문에 각 프로그램은 고유한 식별자에 의해 할당되고 대체될 수 있다는 것이었다.다음으로 프로그램 내의 모든 함수 애플리케이션은 함수 식별자를 첫 번째 인수로 하는 적용 함수에 대한 호출로 대체된다.적용 함수의 유일한 작업은 이 첫 번째 인수에 대해 디스패치한 후 나머지 인수에 대해 함수 식별자에 의해 나타나는 명령을 실행하는 것입니다.
이 기본 개념의 한 가지 복잡한 점은 함수 추상화가 자유 변수를 참조할 수 있다는 것입니다.이러한 상황에서 기능 해제는 폐쇄 변환(람다 리프팅)이 선행되어야 하며, 따라서 함수 추상화의 자유 변수가 적용하기 위한 추가 인수로 전달되어야 한다.또한 폐쇄가 퍼스트 클래스 값으로 지원되는 경우 데이터 구조를 생성하여 캡처된 바인딩을 나타낼 필요가 있습니다.
프로그램 내의 모든 함수 추상화에 대해 단일 적용 함수 디스패치를 하는 것이 아니라 각 함수 애플리케이션 사이트에서 호출할 수 있는 함수를 결정하기 위해 다양한 종류의 제어 흐름 분석(특정성 또는 유형 서명에 기초한 단순한 구별 포함)을 사용할 수 있으며, 특수한 적용 함수를 참조할 수 있다.ad. 대체적으로, 타겟 언어는 기능 포인터를 통한 간접 호출을 지원할 수 있으며, 이는 디스패치 기반 접근법보다 더 효율적이고 확장될 수 있습니다.
고차 함수 언어의 컴파일 기법으로 사용되는 것 외에, 역기능화는 통역자를 추상 기계로 기계적으로 변환하는 방법으로 (특히 Olivier Danvy와 공동 연구자들에 의해) 연구되어 왔다.기능 해제는 (폐쇄의 대안으로서) 함수 객체에 의해 함수를 나타내는 객체 지향 프로그래밍의 기법과도 관련이 있다.
예
다음은 올리비에 댄비가 하스켈에게 번역한 예입니다.
트리 데이터 유형 지정:
데이터. 트리 a = 잎 a 노드 (트리 a) (트리 a) 다음 프로그램의 기능을 해제합니다.
단점 :: a -> [a] -> [a] 단점 x xs = x : xs o :: (b -> c) -> (a -> b) -> a -> c o f g x = f (g x) 평평하게 하다 :: 트리 t -> [t] 평평하게 하다 t = 걸어. t [] 걸어. :: 트리 t -> [t] -> [t] 걸어. (잎 x) = 단점 x 걸어. (노드 t1 t2) = o (걸어. t1) (걸어. t2) 모든 고차 함수를 교체하여 기능을 해제합니다(이 경우,o고차함수)의 값을 가지는 것은,Lam데이터 타입을 직접 호출하는 대신apply데이터 유형을 해석하는 함수:
데이터. 램 a = 램콘 a 라모 (램 a) (램 a) 적용합니다. :: 램 a -> [a] -> [a] 적용합니다. (램콘 x) xs = x : xs 적용합니다. (라모 f1 f2) xs = 적용합니다. f1 (적용합니다. f2 xs) 단점 :: a -> 램 a 단점 x = 램콘 x o_default :: 램 a -> 램 a -> 램 a o_default f1 f2 = 라모 f1 f2 평탄화 :: 트리 t -> [t] 평탄화 t = 적용합니다. (워크_def t) [] 워크_def :: 트리 t -> 램 t 워크_def (잎 x) = 단점 x 워크_def (노드 t1 t2) = o_default (워크_def t1) (워크_def t2) 「 」를 참조해 주세요.
레퍼런스
- Reynolds, John (August 1972). "Definitional Interpreters for Higher-Order Programming Languages". Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717–740. doi:10.1145/800194.805852.
- Danvy, Olivier; Nielsen, Lasse R. (2001). "Defunctionalization at Work" (PDF). Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. pp. 162–174. doi:10.1145/773184.773202. (더 포괄적인 버전:기술 보고서 BRICS-RS-01-23)
- Danvy, Olivier; Millikin, Kevin R. (June 2009). "Refunctionalization at Work". Science of Computer Programming. 74 (8): 534–549. doi:10.1016/j.scico.2007.10.007. (테크니컬 리포트 BRICS-RS-07-7로도 이용 가능)
