wamcc: Prolog 를 C 로 컴 파일 합 니 다 (No. 7 - 3)

3. 기 존의 논리 프로 그래 밍 번역자
우 리 는 이 절 에서 Janus, KL1, Erlang 과 wamcc 가 제어 흐름 을 어떻게 처리 하 는 지 상세 하 게 소개 할 것 이다.이 프레젠테이션 원 고 는 [5] 에서 영감 을 얻 었 고 중첩 모델 의 목 표를 채택 했다.그러나 우 리 는 실제 집행 과 유사 한 추상 을 따 르 지 않 는 다.이러한 선택의 결 과 는 C 코드 와 WAM 명령 의 상관 성 을 명확 하 게 묘사 했다.편폭 이 제한 되 어 있 기 때문에, 우 리 는 여기에서 만 통제 문 제 를 토론 할 것 이다.우선 이런 사실 에서 wamcc 가 사용 하 는 WAM 은 전통 적 이 고 최적화 되 지 않 았 다.그래서 지금 은 다른 명령 에 쓰 인 코드 가 잘 알려 져 있다 [1].둘째, 효과 적 인 통제 의 관건 은 C 로 번역 하 는 것 이다. WAM 코드 가 평평 하고 분기 로 전환 되 기 때문이다.이것 은 고 차원 적 인 통제 구조, 예 를 들 어 기능 에 더욱 적합 하고 낮은 등급 의 통제 에 더 많은 것 을 제공 하지 않 는 다.따라서 주요 문 제 는 WAM 분기 의 번역 에 적합 한 해결 방안 을 찾 을 것 이다.우리 의 프 리 젠 테 이 션 은 아래 의 예 에서 하나의 자구 와 하나의 사실 만 을 바탕 으로 할 것 이다.

p:  allocate   /* p:- q, r.   */
     call(q)
     deallocate
     execute(r)

q:  proceed    /* q.  */

그러나 이 간단 한 예 는 Prolog 의 제어 가 결정적 인 상황 에서 사용 하 는 명령 을 보 여 준다.번역 방식 의 호출 과 실행 이 특히 두 드 러 질 것 입 니 다. 직접 가 지 를 어떻게 관리 하 는 지 (즉, 목표 주소 가 이미 알 고 있 는 태그 일 때) 명령 번역 으로 문 제 를 해결 하 는 간접 가 지 를 나 누 는 지 (즉, 목표 주소 가 일부 변수의 내용 일 때 이 경우 CP 를 등록 하 는 것).
그러나 문제 가 생 겼 다. 간접 분기 가 갖 춰 지지 않 은 표준 (ANSI) C (따라서 시 뮬 레이 션 해 야 함) 이 고, GOTO 명령 이 같은 기능 의 코드 만 처리 할 수 있 기 때문이다.이 솔 루 션 은 C 프로그램 으로 구 성 된 독특한 기능 인 스위치 명령 으로 간접 GOTO 문 구 를 모 의 한다.이런 방법 을 사용 한 후에 우리 앞의 예 는 다음 과 같이 바 뀔 것 이다.
4. 567913. 이런 방법 은 RISC 기계 에서 비용 이 많이 든다. switch 문장의 비용 은 약 10 개의 기계 명령 (경계 검사 포함) 이기 때문이다.그러나 이런 방법의 주요 단점 은 하나의 프로그램 이 하나의 기능 으로 올 라 가 는 것 이다.따라서 장난감 의 예 를 제외 하고 커 다란 기능 이 생 길 수 있 고 C 컴 파일 러 는 합 리 적 인 시간 안에 처리 할 수 없다.이렇게 설정 하면 모듈 화 에 대응 하 는 것 이 쉽 지 않다.이 모듈 을 통 해 스위치 기능 을 제어 할 수 있 도록 모든 서술 어 에 문의 동적 표를 호출 해 야 합 니 다.또한 완전한 Prolog 를 지원 하기 위해 문맥 변화 상황 에서 정확 한 역 추적 처리 에 도 관심 을 가진다.따라서 모듈 화 를 지원 하 는 것 은 벌칙 이 며, 하나의 추가 모듈 호출 은 하나의 모듈 내 호출 보다 훨씬 많은 비용 을 들일 것 이다.
3.1 Janus
Janus 실현 은 간단 한 사상 을 바탕 으로 C 분 지 를 통 해 WAM 분기, 즉 goto 명령 으로 번역 하 는 것 이다.유사 한 방법, 예 를 들 어 [11] 에서 설명 한 Prolog 컴 파일 러 에서 사용 합 니 다.그러나 문제 가 생 겼 다. 프로필 가 지 는 표준 C (ANSI C) 가 갖 추 지 못 한 (따라서 시 뮬 레이 션 해 야 함) 이 고, goto 명령 은 같은 코드 기능 에서 만 처리 할 수 있 기 때문이다.이 솔 루 션 은 C 프로그램 으로 구 성 된 독특한 기능 인 스위치 명령 으로 간접 GOTO 문 구 를 모 의 한다.이런 방법 을 사용 한 후에 우리 앞의 예 는 다음 과 같이 바 뀔 것 이다.
4. 567913. 이런 방법 은 RISC 기계 에 비 싼 비용 을 쓴다. switch 문장의 비용 은 약 10 개의 기계 명령 (경계 검사 포함) 이기 때문이다.그러나 주요 단점 은 프로그램 이 단일 한 기능 으로 올 라 가 는 것 이다.따라서 장난감 의 예 를 제외 하고 커 다란 기능 이 생 길 수 있 고 C 컴 파일 러 는 합 리 적 인 시간 에 처리 할 수 없다.이 설정 에서 모듈 화 에 대응 하 는 것 은 쉽 지 않 습 니 다. 이 모듈 을 통 해 스위치 기능 을 제어 할 수 있 도록 모든 서술 어 에 문의 동적 표를 호출 하 라 고 요구 합 니 다.또한 완전한 Prolog 를 지원 하고 환경의 변 화 를 배려 하 는 상황 에서 역 추적 을 정확하게 처리한다.따라서 지원 모듈 화 는 징벌 적 이 며, 추가 모듈 호출 은 한 모듈 내 호출 보다 훨씬 비싸다.
3.2 KL1
C 함수 로 서 의 어 셈 블 리 는 비 현실 적 이 며, C 프로그램 WAM 코드 를 몇 가지 기능 으로 자 르 는 것 을 대표 한다.모든 Prolog 서술 어 는 C 함수 로 자 연 스 럽 게 번역 되 어 보인다.WAM 가 지 는 함수 호출 까지 올 라 갑 니 다.이러한 함 수 는 되 돌아 오기 전에 다른 내장 함수 (분기) 를 호출 합 니 다. 이에 따라 유추 합 니 다.이렇게 되면 프로그램 이 끝나 기 전 까지 는 영원히 돌아 오지 않 을 것 이다.따라서 C 제어 스 택 에 쌓 인 데 이 터 는 쓸모 가 없어 메모리 가 넘 칠 수 있 습 니 다.해결 방법 은 하나의 가 지 를 실행 하기 전에 모든 함수 에서 되 돌아 오고 하나의 프로 세 스 감독 기 가 가 지 를 충분히 연장 시 키 는 것 이다.이것 은 다음 과 같은 우리 가 계속 하 는 코드 예 시 를 초래 했다.
4. 567913. 위의 코드 를 묘사 하면 PC 레지스터 의 최적화 를 억제 하고 그 정 보 를 되 돌려 주 는 기능 을 할 수 있다.따라서 전달 제어 와 분기 가 필요 할 때 모든 기능 은 줄 계산 과 터미널 주 소 를 되 돌려 줍 니 다.이러한 방법의 분석 은 하나의 WAM 분기 가 하나의 함수 에서 호출 된 후에 하나의 반환 에서 관리자 로 실시 되 었 음 을 나타 낸다.이 비용 은 간단 한 jmp 명령 보다 현저히 높 아서 로 컬 코드 컴 파일 러 가 생 길 것 이다.그러나 추가 모듈 호출 은 현재 추가 비용 을 지불 하지 않 아 도 될 것 으로 보인다.처음 실 시 된 wamcc 는 이 기술 을 사용 하고 시 뮬 레이 션 Sicstus 보다 두 배 정도 느 립 니 다.KL1 은 함수 호출 과 반환 을 줄 이기 위해 저울질 을 했 습 니 다. 같은 모듈 내 덕 때문에 서술 어 는 하나의 기능 으로 번역 되 었 습 니 다.따라서 하나의 모듈 만 있 으 면 KL1 행 위 는 Janus 와 같다.감독 기능 은 추가 모듈 에 대한 상하 문 전환 만 필요 하기 때문에 원가 가 내부 모듈 호출 을 초과 한다.
마지막 으로 이런 방법 (KL1 건의 개선 여부 와 상 관 없 이) 이 100% ANSI C 에 가장 적합 한 솔 루 션 임 을 진술 합 시다.
3.3 Erlang 은 Erlang 에서 도 C 함수 술어 로 번역 된다.그러나 함수 호출 과 반환 비용 을 피하 기 위해 Erlang 의 장점 은 GNU C 컴 파일 러 (GCC) 가 제공 하 는 새로운 가능성 이다.실제로 GCC 는 (jump 명령) 탭 을 첫 번 째 대상 으로 하고 포인터 변수의 탭 에 저장 할 수 있 도록 하 며 다음 실행 값 의 간접 점프 에서 이러한 변 수 를 지적 합 니 다.따라서 우리 의 생각 은 번역 한 WAM 이 프로필 로 나 누 어 내부 C 함수 호출 을 통 해 추가 비용 을 피 하 는 것 이다.그리고 전역 표 의 모든 주 소 를 저장 해 야 합 니 다. 모든 함수 의 첫 번 째 호출 을 초기 화해 야 합 니 다.돌아 와 서 우리 가 피 할 수 없 는 예 를 말 하면 이것 은 발생 할 것 이다.
4. 567913. 모든 가 지 는 하나의 전체 주소 표를 통 해 goto 를 간접 합 니 다.직접 이동 하 는 비용 을 간접 적 으로 대체 하기 위해 Erlang 은 KL1 이나 Janus 처럼 주어진 모듈 의 모든 서술 어 를 하나의 단일 기능 으로 컴 파일 합 니 다.따라서 추가 모듈 호출 만 전역 주소 표 의 문의 가 필요 하고 이 내부 모듈 호출 이 더욱 비싸다.
관찰 지점 은 함수 내부 에 직접 있 습 니 다. 서문 을 피 했 기 때문에 국부 변 수 를 사용 할 수 없습니다 (C 스 택 에 보존 공간 이 없 음). 이 는 국부 변수 만 사용 하 는 것 을 의미 합 니 다.또 주의해 야 할 것 은 어떤 명령 도 전항 라벨 을 움 직 이지 않 아야 한 다 는 것 이다. 이것 은 상당히 보장 하기 어렵다.전역 표 의 요소 에 대한 접근 을 고려 합 시다.이것 은 주소 표 의 부하 로 컴 파일 되 었 으 며, 그 다음은 주어진 요소 에 접근 하 는 명령 표 의 주소 입 니 다.컴 파 일 러 는 테이블 의 접근 을 임의로 최적화 할 수 있 으 며 함수 의 시작 부분 에 테이블 의 주 소 를 설치 할 수 있 습 니 다. 이것 은 테이블 이 시종 실 행 될 것 이 라 고 가정 합 니 다.함수 내 jmp 일 때 문제 가 발생 하고 초기 화 되 지 않 은 레지스터 를 사용 하려 고 시도 합 니 다.