추상 구문 트리

소개하다.

컴파일러가 반드시 취해야 할 첫 번째 단계 중 하나는 인간이 읽을 수 있는 프로그램 형식을 해석하는 것이다. 보통 순수한 텍스트 파일로 컴파일러가 사용할 수 있는 구조에 넣는다.Abstract Syntax Tree.
다음은 AST와 함께 코드 뒤에 있는 간단한 예입니다.

f 2

조금 더 복잡한 예가 하나 더 있다.

( \x -> x + x ) 2

본문에서 저는 앞에서 제시한 요구에 따라 제 언어에 AST를 정의하고 싶습니다.

아래층

저는 주로 다음과 같은 업무에 기반을 두고 있습니다.

[Peyton Jones & Lester 1992] 함수식 언어 구현: 강좌.비록 내가 타성어에 전문적으로 관련된다고 언급해야 하지만, 이 책의 제목은 자명하다.

[Martin-L‰f 1973] 유형의 직각 이론: 술어 부분.본고는 먼저 Martin-Lνf 유형 시스템, 즉 의존 유형을 소개한다.그것은 프로그램에서 값에 대한 명제를 어떻게 유형과 용어로 표현하는지 설명한다.

[Atkey 2018] 수량 유형 이론의 문법과 의미.본고는 수량 유형 이론을 묘사하는데 유형과 선형 값과 지우기를 결합시킨다.

물론 나도 전달할 수 있는 지식과 내가 이곳과 그곳에서 배운 것을 많이 사용했지만 구체적인 출처는 없었다.

기본AST

AST의 외관을 정의하려면 언어 문법을 지정해야 합니다.이것은 보통 BNF (Backus-Naur Form) 기호를 사용하여 완성한다.Haskell과 Idris 같은 언어에서 직접 하나의 유형으로 표현하는 것은 매우 쉽기 때문에 나는 이렇게 할 것이다.
저는 17페이지[Peyton Jones & Lester 1992]에서 제시한AST부터 시작해서 Idris로 번역했습니다.

data Expr a
  = EVar String
  | ENum Int
  | ECtr Int Int
  | EAp (Expr a) (Expr a)
  | ELet IsRec (List (a, Expr a)) (Expr a)
  | ECase (Expr a) (List (Alt a))           
  | ELam (List a) (Expr a)

data Alt a = (Int, List a, Expr a)

여기에 유형 변수a는 값의'귀속기'입니다.일반적으로 이것은 String변수명을 표시하지만 다른 유형도 사용할 수 있다.EVar는 명명 변수를 나타낸다. 예를 들어x.ENum는 숫자 원어를 나타낸다. 1,2,42 등이다.ECtr는 직관적이지 않다. 우리가 하나의 유형을 정의할 때, 예를 들어data MaybeInt = Just Int | Nothing 모든 구조 함수에 하나의 숫자를 부여할 수 있는데 이를 표기라고 부른다.태그는 정확한 구조 함수와 일치하도록 대소문자 표현식으로 내부에서 사용할 수 있습니다.Int의 또 다른 ECtr 매개 변수는arity: 구조 함수는 몇 개의 매개 변수를 받아들입니까?이 예에서 Just는arity1이 있고 Nothing는arity0가 있다.EAp는 함수 응용이다.예를 들어, f x는 EAp (EVar "f") (EVar "x")로 해석됩니다.ELet는 let ... in 표현식을 나타내는데 그 중에서 (a, Expr a) 값은 변수 정의이다.ECase는 대소문자 표현식입니다.Alt a 유형에는 일치하는 표기값, 일련의 구조 함수 매개 변수와 표현식이 있습니다.ELamlambda 함수에 사용합니다.
나는 선호에 따라 약간의 변화를 하고 싶다.
우선, 우리는 폐쇄 정의에 대한 정적 분석을 통해let 표현식이 귀속되는지 확인할 수 있다. 예를 들어let xs = 1 : xs in ....[Peyton Jones & Lester 1992] 6.8.3에서 많든 적든 이렇게 할 것이다.나는 특정한 영역이 있는 것을 좋아하지 않는다. 그러면 나는 단일한 진리의 근원을 가지게 된다.필드IsRec를 삭제합니다.나는 이 책이 의존성 분석을 먼저 해석하는 것을 피하기 위해 이 필드를 사용했을 뿐이라고 의심한다.
둘째, 숫자는 구조기일 뿐이니 그들의 특권을 진정으로 점검해야 한다.기본값 int 은 아주 좋은 버그 원본입니다.디지털에 대한 특수 처리를 통해 우리는 더 많은 통용적인 최적화를 소홀히 했다.ENum 갔어요.
셋째, 나는 Elm 스타일의 안내서에서 몇 가지 힌트를 얻었는데, 더욱 의미 있는 사용자 정의 유형으로 내장 유형을 대체했다.
이러한 기본적인 변화 후에 우리가 남은 것은 다음과 같다.

data Expr a
  = EVar VarID
  | ECtr CtrID
  | EAp (Expr a) (Expr a)
  | ELet (List (Def a)) (Expr a)
  | ECase (Expr a) (List (Alt a))           
  | ELam (List a) (Expr a)

data Alt a = MkAlt CtrID (List VarID) (Expr a)

data Def a = MkDef a (Expr a)

일부러 다양한 ID를 정의하지 않았습니다.

세상을 더 미치게 만들다

hollistic 프로그래밍을 지원하기 위해 어떤 변경이 필요한지 고려하기 위해서 우리는 언어의 목표로 돌아가야 한다.
만약 우리가 특정한 프로그램이 아닌 언어로 전체 시스템을 정의하기를 원한다면, 우리는 코드가 시간에 따라 변화하는 것을 고려하기 시작해야 한다.일반적으로 개발자는 변경이 지속적인 시스템(예를 들어 데이터베이스)과의 호환성을 파괴하지 않도록 확보할 책임이 있다.만약 이 시스템이 컴파일러에 의해 생성된다면, 컴파일러는 반드시 이전 버전과 호환성을 증명할 수 있어야 한다.불변성은 이 방면에 큰 도움이 된다.Elm uses immutability to quickly determine what areas of a DOM need updating와 같이 우리도 프로그램 정의 자체가 불변성을 가지기를 바란다. 그러면 우리는 무엇이 호환되는지 정확하게 확정할 수 있다.만약 우리가 어떤'아순'이 있다면 다행이다. 프로그래밍 자체를 순수하게 만드는 것이다.
이를 실현하기 위해 나는 unison의identify-by-hash 방법을 복제할 것이다.만약 이름이 상태가 있고 시간의 추이에 따라 다른 함수를 가리킬 수 있다면 해시는 무상태이다.만약 함수에 변화가 발생한다면, 그것의 산열도 변화가 발생할 것이다.
물론 프로그래머에게 해시를 직접 사용하여 프로그래밍을 하는 것은 불가능하다.우리는 인류와 호환되는 언어가 필요하다. 이를 디스플레이 언어라고 부른다.대부분의 다른 프로그래밍 언어에서 디스플레이 언어는 진리의 원천이다.핵심 언어인 AST는 번역 과정에서 파생된 것이다.이곳에서 기회를 하나 놓쳤다.
개발자들은 순수한 디스플레이 문제로 말다툼을 하여 많은 정력을 낭비했다. 옵션 카드와 공간,camelCase와PascalCase,snake case와kebabcase,조작부호와 함수,가져오기 정의,명명,정렬,이집트 괄호.식별자로서의 이름을 삭제한 후 핵심 언어의 프로그램의AST를 바꾸지 않습니다.만약에 우리가 핵심 언어를 진실의 원천으로 만들고 디스플레이 언어를 핵심 언어로 정의하고 디스플레이 정보(예를 들어 변수 이름)를 추가하면 우리는 이러한 문제점을 완전히 제거할 수 있다.
이제 AST로
많은 명칭 문제는 산열을 사용해서 해결되었지만, 변수는let 표현식, lambda, 슈퍼 조합기에 귀속될 수도 있습니다.여기서 우리는 결코 산열할 필요가 없다.우리는 let 표현식과 슈퍼 조합기 사용에 약간 적응할 수 있는 de Bruijn index 를 사용할 수 있다. (둘 다 lambda 함수로 변환할 수 있지만, 이것은 그 반대인 것 같다.)
나는 데블린 지수의 국부 변수와 전체 변수를 사용해야 한다.귀속 형식이 불필요해졌습니다. 귀속 표현식에 몇 개의 귀속이 있는지 알기만 하면 됩니다.

data Expr
  = ELVar Nat               ||| de Bruijn index of locally-bound variable
  | EGVar Hash              ||| Hash of globally bound supercombinator
  | ECtr CtrID                    
  | EAp Expr Expr
  | ELet (List Expr) Expr   ||| 1st arg is definitions, second is the "in" part
  | ECase Expr (List Alt)           
  | ELam Nat (Expr a)       ||| Only need to know number of arguments

data Alt = MkAlt CtrID Expr ||| # arguments derived from CtrID

의존형

이것은 우리에게 두 가지 문제를 남겼다. CtrID 정의가 없고, 유형을 값으로 사용하는 방법이 부족하다.
불행하게도, 나는 이곳에서 수학을 대량으로 사용하기 시작했고, dev.to에 수학을 표시하는 만족스러운 방법을 찾지 못했다. 이것은 대량의 수공이 필요하지 않다.계속 읽어주세요my website.