유학

. 과연 가능한가?
내 학점이 별로 안 좋아서 TOP4(MIT,CMU,Stanford,Berkeley)는 불가능.
전공이 CS라서 사실 TOP20도 힘들 것 같다.
다른 분야와 달리 CS는 특히 미국이 잡고 있고 유명한 IT업체도 거의 미국에 있다. 공대 중에서 미국인들이 많이 간다.
학교 유학 게시판을 보면 3.9 정도면 자신들이 별로라고 생각하고
4.0 쯤 되는 사람들이 수두룩하다.

아마도 내가 생적은 게시판에 2년에 한 번쯤 올라오는 최하위권자가 아닐까 싶다. (3.5~3.6은 안 가는 걸까? 안 올리는 걸까?)

. 유학준비
그래도 한 번 준비를 해도면 인생에 큰 도움이 될 것 같다.
세상에 KAIST말고도 수많은 학교가 있다는 것도 알게 되고
결국 이 바닥에 있으면 이름 정도는 알고 있어야 하는 학교와 교수들, 사람들 아니던가. (일단 학교이름과 대가들 이름은 줄줄 알게 되지.)

유학준비 하는 사람들은 다들 나보다 실력있는 사람들이니 친해지는 것만으로도 큰 도움이 될 것이다.
TEPS로 찌질대며 영어공부하는 것보다 GRE, TOEFL을 공부하는 게 더 큰 도움이 될 것 같다.
SOP, resume, contact mail쓰면서 writing 연습도 해보고
어디든 일단 interview도 좀 받아보고 교수님들 찾아가서 추천서도 받고
다 그런게 인생 경험이라고 생각한다.

GRE 공부를 하면 교양에도 도움이 꽤 될 것 같다.
TEPS를 공부했을 때도 reading을 읽으면서 교양글들이 참 재미있다는 생각이 들었다. 공돌이가 이런 다양한 분야의 글을 읽을 기회를 자연스럽게 잡으려면 GRE공부나 CNN시청이 좋을 듯하다.

다 reject되도 영어 실력이 남을 테고 내 실력과 한계를 평가해 볼 수 있다.
시도와 노력은 해봤으니 최소한 후회가 되지는 않는 인생이 되겠지.
뭔가 목표가 있는 인생이 되면 그것이 이루어지든 그렇지 않든 그것을 보고 달려가면서 운동이 된다.
목표 없이 방황하는 것보다는 내가 가능한 것보다 약간 높게 잡아두면 김빠지지 않고 열심히 살겠지.

. 기회들
벌써 25살이나 되버렸지만, 사실 19살에 생각했던 것과는 달리 아직도 인생의 기회는 넘치게 남아있다. 지금 해보고, 석사 후에도 또 도전해보고, 석사 후에 연구소를 다니면서 또 도전해볼 수도 있다. 포닥때도 있고.
유학 준비 경험이 나중에 해외 취업 준비에 도움이 될 수도 있다.

. 상위 대학들 중 한국인들이 많은 곳들. (어드미션 포스팅 참고해서 대충 적어봄)
CMU
University of Texas Austin
UCLA
Maryland
Texas A&M (TAMU)
USC

[CG]Star trek II - The wrath of Khan

이번 CG term project 주제다.
The wrath of Khan을 보면 genesis bomb라는 것이 나온다.
Moon-like한 아무도 살지 않는 황폐한 planet에 bomb를 떨어뜨리면
seed가 뿌려지면서 6분만에 earth-link한 살아있는 planet이 된다.

일단 잿빛 행성에 불꽃이 튀면서 화염(wall of fire)이 일고 행성 전체를 덮은 후 붉은 색이 푸른색으로 바뀌면 대기가 생기고 바다와 산이 생긴다.

얼마나 비슷하게 구현할 수 있을 지 모르겠다.
상당히 조악한 수준이겠지만 잘 만들어 봐야지.
23년 전 루카스 필름에서 했던 일을 이제는 내 컴퓨터에서도 할 수 있게 되는 것인가.
(이론적으로는 가능하다. 내 실력이 한계가 될 뿐.)
오늘 하루 종일 논문 3개 읽고 플젝mate와 찌질거리면서 토론하고, 조언자 Ein군에게 문의해서 이것저것 하게 될 것 같다.
너무 오래된 논문이라 교수님께서 뭐라고 하시지는 않을 지 모르겠네..
(난이도도 낮은 편인 듯 하다.)
다른 논문들은 다들 90년대 후반이나 2000년에 나온 것들이다.

시험 끝

'시험 끝'이라고 선언했으면 좋겠지만 시험은 여전히 남아있다.

하지만 Numerical analysis는 원래 시험기간과 독립적이고
공부할 때 pressure가 적은 편이다.
산타할아버지 같은 라스무센 교수님이 떠올라서인 것 같다.
항상 칠판에 글을 적다가 실수하실때마다
"Oh, hohohoho~ OK."라고 말하신다.

CG 발표도 미칠것만 같았는 데, 몇 시간 빈둥거리니 왠지 만만해 보인다.
역시 중요한 것은 심리적인 상태인가.
뭔가 자신감이 솟아 있을 때 하면 용기 백배하여 금방 해결될 듯 하다.
(지난 3일간은 아무것도 되지 않았다.)

대학원생들은 참 불쌍해보인다. '시험 끝'이라고 선언할만한 게 없이
빙글빙글도는 대학원생활을 해야 하다니.

내일은 논문 몇 개 읽고 공상과학 소설 같은 proposal을 써야 겠다.
작년 졸업연구에서도 드러난 것처럼 나는 헛소리에는 소질이 있어보인다.
"그래서 어쩔건데?"라고 묻는 교수님의 반응에도 태연한 것을 보면;;
(과연 석2, 박사 고년차에도 그런 반응을 할 수 있을 지는 모르겠지만..)

아직도 시험기간

목요일에도 시험 하나 본다.
그런데 수요일인 오늘.. 별로 공부도 안되고 유학게시판에 돌돌 말리고 있다.
게시판에 보통 글쓰는 사람들은 학점이 4.0 근방인데,
뒤지다보니 3.5 쯤 되는 사람도 몇 있길래, 용기를 가지고 다시 유학을 생각해보는 중이다.
(3년 전에 좀 그렇게 진지하게 생각하고 계획잡고 살았어야 했지만.)

아무튼 늦었다고 생각했을 때라도 시작해봐야 인생이 후회스럽지 않지.
나 뿐만 아니라 주변사람들 모두 병특하고 그냥 국내에서 전산하는 건
삽질이라고 보고 있으니까.
한국 이공계 위기를 고민할 시간에 영어 단어 암기에 도전하는 게
생산적일꺼라는 생각이 들었다.
기왕사는 거 주사위는 던져봐야지.

여름에 미국 놀러다녀오고 가을에는 불어랑 전공 하나쯤 재수강 하든지 하고(B짜리), GRE, TOEFL 공부에 전념해야 겠다.
조낸 공부해서 점수를 확보한 다음..
석사는 일단 KAIST로 가고 대학원에서 교수님과 잘 상담해서
박사는 외국에서 하고 싶다고 해봐야지.

TOP 20이면 어떻게든 하나쯤은 되지 않을 까 싶다.
(예전처럼 TOP5 아니면 KAIST가 최고지 하는 생각은 아니니까.)
미국이라고 다 좋겠냐만은 아무튼 여기는 사람들 꿈이 많이 죽어버린 것 같다.

나중에 한국에 와서 외국계 기업 영업사원이 되더라도 영어라도 잘 해 놓으면 좋지 않겠나.
잘 되면 Pixar 가고. ㅋㅋ

---------------------------
그런 의미에서 CG 시험을 잘 봐야 되는 데,
시험에 뭐가 나올지 모르겠다. 공부 포인트를 잡지 못해서
그냥 빈둥거리게 되네.

---------------------------
CG랩 석사 2년차 중국인 학생이 CG term project team member를 구하고 있다.
솔직히 한국인들의 성향으로 봐서 member 구하기 힘들듯한데,
리암과 상의해서 같은 팀을 하면 어떨까 생각 중이다.
원래 2인 1조인데, 교수님께 졸라서 3인 해달라고 해볼 생각.
(우리 둘은 학부생이고 중국인은 석사생이니까.)
영어로 대화하다보면 영어도 도움되고 CG실력도 늘지 않을까.

맛과 온도 - 음료수

음료수는 왜 모두 달거나 신맛일까?
자판기 앞에서서 음료수들을 보면 모두 단맛이나 신맛 밖에 없다.
가장 특이한 것이라고 해봐야 쓴맛이 아주 약간나는 녹차음료.

왜 짠맛은 이용하지 않는 걸까?
짠맛 음료수는 시장에서 성공할 수 없을 까?

생각해보면 세상 사람들은 짠맛도 좋아한다.
햄, 치즈, 햄버거, 피자, 감자튀김, 오뎅 등..
다들 짠맛이다.

그런데도 음료수에는 짠맛이 없는 이유는 뭘까?
그것은 온도 때문인 것 같다.

일반적으로 음료수는 캔으로 보관, 판매하는 데 따뜻하게 만들면 유통기한도 짧아진다.
아무튼 그래서 어떤 음료든 다 차게 나온다.
(따뜻한 데자와도 운반시에는 차게 운반하고 자판기에서 데워서 판다.)

단맛이나 신맛은 차가운 것과 어울리고 짠맛은 따뜻한 것과 어울린다.
그래서 짠맛 음료수는 캔으로 안 파는 것 같다.

오뎅 국물을 캔에 담아서 팔면 어떨까?
겨울에는 잘 팔리지 않을 까?
포장마차 상인들을 죽이는 너무 야박한 짓일까?

타협

인생에는 고민해도 풀리지 않는 문제가 있다.
예컨대 오늘 내야하는 CG숙제가 그렇다.
아무리 봐도 문제를 이해할 수가 없다.

교수님께서 내준 모호하고 불완전한 문장을 스스로 채워서
풀었으면 좋겠지만 도저히 알 수가 없다.
TA 형님들도 별다른 comment가 없다.

사실 지난 번에도 이상한 숙제가 나왔는 데,
결론은 교수님의 진술자체가 false라고 적어서 냈더니 맞았다고 해줬다.
(교수님께 몇 번 질문했을 때는 "아무튼 풀어보게."라고 하셨다.)

이번에도 내 생각대로 성의 보이는 선에서 이것저것 적고 자의적인 마무리를 지어야 겠다.
특히나 이번 문제의 내 해법은 공학적이라기보다는 오히려 인문학적이지만 어쩔 수 없지뭐.
부분 점수를 약간 구걸하고 중간고사 시험 공부에 집중해야 겠다.

오늘은 고민하느라 공부 하나도 못했군..
공부 시간의 절반은 스트레스 컨트롤(마인드 컨트롤)에 쓰는 것 같다.

[소설]스페이드 여왕 - 푸쉬킨

. 푸쉬킨
  근대 러시아 문학의 확립자
  19세기초반 러시아 낭만주의
  "대위의 딸", "스페이드 여왕" 등을 지음
  청년장교 단테스와 결투 중 사망
  도스도에프스키 등에게 영향을 줌

. 배경 : 페테르부르크
. 스페이드 여왕 : 감추어진 불길함.
. 트럼프 : 카드 놀이
. 페아로 : 트럼프의 일종

. 톰스키 :
  백작부인의 손자, 이 소설의 나레이터에 해당함.
  도박을 즐기면서 장교 친구들에게 할머니에 관한 이야기를 시작함.

. 오를레앙 공작 :
  베르사유라는 도박장에서 도박을 함

. 한 장교의 할머니(안나 페도로브나 백작부인) :
  젊었을 때 아름다운 용모와 함께 프랑스 파리에 방문
  아들이 넷인데, 모두 상습도박꾼.
  카드 석장을 연속으로 이김.
  나이가 들어서 정신이 오락가락함.
  양녀에게 매우 변덕, 심술을 부림.
  사교에게서 추앙을 받아 성격이 이기적이고 나빠짐.
  젊었을 때의 화장을 하고 항상 무도회에 나타남.
  항상 무도회에 갔지만 늙은 그녀와 놀아주지 않았다.
  하인들도 몰래 주인의 재산을 빼돌렸다.

. 생제르맹 백작 :
  신비에 싸인 인물, 할머니에게 돈을 따는 법을 알려줌.

. 리자베따
  할머니의 양녀, 원래 가난한 사람이었음.
  항상 백작부인에게 책을 읽어주고 심술도 들어줘야 했다. 
  원래의 신분때문에 아무도 그녀와 놀아주지 않았다.
  외모와 복장은 화려했지만 항상 혼자서 울었다.
  게르만을 돕지만 그는 리자베따를 배신하고
  그녀는 집사의 아들과 결혼하여 행복하게 산다.

. 톰스키 알렉산드로비치 공작
  할머니에게 책을 선물함.

. 게르만 :
  러시아에 귀화한 독일사람, 장교, 톰스키의 친구, 치밀하고 강직해서 절대 도박을 하지 않음. 원래 가난한 집안이었기 때문에 러시아로 귀화함.
  백작부인을 꼬시던지, 친해져서 카드의 비밀을 알아내려고 함.
  일단 백작부인의 양녀에게 관심을 보임.
  끈질지게 편지를 보내 결국 그녀도 관심을 갖게 된다.
  하지만 그녀를 배신하고 백작부인을 협박한다. 백작부인은 놀라서 죽어버린다.
  백작부인의 환상은 장례식날 밤 그를 찾아와 비밀의 숫자 - 3, 7, A을 알려준다.
  그것을 그대로 따른 그는 도박장으로 달려서 이틀 연속으로 이기게 된다.
  그러나 마지막날 A대신 스페이드 퀸이 나오는 바람에 지게 된다.
  그 스페이드 퀸을 보고 그는 백작부인이 자신을 속인 것이라고 믿는 다.
  결국 그는 미쳐버리고 정신병원에 입원하여 계속 같은 숫자만 외치게 된다.

----------------
요즘 사회는 상류층이라고 하면 대부분 law school이나 MBA을 떠올리는 데,
30년 전 한국이나 100년전 유럽은 사관학교가 그 역할을 했던 것 같다.
야심차고 수많은 전쟁을 통해서 지위도 상승시키고 권력층과 친해져 보려는
수많은 장교들의 이야기가 나온다.
처음에는 가난하지만 전쟁에서 승리하여 영웅이 되어 돌아오는 장교 등..

러시아와 독일인들의 사고관의 차이도 보이는 것 같다.
치밀하고 절대 도박을 하지 않는 독일인과 도박 중독자들이 많은 러시아.
러시아라고 하면 보드카와 러시아 룰렛이 떠오르는 것도 그런 이유인가.

[소설]토요일 - 헉슬리

화창한 토요일의 하이드 파크.
연인들은 팔짱을 끼고 돌아다니고 아저씨들도 오래된 아내들에게
선물을 하고 싶다는 마음이 절로들고 행복으로 넘치는 날씨다.

초라한 몰골에 다 헤어진 구두, 싼티나는 양복을 신은 총각.
그는 지독한 말더듬이이고 월급도 쥐꼬리만 해서 사람들을 사귀지 못한다.
그의 유일한 낙은 매일 혼자 하이드 파크를 돌아다니며
상상의 나래를 펼치는 것이다.

돈많은 과부를 우연히 만나 그녀를 돕고 서로 정이들어 결혼하는 것.
물에 빠진 그의 아들을 구하기도 한다.
자신과 처지가 비슷하지만 아름다운 여인에게 멋지게 말을 걸어
서로 위로하고 잘 사는 해피엔딩을 생각하기도 한다.

그러던 그는 어떤 아름다운 두 여인을 몰래 쫓아가게 된다.
마치 스토커처럼 그녀들이 하는 말을 몰래 엿들으며 새로운 상상을 한다.
그녀들의 개가 위기에 처해있을 때 그 개를 구해주고
자신은 부상을 당해서 보상으로 그들과 친해지고 결국 결혼을 하는 것이다.

하늘도 감동했는 지, 정말로 개가 다른 개와 싸움이 붙었다.
마침 잘된 일이라고 생각한 그는 잽싸게 뛰어들어 손이 다치는 것에도 불구하고 개들의 싸움을 말린다.
그의 생각처럼 모든 것이 진행되었지만 그는 너무나 심한 말더듬이었고
제대로 씻지도 않은 몸이었기 때문에 결국 그녀들은 그에게
동정처럼 1파운드를 주고 급히 사라져 버린다.
그는 멋지게 1파운드는 필요없다고 신사답게 말하고 싶었지만
역시나 너무 긴장해서 아무말도 못하고 바보처럼 돌아와 버린다.

궁시렁거리면서 그 때 했어야 했던 일들을 다시 상상해보지만 언제나 상상 속에서 뿐이다.
그런 생각을 하던 중 해는 저물고 길거리를 걷다가 지독하게 못생긴 창녀를 만난다.
그는 그녀를 피하기 위해 결국 낮에 받았던 1파운드를 다시 던져주고 그녀들이 그랬던 것처럼 사라져 버린다.

불쌍한 사람들에게 필요한 것은 냉혹한 현실보다는 그처럼 상상 속에서라도 행복해 지는 것인지도 모르겠다.
상상 속에서는 말더듬이도 없고 멋진 신사가 되고 미망인을 만나 부자도 되고 파티에서 여인들과 함께 웃을 수도 있으니까.

라디오(Radio)

라디오 청취층은 몇 종류가 있다.
밤에 듣는 사람들 - 주로 학생들이 많다.
출퇴근 때 듣는 사람들 - 운전자들
낮에 듣는 사람들 - 주부 or 자영업 하는 사람들.

나도 중학교 때까지는 라디오를 많이 들었던 것 같다.
밤에 들었던 적은 거의 없는 것 같고 항상 버스를 탈 때마다 매일 같은 시간타고 다니다보니 라디오를 많이 들을 수 있었다.

주로 듣는 프로는 점심에 하는 "강석, 김혜영의 싱글벙글쇼"라든지,
오후 3~4시 쯤에 하는 "지금은 라디오 시대" 였던 것 같다.
초등학교 등하교나 학원 시간과 잘 맞는 다.

사실 초등학생 독자층을 노린 프로들이 아니라서
어른들 세상 사는 이야기가 주로 나왔다.
그리고 사무직보다는 자영업자라든지, 배달부, 청소부 등..
아무래도 육체 노동을 하는 사람들이 이야기가 더 많았다.
정신 노동을 하는 사람들은 청각을 다른 곳에 쏟을 수 없지만
육체 노동을 하는 사람들은 단순한 작업을 반복하거나
오랜 기다림의 시간동안 무료함을 달래야 하기 때문에 라디오나 음악은 필수다.
역시 라디오는 다른 어떤 것보다도 서민적인 매체인가보다.

작년에 한창 "배철수의 고우영 삼국지"도 들었는 데, 재미있더군.
라디오에서 하는 극들의 특징은 매우 연극같다.
연극처럼 사람들이 다들 과장되게 말한다.
TV처럼 녹화가 가능한 매체지만 라디오 프로들은 녹화가 거의 없다.
생방송으로 하는 경우가 대부분이라 편집도 없어서 연극의 특성을 잘 보존하고
시각적으로 전달이 안되기 때문에 연극보다 더 과장적이기도 하다.

라디오 뉴스를 들어도 TV뉴스 앵커들보다 말을 더 또박또박하고 억양을 더 과장되게 집어 넣는 것 같다.
내가 아는 VOK(KAIST 교내 방송 - 스피커로 라디오처럼 진행)의 한 앵커도 그런 말투를 가지고 있어서 참 재미있었다.

수업교재

교수님들도 각자 수업하는 방식이 다르다.
어떤 교수님은 책과 맞춰서 수업을 하시는 데,
이 경우는 고등학교 때처럼 공부하면 된다.
책만 읽고 들어가면 되니까.

다른 경우는 TP만 보고 하는 경우, 보통 책과 비슷할 수도 있지만 TP는 내용이 부족하다.
그럴 때는 다른 학교들의 TP나 책 저자의 TP를 보면 좋다.
학교마다 curriculum이 거의 비슷하니까.
다른 학교 TP를 copy해서 만드는 경우도 많다.

Stanford, Berkeley 등을 구글에서 찾아보면 Lecture Note들이 잘 되있다. 찾아서 보면 된다.

PL은 교수님이 Stanford TP를 보고 만들었다고 말씀하셨고
CG는 학부 CG껄 보려고 했는 데, 학부 CG가 Maryland TP로 수업을 한단다.
(Maryland CG TP가 꽤 좋은 것 같다. 설명도 친절하고 좋다.)

이런 좋은 걸 왜 예전에는 몰랐을 까?
1. 정보 검색능력이 부족해서.
2. 영어 독해가 안되서 (교과서 읽을 시간도 없는 데, 외국 site에 갈리가 없지.)
3. 검색 엔진이 구려서 그런 거 잘 못 찾았다.(Post-구글 이후 가능해진거다.)
4. 아무도 이런 방법을 말해주지 않았다. (주입식 교육의 폐해)
5. 우물안의 개구리였다. (울 학교와 비슷하거나 더 나은 학교는 국내에는 거의 없지만 세상에는 많다.)

앞으로는 수업들을 때 족보 뿐만 아니라 다른 학교것들도 잘 찾아봐야 겠다.
하지만 벌써 학부 생활이 거의 끝나가는 마당이라 아쉽군.

[소설]어머니 - 서머셋 모옴

라카치라는 살인을 저지르고 7년간 옥살이를 치르고 나온 여인이다.
주위의 따가운 시선을 피해 새로운 동네로 이사를 왔다.
비뚤어진 성격으로 어떤 이웃과도 친해지지 못한다.
심술만 피우고 이웃들을 보고도 안 채도 하지 않는 다.

하지만 그녀에게는 매우 멋진 아들이 있다.
그 아들을 본 이웃들은 그녀와는 전혀 닮지 않는 아들을 보고 놀란다.

사실 그녀가 그런 성격을 가지게 된 것은 아들에 대한 병적인 사랑때문이다.
영화 '올가미'처럼 그녀는 자식을 너무 사랑해서 집착, 질투하게 된다.
사실 그녀가 살인을 저지른 이유도 자식을 괴롭히는 남편을 죽인 것이다.
그래서 세상 어떤 젊은 여자도 자기 아들에게 접근하지 못하게 한다.
그녀에게 접근하는 여자를 보면 괴물처럼 소리를 지르고 인상을 찌푸린다.

결국 아들을 사랑하는 여인을 칼로 찔러 죽이게 된다.
그리고 잡혀가면서도 그녀의 죽음을 확인하고는 "하느님 감사합니다."라고 오히려 좋아한다.
아들을 위해 결국 남편과 젊은 여자를 죽인다.
단순히 어머니라기보다는 자신을 아들의 연인이라고 생각하는 것 같다.

토마스 하디의 '아내'라는 작품과 비슷한 주인공의 집착인 것 같다.
좀 더 잔인하고 과격한 방법으로 말이다.
(오이디푸스 컴플렉스와 반대 방향이네.)

-------
이런 작품들은 중학생이 이해하기는 좀 어려움이 있는 것 같다.
나같은 사람이라면 고등학생이라든지, 성인들이 읽어야 이해할만한 내용인듯.

[PL]2006 봄학기 중간고사 문제 정리

생각나는 대로 적어봤음.

시험시간 : 2시간 (1시간이면 충분한 내용이었음.)
자리배치 : 학번 마지막 자리로 hash해서 두 숫자씩 한 공간을 정해줌.
시험인원 : 대략 90명
분량 : 7장, 6문제 - 시험지에 바로 답을 적어서 냄.

. 용어 설명하기(3줄 이내) - 족보와 거의 일치했음.
  type error
  type system
  polymorphism
  Overloading
  type check를 하면 어떤 이득이 있나?

. CFG보고 parse tree 그리기, ambiguous 판별하기
  . ambiguous 함

. Compile과정 적기
  . source code
  . lexical anaylsis
  . parse tree
  . Abstract syntax tree
  . intermediate code
  . optimization
  . machine code

. Denomational semantic가 주어지고 해석하기
  . binary, xor(#), and(@)
  우리말로 적기
  Binary의 마지막 한 자리만 봄

. Lambda calculus 풀기 2개
  . c h h 3 = c(h(h(3))) => (3+3)+(3+3)
  . 길지않았으나 헷갈림.

. Type inference tree 분석하기
  . type inference tree가 이미 주어져 있었음.
  . equation을 새우고 풀면 됨.

알면 다 풀고 모르면 못 푸는 그런 시험이었음.
lambda calculus 외에 머리 복잡한 계산, 정리 하나도 없었음.
실수를 안했으면 거의 85~95점 나오리라고 봄.

낙서

사람들이 요즘은 화장실 낙서를 덜하는 것 같다.
예전에는 화장실에 가면 유치한 낙서들이 있어서
일단 심심하지는 않았다.

물론 2~3번쯤 가면 모든 낙서를 읽어버려서 다시 지루해지기는 했지만
그럴 때는 이용하는 칸을 바꿔가면 그래도 지루함을 덜 수 있었다.
(화장실 낙서의 절정은 최불암 시리즈와 덩달이 시리즈)

세상이 발달해서 그런게 아닐까 싶다.
우리 학교 화장실도 항상 무슨 자보라든지, 책자가 붙어있어서
그것을 읽느라 심심함을 덜 수 있게 되어있으니까.

모 종교들의 책자라든지(가을의 개벽이나 그분이 오신다 등..),
마케팅, 경영 동아리의 자보,
총학생회와 반운동권, 운동권의 대립,
공연 동아리의 공연 소식 등..

그리고 이제는 벽 말고도 낙서할 공간이 너무 많아졌다.
화장실처럼 가끔 이용하고 적은 내용으로 낙서를 하는 것보다
인터넷에서 마음껏 하면 되니까.
시리즈로 적어가면서 놀 수도 있고
실시간으로 답변도 올라오고 여러명이서 싸울 수도 있다.
수천명이 수만개의 답글을 달며 성지 순례를 할 수도 있다.

로마 시대의 낙서문화가 민주주의 시스템으로 발전하고
결국 문서, 시보, 회의록, 추천서 같은 정형화되고 고도화된 형식이 된것처럼
우리의 화장실 낙서문화도 인터넷 댓글로 발전한 것 같다.

시험 당일

어제까지만 해도 시험 기간 같지 않더니,
당일이 된 긴장되면서 시험 같은 기분이 드는 구나.
(고등학교 때는 시험 1주일 전부터 이런 기분으로 살았는 데.)

한 과목 보고 오면 다른 과목들은 전투 모드로 변신해서
순식간에 지나갈 것 같다.

시험 기간 같은 기분은 뭐라고 표현해야 할까나.
스팀팩 맞은 marine이라든지, 아드레날린 저글링.

확실히 아드레날린 분비가 늘어난 기분이 든다.
심장도 빨리 뛴다. 반면에 어깨와 목, 손은 무거워진다.
샤프심이 계속 부러져 나가고 글씨체가 어지러워진다.

권투 시합처럼 종이 땡하고 치면~
그 때부터는 집중력도 올라가고 뭐든 해낼 수 있을 것처럼 변한다.
그리고 시험이 끝나면 까마득하게 모두 잊어버린다.
뭘 했는 지 하나도 기억나지 않는 다.

그래도 이번 시험 기간은 다른 시험기간들과는 달리
뭔가 새로운 아이디어가 떠오르거나 재미없던 모든 사소한 일들이
재미있어지거나 하지는 않는 구나.

별로 새롭지도 않는 데, 뭔가 영감이 떠오르는 것만 같고
성냥쌓기, 테트리스, 카드게임, 가위바위보마저 재미있어 지는 게
시험기간 아니던가.

[PL]중간고사 족보

. 2005년 중간고사 족보

3. 다음 용어를 설명하라.
1. Imperative programming language
  statement(instruction)들이 줄지어 있어서 어떤 일을 할 지 sequential하게 적는 다.
  assignment statement가 있다. (side-effect가 있다.)
  Von neumann architecture에서 기본적으로 나온다.

2. Binding and binding time
  binding : value와 identifier를 연결한다.

  binding time에는 static(early, compile time)과
  dynamic(late, virtual, run-time)이 있다.
  binding을 언제 결정할지 정하는 것.

3. Parse tree
  formal grammar에 따라 string을 sytatic structure를 가진 tree로 나타낸 것.
  parser에 의해 generate된다.

4. Derivation
  parse tree로 나타낼 수 있는 방법의 한 종류,
  left-derivation과 right-derivation이 있다.
  left-derivation에서는 항상 left child쪽으로 derivation을 하고
  right-derivation에서는 항상 right child쪽으로 derivation을 한다.

5. LR(k)
  LR parser : CFG의 bottom-up parser의 일종
  left에서 right로 읽어 right-derivation을 한다.
  k는 unconsumed look ahead input symbol의 갯수

6. ambiguity of grammars(ambiguous grammar)
  parse tree를 한 가지 이상의 방법으로 generate할 수 있을 때
  어떤 방식을 선택할 지 ambiguity가 발생한다.
  해결을 위해서는 grammar를 ambiguity없이 다시 쓰거나
  precedency나 associativity를 정해 준다.

7. dynamic scope
  runtime에 bing이 결정됨.
  함수 call 순서의 영향을 받음.
  perl, common lisp등에서 사용.

8. virtual machine
  http://en.wikipedia.org/wiki/Java_virtual_machine
  언어와 실제 machine의 중간 쯤 되는 가상적인 것.
  중간코드와 실제 machine사이에서 돈다.
  Portability 등을 위해 사용되기도 한다.
  Java virtual machine 같은 예가 있다.

9. Overloading
  함수나 operator의 argument(input, operand) type에 따라
  각자에 맞는 알고리즘(다른 알고리즘)을 적용하여 계산한다.
  같은 name을 가졌지만 type에 따라 다른 일을 한다.

10. aliasing
  memory 장소(값)을 하나 이상의 변수로 가리키는 것

11. value model of variabls
  http://en.wikipedia.org/wiki/Variable

12. referentially transparent (referential transparency)
  subexpression을 의미의 변화없이 value로 substitute할 수 있음.

13. polymorphism
  여러 type에 대해 동일한 algorithm을 적용해서 각 input type과 관련된 output을 줄 수 있음.

14. Short-circuiting
  필요하지 않은 것은 evaluation하지 않음.
  boolean or : e1이 true이면 e2는 eval하지 않고 true를 return함 e2가 undefined라도 상관없음.

15. side effect
  어떤 function이 return value외에 다른 값을 바꿀 때.
  assigment statement가 있으면 side effect가 발생한다.
  일반적으로 imperative programming language는 side effect가 있고
  functional language는 side effect를 최소화하려고 한다.
  Pure lisp의 경우 side effect가 없다.

16. tail recursion
  recursion을 iteration으로 쉽게 바꿀 수 있는 special case
  stack에 값을 누적하지 않으므로 spack space를 줄일 수 있다.

17. type system
  type check를 하는 system
  type간의 관계를 정의하고 각 변수, input, output type을 검사한다.
  type inference, casting, coercion을 할 수도 있다.

  http://en.wikipedia.org/wiki/Type_checking
  value와 variable을 type으로 classify한다.
  각 type들을 어떻게 manipulate하고 그들이 어떻게 interact하는 지 정의한다.

18. strong typing
  conservative하게 type을 check함(sound)
  이것을 통과한 것에 대해서는 항상 type-safe하다고 할 수 있다.
  영원이 돌거나 의도한 결과를 준다.

19. coercion vs casting
  http://en.wikipedia.org/wiki/Type_casting
  coercion : implicit type conversion
  compiler가 automatic하게 바꾼다.

  casting : expilcit type conversion
  checked : type을 바꾸기전에 가능한 것인지 확인한다.
  unchecked : check를 안한다.
  bit pattern : bit representation이 그냥 복사된다.

20. control flow statement 중 selection statement의 종류를 나열하라.
  . control flow statement
  http://en.wikipedia.org/wiki/Control_flow
  sequential order에 변화를 줄 수 있는 statement
  labels, goto, subroutines, if then else, loop, conditions, exception, nonlocal goto
  . selection statement
  if then, if then else, else if, switch-case, computed goto, arithmetic if,

21. subroutine closure
  http://en.wikipedia.org/wiki/Closure_%28computer_science%29
  . a subroutine bundled together with a referencing environment
  . a closure is a function that refers to free variables in its lexicla context.

22. applicative-order evaluation
  http://en.wikipedia.org/wiki/Applicative-order_evaluation
  evaluation strategy의 하나.
  function의 argument가 left to right 순의 post-order traversal로 reduce됨.
  function bod에서 가능한한 많은 evaluation을 reduce함.

23. Name equivalence of type checking
  name이 같을 때 같은 type으로 본다.
  C의 record, ada, modula-2

  structural equivalence : structure가 같으면 같은 type으로 본다.

24. derived type vs subtype in ADA

25. Module type

. 2004년 중간고사 족보
1. 다음 용어를 설명하라.
  1. type inference
    strongly statically typed programing lagnuages의 특성
    값에 type이 annotation되어 있지 않아도 자동으로 값의 type을 추론해냄.
    각 값의 관계에 따라 type에 관한 equation을 만드록
    그 equation을 풀면 된다.    

  2. coercion
  3. virtual machine  
    http://en.wikipedia.org/wiki/Virtual_machine
    User와 platform 환경 사이를 virtualize함.

  4. type compatibility by name
  5. overloaded operator (operator ad-hoc polymorphism)
    http://en.wikipedia.org/wiki/Operator_overloading
    operator의 argument의 type에 따라 다른 implementation을 사용하는 것

  6. dangling pointer
    http://en.wikipedia.org/wiki/Dangling_pointer
    적절한 type의 object를 가리키고 있지 못하는 pointer,
    잘못된 공간을 가리키고 있는 pointer
    unpredictable한 결과를 초래할 수 있다.

  7. axiomatic semantics
    수학 logic을 이용하여 computer program의 correctness을 prove하는 것

  8. interpreter
    http://en.wikipedia.org/wiki/Interpreter_%28computing%29
    a computer program that executes other programs.
    source code를 바로 실행시킴.
    반면에 compiler는 translate만 하고 execution은 안함.
    prototyping이나 test시에 간편하게 쓰임.

  9. aliasing
    하나의 값을 2개 이상의 변수가 가리키는 것.

  10. stack-dynamic array
     http://www2.hawaii.edu/~cheungca/ICS313/hw6/2031.txt
     Stack-dynamic array have dynamically bound subscript ranges and dynamic storage allocation at run time and have greater flexibility not requiring array size until used.
     Fixed heap-dynamic array have dynamically bound subscript ranges and dynamic storage allocation, but are static after storage allocation on a heap, rather than stack, and are bound when at user-program request.  Heap-dynamic array have dynamic binding of subscript ranges and storage allocation, can change, if flexible, and can adapt to the size required.

  11. orthogonality in programming language
     어떤 조합이든 valid하게 정의되어 사용될 수 있는 것,
     record의 array, int array, float array, array의 record 등이 모두 가능.
     primitive type과 combination, operator와 operand 등.

  12. enumeration type (enumerated type)
     http://en.wikipedia.org/wiki/Enumerated_type
     programmer가 a finite list로 data type의 value를 정의한 것.
     C언어에서는 enum으로 정의가능.

  13. reference count for memory management
     각 memory cell이 자신을 가리키고 있는 reference(pointer)의 갯수를
     가지고 있음. reference count가 0이 되면 garbage collect됨.

  14. grammar가 ambiguous하다.
     http://en.wikipedia.org/wiki/Ambiguous_grammar
     어떤 string이 여러가지 방법으로 parse tree가 생성될 수 있다.

2. subtype and derived type
  http://en.wikipedia.org/wiki/Subtype
  supertype에 관련되어 만들어진 type.
 
  derived type
  original type과 구조적으로 같지만 다른 type으로 정의된 것.
  의도적으로 두 개를 별개의 type으로 보기 위해 이름을 다르게 붙인 것.

  subtype과 derived type의 공통점 : 원래 type으로 부터 나온다.
  원래 type의 구조를 포함하고 있다.

  차이점 : derived type은 원래 type과 구조가 같지만
  subtype은 원래 type에 일부 구조를 더 할 수 있다.

3. 각 binding time에 일어나는 binding을 여러분이 아는 language에서 예를 하나씩 들어라.
  1. language design time

  2. language impelmentation time

  3. compile time by translator(compiler)

  4. runtime on entry of subprogram

  5. runtime at arbitrary point of execution

4. static array int A[LB1:UB1, LB2:UB2]가 있을 때
  어떤 array element A[i,j]를 access하는 공식을 i, j의 함수로 나타내라.
  필요한 상수는 정의하여 사용하고 그 값을 구하는 방법을 명기하라.
  (row-major로 나열하라.)

  row-major order
  http://en.wikipedia.org/wiki/Row_major

  NUMROWS = LB1 - UB1 + 1
  NUMCOLS = LB2 - UB2 + 1

  A[i, j]

  row-major일 때
  offset = (i - LB1) * NUMCOLS + (j - LB2)

  column-major일 때
  offset = (j - LB2) * NUMROWS + (i - LB1)

5. BNF로 정의된 grammar에 대하여 답하라.
  <S> -> a <S> a | b <S> b | c
  (1) parse tree 그리기

  (2) grammar로 정의된 L를 우리말로 쓰기

  (3)
  . denotational semantics
  M('c') = 0
  M(a <S> a) = 2 * M(<S>)
  M(b <S> b) = 2 * M(<S>) + 1

  'babcbad'의 의미는 무엇인가?
  2 * (2 * (2 * (0) + 1)) + 1 = 5
  0을 2배해서 1 더하고 그것을 2배하고 다시 2배해서 1을 더한다.
  => 5

  (4) <S> -> (a|b)<s>(a|b) | c
  이 grammar는 원래 grammar와 같은 가?
  다르다.
  'bca'라는 string의 경우 원래 grammar에서는 안되지만
  이 grammar에서는 된다.
  증명) 원래 grammar에서는 a,b가 항상 짝수개만 올 수 있다.

6.
  (1) union이란 무엇인가?
     http://en.wikipedia.org/wiki/Union_%28computer_science%29
     여러 종류의 type을 하나의 장소에 넣을 수 있다.
 

  (2) 다음과 같은 program segment가 있을 때, 이 언어는 왜 compile time에
     type compatibility를 check 할 수 있는 지/없는 지 이유를 말하라.

     union (real, int) chameleon;
     int intvar;
     real reavar;
     chameleon = intvar;
     ............
     realvar = chameleon;

     프로그램을 직접 수행하지 않고는 언제 chameleon이 int나 real로 되는 지
     예측할 수 없다.

  (3) 이러한 union type의 변수가 포함된 statement에서 type이 일치하는 지를
     runtime에는 check할 수 있게 하는 방안을 설명하라.
     union type의 변수에 tag를 달아서 현재 어떤 type의 값을 저장했는 지 기록한다.
     assign시마다 assign하는 값의 type을 적어둔다.

[PL]Ch.5 - The algol Family adn ML

. Algol 60
  . Basic language of 1960
  . Simple imperative language + functions
  . Successful syntax, BNF - used by many successors
     . statement oriented (statement by statement)
     . begin .. end blocks (like C { } )
     . if .. then .. else
  . recursive functions and stack storage allocation
  . fewer ad hoc restrictions than fortran
     . general array references : A[x+B[3]*y]
     . orthogonality : 간단한 몇 개의 primitive가 어디든 적용된다.
       . 어떤 type이든 array가 됨
       . 어떤 type이든 pointer가 됨
  . Type discipline was imporved by later languages. (type을 강요함)
  . Very influential but not widely used in US (유럽에서는 좀 씀.)
. Fortran은 IF(B) stmt, (else가 없다.)
  . IF (exp) 30, 40, 50 (arithmetic if, -,0,+에 따라 goto함)
. Fortran은 변수 선언 안해도 됨.
  => 변수명을 쓰다가 오타가 나면 새 변수가 생겨버림.(실수 확률이 높다.)

. Algol 60 Sample
  . no array bounds
  . end; 바로 앞 stmt에 semicolon이 없다.
  . return command가 없다. procedure명과 같은 변수명에 assign

. Algol Joke
  . Question
  . Is x:= x equivalent to doing nothing? (C와 다르다.)
  . equivalent가 아니고 recursive call일 수도 있다.
  integer procedure p;
  begin

  p := p
  앞의 p : return value p에 assign(l-value)
  뒤의 p : procedure p를 recursive call(r-value)
  end;

. Algol의 모든 variable의 reference는 자동으로 dereference된다.
  int ref ref x ; (= int **p)
  int y;
  y = x + 1;이라고 적으면 C의 y = **x + 1과 같다.
  automatic dereference를 한다.

. Some trouble spots in algol 60
  . Type discipline improved by later languages
  . parameter types can be array
     . no array bounds
  . parameter type can be procedure
     . no argument or return types for procedure parameter

     int procedure f(x, y, g)
         int x, y;
         procedure g;

     f : int * int * fun -> int
     g : don't care

  . Parameter passing methods
  . Pass-by-name had various anomalies
     . "Copy rule" based on substitution, interacts with side effects
  . Pass-by-value expensive for arrays(전부 copy한다.)
  . Some awkward control issues
  . goto out of block(non-local goto) requires memory management
  . non-local goto : exception handlgin에서 주로 사용한다.

. Algol 60 Pass-by-name
  . Substitute text of actual parameter
  . Unpredictable with side effects
  . Ex)
  procedure inc2(i, j);
     integer i, j;
     begin
       i := i+1;
       j := j+1
     end;
  inc2(k, A[k]);

  i=>k, j => A[k]로 치환

     begin
       k := k+1;
       A[k] := A[k]+1
     end;

  Is this what you expected?
  (따라서 원하지 않은 결과가 나타난다.)
  . 특징 - 별 짓을 다할 수 있다. (젠센's device)

. Algol 68
  . Considered difficult to understand
  . idiosyncratic(기이한, 색다른) terminology
     . types were called "modes"
     . arrays were called "multiple values"
  . vW grammars instead of BNF
     . context-sensitive grammar invented by A. van Wijngaarden
       http://en.wikipedia.org/wiki/Context-sensitive_grammar
       ex)
       S → abc | aSBc
       cB → Bc
       bB → bb

       a^n b^n c^n, a^n b^n c^n d^n 같은 것도 표현할 수 있다.
       (context-free grammar로 안되는 것)
       Noam-chomsky가 제안했다. CFG보다 표현력이 좋고 TM보다는 덜하다.
  . elaborate type system
  . complicated type conversions
  . Fixed some problems of algol 60
  . eliminated pass-by-name
  . Not widely adopted 

. Algol 68 Modes
  . Primitive modes
  . int, real, char, bool, string, compl(complex), bits, bytes, sema(semaphore), format(I/O),
     file
  . compound modes
  . arrays, structures, procedures, sets, pointers
  . Rich and structured type system is a major contibution of algol 68
  . Orthogonaloty : primitive mode와 compound mode의 모든 combination이 가능함.

. Other features of algol 68
  . Storage management
  . local storage on stack
  . Heap storage, explicit alloc and garbage collection(free는 알아서 함)
  . Parameter passing
  . pass-by-value
  . Use pointer types to obtain pass-by-reference
  . Assignable procedure variables
  . Follow "orthogonality" principle rigorously

. Pascal - Algol이 너무 복잡해서 type을 단순하게 만들고 교육하기 쉽게함.
  . http://en.wikipedia.org/wiki/Pascal_programming_language
  . Revised type system of algol
  . Good data-structuring concepts
     . records, variants, subranges
  . More restrictive than algol 60/68
     . procedure parameters cannot have procedure parameters
  . Popular teaching language(교육용)
  . Simple one-pass compiler
  . gcc는 매우 여러번 program을 본다.

. Limitations of pascal
  . Array bounds part of type
  procedure p(a:array[1..10] of integer)
  procedure p(n:integer, a:array[1..n] of integer) -> illegal, 제약이 너무 심하다.
  . int a[10], b[11] -> a와 b를 다른 type으로 간주함.
  . Attempt at orthogonal design backfires
  . parameter must be given a type
  . type cannot contain variables
  . How could this have happened? emphasis on teaching
  . Not successful for "industrial-strength" projects
  . Kernighan - Why Pascal is not my favorite language
  . Left nich for C; niche has expanded.
  . 하나의 파일에 program을 다 써야 한다.

. C programming language
  . Designed for writing unix by dennis ritchie
  . evloved from B, which was based on BCPL
  . B was an untyped language; C adds some checking
  . Relation between arrays and pointers
  . An array is treated as a pointer to first element
  . E1[E2] is equivalent to ptr dereference *((E1)+(E2))
  . pointer arithmetic is not common in other languages.
     (이해가 어렵다. ex - p = p+ 1 , p는 pointer, p의 size에 따라 +의 의미가 다르다.)
  . Ritchie quote "C is quirky, flawed, and a tremendous success."
  (나쁘고 변덕스러운 언어)
  . DEC의 PDP machine의 OS를 다시 만듬 : Unix
  . Unix를 위해 만든 언어 : C
  . C는 assembly도 끼워 넣을 수 있다.

. ML
  . Typed programming laguage
  . Intended for interactive use
  . Combination of Lisp and Algol-like features
  . Expression-oriented
  . Higher-order functions
  . Garbage collection
  . Abstrac data types
  . Module system
  . Exceptions(exception handler)
  . General purpose non-C-like, not OO language
  . Related languages : haskell, OCAML

. Why study ML?
  . Learn an important language that's different
  . Discuss general programing laguages issues
  . types and type checking
     . general issues in static/dynamci typing
     . type inference
     . polymorphism and generic porgramming
  . Memory management
     . static scope and block structure
     . function activation records, higher-order functions
  . Contrl
     . Froce and delay
     . Exceptions
     . Tail recursion and continuations
  . 교과서 저자가 ML을 좋아함.

. History of ML = Meta language
  . http://en.wikipedia.org/wiki/ML_programming_language
  . Robin Milner
  . Logic for Computable functions
  . Meta langage of the LCF system(목적)
  . Theorem proving
  . Type system
  . Higher-order functions
  . LCF : Logic for Computable Function
  http://en.wikipedia.org/wiki/LCF_theorem_prover

. Logic for computable functions
  . Dana scoot, 1969 - recursive call의 converge를 증명(?)
  . Formulate logic for proving properties of typed functional programs
  . Milner
  . Project to automate logic
  . Notation for programs
  . Notation for assertions and proofs
  . Need to write programs that find proofs
     . Too much work to construct full formal proof by hand
  . Make sure proofs are correct

. LCF proof search
  . Tactic : function that tries to find proof
  tactic(formula) =
  1. succeed and return proof
  2. search forever(solution space가 infinite하게 크기 때문)
  3. fail

. Express tactics in the Meta-language(ML)
. use type system to facilitate correctness
  (type이 매우 유용하더라.)

. logic에서 중요한 것.
  . 어떤 formula가 이미 주어진 axiom과 theorem으로부터 항상 true임을 증명하는 것.
  . proof를 automatic하게 해보자.

. Tactics in ML type system
  . Tactic has a functional type
  . tactic : formula -> proof
  . type system mush allow "failure"
  . Tactic : function that tries to find proof
  tactic(formula) =
  1. succeed and return proof
  2. search forever(solution space가 infinite하게 크기 때문)
  3. fail and raise exception(!!)
 
. type system이 logic formula에 매우 편하다.

. Higher-order functions
  . Tactic is a function
  . Method for combining tactics is a function on functions

. Basic overview of ML
  . Interactive compiler : read-eval-print
  . Compiler infers type before compiling or executing
  . type system does not allow casts or other loopholes.

. Compound types
  . Tuples - Heterogeneous fixed size
  . (4, 5, "Hi") : int * int * string
  . Lists - Homogeneous, not fixed size
  . nil
  . 1::[2,3,4]
  . Record
  . {name = "Fido", hungry=true}
     : {name : string, hungry : bool}

. Patterns and declarations
  . patterns can be used in place of variables
  <pat> ::= <var> | <tuple> | <cons> | <record>
  . value declarations
  . general form
    val <pat> = ,exp>

. Functions and pattern matching
  . Anonymous function
  fn x => x+1; Like lisp lambda

. list reverse
  . stack에 넣고 다시 꺼내면 된다.

. variable and assignment
  . General terminology : l-values and r-values
  . assignment
  . identifier on left refers to a memory location, called l-value
  . identifier on right refers to contents, called r-value
  . variables
  . Most languages
     . A variable names a stroage location
     . Contents of location can be rea, can be changed
  . ML reference cell
     . A mutable cell is another type of value
     . Explicit operations to read contents or change contents
     . seperates naming(declaration of identifiers) from variables

  . ML imperative constructs
  . ML reference cells
     . Different types for location and contents
       x : int , non-assignable integer value
       y : int ref, location whose contents must be integer
       !y , the contents of location y
       ref x , expression creating new cell initialized to x
  . ML assignment
     . operator := applied to memory cell and new contents
  . ex)
     y := x+3, place value of x + 3 in celly; requires x:int
     y := !y + 3, add 3 to contents of y and store in location y
  . 모든 variable은 initialize 되어야 한다.

. Core ML
  . Patterns
  . Declarations
  . Functions
  . Polymorphism
  . Overloading
  . Type declarations
  . Exceptions
  . Reference cells

[PL]Ch.6 - Types

. General discussion of types
  . What is a type?
  . compile-time vs run-time checking
  . conservative program analysis
  (조금만 이상하면 그냥 틀렸다고 한다.)
  compile time에 모든 것을 알 수는 없다.
  (halting problem과 동치?)

. Type inference
  . Good example of static analysis algorithm
  . Will study algorithm and examples

. Polymorphism
  . Polymorphism vs overloading
  . Uniform vs non-uniform impl of polymorphism

. Type
  . Semantic analysis에서 가장 먼저하는 것
  . 최근 PL의 가장 큰 break through
  . A type is a collection of computable values that share some structural property.
  . well-define되는 것만 type이고 well defined 안되면 type이 아니다.
  . type : well define된 value의 set과 그것들에 가능한 operation을 모은 것.
  . 어떤 언어든 manual 처음은 각 언어의 primitive type을 설명함.
  (그만큼 type이 중요하다는 뜻.)

. Uses for types (type check)
  . Program organization and documentation
  . seperate types for separate concepts
     . represent concepts from problem domain
  . Indicate intended use of declared identifiers
     . Types can be checked, unlike program comments

  . Identify and prevent errors
  . Compile-time or run-time checking can prevent
     meaningless computations such as 3 + true

  . support optimization
  . ex : short integers require fewer bits
  . access record component by known offset
  . type이 틀렸다면 아마 error일 것이다.
  . type이 정해지면 field(layout)이 정해져서 structure에서 offset을 정할 수 있다.
  . bit-pattern(binary representation)이 type이 있어야 의미가 결정된다.
      
. Type erros
  . Hardware error
  . Fuction call x() where x is not a function
     (x가 적절한 address가 아니고 엉뚱한 instruction이다.)
  . May cause jump to instruction that does not contain a legal op code

  . Unintended semantics
  . int_add(3, 4.5) - 다른 representation을 연산하면 당연히 이상한 값이 나온다.
  . Not a hardware error, since bit pattern of float 4.5
     can be interpreted as an integer
  . Just as much a program erros as x() above

. General definition of type error
  . A type error occurs when execution of program
  is not faithful(충실하지 않음) to the intended(의도한) semantics
  . Do you like this definition?
  . Store 4.5 in memory as a floating-point number
     location contains a particular bit pattern
  . to interpret bit pattern, we need to know the type
  . If we pass bit pattern to integer addition function,
     the pattern will be interpreted as an integer pattern
  . type error if the pattern was intended to represent 4.5

. Type system : type check를 하는 systme
. Type system을 통과했다. = type error가 없다.
  = 우리가 원하는 semantic대로 움직인다.
  물론 logic이 틀렸으면 다른 값이 나올 것이다.

. Compile-time(static check)
. run-time checkcing(dynamic check)

. Lisp uses run-time type checking
  . (car x) make sure x is list before taking car of x

. ML uses compile-time type checking
  . f(x) must have f:A->B and x:A

. Basic tradeoff
  . Both prevent type errors
  . Runtime checking slows down execution
  . Compile-time checking restricts program flexibility
  . Lisp list : elements can have different types
  . ML list : all elements must have same type
  . variable이 runtime에 type이 바귈까? 언어에 따라 다르다.

. Expressiveness(표현력)
  . In Lisp, ew can write function like
  (lambda(x) (cond ((less x 10) x) (T (car x))))
  => x가 10보다 크거나 같으면 9car 10)이 안되므로 type error
  . some uses will produce type error, some will not
  . dynamic하면 run-time check이면 expressiveness는 커지지만
  어떻게 될지 모른다.

. Static typing always conservative(soundness)
  . Cannot decide at compile time if run-time error will occur
  (halting problem의 undecidability와 관련있다.)
  . sound < A < completeness < U
  . A : 우리가 check하는 성질
  . sound and complete = A

. type check를 통과한 program
  1. 내가 원하는 결과가 나오거나(옳은 결과)
  2. 영원히 끝나지 않음.

. soundness : yes라고 말하면 반드시 yes
. completeness : yes인 것은 항상 yes라고 대답, no인 것도 가끔 yes로 대답할 수 있음.

. relative type-safety of languages
  (type-safe language = sound = strongly typed)
  . Not safe : BCPL family, including C and C++
  . BCPL : 거의 type이 없다.
  . Cast, pointer arithmetic(가장 악명높다.)
  . Almost safe : Algol family, pascal, Ada.
  . Dangling pointers (allocate는 문제 없으나 free가 문제)
     . Allocate a pointer p to an interger, deallocate the memory
       referenced by p, then later use the value pointed to by p
     . No language with explicit deallocation of memory is fully type-safe
  . Safe : Lisp, ML, Samlltalk, and Java
  . Lisp, Smalltalk : dynamiclly typed(run-time)
  . ML, Java : statically typed(compile-time)
  . ML, Java는 pointer가 없고 reference만 있다.

. Type checking and type inference
  . Standard type checking
  . Look at body of each function and use declared types of identifies to check aggrement.
  . Type inference
  . Type을 안 적어도 알아냄.
  . Look at code without type information and figure out what types could have been declared.
  . ML is designed to make type inference tractable.

. Motivation
  . Types and type checking
  . Type systems have improved steadily since algol 60
  . Important for modularity, compilation, reliability
  . Type inference
  . Cool algorithm
  . widely regarded as important language innovation
  . ML type inference gives you some idea of how many
     other static analysis algorithms work

. Application
  f(x)
  @(f(x)) : r  (parent)
  f : s (left-child)
  x : t (right-child)

  s = t -> r

  t : domain
  r : range(codomain)

. Abstraction
  lx.e

  l : s->t (parent)
  x : s (left-child)
  e : t (right-child)
 
. Types with type variables
  . Assign tpes to leaves
  . Propagate to internal nods and generate constraints
  (위로 propagete한다.)
  . solve by substitution

. Use of Polymorphic function
  . argument type에 따라 return type이 결정됨, 여러 종류를 넣을 수 있다.
  . most general form - 더 general하게 적을 수 없다.
  ex)
  (int -> t) -> t : general form: 가장 simple하고 모든 것을 나타냄.
  : (int -> int) -> int
  : (int -> (s->t->r)) -> (s->t->r)

. Main points about type inference
  . Compute type of expression
  . Does not require type declarations for variables
  . Find most general type by solving constraints
  . leads to polymorphism
  . Static type chcking without type specifications
  . May lead to better error detection than ordinary type checking
  . Type may indicate a programming error even if there is no type error

. ML에서는 type inference가 잘 되게 type system이 define되있다.
  (C는 그렇지 않다.)

. Polymorphism vs overloading
  . Parametric polymorphism(같은 algorithm)
  . single algorithm may be given may types
  . Type variable may be replaced by any type
  . Overloading (다른 algorithm)
  . A single symbol may refer to more than one algorithm
  . Each algorithm may have different type
  . Choice of algorithm determined by type context
  . Types of symbol may be arbitrarily different

. Parametric Polymorphism : ML vs C++
  . ML polymorphic function (implicit polymorphism)
  . Declaration has no type information
  . Type inference : type xpression with variables
  . Type inference : substitute for variables as needed
  . C++ function template(explicit polymorphism)
  . Declaration gives type of function arg, result(type parameter의 name을 줌)
  . Place inside template to define type variables
  . Function application : type checker does instantiation

. ML also has module system with explicit type parameters

. Example : swap two values(polymorphism)
  . ML : 모든 변수는 pointer임. (function이 1 copy면 됨.)
  . swap is compiled into one function
  . typechecker determines how function can be used

  . C++ : stack에 들어가는 변수가 있기 때문에 swap function의 size가 달라짐.
  . 그래서 type에 따라 function이 여러 copy가 필요함.
  . swap is compiled into linkable format
  . linker duplicates code for each type of use

  . Why the difference
  . ML ref cell is passed by reference(pointer), but
     local x is on stack, size depends on type

. Another example
  . C++ polymorphic sort function
  . What parts of implementation depend on type?
  . Indexing into array(type의 size가 다름)
  . Meaning and implementation of <
  . Swap

. ML Overloading
  . Some predefined operators are overloaded
  . User-defined functions must have unique type
  (User defined는 polymorphic일 수는 있으나, overloading은 안됨)
  . Why is a unique type needed?
  . Need to compile code => need to know which +
  . Efficiency of type inference
  . Aside : general overloading is NP-complete

. Summary
  . Types are important in modern languages
  . Program organization and documentation
  . Prevent program errors
  . Provide important information to compiler
  . Type inference
  . Determine best type for an expression, based on
     known information about symbols in the expression
  . Polymorphism
  . Single algorithm (function) can have many types
  . Overloading
  . Smbol with multiple meanings, resolved at compile time

. type
  . a collection of computational entities that share some common property
  . naming and organizing concepts
  . making sure that bit sequences in computer memory are interpreted consistently.
  . providing information to the compiler about data manipulated by the program

. type inference하는 법
  . 일단 lambda calculus로 바꾼다.

  . lambda lx.y
  l이 parent가 됨 : s
  left child는 bound variable(x) : t - node를 그리는 것이 아니라 leaf node와 잇는 다.
  right child는 function body(y) : u
  s = t -> u

  . function : f(x) =>  f = x -> f(x)  => lx.(f x)
  @이 parent가 됨 f(x) : s
  left child는 f : t
  right child는 x : u
  t = u -> s

  . + : int -> int -> int

  . recursive function의 경우 argument가 여러번 쓰이는 경우 lambda에서 여러개 잇고 각 node들을 같은 type variable로 적는 다.

[소설]토마스 하디 - 아내를 위하여

. 토마스 하디
  1840년 영국의 건축가, 소설가.
  테스, 귀향, 아내를 위하여 등의 소설을 씀.
  문학은 독학으로 공부함.
  영국 남서부 웨섹스 지방을 배경으로 함..
  공동체의 붕괴, 계급간의 갈등, 종교적 회의 등.
  사회 계량주의자
  기독교 신앙에 회의를 느낌.
  개인의 의지와 선택의 폭이 그리 크지 않고 환경이 주인공을 지배함.
  내재적 의지 - 우주의 맹목적 의지

. 배경 : 바닷가 마을

. 등장인물
  쉐이드릭 - 주인공, 작은 배의 선장, 종교적이고 고지식함.
  에밀리 - 첫번째 여자친구, 내성적, 부자 상인과 결혼
  조안나 - 두번째 여자친구(아내), 질투심이 강함, 쉐이드릭과 결혼

. 내용
  두 여자와 갈등하다가 결국 조안나와 결혼함.
  조안나의 집은 점점 가난해지고, 에밀리는 점점 부자가 됨.
  쉐이드릭은 장사에 전혀 소질이 없었고 뱃일 밖에 몰랐음.
  조안나는 에밀리의 집안을 엄청나게 질투하게 되고 돈에 대한 욕심이 매우 커짐.
  결국 조안나와 쉐이드릭은 위험하지만 두 아들과 전재산을 걸고
  다시 바다로 나가게 됨.
  결국 조안나는 늙고 병들어 버리고 에밀리의 집에서 얹혀 살게 됨.
  쉐이드릭과 그 아들들은 영영 돌아오지 않음.

  조안나의 야심은 쉐이드릭의 성격과 어울리지 않음.
  조안나는 자신과 사실 관련이 없는 에밀리를 질투하여 평생 고통을 겪게 됨.
  조안나는 과거만 생각하면서 현실을 받아들이지 못함. 비극적 결말

[PL]Ch.4 - Fundamentals

. Syntax and semantics of programs
  . syntax : the symbols used to write a program
  . semantics : the actions that occur when a program is executed
  . programming language implementation
  . syntax -> semantics
  . tranform program syntax into machine instructions
     that can be executed to cause the correct sequence
     of actions to occur

. Interpreter vs Compiler
  . Interpreter : 느리다. 컴파일이 따로 필요없어서 간편하다.
  source 코드를 바로 읽는 다.
  . Compiler : 여러 translation을 해서 복잡하지만 빠르다.
  target program으로 먼저 번역한다.

. Typical compiler
  1. source program

  2. lexical analyzer(lexer, scanner)
    http://en.wikipedia.org/wiki/Lexical_analyzer
    Regular expression, finite automata, lex
    keyword, variable 등을 나눔(lexical token을 구함)
    쓸데 없는 blank도 제거

  3. syntax analyzer(parsing, parser)
    http://en.wikipedia.org/wiki/Syntax_analysis
    http://en.wikipedia.org/wiki/Yacc
    Context free grammar, BNF, yacc(yet another compiler compiler)
    parse tree를 만듬.
    terminal node를 모으면 program이 된다.
    nonterminal node도 이ㅆ음.

  4. semantic analyzer - PL에서 다룸
    Abstract syntax tree(AST) : parse tree에서 중요한 것만 남김
    augmented parse tree : type와 declare된 장소에 관한 정보를 더함.(annotation)
    type system
    Annotation : symbol table을 이용해서 각 variable이 어디에 쓰이는 지 type등을 적음.

  5. intermediate code generator - OS, architecture에서 다룸
    function_start(), computer_expr(), assing() ...
    AST를 tree traverse하여 depth first search하면 intermediate code가 된다.
    Virtual Machine, 3-address instructions

  6. code optimizer - OS, architecture에서 다룸
    Common subexpression elimination : 한번만 계산하고 저장해뒀다가 사용
    copy propagation : 같은 value 한번만 assign
    dead-code elimination : 실행 안되는 코드 제거
    loop optimizations : loop 밖으로 최대한 꺼냄
    function in-lining : 함수 호출을 줄임, 프로그램 크기가 증가함.

  7. code generator
    Machine architecture
    Register allocation
    Optimization
    reuse registers efficiently

  8. target program - machine code

. Brief look at syntax
  . Grammar
  e ::= n | e+e | e-e
  n ::= d | nd
  d ::= 0|1|2|3|4|5|6|7|8|9
  . expressions in language
  e -> e-e -> e-e+e -> n-n+n -> nd-d+d -> dd-d+d -> .. -> 27-4+3

. Derivation represented by tree
  Tree shows parenthesization of expression

. Parsing
  . Given expression find tree
  . Ambiquity
  . Expression 27-4+3 can be parsed two ways
  . Problem : 27-(4+3) != (27-4)+3
  . Ways to resolve ambiquity
  . Precedence(다른 operator일때) - high or low
     . Group * befor +
     . Parse 3*4+2 as (3*4)+2
  . associativity(equal precedence일때) - left or right
     . parenthesize operators of equal precedence to left(or right)
     . (3-4)+5 : left-associative
     . 3-(4+5) : right-associative

. Theoretical foundatinos
  . many foundational system
  . computability theory
  . Program logics
  . Lambda calculus
  . denotational semantics : PL의 semantics
  . operational semantics : PL의 manual 같은 것
  . Tyep theory

  . consider these methods
  . Lambda calculus(syntax, operational semantics)
  . computability theory
  . denotational semantics

. lambda calculus
  . 가장 primitive하지만 모든 것이 표현가능, theoretical한 증명이 쉽다.
  . formal system with three parts
  . Notation for function expressions
  . proff system for qeuations
  . calculation rules called reduction
  . additional topics in lambda calculus
  . mathematical semantics
  . type systems

. history
  . original intention
  . formal theory of substitution
  . more successful for computablel functions
  . substitution -> sybolic computation
  . church/turing thesis
  . influenced design of Lisp, ML, other languages
  . See boost lambda library for C++ function objects
     http://www.boost.org/libs/lambda/index.html
  . important part of CS history and foundations

. Why study this now?
  . Basic syntactic notions
  . Free variables : global variable
  . Bound variable : function argument
  . functions
  . declarations - 선언과 정의

  . Calculation rule(매우 간단하다) - 단 1개의 symbolic substitution
  . Symbolic evaluation useful for discussing programs
  . Used in optimization (in-lining), macro expansion
     . correct macro processing requires variable renaming
       (Name conflict control)
  . Illustrates some ideas about scope of binding
     . Lisp originally departed from standard lambda calculus,
       returned to the fold through Scheme, Common Lisp

. Lambda expression
  . Symbolic computation, pattern matching을 잘해서 reduction

. BNF
  . M :: = x (variables)
     | M1 M2 (application), M1: function, M2: function의 actual parameter
     | lx.M (abstraction), M:function body, x : M의 formal parameter
ex)
lx.x = identity function의 abstraction form
lx.(f (g x))
(lx.x)5
lx.x y == lx.(x y) : 최대한 길게 뒤로 가서 parsing
application, abstration 모두 되므로 ambiguous grammar

. ambiguous grammar
  . if there si some string that it can generate in more than one way.
  . http://en.wikipedia.org/wiki/Ambiguous_grammar
  ex) CFG, A->A+A|A-A|a, is ambiquous.

. expression
  x + y

. functions
  lx.(x+y)

. application
  (lx.(x+y))3 = 3+y

. Higher-order functions
  . Given function f, return funcition f.f
  . lf. lx.f(f x)
  . How does this work?
     (lf. lx. f(f x))(ly.y+1)
    => lx.(ly.y+1)((ly.y+1) x)
    => lx.(ly.y+1)(x+1)
    => lx.x+1+1

. Free and Bound Variables
  . Bound variable is "placeholder" - 따라서 항상 rename 가능
  . Variable x is bound in lx.(x+y)
  . function lx.(x+y) is same function as lz.(z+y)
  . Name of free(=unbound) variable does matter
  . variable y is free in lx.(x+y)
  . function lx.(x+y) is not same function as lx.(x+z)
  . Occurrence
  . y is freee and bound in lx((ly.y+2) x) + y
  . scope
  . bound variable : 이름 바꾸기 가능(local이므로)
  . free variable : 이름 바꾸기 불가능(global이므로)
  . lambda calulus는 static scope이다.

. alpha-reduction : varialbe rename

. beta-reduction : substitution
  . (lx.e1)e2 -> [e2/x]e1
  . e1의 free variable x를 e2로 clghks
  . where substitution involves renaming as needed
  (name conflict를 피하려면 renmaing해야 한다.)

. reduction
  . apply basic computation rule to any subexpression
  . repeat

. confluence : 맘대로 evaluation해도 결과는 같다.
  . final result (if there is one) is uniquely determined
. Redex : reducable expression

. Substitution
  . [N/x]x = N
  . [N/x]y = y where y is different from x
  . [N/x](M1 M2) = ([N/x]M1 [N/y]M2)
  . [N/x](lx.M) = lx.M (헷갈리는 부분, 두 x의 scope가 다르다.)
  . [N/x](ly.M) = ly.([N/x]M) where y is not free in N
  (free y를 bound y로 만들면 안된다.)
  ex.1)
  (lx.(ly.(x+y+1))(y+1)
  => (lx.(lz.(x+z+1))(y+1) (rename을 먼저해야 한다.)
  => lz.(y+1+z+1)
  != ly.(y+1+y+1) (free y를 bound y로 만들면 안된다.)

  ex.2)
  (lx.(lx.x+1))5
  => [5/x](lx.(x+1))
  => lx.(x+1)
  혹은
  => (lx.(ly.y+1))5
  => ly.y+1
  != 5+1

  . FV(x) = {x}
  . FV(M N) = FV(M) U FV(N)
  . FV(lx.M) = FV(M) - x

. function with several arguments(argument가 여러개 일때)
  . curried form
  . http://en.wikipedia.org/wiki/Currying
  . ex) f(g,x) = g(x)
  . f curry = lg.lx.g x
  . f curry g x = g x = g(x) = f(g,x)
  . pair notation = curried form
     . f=l(g,x).g x

. Recursion and fixed Point
  . factorial function
  function f(n) { if n = 0 then 1 else n*f(n-1)};
  -> 이것은 f의 definition이 아니라 equation이다.
  . Equation with recursive definition
  f(n) = if n = 0 then 1 else n * f(n-1)
  . Get the solution f with above equation, Let
  G = lf.ln.if n=0 then 1 else n*f(n-1)
  . f is the fixed point of function G, ex f = G(f)

. Fiexed point operator = Y-combinator, domain theory로 증명가능
  . http://en.wikipedia.org/wiki/Fixed_point_operator
  . fixed point combinator allow the definition of anonymous recursive functions
  . a fixed point operator Y
  Y = lf.(lx.f(x x))(lx.f(x x))
  . Show that Yf = f(Yf)
  Yf = (lf.(lx.f(x x))(lx.f(x x)))f
  => (lx.f(x x))(lx.f(x x))
  => f((lx.f(x x)) (lx.f(x x)))
  => f(Yf)

. original motivation for topic
  . denotational semantics를 배우는 이유
  . Precision
  . Use mathematics instead of english
  . avoid details of specific machines
  . Aim to capture "pure meaning" apart from implementation details
  . Basis for program analysis
  . Justify program proof methods
     . soundness of type system, control flow analysis
  . Proof of compiler correctness
  . Language comparisons

. Why study this?
  . Look at programs in a different way
  . Program analysis
  . Initialize befor use
  . Introduce historical debate: functional vs imperative programming
  . program expressiveness : what does this mean?
  . theory vs practice : we don't have a doog theoretical understanding of programming language "usefulness"

. Basic Principle of denotational semantics
  . compositionality
  . The meaning of a compound program must be defined from the meanings of its parts (not the syntax of its parts)
  . Exmaples
     . P; Q
       composition of two functions, state -> state
     . letrec f(x) = e1 in e2
       meaning of e2 where f denotes function

. Trivial example : binary numbers
  . syntax
  b ::= 0|1
  n ::= b|nb (binary number)
  e ::= n|e+e (e: starting symbol)

  . semantics value fuction E : exp -> numbers
  E[[0]] = 0
  E[[1]] = 1
  E[[nb]] = 2*E[[n]] + E[[b]]
  E[[e1+e2]] = E[[e1]] + E[[e2]]

  E : syntatic element를 mathematical(semantic) entity로 mapping
  무한한 mapping을 유한하게 describe해보자.(structural induction)

. Second ex : expressions
 
  . syntax
  b ::= 0|1|...|9
  n ::= b|nb (decimal number)
  e ::= s|n|e+e (e: starting symbol)

  . semantics
  value E : exp -> numbers
  state s : vars -> numbers

  E[[x]]s = s(x) : variable namve -> value
  E[[0]]s = 0
  E[[1]]s = 1
  E[[nb]]s = 2*E[[n]]s + E[[b]]s
  E[[e1+e2]]s = E[[e1]]s + E[[e2]]s

  E[[x]]s -> E[[x,s]] : argument가 2개로 늘어난 셈

  . x : variable - 어떤 state function s가 name x를 받으면 value를 return
  E[[x+z]]는 syntactic element뿐만 아니라 state에 따라 의미가 달라진다.
  S0 = {x->4, y->7, z->8}
  E[[x+4+y]]S0
  = E[[e1+e2]]S0
  = E[[e1]]S0 + E[[e2]]S0
  = E[[e3+e4]]S0 + E[[e2]]S0
  = E[[e3]]S0 + E[[e4]]S0 + E[[e2]]S0
  = E[[x]]S0 + E[[4]]S0 + E[[y]]S0
  = 4 + 7 + 4

. Semantics of imperative programs
  . Syntax
  . P ::= x:=3 | if B then P else P | P; P | while B do P
  . Semantics
  . C : Programs -> (State -> State)
  . State = Variables -> Values
     would be locations -> values if we wanted to model aliasing
. C: P의 semantic function
. Program : Initial state -> final state
. C[[P]]S0 = S1

. Semantics of Assignment
  . C[[x:=e]]
  is a function states -> states
  . C[[x:=e]]s = s'
  where s':variables->values is identical to s except
  s'(x) = E[[e]]s gives the value of e in state s

. Semantics of Conditional
  C[[if B then P else Q]]
  C[[if B then P else Q]]s
  = C[[P]]s if E[[B]]s is true
  = C[[Q]]s if E[[B]]s is false

. Semantics of iteration
  C[[while B do P]]
  is a function states -> states

  C[[while B do P]] = the function f such that
  f(s) = s if E[[B]] is false
  f(s) = f(C[[P]](s)) if E[[B]] is true

  f is recursively defined(사실 define이 아니라 equation)

  C[[P1;P2]]S0 = C[[P2]](C[[P1]]S0)
  C[[P1]]S0 = S1
  C[[P2]]S1 = S2

. Perspective
  . Denotational semantics
  . Assign mathematical meanings to programs in a
     structured, principled way
  . Imperative programs define mathematical functions
  . Can write semantics using lambda calculus, extended with operators like
     modify:(state x var x value) -> state
  . Impact
  . Influential theory
  . Application via
     abstraction interpretation, type theory
  C[[x:=e]]S0 = S1
  modify(S0, x, e) = S1

. What is a functional language?
  . No side effects = pure(LISP)
  . OK, we have side effects, but we also have higher-order functions

. No-side-effects language test
  = Referential transparency
  . within the scope of specific declarations of x1, x2, ..., xn
  all occurrences of an expression e containing only
  variables x1, x2, ..., xn must have the same value.
 
. Example languages
  . Pure Lisp
  atom, eq, car, cdr, cons, lambda, define
  . Impure Lisp: rplaca, rplacd
  . Common procedural languages are not functional
  . Pascal, C, Ada, C++, Java, Modula

. Backus' Turing Award
  . John Backus was designer of Fortran, BNF, etc.
  . Turing Award in 1977
  . Turing Award Lecture
  . functional prog better than imperative programming
  . Easier to reason about functional programs
  . More efficient due to parallelism
  . Algebraic laws
     . reason about programs
     . Optimizing compilers(translate가 쉽다.)

. Reasoning about programs
  . To prove a program correct
  . Must consider everything a program depends on
  . In functional programs
  . dependence on any data structure is explicit
  . therefore
  . easier to reason about function programs
  . Do you believe this?
  . This thesis must be tested in practice
  . Many who prove properties of programs believe this
  . Not many people really prove their code correct

. Haskell Quicksort
  . Very succinct program(5줄 밖에 안된다.)
  . This is the whole thing
  . No assignment - just write expression for sorted list
  . No array indices, no pointers, no memory management

. Compare : C quicksort 14줄

. Interesting case study
  . Abstraction이 잘 될수록 high-level이고 사람을 efficient하게 만든다.
  . Haskell이 가장 짧고 C++이 가장 길다.
  . Relational Lisp이 가장 시간이 적게 걸렸다.

. Disadvantages of functional prog
  . Assign이 없으므로 copy를 너무 자주한다.

. Von Neumann bottleneck = stored program
  . Von numann - data의 절반이 instruction
  . Mathematician responsible for idea of stored program
  . Von numann Bottleneck
  . Backus' term for limitation in CPU-memory transfer
  . Related to sequentiality of imperative langauges

. Eliminating VN bottleneck
  . No side effects
  . Evaluate subexpressions independently => parallel하게 계산가능
  . Does this work in practice? good idea but
  . Too much parallelism
  . Little help in allocation of processors to processes
  . Scheduling overhead가 크다.
  . communication overhead가 크다.
  . David shaw promised to build the non-Von
  . Effective, easy concurrency is a hard problem

. Functional vs Imperative programs
  . Denotational semantics shows
  . Every imperative program can be written as a
     functional program, using a data structure to
     represent machine states
  . This is a theoretical result
  . I guess "theoretical" means "it's really true"
  . What are the practical implications?
  . Can we use functional programming languages for practical application?
     compilers, graphical user interfaces, network routers.
     => I/O, meta circular evaluation이 중요

. Summary
  . parsing
  The real program is the disambiquated parse tree
  . lambda calculus
  Notation for functions free and bound variables
  Calculate using substitution, rename to avoid capture
  . Pure functional program
  May be easier to reason about
  Parallelism : eay to find, too much of a good thing
  . computability
  Halting problem makes some error reporting, optimization impossible

. Formal languages
  . language - a set of strings
  L = {if, while, for, then, else ...}
  . string - a finite sequence of symbols from some alphabet
  . alphabet - a finite set of symbols
  {a,b,c, ..., z}, {0, 1, ... , 9}
  . A generator generates members of the set
  . A recognizer recognizes members of the set

. Regular expressions
  . symbols, empty string, alternation, concatenation, repetition

. Context-free Grammars
  . S : statement
  . E : expression
  . Language : 우리가 작성한 모든 program의 set
  . S -> S;S
  . S -> id:=E
  . E -> num
  . E -> E + E
  . terminals - tokens :  최종적으로 program에 나오는 것
  . Nonterminal - symbols used in grammar (S, E)
  . Start symbol - a nonterminal
  . Derivation - generating phrases of language by replacing
  nonterminals with r.h.s of productions
  . 무한개를 생성할 수 있는 이유 : S와 E가 자기자신으로 정의된다.
  . Nested structures require recursion

. BNF(Backus Naur Form)
  . 1958년 algol의 syntax define시 사용
  . CFG define productions
  . Each production consists of a
  . left-hand side non-terminal, and a
  . right-hand side sequence of terminals and non-terminals
  . A grammar also defines a non-terminal start symbol

. BNF ex
  . Notation typically used for defining languages
  <statement> ::= <statement> ; <statement>
  <statement> ::= <identifier> := <expression>
  <expression> ::= <number>
  <expression> ::= <expression> + <expression>

  <statement>, <expression>, <identifier>, <number> : non-terminal(<   >로 기술)
  ;, :=, + : terminal

. Extended BNF
  . optioanl syntax : [] : 0 or 1번
  . Repeated syntax : {} : RE의 *와 비슷

. syntax diagrams

. Derivations
  . Begin with start symbol, replace any nonterminal with the rhs of some production for that nonterminal
  . leftmost - pcik leftmost nonterninal to expand
  . rightmost - pcik rightmost nonterninal to expand
  . ex) leftmost
  S -> id:= E
  -> id:= E + E
  -> id:= E + E + E
  -> id:= num + E + E
  -> id:= num + num + E
  -> id:= num + num + num

. Derivation algorithm
  1. Begin with the start symbol nonterminal
  2. Replace the non-terminal with the right-hand side of a matching production
  3. Choose a non-terminal from the resulting sequence
  4. repeat steps 2 and 3 until no non-terminals remain

. This algorithm includes two choices
  step2. choice of matching production
  step3. choice of non-terminal

. Parse tree
  . a tree representaion of a derivation
  . connect a symbol to the one from which it was derived
  . leaf node = treminal
  . left most derivation이면 left child들이 더 풍성하다.

. Ambiquity - syntax에는 문제가 없으나 semantics(evaluation)에서는 문제가 있다.
  . a grammar is ambiguous if a phase has two different derivations.
  . equivalently, two parse trees
  . example (rightmost derivation)

. Problems with ambiquity(= grammar의  므ㅠㅑ벼ㅑ쇼)
  . If the shape of the parse tree conveys meaning, then ambiquity in a language's grammar(syntax) translates into ambiquity in the language's meaning (semantics)
  . Problematic grammar
  <statement> :: <condition> | <assignment> | begin { <statement> } end

  해결책
  1. grammar를 다시 쓴다.(Unambiquous grammars) (C언어의 방법 - 가까운 곳에 match)
  2. endif를 도입
  3. then다음에 if가 올 수 없고 반드시 begin-end가 와야 한다.

. Denotational semantics
  http://en.wikipedia.org/wiki/Denotational_semantics
  formalizeing the semantics of system by constructing mathematical objects with express the semantics of these systems.

. Axiomatic semantics
  http://en.wikipedia.org/wiki/Axiomatic_semantics
  mathematical logic에 따라 program의 correctness를 따짐.

. Operational semantics
  http://en.wikipedia.org/wiki/Operational_semantics
  give meaning to computer programs in a mathematically rigorous ywa

. semantics of initialize-before-use

. single assignment
  . can bind a value to a name at most once.
  . oftern function languages.
  . Erlang, Haskell, SISAL

bidet(비데)

CT 대학원이 생긴지 얼마 안되서 interior가 화려한 편이다.
원래 산디과에 있던 학제전공이라서 더 그런것 같다.
아무튼 화장실도 꽤 깔끔하고 신기한 편인데,
들어가보니 비데가 있었다.
(돈많은 전자과, 일부 화장실에만 있다는 그 물건;)

heating기능이 있어서 의자도 따뜻하게 데우고 있었다.
그냥 버튼만 이리저리 눌러봤는 데, 반응이 없었다.

센서가 있어서 사람이 앉아있지 않으면 동작이 되지 않는 모양이다.
그래서 센서를 손으로 가리고 버튼을 눌렀더니,
숨겨져있는 분수꼭지가 나와서는 폭포수처럼 물을 뿌리고는 사라졌다.
(그럴 줄 알고 옆으로 피해 있었다.;)

드라이 기능, 온도 조절기능, 물 세기 조절 기능 등 많은 기능이 있더군.
다음번에는 진짜로 써봐야지..

----------------------------
비데는 원래 중세 시대(십자군 시대)에 피임용, 의료용 등으로 고안되었다고 한다.
좌욕기와 거의 비슷했나보다.

[Math]Gradient, curl, divergence

. dot product(inner product)
  . http://en.wikipedia.org/wiki/Dot_product
  . (vector * vector) -> scalar
  . lengths and angles (projection)
  . a.b = |a||b|cos(theta)

. cross product(outer product)
  . vector * vector -> vector
  . area of parallelogram, perpendicular
  . a x b = n|a||b|sin(theta)

. Scalar triple product
  . http://en.wikipedia.org/wiki/Triple_product
  . V = |a.(bxc)|

. Vector triple product
  . ax(bxc)

. del
  . differential operator del
  . nabla(역삼각형 모양)
   http://en.wikipedia.org/wiki/Nabla_symbol

. flux
  . http://en.wikipedia.org/wiki/Flux
  . the magnitude of a river's current
  . the amount of water that flows through a cross-section of the river each second

. Gradient
  . http://en.wikipedia.org/wiki/Gradient
  . Measure of the slope(steepness, fall, incline) of a straight line
  . Whose magnitude is the greatest rate of change
  . the direction of the greatest rate of increase of the scalar field
  . f(x) : scalar function (vector -> scalar)
  . x : vector variable
  . grad(f) = (af/ax1, ... af/axn) : (vector -> scalar) -> vector
  . a : partial derivatives
  . invariant under orthogonal transformations

. Divergence
  . F = (F1, F2, .. Fn)
  . div F : (aF1/ax1 + aF2/ax2 + .. + aFn/xn) : vector -> scalar
  . div = nabla inner-product
  . linear operator
  . vector field's tendency to originate from or converge upon a give point
  . flux density
  . derivative of the net flow of the vector field
  . div F(x0, y0) > 0 : source, expand
  . div F(x0, y0) < 0 : sink, shrink

. Curl
  . http://en.wikipedia.org/wiki/Curl
  . vector operator
  . F : vector
  . curl(F) : vector -> vector
  . curl = nable cross-product
  . vector fields's rate of rotation
  . the direction of the axis of rotation
  . the magnitude of the rotation
  . circulation density

[PL]Ch.3 - LISP

. LISP - 1960년대 John MCcathy가 개발
  . elegant하고 minimalist language, mathematically well-defined
  . Not C, C++, Java : a chance to think differently
  . AI, symbolic programming (예 - 미적분)
  . prefix format - easy to parse -> program 자체가 data로 사용가능
  -> LISP program을 짜는 LISP program
  . illustrate general themes in language design
  . Stems from interest in symbolic computation(math, logic)
  . dynamically scoped languae

. Many different dialects
  . Lisp, CommonLisp, Scheme, Lisp 1.5

. John McCarthy
  . Pioneer in AI
  . Formalize common-sense reasoning
  . Proposed timesharing
  . Mathematical theory

. S-expression = symbolic expression
. Both code and data in LISP
. Semi-structured data in human-readable textual form
ex) 3, 4, (3. 4), ((x. 3), (3. 5)), nil, (3 . nil), . (2. (3. nil))
. S-expression 중 list는 .을 생략가능
http://en.wikipedia.org/wiki/S-expression
ex) (+ . (1 . (2 . (3 . nil)))) = (+ 1 2 3)
. interactive optlevel
. interactive computer programming environment
. (cons 3 4) => (3 . 4)
. (cons (+ 4 7) (* 4 7)) => (11 . 28)
. (quote A) - A를 eval하지 말고 A라고 찍어라
. (quote (+ 1 2)) => (+ 1 2) - 계산 끝 (더 이상 eval 안함)
. (car '(3 . 4)) => 3
. (car (cons 3  4) => 3
. (cdr '(3 . 4)) => 4
. (cdr (cons 3  4) => 4
. (car (3 4)) => error : 3이라는 operator를 eval할 수 없음.
. (car 3 4) => error : car는 operand를 1개만 받음.

. Atoms include numbers, indivisible "strings"
<atom> ::= <smbl> | <number>
<smbl> ::= <char> | <smbl><char> | <smbl><digit>
<num> ::= <digit> | <num><digit>

. dotted pairs
  . LISP의 basic data structure
  . Write (A.B) for pair
  . Symbolic expressions, called S-expressions
  <sexp> ::= <atom> | (<sexp> . <sexp>)
. Note on syntax
  . Book uses some kind of pidgin(혼성어) Lisp
  . Will provide executable alternative, so examples run in scheme
  . In scheme, a pair prints as (A. B) but (A.B) is not an expression

. Basic functions
  . Functions on atoms and pairs
  cons, car, cdr, eq, atom
  . Declarations and control
  . cond, lambda, define, eval, quote
 
  . Example
  (lambda (x) (cond ((atom x) x) (T (cons 'A x))))
  function f(x) = if atom(x) then x else cons("A", x)
  . functions with side-effects
  rplaca, rplacd

. special form
  . cond, lambda, define, quote
  . 모든 expression part를 evalution하는 것이 아니므로 special form이라고 부름.

. pure LISP : side effects가 없음.
. impure LISP : side effects가 있음.

. Side-effect
  . http://en.wikipedia.org/wiki/Side_effect_%28computer_science%29
  . 어떤 함수가 return value가 아닌 다른 어떤 state를 바꿀 때.
  . global, static variable, arguments 등을 바군다.
  . Imperative program은 side-effect를 가진다.
  . Function programing은 side-effect를 최소화 하려고 한다.
  . referentially opague = Not referentially transparent
  . purely functional programming에서 없음.

. Referential transparency
  . http://en.wikipedia.org/wiki/Referential_transparency
  . 어떤 subexpression을 value로 meaning의 change없이 바꿀 수 있을 때
  . purely functional programming에서 가능

. read-eval-print loop(REPL)
  http://en.wikipedia.org/wiki/Read_Eval_Print_Loop
. Function call (function arg1 ... argn)
  . evaluate each of the arguments
  . pass list of argument values to function
. special forms do not eval all arguments
  . example (cond (p1 e1) ... (pn en))
  . cond에서는 lazy evaluation을 함
  . proceed from left to right
  . find the first pi with value true, eval this ei
  . example (quote A) does not evaluate A

. McCarthy's 1960 Paper
  . Interesting paer with
  . good language ideas, succinct(간결한, 간명한) presentation
  . Some feel for historical context
  . Insight into language design process
  . Important concepts
  . Interest in symbolic computation influenced design
  . Use of simple machine model
  . Attention to theoretical considerations
     Recursive functino theory, lambda calculus
  . Various good ideas : Programs as data, grabage collection

. Motivation for Lisp
  . Advice Taker
  . Process sentences as input, perform logical reasoning
  . Symbolic integration, differentiation
  . Expression for function -> expression for integral
     (Integral '(lambda (x) (times 3 (squeares x))))
  . Motivating application part of good lang design
  . Keep focus on most important goals
  . Eliminate appealing but inessential ideas
     . Lisp : symbolic computation, logic, expreimental prog.
     . C : Unix operating system
     . Simula : simulation(descrete simulation, C++과 비슷)
     . PL/1 : "Kitchen sink", not successful in long run
       . fortran + cobol을 하려고 함, 복잡해서 실패.

. Program Execution Model(abstract Machine)
  . Language semantics must be defined
  . Too concrete(hardware에 너무 가까움)
     . Programs not portable, tied to specific architecture
     . Prohibit optimization (ex - C eval order undefined in expn)
  . Too abstract
     . cannot easily estimate running time, space
       (User와 구현자의 입장차가 커짐)
  . LISP : IBM 704, but only certain ideas
  . Address, decrement registers -> cells with two parts(car, cdr)
  . Garbage collection provides abstract view of memory
  . LISP의 기본 memory model : cell(pair)
  . Evaluation order를 specify하면 optimization이 안된다.
  . car : contents of address register
  . cdr : contents of data register

. Abstract Machine
  . Concept of abstract machine
  . Idealized computer, executes programs directly
     (무한 용량, 무한 정확도)
  . Capture programmer's mental image of execution
  . Not too concrete, not too abstract
  . Example
  . Fortran
     . Flat register machine; memory arranged as linear array
       -> Von neumann architecture를 그대로 반영
     . No stack, no recursion
  . Algol family
     . Stack machine, contour model of scope
     . heap storage(memory allocation, C++의 new, delete)
     . Stack이 기본 memory structure
  . Smalltalk
     . Objects, communicating by messages.   
  . 심볼릭스 - Lisp 전용 machine
  . association list(A-list, run-time stack)
  . 현재 expression이나 다음에 사용될 변수의 값을 저장.

. Theoretical considerations
  . McCarthy's description
  . Scheme for representing the partial recursive functinos of a certain class of symbolic expressions
  . Lisp uses
  . Concept of computable(partial recursive) functions
     . Want to express all computable functions
  . Function expressions
     . Known from lambda calculus(eveloped A. Church)
     . lambda calculus equivalent to Turing Machines, but provide useful syntax and computation rules.

. Innovations in the design of Lisp
  . Expression-oriented
  . function expressions
     (lambda calculus를 기반으로 하고 있어 수학적이다.)
  . conditional expressions
  . Recursive functions - loop대신 사용
  . Abstract view of memory
  . Cells instead of array of numbered locations
  . Garbage collection
  . Programs as data
  . higher-order function : function을 parameter로 받고 return value로 넘김.
  . first-order function : argument와 function이 아닌 것.
  . second-order function : argument로 first-order function을 받는 것
  . third-order function : argument로 first-order function을 받는 것

. Algol : function이 nested define 가능하다.
. C의 scope : local or global, 2종류 밖에 없다.

. Parts of speech
  . statement - load 4094 r1
  . Imperative command
  . Alters the contents of previously-accessible memory
  . Expression - (x+5)/2
  . Syntactic entity that is evaluated
  . Has a value, need not change accessible memory
  . If it does, has a side effect
  . Declareation - integer x
  . Introduces new identifier - identifier의 atribute를 정의
  . May bind value to identifier, specify type

. expression과 statement의 차이점
  statement는 state를 바꾸지만 expression은 memory state를 바꾸지 않을 수도 있다.
  LISP은 statement based가 아니라 expression based이다.

. function expressions
  . Form
  . (lambda (parameters) (function_body))
  . Syntax comes from lambda calculus : lambda calculus에는 function이름이 없다.
  lf.lx.f (f x)
  (lambda (f) (lambda(x) (f (f x))))
  . Defines a function but does not give it a name t
  ((lambda (f) (lambda 9x) (f (f x))) (lambda(x) (+ 1 x)) )

  . (define twice (lambda (f) (lambda (x) (f (f x)))))
  . (define inc (lambda (x) (+ 1 x)))
  . ((twice inc) 2)

. Conditional expressions in Lisp
  . sequential conditional expression
  . Generalized if-them-else (lazy evaluation)
  . (cond (p1 e1) (p2 e2) ... (pn en))
  . evaluate conditions p1 ... pn left to right
  . if pi is first condition true, then evaluate ei
  . value of ei is value of expression
  No value for the expression if no pi true, or
     p1 ... pi false and pi+1 has no value, or
     relevant pi true and ei has no value
  . conditional statements in assembler
  . Conditional expression apparently new in Lisp
  . P1~Pn이 모두 true가 아닐 때
     . Scheme : null을 return
     . 아무것도 return 안하기도 함.

. strict ness
  . An operator or expression form is strict if it can have a value only if all operands or subexpression have a value
  . 모든 argument를 계산 후에 operator를 적용
  . Lisp cond is not strict, but addition is strict
  . (cond (true 1) (diverse 0))
  . (+ e1 e2)

. Lisp memory Model
  . Cons cells
  . Atoms and lists represented by cells

. Sharing
  . Both structures could be printed as ((A.B).(A.B))
  . Which is result of evaluating?
  . 단지 print만 해서는 internal representation을 알 수 없다. (구별안됨)
  . Imperative feature가 없으면 구별이 안된다. (replaca, replacd)

. Garbage collection
  . Garbage
  . At a given point in the execution of a program P
     a memory location m is garbage if no continued execution of P
     from this point can access location m.
  . 가만 놔둬도 되지만 memory가 부족할 때 machine이 run time에 함.
     programmer는 언제 수행될지 모름,
     execution time을 추정할 수 없음. - realtime에서 매우 중요
  . free list ( = free storage list)
  . the list of available memory location
  . Garbage collection
  . Detect garbage during program execution
  . GC invoked when more memory is needed
  . Decision made by run-time system, not program
  . This is can be very convenient. ex) in building text-formatting programming, ~40% of programmer time on memory management.
  . C에서는 string을 위해 매우 오랜시간을 쓴다.
  . Memory leak, dangling modifier

. Ex)
  car (cons (e1) (e2)))
: cells created in evaluation of e2 may be garbage, unless shared by e1 or other parts of program

. Mark-and-sweep algorithm
  . Assume tag bits associated with data
  . Need list of heap locations named by program
  . Algorithm
  . Set all tag bits to 0
  . Start from each location used directly in the program
     follow all links, changing tag ibt to 1
  . Place all cells with tag = 0 on free list

. Why garbage collection in Lisp?
  . McCarthy's paper says this is
  more convenient for the programmer than a system in which he has to keep track of and erase unwanted lists.
  . Does this reasoning apply equally well to C?
  (C에서는 왜 안했을 까?)
  . Is garbage collection "more appropriate" for Lisp than C? Why?
  (시험에 냄, 책 찾아보기, P.38)
  . LISP은 garbage가 필연적으로 생기지만
     C의 경우 간단한 프로그램의 경우 user-allocated memory를 안 써서, garbage가 안 생길 수도 있다.

. Programs as data
  . Programs and data have same representation
  . Eval function used to evaluate contents of list
  . substitute x for y in z and evaluate
  (define substitute (lambda (x y z)
     (cond ((null z) z)
           ((atom z) (cond ((eq z y) x) (true z)))
           (true (cons (substitute x y (car z))
                       (substitute x y (cdr z)))))))
  (define substitute-and-eval
     (lambda (x y z) (eval (substitute x y z))))
  (substitute-and-eval '3 'x '(+ x 1))

. Recursive functions
  . Want expression for function f such that
  (f x) = (cond ((eq x 0) 0) (true (+ x (f (- x 1)))))
  . Try
  (lambda (x) cond ((eq x 0) 0) (true (+ x (f (- x 1)))))
  . mcCarthy's 1960 solution was operator "label"
  (label f -> f가 recursive function임을 알려줌 (recfun 등도 씀)
     (lambda (x) cond ((eq x 0) 0) (true (+ x (f (- x 1))))))

. Recursive vs non-recursive declarations
  . Recursive definition
  (lambda (x) cond ((eq x 0) 0) (true (+ x (f (- x 1)))))
  . Legal scheme : treats inner f as function being defined
. Non-recursive definition
  . (define x (+ x 2))
  . Error if x not previously defined
  while evaluating arguments to + in expression (+ x 2)
  Unbound variable: x
  ABORT: (misc-error)
. Theory와 implementation입장에서 복잡함.(recursion 때문에)

. Higher-order functions
  . Function that either
  . takes a functino as an argument
  . returns a function as a result
  . Example: function composition f(g(x))
  . (define compose (lambda (f g) (lambda (x) (f (g x)))))
  . example : maplist -> 모든 원소에 function을 apply
  . (define maplist (lambda (f x)
        (cond ((null x) nil)
              (true (cons (f (car x)) (maplist f (cdr x)))))))

. Example
  . (define inc(lambda(x) (+ x 1))
     (maplist inc '(1 2 3))
     => (2 3 4 . nil) = (2 3 4)

. scheme preamble
  . (define true #t)
  . (define false #f)
  . (define eq eq?)
  . (define null null?)

. Efficiency and side-effects
. expression을 eval하면 value가 달라진다.
. Pure Lisp : no side effect
  . 대신 efficiency가 떨어짐, data copy를 너무 자주함.
. Additional operations added for "efficiency"
  (rplaca x y) replace car of cell x with y
  (rplacd x y) replace cdr of cell x with y
. What does "efficiency" mean here?
  . Is (rplaca x y) faster than (cons y (cdr x)) ?
  . Is faster always better? - 좋을 때도 있고 아닐 때도 있다. (yes or no)

. scheme preamble
  . (define rplaca set-car!)
  . (define rplaca set-cdr!)

. Summary : contributions of LISP
  . Successful language
  . Symbolic computation, experimental programming
  . Specific language ideas
  . Expression-oriented : functions and recursion
  . Lists as basic data structures
  . Programs as data, with universal function eval
  . Stack implementation of recursion via "public pushdown list"
  . Idea of garbage collection

. Exploratory programming
  . experimental evalutino에 따라 system이 radicall하게 바뀌는 것.

. Turing complete
  . Turing equivalent
  . Computationally universal
  . http://en.wikipedia.org/wiki/Turing_complete
  . Universal turing machine과 computational power가 같다.

. static scoping ( = lexical scoping)
  . http://en.wikipedia.org/wiki/Static_scoping
  . A variable always refers to its nearest enclosing binding.
  . ML, Haskell, scheme
  . unrelated to the runtime call stack
  . compile time에 binding 된다.
  int x = 0;
  int f () { return x; }
  int g () { int x = 1; return f(); }
  g()는 0을 retrun 함

. dynamic scoping
  . each identifier has a global stack of bindings
  . compile type이 아닌 runtime에 binding stack을 해야 한다.
  . Dangerous하므로 현대적 언어들은 쓰지 않는 다.
  . Perl, Common Lisp
  . run time에 binding 된다.
  int x = 0;
  int f () { return x; }
  int g () { int x = 1; return f(); }
  g()는 1을 retrun 함

. formal parameter
  . a placeholder in the funcion definition

. actual parameter
  . formal parameter에 값이 apply되었을 때.

. anonymous function
  . lambda를 이용하여 declared name이 없는 함수를 만들 수 있다.

. short-circuting
  . 필요하지 않ㅎ는 것은 evaluate하지 않음.
  . Scor(e1, e2), boolean or : e1이 true이면 바로 true를 return함, e2가 undefined라도 상관없음.
  . Por(e1, e2), parallel or : e1, e2가 side effect가 없고 둘 중 하나가 undefined라도 다른 하나가 ture이면 true를 return함.

. reference counting
  . a simple garbage-collection scheme
  . 각 메모리 공간이 자신을 가리키는 reference count를 가지고 있음.
  . impure Lisp에서는 cycle이 가능하기 때문에 그 경우 reference counting은
  실패하게 된다.