Restructor는 코드 전체를 자동으로 중복 없는 형태로 바꾸려 한다

Restructor는 코드베이스 전체를 자동으로 리팩터링해 중복이 가장 적은 형태, 즉 정규형으로 만드는 시스템이자 알고리즘이다. 2005년부터 2010년까지 진행한 연구 프로젝트로, 지금까지 두 가지 프로토타입을 만들었다.

동기와 한계

코드 품질 문제의 상당수는 추상화가 부족해 코드를 복사해 붙여 넣거나, 반대로 지나치게 설계하는 데서 비롯된다는 생각이 출발점이다. 어느 한쪽으로 치우치지 않으려면 계속 리팩터링해야 하지만, 코드베이스가 커질수록 그 작업은 훨씬 어려워진다. 리팩터링을 미루면 나중의 리팩터링은 더 힘들어지고, 코드가 ‘신선할’ 때 가장 쉬운 리팩터링을 놓치면서 이후 변경도 어려워지고 오류가 생기기 쉬워진다.

가장 단순하면서도 효과적인 리팩터링은 ‘코드 압축’이다. 같은 코드가 두 번 나타나면 함수 호출로 바꾸고, 호출자가 하나만 남은 함수는 인라인으로 되돌린다. 사람에게는 몹시 지루한 알고리즘이지만 컴퓨터에는 쉬운 작업이어야 한다.

많은 통합 개발 환경(IDE)이 리팩터링 기능을 제공하지만, Restructor가 하려는 일은 그와 다르다. 코드베이스 전체를 한꺼번에 살펴 모든 코드를 자동으로 정리하고, 더는 개선할 부분을 찾지 못할 때까지 작업하도록 설계됐다. 프로그램에서 코드를 복사하고, 옮기고, 지운 다음 버튼을 누르면 모든 코드가 ‘한 번, 오직 한 번(Once and Only Once)’ 원칙을 따르게 하는 모습을 상상하면 된다.

프로토타입

가장 완성도가 높은 것은 C#과 WPF로 만든 프로토타입이다. 아래에는 무작위 테스트 코드 예제가 있다.

이 프로토타입에는 익숙한 텍스트 언어와 최대한 비슷하게 코드를 보여주려는 시각적 프로그래밍 환경이 들어 있다. 내부적으로는 트리 기반 편집기지만, 모든 노드와 삽입 내용을 텍스트 코드로 서로 변환할 수 있어 익숙한 방식으로 편집할 수 있다. 구문 분석이나 타입 오류는 즉시 표시한다. 노드를 빨간색으로 보여주고, 마우스를 올리면 오류가 나타난다. 간단한 디버깅 기능도 통합돼 있다.

내장 Restructor 언어를 위한 파서, 타입 검사기, 코드 생성기도 제공한다. 타입 검사기는 제네릭을 처리한다. 코드 생성기는 CLR 바이트코드를 직접 출력하므로 편리하고 빠르며, 독립 실행 파일을 저장할 수 있다.

예제

간단한 예제부터 보자. 시작 코드는 다음과 같다.

((1 - 3) + (1 - 4)) * ((2 - 7) + (2 - 6))

결과에서는 반복되는 +와 - 표현식을 각각 나타내는 함수 b와 a가 만들어졌다. 또 a의 왼쪽 항이 b의 양쪽에서 항상 같다는 점을 찾아내 b 함수의 인자로 만들었다. 이 값은 a에서는 자유 변수로 표시되며([]로 나타냄), a는 들여쓰기로 표시된 것처럼 b 안의 지역 함수다.

부작용도 올바르게 처리하는 예제는 다음과 같다.

x = 2 => ((x = 3) + x) * ((x = 5) + 4)

이 코드는 변수 x를 만든 뒤 비슷한 방식으로 두 번 값을 대입한다. 알고리즘은 (A = B) + C 패턴을 함수로 만들려 한다. 그러면 x가 인자가 되지만, 첫 번째 출현이 이를 막는다. 첫 번째 출현에서 x를 인자로 넘기면 값은 2가 되지만, 실제로는 그 표현식을 평가할 때 3이어야 하기 때문이다. 이 언어는 왼쪽에서 오른쪽으로 엄격하게 즉시 평가한다.

알고리즘은 이 순서 의존성을 찾아 x를 함수로 만들고, 필요한 시점마다 평가되도록 한다. !는 함수 평가를 강제하는 축약 표기다. 보통은 따라가기 쉽도록 이런 함수를 인라인으로 보여주겠지만, 그 기능은 아직 구현되지 않았다.

이 예제는 단순하지만 어떤 크기의 코드에도 적용된다. 다음 코드는 코드를 여러 번 무작위로 복사해 붙여 넣은 결과이며, 사람은 구조를 찾기 매우 어렵다.

2+4*3-6+1*9-2+4*3-6+1*9-5+7*6*8-2+4*3-6+1*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+7*2+4* 3-2+4*3-6+2+4*3-6+1*9-5+2+4*3-6+1*9-2+4*3-6+1*9-2+4*3-6+1*9-5+7*6*8-2+4*3-6+1*9- 5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+7*2+4*3-2+4*3-6+2+4*2+4*3-6+1*9-2+4*3-6+1*9-5+7*6* 8-2+4*3-6+1*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+7*2+4*3-2+4*3-6+2+4*3-6+1*9-5+2+4*3- 6+1*9-5+7*6*8-7*2+4*3-6+1*9-5+7*6*8-7*8-2+4*3-6+1*9-2+4*3-6+1*9-5+7*6*8-2+4*3-6+ 1*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+7*2+4*3-2+4*3-6+2+4*3-6+1*9-5+2+4*3-6+1*9-5+7* 6*8-7*2+4*3-6+1*9-5+7*2+4*3-6+1*9-2+4*3-6+1*9-5+7*6*8-2+4*3-6+1*9-5+2+4*3-6+1*9- 5+7*6*8-7*6*8-7+7*2+4*3-2+4*3-6+2+4*3-6+1*9-5+2+4*3-2+4*3-6+1*9-2+4*3-6+1*9-5+7* 6*8-2+4*3-6+1*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+7*2+4*3-2+4*3-6+2+4*3-6+1*9-5+2+4* 3-6+1*9-5+7*6*8-7*2+4*3-6+1*9-5+7*6*8-7*8-7*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+1*9- 5+7*6*8-7*8-7+1*9-5+7*6*8-7*2+4*3-6+1*9-5+7*6*8-7*8-7*9-5+2+4*3-6+1*9-5+7*6*8-7* 6*8-7+1*9-5+7*6*8-7*8-7*8-7*8-7*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+1*9-5+7*6*8-7*8- 7*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+1*9-5+7*6*8-7*8-7-6+1*9-5+2+4*3-6+1*9-5+7*6*8- 7*2+4*3-6+1*9-5+7*6*8-7*8-7*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+1*9-5+7*6*8-7*8-7+7* 6*8-7*2+4*3-6+1*9-5+7*6*8-7*8-7*9-5+2+4*3-6+1*9-5+7*6*8-7*6*8-7+1*9-5+7*6*8-7*8-7

Restructor는 이 코드를 다음과 같은 복잡한 코드로 바꾼다.

변환된 결과가 반드시 읽기 쉬운 것은 아니지만, 중복은 완전히 제거돼 있다. 모든 코드 구조는 정확히 한 번만 나타나며, 가장 자주 반복되는 코드 구조가 가장 단순한 추상화가 되도록 함수가 선택된다.

자동 재구성이 낳는 문제

이론상 그럴듯한 Restructor가 왜 ‘소프트웨어 위기’의 해답은 아닐 수 있을까?

자동 재구성은 프로그래머의 정신적 모델을 무너뜨릴 수 있다. 책과 서류 더미로 가득한 교수의 사무실을 떠올려 보자. 몰래 사무실에 들어가 책 더미를 전부 재배치한 뒤, 돌아온 교수에게 “책을 색깔별로 정리해 뒀다”고 말하면 기뻐할까, 아니면 화를 낼까? 아마 후자일 것이다.

프로그래머도 비슷한 일을 겪을 수 있다. 코드에 대한 이해는 소스 코드의 구조와 이름 등 여러 세부 사항에 깊이 연결될 수 있다. Restructor 알고리즘은 전역적으로 작동하므로 많은 코드를 옮길 수 있다. 특히 호출자 집합에 따라 코드가 함수 안팎으로 이동하면서 함수 경계가 계속 달라질 수 있다.

이를 피할 방법은 있지만 쉽지 않다.

• 이름을 함수가 아니라 표현식에 연결하면 코드가 이동해도 이름을 유지할 수 있다.
• 리팩터링된 코드가 원래 코드가 있던 위치와 가까이 놓이도록 정렬하는 방법이 필요하다.
• 기존의 큰 코드베이스보다 Restructor 기반 언어로 새 프로젝트를 시작하는 편이 나을 수 있다. 기존 코드에 적용하면 방향 감각을 잃을 정도로 혼란스러울 수 있다.
• 고유한 편집을 할 때마다, 가능한 한 자주 Restructor를 실행하는 편이 좋다. 그러면 편집기가 변경된 부분을 차이 비교처럼 강조해 새 코드 구조를 따라갈 수 있고, 필요하면 새로 생긴 함수에 이름을 붙여 혼란을 줄일 수 있다.
• 한 번에 리팩터링 하나만 허용해 알고리즘을 전역적으로 작동하지 않게 할 수도 있다. 현재 알고리즘은 최종 결과를 만들기 위해 수많은 작은 리팩터링을 수행하므로 이 방식을 지원하지 않는다. 하지만 구현할 수는 있을 것이다. 프로그래머가 변화를 더 쉽게 따라갈 수 있고, 한 번도 리팩터링하지 않은 기존 코드베이스도 점진적으로 개선할 수 있다는 장점이 있다.
• 데이터 흐름 그래프처럼 이름이 적고 코드 구성에 대한 기대도 적은 그래픽 언어를 대상으로 만들 수도 있다.

여러 사람이 함께하는 프로젝트에도 잘 맞지 않을 수 있다. 코드가 이리저리 이동해 생기는 혼란은 여러 사람이 같은 코드베이스를 작업할 때 훨씬 커진다. 바뀌는 부분이 많아 코드를 병합하기 어렵고, 다른 사람이 동시에 편집하고 리팩터링하는 상황을 공유 편집 환경에서 처리하는 것도 쉽지 않다.

여러 사람이 작업할 때 현실적으로 가능한 방법은 각자가 서로 격리된 하위 시스템을 맡고, 리팩터링 대상이 아닌 인터페이스를 통해 통신하게 하는 것이다. 그러나 이 방식은 모듈을 넘나드는 리팩터링을 놓치고 전체 코드베이스의 품질이 떨어지도록 둘 수 있다. 오랫동안 손대지 않은 코드베이스는 구조가 완전히 달라져 있을 수 있으므로, 사람들이 그 코드에 대한 지식을 유지하기도 어렵다.

Restructor는 기존 언어 대부분과 잘 맞지 않는다. 앞서 소개한 프로토타입이 새 언어와 편집 환경을 쓰는 이유도 여기에 있다. 프로그래머가 이런 시스템을 불편 없이 쓰게 만드는 일은 어렵다. 처음부터 시스템에 맞춰 설계할 수 있는 새 언어가 더 나은 경험을 제공할 가능성이 크다.

기존 언어에서도 구현할 수 있지만 결과 코드가 낯설게 보일 수 있다. 코드를 자유롭게 옮기려면 부작용이 있거나 실행 횟수가 1이 아닌 0..N회인 코드도 이동할 수 있어야 한다. 예를 들어 다음 코드가 있다.

for (int i = 0; i < max; i++) print(i); for (int i = 0; i < max; i++) sum += i;

알고리즘은 루프를 함수로 만들고 본문을 인자로 삼아야 한다. 그러려면 인자가 함수 값, 즉 람다가 되어야 한다. 많은 언어에서 람다의 타입과 값 표기는 장황하고 어색하다. Restructor는 람다를 많이 도입할 수 있고, 많은 프로그래머가 이를 따라가기 어렵다고 느낄 수 있다. 하지만 람다가 필요하지 않은 코드만 리팩터링하도록 제한하면 임의로 많은 리팩터링을 놓치게 된다.

새 언어라면 람다를 장황하지 않으면서도 명확하게 표현하고, 가능하면 람다의 필요성을 줄이는 언어 기능을 도입할 수 있다. 예를 들어 가능한 곳에서 함수형 기능을 더 많이 사용할 수 있다.

알고리즘의 세부 내용

자료 구조는 다음과 같다.

• AST 노드는 타입과 자식 노드 목록을 가진다.
• 노드 타입은 실제로 계층 구조의 객체다. 리터럴이나 함수의 인자 목록처럼 자식 노드 이외의 정보를 저장한다.
• 프로그램은 함수 목록이며, 각 함수는 루트 노드를 하나씩 가진다.
• 임시 자료 구조인 TwoNode는 노드 두 개의 튜플이며, 항상 부모 노드와 그 자식 노드 하나를 가리킨다.

알고리즘은 리팩터링할 항목이 남아 있는 동안 한 차례씩 반복한다.

• 코드를 모두 순회하며 가능한 모든 TwoNode를 찾는다. 가능한 각 종류의 TwoNode를 키로, 해당 구조가 나타나는 위치 목록을 값으로 하는 맵에 넣는다. 이 단계에서 코드 안의 구조적으로 같은 복사본을 모은다. 예를 들어 (1 + 2) * (1 + 3)에서는 인덱스 0에 있는 자식 1과 부모 +로 이루어진 TwoNode가 가장 많이 나타난다. 리팩터링은 구조를 바꾸므로 각 노드는 TwoNode 하나에만 참여할 수 있다. 참여하지 못한 조합은 다음 반복에서 찾을 수 있다.
• 목록에 항목이 두 개 이상인 맵 항목을 모두 전체 목록에 넣고, 출현 횟수로 정렬한다. 이 목록이 비어 있으면 리팩터링을 마친다.
• 전체 목록을 출현 횟수가 많은 순서로 훑는다. 각 TwoNode를 본문으로 하는 새 함수를 만든다. 해당 부모의 다른 자식과 해당 자식의 모든 자식을 위한 자리표시자를 만든다. 자식이 이미 자리표시자라면 새 함수의 자유 변수가 된다. 두 노드 중 하나가 함수라면 그 함수의 자유 변수도 새 함수에 추가한다. 예를 들어 자식이 자리표시자가 아니라면 함수는 f(x) = 1 + x가 될 수 있다.

모든 출현 위치를 지배하는 가장 가까운 공통 조상 함수를 찾아 새 함수를 가능한 한 지역적으로 정의하고, 이를 부모 함수로 삼는다. 모든 함수가 전역 함수라면 이 작업은 생략할 수 있다.

자식이 마지막 자식이 아니라면, 즉 다른 자식과의 평가 순서가 바뀔 수 있다면 추가 처리가 필요하다. 자식의 모든 자식에서 부작용을 찾으며, 이때 해당 노드에서 시작하는 호출 그래프 전체를 고려한다. 부작용이 있으면 뒤에 오는 각 자식과 그 자식의 모든 출현 위치에 대해 두 자식의 순서가 서로 의존하는지 확인한다. 예를 들어 g(a = 1, a)와 g(a, a = 1)은 순서에 의존하지만 g(a = 1, b)는 그렇지 않다. 다른 자식이 순서에 의존하면 일반 인자로 만들 수 없다. 대신 함수 값 인자로 만들어 일반 순서 평가를 적용하고 평가 순서가 바뀌지 않게 한다. 그런 다음 모든 출현을 새 함수로 바꾼다. 예를 들어 표현식은 f(2) * f(3)이 된다. 모든 출현에서 인자 값이 같으면 해당 인자들을 합친다.

• 호출자가 하나뿐인 모든 함수는 인라인으로 바꾼다. 앞 단계에서는 본문이 노드 하나뿐인 작은 함수가 많이 생기므로, 이 단계에서 이를 다시 가장 큰 함수로 합치고 추상화의 경계를 이동한다. 여러 번 나타나는 함수 호출이 새 함수의 자식이 될 때 호출자가 하나인 함수가 생기는 것은 위 알고리즘의 자연스러운 결과다. 두 단계를 함께 적용하면 원래 코드 구조와 무관하게 적절한 함수 경계를 찾는 ‘창발적’ 동작이 나타난다.
• 사용자가 편집한 코드를 완전히 리팩터링하려면 사용되지 않는 인자도 제거해야 한다. 그렇지 않으면 해당 인자가 리팩터링을 막을 수 있다. 이 기능은 아직 완전히 구현되지 않았다.

구현과 사용 조건

앞서 소개한 가장 완성도가 높고 최신인 프로토타입은 C#으로 작성했고, GUI에는 WPF를 사용한다. 일부는 미완성이지만 작동 방식을 실험해 볼 만큼은 구현돼 있다.

GitHub 저장소에서 받을 수 있다.

Visual Studio에서 프로젝트를 여는 것이 좋다. 처음 불러오는 코드는 Main.cs:TestCase()에 정의돼 있다. 서로 다른 테스트 사례를 시도하려면 해당 줄의 주석을 해제하거나 새 사례를 추가하면 된다. 편집기에서 시각적으로 직접 편집할 수도 있다.

WPF를 사용하므로 Mono에서는 실행되지 않는다. Linux와 OS X에서는 실행할 수 없다.

알고리즘은 Program.cs:Restructor()에서 시작한다. 위의 설명은 알고리즘의 개요이며, 같은 설명이 코드에도 주석으로 들어 있다.

언어와 개발 이력

언어는 알고리즘에 최대한 적합하도록 설계했다. 현실적인 시험 사례가 되도록 부작용을 지원하지만, 그 밖에는 리팩터링 결과를 따라가기 쉽도록 가능한 한 즉시 평가하는 함수형 언어를 지향한다.

정적으로 타입을 검사하고 map, reduce 같은 함수에 제네릭을 지원한다. 현재는 정수, 부동소수점 수, 문자열, 리스트만 있으며 객체를 정의하는 방법은 아직 없다.

C#과 비슷한 가벼운 함수 값 표기를 제공한다. 예를 들어 x => x * x처럼 쓸 수 있고, 매개변수가 둘 이상이면 ()를 쓴다. 같은 표기로 범위 안의 변수를 정의할 수도 있다. 예를 들어 x = 2 => x * x는 4와 같다.

이전 프로토타입은 C++과 wxWidgets로 만들었다. 당시 모습은 스크린샷에서 볼 수 있다. 실제로 실행하려면 파일을 내려받아 RS/restructor.exe를 실행하거나 포함된 소스 코드를 빌드하면 된다.

이전 버전은 빠르게 복잡해졌다. 그 작업을 하며 가비지 컬렉션이 있는 언어로 구현을 단순화할 방법을 떠올렸다. 평소 가비지 컬렉션을 선호하지는 않지만 복잡한 그래프를 조작할 때는 큰 도움이 된다. 더 나은 GUI 라이브러리와 즉시 코드 생성 도구도 다음 프로토타입에 C#을 선택하게 한 요인이었다.

프로토타입을 만들기까지 몇 년이 걸렸다. 지금은 꽤 분명해 보이는 알고리즘을 알아내는 데도 오래 걸렸으며, 특히 값 공유와 부작용을 다루는 방법을 찾는 데 시간이 들었다. 당시의 자료로는 아이디어를 설명하려고 작성한 논문, 시각 언어 구성을 위한 목업, 생각이 맴도는 과정을 보고 싶다면 브레인스토밍 문서가 있다.

모든 언어에서 작동하도록 만든 더 단순한 도구로 Sloppy도 있다. 다만 리팩터링은 사람이 직접 해야 한다.