lambda 8cc
1.0.0
Lambda-8CC는 모 놀리 식 폐쇄되지 않은 람다 미적분학 용어로 작성된 X86 C 컴파일러입니다.
문자 크기의 종이에 인쇄되면 22MB PDF에서 길이가 18,506 페이지가됩니다. PDF는 여기 내 Github 페이지에서 볼 수 있습니다. 라텍스 소스는 448MB이고 라텍스 컴파일 로그 파일 main.log 284MB입니다. 나는 라텍스가 그렇게 할 수 있다고 믿을 수 없었다.
이 거대한 Lambda 미적분학 용어는 C 컴파일러입니다. 다음은 오류없이 GCC에서 컴파일하는 프로그램 인 Rot13.c입니다. X86/x86-64 Linux에서 실행 가능한 X86 실행 ROT13.BIN을 생성하는 Lambda-8CC를 사용하여 동일한 프로그램을 컴파일 할 수 있습니다.
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !거대한 크기에도 불구하고 ROT13.C는 Lambda 미적분학 통역사를 사용하여 내 컴퓨터에서 8 분 안에 마감됩니다. 이 repo를 복제하여 자신의 PC에서 시도해 볼 수 있습니다. 실행 시간 통계는 실행 시간 및 메모리 사용 섹션에 요약되어 있습니다. 컴파일에 시간이 걸리지 만 컴파일 된 바이너리는 즉시 실행됩니다.
추가 기능으로 Lambda-8CC는 C를 X86으로 컴파일 할 수있을뿐만 아니라 C를 Lambda 미적분학 용어로 컴파일하여 ROT13.lam과 같은 것을 생성 할 수도 있습니다. 컴파일 된 Lambda 용어는 Lambda-8CC 자체를 실행하는 데 사용되는 동일한 Lambda 미적분학 통역사에서 실행됩니다.
Lambda-8CC는 컴파일 옵션을 사용하여 C를 5 개의 다른 형식으로 컴파일 할 수 있습니다. 다음은 기능의 전체 목록입니다.
목록 중에는 8 개의 지침 만있는 최소의 명령 언어 BF와 유사하게 4 명의 내장 연산자 만있는 최소 순수한 기능 언어 인 Lazy K가 있습니다. 블로그 게시물에서도 조금 다루었습니다.
Lambda-8CC는 다음과 같은 3 가지 프로젝트를 기반으로합니다. 첫 번째 프로젝트는이 REPO Hikaru Ikuta의 저자가 작성한 Lambdavm입니다. 이것은 Rui Ueyama의 8CC와 Shinichiro Hamaji의 ELVM의 수정 된 버전과 결합됩니다.
PDF의 첫 페이지는 다음과 같습니다. 왼쪽 상단의 페이지 수에 주목하십시오.
그랜드 피날레는 오른쪽 괄호로 가득 찬 페이지로 박수를 보냅니다.
Lambda-8CC는 폐쇄되지 않은 람다 미적분 용어로 작성되었습니다
여기서도 문자열조차도 람다 용어로 인코딩됩니다. 문자와 바이트는 비트 목록으로 인코딩됩니다.
따라서 정수를 포함하여 계산 프로세스의 모든 것은 람다 유형이 아닌 객체를 소개 할 필요없이 순수한 람다 용어의 세계에서 닫힙니다. Lambdas 이외의 원시 유형을 사용하지 않습니다. Lambda-8CC는 베타를 X86으로 컴파일하기위한 유일한 요구 사항을 베타 감소시킵니다. 프로세스는 변수 이름의 선택에 의존하지 않습니다. 문자 A 이름과 변수로 인코딩하는 대신 A 는 01000001 인코딩 ASCII의 비트 목록으로 인코딩됩니다.
인코딩 프로세스는 최소한 손으로 할 말이 약간 번거 롭습니다. 이것은 Lambda 미적분학 통역사를 사용하여 해결할 수 있습니다. 다양한 Lambda 미적분학 통역사는이 I/O 형식을 자동으로 처리하여 터미널에서 실행됩니다. 표준 입력은 Lambda 항으로 인코딩되고 출력 Lambda 용어가 디코딩되어 터미널에 표시됩니다. 이러한 통역사를 사용하여 Lambda-8CC는 터미널에서 실행하여 GCC와 같은 C 프로그램을 컴파일 할 수 있습니다.
I/O 처리 방법 및 Lambda Calculus로 프로그램이 작성되는 방법에 대한 자세한 내용은 다른 프로젝트 Lambdalisp의 구현 세부 정보 인 LISP 통역사의 구현 세부 정보를 참조하십시오.
X86 외에도 Lambda-8CC는 C를 Lambda 미적분학에도 컴파일 할 수 있습니다. 출력 프로그램은 Lambda-8CC 자체를 실행하는 데 사용되는 동일한 Lambda 미적분학 통역사에서 실행됩니다. 편집 된 Lambda 용어는 Justine Tunney가 작성한 521 바이트 Lambda Calculus 통역사 Sectorlambda와 John Tromp가 작성한 IOCCC 2012 "가장 기능적인"통역과 같은 최소한의 통역사에서도 실행됩니다 (소스 소스는 λ의 모양입니다). 이것은 Lambda-8CC가 Lambda 미적분의 영역에 자체 포함됩니다.
컴퓨터 과학에서 Lambda 미적분학은 틸트가 완성 된 것으로 오랫동안 알려져 왔습니다. Lambda-8CC는 C 프로그램이 Lambda 미적분학 용어로 직접 컴파일 될 수 있음을 보여줌으로써 다소 간단하게 보여줍니다.
Lambda 미적분학의 좋은 점은 언어 사양이 매우 간단하다는 것입니다. Lambda-8CC를 사용하면 시대를 초월한 방법으로 C를 컴파일하는 방법에 대한 지식을 보존하고 있습니다. 람다 미적분학의 규칙을 기억하고 람다 -8cc에 대한 람다 용어를 가지고있는 한 인류가 x86 명령 세트에 대한 지식을 잃어 버려도 Lambda-8CC를 통해 전체 C 언어를 사용하고 다시 모든 것을 만들 수 있습니다.
다음은 ROT13 암호에 대한 표준 입력을 인코딩/디코딩하는 프로그램 ROT13.c입니다. GCC를 사용하여 오류없이 컴파일합니다.
// rot13.c: Encodes/decodes standard input to/from the ROT13 cipher
#define EOF -1
int putchar ( int c );
char getchar ( void );
char c ;
int offset ;
int main ( void ) {
for (;;) {
c = getchar ();
if ( c == EOF ) {
break ;
}
offset = 0 ;
if (( 'a' <= c && c < 'n' ) || ( 'A' <= c && c < 'N' )) {
offset = 13 ;
} else if (( 'n' <= c && c <= 'z' ) || ( 'N' <= c && c <= 'Z' )) {
offset = -13 ;
}
putchar ( c + offset );
}
return 0 ;
}동일한 프로그램은 다음과 같이 Lambda-8CC에서 컴파일 될 수 있습니다.
먼저 도구를 구축하고 Lambda-8CC를 준비하십시오.
$ make tools # Build the interpreter uni++ and the tools lam2bin, asc2bin
$ unzip bin/lambda-8cc.lam.zip
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin > lambda-8cc.Blc # Prepare format for uni++요구 사항은 다음과 같습니다.
uni++ 빌딩을위한 clang++lam2bin 및 asc2bin 빌딩 용 gcc 또는 cc여기에 제작 된 도구는 다음과 같습니다.
uni++ : Melvin Zhang이 작성한 매우 빠른 Lambda 미적분학 통역사.lam2bin : Justine Tunney (https://justine.lol/lambda/에서 사용 가능)가 작성한 유틸리티는 xx 와 같은 일반 Lambda 미적분학 표기법을 Binary Lambda Calculus 표기법으로 변환합니다.asc2bin : 0/1 ASCII 비트 스트림을 바이트에 포장하는 유틸리티.이 도구는 Lambda 미적분학 개발 키트를 통해 구축됩니다.
Lambda-8cc.lam에서 Lambda-8cc.blc 로의 전환은 단순히 통역사 UNI ++가 수락 한 형식에 대한 표기법의 변환입니다. 세부 사항은 자세히 설명되어 있습니다 .md.
그런 다음 rot13.c는 다음과 같이 컴파일 될 수 있습니다.
$ cat lambda-8cc.Blc examples/rot13.c | bin/uni++ -o > a.out
$ chmod 755 a.out
$ echo ' Hello, world! ' | ./a.out
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./a.out
Hello, world ! 이것은 내 컴퓨터에서 약 8 분 안에 실행됩니다. 그러나 조심하십시오 - 그것을 실행하려면 145GB의 메모리가 필요합니다! 무료 저장 공간 또는 USB 드라이브가있는 경우 mkswap 및 swapon 있는 스왑 파일을 사용하여 파티션 설정을 구성하지 않고 스왑을 확장 할 수 있습니다. 또한 어셈블리 및 X86 실행 가능을 별도로 컴파일하면 자세한 사용 섹션과 같이 RAM 사용량을 65GB로 절반으로 절반으로 절반으로 줄일 수 있습니다. putchar.c와 같은 작은 프로그램은 약 40GB의 메모리 만 사용합니다. 아직 확인하지는 않았지만 Mark-and-Sweep GC를 통역사에게 도입하여 RAM 사용을 줄일 수 있다고 생각합니다.
더 많은 실행 시간 통계는 실행 시간 및 메모리 사용 섹션에서 사용할 수 있습니다. 더 많은 예제 C 프로그램 Lambda-8CC가 편집 할 수있는 프로그램은 ./examples 아래에서 찾을 수 있습니다.
다른 컴파일 옵션은 자세한 사용 섹션에 설명되어 있습니다.
람다 미적분학, 당연히 Lambda-8CC의 편집 옵션은 Lambda 미적분학 용어로 표현됩니다. 이 옵션은 Lambda-8CC의 전체 기능을 잠금 해제하는 데 사용될 수 있습니다.
컴파일 옵션은 입력을 미리 AS (lambda-8cc option) 로 적용하여 사용됩니다. 이것은 Lambda Term lambda-8cc 의 동작을 변경하여 다른 입력/출력 형식을 수락/생성합니다.
다음은 Lambda-8CC의 편집 옵션입니다.
| 입력 | 산출 | 컴파일 옵션 |
|---|---|---|
| 기음 | x86 실행 가능 | |
| 기음 | 일반 텍스트 람다 미적분 용어 | |
| 기음 | 이진 람다 미적분학 표기법 (BLC 프로그램) | |
| 기음 | 스키 콤비네이터 미적분학 (Lazy K 프로그램) | |
| 기음 | ELVM 어셈블리 | |
| ELVM 어셈블리 | x86 실행 가능 | |
| ELVM 어셈블리 | 일반 텍스트 람다 미적분 용어 | |
| ELVM 어셈블리 | 이진 람다 미적분학 표기법 (BLC 프로그램) | |
| ELVM 어셈블리 | 스키 콤비네이터 미적분학 (Lazy K 프로그램) |
각 옵션은 3- 튜플 형식입니다
이전에 표시된 컴파일 옵션은 다음과 같이 터미널에서 사용할 수 있습니다.
ELVM 어셈블리 목록에 C를 컴파일하려면 as
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.x) (\x.\y.\z.\a.\b.b) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat input.c ) | bin/uni++ -o > a.s x86 실행 파일 a.out 에 as ELVM 어셈블리 목록을 컴파일하려면 :
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.y) (\x.\y.\z.\a.\b.x) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat a.s ) | bin/uni++ -o > a.out
chmod 755 a.out 앞에서 설명한 바와 같이, 이러한 명령을 사용하여 as 및 a.out 를 별도로 컴파일하여 각 프로세스가 완료되면 메모리가 해제되기 때문에 최대 RAM 사용량을 절반으로 절단 할 수 있습니다.
입력이나 옵션없이 Lambda-8CC를 실행하면 전체 옵션 세트를 보여주는 사용 메시지를 볼 수 있습니다.
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin | bin/uni++ -o
lambda-8cc v1.0.0
Usage:
apply lambda-8cc.lam [input-file]
apply lambda-8cc.lam [option] [input-file]
Options:
(f.(f [input] [output] (x.x)))
(f.(f (x.y.x) (x.y.z.a.b.x) (x.x))) : C to x86 (defualt)
(f.(f (x.y.x) (x.y.z.a.b.y) (x.x))) : C to *.lam (plaintext lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.z) (x.x))) : C to *.blc (binary lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.a) (x.x))) : C to *.lazy (SKI combinator calculus, as a Lazy K program)
(f.(f (x.y.x) (x.y.z.a.b.b) (x.x))) : C to ELVM assembly
(f.(f (x.y.y) (x.y.z.a.b.x) (x.x))) : ELVM assembly to x86
(f.(f (x.y.y) (x.y.z.a.b.y) (x.x))) : ELVM assembly to *.lam
(f.(f (x.y.y) (x.y.z.a.b.z) (x.x))) : ELVM assembly to *.blc
(f.(f (x.y.y) (x.y.z.a.b.a) (x.x))) : ELVM assembly to *.lazy
lambda-8cc includes the following projects. All of the following projects
are released under the MIT license. See the LICENSE in each location for details.
8cc: By Rui Ueyama - https://github.com/rui314/8cc
ELVM: By Shinichiro Hamaji - https://github.com/shinh/elvm
LambdaVM: By Hikaru Ikuta - https://github.com/woodrush/lambdavm
lambda-8cc: By Hikaru Ikuta - https://github.com/woodrush/lambda-8cc
다음 표는 Melvin Zhang의 Lambda Calculus 통역사의 편집 시간 및 메모리 사용을 보여줍니다.
| 프로그램 | 컴파일 시간 | 맥스. 컴파일 시간에 RAM 사용 | x86 이진 크기 | 설명 |
|---|---|---|---|---|
| putchar.c | 1.8 분 | 31GB | 342 바이트 | 인쇄 A |
| 안녕하세요 .C | 2.4 분 | 42GB | 802 바이트 | 인쇄 인쇄 Hello, world! |
| echo.c | 2.5 분 | 46GB | 663 바이트 | 표준 입력을 반향합니다 |
| rot13.c | 7.7 분 | 84GB | 2,118 바이트 | ROT13으로/에서 stdin을 인코딩/디코딩합니다 |
| fizzbuzz.c | 49.7 분 | 240GB | 5,512 바이트 | Fizzbuzz 시퀀스를 최대 30까지 인쇄합니다 |
| primes.c | 53.0 분 | 241 GB | 5,500 바이트 | 최대 100까지 인쇄합니다 |
이제 그것은 많은 기억입니다! 거대한 RAM이 필요한 프로그램을 컴파일하려면 스왑 파일을 사용하여 파티션 설정을 변경하지 않고 스왑 영역을 확장 할 수 있습니다. Linux를 실행하고 무료 스토리지 또는 USB 드라이브가있는 경우 해당 스토리지를 사용하여 mkswap 및 swapon 사용하여 스왑 영역을 쉽고 동적으로 확장 할 수 있습니다. 이 테이블의 통계는이 방법으로 확장 된 스왑 영역으로 실행됩니다. 이 askubuntu 스레드에 지침이 설명되어 있습니다. 아직 확인하지는 않았지만 Mark-and-Sweep GC를 통역사에게 도입하여 RAM 사용을 줄일 수 있다고 생각합니다.
컴파일 시간입니다. 컴파일 된 x86 바이너리의 실행 시간은 순간적입니다. 이것은 C를 Lambda 미적분학 용어로 컴파일 할 때도 유지됩니다. 편집 된 Lambda 용어는 즉시 실행되며 Lambda 미적분학 통역사에서 실행될 때 몇 기가 바이트의 메모리 만 사용합니다.
이 통계의 편집은 48GB RAM, 16GB SSD 스왑 (기본 파티션) 및 274GB (256GIB) HDD 스왑 ( mkswap 및 swapon 과 함께 동적으로 추가)을 갖춘 우분투 22.04.1 기계에서 실행되었습니다. 여기에 표시된 실행 시간은 메모리 작업을 포함한 벽 시계 실행 시간입니다. 스왑이 많은 프로그램의 경우 더 빠른 I/O 속도를 가진 장치를 사용하여 실행 시간을 줄일 수 있습니다.
통계는 달리기를 통해 측정되었습니다
cp examples/[program].c ./input.c
make 전체 메모리 사용량을 저장 input.c a.out as . 각 패스에 대한 더 자세한 통계 테이블이 자세히 표시됩니다 .md.
세부 사항을 참조하십시오 .md.
Source의 건축에 대한 자세한 내용은 세부 사항을 참조하십시오 .md.
Lambda-8CC는 3 개의 프로젝트, Lambdavm, Elvm 및 8CC의 조합입니다. Lambdavm 은이 저장소 (Lambda-8CC)의 저자 인 Hikaru Ikuta에 의해 작성되었습니다. ELVM 아키텍처는 Shinichiro Hamaji가 작성했습니다. 8CC는 Rui Ueyama에 의해 작성되었습니다. Lambda-8CC에 사용되는 8CC 버전은 Shinichiro Hamaji 및 기타에 의해 수정 된 ELVM의 일부로 포함 된 8CC의 수정 된 버전입니다. Lambda-8CC에는 또한 Shinichiro Hamaji가 작성한 ELC의 일부인 ELC가 포함되어 Hikaru Ikuta가 수정하여 ELVM 어셈블리를 Lambda Calculus로 컴파일 할 수 있습니다. ELVM의 Lambda 미적분학 백엔드는 Lambdavm을 ELVM에 통합하여 Hikaru Ikuta에 의해 작성되었습니다. 실행 시간 및 메모리 사용 통계는 Melvin Zhang이 작성한 Lambda Calculus 통역사를 사용하여 측정되었습니다. Lam2bin은 Justine Tunney가 작성했습니다.
