Skip to content

Latest commit

 

History

History
683 lines (663 loc) · 81.2 KB

functional_programming.md

File metadata and controls

683 lines (663 loc) · 81.2 KB

Functional Programming

ADT (Algebraic Data Type)

Book

Category Theory

Conference

Clojure

C++

Curry

Functor

Go

Higher Order Functions

Java

JavaScript

Kind

Lambda

  • 람다, 익명 함수, 클로저
  • 람다 표현식의 장점
  • 람다와 친해지고 싶다면
  • Lambdas are not functional programming
  • An Alien Lambda Calculus • Xuanyi Chew • YOW! 2019 - YouTube
    • VidiGo An Alien Lambda Calculus • Xuanyi Chew • YOW! 2019
      • 컴퓨터 과학과 클로저 계산법
        • 바란조 j. 처치라는 과학자는 그들의 움직임이 계산임을 발견하였고, 계산에는 에테르가 필수적임을 알아냄
        • 클로저 계산법은 순수 람다 계산법과 유사하지만 기존 컴퓨팅 하위 구조에 의존하지 않고 계산을 설명 가능
        • 클로저 계산법은 함수와 환경으로 구성되어 있으며, 모든 것이 함수로 구성되어 있다고 가정하는 것과 관련하여 10개의 축소 규칙 존재
      • 클로저 계산법의 중요성
        • 클로저 계산법은 이름이 축소 과정에서 안정적으로 유지되어 신뢰 가능
        • 클로저 계산법은 메타 연산과 메타 이론을 제거하여 계산을 기술함으로써, 어떤 기반에도 의존하지 않는 자유로운 계산 가능
        • 클로저 계산법은 순수 람다 계산법보다 훨씬 쉽게 기계화할 수 있어, 함수형 언어의 컴파일러 작성자에게 유용
      • 클로저 계산법의 구현과 최적화
        • 클로저 계산법은 재귀 프로그램을 정규 형태로 작성할 수 있게 하며, 이는 컴파일에 매우 유리
        • 클로저 계산법은 간단한 구현과 빠른 실행 속도
          • go, haskell, ocaml 등 다양한 언어로 구현된 클로저 계산법 인터프리터는 순수 람다 계산법인터프리터보다 5배 빠른 성능
        • 클로저 계산법인터프리터는 haskell과 비교해도 30%의 속도를 달성하여 효율적임을 입증
      • 클로저 계산법의 미래와 응용
        • 클로저 계산법은 메타 이론이 없고 간단한 컴파일러를 통해 더 빠른 프로그램을 생성할 수 있다는 장점
        • 저자는 agi(인공 일반 지능) 개발 목표와 관련하여 자신의 딥러닝 라이브러리가 클로저 칼큘러스 개념 위에 구축될 것
        • 클로저 칼큘러스는 함수형 프로그래밍 언어의 기반이 되어야 한다고 주장하며, 타입 있는 람다 칼큘러스에 대한 약속도 함께 제시
    • 외계인 람다 미적분 - 쉬안이 츄 - YOW! 2019 | The fastest way to absorb knowledge | Lilys AI | Lilys AI 6. 인공신경망과 람다 계산의 관련성과 한계
      • Markov 체인은 기억이 없다고 말하며, 계산은 안정 상태의 수정이라고 설명
      • 안정 상태는 '기질(기저체)'에 보관되며, 다양한 종류의 기질이 존재 가능
      • 람다 계산은 인공신경망에서 설명할 수 없지만, 실현 가능성 이론에 따르면 람다 계산은 자체를 실현할 수 없다는 것을 보여줌
      • 람다 계산에는 기질 개념이 필요함을 강조하며, 계산적 기질은 실행 문맥을 추적해야 한다는 것을 강조
      1. 컴퓨터 전산 처리에는 반드시 콘텍스트가 필요
      • 컴퓨터 전산 처리는 항상 콘텍스트 속에서 이뤄짐
      • 'a'는 원래 프로그램의 자유변수로 어떠한 값을 대표 가능
      • 문맥 없이 이 프로그램이 무엇을 하는지 이해할 수 없으며, 단순히 결과물을 반환하는 프로그램
      • 자유변수는 맥락성의 메타 구성요소를 필요로 하는 자유도
      • 컴퓨팅에 필요한 자유도는 단순히 계산을 수행할 콘텍스트를 가지는 것으로 해결
      1. 클로저 계산 화법 소개 및 튜링 완전성
      • 컴퓨테이션에는 'Ether'가 필요하며, 이것은 맥락에 대한 유추의 유사와 동일. 편집기 작성자들은 컨텍스트를 가진 것에 대해 명확하게 이해
      • '람다 x. a'로 'a'를 작성하는 것을 허용하지 않아 컴파일러 오류 유발. 더불어 Haskell이나 OCaml과 같은 함수형 언어 컴파일시 클로저 변환 단계 필요
      • 환경을 힙에 유지할 수 있게 모든 것을 클로저로 번역하고 런타임에서 힙의 구멍을 채우는 것
        • 클로저 계산 화법 소개는 클로저 계산 화법을 소개하기에 완벽한 선행임을 이중하며 튜링 완전성을 갖는 람다 계산의 아름다운 부분을 설명
      • 퓨어 람다 계산과 마찬가지로 함수의 일관된 이론이며 즉각적인 진행과 보존이 일어나는 증명 존재
      1. 폐쇄 계산법의 위상과 추상화 과정
      • 필의 작업장 이후에 출현, 폐쇄 계산법은 기존의 람다 계산법과 비교했을 때 계산을 설명할 때 기본적인 계산기 밑바닥에 의존하지 않고도 가능
      • 이 때 사용되는 용어의 형태는 매우 간단하며 켄과 순수한 람다 계산법과 유사
        • 변수 심볼 X가 일반적이며, 응용이 존재하면서 더 이상한 형태의 태그 적용 존재
      • 문맥 확장 문법이 있어 이는 환경이자 명확한 치환을 나타내는 데 사용. 배울 점이 많은데 그 중 하나는 폐쇄라는 형태 하나만 사용 가능하다는 것
      • 이제 순수 람다 계산법의 추상화 개념과 비교
      1. 클로저 캘큘러스의 기본 개요
      • 클로저 캘큘러스에서는 람다와 클로저, 즉 함수와 환경을 생성. 환경은 시그마와 상자로 표시
      • 여기서 본 모든 것은 추상적인 구문이며, 클로저 추상화의 구체적인 버전 확인
      • 환경이 여러 명칭을 포함할 때는 어떻게 되는지 알아보고, 기본적으로 함수는 그대로이지만 클로저는 더 많은 명칭을 포획
      1. 람다 계산 논리와 클로저 계산 논리 간 비교
      • 람다 계산 논리에는 1개부터 3개의 축약 규칙이 있으며 EA 확장이 규칙 집합의 일부로 간주되어야 하는지 여부에 따라 다를 수 있음
      • 순수 람다 계산에는 3개의 규칙이 있지만 클로저 계산에는 10개의 축약 규칙이 있으며 이 중 2개는 메타 이론을 가지고 있음
      • 메타 이론을 가지지 않은 11개 규칙을 가진 다른 버전의 클로저 계산도 있음
        • 클로저 계산의 중요성은 계산이 물질에 의존하지 않으므로 보다 단순하고 빠르다는 것에 있음
      • 클로저 계산으로 기술된 계산은 모든 메타 이론에서 자유로우며 순수 람다 계산보다 더 쉽게 기계화 가능
      1. 자유 변수와 클로저 계산
      • 클로저 계산에서는 자유 변수가 어디서나 실제로 자유로움
      • 순수 Lambda 계산에서 변수 x의 자유 여부는 문맥에 의해 결정, 바깥 쪽에서 활용될 시 자유가 아닌 경우가 있어 복잡성이 증가
      • 클로저 계산에서는 변수 x가 여기서도 자유하며, 자유 변수의 존재로 축약 과정을 이해하기 어렵게 만듦
      • 이런 이유로 변수 자체에 대한 매핑 추가로 축약이 올바르게 작동하도록 할 수 있음
      1. ️컴파일러 작성자의 함수형 프로그래밍 관점에서의 변수 할당
      • 함수형 언어에서 컴파일러 작성자이고, x를 자신에게 매핑하는 것은 컴파일러에서 익숙한 일
      • STG의 이는 새로운 L을 생성하며, f는 힙에 있는 클로저로, 몸체는 힙에 있는 코드에 지정. 각 자유 변수는 값을 보유하는 메모리 위치에 지정
      • 환경으로 해석되며 degrees of freedom, 계산 변수를 구현하는 방법은 그것을 메모리 위치에 대한 포인터로 놓는 것
        • 자유 변수는 함수 안에서 자유롭지만 클로저 안에서는 바운드된 것으로 해석 가능
      • 클로저 계산이 간단해지며 재귀적 프로그램 작성도 가능, 클로저 계산의 특성 상 자연스럽게 정규형으로 컴파일이 가능
        • 여기서 정규형은 약신경 정규형처럼 개념적인 것이 아닌, 단순 계산 규칙을 더 이상 줄일 수 없는 형태를 의미
      1. 함수형 프로그래밍에서의 'Frozen Form' 개념
      • Frozen Form은 pen, paper 또는 기계기억장치의 비트로 작성되는 것이다. 일반형태와는 다름
      • 함수형 프로그래밍 언어에서 컴파일된 프로그램 대해 고려하지 않는다. 컴파일 및 실행을 구분해 최소한의 작업으로 런타임에 대비
      • 컴파일과 런타임 사이, 이진코드로 변환하여 하드디스크에 저장
      1. 태깅 어플리케이션의 컴파일 시간 축소 중지와 재귀 프로그램 실행 방법
      • 프로그래머에게 '태깅 어플리케이션에서 @ 기호는 컴파일 시간에 축소를 중지하는 방법'
      • 태깅 어플리케이션의 최종 프로그램 평가에는 무영향. 이 두 프로그램은 실행 중에 '@'로 평가
        • 컴파일 시간에 두 단계의 축소를 가지고 있을 때, 이 프로그램들의 컴파일된 버전을 살펴보면 하나는 간단하고 하나는 그렇지 않음
      • 프리즌 용어 제거하는 방법은 대체로 베타의 동등하게 대체함으로써 각 단계에서 Frozen term을 제거 가능
      • 우리는 컴파일러가 재귀성에 빠지는 것을 방지하기 위해 ad를 추가함으로써 컴파일러 중지 가능
        • 이러한 경우에도, 태그를 제거할 수 없기 때문에, 이젠 쓸모 없는 용어가 됨
      1. 프로그램 정규화의 중요성과 실행 속도에 미치는 영향
      • 정규화된 폐포 논리 계산 형식을 사용하면 표준 응용프로그램인 SS, 즉 정규형이 출현
      • 정규 형식을 도입한 후, 정규 형식이 아닌 용어를 강제로 정규화된 폐포 논리 해석기에 통과시키면 Lambda 아래로 축소 시도
        • 결과적으로 정규 형식인 항등 함수로 변환
      • 프로그램을 정규 형식으로 작성할 수 있는 능력은 매우 중요, 이는 프로그램이 실행 시간에서 더 빨라지도록 함
      • 따라서 프로그램에서 정규 형식을 활용하는 이유가 중요
        • 실행 전에 프로그램을 빠르게 실행할 수 있는 정규 형식을 강제로 정규화함으로써 실행 속도를 향상 가능
      1. AGI를 만드는 열정, 클로저 산술 해석기 공부와 성과
      • "AGI를 구축하는 것이 인생 동기"로, 기본 컴퓨테이션을 이해하는 것이 중요
      • 자체 딥 러닝 라이브러리 보유, 클로저 산술 해석기 구현 및 성능 평가
      • 클로저 산술 해석기 구현과 속도 측면에서 우월함, 순수 람다 산술보다 5배 빠름
      1. 람다 계산법의 메타이론과 클로저 계산법의 성능 측정 비교
      • 람다 계산법의 메타 이론에 많은 시간을 들이며, 클로저 계산법의 성능을 평가하기 위해 해시를 사용한 클로저 계산법 해석을 이용한 벤치마킹을 실시
      • 표준 방법이 아닌 람다 계산법을 빠르게 만들고 싶다면, 기존의 프로그램에 복잡성을 더하는 것을 고려 필요
      • 일반적인 벤치마크 프로그램이 HLL 언어로 개발되는 것이 어려워, Haskell 언어로 만든 프로그램을 통해 순수한 람다 계산법과 클로저 계산법의 비교 진행
      • 벤치마크 프로그램의 첫 번째 해석기를 HLL 언어로 작성하였으나 일관성 없는 결과를 얻어 결국 Haskell 언어로 변경
        • 런타임에서 조절할 수 있는 매개변수가 많아 결정적인 벤치마킹이 어려웠음
      • 프로그램들은 Haskell 프로그램으로 시작하여 순수한 람다 계산법으로 변환, 이후 클로저 계산법으로 변환
        • 결과적으로 클로저 계산법을 통해 Haskell 언어와 벤치마킹을 수행
      1. 하스켈 홈페이지의 프라임 함수와 클로저 산식의 중요성
      • 헤스켈 홈페이지에 있는 프라임 함수를 소개하며 하스켈의 간결함을 강조하고, 기능을 벤치마킹해야 한다고 강조
      • 최초에는 순수 람다 계산의 '스콧 코딩' 버전을 사용했으나, 이는 700줄의 코드로 복잡하다고 언급
        • '암시적 프렐류드'를 사용하면 더 어려워진다고 설명
      • 특히 클로저 산식을 사용하면 메타이론없이 더 간단하고 빠른 프로그램 제작 가능, 이를 기반으로 함수형 프로그래밍을 추구해야 한다고 강조
      • 그리고 추후에는 람다에 대한 타입이 나오고 더 많은 질문과 답변이 이루어질 것을 기대
      1. 개별적인 계산법으로의 발전에 대한 토론
      • 간단하게 'SK'같은 복잡한 계산법이 개발되는 과정이 내용 독립성과 명명 주제로
      • 클로저 클로저 계산법과 비교했을 때, 추상화 계산법을 통해 이에 대한 느낌을 하나의 측면으로 보는 것 같음
      • 추상화 계산법에 대한 강인한 신뢰, 클로저 클로저 계산법은 한 측면에서 부수 트랙같은 요소로 이해 가능

Lisp

Monad

Python

Racket

Scala

Swift