F # 및 Ocaml (및 기타 언어)의 함수가 기본적으로 재귀 적이 아닌 이유는 무엇입니까?
즉, 언어 디자이너 rec
가 다음과 같은 선언에 명시 적으로 입력하는 것이 좋은 생각이라고 결정한 이유는 무엇입니까?
let rec foo ... = ...
기본적으로 함수 재귀 기능을 제공하지 않습니까? 명시 적 rec
구성 이 필요한 이유는 무엇 입니까?
답변
원래 ML의 프랑스와 영국 후손은 다른 선택을했으며 그들의 선택은 수십 년 동안 현대적인 변형으로 이어졌습니다. 그래서 이것은 단지 유산이지만 이러한 언어의 관용구에 영향을 미칩니다.
프랑스어 CAML 계열 언어 (OCML 포함)에서는 함수가 기본적으로 재귀 적이 지 않습니다. 이 선택을 통해 let
새 정의의 본문 내에서 이전 정의를 참조 할 수 있으므로 해당 언어에서 사용하는 함수 (및 변수) 정의를 쉽게 대체 할 수 있습니다. F #은 OCaml에서이 구문을 상속했습니다.
예를 들어, p
OCaml에서 시퀀스의 Shannon 엔트로피를 계산할 때 함수를 대체합니다 .
let shannon fold p =
let p x = p x *. log(p x) /. log 2.0 in
let p t x = t +. p x in
-. fold p 0.0
p
고차 shannon
함수에 대한 인수 가 p
본문의 첫 번째 줄에서 다른 인수 로 대체되고 본문 p
의 두 번째 줄에서 다른 인수 가 어떻게 대체 되는지 확인하십시오 .
반대로, ML 계열 언어의 영국 SML 분기는 다른 선택을했으며 SML의 fun
바인딩 된 함수는 기본적으로 재귀 적입니다. 대부분의 함수 정의에서 함수 이름의 이전 바인딩에 액세스 할 필요가없는 경우 코드가 더 간단 해집니다. 그러나, 대체 된 기능은 (다른 이름을 사용하여 만들어진 f1
, f2
범위 및 오염을 가능하게하는 등)에 실수 함수 잘못된 “버전”호출한다. 그리고 이제 암시 적으로 재귀 적 fun
바운드 함수와 비재 귀적 바운드 함수 사이에 불일치가 val
있습니다.
Haskell은 정의를 순수로 제한하여 정의 간의 종속성을 추론 할 수 있습니다. 이것은 장난감 샘플을 더 단순하게 보이게하지만 다른 곳에서는 엄청난 비용이 듭니다.
Ganesh와 Eddie가 제공 한 답변은 붉은 청어입니다. 그들은 let rec ... and ...
유형 변수가 일반화 될 때 영향을주기 때문에 함수 그룹을 거인 안에 배치 할 수없는 이유를 설명 했습니다. 이것은 rec
SML의 기본값 과 관련 이 없지만 OCaml은 아닙니다.
답변
를 명시 적으로 사용하는 한 가지 중요한 이유는 rec
(다양한 방식으로 변경되고 확장되었지만) 모든 정적으로 형식화 된 함수형 프로그래밍 언어의 기초가되는 Hindley-Milner 형식 추론과 관련이 있습니다.
당신이 정의가있는 경우 let f x = x
, 당신은 유형을 가지고 기대 'a -> 'a
와 다른에 적용 할 수 'a
서로 다른 지점에서 유형. 하지만 똑같이를 작성 하면 나머지 본문에서 로 취급 될 let g x = (x + 1) + ...
것으로 예상 x
됩니다 .int
g
Hindley-Milner 추론이 이러한 구분을 다루는 방식은 명시 적 일반화 단계를 통하는 것 입니다. 프로그램을 처리 할 때 특정 지점에서 유형 시스템은 중지하고 “좋아요, 이러한 정의의 유형이이 지점에서 일반화 될 것입니다. 따라서 누군가이를 사용할 때 해당 유형의 모든 자유 유형 변수가 새로 인스턴스화 됩니다. 이 정의의 다른 사용을 방해하지 않습니다. “
이 일반화를 수행하는 합리적인 장소는 상호 재귀적인 함수 집합을 확인한 후입니다. 이전에는 너무 많이 일반화되어 유형이 실제로 충돌 할 수있는 상황이 발생합니다. 나중에는 너무 적게 일반화하여 여러 유형 인스턴스화에 사용할 수없는 정의를 만들 것입니다.
따라서 유형 검사기가 상호 재귀적인 정의 집합에 대해 알아야하므로 무엇을 할 수 있습니까? 한 가지 가능성은 범위의 모든 정의에 대한 종속성 분석을 수행하고 가능한 가장 작은 그룹으로 재정렬하는 것입니다. Haskell은 실제로이 작업을 수행하지만 제한없는 부작용이있는 F # (및 OCaml 및 SML)과 같은 언어에서는 부작용도 재정렬 할 수 있기 때문에 이것은 나쁜 생각입니다. 따라서 대신 사용자에게 상호 재귀적인 정의를 명시 적으로 표시하고 확장하여 일반화해야하는 위치를 표시하도록 요청합니다.
답변
이것이 좋은 아이디어가되는 두 가지 주요 이유가 있습니다.
첫째, 재귀 적 정의를 활성화하면 동일한 이름 값의 이전 바인딩을 참조 할 수 없습니다. 이것은 기존 모듈을 확장하는 것과 같은 작업을 할 때 종종 유용한 관용구입니다.
둘째, 재귀 값, 특히 상호 재귀 값 세트는 순서대로 진행되는 정의이며, 각각의 새로운 정의는 이미 정의 된 것 위에 구축됩니다. 이러한 코드를 읽을 때 명시 적으로 재귀로 표시된 정의를 제외하고는 새 정의가 이전 정의 만 참조 할 수 있다는 보장을받는 것이 좋습니다.
답변
몇 가지 추측 :
let
함수뿐만 아니라 다른 일반 값을 바인딩하는데도 사용됩니다. 대부분의 값 형식은 재귀 적이 될 수 없습니다. 특정 형태의 재귀 값 (예 : 함수, 지연 표현식 등)이 허용되므로이를 나타 내기 위해 명시적인 구문이 필요합니다.- 비 재귀 함수를 최적화하는 것이 더 쉬울 수 있습니다.
- 재귀 함수를 만들 때 생성 된 클로저에는 함수 자체를 가리키는 항목이 포함되어야합니다 (따라서 함수가 자신을 재귀 적으로 호출 할 수 있음). 이는 비 재귀 클로저보다 재귀 클로저를 더 복잡하게 만듭니다. 따라서 재귀가 필요하지 않을 때 더 간단한 비 재귀 클로저를 만들 수 있으면 좋을 것입니다.
- 이전에 정의 된 함수 또는 동일한 이름의 값으로 함수를 정의 할 수 있습니다. 나쁜 습관이라고 생각하지만
- 추가 안전? 의도 한대로하고 있는지 확인합니다. 예를 들어 재귀 적이 지 않지만 실수로 함수 자체와 동일한 이름을 가진 이름을 함수 내에서 실수로 사용한 경우 (이전에 이름이 정의되지 않은 한) 불평 할 가능성이 큽니다.
- 이
let
구성은let
Lisp 및 Scheme 의 구성 과 유사합니다 . 비재 귀적입니다.letrec
Scheme에는 재귀를위한 별도의 구조가 있습니다.
답변
이것을 감안할 때 :
let f x = ... and g y = ...;;
비교:
let f a = f (g a)
이것으로 :
let rec f a = f (g a)
전자 는에 적용한 결과에 f
이전에 정의 된 내용을 적용하도록 재정의 합니다 . 후자 는 일반적으로 ML 변형에서 원하는 것이 아닌에 영원히 적용 하도록 재정의 합니다 .f
g
a
f
g
a
즉, 언어 디자이너 스타일입니다. 그냥 해.
답변
그것의 큰 부분은 프로그래머가 로컬 범위의 복잡성을 더 잘 제어 할 수 있다는 것입니다. 의 스펙트럼 let
, let*
그리고 let rec
제공하는 전력 및 비용 모두의 증가 수준. let*
그리고 let rec
본질적으로 간단한 버전을 중첩 let
그래서 하나가 더 비싼 중 하나를 사용하여. 이 등급을 사용하면 당면한 작업에 필요한 수준을 선택할 수 있으므로 프로그램 최적화를 세부적으로 관리 할 수 있습니다. 재귀 나 이전 바인딩을 참조 할 수있는 기능이 필요하지 않은 경우 약간의 성능을 절약 할 수있는 간단한 방법으로 대체 할 수 있습니다.
Scheme의 등급이 매겨진 동등 조건 자와 유사합니다. (예 eq?
: eqv?
및 equal?
)