람다 계산식

Question

람다 식 (x (λx y. x y) z h)의 경우, 자유 변수 x (outer x), z 및 h을 어떻게 C 코드로 변환 할 수 있는지 이해하지 못했습니다. C 코드 람다 계산법 변환

감사 darkie

Answer 1

자유 변수는 람다 미적분학의 특별한 경우입니다. 아무 것도 사용할 수 없으므로 대개 기호로 취급됩니다. 당신의 예에서와 람다 표현식에 대한 몇 가지 가상 생성자를 제공, 당신은 (암시 적 태닝 처리 포함) 다음과 같은 C와 같은 표현으로 번역 것 :

mk_app(mk_app(mk_app(mk_sym("x"), 
        mk_lam("x", 
          mk_lam("y", 
            mk_app(mk_var("x"), 
              mk_var("y"))))), 
       mk_sym("z")), 
     mk_sym("h")); 

를 분명히, 당신은 사람들을 위해 mk_var()을 사용할 수 있습니다 심볼도 있지만, 실제로는 변수가 아니기 때문에 오해의 소지가 있습니다. 즉, 표현식에서 알파 변환을 수행하면 동일하게 유지해야합니다.

(BTW, 관련 부분은 Barendregt의 자유 변수 가정입니다.)

Answer 2

은 사소하다. 일반적으로 단계별로 평가되는 통역사를 작성합니다. 즉, 표현식을 트리로 바꾸고 왼손 쪽이 람다 인 응용 프로그램 인 루트에 가장 가까운 노드를 찾으십시오. 이제 오른쪽으로 대체하십시오. 더 이상 적용 할 수 없을 때까지 반복하면 결과가 나타납니다.

여기서 자유 변수와 직접적으로 동일한 것은 없습니다. 우리는 물건을 대체 할 장소를 알기 위해 그것들을 사용하고 있습니다.

튜링 동등성은 정확한이 두 튜링 완성 언어의 모든 개념간에 등가가 아니어야 함을 명심하십시오. 그것은 단순히 당신이 다른 하나와 에뮬레이트 할 수 있어야하고, 그 반대도 마찬가지입니다.