[PL] APL을 아십니까

projects

[PL] APL을 아십니까 - APL 소개글

ketrewq 2025. 3. 31. 14:34

1. APL이 뭔데

우리가 아는 프로그래밍 언어를 제외하고도 세상에는 수많은 언어가 존재한다. 어떠한 언어는 성공적으로 상용화되지만 어떤 언어는 애초에 유명해지지 못하기도 하고 어떤 언어는 역사의 뒤편으로 사라지기도 한다.

오늘 소개하려는 APL은 굳이 따지면 잊혀진 언어다. 60-70년대 미국에서는 많이 쓰였을지 몰라도 2025년 한국에서는 APL을 모르는 사람들이 더 많다. 그도 그럴 게 쓰일 일이 없다. 유지보수도 어렵기 때문에 write-only language라고 불리기도 한다.

APL의 시작은 수학을 좀 더 간결하게 표현하기 위해서 Ken Iverson이 기호를 끼적이다가 어? 이거... 프로그래밍 언어로 써도 꽤 잘돌아가잖아? 했던 게 시작이었다.

그런 언어를 왜 소개하려고 하는가? 재밌고 아름답기 때문이다.

2. 몇가지 예시

한 가지 예시를 보자. 아래는 파이썬으로 구현한 중국인의 나머지 정리이다. 출처

def gcd_extended(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = gcd_extended(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def find_min_x(num, rem):
    prod = 1
    for n in num:
        prod *= n

    result = 0
    for i in range(len(num)):
        prod_i = prod // num[i]
        _, inv_i, _ = gcd_extended(prod_i, num[i])
        result += rem[i] * prod_i * inv_i

    return result % prod

# Example Usage
num1 = [5, 7]
rem1 = [1, 3]
print("x is", find_min_x(num1, rem1)) 

num2 = [3, 4, 5]
rem2 = [2, 3, 1]
print("x is", find_min_x(num2, rem2))

그런 반면 아래는 APL로 구현한 중국인의 나머지 정리이다.

crt←{m|⍵+.×⍺(⊣×⊢|∘⊃{0=⍵:1 0 ⋄ (⍵∇⍵|⍺)+.×0 1,⍪1,-⌊⍺÷⍵})¨⍨⍺÷⍨m←×/⍺}

아름다울 정도로 간결하다. 솔직히 해석해야하는 코드의 밀도는 비슷하다. 처음에는 "이게 뭐가 프로그래밍 언어야" 싶겠지만 뜯어보면 APL의 미학을 이해할 수 있을 것이다.

두번째 예시는 Game of Life이다.

이런 보드게임을 코드로 구현한 것인데, APL 구현은 다음과 같다. 출처

  life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵}

이 한줄의 코드로 게임 하나가 돌아간다. 이 영상이 아마 APL 관련 영상 중 제일 유명할 것이다.

https://youtu.be/a9xAKttWgP4?si=-VO6q6evxzVHpjaK

3. 어떻게 읽는데?

재미로 중국인의 나머지 정리를 해석해보자. 완전히 이해할 필요는 없다.

crt←{m|⍵+.×⍺(⊣×⊢|∘⊃{0=⍵:1 0 ⋄ (⍵∇⍵|⍺)+.×0 1,⍪1,-⌊⍺÷⍵})¨⍨⍺÷⍨m←×/⍺}

이 코드는 좀 더 분리해서 해석할 수 있다. APL은 오른쪽에서 왼쪽으로 읽는다.

m←×/⍺

×/는 APL에서 다음에 오는 리스트 안의 모든 원소를 곱한다는 뜻이다. 예를 들어 ⍺가 [a b c]라면, ×/⍺는 a×b×c다. ←는 대입 연산자다. 이 줄에선 m에 ⍺의 모든 원소의 곱이 대입된다.

 ⍺÷⍨m

÷는 나눗셈, ⍨는 인자를 뒤집는 역할을 한다. ⍺÷⍨m은 결국 우리가 예전에 정의한 m으로 각각의 ⍺를 나누는 과정이다. 자 예를 들어 구체적으로 a, b, c가 있을 때, m = a×b×c이고, 여기서는 a÷m, b÷m, c÷m 같은 식이 된다.

그니까 (… )¨⍨⍺÷⍨m 형태로 사용하면, a÷m, b÷m, c÷m을 각각 왼쪽에 (… ) 함수에 적용하라는 뜻이 된다.

(⍵∇⍵|⍺)

재귀적으로 ⍵라는 함수를 호출한다. ⍵|⍺는 ⍺를 ⍵로 나눈 나머지다.

{0=⍵:1 0 ⋄ (⍵∇⍵|⍺)+.×0 1,⍪1,-⌊⍺÷⍵}

{ } 안의 함수는 람다 즉 익명 함수 형태다. 얘도 뜯어보자.

 0=⍵:1 0 ⋄ (...)

인자 ⍵가 0이면, 벡터 [1, 0]을 반환하라는 뜻이다. ⋄ 뒤는 그렇지 않을 때의 분기다.

+.×0 1,⍪1,-⌊⍺÷⍵

+.× 는 inner product을 의미한다. 여기서는 행렬 곱셈처럼 동작한다. 그 뒤에 오는 건 2x2 행렬을 만든다.

0 1 은 첫 번째 행 (벡터)
1,-⌊⍺÷⍵ 는 두 번째 행 (벡터)
,⍪ 는 위의 두 벡터를 “아래로 붙여서(행을 추가해서)” 2×2 행렬로 만드는 연산이다.

결과적으로 이 부분은 다음과 같은 행렬 하나를 형성한다.

[ 0 1 ]
[ 1 -⌊⍺÷⍵ ]

그런다음 +.× 로 어떤 2요소 벡터 A(예를 들자면 [x,y])를 이 행렬과 곱하면,

A +.× (이 2×2 행렬)
= A (행 벡터) × M (2×2 행렬)
= [ x×0 + y×1 , x×1 + y×(-⌊⍺÷⍵) ]
= [ y , x - y×⌊⍺÷⍵ ]

이렇게 2개의 원소를 갖는 새로운 벡터가 결과로 나온다.

결국 확장 유클리드 알고리즘이다. 반복적인 재귀/분할을 통해 (x,y)를 (y, x - q×y) 형태로 갱신하고 계산하는데, 여기서 q가 ⌊⍺÷⍵ 이 되는 식이다.

⌊⍺÷⍵

a를 b로 나눈 뒤, 소수점 이하는 버리고 정수 부분만을 취한다는 뜻이다.

다시 돌아가서,

⊢|∘⊃

⊃는 벡터에서 첫 번째 요소를 추출한다. |는 나머지(mod)를 구한다. ∘는 두 함수를 합성(composition)한다.

따라서 ⊢|∘⊃는 결과로 나온 벡터에서 특정 요소를 꺼낸 뒤, 그것에 대하여 오른쪽 인자(⊢)와 나머지 연산을 수행한다는 의미이다.

(⊣× … )

위에 나온 문양을 좌우반전 한 것처럼 생긴 게 하나 있는데. 직관적으로 이해한 바와 같이 ⊣는 왼쪽 인자를 그대로 반환하는 연산자이다.

(⊣× … )는 결국 왼쪽 인자와 …에서 나온 결과를 곱하라는 얘기다.

결국 다 종합해보면, 이는 확장 유클리드 알고리즘 결과로 얻어진 계수를 왼쪽 인자와 곱한다.

서로 다른 모듈러 여러 개에 대해 / 각 모듈러에 맞춘 어떤 나머지를 동시에 만족하는 수를 구한다. / 입력된 모듈러들의 곱을 구하고, / 각각의 모듈러에 대해 해당 곱을 나눈 뒤, / 그 결과의 모듈러 역원을 확장 유클리드 알고리즘으로 구해 / 전체 합산한다. / 마지막에 다시 원래의 곱으로 나눈 나머지를 취한다. /
그러면 유일한 해(값)를 얻을 수 있다.

이렇게 자연어로 풀어낼 수 있다. 이것이 APL로 구현한 중국인 나머지 정리이다.