Computer Science/프로그래밍언어론

[Programming Language Pragmatics] 06 Control Flow(1)

계속지나가기 2020. 10. 25. 15:53

[06 Control Flow (1) ] 6.0~6.1.2

6.0 Introduction

6.1. Expression Evaluation
- 6.1.1 Precedence and Associativity
- 6.1.2 Assignments

6.0 Introduction

Control flow or ordering in program execution

Sequencing
: 절차지향언어에서는 기본적으로 순차적으로 코드 실행
Selection(alternation) : 조건문
: 특정 런타임 컨디션에 의존함, 가장 자주 볼 수 있는 구조의 조건문은 if 와 case(switch) 문임
Iteration : 반복문
: 반복적으로 특정 부분의 코드가 실행됨 예로는 for/do, while, repeat문이 있음
Procedural abstaction
: control construct의 잠재적으로 복잡한 콜랙션을 단일 단위로 처리할 수 있는 방식으로 캡슐화하며 일반적으로 매개변수화의 대상이 된다. 예로는 함수, 클래스 등
Recursion
: 직접적 혹은 간접적으로 스스로에 의해 정의된 표현으로 복잡한 모델의 경우 식의 인스턴스를 부분적으로 판단하는 것과 관련된 정보를 스택위에 저장하는 것이 필요로 함

Exception handling and speculation

Exception Handling 이란? 예외 사항이 생길 시, 해당 예외 사항 처리 코드
Speculation이란? 실행해왔던 작업들을 undo, 혹은 roll-back 하는 것
Program fragment는 긍정적(낙관적)으로 실행되는데, 이는 경우에 따라서 그렇지 않을 경우가 많다
: 프로그래머가 코드를 짤 때 "되겠지~"하며 낙관적으로 짜나 예상치 못한 오류 상황에 부딪힐 때가 많음
만약 그렇지 않은 경우라면, 보호된 fragment의 remainder의 place안에서 실행되었던 핸들러로 실행이 branch된다.

Concurrency & Nondeterminacy

concurrency
- 두 개 또는 그 이상의 fragment가 동시에 동작하거나 evaluate 되는 경우를 말함
- 각각의 프로세서에서 parallel하게 실행되거나 단일 프로세서에서 interleave하게 실행하는 경우 모두 같은 효과를 달성하게 된다
nondeterminacy
- Statement, expression이 실행되는 순서가 정확하게 정해져있지 않은 경우
  : 이는 어떤 순서로 실행하여도 상관없음(Both lead to correct results )
- 몇몇 언어에서는 공정하게 혹은 랜덤하게 선택할 필요가 있음

6.1 Expression Evaluation

Expression은 일반적으로 아래와 같이 구성되어 있음
- A simple object
  : literal constant or a named varialbe or constant
- 연산자 혹은 인자에 대해서 함수를 사용하는 것도 포함
Operator
: 빌트인 함수들로 간단한 syntax와 특별한 곳에 사용되는 것을 말함
- 2 + 3 : 2,3 -> operand | + -> oprator
Operand
: 연산자의 argument
대부분의 절차지향 언어들에서 함수는 함수의 이름이 나온 후 괄호가 붙고 콤마로 분리되어 있는 argument의 리스트로 구성
연산자는 간단한데, 한 개 혹은 두 개의 argument만을 취한다
: 괄호 혹은 콤마로 구분됨
몇몇 언어들은 normal-looking function에 syntatic sugar을 취한다
- syntatic sugar란? 좀 더 달아보이게(좋아보이게) syntax를 씀
  : In C++, a.operator+(b) 를 a + b 형태로 쓰는게 syntatic sugar라고 함
일반적으로, 언어는 함수 호출시 동반되는 prefix, infix, postfix notation을 구체화할 필요가 있다.
- indicate wheter the function name appears before, among, or after its several arguments
  1. Prefix : 함수의 이름이 먼저 나옴
  2. Infix : 함수의 이름이 중간에 들어감
  3. Postfix : 함수의 이름이 마지막에 들어감
- 대부분의 절차지향 언어에서는 이진 연산자를 위해 infix notation을 사용하고, unary operators와 다른 함수들을 위해 prefix notation을 사용한다

Examples of Other languages

Lisp 에서는 모든 함수들을 위해 prefix notation을 사용( Cambridge Polish notation : 함수의 이름을 괄호 안에 표기)
ML-계열의 언어들에서는 다음과 같이 모호함을 요구하는 상황을 제외하고는 모두 괄호를 사용한다 ( max (2+3) 4; -> 5)
ML, R 스크립트 언어와 같이 몇몇의 언어들에서는 사용자에게 새로운 infix operator를 생성하는 것을 허용함
Smalltalk 은 모든 함수들을 위해 infix notation을 사용함(both built-in and user-defined)
이러한 종류의 다중nfix notation은 다른 언어들에서 아래와 같이 가끔 발생할 수 있음
1. Algo의 경우, a := if b <> 0 then a / b else 0;
2. C의 경우, a = (b != 0 ) ? a /b : 0;
Postfix notation은 Postscript, Forth, 특정 hand-held calculators의 인풋 언어들 그리고 몇몇 컴파일러의 중간 코드 안의 대부분의 함수에서 사용될 수 있음
- Postfix appears가 사용되는 언어예시
  1. Pascal의 역참조 포인터 연산자 : ^
  2. post-increment(전위 연산자)와 decrement operators(후위 연산자)는 C와 C계열의 언어에서 나타남
    : ++a; b++;

6.1.1 Precedence and Associativity

: 우선순위와 결합 순서

대부분의 언어들은 논리 연산과 산술연산에 대한 풍부한 빌트인 셋을 제공
Infix notation으로 작성되었을 때 괄호가 없다면 연산자의 모호성이 생길 수 있음
- In Fortan : ** is used for exponentitaion(승수)
  : How should we parse < a + b * c ** d ** e / f ?
모든 언어에서는 Precedence 와 Associativity에 의거해서 어떤 순서로 계산할지를 정한다
: prefix, postfit notation에서는 문제가 생기지 않음! ONLY INFIX!

Precedence

Precedence Rules이란 괄호가 없을 때 특정 연산자가 먼저 계산되어지는 순서 규칙
: 대부분의 언어에서 곱셈과 나눗셈 그룹이 덧뺄셈 그룹보다 우선순위가 높음
C의 precedence structure은 다른 언어들보다 상당히 풍부하다
- several additional constructs, 타입 캐스트, 함수 호출, 배열 subscripting, record field selection이 C언어에서는 연산자로 분류되기 때문에 아래의 table에서 보는 것보다 훨씬 더 풍부함
Pascal에서는 논리 연산의 우선순위가 비교 연산자의 우선순위보다 높다
: 하지만 대부분의 언어에서는 산술 > 비교 > 논리 연산 순이다
APL, Smalltalk에서는 모든 연산자의 우선순위가 동일.

- Fortan, Pascal, C, Ada에서의 연산자 우선순위 표

Associativity rules

같은 우선순위 그룹의 연산자들이 나열되어 있을 때 왼쪽 혹은 오른쪽부터 계산할 것인지를 구체화해주는 룰
기본적인 산술연산자에서의 결합법칙
- 대부분 왼쪽-> 오른쪽으로 가능
- In Fortan : 승수(*)의 경우 오른쪽 -> 왼쪽으로 계산 됨
  : 4 * 3 ** 2 == 4 ** (3 ** 2)
- In Ada, 승수를 쓸 경우 반드시 괄호로 구분지어서 써줘야 함
일부 언어에서는 표현식에 대입 연산이 가능하다.
- 이 경우 결합 순서는 오른쪽->왼쪽
- In C : a = b = a + c
- Haskell 은 프로그래머가 만든 연산자의 우선순위와 결합순서를 정할 수 있다
  - The predefined operator ^ is declared in the standard library as infix 8 ^
  - right-associative infix operator
    : 4 ^ 3 ^ 2 -> 4 ^ (3 ^ 2)
  - infix, infix declarations 은 left associativity 와 non-associativity로 구체화됨
  - 우선순위 레벨은 0(가장 느슨)~9(가장 타이트함)로 측정한다

6.1.2 Assignments

순수한 함수형 언어의 경우, 프로그램의 블럭들에서 표현식이 빌드되고 표현식 전체를 계산 시 고려한다.
절차지향 언어의 경우 반대로, computation은 일반적으로 메모리에 있는 변수들의 값을 순서대로 바꾸는 것으로 고려되어 진다
: 할당은 값을 변경할 수 있는 중요한 원칙을 제공하는 것으로 봄
일반적으로, 프로그래밍 언어의 구조는 다음과 같은 상황에서 부작용을 가진다고 한다.
: 프로그래밍 언어의 구조가 subsequent computation에 영향을 미치고 궁극적으로 최종 결과값에 영향을 미칠 경우

Assignments in Imperative Language

많은 절차지향언어에서는 Expression 과 Statement를 구별한다
1. Expression : 표현식으로 항상 값이 나와야 한다
2. Statements : 선언문으로 값이 나올 필요는 없다

Assignments in Purely Functional languages

양극단의 예로 보면, 순수 함수형 언어에서는 부작용이 생기지 않는다
- 표현식의 값은 실행흐름의 referencing environment에 의존하며, 프로그램 실행 중 표현식이 언제 평가받느냐에는 영향을 받지 않음
- 만약 표현식 영역이 특정시간 안의 한 지점에서 특정 값이라면, 시간 안의 어떠한 지점에서도 같은 값을 가짐을 보장 받음
- 표현식은 referentially transparent이다
- Haskell , Miranda 는 purely functional language에 속함
- 많은 다른 언어들은 섞여있음(Functional+Imperative)
  - ML, Lisp은 거의 함수형 언어에 가까우나 프로그래머가 원하면 변수 할당을 가능하게 만듦
  - C#, Python, Ruby는 거의 절차지향 언어에 가까우나 거대한 함수 스타일을 사용할 수 있도록 다양한 기능을 제공

References and Values

할당의 표면만 보면 매우 직관적인, 직접적인 연산자로 보임
하지만 표면 아래를 보면 각기 다른 절차지향 언어에서 할당의 semantic 안에서 미묘하게 다른점을 찾을 수 있음
간단한 프로그램 작성 시 잘 드러나지 않기 때문에 이러한 차이점은 대게는 볼 수 없다
포인터들을 사용할 때 프로그램안에서 중요한 임팩트를 가지게 된다.
아래의 C코드를 보자(In C에서 이어서..)
- d = a; // value of a
- a = b + c; // Location of a

In C

// In C
d = a;      /* value of a */
a = b + c;  /* location of a */

C언어의 변수는 값을 위한 지정된 컨테이너이다(named container)

C 와 많은 다른 언어들에서 변수들의 value model을 사용

L-values: expressions that denote locations
a = b ; // a is L-value
f(a); void func(int k){}; // k is L-value
R-values : expressions that denote values
a = b; // b is R-value
f(a); void func(int k){}; // a is R-value

Value model of a variables을 따르는 상황에서는 주어진 표현식이 L-values 혹은 R-values인데 이 경우 나타나는 위치(좌,우)를 확인해보면 된다.
L-value는 표현식 형태로 사용될 수 있음
단, 모든 표현식이 L-values가 될 수 있는 것은 아니다.
: 2 + 3 = a; // error
L-values 와 R-values은 복잡하게 표현될 수 있음
: (f(a) + 3 ) -> b[c] = 2; (자세하게는 아래 코드 참조)
In C++, 함수는 sturuture에 포인터가 아닌 참조를 반환할 수 있음
: g(a).b[c] = 2;

+ (f(a) + 3 ) -> b[c] = 2 해석

(f(a)+3) → (f(a))[3] : 즉 구조체나 클래스의 포인터에 해당, 따라서 f는 이중 포인터(포인터의 포인터 형태)를 반환

A** pp = f(a);
A* p = pp[3];
p->b[c] = 2;

f() 함수에서 반환하는 것은 다음과 같이 A의 주소값이 됨

A* arr[5] = { ... }; // 초기화 코드


A** f(int c) 
{

  ...

  return arr;

}

// 위 코드를 아래와 같이 좀 더 간단하게 작성 가능
A* f(int c) 
{

  ...

  return arr[3];

}

아래의 코드로 작성할 경우 더 간단한 형태로 표현 가능

(f(a) + 3 ) -> b[c] = 2 → (f(a))->b[c] = 2

+ 참조형을 반환하는 경우 : g(a).b[c] = 2;

g(a)는 A라는 구조체가 차지하는 공간을 반환

만약 g(a)가 앞에서 보았던 (f(a) + 3)과 같은 역할을 한다고 하면, 아래와 같은 형태로 나타낼 수 있음

A&r = g(a);
r.b[c] = 2;

g()함수는 다음 형태로 구현됨

A& g(int c) 

{
  ...

  return *(arr[3]);
}

Reference model of variables

L-values와 R-values 사이의 구분을 더욱 명확하게 해야함

: Algol 68, Clu, Lisp/Scheme, ML, Smalltalk

위에서 언급한 언어들의 경우 변수가 단순하게 값을 저장하는 named cotainer가 아님
: 그보다는 값에 대한 named reference 임

reference model을 사용하는 언어의 경우 모두 L-value의 개념을 갖게 됨

R-value를 사용해야 할 것 같은 상황이 있을 경우 해당 값을 참조하는 value를 얻어내는 dereferenced 작업이 일어나야 한다
reference model을 참조하는 대부분의 언어에서 dereference는 내부적, 자동적으로 일어난다
: 단 ML에서는 dereference operator 명령어를 써줘야 한다.

Pascal : 변수가 named container로 사용 Clu : 변수가 named refrence로 사용

변수의 Value와 reference 모델 사이의 차이점은 매우 중요하다

: 변수가 참조하는 value가 연결된 데이터 구조를 가진 많은 프로그램에서와 같이 "In place"로 변경될 수 있는지의 여부

In place : In data structure, "linked list"
이는 같은 값을 가지는 다른 객체를 참조하는 변수를 위해 가능한 경우
단순히 값이 같은 지, 같은 객체를 가리키고 있는 것인지 확인 필요

C#, Eiffel의 경우 프로그래머가 선택할 수 있음

class : reference type
struct : value type

Boxing

- 빌트인 타입들을 위해 Value 모델을 사용하는 Drawback은 클래스 타입의 파라미터 인자를 기대하고 있는 메소드에 빌트인 타입을 전달 할 수 없다.

- 따라서 자바의 초기 버전은 프로그래머에게 빌트인 타입들로 wrap해주는 "wrap" 객체를 요구함

- C#과 최근 버전의 자바의 경우 많은 경우에서 wrapper syntax를 사용하는 것을 피할 수 있는automating boxing, unboxing 연산자를 제공해줌

- 자바의 제네릭은 프로그래머가 값을 리턴받는 cast의 니즈를 제거해줌

C#의 경우, boxing의 니즈를 제거해줌

아래는 초기버전의 자바로, wrap 객체를 사용한 예제 코드

// In Java
import java.util.ArrayList;
…
ArrayList list = new ArrayList();
…
list.add(new Integer(31));
Integer m = (Integer) list.get(0);
int newm = m.intValue();

아래는 최근 버전으로 automatic boxing & unboxing을 제공하는 예제 코드

//In Java
import java.util.ArrayList;
…
ArrayList list = new ArrayList();
…
list.add(31);
int newm = (Integer) list.get(0);

Orthogonality

수학적 용어로는 직교라는 뜻을 가지고 있지만 프로그래밍에서는 일관성이라고 이해하면 좋다.
프로그래밍 언어를 만드는데 있어 공통의 설계 목표로 언어를 가능한 orthogonal, 일관성 있게 만드는 것
Orthogonality는 어떤 기능이 있을 때 어떠한 조합을 만들든지 사용할 수 있어야 하고, 일관성이 있어야 한다.
: 기능들을 조합하여 사용할 때 당연히 타당성이 있어야 하고, 일관성이 있어야 한다
Algol 68의 경우 Orthogonality를 가장 주된 목표로 삼은 첫번째 언어이다.
- 이 이후에 매우 극소수의 언어만이 해당 목표를 가지고 설계되었다
- Algol 68은 expression-oriented함 : It has no separate notion of statement
- 다른 많은 언어 안에서 statement라고 부를 수 있는 문맥 속의 임의의 표현식과 다른 언어에서 statement로 고려되어지는 construct는 expressions 내에서 나타날 수 있다.
- 아래는 Algol68의 코드 예제

// In Algol68
begin
  a := if b < c then d else e;
  a := begin f(b); g(c) end;
  g(d);
  2 + 3
end

C의 경우 intermediate approach 방식을 취함
- 다른 언어들에 비해서는 Algo 68에 근접한 방식을 취함
- Statements, expressions 사이를 구분하나 statement의 클래스들 중 하나를 "expression statement"라고 함
  - 표현식의 값을 계산한 이후에 저장하지 않고 버려버림
  - 이는 대부분의다른 statement에서 문장에 필요한 문맥에 표현식이 등장하는 것을 가능하게 함
- 아래는 C언어에서의 Expression Statement 예제 코드
  - statement는 일반적으로 표현식 문맥에서는 사용하지 못함
  - C언어에서는 selection과 sequencing을 위한 특별한 표현 형태를 제공함
  - Algol 60은 if...then...else를 statement, expression 둘 다로 정의 한다

// In C
x = (y + 3);  /*x is assigned the value of y+3*/  
x++;            /* x is incremented */  
x = y = 0; /* Both x and y are initialized to 0 */  
proc(arg1, arg2); /* Function call returning void */  
y = z = (f(x) + 3); /* A function-call expression */

Algol 68, C 둘다 표현식 안에서 할당을 허용한다
- Algol 60 use the := token for assignment
- C uses = for assignment
- C uses == to represent a test for equality
- C++에서는 boolean 타입의 클래스를 제공하나 C 계열의 언어이므로 == 역시 가능
- 아래는 C 코드 예제
  - 아래와 같이 if ( a = b) 코드 선언문은 a,b가 둘다 Boolean Type이 아닌 이상 컴파일 타임 에러가 발생

// In C
if (a == b) {
   /* do the following if a equals b */
   …

if (a = b) {
    /* assign b into a and then do 
       the following if the result is nonzero */
    …

- numeric, pointer, enumeration type의 자동형변환을 제공하기 때문에 C++에서는 위와 같은(C에서와 동일) 문제를 겪음

- 자바와 C#은 Boolean context상에서 정수타입의 선언이 들어가는 것을 문법적으로 허용하지 않기 때문에 위와 같은 문제가 생기지 않음

Lack of Orthogonality in C

void func(int b);

int a = 3;
func(a);

typedef struct { int a, b } S;
void func(S s);
S a = { 1, 2 };
func(a); /* ok */
func({1,2}); /* not ok */
a = { 3, 4 }; /* not ok */

S f(void) {
    return {3, 4}; /* not ok */
}

C언어의 구조체에서 변수를 선언하는 것은 가능하나 함수 선언은 불가능하다
자바는 오브젝트 타입은 저장 가능하나 클래스 타입은 불가
대부분의 언어들은 정수와 소수의 간단한 타입들로만 배열의 인덱스를 표시하는 것을 허용한다.
대부분의 언어들은 switch, case 문의 경우 역시 정수와 다른 간단한 타입만 가능
Orthogonality suggests any variable should be allowed to be on the left of an assignment, presuming the types match.
: C/C++ forbids arrays to be assigned

Non-Orthogonality in Many Languages

C 언어의 struct에서는 variable declaration은 가능하나 함수 선언은 불가능
자바에서는 Object x 선언시 클래스 타입 저장은 가능하나 빌트인 타입(primitive type)은 불가능
- 자바 8버전 이후부터 박싱을 지원해서 빌트인 타입이 가능해 보이나 사실 아님
대부분의 언어에서는 배열의 인덱스 선언시 정수, 혹은 정수와 간단한 심플 타입만 가능
대부분의 언어에서 switch, case문에서 정수 혹은 간단한 심플 타입만 가능
만약 Orthogonality가 가능하다고 하면, 우변 좌변에 어떠한 것이 와도 가능해야 되지만 C/C++의 경우 배열 할당을 불가능하게 한다

// In C
#include <stdio.h>
int main(void){
	int a[10];
    int b[10];
    
    a = b; //forbid arrays to be assigned in C/C++
    return 0;
}

Combination Assignment Operator

C/C++ 에서 += , -=, *= 을 Combination Assignment Operator라고 함

절차지향 프로그램들은 반드시 변수를 자주 업데이트해줘야 함
많은 언어들에서 아래와 같은 선언문을 자주 볼 수 있음
: a = a + 1;
자주 쓰는 위와 같은 선언문에 중복성을 줄여주고 간단하게 사용할 수 있도록 아래와 같이 연산자 지원
: a += 1;
만약 주소 연산이 부작용을 가질 경우에도 훨씬 더 유용하게 사용 가능
- 즉 a = a+1 을하게되면 서로 다른 a에 할당이 될 수 있는데 a += 1을 할경우 같은 a에 저장하게 됨

// In C
void update(int A[], int index_fn(int n)) {
    int i, j;
    /* calculate I */
    …
    j = index_fn(i);
    A[j] = A[j] + 1;
}

here we cannot safely write

A[index_fn(i)] = A[index_fn(i)] + 1;

index_fn을 다음과 같이 구현했다고 해보자

int index_fn(int i) {
    static int n = 3;
    n++;
    return i + n;
}

중복 주소 계산과, 중복된 side effect 문제를 피하기 위해서 Combination Assignment Operator를 제공함

a += 1;
b.c[3].d *= e;
A[index_fn(i)] += 1;

aesthertically cleaner를 추가적으로 제공해주는 것은 할당 연산자의 형태를 주소 계산과 모든 side effect에 대해서 한 번만 일어나게 하는 것을 보장한다.
C언어의 경우에는 이러한 할당 연산자를 10가지 정도 제공함
- 또한 prefix, postfix 증감자를 제공함
- allow event simpler code in update

A[index_fn(i)]++;
or
++A[index_fn(i)];

증감연산자는 아래와 같이 코드를 더 간결히 표현해줌

A[--i] = b;
*p++ = *q++;

++/--의 prefix form은 +=, -=의 syntax sugar일 뿐임( 같은 의미임)

A[--i] = b;
A[i -= 1] = b;

단, 아래와 같은 postfix form은 syntax sugar가 아님

*p++ = *q++;
*(t = p, p += 1, t) = *(t = q, q += 1, t)

Multiway Assignment

일부 언어에서 아래와 같이 사용하는 것을 지원( Clu, ML, Perl, Python, Ruby)

a, b = c, d;
a = c; b = d;

multiway assignment는 아래와 같은 것 역시 지원(tuple)

a, b = b, a (* swap and b *)

또한 여러개의 값을 반환하는 것 역시 지원

a, b, c = foo(d, e, f);

이런식의 multiway assignment를 지원하는 것은 orthogonality하다고 하는데 이는, 함수의 인자로 전달하는 것은 여러개를 가능하게하나 반환 값은 한개로 출력하는 non-orthogonality하다고 하기 때문

티스토리

[Programming Language Pragmatics] 06 Control Flow(1)

[Programming Language Pragmatics] 06 Control Flow(1)

[06 Control Flow (1) ] 6.0~6.1.2

Table of Contents

6.0 Introduction

Control flow or ordering in program execution

Exception handling and speculation

Concurrency & Nondeterminacy

6.1 Expression Evaluation

Examples of Other languages

6.1.1 Precedence and Associativity

Precedence

Associativity rules

6.1.2 Assignments

Assignments in Imperative Language

Assignments in Purely Functional languages

References and Values

In C

+ (f(a) + 3 ) -> b[c] = 2 해석

+ 참조형을 반환하는 경우 : g(a).b[c] = 2;

Reference model of variables

Boxing

Orthogonality

Lack of Orthogonality in C

Non-Orthogonality in Many Languages

Combination Assignment Operator

Multiway Assignment