평가에 의한 정규화

이 기사 또는 섹션은 포맷이 필요할 수 있다. 위키피디아는 당신이 방법을 알고 있다면 포맷하여 도움을 줄 수 있다. 또한 이 통지를 보다 구체적으로 변경하는 것도 고려하십시오. (2014년 4월)

언어 의미론 프로그래밍에서 평가(NBE)에 의한 정상화는 그들의 변위적 의미론에 호소하여 λ-미적분학의 정상적인 용어 형태를 얻는 스타일이다.항을 λ-기간 구조의 변성 모델로 먼저 해석한 다음, 변성체를 다시 해석하여 정합(β-정규 및 η-길이) 대표자를 추출한다.그러한 본질적으로 의미론적 접근방식은 β-저감이 β-저감이 β-저감되는 용어 재작성 시스템의 감소로서 정상화에 대한 보다 전통적인 통사적 설명과는 다르다.

NBE는 간단히 타이핑된 람다 미적분학을 위해 처음 설명되었다.^[1]이후 영역 이론적 접근법을 이용한 비형식 람다 미적분학과^[2] 같은 약한 유형 체계와 마틴 뢰프 유형 이론의 여러 변종과 같은 풍부한 유형 체계로 확장되었다.^[3][4]

개요

간단히 타이핑된 람다 미적분학을 고려해 보십시오. 여기서 타입 τ은 기본형(α), 함수형(→) 또는 제품(×)이며, 다음과 같은 백커스-나우르 양식 문법(→평소처럼 오른쪽과 연관됨)이 주어진다.

(유형) τ ::=α τ₁ → τ₂₁ × τ₂

이러한 데이터 형식은 메타 언어에서 데이터 형식으로 구현될 수 있다. 예를 들어 표준 ML의 경우 다음을 사용할 수 있다.

 데이터타입 ty = 기본 의 끈을 매다                화살표 의 ty * ty                프로드 의 ty * ty 

용어는 두 가지 수준에서 정의된다.^[5]낮은 구문적 수준(동적 수준이라고도 함)은 정상화를 의도하는 표현이다.

(Syntax 약관) s,t,… :=var x lam (x, t) app (s, t) pair (s, t) fst t snd t.

여기서 lam/app(resp. pair/fst,snd)는 → (resp)를 위한 도입/엘림 양식이다.×) 및 x는 변수다.이러한 용어는 메타 언어의 1차 주문으로 구현하기 위한 것이다.

 데이터타입 tm = 시합을 하다 의 끈을 매다                램 의 끈을 매다 * tm   앱. 의 tm * tm                짝을 짓다 의 tm * tm   fst 의 tm   코를 납작하게 만들다 의 tm 

메타 언어의 (폐쇄) 용어의 변절적 의미론에서는 구문의 구조를 메타 언어의 특징적인 측면에서 해석하므로 lam은 추상화, 어플리케이션으로서의 앱 등으로 해석된다.구성된 의미론적 객체는 다음과 같다.

(근대적 용어) S,T,… ::= LAM (λx. S x) PARE (S, T) SYN t

의미론에는 변수나 제거 형식이 없으며 단순히 구문으로 표현된다.이러한 의미론적 객체는 다음과 같은 데이터 유형으로 표현된다.

 데이터타입 셈 = 램 의 (셈 -> 셈)                 쌍 의 셈 * 셈                 SYN 의 tm 

통사적 계층과 의미적 계층 사이를 왔다 갔다 하는 한 쌍의 유형 색인화 함수가 있다.보통 ↑_τ이라고 쓰여진 제1함수는 구문이라는 용어를 의미론에 반영하고, 제2함수는 의미론을 통사적 용어(↓로 표기)로 재합성한다.^τ이들의 정의는 다음과 같이 상호 재귀적이다.

${\displaystyle {\begin{aligned}\uparrow _{\alpha }t&=\mathbf {SYN} \ t\\\uparrow _{\tau _{1}\to \tau _{2}}v&=\mathbf {LAM} (\lambda S.\ \uparrow _{\tau _{2}}(\mathbf {app} \ (v,\downarrow ^{\tau _{1}}S)))\\\uparrow _{\tau_{1}\times(_{2}}v&, =\mathbf{PAIR}(\uparrow_{\tau_{1}}(\mathbf{fst})v),\uparrow _{\tau_{2}}(\mathbf{과 에이브라함 링컨})v))\\[1ex]\downarrow ^ᆲ(\mathbf{SYN})t)&, ^{\tau_{1}\to \tau _{2}}(\mathbf{LAM})S)& =t\\\downarrow, =\mathbf{ 때리다})(x,\downarrow ^{\tau_{2}}(S\(\uparrow_{\tau_{1}}({})\mathbf)))).){\text{ where }}x{\text{ is fresh}}\\\downarrow ^{\tau _{1}\times \tau _{2}}(\mathbf {PAIR} \ (S,T))&=\mathbf {pair} \ (\downarrow ^{\tau _{1}}S,\downarrow ^{\tau _{2}}T)\end{aligned}}}$

이러한 정의는 메타 언어로 쉽게 구현된다.

 (* fresh_var : unit -> string *)  발랄하게 하다 variable_ctr = 참조하다 ~1  재미있다 fresh_var () =        (variable_ctr := 1 + !variable_ctr;         "v" ^ 인트.토스트링 (!variable_ctr))   (*반사 : ty -> tm -> sem *)  재미있다 반영하다 (화살표 (a, b)) t =        램 (fn S => 반영하다 b (앱. (t, (재조명화하다 a S))))      반영하다 (프로드 (a, b)) t =        쌍 (반영하다 a (fst t), 반영하다 b (코를 납작하게 만들다 t))      반영하다 (기본 _) t =        SYN t   (* reify : ty -> sem -> tm *)  그리고 재조명화하다 (화살표 (a, b)) (램 S) =        하게 하다 발랄하게 하다 x = fresh_var () 에          램 (x, 재조명화하다 b (S (반영하다 a (시합을 하다 x))))        종지부를 찍다      재조명화하다 (프로드 (a, b)) (쌍 (S, T)) =        짝을 짓다 (재조명화하다 a S, 재조명화하다 b T)      재조명화하다 (기본 _) (SYN t) = t 

형식 구조에 대한 유도에 의해, 의미 객체 S가 타입 of의 잘 짜인 용어 s를 나타내면, 물체(즉, ^τs S)를 재화하면 β-정규 normal-긴 형태의 s가 생성된다는 것을 따른다.그러므로 남아 있는 모든 것은 초기 의미 해석 S를 통사적 용어 s에서 구성하는 것이다.∥s∥_Γ라고 쓰여진 이 운영은, ∥이 바인딩의 맥락인 경우, 오직 용어 구조에만 근거하여 유도에 의해 진행된다.

${\displaystyle{\begin{정렬}\ \mathbf{초본})x\ _{\Gamma}&, =\Gamma())\\\ \mathbf{ 때리다})(x,s)\ _{\Gamma}&, =\mathbf{LAM})(\lambda S.\)s\_{\Gamma ,x\mapsto S})\\\\mathbf{앱})(s,t)\ _{\Gamma}&, =S\()t\_{\Gamma}){\text{어디}})s\ _{\Gamma}=\mathbf{LAM})S\\\ \mathbf{쌍})(s,t)\ _{\Gamma}&, =\mathbf{PAIR}\. (\ s\ _{\Gamma},\ t\ _{\Gamma })\\\ \mathbf {fst} \ s\ _{\Gamma }&=S{\text{ where }}\ s\ _{\Gamma }=\mathbf {PAIR} \ (S,T)\\\ \mathbf {snd} \ t\ _{\Gamma }&=T{\text{ where }}\ t\ _{\Gamma }=\mathbf {PAIR} \ (S,T)\end{aligned}}}$

구현 시:

 데이터타입 ctx = 텅 빈                  덧셈을 의 ctx * (끈을 매다 * 셈)   (* 조회 : ctx -> 문자열 -> sem *)  재미있다 찾다 (덧셈을 (리머드, (y, 가치를 매기다))) x =         만일 x = y 그때 가치를 매기다 다른 찾다 리머드 x   (* 의미 : ctx -> tm -> sem *)  재미있다 의미 G t =        케이스 t 의          시합을 하다 x => 찾다 G x          램 (x, s) => 램 (fn S => 의미 (덧셈을 (G, (x, S))) s)          앱. (s, t) => (케이스 의미 G s 의                           램 S => S (의미 G t))          짝을 짓다 (s, t) => 쌍 (의미 G s, 의미 G t)          fst s => (케이스 의미 G s 의                      쌍 (S, T) => S)          코를 납작하게 만들다 t => (케이스 의미 G t 의                      쌍 (S, T) => T) 

비소진 사례가 많지만, 닫힌 웰타입 용어에 적용할 경우 이러한 누락 사례 중 어느 것도 발생하지 않는다는 점에 유의하십시오.닫힌 조건에서의 NBE 운영은 다음과 같다.

 (* nbe : ty -> tm -> tm *)  재미있다 nbe a t = 재조명화하다 a (의미 텅 빈 t) 

그 사용의 예로서, 통사적 용어를 고려한다.SKK아래에 정의된:

 발랄하게 하다 K = 램 ("x", 램 ("Y", 시합을 하다 "x"))  발랄하게 하다 S = 램 ("x", 램 ("Y", 램 ("z", 앱. (앱. (시합을 하다 "x", 시합을 하다 "z"), 앱. (시합을 하다 "Y", 시합을 하다 "z")))))  발랄하게 하다 SKK = 앱. (앱. (S, K), K) 

이것은 결합논리학에서 아이덴티티 함수의 잘 알려진 인코딩이다.ID 유형에서 이를 정규화하면 다음과 같은 결과가 발생한다.

 - nbe (화살표 (기본 "a", 기본 "a")) SKK;  발랄하게 하다 그럭저럭 = 램 ("v0",시합을 하다 "v0") : tm 

결과는 다른 신분 유형에서 정상화하는 것으로 쉽게 알 수 있듯이 실제로 η-긴 형식이다.

 - nbe (화살표 (화살표 (기본 "a", 기본 "b"), 화살표 (기본 "a", 기본 "b"))) SKK;  발랄하게 하다 그럭저럭 = 램 ("v1",램 ("v2",앱. (시합을 하다 "v1",시합을 하다 "v2"))) : tm 

참고 항목

• MINLOG, NBE를 리프레시 엔진으로 사용하는 증명비서 MINLOG.

참조