how lazy evaluation works in haskell

Lazy evaluation이 동작하는 방식

게으른 평가(lazy evaluation)는 하스켈 프로그램이 실행될 때 광범위하게 사용된다. 게으른 평가의 적용은 코드를 보다 단순하게 만들어줄 수 있지만, 초보자에게는 종종 메모리 사용과 관련된 함정이 되기도 한다. 예를 들어 foldl (+) 0 [1..10^8] 이라는 간단한 표현식은 계산에 있어 수기가바이트의 메모리를 요구한다.

게으른 평가는 일종의 트레이드 오프이다. 이는 코드를 단순하게 만들어주지만 그것이 튺정한 프로그램에서 실제로 어떻게 평가하는지 완전히 이해할 수는 없게 된다. (케바케라서…)

그래프 축약

하스켈 프로그램은 표현식을 평가하는 것으로 실행된다. 다음 함수를 예로 들어보자.

square x = x * x

그리고 다음 표현식을 평가해보자.

square (1 + 2)

이 식은 square라는 함수의 인자를 (1+2)라는 표현식으로 대체하여 다음과 같은 표현식으로 치환된다.

square (1+2)
=> (1+2)*(1+2)

그리고 (+), (*) 함수가 계속해서 평가된다.

(1+2) * (1+2)
=> 3 * (1 + 2)
=> 3 * 3
=> 9

다시 처음의 식을 그래프로 표현해보자.

square _
       |
       + _ _
         | |
         1 2

각각의 라인은 함수의 적용이다. 맨 앞은 함수의 이름, 그 뒤 언더스코어로 표시한 빈 칸들은 각각의 인자가 된다. 이러한 그래프는 마치 컴파일러가 메모리 포인터를 이용해서 표현식을 나타내는 방식과도 많이 닮아 있다.

프로그래머가 작성하는 모든 함수들은 축약법칙을 따르는데, 이는 함수 적용이 결국 우변의 표현식으로 대체된다는 의미이다.

square _  ==>  * _ _
       |         \ |
       x            x

위 그래프에서 x는 함수의 인자이고, 표현식일 수 있기 때문에 서브 그래프를 함축한 표현이된다. 이 때 (*) 함수의 두 인자가 동일한 그래프를 가리키고 있는 점에 유의하자. (하스켈의 모든 것은 함수이므로, 같은 이름은 같은 포인터라 봐도 무방하다.)

어떤 그래프가 축약 가능한 경우 이를 reducible expression이라고 하고 줄여서 redex (여기서는 리딕스라 하겠다.)라 부른다.

square _
       |
       + _ _
         | |
         1 2

위 그래프에서 1행과 2행의 그래프는 각각 리딕스이다. 각각의 리딕스를 위에서부터 순차적으로 축약해 나가보면

square _ (r)        ==> * _  _         ==> * _ _ (r) ==> 9
       |                  ㄴ |                \|
       + _ _                 + _ _ (r)         3
         | |                   | |
         1 2                   1 2

위와 같이 축약을 거듭해 나가는 것으로 최종 값이 산출된다. 최종값 9는 더 이상 축약될 수 없는 데 이러한 모양의 그래프를 normal form이라 하다. 노멀폼에는 이러한 단위 숫자만 올 수 있는게 아니라 특정한 콘크리트 타입의 상수(중 일부)가 올 수 있다. 이를테면 리스트 말이다.

: _  _
  |  |
  1  : _  _
       |  |
       2  : _  _
            |  |
            3  []

위 그래프는 리스트 1:2:3:[]을 나타낸다. 이 리스트는 하나의 데이터타입에 대한 값이므로 더 이상 축약될 수 없고, 따라서 노멀폼이다. 즉, 어떤 그래프의 최상위 노드가 컨스트럭터일 때 해당 그래프는 (항상은 아니다) 노멀폼이된다.

노멀폼이 되는 조건이 두 가지 있는데, 하나는 유한해야 한다는 것과 다른 하나는 순환이 없어야 한다는 것이다. 다음 식을 보자.

ones = 1 : ones

이 식은 그래프로 표현하면


┌───────┐ : _ _ │ | │ │ 1 └─┘

위와 같이 순환하는 구조가 된다. 이 그래프는 리딕스가 아니다. 그러면서도 순환이 발생하기 때문에 노멀폼도 아니다. 리스트의 꼬리는 재귀적으로 자기자신을 가리키면서 결과적으로 무한리스트가 된다. 이와 같이 노멀폼을 가지지 않으면서 무한 루프에 대응하게 되는 표현식들이 존재할 수 있다.

하스켈에서는 실질적으로 표현식 평가가 바로 노멀폼으로 이어지지는 않는다. 보통은 그래프를 축약해나가다가 weak head normal form을 만나면 일단 평가를 멈추게 된다. (약어로 WHNF라 한다) 우선 그래프의 탑노드가 컨스트럭터라면 WHNF라 말할 수 있는데, 예를 들어 (7+12):[] 은 다음과 같이 WHNF가 된다.

:  _   _
   |    \
  + _ _  []
    |  \
    7  12

위 그래프는 노멀폼은 아니지만, 최상위 노드가 :이므로 WHNF이다. 반면, WHNF가 아닌 형태의 그래프는 청크 혹은 미평가식이라한다. 위 그래프에서 최상위 노드는 컨스트럭터이지만, 첫번째 인자는 미평가된 식이다.

이러한 WHNF에서 흥미로운 점은 위에서 언급한 ones이다. 이 그래프의 탑노드는 컨스트럭터이므로, 하스켈에서는 무한 리스트를 표현하고 다룰 수 있다. 이런 점은 코드를 보다 모듈단위가 될 수 있게 해준다.

평가 순서, 게으른 평가

하나의 표현식이 여러 리딕스를 포함하는 일은 흔하다. 이 때 이들을 축약하는 순서가 중요할까?

eager evaluation라 불리는 축약방법은 함수 파라미터를 적용하기 전에 먼저 축약한다. 따라서 함수가 실제로 평가되기 전에 파라미터들이 모두 평가된다. 대부분의 언어가 이런 방식을 적용한다.

하지만 하스켈 컴파일러는 좀 더 다른 방식을 적용한다. 이른바 게으른 평가인데, 상위 노드를 먼저 평가하려 한다.

&& 연산자가 평가되는 방식을 살펴보자. 다음의 식을 생각해보자.

('H' == 'i') && ('a' == 'm')

이 연산식은 아래와 같은 그래프로 구성된다.


(&&) _ _ :1 │ │ │ └ (==) _ _ :3 │ │ \ │ 'a' 'm' (==) _ _ :2 │ \ 'H' 'i'

위 그래프에서 :2, :3은 축약 가능한 리딕스인데 그 중 먼저 계산되는 것은 :2이다. (==) 'H' 'i'False로 축약된다. 축약된 식은 (&&) False x 가 되는데, 하스켈은 이 때 탑노드를 평가하려고 시도한다. &&의 정의에 따라,

(&&) :: Bool -> Bool -> Bool
True && x = x
False && x = False

이는 두 번째 파라미터가 노멀폼이 되든 안되든 탑 노드가 리딕스가 된다. 그리고 축약하면 False가 된다.

이를 수식형태로 다시 표현하면 다음과 같다.

('H' == 'i') && ('a' == 'm')
=> False && ('a' == 'm')
=> False

위에서 계산했던 square 의 식을 써보면

square (1 + 2)
=> let x = (1 + 2) in x * x
=> let x = 3 in x * x
=> 9

시간복잡도와 공간복잡도

시간

표현식을 평가하는데 얼마나 많은 단계가 필요할까? “급한 평가”에서 이는 간단하다. 모든 함수 평가에 대해서 각 파라미터를 평가하는데 걸리는 시간의 총 합과 함수를 계산하는데 드는 시간을 더하면 된다. 하지만 느린 평가에서는? 게으른 평가는 가능한 평가를 뒤로 미룬다 뿐이지 실제로 급한 평가보다 계산을 더 많이 하지는 않는다. 대신 위에서 본 바와 같이 운이 좋다면 미평가식을 포함한 계산식은 리딕스가 될 수가 있고 이 경우에는 급한 평가에 비해서 적은 단계로 계산이 수행될 수 있다.

공간

게으른 평가는 시간과 공간의 트레이드 오프이다. 게으른 평가는 시간에 있어서는 이익을 볼 수 있지만 공간에 대해서는 손해를 볼 수도 있다. 계산에 필요한 메모리의 크기는 미평가식의 크기만큼이나 쓰이기 때문에 노멀폼에 비해서 엄청나게 큰 용량의 메모리를 쓸 경우가 있다.

특히 리스트를 접는 foldl 함수의 경우 느리게 평가되면서 단순히 연속된 자연수의 합을 구하는 계산이 수십기가바이트의 메모리를 요구하는 경우가 있을 수 있다.

project euler 33

오일러 프로젝트 33 번

분수 49/98에는 재미있는 성질이 있습니다. 수학을 잘 모르는 사람이 분모와 분자에서 9를 각각 지워서 간단히 하려고 49/98 = 4/8 처럼 계산해도 올바른 결과가 됩니다.

이에 비해 30/50 = 3/5 같은 경우는 다소 진부한 예라고 볼 수 있습니다.

위와 같은 성질을 가지면서 '진부하지 않은' 분수는, 값이 1보다 작고 분자와 분모가 2자리 정수인 경우 모두 4개가 있습니다.

이 4개의 분수를 곱해서 약분했을 때 분모는 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=33

여기서 진부한 경우란 분모, 분자가 모두 0으로 끝나는 경우들을 가리킨다.

from functools import reduce 

def gcd(a, b):
    a,b = (a, b) if a > b else (b, a)
    if a % b == 0:
        return b
    return gcd(b, (a%b))

def getFractionValue(q, d):
    g = gcd(q,d)
    return (q//g, d//g)


def test(n1, n2):
    if n1 % 10 == 0 or n2 % 10 == 0:
        return False
    l1 = [int(x) for x in list(str(n1))]
    l2 = [int(x) for x in list(str(n2))]
    v = getFractionValue(n1, n2)
    for i in l1:
        if i in l2:
            l1.remove(i)
            l2.remove(i)
            v2 = getFractionValue(l1[0], l2[0])
            if v == v2 :
                return True
    return False

def e033():
    answers = []
    for y in range(11,100):
        for x in range(10,y):
            if x < y and  test(x, y):
                answers.append((x, y))

    uppers = [ i[0] for i in answers]
    lowers = [ i[1] for i in answers]

    u = reduce(lambda x,y:x*y, uppers, 1)
    l = reduce(lambda x,y:x*y, lowers, 1)
    g = gcd(u, l)
    print(l/g)

%time e033()
# 100.0
# Wall time: 37 ms

파이썬 커맨드라인 실행방법

Windows7 명령줄도구에서 파이썬 스크립트 실행하기

기본적으로 파이썬을 설치하면 PATH 환경변수에 파이썬의 설치 경로가 추가된다. 이를 확인해보려면 명령프롬프트를 열고 path라고 입력한다음 엔터.

d:\temp>path
PATH=.......;C:\python34\;C:\python34\scripts\;........

여기서 C:\python34눈 파이썬 인터프리터인 python.exe가 설치되어 있는 곳이고, C:\Python34\Scripts는 그외 파이썬의 부가패키지의 실행파일들이 설치된다. 다른 패키지를 내려받고 설치하도록 도와주는 pip같은 것들이 여기에 설치된다고 보면 된다.

윈도 환경변수 PATH는 실행파일이 있는 위치를 지정하여, 실행파일의 전체 경로를 적지 않고도 해당 파일이 실행될 수 있도록 한다. 파이썬의 설치경로가 PATH에 포함되어 있다면 명령줄 도구에서 파이썬 스크립트를 다음과 같이 실행할 수 있다.

d:\temp> python mycalc.py 1 + 3
4
# 이 때 mycalc.py 는 d:\temp\ 에 위치한다.

OSX나 리눅스에서는 보통 기본적으로 파이썬이 설치되어 있고, 주로 /usr/bin/python이나 /usr/local/bin/python 등의 경로로 설치되어 있다.

py, pyw

환경변수 설정에 어려움을 겪는 사람들이 많아서인지, 요즘의 파이썬 설치 패키지에는 py.exe라는 파일이 포함되어 있다. 이 파일은 파이썬 인터프리터를 실행해주는 역할을 하며, C:\Windows 폴더에 들어가게 된다. 보통 이 경로는 기본적으로 PATH에 포함되어 있기 때문에 다음과 같이 실행해도 된다.

d:\temp> py mycalc.py 1 + 3
4

py.exe는 특히 파이썬이 2개 이상 버전으로 등록된 경우에 유용하게 쓸 수 있다. 예를 들어 파이썬 2.7과 3.4가 동시에 설치되어 있고, 이중 2.7이 PATH에 포함되어 있다면,

  • py : 디폴트 설정 버전을 실행한다.
  • py -2 : Python 2.x 대 버전을 실행한다.
  • py -3 : Python 3.x 대 버전을 실행한다.

PATHEXT

하지만 파이썬 스크립트를 실행할 때 매번 앞에 python 이나 py를 붙이는 것도 귀찮을 때가 있다. 배치 파일 같은걸 만들어서 쓰는 사람도 있을 수 있겠지만, 윈도에서 리눅스처럼 스크립트명 만으로 해당 스크립트를 실행할 수 있다.

리눅스나 OSX에서는 파이썬 소스코드 맨 첫줄에 #! python, #!/usr/bin/python 등으로 인터프리터 명령이나 경로를 지정해놓으면, 해당 인터프리터로 알아서 실행된다. 이는 펄, 루피, JS 스크립트등 모든 스크립트에 대해서 공통적으로 지원되는 기능이다.

파이썬 설치시에 .py 파일을 파이썬과 연결할 것이냐는 걸 물어보는데 (보통은 그냥 체크하고 넘어갈테다) 이 옵션을 사용해서 설치했다면 아마 설정이 되어 있을 것이다.

윈도 환경변수중에는 PATHEXT라는게 있는데, 이는 특정 확장자를 가진 파일을 실행가능한 것으로 인식하게끔한다. 윈도 명령행에서 각 환경변수는 %를 앞뒤로 붙인 이름으로 인식한다.

d:\temp>echo %PATHEXT%
.COM;.EXE;.BAT;.CMD;.VBS..... ;.PYW;.PY

위 와 같은 식으로 .PYW, .PY가 등록되어 있다면 mycalc.py 라는 스크립트는 다음과 같이 실행할 수 있다는 의미이다.

d:\temp> mycalc.py 2 + 3
....?

실행이 되면 좋겠다. 하지만 모든 시스템의 상태가 동일하다고 보장할 수는 없으니 실행이 안되는 사람도 있을 수 있다. 물론, 많은 경우에는 py 명령이면 충분하겠지만, 스크립트 이름만으로 실행하고픈 사람이라면 아마 파이썬으로 여러가지 도구를 만들어서 쓰려는 사람일것이니, 약간의 도움을 주겠다.

assoc, ftype

윈도에서는 특정 파일의 확장자가 어떤 파일인지를 식별하고, 어떻게 실행할 것인지를 따로 저장해서 관리한다. 명령줄에서 이를 확인하고 변경할 수 있는 명령이 assoc, ftype이다.

assoc 명령은 특정 확장자 파일이 어떤 형식인지를 시스템으로부터 알아내거나 이를 변경할 수 있다. 파이썬과 관련된 확장자와 그 파일타입은 다음과 같은 값이 있다.

  • .py=Python.File
  • .pyc=Python.CompiledFile
  • .pyw=Python.NoConFile

이 명령을 어떻게 쓰는지 궁금하면 /?를 붙여서 실행해본다. 물론 MS프로그램의 도움말은 30년전부터 그다지 도움은 되지 않는게 대부분이다.

d:\temp>assoc /?
파일 확장명 연결을 보여주거나 수정합니다.

ASSOC [.확장명=[파일 유형]]

  .확장명   파일 유형과 연결할 파일 확장명을 지정합니다.
  파일 유형 파일 확장명과 연결할 파일 유형을 지정합니다.

현재 파일 연결을 보려면 매개 변수 없이 'ASSOC'라고 입력합니다.
ASSOC가 파일 확장명만 가지고 불려진 경우, 해당 파일 확장명에 대한 현재
파일 연결을 보여줍니다. 파일 유형에 대해 아무 것도 지정하지 않으면
명령은 해당 파일 확장명의 연결을 제거합니다.

이제 assoc 명령을 아무런 인자없이 실행하면 전체 리스트를 보여준다.

d:\temp> assoc
...
...

근데 양이 엄청 많을 것이다. 뭐 인내심이 강한 사람이라면 assoc | more와 같이 실행해서 하나하나 찾는 방법이 있겠지만, 우리는 바쁘니까 다음과 같이 실행한다.

d:\temp>assoc | findstr ".py"
.py=Python.File
.pyc=Python.CompiledFile
.pyo=Python.CompiledFile
.pys=pysFile
.pyw=Python.NoConFile

만약 여기에 .py=Python.File이 없다면? 아래와 같이 연결을 만들어준다.

d:\temp>assoc .py=Python.File
.py=Python.File

이제 다음은 ftype으로 해당 타입의 파일을 어떻게 실행할 것인지를 정해준다. 역시 ftype은 assoc과 비슷한 사용법을 가지고 있다. 먼저 파일 타입 연결을 확인한다.

d:\temp>ftype | findstr "python"
Python.CompiledFile="C:\Python34\python.exe" "%1" %*
Python.File="C:\Python34\python.exe" "%1" %*
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Python.NoConFile="C:\Python34\python.exe" "%1" %*

대충 위외 비슷한 값이 나오면 된다. Python.File="C:\Python34\python.exe" "%1" %*이 부분이 가장 중요하다. 만약 없거나 다르게 되어 있다면 수정하도록하자. 단, 여기서 C:\Python34는 파이썬의 설치 경로여야 한다. 파이썬을 다른 데 설치했으면 알아서 잘 변경하도록 하자.

d:\temp>ftype Python.File="C:\Python34\python.exe" "%1" %*
Python.File="C:\Python34\python.exe" "%1" %*

레지스트리

여기까지 했을 때 잘되면 좋은데, 그래도 안되는 경우가 있다. 이건 다 윈도때문인데, 윈도는 레지스트리에 이런 정보를 또 따로 저장하는데, 이게 위에서 설정한 것과 안 맞으면 안되는 경우가 있다. (안맞아도 되는 경우도 있다!)

그래서 이게 안되면 레스트리 편집을 해야하는데, 여기서는 힌트만 주겠다. 왜냐면 레지스트리 편집을 부주의하게 하는 경우, 시스템이 정상작동하지 않는 불상사가 생길 수 있는데 그 책임을 내가 대신 져줄 수는 없기 때문이다. “나는 레지스트리를 잘 모른다” 하는 사람은 그냥 좀 불편해도 py 명령 정도로 만족하고 지내도록 하자.

  1. HKEY_CLASSES_ROOT\.py 키의 값이 Python.File 인지 확인한다.
  2. HKEY_CLASSES_ROOT\Applications\python.exe\shell\open\command 키의 값이 "C:\Python34\python.exe" "%1" %*인지 확인한다.
  3. 일부 시스템의 경우에는 HKEY_CLASSES_ROOT\py_auto_file\shell\open\command 이 키를 참조하여 실행하는 경우가 있다. 역시 "C:\Python34\python.exe" "%1" %*라는 값이 들어가 있는지 확인한다.

일단 여기까지 하면

d:\temp> mycalc 1 + 3
4

와 같이 파이썬 스크립트를 일반 명령처럼 쓸 수 있고, 자신이 생각하기에 유용하다 생각되는 스크립트는 어디 한 군데 몰아놓고 PATH에 추가해두면 유용하게 쓸 수 있다. 나의 경우, 명령줄에서 간단한 수식을 계산할 수 있는 calc.py나 우리 동네 대기 오염 정보를 가져와서 출력해주는 스크립트 등을 만들어서 한군데 모아놓고 사용하고 있다.

flex활용

flex-box 활용법

플렉스박스 레이아웃을 구성하는 요소는 컨테이너와 개별 아이템으로 나뉘어지며, 각각의 요소에 대해서 주로 적용하는 속성은 다음과 같다.

컨테이너

컨테이너는 우선 다음 항목을 적용한다.

.container {
    display: flex;
}

컨테이너 내부 아이템은 자신이 얼마나 늘어나고 줄어들 것인지를 결정한다.

.item {
    flex: 1 0 auto;
}

단일 요소의 가운대 배치

가로 방향으로 이어지는 단일 요소를 가운데로 정렬하고 align-items: center 속성을 부여한다. 이는 진행 축의 직교 방향으로 아이템을 배치하는 방법을 나타낸다.

복수요소의 가운대 배치

복수요소의 세로 가운데 배치는 단일 컨테이터-아이템 구조로는 구현할 수 없고, 각각의 아이템이 이너 컨테이너로 기능해야 한다.

project euler 32

오일러 프로젝트 32 번

1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다.
예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다.

7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다.

이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까?

(참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다)

http://euler.synap.co.kr/prob_detail.php?id=32

팬디지털 숫자인지 확인해보는 것은 정렬해서 “123456789” 인지만 보면 된다. 케이스는 2자리x4자리=4자리, 3자리x3자리=3자리의 경우가 있을 수 있으므로 이 범위만 체크한다.

def check_pandigital(a, b):
    c = a * b
    d = "%d%d%d" % (a, b, c)
    return "".join(sorted(d)) == "123456789"

def e32():
    s = set()
    for a in range(1,10):
        for b in range(1234,9999):
            if check_pandigital(a, b):
                s.add(a*b)
    for a in range(12, 100):
        for b in range(123,1000):
            if check_pandigital(a, b):
                s.add(a*b)
    print(sum(s))

%time e32()

# 45228
# Wall time: 548 ms