[PLT/프로그래밍언어론] 02. PL Principle 1

02. Principle 1

#PLT

Computers and Turing Machine

What is a Computer?

이 강의에서는 PL을 중점으로 다룰 예정이다.
우리는 프로그래밍 언어의 크리에이터가 된다고 생각하자.
PL을 디자인할 때, 컴퓨터에서 프로그램이 동작하도록 하기 위해 많은 것들을 고려해야 하고, 우리는 이 부분을 중점으로 학습한다.

• PL의 관점에서 컴퓨터란 무엇인가요?
• 프로그래밍 언어는 결국 컴퓨터에서 실행됩니다.
• 프로그래밍 언어를 설계하거나 프로그래밍 언어로 프로그램을 개발하려면 ➞ 컴퓨터가 어떻게 작동하는지 이해해야 합니다.
• 이 질문을 들으면 컴퓨터에 대한 다양한 이미지가 떠오를 수 있습니다.
• 이번 주 강의에서는 이 질문에 대해 좀 더 이론적으로 살펴볼 것입니다.
• 강의가 끝나면 컴퓨터에 대한 일반적이고 보편적이며 보다 이론적인 시각을 갖게 될 것입니다.

무엇을 고려해야 할까요?

• 컴퓨터에서 PL을 돌릴 때 고려해야 할 사항은 무엇인가요?
• PL의 관점에서는 컴퓨터가 다음을 제공하고 있는 것처럼 보인다.
  • Data types
  • Operators
  • Control of Execution
  • Control of Data
  • Memory Management
  • Input and Output

Data types

• 컴퓨터가 계산을 수행할 때는 데이터에 대해 계산이 수행되는 경우가 많다.
• 다양한 데이터 타입이 존재하며 적용 가능한 연산은 데이터 타입에 따라 달라집니다.
  • ex) String vs Number
• 데이터 타입은 연산의 정확성을 확인하고 올바른 계산을 선택하기 위해 고려해야 합니다.
  • ex) str1 + str2 와 2 + 3 에서 더하기 연산(+)를 생각해보자

Operators

• 컴퓨터가 복잡한 계산을 쉽게 처리할 수 있는 것처럼 보입니다.
  • 우리는 내부적으로 컴퓨터가 어떻게 처리하는지 신경쓰지 않아도 된다.
• PL은 또한 운영자에게 우리에게 익숙한 계산을 지원하는 기능을 제공합니다.
  • 예) 문자열 연결, 모듈로 연산자 등)
• 이러한 복잡한 계산을 내부적으로 처리하기 위해 다양한 기본 연산이 결합된다.

Control of Execution

• 컴퓨터는 연산의 실행을 제어해야 합니다.
  • 예) 조건부 또는 반복적으로 연산 실행.
• 원하는 결과를 얻으려면 의도에 따라 연산을 실행해야 합니다.

우리가 PL을 새로 만든다고 한다면 실제로 Control of Execution이 어떻게 일어나는지 이해해야 한다.

Control of Data

• 컴퓨터에서 CPU는 결국 계산 중인 데이터를 처리합니다.
• 그러나 이 데이터는 처음에는 CPU에 존재하지 않습니다.
• 따라서 컴퓨터 내부의 데이터 흐름을 제어할 필요가 있습니다.

a = b + c
b와 c가 저장되어있는 메모리에서 값을 CPU 레지스터에 복사한 뒤 값을 계산하여 a 메모리에 저장한다.

Memory Management

• 컴퓨터가 프로그램을 실행하면 일반적으로 프로그램이 메모리에 로드됩니다.
  • 프로그램 자체가 사용 가능한 메모리보다 크면 어떻게 하나요?
• 프로그램도 계산을 위해 일부 데이터를 처리해야 합니다. 이 때도 메모리를 써야 한다.
  • 계산 중에 생성된 일부 정보를 저장해야 하는 경우 어떻게 해야 하나요?
• 메모리에서 데이터를 로드하고 제거하려면 적절한 메모리 관리가 필요합니다.

Input and Output

• 사용자가 컴퓨터를 사용 중인 경우
  • 컴퓨터가 사용자로부터 입력을 받고, 사용자에게 output을 제공한다.
  • ex) 네트워크
• 컴퓨터는 PL에게 I/O 기능을 제공해야 한다.
• 일반적으로 I/O는 처리 시간이 많이 걸리므로 컴퓨터도 이를 효율적으로 처리해야 한다.

So What?

• 고려해야 할 사항은 알고 있지만 프로그래밍 언어마다 이러한 문제를 처리하는 방식이 다릅니다.
  • 예) 무조건 분기(goto)가 있는 언어와 무조건 분기가 없는 언어 비교.
• 컴퓨터를 좀 더 일반적이고 이론적인 방식으로 정의할 수 있을까요? Turing Machine

Turing Machine

• 1936년 앨런 튜링에 의해 처음 소개되었습니다.
• 원래는 자동 기계를 뜻하는 'a-machine'이라고 불렀습니다.
• 일반적으로 계산의 속성을 증명하기 위해 발명된 이론적인 가상의 기계였습니다.
• 나중에 이 기술은 현대 컴퓨터의 기반이 되었습니다. (폰노이만 구조)

(Tape는 가상의 모델임)
Control Unit의 Internal States에 따라 테이프의 헤드가 가리키는 Symbol을 읽을 수 있다.

current state가 b라면 # symbol을 읽고 0을 쓴 다음 오른쪽으로 이동한다. 이는 프로그램으로 볼 수 있다.

튜링 완전성(Turing Completeness)

• 지금까지 모든 계산 문제는 튜링 머신으로 해결할 수 있는 것으로 알려져 있습니다.
  • 예) 컴퓨터가 할 수 있는 모든 일은 튜링 머신으로도 할 수 있습니다.
  • 특정 문제가 계산으로부터 답을 얻을 수 있다면, 이 문제는 튜링 머신으로 해결할 수 있다.
• 튜링 머신을 시뮬레이션하는 데 사용할 수 있는 시스템이라면(모든 문제가 튜링 머신으로부터 해결된다면) 튜링이 완성된 것(Turing Complete)입니다.
  • 여기서 시스템은 프로그래밍 언어와 같은 것을 말한다.
• 기억해야할 것: 튜링 완전 시스템(Turing complete system)은 튜링 머신과 동등한 연산 능력을 갖추고 있습니다.
• 프로그래밍 언어의 이론적 계산 능력

PL을 만드는 방법 ?

To Design a New PL

• 새로운 프로그래밍 언어의 목적은 무엇인가요?
  • 수치 계산, 웹 프로그래밍, 시스템 프로그래밍 등
  • ex) Java : Null Safety
• 새로운 프로그래밍 언어의 목적에 유용한 공통 개념을 구현합니다.
• 이러한 개념으로 인한 단점을 최소화하여 목적을 달성합니다.
  • ex) 모든 객체가 null 값을 가지지 않도록 해보자

Criteria for Language Design(언어 디자인 기준)

• 프로그래밍 언어를 잘 설계하려면 다양한 기준을 고려해야 합니다.
• 이러한 기준은 언어의 여러 특성에 따라 영향을 받습니다.

단순성, 직교성, 데이터 타입, 구문 설계, 추상화 지원, 표현력, 타입 체킹, 예외 처리, 제한된 엘리어싱

• Readability : 언어를 얼마나 쉽게 읽고 이해할 수 있는지?
• Writability : 원하는 프로그램을 얼마나 쉽게 작성할 수 있는 언어인지?
  • ex) assembly 언어 vs C/C++ vs Python
• Reliability : 언어가 항상 예상대로 작동하는지?
  • ex) 타입 체킹, 예외 처리, 앨리어싱

Orthogonality(직교성)

• 직교성은 컴포넌트를 독립적으로 사용할 수 있음을 의미합니다.
• PL에서는 일련의 규칙에 따라 소수의 기본 구성(constructs, 조건문이나 assignment, if, loop문)을 결합하여 복잡한 프로그램을 만들 수 있습니다.
• 이러한 직교성에는 몇 가지 장점이 있습니다.
  • 우리는 작은 구조와 규칙을 익힌 후에 언어를 사용할 수 있습니다.
  • 같은 패러다임인 언어를 알고있다면 더 쉽게 사용할 수 있따? 요런뜻인듯?
• 그러나 올바른 프로그램을 작성하는 것이 더 어려울 수 있습니다.
  • constructs의 조합은 합법적(legal)일 수 있지만 우리가 원하는 대로 작동하지 않을 수 있습니다.

Aliasing(앨리어싱)

앨리어싱이 유발하는 문제가 많기 때문에 특정 언어에서만 앨리어싱을 지원하고 있다.

• 앨리어싱은 동일한 객체를 다른 이름으로 참조할 수 있음을 나타냅니다.
  • 예) C++ 참조 변수.
  • int val = 10; int& ref = val;
• 프로그래머는 변수 값을 수정할 때 영향을 예측하기 위해 변수에 대한 모든 참조를 기억해야 합니다.
  • 이러한 언어로 작성된 프로그램의 신뢰성에 영향을 미칩니다.
  • C++을 Rust로 바꾸려는 이유

이외에도

• Type Saftey
  • C/C++ vs Rust
• Null Safety
  • Java vs Kotlin / Dart
• Compatibility(호환성)
  • C++ vs Java vs JavaScript
  • 자바는 JVM, C++는 OS별 실행 파일
• Easy to use / learn
  • C++/Java vs Python
• Performance
  • Python vs Julia / Mojo

PL은 어떻게 구현하나요?

• 인간: 고급 언어가 더 이해하기 쉽습니다.
• 컴퓨터: 기계의 명령어만 이해할 수 있습니다.

고급 언어와 기계어 사이의 bridge 역할을 하는 프로세스를 구현해야 한다.

• PL 구현: 높은 수준의 언어를 낮은 수준의 언어로 번역하는 프로세스를 구현합니다.
• 이러한 번역은 컴파일러 또는 인터프리터가 수행합니다.
• 결국 PL 구현은 컴파일러 또는 인터프리터 구현과 동일합니다.

컴파일러 vs 인터프리터

컴파일러와 인터프리터는 모두 사람이 작성한 코드를 기계가 실행할 수 있는 저수준 코드로 변환합니다.

• 컴파일러
  • complete code ➞ 실행 가능한 프로그램으로 변환
• 인터프리터
  • 표현식 읽기 및 평가 명령어 실행 순으로 진행된다.

• 컴파일러
  • 생성된 실행 프로그램의 실행 성능과 효율성에 집중하세요.
  • 코드와 실행을 연결하기가 상대적으로 어렵습니다.
  • 컴파일 시 오류를 찾습니다.
    • 만약 컴파일 시 체크 없이 돌린다면 런타임 에러를 통해서 코드에서 문제가 발생한 부분을 찾아야 한다.
• 인터프리터
  • 구현하기는 쉽지만 속도가 느립니다.
  • 런타임 오류 ➞ 코드에 직접 연결.
    • 표현식 하나하나 읽고 평가하여 output이 나오기 때문
  • 부분 코드(일부 표현식만)를 실행할 수 있습니다.

컴파일러와 인터프리터를 선택할 때는 여러분의 목적에 맞춰 각각의 장단점을 고려해야 한다.

컴파일러

• 하이레벨 언어의 코드를 target machine에서 실행 가능한 기계어 명령어로 변환합니다.
• 인간과 기계 사이의 번역기.
• 컴파일러는 object(target) language로 코드를 생성하며, 그 결과물을 흔히 object file이라고 합니다.
• 그런 다음 object file은 하나의 실행 프로그램으로 결합된다.

컴파일 단계

• Lexical Analysis(어휘 분석)
• Syntax Analysis(구문 분석)
• Semantic Analysis(의미 분석)
• Intermediate Code Generation(중간 코드 생성)
• Code Optimization(코드 최적화) (low-level code을 말함)
• Code Generation(코드 생성) (low-level code을 말함)

Lexical Analysis(어휘 분석)

• 컴파일러의 첫 번째 단계입니다.
• 소스 코드를 일련의 토큰으로 변환합니다.
  • 예) 키워드, 리터럴, 식별자, 숫자, 연산자 등입니다.
  • int a = 10; ➞ int (키워드), a (식별자), = (연산자), 10 (숫자 리터럴), ; (symbol).
• 공백과 주석을 제거합니다.
• 토큰이 유효하지 않으면 오류가 발생합니다.

Syntax Analysis(구문 분석)

• 이제 일련의 토큰이 생겼습니다.
• 구문 분석 단계에서는 토큰의 순서가 올바른 구문을 따르는지 확인합니다.
• 이 단계를 흔히 “Parsing” 이라고 합니다.
• 소스 코드의 구문 구조를 나타내는 Concrete Syntax Tree(vs Abstract Syntax Tree) / Parse Tree / Derivation Tree를 생성합니다. (같은 것들임. 이름만 다름. parse tree라는 이름을 제일 많이 사용)
• 구문 분석할 수 없는 코드 ➞ 구문적으로 잘못된 코드!

bottom-up 방식. 컴파일러는 구문을 보고 assignment에 해당함을 알 수 있다.

Semantic Analysis(의미 분석)

• parse tree는 의미 분석을 통해 '주석(annotated)’ 또는 '장식(‘decorated)됩니다.
• 이 단계에서 수집된 정보는 코드 생성에 사용됩니다.
• 구문 분석은 코드가 무엇을 의미하는지에 대한 정보를 제공하지 않습니다.
  • 단순히 주어진 코드가 구문 rule을 따르는지 체크한다.
  • 프로그램이 올바르게 작성되었는지, 특히 변수, 함수, 데이터 타입 등의 사용이 적절한지를 확인
• 따라서 코드의 의미를 파악하고 최소한 평가할 수 있어야 합니다.
• 구문 분석과 결합되는 경우가 많다.

부연설명: 코드의 의미
프로그램이 무엇을 의도하고 수행하려고 하는지를 이해하고, 이를 컴퓨터가 실행할 수 있도록 하는 것을 의미합니다. 이 과정은 컴퓨터가 사람이 작성한 소스 코드를 실제로 수행할 때 발생할 수 있는 의미적 오류를 방지하고 올바르게 작동하도록 보장하는 데 목적이 있습니다

타입의 일관성 확인:
예를 들어, 변수 x가 정수형(int)으로 선언되었다면, 그 변수에 문자열이나 부동 소수점 값을 할당하려고 하면 안 됩니다. 이러한 타입 일관성을 검사하는 것이 코드의 의미를 파악하는 것의 일환입니다.
기능의 의도된 사용 확인:
함수 f(a, b)가 두 개의 정수를 인자로 받도록 정의되었을 때, 호출 시에 실제로 두 개의 정수가 전달되는지를 확인합니다. 만약 잘못된 타입이나 개수의 인자가 전달되면, 의미적 오류가 발생합니다.
변수 및 심볼의 스코프와 사용 검사:
각 변수나 함수가 선언된 위치에서 올바르게 사용되는지, 해당 스코프(유효 범위) 내에서만 참조되는지 확인합니다. 예를 들어, 함수 내부에서 선언된 지역 변수는 함수 외부에서 사용될 수 없습니다.
논리적 의미의 검증:
코드의 실행 흐름이 논리적으로 유효한지 확인합니다. 예를 들어, if 문 다음에 조건이 항상 참일 수 없거나, while 문이 무한 루프에 빠질 가능성이 있는지 검사할 수 있습니다.
명시적 및 암시적 타입 변환의 유효성 검사:
암시적 타입 변환(예: 정수를 부동 소수점 수로 변환)이 프로그램의 의미에 맞는지, 또는 명시적 타입 변환이 허용 가능한지를 검사합니다. 예를 들어, 정수를 포인터로 변환하는 등의 위험한 변환이 발생하지 않도록 확인합니다.

구문 분석(Syntactic Analysis)은 코드의 형식적 구조에 집중하지만, 의미 분석(Semantic Analysis)은 이러한 구조가 의미론적으로 맞는지를 확인하는 것입니다.

Intermediate Code Generation(중간 코드 생성)

• 컴파일러의 최종 결과는 종종 기계에 따라 달라집니다.
• 따라서 머신 코드는 기계에 독립적인 코드 최적화를 적용하기에 바람직한 대상이 아닙니다.
• 대신 컴파일러는 대상 머신과 독립적인 Intermediate Code를 생성합니다.
• 그런 다음 코드를 먼저 최적화하고 대상 머신에 대한 명령어로 변환합니다.

Code Optimization(코드 최적화)

컴파일러 강좌는 아니니까 자세히 알 필요는 없다.~

• 컴파일러는 실행 가능한 프로그램을 생성하기 전에 자동으로 코드 최적화를 수행합니다.
  • 예) 데드 코드 제거, 공통 하위 표현식 제거, 복사 전파(copy propagation), 루프 최적화 등)
  • a=ij+k; B=IJK; ➞ TMP=IJ; A=TMP+K; B=TMP*K;
    • IJ라는 공통 하위표현식을 tmp로 처리함
• 이러한 최적화를 통해 코드를 크게 개선할 수 있습니다.
• 인터프리터와 비교할 때 가장 중요한 장점 중 하나이다.
  • 인터프리터는 앞으로 어떤 코드가 올 지 모르기 때문에 최적화가 어렵다.
  • a = ij + k에서 b = ijk라는 사실을 알 수가 없음

Code Generation(코드 생성)

• Intermediate code를 입력으로 받아 동등한 대상 프로그램을 생성합니다.
• Requirements(요구사항)
  • 출력 코드가 정확해야 합니다.
  • 출력 코드는 대상 머신의 리소스를 효율적으로 사용해야 합니다.
  • 코드 생성기 자체는 효율적으로 실행되어야 합니다.
    • 막 10일동안 걸리면 안됨.

Interpreter

• 소스 코드를 직접 읽고 코드를 평가하여 결과를 얻습니다.
• 때로는 실제 컴퓨터에서 실행되는 가상 컴퓨터를 구현한 다음 가상 컴퓨터에서 코드를 실행하기도 합니다.
• 구현이 더 쉽고 컴파일러보다 메모리를 덜 차지하지만 속도가 느립니다.
  • 최적화를 적용하기 어렵기 때문
• 예) Python, ML, Scheme, Prolog 등

REPL

Read-Eval-Print-Loop
읽기-평가-출력 루프.

• 인터프리터는 실제로 위의 세 가지 작업을 반복합니다.
• 전체 프로그램이 필요하지 않고 읽은 내용을 평가하기만 하면 됩니다.
• 런타임에 코드를 작성할 수 있습니다 ➞ 사용하기 쉽습니다.

정리

프로그래밍 언어를 설계하거나 프로그램을 개발할 때, 컴퓨터가 어떻게 작동하는지 이해해야 효과적이고 정확한 코드를 작성할 수 있다.

먼저 컴퓨터에 대해 알아보자.
컴퓨터를 통해 프로그래밍 언어를 실행할 때, 데이터 타입, 연산자, 실행/데이터 제어, 메모리 관리, I/O 등을 고려해야 한다. 이러한 요소들을 고려하더라도 프로그래밍 언어마다 접근 방식이 다를 수 있다. 컴퓨터를 더 일반적이고 이론적인 방식으로 정의할 수 있을까? Turing Machine

지금까지 모든 계산 문제는 튜링 머신으로 해결할 수 있는 것으로 알려져 있다. 따라서 컴퓨터가 할 수 있는 모든 일은 튜링 머신이 할 수 있다. 모든 문제가 튜링 머신으로부터 해결된다면 튜링이 완성된 것(Turing Complete)이라고 할 수 있고, 이는 프로그래밍 언어의 이론적 계산 능력을 함축한다.

프로그래밍 언어를 디자인 해보자.

어떤 것들을 고려해야 할까?

1. 프로그래밍 언어의 목적을 고려해서 단점을 최소화 하자.
2. 단순성, 직교성, 데이터 타입, 구문 설계, 추상화 지원, 표현력, 타입 체킹, 예외 처리, 제한된 엘리어싱…과 같은 기준을 고려하자.

어떻게 구현해야 할까요?
인간은 High-level language(인간의 평소 표현과 비슷한)로 작성하고, 기계는 low level language(기계어)만 이해할 수 있다. 따라서 High-level language를 low level language로 번역하는 프로세스를 구현해야 한다.
즉, 컴파일러 또는 인터프리터를 구현하는 것이 곧 PL을 구현하는 것이다.

컴파일러 vs 인터프리터
공통점 : 컴파일러와 인터프리터는 모두 사람이 작성한 코드를 기계가 실행할 수 있는 저수준 코드로 변환한다.

컴파일러

• complete code ➞ 실행 가능한 프로그램으로 변환
• 실행 성능이 좋고 효율적임
• 컴파일 시 오류 체크
• target machine에서 실행가능한 기계어로 번역
• 다음 컴파일 과정을 거쳐 object file로 만든다.
  • Lexical Analysis(어휘 분석)
    • 토큰으로 쪼개고
  • Syntax Analysis(구문 분석)
    • 소스 코드의 구문 구조를 나타내는 Parse Tree를 만들어 구문 순서를 체크한다.
    • 코드의 형식적 구조
  • Semantic Analysis(의미 분석)
    • 단순히 주어진 코드가 구문 rule을 따르는지 체크
    • 코드 구조가 의미론적으로 옳은지
  • Intermediate Code Generation(중간 코드 생성)
    • target machine과 독립적인 Intermediate Code를 생성
  • Code Optimization(코드 최적화) (low-level code을 말함)
    • 파일러는 실행 가능한 프로그램을 생성하기 전에 자동으로 코드 최적화를 수행
    • 인터프리터에서는 최적화 하기가 어렵다
  • Code Generation(코드 생성) (low-level code을 말함)
    • 최적화한 Intermediate code를 입력으로 받아 프로그램을 생성.
    • 정확하고, 효율적이고, 빠르게 생성해야 한다.

인터프리터

• 표현식 읽기 및 평가 명령어 실행 순으로 진행된다.
• REPL(Read-Eval-Print-Loop 읽기-평가-출력 루프) 프로세스를 거친다.
  • 전체 프로그램이 필요하지 않고 읽은 내용을 평가하기만 하면 된다..
• 런타임에 코드를 작성할 수 있습니다 ➞ 사용하기 쉽다.