푸나그 문제

컴퓨터 과학에서 funarg 문제(기능 인수 문제)는 함수의 스택 기반 메모리 할당을 사용하기 위해 프로그래밍 언어 구현에서 1종 기능(일종 객체로서의 기능)을 구현하는 데 어려움이 있는 것을 말한다.

난이도는 내포함수의 본체가 함수가 정의된 환경에서 정의된 식별자를 직접(즉, 인수합병(argain passing)하지 않고 함수 호출의 환경에서 직접 참조하는 경우에만 발생한다.^[1]표준 결의안은 그러한 언급을 금지하거나 폐쇄를 만드는 것이다.^[2]

미묘하게 다른 두 가지 버전의 화난 문제가 있다.위쪽의 funarg 문제는 함수 호출에서 함수를 반환(또는 "위로" 전송)함으로써 발생한다.아래쪽의 funarg 문제는 함수를 다른 함수 호출에 매개 변수로 전달함으로써 발생한다.

위쪽의 화기 문제

일반적인 프로그램 실행 중에 한 기능이 다른 기능을 호출할 때 호출자의 로컬 상태(파라미터 및 로컬 변수 포함)를 보존해야 캘리어가 반환된 후 실행이 진행될 수 있다.컴파일된 대부분의 프로그램에서 이 로컬 상태는 스택 프레임 또는 활성화 기록이라고 하는 데이터 구조로 호출 스택에 저장된다.이 스택 프레임은 다른 함수를 호출하기 위한 전주곡으로 푸시되거나 할당되며, 다른 함수가 호출을 수행한 함수로 복귀할 때 펑크나 할당 해제된다.위쪽의 funarg 문제는 호출함수가 해당 함수가 반환된 후 호출함수의 상태를 참조할 때 발생한다.따라서 호출된 함수의 상태 변수를 포함하는 스택 프레임은 함수가 반환될 때 스택 기반 함수 호출 패러다임을 위반하여 할당을 해제해서는 안 된다.

위쪽의 funarg 문제에 대한 한 가지 해결책은 스택 대신 힙에서 모든 활성화 레코드를 할당하고 더 이상 필요하지 않을 때 할당을 해제하기 위해 어떤 형태의 가비지 수집 또는 참조 카운트에 의존하는 것이다.힙에 대한 활성화 레코드의 관리는 역사적으로 스택에 비해 효율성이 떨어지는 것으로 인식되어 왔으며(이는^[3] 부분적으로 모순되어 있지만) 상당한 구현 복잡성을 야기하는 것으로 인식되어 왔다.일반적인 프로그램의 대부분의 기능(기능적 프로그래밍 언어의 프로그램에는 해당되지 않음)은 위로 올라가는 푸나그를 생성하지 않으며, 그 구현과 관련된 잠재적 오버헤드에 대한 우려를 더한다.게다가, 이러한 접근법은 쓰레기 수집을 지원하지 않는 언어에서는 정말로 어렵다.

일부 효율 마인드를 가진 컴파일러는 정적 프로그램 분석을 통해 컴파일러가 위쪽의 funarg를 생성하지 않는다고 추론할 수 있는 경우 함수에 대한 활성화 레코드를 스택에서 할당하는 하이브리드 접근방식을 채택한다.그렇지 않으면 활성화 레코드가 힙에서 할당된다.

또 다른 해결책은 단순히 폐쇄가 만들어질 때 변수의 값을 폐쇄에 복사하는 것이다.이렇게 되면 국가가 더 이상 폐쇄 간에 공유되지 않기 때문에 변이 가능한 변수의 경우 다른 행동을 일으킬 것이다.그러나 변수가 일정하다는 것이 알려지면, 이 접근법은 동등할 것이다.ML 언어는 이러한 언어의 변수가 값(즉, 변수를 변경할 수 없음)에 구속되기 때문에 이러한 접근방식을 취한다.Java는 또한 익명 클래스에 관해서도 이러한 접근법을 취하는데, 이는 단지 한 사람이 주변 범위에 있는 변수를 언급할 수 있도록 허용하기 때문이다.final(즉, 상수).

어떤 언어들은 프로그래머가 두 행동 중 하나를 명시적으로 선택할 수 있게 한다.PHP 5.3의 익명 함수는 다음을 사용하여 폐쇄에 포함할 변수를 지정해야 한다.use ()절; 변수가 참조로 나열되는 경우, 원래 변수에 대한 참조를 포함하고, 그렇지 않으면 값을 전달한다.Apple의 Blocks 익명함수에서 캡처된 로컬 변수는 기본적으로 값에 의해 캡처된다. 폐쇄 사이에 상태를 공유하거나 폐쇄와 외부 범위 사이에 상태를 공유하려면 해당 변수를 다음과 같이 선언해야 한다.__block수정자, 즉 해당 변수가 힙에 할당되는 경우.

예

다음과 같은 하스켈 유사 유사성 부호는 함수 구성을 정의한다.은 함수 구성을 정의한다.

구성 f g = λx → f (g x)

λ새로운 함수를 구성하기 위한 연산자인데, 이 경우 하나의 인수가 있다.x, 그리고 처음 적용한 결과를 반환한다.g로x, 그런 다음 적용f거기에이 λ 함수는 함수를 운반한다.f그리고g내부 상태로서 (또는 이들을 위한 포인터)

이 경우 작성 함수가 매개변수 변수를 할당하는 경우 문제가 발생한다.f그리고g겹겹이 쌓여언제compose반환, 다음을 포함하는 스택 프레임f그리고g버림받다 버려진다.내부 기능인 경우λx접근 시도g그것은 버려진 기억 영역에 접근할 것이다.

아래쪽으로 푸나그 문제

아래쪽의 funarg는 기능이 실제로 실행되지 않을 때 기능의 상태를 나타낼 수도 있다.그러나, 정의상, 아래쪽의 푸나르의 존재는 그것을 생성하는 기능의 실행에는 포함되어 있기 때문에, 함수의 스택 프레임은 여전히 스택에 저장될 수 있다.그럼에도 불구하고, 아래쪽의 푸나그의 존재는 프로그램 상태에 대한 인간과 기계의 추론을 복잡하게 만들 수 있는 폐쇄와 스택 프레임의 나무 구조를 암시한다.

하향식 funarg 문제는 연속 패스 스타일로 작성된 테일 콜과 코드의 효율적인 컴파일을 복잡하게 만든다.이러한 특별한 경우에 프로그래머의 의도는 (보통) 기능이 제한된 스택 공간에서 실행되기 때문에, "더 빠른" 행동은 실제로 바람직하지 않을 수 있다.

실제적 함의

역사적으로, 상향식 문제는 더 어려운 것으로 증명되었다.예를 들어, Pascal 프로그래밍 언어는 함수를 논쟁으로 전달하지만 결과로는 반환되지 않는 것을 허용한다. 따라서 Pascal의 구현은 아래쪽의 funarg 문제를 다루기 위해서가 아니라 위쪽의 funarg 문제를 다루기 위해서 필요하다.Modula-2와 Oberon 프로그래밍 언어(Pascal의 설명)는 파라미터와 반환값으로서의 기능을 모두 허용하지만, 할당된 함수는 내포된 함수가 아닐 수 있다.C 프로그래밍 언어는 역사적으로 함수 정의가 중첩되지 않도록 함으로써 funarg 문제의 주요 난이도를 회피한다. 왜냐하면 모든 함수의 환경은 정적으로 할당된 전역 변수와 함수만을 포함하는 동일하기 때문이다. 함수의 코드에 대한 포인터는 함수를 완전히 설명한다.애플은 필요에 따라 스택에서 힙으로 클로져를 동적으로 이동시켜 위쪽의 푸나그 문제를 해결하는 C에 대해 클로즈 구문을 제안하고 구현했다.^{[citation needed]}자바 프로그래밍 언어는 익명 내부 및 로컬 클래스에서 중첩된 함수에 의해 사용되는 컨텍스트를 최종으로 선언하고 람다 표현에 의해 사용되는 컨텍스트를 효과적으로 최종으로 선언하도록 요구함으로써 그것을 다룬다.C#와 D에는 함수 포인터 및 관련 변수를 캡슐화하는 람다(closure)가 있다.

기능 언어에서 함수는 어느 곳에서도 통과할 수 있는 1등급 가치다.따라서, Scheme 또는 Standard ML의 구현은 위와 아래 모두의 funarg 문제를 다루어야 한다.이는 일반적으로 기능 값을 앞에서 설명한 힙할당 폐쇄로 표현함으로써 이루어진다.OCaml 컴파일러는 (프로그램 분석에 기반한) 하이브리드 기법을 채택하여 효율성을 극대화한다.^{[citation needed]}

참고 항목

• 폐쇄(컴퓨터 과학)
• 기능 프로그래밍
• 람다 미적분학
• 남자 또는 남자 테스트
• 이름 바인딩
• 참조 투명도
• 범위(프로그래밍)
• 스파게티 스택

참조

외부 링크

• 조셉 바이젠바움.1968년 "FUNARG 문제 설명"
• 조엘 모세."LISP에서 기능의 기능 또는 FUNARG 문제를 환경 문제라고 불러야 하는 이유".MIT AI 메모 199, 1970.
• 바인딩, 절차, 기능, 기능 프로그래밍 및 람다 미적분학