모든 명령형 기능에 대해 동일한 성능이나 지침을 갖춘 기능적 대응이 있습니까?

Question

현재 C/C++와 동일한 성능을 얻을 수 있는 함수형 언어에 대해 배운 적이 없습니다.그리고 Scala 및 Rust와 같이 명령형 프로그래밍보다 함수형 프로그래밍을 선호하는 일부 언어는 효율성을 높이기 위해 명령형 방식을 사용하여 라이브러리 기능을 구현한다는 것을 배웠습니다.

따라서 명령형 명령을 실행하는 오늘날의 컴퓨터에서 이것이 컴파일러 또는 함수형 프로그래밍 자체의 제한 사항입니까? 질문이 있습니다.C/C++/Rust/어셈블리와 같은 GC가 없는 언어나 Java와 같은 GC가 있는 언어에서 부작용이 없는 모든 명령형 함수에 대해 Haskell, Scala 등에 순수 기능 대응이 있습니까?꼬리 재귀, 게으름, 정적 분석, 형식 검증 등 내가 모르는 것은 무엇입니까?

나는 λ-computable과 Turing computable의 동등성을 알고 있지만 온라인에서 이 질문에 대한 답을 찾을 수 없었습니다.있다면 컴파일러 예제나 증명을 공유해 주세요.그렇지 않다면 그 이유를 설명하고 반대 예를 보여주십시오.아니면 이것은 사소하지 않은 공개 질문입니까?

---

제안한 보충 편집 안드레이 바우어:

보다 구체적으로 이 질문에 대해 생각하게 된 두 가지 예가 있습니다.

예를 들어 꼬리 재귀 및 누산기는 다음을 사용하여 명령형 구현과 동일하도록 일부 재귀 함수의 성능을 향상시킬 수 있습니다. for.어떤 경우에는 동일한 지침이 있을 수도 있습니다.

또 다른 예는 Haskell의 게으름에 관한 것입니다.게으름은 데이터 구조의 불필요한 복사를 방지하고 성능을 향상시키는 데 도움이 될 수 있습니다.그러나 게으름으로 인해 포장, 마감 등이 발생합니다.런타임에 여전히 그런 것이 없는 명령형 구현만큼 빠르게 프로그램을 만들 수는 없습니다.그래서 컴파일 중에 런타임 전에 이러한 것들을 정적으로 제거할 수 있는지 궁금합니다.

제안한 보충 편집 니어루:

질문은 다음과 같이 기술될 수도 있습니다.최적화된 컴파일러와 함께 순수 함수형 프로그래밍과 명령형 프로그래밍을 모두 지원하는 언어가 있습니까? 명령형으로 구현된 부작용이 없는 모든 함수를 성능 비용 없이 순수하게 기능적으로 구현된 함수로 대체하거나 심지어 동일한 언어로 컴파일할 수도 있습니다. 지침?

Answer 1

1. 성능은 언어의 속성이 아니라 언어 내 특정 프로그램의 속성입니다.일부 언어는 어떤 작업에서는 매우 빠르지만 다른 작업에서는 느릴 수도 있습니다.

   예를 들어, Chez-Scheme은 때때로 C와 비슷한 성능을 찾을 수 있습니다. 이는 언어가 더 효율적이기 때문이 아니라 프로그래머가 C에서 자주 사용하는 방어 방법이 체계에서 덜 필요하기 때문입니다.

   마찬가지로 Haskell이 매우 효율적인 병렬성이나 동시성을 수행할 수 있는 경우가 있습니다. 이는 C보다 빠르기 때문이 아니라 언어의 불변성 보장으로 프로그래머가 잠금 및 기타 동기화 기술과 같은 것을 피할 수 있기 때문입니다.

   그리고 성능은 구현마다 다릅니다.C 인터프리터를 직접 작성할 수는 있지만 확실히 빠르지는 않습니다.C는 빠르지 않지만 GCC와 Clang은 빠릅니다.

2. "기능적" 언어로 간주되는 것은 무엇입니까?모든 실용적인 함수형 언어에는 변경 가능한 상태를 위한 몇 가지 기능이 있습니다.OCaml, Haskell, Scala, Lisp, Scheme 등꼬리 재귀는 for 루프 내부의 돌연변이와 거의 동일한 것을 제공합니다.그러나 이것이 충분하지 않은 경우 함수형 언어는 프로그래머에게 변경 가능한 상태에 대한 액세스를 제공합니다.Haskell의 경우 이는 유형 시스템에 의해 제어되므로 암시적 변경 가능 상태, 그러나 Haskell에서는 돌연변이가 매우 많이 허용되고 심지어 권장됩니다.하스켈 코드를 보면 어디에서나 IO 모나드를 볼 수 있습니다.마찬가지로 ML 언어는 유형을 구별합니다. T 그리고 ref T, 따라서 변수가 변경 가능한지 여부를 유형으로 알 수 있습니다.

3. Rice의 정리 덕분에 "최적의" 컴파일러는 없습니다.명령형이든 기능형이든 모든 컴파일러는 "최선의 노력"을 기울입니다. 즉, 코드를 최적화하기 위해 보수적인 근사치를 사용합니다.

   최적의 컴파일러가 있다면 모든 프로그램은 항상 가장 효율적인 지침을 사용하여 실행되며 문제를 어떤 언어로 코딩했는지는 중요하지 않을 것입니다.문제를 계산하는 최적의 명령 순서는 소스 언어에 의존하지 않습니다.하지만 이것이 있다면 이 컴파일러는 정지하지 않는 모든 프로그램을 다음과 같이 컴파일할 것입니다. while(0), 이는 정지되지 않는 프로그램을 감지할 수 있다는 의미입니다. 이는 불가능합니다.

4. Turing Machines 및 람다 미적분학의 경우 Turing Machines용 람다 미적분학 인터프리터를 구현하는 것은 매우 사소한 일이라고 생각합니다. 점근적으로 만능 튜링 기계와 동일하다.Big-O 복잡성은 사람들이 "기능적 언어가 느리다"라고 말할 때 의미하는 것이 아닙니다.일반적으로 지속적인 오버헤드에 대해 이야기하는데 이는 매우 다릅니다.이를 수학적으로 모델링할 수 있는 좋은 방법이 없기 때문에 일반적으로 정확한 성능을 측정하기 위해 실험을 사용하게 됩니다.