5 min to read
혀엉 언어 삽질기
혀엉언어 삽질기
작년 말에 새로이 알게 된 충격적인 언어가 하나 있습니다. 바로 혀엉 언어였죠. 당시 Brainfuck이라 던지 아희라든지 난해하고 변태적인 프로그래밍 언어에 막 관심을 들인 제게 이 언어는 신선한 충격 이였습니다. 색다른 센스의 신사력과 엄청난 BL력을 지닌 이 언어는 그저 혁신 이였습니다. 그래서 한창 혀엉언어를 만지작거리면서 놀다보니 의문이 생겼습니다.
BF도 아희도 print”문자” 를 할 수 있게 만들어주는 사이트가 있던데 왜 혀엉은 없지?
이 간단하고 신사적인 질문에 저는 고민하기 시작했습니다.
그리고 결론은 “내가 만들면 된다.” 가 되었습니다.
어떻게 만들까
사실 이 부분이 문제였습니다.
하트, 물음표, 느낌표 라는 구문은 아직 제게 익숙지 않았고 이걸 이용해서 조건분기문을 만드는 건 상당히 까다로운 작업입니다. 결국 기본적인 명령어 셋만을 이용해야했고 이 점이 더 어렵게 만든 것 같습니다.
혀엉언어 생성기를 만들면서 목표를 2가지 설정했습니다.
- 최대한 짧은 코드를
- 모든 구현체에서 동작하도록
BF생성기 중 유명한 copy.sh는 코드를 생성할 때 언더플로와 오버플로를 적극적으로 활용합니다. 때문에 8bit 구현체에서만 동작하죠. 하지만 혀엉언어에는 스택에 해당 사양에 관한 언급이 없습니다. 구현체에 따라 8bit일수도 16bit일 수도 그 이상 일 수도 있죠. elm구현체에서는 32bit를 사용합니다. 하지만 역시 정해진 사양이 없기 때문에 모든 구현체에서 동작하기 위해선 언더플로나 오버플로를 활용 할 수 없습니다. 게다가 짧은 코드를 위해서라도 이는 비효율적입니다. 언더플로를 활용하면 2바이트 정도의 크기인 한국어를 만들 때 핥을 기준으로 2147429018 개의 수를 건너뛰어야 하고 혀엉에는 효율적으로 뺄셈을 할 수 있는 명령어가 없습니다. 최소한 흡(부호변경)+항(덧셈)을 해야 뺄셈을 할 수 있죠.
이리 고민을 하다 보니 끝이 나지 않을 것 같아서 우선 만들어 보기로 했습니다. (만든 방법은 뒤에 상세히 기술하겠습니다)
제가 생성할 문자의 예제는 항상 Hello, world!입니다.
비교 대상은 예제코드에 있는
혀어어어어어어어엉........ 핫. 혀엉..... 흑... 하앗... 흐윽... 형. 하앙.
혀엉.... 하앙... 흐윽... 항. 항. 형... 하앙. 흐으윽... 형... 흡... 혀엉..
하아아앗. 혀엉.. 흡... 흐읍... 형.. 하앗. 하아앙... 형... 하앙... 흐윽...
혀어어엉.. 하앙. 항. 형... 하앙. 혀엉.... 하앙. 흑... 항. 형... 흡 하앗.
혀엉..... 흑. 흣
234글자(newline 포함)짜리 코드입니다.
그리하여 완성된 첫 번째 생성기
첫 번째 생성기에 쓰인 생성전략은 단순합니다. 정말 너무 너무너무 단순해서 한숨이 나옵니다.
2018-02-07일에 생각해내고 완성시킨 첫째 전략은
아 그냥 1*출력할_문자열 하면 되지 않냐?
입니다. 형(인자간 곱셈후 PUSH)명령에 .을 출력할 문자의 값만큼 만든 다음, 항.(원래는 덧셈 여기서는 MOV처럼 사용)을 이용해서 stdout으로 보내는 방법입니다. 이 단순한 방법은 다음과 같은 결과를 만들었습니다.
형........................................................................항.
형.....................................................................................................항.
형............................................................................................................항.
형............................................................................................................항.
형...............................................................................................................항.
형............................................항.
형................................항.
형.......................................................................................................................항.
형...............................................................................................................항.
형..................................................................................................................항.
형............................................................................................................항.
형....................................................................................................항.
형.................................항.
형흑.흣
이 1204글자짜리의 과묵하고 소심한 동생의 중얼거림 같은 코드는 성공적으로 Hello, world!를 출력해냈습니다.
물론 비효율의 끝판왕 이였죠.
다음날 생각난 두 번째 생성기
두 번째 생성기는 첫 번째 생성기를 만든 다음날 아침 기상과 함께 생각났습니다.
출력할 글자의 최솟값을 구하고 해당 최솟값을 복제해서 출력할 글자 수만큼 만들고, 그 다음부터는 그 값에 덧셈만 하면 되지 않을까?
띠용! 이렇게 단순한 걸 생각하지 못하다니!
와 정말이지 또 다른 단순한 방법입니다. 흑(값 복제)명령으로 미리 글자를 부분적으로 스택에 쌓아둔다니! 사실 이 방법은 Brainfuck의 Hello World! 예제에서 착안했습니다. 먼저 4개의 다른 값을 만들고 해당 값을 복제해서 이용하는 방법인데 혀엉에서도 현재 스택을 오가면서는 쓸 수 있겠지만 별로 어울리는 방법은 아닌 거 같았습니다.
그래서 고른 것이 최솟값인데, 이런 방법으로 생성된 코드는 849자 길이의 코드가 나왔는데요.
형................................
흐으으으으으으으으으으윽...
형........................................하앙.
형.....................................................................하앙.
형............................................................................하앙.
형............................................................................하앙.
형...............................................................................하앙.
형............하앙.
형하앙.
형.......................................................................................하앙.
형...............................................................................하앙.
형..................................................................................하앙.
형............................................................................하앙.
형....................................................................하앙.
형.하앙.
형흑.흣
소심한 동생이 대성통곡하고 나서 중얼거리는 듯한 이 코드는 첫째 방법에 비해서 30% 정도 코드를 줄였습니다. 하지만 형하앙. 같은 항.으로 더 짧게 대체될 수 있는 명령이 보이는 것은 아쉽지만 이는 나중에 replace등등으로 대체할 수 있으니 내일하잫ㅎ 차후의 일로 미뤘습니다.
좀 제대로 줄여보려 만든 세 번째 생성기
2일 뒤, 주말이 되고 토요일이 오자 머릿속에 담아 두었던 생성 방법을 구현해 보자 생각이 들었습니다.
바로 소인수 분해인데요. 형......(생략)을 방지하기 위해서 먼저 소수를 체크하고 소수라면 1을 빼줍니다. 그 후 소인수 분해를 수행하면 길이를 더 줄일 수 있습니다.
혀어어엉........
흐으으으으으으으으으으윽...
혀어어어엉........하앙.
혀어엉.......................하앙.
혀어어엉...................하앙.
혀어어엉...................하앙.
혀어어어어엉.............형.하앙...하앙.
혀어어엉...하앙.
형하앙.
혀어엉.............................하앙.
혀어어어어엉.............형.하앙...하앙.
혀엉.........................................하앙.
혀어어엉...................하앙.
혀어어엉.................하앙.
형.하앙.
형흑.흣
어우 이제 좀 야릇한 코드가 되었네요. 다만 수가 (2,3,5)*소수 형태의 수를 만들어야 할 때는 아주 불리한 생성전략이 되었습니다. 하지만 소인수 분해 하나만 적용 시켰을 뿐인데 코드의 길이는 336자가 되었고 2번째 생성기에 비해 61%정도 크기를 줄일 수 있었습니다.
10개월 뒤에 다시 잡고 만든 네 번째 생성기
10개월 뒤에 다시 혀엉 언어를 잡았습니다. CTF문제를 만들다가 다시 잡게 되었는데 gist를 뒤지다가 이런걸 찾았고 앞서 만든 3개의 생성기를 봤습니다. 그리고 다시 더 길이를 줄여 보기로 했습니다.
우선은 명령어를 좀 더 짜기 편하게 만들었습니다. 각 명령어를 다음과 같이 대응되는 객체로 만들었습니다.
형=Mul(곱)
항=AccAdd(누적합)
핫=AccMul(누적곱)
흑=DupMov(복제&이동)
흡=InvAccMul(역수 변환 후 누적곱)
흣=NegAccAdd(부호 변환 후 누적합)
Typescript 공부도 해볼 겸 Typescript로 만들었습니다.
그 후, 이번에는 좀 더 깊은 생각을 해보기로 했습니다. 고1도 되었겠다, 증명에서 배운 식을 좀 써보기로 했습니다.
우선 혀엉… 명령어를 통해서 생성해야하는 값을 X라고 하고 글자(형)수를 a, 점의 수를 b, 명령구문의 길이를 Y라고 하면 \(X=ab\\ Y=a+b\\ a+b\le2\sqrt{ab}\\ Y\le2\sqrt{ab}\\ E=\{x|x\le2\sqrt{ab}\}\\ \therefore {a=b} \implies min(E)\) 즉, 최소길이의 명령구문으로 X를 생성하려면 X의 제곱근을 a, b 값으로 하면 됩니다.
하지만 글자에 정수만 들어가야 하므로 제곱수가 아닌 경우에는 나머지가 생기게 됩니다. 이 문제를 해결하기 위해 저는 다음과 같은 tactic함수를 만들었습니다.
와! 재귀 함수를 배우니 할 수 있을게 늘었네요.
정수 범위에서 한 sqrt는 단순히 sqrt를 floor를 시켜서 구현 했습니다. 그에 따라서 생기는 나머지는 다음 tactic을 시도하여서 최소 길이의 찾아내는 방식입니다.
이런 방법으로 생성된 코드는 302 글자로 34글자 줄었습니다.
혀어어엉........
흐으으으으으으으으으으으윽...
혀어어어엉........하앙.
혀어어어어어어엉........형.....하아앙.
혀어어엉...................하앙.
혀어어엉...................하앙.
혀어어어어어어엉........혀어어어엉...하아앙.
혀어어엉...하앙.
형하앙.
혀어어어어어어어엉.........혀어엉..하아앙.
혀어어어어어어엉........혀어어어엉...하아앙.
혀어어어어어어어엉.........형.하아앙.
혀어어엉...................하앙.
혀어어엉.................하앙.
형.하앙.
형흑.흣
어디 까지 줄일 수 있을까. 4번째 생성기
WIP
- 1:3 비율
- 다중 base
Comments