대한 축구 협회 프로그래밍 랭기지를 만들어보자 되도록 튜링완전하게..

대한축구협회 프로그래밍 랭기지 KFAlang 의 레포는 여기

Lee-WonJun/KFAlang: 축구협회 프로그래밍 랭기지 (github.com)

GitHub - Lee-WonJun/KFAlang: 축구협회 프로그래밍 랭기지

축구협회 프로그래밍 랭기지. Contribute to Lee-WonJun/KFAlang development by creating an account on GitHub.

github.com

누군가 내 임기 도중 이뤄냈던 실적 에 대해 점수를 매겨보라고 한다면 10점 만점에 720점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 명예 에 대해 점수를 매겨보라고 한다면 10점 만점에 690점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 축협 에 대해 점수를 매겨보라고 한다면 10점 만점에 760점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 협회장 에 대해 점수를 매겨보라고 한다면 10점 만점에 760점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 임기 에 대해 점수를 매겨보라고 한다면 10점 만점에 320점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 협회 에 대해 점수를 매겨보라고 한다면 10점 만점에 790점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 월드컵 에 대해 점수를 매겨보라고 한다면 10점 만점에 870점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 리더십 에 대해 점수를 매겨보라고 한다면 10점 만점에 820점 정도는 된다고 대답하고 싶다
누군가 내 임기 도중 이뤄냈던 머니볼 에 대해 점수를 매겨보라고 한다면 10점 만점에 680점 정도는 된다고 대답하고 싶다

의원님께서 혹시 실적 이라는 영화 보신 적이.. 
의원님께서 혹시 명예 이라는 영화 보신 적이.. 
의원님께서 혹시 축협 이라는 영화 보신 적이.. 
의원님께서 혹시 협회장 이라는 영화 보신 적이.. 
의원님께서 혹시 협회 이라는 영화 보신 적이.. 
의원님께서 혹시 임기 이라는 영화 보신 적이.. 
의원님께서 혹시 월드컵 이라는 영화 보신 적이.. 
의원님께서 혹시 협회 이라는 영화 보신 적이.. 
의원님께서 혹시 리더십 이라는 영화 보신 적이.. 
의원님께서 혹시 협회장 이라는 영화 보신 적이.. 
의원님께서 혹시 머니볼 이라는 영화 보신 적이..

HELLO WORLD

아이디어는 어디에나 있다

슬슬 프로그래밍 언어 하나 만들때가 된거 같아서 요 며칠사이 아이디어를 구하고 있던도중 축구협회 현안 질의 방송을 보고 이거다 싶었다.

그동안 예비군이 였기때문에 안그래도 할거없는 예비군동안 문법을 좀 고민했는데, 아무래도 튜링완전에 가깝게 만들고 싶다 보니 고민을 좀 오래 했다. 튜링완전을 위해서는 기본적으로 JUMP 가 가능한 로직을 구현하면되는데, IF 분기 + GOTO 문으로 구현하려다가, 인터프리터 구현할때 좀 빡세서 WHILE 문으로 방향을 틀었다.

사용한 언어는 역시 F# 에 [주술회전 대사로 프로그래밍을 해보자] 에서 사용한 Fparsec 조합, 다만 이번에는 Monad expression 를 사용했다. 확실히 이게 편하긴 하다.

parse expression 을 사용하면 그냥 직관적으로 기술해도 파싱이 된다 와! 마법!

명언 =Equal= 문법

처음에는 KFA 관련 명언이 너무 많아서 쉽게 찾을 수 있을 줄 알았는데, 오산이었다. 말은 많지만 프로그래밍 언어로 구현하기에는 실속이 없는 경우가 많았다.

BrianFuck과 같은 난해한 프로그래밍 언어보다는 상황에 맞는, 예를 들어 변수 선언 문법에는 변수 선언에 적합한 문장을, IF 문에는 IF 문에 적합한 문장을 사용하는 언어를 만들고자 했다. 난해하지만 읽다 보면 얼추(?) 상황에 맞는 문장을 사용함으로써 이해할 수 있는 그런 언어를 만들기 위해 딱 맞는 문장을 찾아야 했다.

내가 구현하려고 하던 문법의 최소 치는 다음과 같다.

변수 선언 - 메모리에 특정 값 (정수 한정) 저장 / 갱신
사칙 연산 - 값 계산
IF + GOTO - 튜링완전을 위한 Flow Control -> 이건 While 문으로 대체 했다.
Print - 그래도 HELLO WORLD 는 출력 해야 되지 않아 싶어서..
Return / Sleep - 기타 유틸성 함수

1. 변수 선언은 "축구의 시대" 서적에 나오는

누군가 내 임기 도중 이뤄냈던 업적에 대해 점수를 매겨보라고 한다면 10점 만점에 8점은 된다고 대답하고 싶다

해당 문장을 사용하기로 처음부터 마음 먹었는데, 이게 숫자를 넣는건 자연스러운데, 변수를 사용해서 다른 변수를 초기화 하기에는 문장이 너무 어색해지므로, 다른 선언법을 추가 하였다.

2. 사칙연산의 경우, + - * / 같은 오퍼레이터가 직접적으로 사용되면, 문장이 너무 어색해지기 때문에,
짧고 간결하면서, 어느 문장에 들어가도 어색하지 않은 문장부호나 감탄사같은것을 사용하려고 했기 때문에, 현안 질의 영상에서 가장 많이 나오는 짧고 간결한 말을 채택

3. Flow Control은 IF 문으로 "이게 팀이야??"를 사용하기로 하고,
GOTO 문으로 특정 라인으로 이동하기 위해 숫자가 포함된 "전력강화위원과는 2분 30초 통화했습니다"라는 문장을 사용하여 구현하려다가, 파서까지는 다 구현했지만 깊이가 있는 상황에서 GOTO 문으로 자유롭게 점프하는 인터프리터 구현이 너무 어려워 고민을 좀 했다.
구현 자체가 복잡한 것도 있었지만, GOTO가 깊게 중첩되는 상황에서 Flow Control이 어떻게 되어야 정상적인가를 고민해봤는데, 어느 방향으로 가도 너무 애매해서 그냥 "이게 팀이야??"를 WHILE 문으로 대체하고, "전력강화위원과는 2분 30초 통화했습니다"는 숫자가 포함되어 있으니 Sleep 문으로 대체했다.

4. Print은 많이 고민했는데, 어쨌든 출력에 가까운 의미를 가진 문장을 찾아야 했다. 그런데 생각해보니 일상 대화에서 '출력'이라는 단어가 나올 리가 없어서… 어쨌든 "머니볼이라는 영화를 보신 적이…"를 Watch → 보다 → 보는 것 → 출력되어야 해서 Print라는 기적의 논법으로 사용하게 되었다.

5. 유틸성 함수에서 Sleep 은 이미 했고, Return 은 사실 굳이 필요 없는데,
"결과적으로는 제 안에 있는 무언가가 나오기 시작했습니다" <- 이 대사가 너무 찰져서(?) 쓰고 싶어서 사용했다,
Try-Catch-Finally 구문을 내가 구현했다면 아마 Finally 에 쓰지 않았을까 하는 TMI..

F# 의 ADT 표현력은 세계 제일!

ML 계열의 대수적 데이터 타입(ADT) 기술은 다른 언어에서도 빼껴 쓰고싶을정도로 깔끔하다.
Kotlin 도 많이 깔끔한 편인데, ML계열은 비교도 안될정도로 좋다

문법이 나왔으므로 AST 의 ADT 를 정의하자.

type Ops = Add | Sub | Mul | Div

type Expr =
    | Number of int
    | Variable of string
    | BinaryOp of Expr * Ops * Expr

type Statement =
    | VariableAssignment of string * Expr
    | Sleep of int
    | WhileStatement of string * Block
    | Output of string
    | Return of string
and Block = Statement list

이 아름답고 우아한 표현법을 보라.. 짜릿해 늘 새로워 잘생긴게 최고야

FParsec 근데 GPT 를 곁들인

FParsec은 F#에서 사용하는 모나딕 파서 조합기로, 풍부한 고차 함수를 제공해준다. 파서를 수동으로 직접 짜는 건 정말 개고생인데, 이런 라이브러리를 쓰면 뚝딱이다.

유일한 단점은 조합기가 너무 많고, 처음 봤을 때 이해가 안 되는 부분이 너무 많아 초기 러닝 커브가 길다는 점인데, 대 AI 시대 우리의 친구 GPT와 함께라면 문제없다. 거기에 parse monad expression 까지 쓴다면..?

let whileBlock =
    parse {
        let! _ = pstring "골 먹고 전부 다 손 들고. 이게" .>> ws
        let! var = identifierSentenceFactory ["이야??"]  |>> trim 
        let! block = many (ws >>. statement .>> optional newline)
        let! _ = pstring "전부 다 넘어지면 아! 아! 내가 분명히 얘기했지!" .>> newline
        return WhileStatement(var, block)
    }

골 먹고 전부 다 손 들고. 이게 (시작 구문, 코드에선 _ ) {identifier} (var) 이야??
내부다른 statement 들 (block)
전부 다 넘어지면 아! 아! 내가 분명히 얘기했지! (종료 구문, 코드에선 _ )

위 문법을 약간의 FParsec 조합기로 살짝만 건들어주면 바로 While 문 파서가 완성된다. 거의 자연어로 기술한 것을 그대로 가져다 쓴 정도이다.

사실 Python처럼 Depth 구분인 indentation-based으로 하려다가, 종료 구문으로 "전부 다 넘어지면 아! 아! 내가 분명히 얘기했지!"를 넣었다.

그 이유는 FParsec과 같은 Parser combinator는 대개 명확한 lexing 단계가 없어서 Depth 기반 구현이 좀 까다롭기 때문이다. 당연히 불가능한 건 아니지만, indent를 추적하면서 돌아가야 하는데 좀 까다로운 반면, end block이 명확하다면 위의 코드처럼 그냥 마지막에 검사하면 끝난다.

혹시나 Parser Combinator의 indentation based parsing에 관심 있는 사람을 위해서 몇 개 링크를 첨부… 다음 언어에서는 indentation based lang을 만들어 볼 생각.

해석해주기 전에는 그는 다만 하나의 데이터에 지나지 않았다

문장을 파싱했다면 AST, 즉 데이터가 트리 형태(리스트의 서브 리스트를 포함한 형태)로 변환된다.

이 리스트는 단순한 리스트에 불과하므로, 해석기(Interpreter)를 만들어서 해석해 줘야 한다.

복잡하지 않은 AST는 일반 DSL처럼 재귀적으로 해석해서 실행하면 된다.

프로그램의 상태를 관리해줘야 하는데,

이 언어에서는 함수가 없어서 콜 스택이 없고,
깊이별 로컬 변수도 없으므로 로컬 변수 관리를 위한 스택도 없으며,
복잡하게 이동하는 JUMP도 없으므로 명시적으로 PC용 변수(포인터)도 필요 없다.
(엄밀히 말하면 그냥 다음 줄이 다음 명령어이며, WHILE 문에서 탈출될 수 있지만, 인스트럭션을 PC로 참조하여 넘어가지 않고 인터프리터 내부에서 WHILE을 돌려서 PC 선언 없이 알아서 돌아간다.)

그래서 그냥 글로벌 변수를 저장할 스택 하나 있으면 된다. 편의상 Dictionary로 구현했다.

let interpret (program: Program) =
    let state = {
        Variables = Dictionary()
    }

    let rec exec program = 
        match program with
        | [] -> ()
        | VariableAssignment(var, expr) :: rest ->
            let value = evalExpr expr
            if state.Variables.ContainsKey(var) then
                state.Variables.[var] <- value
            else
                state.Variables.Add(var, value)
            exec rest

        | WhileStatement(var, block) :: rest ->
            while state.Variables.[var] <> 0 do
                exec block 
            exec rest

        | Sleep(seconds) :: rest ->
            System.Threading.Thread.Sleep(seconds * 1000)
            exec rest

        | Output(var) :: rest -> 
            let ascil = state.Variables.[var] |> Convert.ToChar
            printf "%c" ascil
            exec rest

        | Return(var) :: _ -> // 프로그램 완전 종료
             System.Environment.Exit(state.Variables.[var])


    and evalExpr expr =
        match expr with
        | Number(n) -> n
        | Variable(var) -> state.Variables.[var]
        | BinaryOp(x, op, y) ->
            let x' = evalExpr x
            let y' = evalExpr y
            match op with
            | Add -> x' + y'
            | Sub -> x' - y'
            | Mul -> x' * y'
            | Div -> x' / y'

    exec program
    state

더 추가하기

GitHub에 README까지 작성하고 보니, 이 언어의 불편한 점이 몇 개 눈에 띄어서 일부 수정했다.

1. 조사 관련

조사는 예를 들어, 출력을 할 때 "~이라는"을 붙여야 하는데, "축구라는 변수가 있다면 "축구이라는"처럼 애매한.. 문장이 나와서 수정했다.
만약 "축구이"라는 변수도 있다면, "축구 + 이라는" 인지, "축구이 + 라는" 인지 구분이 안가는 상황이 나오긴 하는데... 그래도 조사를 지원해주는 게 코드가 더 깔끔하게 나올 것 같아서 수정했다. (돌려보니 "축구 + 이라는" 으로 인식함)

FParsec에서는 Choice 조합기를 사용하면 된다. 아니면 <|>를 써도 된다.

2. BREAK

현재는 IF 문이 없어서 WHILE과 변수의 조합으로 IF 문을 흉내 내야 하는데, BREAK 구문이 있다면 귀찮게 변수 컨트롤을 하지 않아도 IF 문처럼 사용할 수 있으므로 BREAK 구문을 추가했다.
대략적으로 중지 관련한 대사로 "제가 사퇴하겠습니다"와 "계속 정치적으로 압박을 받으면 FIFA의 제재를 받을 수 있다, 최악의 경우엔 월드컵 본선에 못 나갈 수 있다" 두 개를 찾아서 그냥 두 가지를 모두 사용했다.

다만 WHILE 문 안에서만 사용 가능해야 하므로 WHILE 문 파서를 조금 수정

// 이 코드를
let! block = many (ws >>. statement .>> optional newline)

// 이런식으로 해서 Block 안에서만 기존 statement OR breakSign 파서를 사용 가능하도록 한다.
let statementWithBreakSign = attempt breakSign <|> statement
let! block = many (ws >>. statementWithBreakSign .>> optional newline)

그리고 이를 인터프리터에서 BREAK AST를 만나면 WHILE 문을 중단하도록 했다.
WHILE 문을 중단하려면 인터프리터 내부에서 수행 중인 Instruction의 Return 값이 필요해서 Signal 값을 리턴하도록 했고, WHILE 도중 Break Signal을 만나면 중단하도록 수정했다. 이를 구현하는 방법은 다음과 같다

// Signal 추가
type Signal = NormalSign | BreakSign

let interpret (program: Program) =
	// ...
    let rec exec program = 
        match program with
        | [] -> NormalSign 
    	// ...
        | WhileStatement(var, block) :: rest ->
            let mutable inside_continue = true
            while inside_continue && state.Variables.[var] <> 0 do
                exec block |> function 
                | Signal.BreakSign -> inside_continue <- false
                | _ -> ()
            exec rest
		// ...
        | Break :: _ ->
            Signal.BreakSign

꼭 이렇게 구현하는게 정답은 아니고

그냥예외를 일으켜서 중단하거나, (제일 쉬워보인다)
Exec 결과값을 받아서 중단하거나, (이걸썻다)
재귀 함수로 넘기는 Continuation을 조작하거나 (이게 가장 함수형스럽다).

하면 되는데 이미 편의상 While-do 문법으로 While 문을 구현했기 때문에 Exec 결과값을 넘기는 식으로 구현했다.

완성! 과 잡담

문법 -> 파싱 -> 해석만 하면 나만의 프로그래밍 언어 완성!

이렇게 주기적으로 이상한 프로그래밍 언어를 만드는것을 좋아하는데,

프로그래밍 언어를 만드는 것은 프로그래밍의 정수를 담고 있다.

문법을 생각하고 적용하는 것은 설계와 추상화이며, 의도가 잘 전달되도록 어떻게 해야 할지 고민하게 된다.

안전하게 파싱하는 것은 외부 도메인 특화 언어(external DSL)를 개발할 때 매우 중요한 요소다. 내부 DSL(internal DSL)을 만들더라도, 사용하는 호스트 언어의 문법과 기능을 깊이 이해할수록 이를 기반으로 설계하는 것이 유리하고 이는 더 나은 DSL 을 설계하는데 도움이 될것이라 믿는다.

해석기를 만드는 것은 결국 데이터를 처리하는, 우리가 말하는 프로그램을 구현하는 일이다.

DSL을 설계하고 구현하는 것은 현대 프로그래밍에서 추상화 레이어를 만들어 복잡성을 숨기고 누구나 이해하고 수정할 수 있도록 하여, 복잡성과 위험의 범위를 줄이는 핵심 요소 중 하나이다. 튜링 완전성을 갖추면 프로그래밍 언어, 그렇지 않다면 DSL로 볼수 있는데, 프로그래밍 언어를 한 번 만들어본 경험은 DSL을 설계할 수 있다는 증거가 된다고 본다.

근데 왜 만드는거죠?

728x90

저작자표시

'프로그래밍 기록 > 토이' 카테고리의 다른 글

주술회전 대사로 프로그래밍을 해보자 (2)	2024.02.12
트랙볼을 활용한 가난한자의 레이싱휠 제작 (0)	2023.09.19
[CodePaper] 코드들을 하나의 md 문서에 모으기 (0)	2023.04.25
[GPT] AI-Powered 심리테스트 (0)	2023.03.26
[ChatGPT] API 가 나온 기념 AI 끼리 신나게 놀게 해보자 (3)	2023.03.04

SeeRoE 프로그래밍 기록

블로그 홈

대한 축구 협회 프로그래밍 랭기지를 만들어보자 되도록 튜링완전하게..

아이디어는 어디에나 있다

명언 =Equal= 문법

F# 의 ADT 표현력은 세계 제일!

FParsec 근데 GPT 를 곁들인

해석해주기 전에는 그는 다만 하나의 데이터에 지나지 않았다

더 추가하기

1. 조사 관련

2. BREAK

완성! 과 잡담

근데 왜 만드는거죠?

'프로그래밍 기록 > 토이' 카테고리의 다른 글

티스토리툴바

대한 축구 협회 프로그래밍 랭기지를 만들어보자 되도록 튜링완전하게..

아이디어는 어디에나 있다

명언 =Equal= 문법

F# 의 ADT 표현력은 세계 제일!

FParsec 근데 GPT 를 곁들인

해석해주기 전에는 그는 다만 하나의 데이터에 지나지 않았다

더 추가하기

1. 조사 관련

2. BREAK

완성! 과 잡담

근데 왜 만드는거죠?

'프로그래밍 기록 > 토이' 카테고리의 다른 글

'프로그래밍 기록/토이' Related Articles

티스토리툴바