Blog

Programming Language, Week1

October 10, 2014

Programming Language, Week1

Programming Language by Dan Grossman, Coursera

Coursera PL 클래스인데 과제 마감기한도 까다롭고, 동료평가도 있고, 여러모로 조금 빡세다. 유일한 낙은 언어의 다양한 특징들을 탐구하기 위해 ML 을 사용하고 오오 갓 ML , emacs 를 사용한다는 건데.. 잘 버틸수 있을까 의심스럽다. 무려 첫 강의부터 대략 300분이 넘는 동영상을 올려주시는 교수님 -_-;

미국 CS 전공자들은 모두 이렇게 빡세게 배우는가요 ㅠㅠ?

SML/nj 와 Emacs 에 sml-mode 설치 후 시작한다. c-c, c-sREPL 을 켠다.

ML Variable Bindings and Expressions

(* This is a comment. *)

val x = 34;  
(*: static env: x : int *)
(*: dynamic env: x --> 34 *)
val y = 35 : int;  
val z = (x + y) + (y + 2);  

각 라인마다, dynamic environment 에 바인딩을 하나씩 추가한다. 따라서 세번 째 라인에서 xyz 를 바인딩하기 위해 사용할 수 있다.

그리고, dynamic env 에 바인딩을 추가하기 전에 static enviornmentType 을 추가한다. 맨 처음엔 x: int 가 추가되고 y 와 값이 바인딩 되기 전에는 x: int, y: intstatic env 에 추가된다.

따라서 매 라인마다 type checking 이 먼저 일어나고 그 후에야 프로그램이 evaluated (excuted) 된다.

ML 에서 if 는 다음과 같이 작성할 수 있다. 다르 언어와 비슷하다.

val abs_of_z = if z < 0 then 0 - z else z;  

여기서 잠깐 SyntaxSemantics 를 정리하자면

Syntax is just how you write something

Semantics is what that something means
Type-checking (before program runs)
Evaluation (as program runs)

variable binding 에서는, type checkingstatic environment 를 확장하고, evaluationdynamic environment 를 확장한다.

Rules for Expressions

expressionsub-expression 을 가질 수 있기 때문에, expression 을 해석 하는데 있어서 3가지가 꼭 필요하다.

(1) Syntax
(2) Type-checking rules: produces a type of fails
(2) Evaluation rules: produces a value

다시 말하면 SyntaxSemantics 가 필요하단 이야기다.

Variables

Syntax: sequence of letters, digits, _, not starting with digit

Type-checking: look up type in current statix env if
non there, fail

Evaluation: look up value in current dynamic env

Addition

Addition 의 경우에는 sub-exp 가 있을 수 있다.

Syntax: e1 + e2 where e1 and e2 are expressions

Type-checking: if e1 and e2 have type int then int

Evaluation: if e1 evaluates to v1 and e2 evaluates to v2, then sum of v1 and v2

Values

모든 valueexpression 이다. 그러나 모든 expressionvalue 인 것은 아니다. 그리고,

Every value evaluates to itself in zero steps

참고로, ()unit 타입을 가진다.

Conditional

Syntax: if e1 then e2 else e3 where if, then, and else are keywords and e1 e2 and e3 are sub-expressions

Type-checking: e1 must have type bool. e2 and e3 can have any type, but they must have the same type

Evaluation: first evaluate e1 to v1, if it’s true evaluate e2 and that resut is the whole expressions’s result else evaluate e3

REPL and Errors

use

use 는 특정 파일을 읽어 binding 하고 it: unit 을 돌려주는데, 이건 무시해도 된다. 그리고 같은 파일을 use 할때는 항상 REPL 을 다시 시작하자. C-d, C-c, C-s

Error

대부분의 에러는 syntax, type-checking, evaluation 의 문제다.

Shadowing

같은 변수에 대한 multiple bindingpoor style 이다. 그러나 이를 통해 environmentbinding 이 어떻게 동작하는지 알 수 있다.

val a = 10;  
val b = a * 2  
val a = 5; (* this is not an assignment statement *)  
(* a -> 5, b -> 20 *)
val c = 2;  
(* a -> 5, b -> 20, c -> 20 *)

val a = 5 문장은, 할당하는게 아니라 ashadowing 한다. ML 에서는 mutate 할 수 없다. 매번 새롭게 dynamic env 를 만든다.

val d = a  
(* ..., d -> 5 *)
val a =  a + 1  
(* ..., a -> 6 *)
val f = a * 2  

use 를 이용하면, 기존의 a 의 값이 <hidden-value> 로 나오는 것을 확인 할수 있다.

val a = 1;  
val b = a;  
val a = 2;  

다음과 같은 예제가 있을 때, b1 이다. eagerly evaluated 되어 바인딩 후에는 value 를 만든 expression 과는 관련이 없어진다. 다시 말해 바인딩 후에는 ab는 상관이 없다.

그리고 위에서 언급 했듯이 ML 에서는 assign to 가 없고, 앞의 a 는 뒤의 a 에가 있는 dynamic env 에 의해서 가려질 뿐이다.

그렇기 때문에 REPL 을 재시작 하지 않고서 같은 파일을 여러번 use 하면 문제가 생길 수 있다고 교수님이 누차 말한 것

Functions Informally

fun pow (x: int, y: int) =  
  if y = 0
  then 1
  else x * pow(x, y-1)

fun cube(x: int)  
  pow(x, 3)

이 경우 두 함수 모두 타입은 fn: int -> int 다. 타입을 이름 뒤에 사용하는것도 그렇고, 함수 타입도 그렇고 스칼라와 문법이 비슷한 것 같다.

* 가 타입에 있을때는 곱셈이 아니라 , 같은 역할을 한다. 따라서 다음과 같이 pow 를 호출할 수 있다.

val x : int * int = (2, 3)  
val y = pow x  

참고로, 함수를 사용한 후 정의하는 것은 불가능하다. 따라서 사용하는 expression 위에 함수를 정의해야 한다.

Recursion

재귀에 대해서도 간단히 언급을 하는데, 문제를 간단한 방법으로 나누어 푸는 좋은 기술이라고..

Functions Formally

우리가 Function 이 무엇인지 PL 에서 정의하려면 위에서 언급했듯이 syntaxsemantics 가 필요하다.

Syntax: fun x0 (x1: t1, ... , xn: tn) = e

Evaluation: A function is a value. x0 is added to dynamic env

Type-checking: (t1 *, ..., * tn) -> t

타입체킹이 조금 복잡한데, et 타입을 가지는지 검사하고, 파라미터도 마찬가지로 올바른 타입을 가지는지 검사한다.

다른 언어와 마찬가지로 t1 등의 파라미터는 e 를 위한 environment 에만 추가된다.

x0dynamic, static env 에 추가되므로 이후의 코드에서 recursion 을 사용할 수 있다.

Function calls

Function callssyntaxe0 (e1, ..., en) 이다. 만약에 인자가 하나라면 괄호(parentheses) 는 없어도 된다.

참고로 ML 에서는 variable numbers of arguments 를 함수에서 받을 수 없다. 인자의 개수가 정해져야 한다.

type-checking 의 경우에는 , e0(t1 * ... * tn) -> t 인지 검사하고 entn 타입을 가지면, e0t 타입이다.

Evaluation 스텝은 다음과 같다.

(1) evaluate e0 to fun x0(x1: t1, ... , x: tn) = e
(2) evaluate arguments e1, … , en to v1, …, vn
(3) extend dynamic env mapping x1 to v1 , … , xn to vn

두 번째 스텝에서는 eager evaluation 이 사용되는데 pow(2, 2+2) 같은 경우 인자가 2, 4 가 된다.

세 번째 스텝에서는 dynamic environment 를 확장하는데, 현재 함수인 x0 과 인자들인 xn 을 포함하도록 한다. 따라서 recursion 이 가능하다.

사실은 스칼라의 그것과 같은데 교재에 나온 설명이 너무 함축적이어서 이해하기가 어렵다.

Pairs and Other Tuples

위에서 잠깐 보았던 t1 * t2 같은 것들이 Pair 다. 다른말로 2-tuples 라 부른다.

Syntax(e1, e2)Type-checkinge1e2 가 올바른 타입을 가졌는지 검사한다.

Pair 에 접근할때는 #1 e 또는 #2 e 와 같은 Syntax 를 사용하고, et1 * t2 타입인지, 그 후에 #1 et1 또는 #2 et2 타입을 가졌는지 검사한다.

fun su_two_pairs (pr1: int * int, pr2: int* int) =  
  (#1 pr1) + (#2 pr1) + (#1 pr2) + (#2 pr2)

의 경우에는 타입이 (int * int) * (int * int) -> int 된다. 그리고 다른 언어와 마찬가지로 tuple 도 겹칠 수 있다.

val x1 = (7, (true, 9)) // int * (bool * int )  
val x2 = #1 (#2 x1) // true  

Introducing Lists

Tuple 은 여러 타입을 가질 수 있지만, 정해진 갯수만큼의 element 만 저장할 수 있다. 반면 List 는 하나의 타입만 가져야 하지만, 원소의 갯수가 변할 수 이다.

빈 리스트는 [] 와 같이 만든다. [3, 4, 5]int list 다. [(1+2), 3, 7] 과 같이 초기화하면 [3, 3, 7] 이 나온다. 리스트는 그 자체로 value 다.

::cons 라 발음하고, 다음과 같이 쓸 수 있다.

val x = [3, 4, 5]  
val y = 2 :: x  

cons 뒤에 오는것은 List 여야 한다. 리스트가 비었는지 검사하기 위해 null 을, head 를 얻기 위해 hd 를, tail 을 얻기 위해 tl 을 이용한다. 따라서 tl [3, 4, 5][4, 5] 를 돌려준다.

그리고 다른 함수형 언어와 마찬가지로 tl [9][](nil) 이다.

리스트는 다양한 타입을 가질 수 있기 때문에 (int * int) list 같은 것도 타입이 될 수 있다. [(3, 4), (5, 6)] 처럼.

nullfn: a list -> bool 타입이고,
hdfn: a list -> a,
tlfn: a list -> a list

[]: a list 는 좀 특이한데, 다양한 타입이 될 수 있다. 3 :: [], false :: [] 이라던지.

List Functions

리스트를 조작하는 간단한 함수를 ML 로 몇 개 짜보자.

fun pow(x: int, y: int) =  
    if y = 0 then 1 else x * pow(x, y - 1);

fun cube(x: int) =  
    pow(x, 3);

fun sum_list(xs: int list) =  
    if null xs
    then 0
    else hd xs + sum_list(tl xs)

fun product_list(xs: int list) =  
    if null xs
    then 1
    else hd xs * product_list(tl xs)

fun countdown(x: int) =  
    if x = 0
    then []
    else x :: countdown(x - 1)

fun append(xs: int list, ys: int list) =  
    if null xs
    then ys
    else (hd xs) :: append(tl xs, ys)

fun sum_pair_list(xs: (int * int) list) =  
    if null xs
    then 0
    else (#1 (hd xs)) + (#2 (hd xs)) + sum_pair_list(tl xs)

fun firsts(xs: (int * int) list) =  
    if null xs
    then []
    else #1 (hd xs) :: firsts(tl xs)

fun seconds(xs: (int * int) list) =  
    if null xs
    then []
    else #2 (hd xs) :: seconds(tl xs)

fun sum_pair_list(xs: (int * int) list) =  
    if null xs
    then 0
    else sum_list(firsts xs) + sum_list(seconds xs)

fun factorial(n : int) =  
    product_list(countdown(n))

참고로 #+ 이나 :: 보다 우선순위가 높다.

List Recursion

재귀에 대해 생각할땐, 항상 명심해야 하는게 있는데 탈출 조건 이다. 따라서 empty-list 에 대해선 어떤걸 돌려줄지, non-empty-list 에 대해서는 무엇을 처리해야 할지 항상 생각해야 한다.

Let Expressions

letlocal variable 을 바인딩하는 법이다.

Syntax: let b1 b2 ... bn in e end. Each b1 is any binding and e is any expression

Type-checking: Type of whole let-expression is the type of e. Type-check each b1 and e in a staic env that includes the previous bindings

*Evaluation: * evaluate each b1 and e in a dynamic env that includes the previous bindings. Result of whole expression is result of evaluating e

fun silly () =  
    let
      val x = 3
    in
      (let val x = 2 in x + 1 end) + (let val y = x + 1 in y + 1 end)
    end

여기서 Scope 의 개념이 나온다.

Scope: Where a binding is in the environment

Nested Functions

Functionbinding 이다. 따라서 let 내부에서 local binding 할 수 있다.

fun count_from_1 (x: int) =  
    let
    fun count (from: int, to: int) =
        if from == to
        then []
        else from :: count(from + 1, to)
    in
    count(1, x)
    end

이렇게 하면 top-level 에서 count 는 사라진다. 그리고 엄밀히 말해서 count 가 가진 environment 에는 to 가 있기 때문에, to 를 인자로 가질 필요가 없다.

fun count_from_1 (x: int) =  
    let
    fun count (from: int) =
        if from = x
        then []
        else from :: count(from + 1)
    in
    count(1)
    end

Let and Efficiency

가장 큰 숫자를 찾는 다음의 함수를 고려 해 보자

fun bad_max (xs : int list) =  
  if null xs
  then 0
  else if null (tl xs)
  then hd xs
  else if hd sx > bad_max(tl xs)
  then hd xs
  else bad_max(tl xs)

이 함수는 [1, 2, ... , 30] 과 같은 리스트에 굉장히 나쁜 성능 exponentially (2^30) 을 보여준다. bad_max(tl xs) 를 두번 호출하기 때문이다. 따라서 max(tl xs) 를 변수로 놓아 캐싱하면

fun good_max (xs: int list) =  
    if null xs then 0
    else if null (tl xs) then hd xs
    else
    let
        val res = good_max(tl xs)
    in
        if hd xs > res then hd xs
        else res

    end

bad_maxif-then-else 가 10^-7 정도의 시간이 든다고 하면, [1, 2, ..., 55] 는 100년이 넘게 걸린다. 따라서 재귀를 구현하는데 있어서 local binding 은 필수다.

Options

참고로, good_max 는 리스트가 모두 음수일때 0 을 돌려준다. 이건 리스트가 비었을때 0 을 돌려주기 때문에 생기는 문제인데, 0 말고 다른 무언갈 돌려줄 수 없을까?

SMLScala 처럼 Option 을 지원한다.(물론 SML 이 먼저..) NONEa option 타입이고, SOME et option 이다. te 의 타입.

Option 을 이용해 max 를 리팩토링 해 보면,

fun max1 (xs: int list) =  
  if null xs NONE
  else 
    let val res = max(tl xs)    
    in if isSome res andalso isVal res > hd xs then res
       else Some(hd xs) 
    end

그런데, 이 max1 또한 문제가 있다. 사실 [] 는 리스트가 오름차순으로 구성되어있을때 ([1, 2, 3, 4]) 맨 마지막 호출에서만 오는데, 매번 isSome 으로 검사하니까 비효율적이다. 다시 리팩토링하면

fun max2 (xs: int list) =  
    if null xs then NONE
    else
    let
        fun max_non_empty(ys: int list) =
        if null (tl ys) then hd ys
        else
            let val res = max_non_empty(tl ys)
            in if hd xs > res then hd ys
               else res
            end
    in
        SOME (max_non_empty xs)
    end

교수님 let in end 는 제발그만 가..가독성이

Booleans and Comparison Operations

다른 언어의 && (and)|| (or) ! (not)SML 에서는 ansalso, orelse, not 이다.

그리고 andalso, orelse 연산자는 다른 언어처럼 Short circuiting 을 제공한다. 함수가 아니다.

andalsoorelse, not 은 다음처럼 쓸 수도 있다.

(* andalso *)
if e1  
then e2  
else false

(* orelse *)
if e1  
then true  
else e2

(* not *)
if e1  
then false  
else true  

if-then-else 만 가지고도 할 수 있으나, 그냥 andalsoorelse, not 을 쓰는게 코드를 읽는 사람의 정신 건강에 좋다.

Comparisons

비교의 경우엔 == 가 아니라 = 를 쓴다. != 가 아니라 <> 를 쓴다.

그리고 3.0 > 2 와 같은 비교는 안된다.3.0real 이고, 2intReal.fromInt 를 이용하자.

No Mutation

교수님이 A valuable non-feature 라고 이야기 하시는데, 기능이 없는게 장점이라고.. SML 에서는 아래의 두 코드가 같다. (inditinguishable)

fun sort_pair(pr: int * int) =  
  if #1 pr < #2 pr then pr
  else (#2 pr, #1 pr)

fun sort_pair(pr: int * int) =  
  if #1 pr < #2 pr then (#1 pr, #2pr)
  else (#2 pr, #1 pr)

위가 더 나은 style 이라고 주장할 순 있지만, 다르다고 말할 순 없다. 그러나 mutable compound data 를 다루는 다른 언어에서는 위 두 함수는 다르다

예를 들어서 mutable data 를 다루는 언어라 가정하고 다음의 코드를 고려 해 보자.

val x = (3, 4)  
val y = sort_pair x

(* somehow mutate #1 x to hold 5 *)

val z = #1 y  

이제 z 의 값은 무엇일까? sort_pair 구현에 따라 다르다. then 에서 pr 을 돌려줬다면, 5 일거고, (#1 pr, #2 pr) 을 돌려줬다면 3 일거다. 그러나 ML 에선 문제가 안된다. immutable 하니까. 오오 immutable 오오

But without mutation, we can implement either way

– No code can ever distinguishe aliasing vs identical copies
– No need to think about aliasing: focus on other things
– Can use aliasing, which saves space, without danger

ML 에서는 tl 이 상수 시간내에 이뤄진다. 첫번째 원소를 제외한 나머지를 가리키기만 하면 되니까. 어차피 그 데이터는 immutable 이니까 그냥 쓰기만 하면 된다. 변경이 필요하면, 그 때 새로 만들면 된다.

Java Mutation

public String[] getAllowedUsers() {  
  // return a references of allowedUsers
}

allowedUsers 자체가 private 여도, 다음과 같은 코드에 취약하다.

p.getAllowedUsers()[0] = p.currentUser();  
p.useTheResource();  

따라서 위의 getAllowedUserscopy 를 돌려줘야한다.

ML 같은 immutable 한 언어에서는 Reference (Alias) vs Copy 는 문제가 안된다.

Pieces of a Language

언어를 배울때는 다음의 다섯가지를 고려해야한다.

(1) Syntax: How do you write language constructs?
(2) Semantics: What do programs mean? (Evaluation rules)
(3) Idioms: What are typical patterns for using language features to express your computation
(4) Libraries: What facilities does the language provide standard?
(5) Tools: What do language implementations provide to make your job easier? (REPL debugger..)

다시 말하면 다섯가지를 모두 배워야 한다. 언어의 코어부터 그 확장인 라이브러리와 툴까지. 그러나 이 코스에서는 SemanticsIdioms 에 집중한다. ML 을 고른것도 그 이유고, 이걸 잘 이해하게 되면 Libraries 가 어떻게 구성되었는지 더 잘 이해할 수 있다.

Summary

처음엔 재귀가 어려웠는데, 시간이 지날수록 재귀가 얼마나 재밌고 강력한지 알게 된다. 함수를 building block 처럼 조립하는것도 너무 재밌고

Lisp 을 이용했으면 개인적 취향에 맞아 더 재밌게 배울 수 있었을텐데. 나중에 수업이 모두 끝났을때 ML 을 고른 이유를 느낄 수 있었으면 좋겠다.

그리고 Emacs sml-mode 가 좀.. 음.. 빈약한데 더 좋은걸 찾아야겠다. MELPA 엔 없던데.. 테스팅 프레임워크도 좀 찾아서 해보고.