간서치의 IT세상

2019년 4월 26일 금요일

[리뷰][scheme] Programming and Meta-Programming in Scheme 을 읽고

https://www.amazon.com/Programming-Meta-Programming-Undergraduate-Computer-Science/dp/1461272432
이 책은 얼떨결에 읽게 되었다.

Scheme 관련 책을 골라보려고 샘플을 받았는데 페이지를 넘기다가 얼떨결에 구매해 버린것이다!
게다가 만원 2만원도 아닌 60달러 이상이 되는 책이었다.
Scheme에 대해 꽤나 자세하게 되어있고, SICP에서 설명하는 강의의 내용과 꽤나 비슷한 내용들이 많았다.

SICP를 읽기 위한 전과정이라 생각해도 될 것 같다는 생각을 했다.
일단 Scheme책이기 때문에 Scheme에 대한 깊은 내용이 나올 때도 있다. 관심이 없지만 아마 다른 Lisp들도 비슷한 컨셉으로 만들어져있지 않을까 하는 마음이 들어서 계속 읽었다.

매크로에 대한 내용은 생각보다 많이 나오진 않았다.
오히려 개발에 대한 일반철학을 설명할 때가 좋았다. 아마 그런 걸 더 느끼고 싶어서 SICP를 읽어보려는 걸지도 모르겠다.

아쉬운 점은 해당 사이트를 찾아보려고 했는데 잘 작동하는 것 같지 않았다.
http://www.cs.sjsu.edu/faculty/pearce/scheme/index.html

읽으면서 가장 기억에 남는 것은 heap을 구현해보는 것이었다.
아직도 좀 난해한데 나중에 시간 나면 그 부분만 다시 따라쳐보면서 이해해볼까 한다.

글로는 대충 느낌이 오는데 소스코드가 난해하다.
그래서 타입체크 하는 부분을 좀 줄이고 한가지 타입만 저장가능하도록 줄여서 구조를 이해해볼까 한다.

다음은 How to Design Program을 도서관에서 빌려 볼까 한다.

2019년 4월 18일 목요일

[SICP][scheme][javascript] 아무것도 없는 것에서 무언가를 추상화할 수 있을까?

출처 : https://youtu.be/ymsbTVLbyN4

SICP의 강의는 손이 잘 가지 않는 영상이다.
난 항상 SICP를 읽어보려고 하지만 일주일이 지나면 역시나 다른책을 꺼내 읽고 있다. 이 못난 학생은 그럼에도 황새를 쫓아가보겠다고 공부를 하다. 그러다 나는 아래의 코드를 보게 되었다.

(define (cons a b)
  (lambda (pick)
    (cond ((= pick 1) a)
          ((= pick 2) b))))

(define (car x) (x 1))
(define (cdr x) (x 2))

;; 설명을 위해 더해진 것.
(define A (cons 1 2))
(print (car A))
(print (cdr A))

이 비디오를 보는 사람들 중 몇몇은 이미 이 내용을 설명할 때, 경악을 금치 못했다.
이 코드가 대체 무엇이길래 그러는가. 난 이 코드에서 모든 추상화가 시작되진 않았을까 상상해본다.
데이터 추상화란 무엇인가.

1. "부를 수 있게 된다"는 것이다. (그것은 이름업슨 데이터에 이름을 부여함으로써 시작된다. 하여 머릿속으로도 다룰 수 있게 된다.) 2. 그것은 마치 마술사가 주문에 이름을 부여하는 것처럼 마법과 같다.
3. 우리는 이 개념의 정확한 정의를 나중에 내릴 수 있게 된다. (일단 이름을 부름으로써 나중에 해당 개념에 대한 정의가 바뀌면 그 정의만 바꾸면 되는 것이다.)
4. (추가적인 특징) 우리는 이 추상화된 데이터를 강제할 수 있다.

rational number

이 책에서 설명하는 rational number에 대해 알아보자.
우리는 일단 데이터를 추상화 해야 한다.
분자 n, 분모 d가 있다.
이것들을 make-rat에 넣어서 하나의 패키지를 생성하는 것이다.

(make-rat n d) ; rational-number (n,d의 저장형태는 알 필요없음)
(numer rational-number) ; numerator 분자
(denom rational-number) ; denominator 분모

여기서 make-rat는 constructor, numer/denom은 selector라고 불린다.
하나의 데이터는 이렇게 constructor와 selector로 추상화될 수 있다.

이렇게 유리수를 make-rat, numer, denom으로 추상화 하였다.
한번 더하기를 해보자.

(define (+rat x y)
  (make-rat
    (+ (* (numer x) (denom y))
       (* (numer y) (denom x)))
    (* (denom x) (denom y))))

여기서 x,y는 rational-number이다. 우리는 x,y가 어떻게 구현되어 있는지는 모르지만, make-rat으로 유리수를 만들 수 있고, numer/denom으로 꺼낼 수 있는 것은 알고 있다.
곱하기도 만들자.

(define (*rat x y)
  (make-rat)
  (* (number x) (number y))
  (* (denom x) (denom y)))

자 이제 유리수를 구현해보자. 어떻게 담아야 할까?

(define (make-rat n d) (cons n d))
(define (numer x ) (car x))
(define (denom x) (cdr x))

이렇게 cons를 이용하여 pair(리스트)를 만든다.
그러니 rational-number란 무엇인가?
이것은 사실 pair일 뿐이다. 첫번째와 두번째라는 박스가 있는 자료구조일 뿐이다.
그렇다면 pair라는 것은 무엇인가? 이것도 또한 두개의 값이 쌍으로 있는 추상적인 개념이다.
쌍의 개념은 cons라는 constructor와 car, cdr이라는 selector로 표현할 수 있다.
여기서 car는 첫번째 값을 말하며, cdr는 두번째 값을 지칭한다.

아무것도 없는 곳에서 추상화하기

그렇다면 pair라는 추상적인 개념은 무엇을 기반으로 만들어진 개념일까?(무엇 위에서 쌓여 올라왔는가)
여기서 저자는 아무것도 없는 곳에서 생성된다고 한다.

(define (cons a b)
  (lambda (pick)
    (cond ((= pick 1) a)
          ((= pick 2) b))))

(define (car x) (x 1))
(define (cdr x) (x 2))

여기에 데이터가 보이는가? 어떤 자료구조가 보이는가?
쌩뚱맞게 lambda가 보인다. cons는 일단 procedure를 다시 리턴한다.
그리고 pick이라는 변수를 받는데 그것이 1이면 a를 리턴하고, 2이면 b를 리턴하는 함수를 리턴한다.

car를 보자. (x 1)라는 함수가 있는데, 여기서 1이 매개변수 pick에 매핑될 것이다. 첫번째 값(즉 a)이 리턴
cdr에서는 (x 2)로써, pick=2가 되고 두번째 값(b)가 리턴된다.

대체 어디에 a,b는 어떤 자료구조로 저장되는 건가? 아무것도 아닌 것에 저장되는 느낌이다.
closure를 이해한다고 생각했는데 이 코드를 보자마자 '이해한다는 것이 무엇인지조차 모르고 있었구나' 라는 생각이 들었다.

공부를 하면 할 수록, 항상 겸손해야 한다는 생각을 할 수 밖에 없다.
겸손하지 않으면, 배울 수가 없으니...

강의 교수님이 한 말씀을 여기 기록하지 않을 수가 없다.

So in some sense, we don't need data at all to build these data abstractions.
We can do everything in terms of procedures.

procedures are not just the act of doing something.
procedures are conceptual entities, objects.

강의가 끝나고 한 지적인 학생이 엄청난 질문은 하는데 그것은 바로
(cons 1 2)의 값과 1초 후 동일한 프로시저호출인(cons 1 2)는 동일한 녀석인가? 이다.

이 말은 (+ 2 2)와 4는 동일한 녀석인가?

를 고민하는 문장인데, 한시간의 수업에서 대체 이런 질문이 어떻게 나올 수 있었을까? 라는 생각이 든다.
이 질문에 대해 교수님은 당장은 대답할 수 없지만, 곧 하게 될 것이라는 말을 하며 끝낸다.

언제 저 답을 알 수 있을까? 빨리 다음을 알고 싶다.

여담으로 아래 scheme코드를 js로 변경해보자.

function cons (a , b) {
  return function(pick) {
    switch(pick) {
    case 1 : 
      return a;
    case 2 :
      return b;
    default:
      return;
    }
  }
}

function car(x) { return x(1); }
function cdr(x) { return x(2); }

var procedure = cons(10,20);

car(procedure);
cdr(procedure);

2019년 3월 20일 수요일

[리뷰][Coursera] 코세라의 [Concurrent Programming in Java] 수강을 마치며

Coursera에서 수강할 수 있는 Concurrent Programming의 수강을 마쳤다.

이번에는 lock와 readwritelock에 대해 배웠으며, Actor의 개념도 살짝 나왔다.

실제로 Actor를 제대로 구현해서 사용하는 것은 아니지만 개념정도 알고 어떻게 사용되는
지만 알아도 Actor가 좀 더 친근해진 느낌이다.

조금 어려운 내용이 나오기도 했지만 프로젝트 자체는 어렵지 않고, 친절하게 프로젝트 자체를 설명해주기 때문에, 잘 넘길 수 있었다. 내 생각에 이 코스에서 중요한 부분은 프로젝트 어사인먼트가 아니라 QUIZ인 것 같다.

개념을 잘 이해해야 하는 경우가 있으며, 내가 어떤 부분을 헷갈려 하는지 알 수 있기 때문에 같은 부분을 계속 듣고 확인하게 만들어 준다.

괜찮은 강의였으나, 좀 더 설명이 길었으면 하는 아쉬움이 있다.

2019년 3월 5일 화요일

[javascript] 그래서 커리를 어떻게 쓰려고?

내가 처음 커리를 써야겠다고 생각했던 것은 로직이 계속 겹치고 있었기 때문이다.

예를들어보자. 인풋별로 유효성을 체크하는데 유효성을 체크할 때마다 하는일이 조금씩 다르다.

// 핸드폰 인풋 묶음 3개 유효성검사
var phone_1 = trim($("#phone_1").val());
var phone_2 = trim($("#phone_2").val());
var phone_3 = trim($("#phone_3").val());

if (phone_1 < 3 && phone_1 ...) { // 여러 and문과 유효성검사
  $("#phone_1").focus();
  alert("휴대폰 유효성검사실패");
  return;
}
... phone_2, phone_3

$("#hidden_phone_").val(phone_1 + "-" phone_2 + "-" + phone_3);

이런 코드가 있다. 익숙하다. 일단 커리를 쓰기 전에 여기서 if문에 있는 모든 유효성검사는 하나의 함수로 추상화 해놓자.

if (validate(phone_1) { // 여러 and문과 유효성검사
  $("#phone_1").focus();
  alert("휴대폰 유효성검사실패");
  return;
}
if (validate(phone_2) {
  $("#phone_2").focus();
  alert("휴대폰 유효성검사실패");
  return;
}
if (validate(phone_3) {
  $("#phone_3").focus();
  alert("휴대폰 유효성검사실패");
  return;
}

이런 코드를 본 적 없는가? 여기서 분명 우리는 뭔가 더 할 수 있을 것 같다. 어떻게 해야 할까? 맞다 객체를 넘기는 것이다.

function validateAndFocus(phone, $phone) {
  if (!validatePhone(phone) {
    alert("휴대폰 유효성검사 실패");  
    $phone.focus();
    return false;
  }
  return true;
}

이제 이걸 사용해보자

if(!validateAndFocus(phone_1, $("#phone_1")) {
  return;
}
if(!validateAndFocus(phone_2, $("#phone_2")) {
  return;
}
if(!validateAndFocus(phone_3, $("#phone_3")) {
  return;
}
...

뭔가 여기도 겹치는 것 같다.

if (!(validateAndFocus(phone_1, $("#phone_1")) &&
      validateAndFocus(phone_2, $("#phone_2")) &&
      validateAndFocus(phone_3, $("#phone_3"))) {
  return;
}

undersocre.js의 and가 있다면 더 좋을 것 같다. 끝이 없을 것 같으니 여기서 넘어가자. underscore를 쓸 수 없어서 curry만 임시 사용하는 것이다. 이정도만 깔끔해보인다. 그런데 여기 주민번호와 카드번드까지 추가되었다.

var card1 = $("#card1");
var card2 = $("#card2");
var card3 = $("#card3");
var card4 = $("#card4");

var national_id_1 = $("#national_id");
var national_id_2 = $("#national_id");

우리는 validateAndFocus를 사용할 수 있는가? 사용할 수 없다. 1. 휴대폰번호의 유효성과 아이디의 유효성은 다르다. (predicate의 분리 필요) 2. 유효성 검사 이후 하는 일이 각각 다를 것이다. 하지만 형태는 동일하다. 1. 주어진 값의 유효성을 검사한다. 2. 통과하면 true 실패하면 false를 리턴한다. 3. 유효성검사에 실패하여 false를 리턴하기 전에 각각 해야하는 일이 있다.

// 동일한 형태의 일을 하는 함수 템플릿 정의
function validateTemplate(pred, func, obj1, obj2, obj3) {
  if (pred(obj1, obj2, obj3)) {
    func(obj1, obj2, obj3);
    return false;
  }
  return true;
}

자 이 형태를 만들었다. 이제 어떻게 사용할지 보자. 유효성 검사를 분리해서 넣을 것이다. 그렇다면 이렇게 될 것이다.

var curried = curry(validateTemplate);
var validatePhoneCurried = curried(function(n) {
  return validatePhone(n);
});
var validateCardCurried = curreid(function(n) {
  return validatePhone(n);
});
var validateNationalidCurreid = curried(function(n) {
  return validateNationalid(n);
});

뭐 대충 이렇게 코딩했다. 현재까지는 pred를 커리하고 이제는 각 pred마다 할일을 다르게 넣을 수 있겠다. 첫번째 인자를 _로 한 이유는 focus나 val("") 등 DOM조작을 위한 객체를 따로 넘긴다고 하자.

var validatePhoneFinal = validatePhoneCurried(function(_, $dom) {
  alert("헨드폰문제!");
  $dom.focus();
});

var validateCardFinal = validateCardCurried(function(_, $dom) {
  alert("카드문제");
  $dom.focus();
});

var validateNationalidFinal = validateNationalidCurreid (function(_, $dom) {
  alert("주민번호문제");
  $dom.focus();
});

이렇게 만들었다 치자. 이제 위에 코드를 저것들로 바꾸면 된다.

if (!(validatePhoneFinal(phone_1, $("#phone_1")) &&
      validatePhoneFinal(phone_2, $("#phone_2")) &&
      validatePhoneFinal(phone_3, $("#phone_3"))) {
  return;
}

....
if (!(validateCardFinal(card_1, $("#card_1")) &&
      validateCardFinal(card_2, $("#card_2")) &&
      validateCardFinal(card_3, $("#card_3")) &&
      validateCardFinal(card_4, $("#card_4"))) {
  return;
}
...
if (!(validateNationalidFinal(national_id_1 , $("#national_id_1")) &&
      validateNationalidFinal(national_id_2 , $("#national_id_2"))) {
  return;
}

여기서 map이나 every 같은 것을 이용하는 것이 큰 도움이 될 것 같지만 그러진 않겠다. 오늘의 주제는 커리니까.
curry라는 함수 한번 가지고 놀아봤다.

[javascript]자바스크립트 curry 구현소스를 파악해보자.

출처 :
https://edykim.com/ko/post/writing-a-curling-currying-function-in-javascript/
https://medium.com/@kevincennis/currying-in-javascript-c66080543528

커링이라는 개념은 하스켈을 공부할 당시 알게 되었다.
clojure의 partial과 비슷한 개념이다. (동일한가?)

여튼 자바스크립트로 curry를 쓰고 싶은 욕구가 강했지만, underscore.js같은 라이브러리를 사용할 수 없는 제약이 있어,
다른 누군가가 어떻게 curry만을 구현했는지 확인하고 복붙을 하기로 하였다.

그 중에 위의 링크를 확인했고 하나하나 파고들어갔다. 아래 내용은 위 블로그를 읽고 나만의 부연설명을 추가한 것이다.

function curry(fn) {
 var arity = fn.length; // 함수의 필요 인자
 // 매번 curry된 함수를 호출할 때마다 새로운 인자를 배열에 넣어 클로저 내에 저장한다.
 // 배열의 길이는 fn.length와 동일해야 한다. (실행될 때)
 // 혹여 인자의 수가 동일하지 않으면 새로운 함수로 반환한다.
 
 // 인자 목록을 가지는 클로저가 필요하다 (함수로 둘러쌓아야 한다 
 // 또 여기서 개별의 클로저가 생성되야 하니까 즉시 실행함수로 만든다.)
 // 전체인자(배열)과 fn.length를 확인
 // 인자의 수가 부족하면 부분적으로 적용된 함수를 반환 
 // 인자의 수가 충족하면 fn에 모든 인자를 적용,호출하여 리턴
 return (function resolver() {
  // 지금까지 받은 인자를 복사한다.  // 이전 클로저가 오염되지 말게
  var memory = Array.prototype.slice.call(arguments);
  // resolver는 익명함수를 반환한다. 
  // resolver는 인자가 부족할 때 반환한다.
  // resolver가 새로 반환되는 이유는 클로저를 위한 것같다.
  
  // resolver는 바로 실행되고 익명함수를 하나 리턴한다.
  // resolver가 이전까지 모은 인자를 가지고 있다. (memory)
  // 이걸 변수에 담았다가 나중에 실행시킬 것이다.
  // 실행시키면 arguments에서 인자를 memory와 합체한다.
  // 그리고 원래 실행되어야할 함수(fn)이 필요로 하는 인자의 갯수와 비교
  // 지금까지 모은 인자(local)과 arity의 길이가 맞다면
  // 원래함수를 호출(fn), 그렇지 않으면 resolver를 다시 반환 (인자를 더 받는다)
  return function() {  
   var local = memory.slice();
   Array.prototype.push.apply(local, arguments);
   next = local.length >= arity ? fn : resolver;
   return next.apply(null, local);
  };
 }());
}

한번 생성한 커리에 함수를 넣어보자. 지금 함수를 넣으면 인자 fn에 들어가는 것이다.
====

function volume(l, w, h) {
  return l * w * h;
}

var curried = curry(volume);

이제 아래 코드를 보면서 어떻게 되는지 보자.

function curry(fn) {
 var arity = fn.length; // 1. 숫자 3이 저장된다.
 return (function resolver() {
  var memory = Array.prototype.slice.call(arguments); // 2. resolver를 인자없이 실행하였다.(현재는 커리만 되는 상태)
  
  return function() {
   var local = memory.slice();
   Array.prototype.push.apply(local, arguments);
   next = local.length >= arity ? fn : resolver;  // 3. arity가 부족하므로 함수를 리턴.
   return next.apply(null, local);
  };
 }());
}

함수를 리턴받아서 curried에 넣었다. 여기에 다른 인자들을 넣어보자.
일단 2를 넣을 것인데 l, w, h 총 3개가 필요한 함수에게는 부족한 인자 갯수이다.

var length = curried(2);

어떤 일이 일어나는지 아래를 보자.

function curry(fn) {
 var arity = fn.length; 
 return (function resolver() {
  var memory = Array.prototype.slice.call(arguments);
  
  return function() {  // 1. resolver로 반환된 익명함수가 실행됨. 
   var local = memory.slice();  // 2. memory는 현재 0개의 인자를 가지고 있다. 
   Array.prototype.push.apply(local, arguments);  // 3.이번에 추가된 2가 local에 push된다.
   next = local.length >= arity ? fn : resolver;  // 4.아직 인자가 1개이기 때문에 다시 resolver를 반환한다.
   return next.apply(null, local);  // 4. 알다시피 이번에 던져지는 resolver는 또한 새로운 클로저와 함께하는 새로운 함수다.
  };
 }());
}

한번 더

var lengthAndWidth = length( 3 );

function curry(fn) {
 var arity = fn.length; 
 return (function resolver() {
  var memory = Array.prototype.slice.call(arguments);
  
  return function() {  
   var local = memory.slice();  // 1. 새로운 클로저에 들어있는 memory는 [2] 이다. local에 복사한다. (이전 클로저에 해를 끼치지 않게)
   Array.prototype.push.apply(local, arguments);  // 2. 새로운 인자 3을 추가한다. [2,3]
   next = local.length >= arity ? fn : resolver;  // 3.아직 인자가 2개이기 때문에 다시 resolver를 반환한다.
   return next.apply(null, local);  // 4. 알다시피 이번에 던져지는 resolver는 또한 새로운 클로저와 함께하는 새로운 함수다.
  };
 }());
}

이제 마지막으로 하나의 인자만 더 넣으면 실행될 것이다.

console.log( lengthAndWidth( 4 ) ); // 24

왜 그렇게 되는지 아래를 보자.

function curry(fn) {
 var arity = fn.length; 
 return (function resolver() {
  var memory = Array.prototype.slice.call(arguments);
  
  return function() {  
   var local = memory.slice();  // 1. 새로운 클로저에 들어있는 memory는 [2,3] 이다. local에 복사한다. (이전 클로저에 해를 끼치지 않게)
   Array.prototype.push.apply(local, arguments);  // 2. 새로운 인자 4을 추가한다. [2,3,4]
   next = local.length >= arity ? fn : resolver;  // 3.아직 인자가 3개이기 때문에 fn을 넣는다. (fn은 지금까지 변경된 적도 사용된 적도 있다. 하지만 이날을 위해 기다렸다)
   return next.apply(null, local);  // 4. 이번에는 함수를 던지지 않고 fn의 리턴값이 실행될 것이다. (하지만 fn이 리턴하는게 함수라면... 음...)
  };
 }());
}

2019년 2월 15일 금요일

[clojure] 4clojure easy버전 0에서 50까지 문제 풀고 중간점검

clojure로 뭘 할지 감이 잡히지 않아서, 그냥 4clojure나 가끔씩 풀어보기로 했다.
elementary, easy부분만 풀었는데 괜찮았다. 글자그대로 쉬웠지만 어떤 것들은 꽤나 생각을 해야 했다.
4clojure를 풀다보면 내 뇌의 생각하는 방식이 바뀌어야 한다는 느낌이 든다. 운동을 할 때도 가동범위가 중요한데, 사용하지 않던 뇌부분을 사용한 느낌이 들면서, 나의 뇌 가동범위가 부족한 것이 아닌가 싶었다.

clojure로 언젠가 개발을 하지 않더라도, 이 문제를 풀면서 뭔가 개발을 할 때 생각하는 방식이 늘어나는 느낌을 받을 것 같다. (좀더 난이도가 올라가면 말이다)

결과적으로 4clojure를 풀기로 결심한 것은 만족이다.
https://github.com/ssisksl77/clj-web-demo/blob/master/src/web_demo/4clojure/elementary.clj

51~100도 금방 가자.

2019년 2월 14일 목요일

[리뷰][Coursera] 코세라의 [Parallel Programming in Java] 수강을 마치며

코세라에서 수강할 수 있는 병렬프로그램의 첫번째 코스를 마쳤다.
생각보다 어렵지 않았다.

1. 병렬프로그램 개발을 하기 이전에 나의 코드를 분석할 수 있는 기본적인 방법을 알려준다. WORK, SPAN 등등
2. Fork/Join Framework에 대해서 설명한다.
3. Future에 대해서 배운다.
4. Barrier를 배운다.
5. Phaser를 배운다.
6. Phaser를 이용한 다양한 예시를 배운다.

사실 이번 강의에서 인상깊었던 것은 4주차에서 배운 Phaser라는 기능이다. 이 기능은 정말 멋지다. 동기화에 대한 많은 생각을 해주게 하는 기능이다. 아니 Latch와 Barrier 이상으로 뭔가 더 동기화 해야할 일이 있단 말인가?

여기에선 있다고 말한다. 아쉬웠던 점은 project assignment가 너무 쉽다. 그냥 수강한 걸보고 배운데로 하면 된다. 좀 더 어려웠으면 하기도 하지만, 그러면 다 fail을 할 수도 있겠다고 생각한 걸까? 예시로 동기화를 하는 기능은 정말 많은 이해가 되었지만, 비동기 통신을 하는 것 자체는 전부 주어진 메소드로 실행해야 하기 때문에 처음부터 만들지는 않는다.

코스가 끝나면 아래처럼 링크드인에 Certificate을 넣을 수 있다.

그리고 주어진 값을 넣으면 링크드인의 자격증명에 보이기 시작한다.

https://www.linkedin.com/in/ssisksl77/

4주 짜리긴 한데 2주만에 끝났다. 이외로 내용이 길지 않았다.
꽤나 후련하다.
3월 쯔음에나 두번째 코스로 들어가지 않을까 싶다.

꽤나 기대된다. 두번째 코스도 내용이 긴 것 같지는 않다.
하지만 액터모델이라는 것이 꽤나 기대된다.

이러다가 스칼라를 공부해야 하는 지도 모르겠다.
사실 스칼라에 손을 대지 않은 이유는 온전히 나의 고집이었다.
그저 Clojure가 더 낫지 않을까 하는 나의 근거없는 확신 때문에 가끔씩 4Clojure나 풀면서 "나는 괜찮은 개발자야" 라고 자위했다.

하지만 둘 다 한다고 더 많은 시간을 들일 것 같지도 않고, 함수형 프로그래밍에 Clojure와 하스켈 맛보기만으로는 아직 잘 모르겠다. (사실 하스켈은 이제... 모나드나 어플리커티브 펑터를 배운 이후로 별로 하고 싶지 않다. 그래도 모나드를 배운 것은 정말 유용했다.)

일단 바로 할지는 모르겠고, Coursera에서 스칼라를 이용한 함수형 프로그래밍 강의가 있는데 함수형 프로그래밍에 대해 더 알기 위해서라도 익혀놔야겠다.

2019년 2월 7일 목요일

코세라에서 병렬프로그래밍을 배우기 시작했다 (1주차)

코세라에서 제공하는 Parallel Programming in Java 라는 코스를 듣게 되었다.
1주차 내용을 Fork/Join 프레임워크에 대한 설명이었다. 사실 프레임워크를 설명하는 것보다는 병렬프로그래밍을 할 때 사용하는 기본적인 패턴을 가르쳐주었으며,
우리가 나중에 만들 병렬프로그램 설계를 분석하는 방법을 알려준다.(암달의 법칙을 빠지지 않는다.)

1주차를 들으면서 든 생각은 [생각보다 괜찮다]였다. 내용이 잘 짜여져 있고, 가르쳐주는 강사님(교수님?) 또한 아주 잘 가르쳐주신다. (한글 자막은 없다, 코세라는 재능기부를 기다리고 있다.)

또한 괜찮은 것은 바로 assignment다 직접 코딩을 하고 점수를 받는 것이다. 필자는 이것을 푸는데 꽤나 오랜시간이 걸렸다. 1시간 정도 걸린 것 같다. 풀고 보니 별 것 아니었다. 병렬프로그래밍이나 Fork/Join 프레임워크에 익숙하다면 풀기 쉬울 것이다. 그렇지 않다면 약간 버벅이면서 풀 수 있는 정도였다.

2주차가 기대된다.

2019년 1월 17일 목요일

[on lisp] 5.6 Recursion on Subtrees (중요)

5.6 Recursion on Subtrees
There is another recursive pattern commonly found in Lisp programs: recursion on subtrees
리스프 프로그램에서 흔히 볼 수 있는 또 다른 재귀 패턴이 있다. 서브트리 재귀
This pattern is seen in cases where you begin with a possibly nested list, and want to recurse down both its car and its cdr.
이 패턴은 중첩 리스트로 시작, car,cdr를 이용하여 재귀적으로 트리 아래로 들어간다.

The Lisp list is versatile structure.
lisp 리스트는 다재다능한 구조이다.
Lists can represent, among other things, sequences, sets, mappings, arrays, and trees.
리스트는 시퀀스, 세트, 매핑, 배열 및 트리를 나타낼 수 있다.
There are serveral different ways to interpret a list as a tree.
리스트를 트리로 해석하는 몇 가지 방법이 있다.

The most common is to regard the list as a binary tree whose left branch is the car and whose right branch is the cdr
가장 보편적인 것은 왼쪽 가지가 car이고 오른쪽 가지가 cdr인 이진 트리로 간주하는 것이다.
Figure 5.7 shows three examples of lists and the trees they represent.
그림 5.7이 리스트(트리)의 3가지 예다.

;; Figure 5.7: Lists as trees.
(a . b) 
(a b c) 
(a b (c d))

이게 어떻게 트리냐고 보는데 점으로 연결된 b는 리스트(또는 그냥 값)으로 볼 수 있다.
그러므로 cdr 값은 subtree라고 보는 것이다.
아래 내용을 보면 이해가 쉬울 것이다.

(a b c) = (a . (b . (c . nil))) 
(a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))

어떠한 형태의 리스트도 2진트리로 해석될 수 있다. 하여 copy-list와 copy-tree와 같은 공통 리스프 함수의 쌍 간의 구별이 필요하다.

The former copies a list as a sequence -if the list contains sublists, the sublists, being mere elements in the sequence, are not copied.
이 리스트를 시퀀스라 간주하고 복사해보자. 만약 리스트에 서브리스트(sublists)를 보유한다면, 그것이 해당 리스트의 요소일 뿐이라도 복사되지 않는다.

(setq x '(a b) listx (list x 1))
((A B) 1)
(eq x (car (copy-list listx)))
T
;; copy-list구현을 다시 보자.
;; copy-list
(lrec #'(lambda (x f) (cons x (funcall f))))
;; Figure 5.5: Function to deﬁne ﬂat list recursers
;; 이전에 본 소스임.
;; 특이하게 함수를 리턴함
(defun lrec (rec &optional base) 
  (labels ((self (lst) 
    (if (null lst) 
     (if (functionp base) 
      (funcall base) 
   base) 
  (funcall rec (car lst) 
               #'(lambda () (self (cdr lst))))))) 
 #'self))

;; 반대로 copy-tree는 리스트를 트리로 간주한다.
;; 서브리스트들 전부 복사된다.
(eq x (car (copy-tree listx)))
NIL

copy-tree구현체를 봐보자.

;; 1. 매개변수가 리스트가 아니라면 리턴
;; 2. car 내용을 재귀로 들어감 (왼쪽 가지도 있을 수 있으니까)
;; 3. (cdr tree)해서 오른쪽 가지가 있따면, 그것도 재귀
;; 4. 왼쪽 오른쪽 cons로 합친다.
;; 5. 머지된거 리턴
(defun our-copy-tree (tree)
  (if (atom tree) 
      tree ;; 1
      (cons (our-copy-tree (car tree)) ;; 2
            (if (cdr tree) (our-copy-tree (cdr tree)))))) ;; 3

트리에서 리프(leaves)의 갯수를 카운트 하는 예제를 만들어보자.

; 1. atom이면 1
; 2. (car tree) 왼쪽서브트리를 재귀
; 2.1 (cdr tree) 오른쪽서브트리가 있으면 재귀
; 2.3 (cdr tree) 오른쪽서브트리가 없으면(nil) 1 리턴
; 2.4 (+ 2.1 2.3) 재귀돈거 더하기
(defun count-leaves (tree)
  (if (atom tree)
      1
      (+ (count-leaves (car tree))
         (or (if (cdr tree) (count-leaves (cdr tree)))
             1))))

A tree has more leaves than the atoms you can see when it is represented as a list:
특이한 것이 있는데 리스트에 들어있는 것 보다 더 많은 숫자가 리턴된다는 것이다.

(count-leaves '((a b (c d)) (e) f))
10

The leaves of a tree are all the atoms you can see when you look at the tree in its dotted-paire representation.
리프는 트리에서 보이는 모든 아톰값을 말하는데, 지금 저 트리는 점으로 이루어진 쌍 값에서 안보이게 한게있음 (미관상)
A dotted-pair notation, ((a b (c d)) (e) f) would have four nils that aren't visible in the list representation (one for each pair of parentheses) so count-leaves returns 10.
dotted-pair에를 잘 보면 마지막에 꼭 '. nil'이 포함되어 있다. 이 nil은 소괄호 마다 마지막에 하나씩 있다.
그러므로 소괄호 하나에 nil은 하나씩 무조건 있기 때문에 4개가 더해진 것

In the last chapter we defined several utilities which operate on trees. For example, flatten(page 47) takes a tree and returns a list of all the atoms in it.
이전 챕터에서 트리에서 이용할 수 있는 유틸리티를 몇개 만들었다.
----잠깐 이전에 공부했던 내용 돌아보기 START

;; Fig 4.3 : Doubly-recursive list utilities
(defun flatten (x)
  (labels ((rec (x acc)
              (cond ((null x) acc)
                    ((atom x) (cons x acc))
                    (t (rec car x) (rec (cdr x) acc))))))
    (rec x nil)))
;; 양쪽 순회가 가능해야 한다.
;; 1 tree가 널이면 acc를 반대로 돌려서 리턴
;; 2 (car tree)가 리스트이면
;; 2.1 (cdr tree)를 남은 트리로 놓고
;; 2.2 (car tree)를 따로 테스트해서 acc에 추가한다.
;; 3 (car tree)가 리스트가 아닌경우
;; 3.1 테스트가 맞는지 확인한다.
;; 3.2 맞으면 버리고 acc만 리턴
;; 3.3 틀리면 (cons (car tree) acc)로 acc에 값을 넣는다.
(defun prune (test tree)
  (labels ((rec (tree acc)
             (cond ((null tree) (nreverse acc))
                   ((consp (car tree))
                    (rec (cdr tree)
                         (cons (rec (car tree) nil) acc)))
                   (t (rec (cdr tree)
                           (if (funcall test (car tree))
                               acc
                               (cons (car tree) acc))))))
    (rec tree nil)))

Fig 4.3 shows two examples of functions that descend into(서서히 빠져들다) nested lists
그림4.3은 nested list 안으로 들어가는 함수들을 보여준다.

flatten, 쫙펴주는 함수
prune, 은 순회하면서 없앤다. (remove-if같은 건가)

(flatten '(a (b c) ((d e) f)))
(A B C D E F)

(prune #'evenp '(1 2 (3 (4 5) 6) 7 8 (9)))
(1 (3 (5)) 7 (9))

----잠깐 이전에 공부했던 내용 돌아보기 END

이 flatten이 아래처럼 다시 쓸 수 있다.(비효율적으로)
하지만 꽤나 간결하다.

(defun flatten (tree)
  (if (atom tree)
      (mklist tree)
      (nconc (flatten (car tree))
             (if (cdr tree) (flatten (cdr tree))))))

find-if의 재귀버전을 마지막으로 보자. 일반리스트, 트리 모든 경우에 먹힌다.
Finally, consider rfind-if, a recursive version of find-if which works on tree as well as flat lists:

;; our-find-if는 비교용
(defun our-find-if (fn lst)
  (if (funcall fn (car lst)
      (car lst)
      (our-find-if fn (cdr lst)))

(defun rfind-if (fn tree)
  (if (atom tree)
      (and (funcall fn tree) tree)
      (or (rfind-if fn (car tree))
          (if (cdr tree) (rfind-if fn (cdr tree))))))

To generalize find-if for trees, we have to decide whether we want to search for just leaves, or for whole subtrees.
find-if를 트리용으로 일반화하려면, 리프만 원하는지 모든 서브트리를 원하는지 결정해야 한다.
Our rfind-if takes the former approach, so the caller can assume that the function given as the first argument will only be called on atoms:
여기서 보인 rfind-if는 전자의 접근방식을 이용한다. 하여 호출자는 첫번째 매개변수는 무조건 atom임을 가정할 수 있을 것이다. 그러므로 predicate으로 찾는게 이건지 확인할 때, 당연히 매개변수가 atom이라는 전재로 들어가야할 것이다.

(rfind-if (fint #'numberp #'oddp) '(2 (3 4) 5))

우리는 지금까지 4가지의 비슷한 형태의 함수를 보았다.
copy-tree, count-leaves, flatten 그리고 rfind-if.

Indeed, they're all instances of an archetypal function for recursion on subtress.
사실, 이것들은 서브트리에 재귀반복을 위한 전형적인 함수들이다.
As with recursion on cdrs, we need not leave this archetype to float vaguely in the background.
cdrs들로만 만든 재귀(일반리스트)와 마찬가지로, 우리는 이 원형을 이 상태로 남겨둬서, 4개의 함수들의 형태를 어정쩡하게 남길 필요는 없다. (다시 유틸리티 함수 같은 것을 만들어야 하지 않을까)

To get at the archetype itself, let's look at these functions and see what's not pattern.
이 원형 자체에 접근하기 위해서, 우리가 만든 4개의 함수 안에 어던 것이 패턴인지 아닌지 확인해보자.
Essentially our-copy-tree is two facts:
our-copy-tree는 두 요소가 있다.
1. In the base case it returns its argument.
base case가 걸린 경우 그 당시 재귀로 들어온 함수를 리턴한다.
2. In the recursive case, it applies cons to the recursions down the left (car) and right (cdr) subtress.
재귀를 해야 하는 case에 걸린 경우, cons로 왼쪽(car)으로 재귀 돈거랑 오른쪽(cdr)으로 재귀 돈 서브트리를 합친다.

이 두개의 요소를 바탕으로 아래처럼 쓸 수 있다.(유틸리티함수는 아래 보자)

(ttrav #'cons #'identity)

ttrav("tree traverser")는 Figure 5.8에서 보여준다.

;; Fig 5.8 : Function for recursion on trees.

; rec(첫번째 매개변수)는 
(defun ttrav (rec &optional (base #'identity))
  (labels ((self (tree)
             (if (atom tree)
                 (if (functionp base)
                     (funcall base tree)
                     base)
                 (funcall rec (self (car tree))
                              (if (cdr tree)
                                  (self (cdr tree)))))))
    #'self))

Instead of passing one value in the recursive case, we pass two, one for the left subtree and one for the right.
재귀를 하는 case에서 값을 하나 보내는 대신, 2개를 보낸다. (왼쪽 서브트리, 오른쪽 서브트리)
If the base argument is a function it will be called on the current leaf.
만약 base매개변수가 함수라면 현재 상태가 리프에 있을 때 실행됨.
In ﬂat list recursion, the base case is always nil, but in tree recursion the base case could be an interesting value, and we might want to use it.
일반 리스트 재귀서는 base case가 항상 nil이다, 하지만 트리재귀에서 base case는 그것과는 아주 다른 값이 될 수 있으며, 그걸 사용하고 싶을 것이다.

With ttrav we could express all the preceding functions except rfind-if.
ttrav는 rfind-if를 제외하고 다른 함수들을 모두 표현할 수 있다.

; our-copy-tree
(ttrav #'cons)

; count-leaves
; (or r 1)은 순회하다가 요소가 nil이 아니면 그걸 뱉는다고 보자.
; r이 nil 이면 1로 리턴
; 두번째 값은 optional인데 1로 넣었다. base case인 경우 1을 리턴
(ttrav #'(lambda (l r) (+ 1 (or r 1))) 1)

; flatten
; nconc로 재귀하고 합치는 거
(ttrav #'nconc #'mklist)

To deﬁne rfind-if we need a more general tree recursion builder which gives us control over when, and if, the recursive calls are made.
rfind-if를 정의하려면 좀 더 일반화된 트리 재귀 빌더(함수)가 필요하다.
이 함수는 when,if 그리고 재귀함수를 만드는 그 상황도 우리가 조절할 수 있어야 하다.
(ttrav는 무조건 트리의 모든 곳을 순회한다.find-if는 찾으면 멈춰야 한다.)
As the ﬁrst argument to ttrav we gave a function which took the results of the recursive calls.
ttrav에서 첫번째 매개변수는 재귀호출의 결과를 받는 함수였다.
For the general case, we want to use instead a function which takes two closures representing the calls themselves.
이제 일반적인 함수에서는 우리는 대신 다른 함수를 사용할 건데, 자기자신을 호출하는 두개의 클로저를 받는다.(??)
Then we can write recursers which only traverse as much of the tree as they want to.
그렇게면 우리는 우리가 원하는 만큼만 순회하는 recurser(재귀호출하는 녀석?)를 작성할 수 있다.

; Fig 5.10: Function for recursion on trees
; 1 lambda로 self를 바로 실행되지 않도록 하였다.
(defun trec (rec &optional (base #'identity))
  (labels
    ((self (tree)
       (if (atom tree)
           (if (functionp base)
               (funcall base tree)
               base)
           (funcall rec tree
                        #'(lambda () ; 1
                            (self (car tree)))
                        #'(lambda ()
                            (if (cdr tree)
                                (self (cdr tree))))))))
    #'self))

Fig 5.10을 보자.
The second arg to trec should be a function of three argument:
두번째 매개변수는 3개의 매개변수를 받는 함수여야 한다.
the current object and the two recursers.
현재 객체와 두개의 recurser(left/right 인듯)가 들어간다.
The latter two will be closures representing the recursions down the left and right subtress.
뒤에 두 매개변수는 왼쪽 오른쪽 서브트리를 재귀로 들어가는 녀석이다.
특이한 것이 이 두 함수는 각자 왼쪽/오른쪽 서브트리를 클로저로 가져간다.
With trec we would define flatten as:
trec 이용하여 flatten을 만들어자.

; (conc l r)에서 (nconc (l) (r))로
(trec #'(lambda (o l r) (nconc (funcall l) (funcall r)))
      #'mklist)
;; ttrav 버전을 다시 보자
(ttrav #'conc #'mklist)

이제 rfind-if를 보자(oddp를 접목하자)

;; (or l r)에서 (or (l) (r))
;; or은 값이 있으면 바로 리턴하고 다음 것은 평가하지 않는다.
;; lambda로 묶어놓은 이유가 바로 이거다.(중요)
(trec #'(lambda (o l r) (or (funcall l) (funcall r)))
      #'(lambda (tree) (and (oddp tree) tree)))

; 비교용
(defun rfind-if (fn tree)
  (if (atom tree)
      (and (funcall fn tree) tree)
      (or (rfind-if fn (car tree))
          (if (cdr tree) (rfind-if fn (cdr tree))))))

이렇게 #'(lambda)로 감싸서 바로 실행되지 않도록 하였다.
잘 보면

2019년 1월 15일 화요일

[on lisp] 5.5 Recursion on Cdrs 재귀함수

5.5 Recursion on Cdrs
Recursive functions are soimportant in Lisp programs that it would be worth having utilites to build them.
재귀 함수는 lisp에서 매우 중요하기 때문에 이것들을 만들기 위한 유틸리티가 있어야할 가치가 있다.
This section and the next describe functions which build the two most common types.
이 섹션과 다음 섹션에서는 가장 일반적인 두 가지 유형의 재귀함수를 소개한다.

In Common Lisp, these functions are a little awkward to use.
Common Lisp에서 이 함수들을 살짝 어색하게 사용된다.
Once we get into the subject of macros, we will see how to put a more elegant facade on this machinery.
일단 우리가 매크로의 주제로 들어가게 되면, 우리는 이 기계에 좀 더 우아한 외관을 넣는 방법을 알게 될 것이다.

'recursers'를 만드는 매크로는 섹션 15.2, 15.3에서 논의된다.

Repeated patterns in a program are a sign that it could have been written at a higher level of abstraction.
반복되는 패턴은 높은 수준의 추상화로 작성될 수 있다는 신호다.

What pattern is more commonly seen in Lisp programs than a function like this:
Lisp에서 일반적으로 이와 같은 함수보다 일반적으로 보이는 패턴은 아래와 같다.

;; 재귀로 길이 구하기
(defun our-length (lst)
    (if (null lst)
        0
        (1+ (our-length (cdr lst)))))
;; or this
;; 재귀로 모두 참인지 구하기
(defun our-every (fn lst)
    (if (null lst)
        t
        (and funcall fn (car lst))
        (our-every fn (cdr lst))))

Structurally these two functions have a lot in common.
구조적으로 이 두 함수는 공통점이 많다.
They both operate recursively on successive cdrs of a list, evaluating the same expression on each step, except in the base case, where they return a distinct value.
둘 다 리스트에 cdr를 재귀로 반복 연산을 하고, 동일한 표현식을 각 스텝에 실행한다, 고유한 값을 리턴하는 base case만 제외한다.

This pattern appears so frequently in Lisp programs that experienced programmers can read and reproduce it without stopping to think.
이 패턴은 리습에서 자주 보인다. 너무 자주 보여서 경험이 있는 개발자는 개발하는데 끊킴이 없이 읽고 재생산 할 수 있다.
Indeed, the lesson is so quickly learned, that the question of how to package the pattern in a new abstraction does not arise.
실제로, 이런 실습을 너무 빨리 배워 패턴을 새로운 추상화로 패키지하는 방법에 대한 질문이 발생하지 않습니다. (왜냐하면 당연스럽게 이런식으로 개발을 하기 때문)

However, a pattern it is, all the same. Instead of writing these functions out by hand, we should be able to write a function which will generate them for us.
하지만 패턴은 모두 같다. 패턴이 있기 때문에 손으로 쓰는 것보다는 그 패턴을 생성해주는 함수를 만드는 것이 타당하다.

;; Figure 5.5: Function to define flat list recursers.
;; rec 요소별로 실행되어야 할 녀석
;; base 디폴트값.
;; 1. #'self 재귀함수를 생성
;; 2. lst가 없으면 (다 돌았으면)
;; 3. base를 리턴한다.(base가 함수면 실행하고 리턴)
;; 4. lst가 있으면 
;; 5. (car lst)로 일단 빼놓고 rec를 재귀로 다시 실행하는 첫번째 매개변수가 되게 한다.
;; 6. (self (cdr lst))를 람다로 묶는다.
;; #'self 함수를 리턴한다.
(defun lrec (rec &optional base)  ;; 함수를 리턴한다.
    (labels ((self (lst)  ;; 1
                   (if (null lst)  ;; 2
                       (if (functionp base)  ;; 3
                           (funcall base)
                           base)
                       (funcall rec (car lst)  ;; 5
                                    #'(lambda () ;; 6
                                              (self (cdr lst)))))))
            #'self))

Figure 5.5 contains a function-builder called lrec("list recurser") which should be able to generate most functions that recurse on successive cdrs of a list
그림5.5에 lrec라는 함수빌더(함수패턴을 만들어주는 녀석)가 있다.
이 빌더는 위 패턴 (리스트의 cdr를 재귀로 실행. 반복연산한다)을 생성할 수 있어야 한다.

The first argument to lrec must be a function of two arguments: the current car of the list, and a function which can be called to continue the recursion.
현재 리스트의 car(초기값)와 재귀로 호출 될 함수이다.
our-length를 다시 만들자.

;; 아래처럼 형태를 만들 필요가 없이 계속 호출될 함수
;; 초기값을 넣는다.
(lrec #'(lambda (x f) (1+ (funcall f))) 0)

리스트의 길이를 찾는데 요소를 확인할 필요나 중간에 멈출 필요가 없으므로 x(요소)는 항상 무시되고 f는 항상 호출된다.
그러나 our-every함수를 표현할 수 잇는 두 가지를 모두 가능성을 모두 표현해야 한다.
예를 들어 oddp

(lrec #'(lambda (x f) (and (oddp x) (funcall f))) t)

재귀케이스가 'our-every'와 같은 함수에서 첫번째 인자가 false를 반환하면 바로 그곳에서 멈추고 싶다. 다돌면 안된다.
즉, 재귀적일 경우에 전달 된 인수는 값이 아니라 함수여야 한다. (호출하면 값을 뱉는) 그러니까 함수의 리스트를 매개변수로 주면 될듯

Figure 5.6은 lrec로 정의된 기존의 Common Lisp함수를 보여준다.
lrec를 이용하는 것이 항상 이상적인 구현은 아니다.
사실 이 장에서 정의된 lrec와 다른 재발생(재귀) 생성기(recurser generators)는 꼬리 재귀랑은 또 다르다.
이러한 이유로 그들은 초기 버전의 프로그램이나 속도가 중요하지 않은 부분에서 사용하기에 가장 적합하다.

Figure 5.6: Functions expressed with lrec.
; copy-list
(lrec #’(lambda (x f) (cons x (funcall f))))
; remove-duplicates
(lrec #’(lambda (x f) (adjoin x (funcall f))))
; find-if, for some function fn
(lrec #’(lambda (x f) (if (fn x) x (funcall f))))
; some, for some function fn
(lrec #’(lambda (x f) (or (fn x) (funcall f))))

2019년 1월 11일 금요일

[on lisp] 5.4 Composing Functions 함수 조합(되게 유익)

5.4 Composing Functions
함수 f의 보수는 ∼f로 표기된다.

5.1절에서 closure가 ∼을 Lisp 함수로 정의할 수 있게 함을 보였다.
함수에 대한 또 다른 공통 연산은 연산자 ◦로 표시되는 '합성'이다.
f와 g가 함수라면, f ◦g는 함수이고 f ◦g (x) = f (g (x))이다.
클로저는 또한 ◦을 Lisp 함수로 정의하는 것을 가능하게합니다
아래 Figure5.3은 여러 함수를 취해 그 혼합물을 리턴하는 compose함수를 정의한다.

;; Figure 5.3: An operator for functional composition.

;; 1. &rest는 복수의 함수를 매개변수를 받겠다.
;; 2. 함수가 존재한다면
;; 2.1 리스트의 마지막 함수 가져오기 (compose는 오른쪽부터 합쳐진다)
;; 2.2 fn1 함수가 어떤 매개변수를 받을지 모르지 args로 다 받음
;; 2.3 마지막 함수를 제외한 함수 리스트를 구함(마지막 리스트는 초기값에 들어감)
;; 2.4 reduces로 하나하나 함수를 누산한다.
;; 2.5 :from-end t 뒤에서 부터 실행하라는 뜻
;; 2.6 :initial-value 첫번째 함수를 초기값으로 세팅
;; 3. 함수가 없으면 identity 리턴
(defun compose (&rest fns) ;; 1
    (if fns ;; 2
        (let ((fn1 (car (last fns))) ;; 2.1
                   (fns (butlast fns))) ;; 2.2
              #'(lambda (&rest args) ;; 2.3
                        (reduce #'funcall fns ;; 2.4
                                :from-end t ;; 2.5
                                :initial-value (apply fn1 args)))) ;; 2.6
             #'identity)) ;; 3
              
;; 사용법
(compose #'list #'1+) ;; 아래 값과 같다.
#'(lambda (x) (list 1+ x))

compose에 대한 인수로 주어진 모든 함수는 마지막 인수를 제외하고, 모두 하나의 인수를 받는 녀석들이어야 한다.
마지막 함수는 아무런 제약이 없다. 무엇이든지 인수가 주어지면 compose에 의해 함수가 초깃값으로 반환될 것이다.

> (funcall (compose #’1+ #’find-if) #’oddp ’(2 3 4))
4

위에 내용은 함수들을 closure로 감싼 함수를 리턴한 것과 같다.

;; Figure 5.4: More function builders.
(defun fif (if then &optional else)
    #'(lambda (x)
              (if (funcall if x)
                  (funcall then x)
                  (if else (funcall else x)))))
(defun fint (fn &rest fns)
    (if (null fns)
        fn
        (let ((chain (apply #'fint fns)))
             #'(lambda (x)
                       (and (funcall fn x) (funcall chain x))))))

(defun fun (fn &rest fns)
    (if (null fns)
        fn
        (let ((chain (apply #'fun fns)))
             #'(lambda (x)
                       (or (funcall fn x) (funcall chain x))))))

not은 리스프 함수이기 때문에, complement는 compose의 특별한 경우이다.
이녀석은 이렇게 정의될 수 있다.

(defun complement (pred)
  (compose #'not pred))

함수들을 조합(composing)하는 것 이외의 다른 방법으로 기능을 결합(combine)할 수 있다.

(mapcar #'(lambda (x)
                  (if (slave x) ; 노예면
                      (owner x) ; 오너를
                      (employer)) ; 아니면 고용주를
                      people) ; 사람 , 노예 아니면 직장인

위와 같은 함수를 자동으로 생성하는 연산자를 정의할 수 있다.
Figure 5.4의 fif를 사용하면 다음과 같은 효과를 얻을 수 있다.

(mapcar (fif #'slave #'owner #'employer)
        people)

아주 간단해졌다.

fif코드에 대해 알아보자.
1. if, then, else를 담은(closure) 람다함수 리턴
1.1 람다는 true/false 값을 받는다.
2. then 걸린 함수 실행
3. else

(defun fif (if then &optional else)
    #'(lambda (x) ; 
              (if (funcall if x) ; 1
                  (funcall then x) ; 2
                  (if else (funcall else x))))) ; 3

Figure 5.4는 일반적으로 발생하는 유형의 함수에 대한 몇 가지 다른 생성자를 포함한다.
두 번째, fint는 다음과 같은 경우입니다.
트루이면 그 상태에서 멈추는 거니까 거기까지만 일을 했다는 것! 특이한 건 그때그때 함수를 실행할 것이겠지?
and이니까 그럴 것이다.(and는 매크로로 보임)
;; 아래 소스는 signed,sealed,delivered가 모두 참인경우

(find-if #'(lambda (x)
                   (and (signed x) (sealed x) (delivered x)))
         docs)

find-if의 인수로 주어진 predicate(술어)는 그 안에서 호출되는 세 개의 predicates의 교차점(intersection)이다.
그러니까 모두 참인경우를 말한다. 교집합
"function intersection"을 뜻하는 fint를 사용해보자.

(find-if (fint #'signed #'sealed #'delivered) docs)

이렇게 유사한 연산자를 정의하여 predicate집합의 합집합을 반환 할 수 있따.
fun 함수는 fint와 비슷하지만 and 대신에 or를 사용한다.
fun = find-union (이렇게 보면 될듯)

2019년 1월 10일 목요일

[on lisp] 5.3 Memoizing 캐싱,메모

5.3 Memoizing
어떤 함수가 계산하는데 비용이 많이 들고, 때로는 같은 호출을 두 번 이상하는 경우가 있다.
이전의 모든 호출의 반환 값을 캐싱하고 함수가 호출 될 때마다 다음과 같이 memoize하는 것이 좋다.
값이 저장되었는지 확인하려면 먼저 캐시를 살펴보십시오.

그림 5.2는 일반화 된 memoizing 유틸리티이다.
memoize 함수를 제공하고, 이전 호출 결과를 저장하는 해시테이블을 포함하는(closure)를 반환한다.

;; Figure 5.2: Memoizing utility.

;; memoize는 cache라는 해시테이블을 가지는 람다를 던진다.
;; 해당 람다는 구조분해를 한 다음에,
;; gethash의 리턴값은 (value, present-p)임 이걸 (val win)에 각각들어감.
;; (gethash에서 args를 키로 한 값을 가져온다.
;; 값이 없는 경우 setf로 해시에 가져온 키값에 설정한 값을 넣음
;; setf는 넣은 값 리턴으로 보임.
(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args) 
        (multiple-value-bind (val win) (gethash args cache)
          (if win  ;; 값이 있으면
              val  ;; 해당 값 리턴
              (setf (gethash args cache)  
                    (apply fn args))))))) 

     
> (setq slowid (memoize #'(lambda (x) (sleep 5) x)))
Interpreted-Function C38346
> (time (funcall slowid 1))
Elapsed Time = 5.15 seconds
1
> (time (funcall slowid 1))
Elapsed Time = 0.00 seconds
1

memoized 함수를 사용하면, 반복 호출은 해시 테이블 조회 일뿐이다.
물론 초기 호출마다 조회 비용이 추가되지만, 계산하기에 충분히 비싼 함수를 메모하는 것이므로 비용은 비교할 때 중요하지 않다고 가정하는 것이 합리적이다.
대부분의 용도에 적합하지만, memoize의 구현에는 몇 가지 제한이 있다.
이 함수는 동일한 인수 목록이 있으면 동일하게 리턴값이 나와야 한다.
만약 함수에 키워드 파라미터가 있으면 너무 엄격할 수 있다.
또한 단일 값 함수에만 사용되며 여러 값을 저장하거나 반환 할 수 없다.

[on lisp] 5. Returning Functions 함수 리턴(클로저)

5. Returning Functions
이전 장에서는 함수를 인수로 전달하는 기능이 추상화 가능성을 어떻게 증가시키는지 보았다.
우리는 함수로 더 많은 것을 할수록, 우리는 더 많은 가능성을 취할 수 있다.
새로운 함수를 구축하고 새로운 함수를 리턴함으로써, 그리는 함수를 인수로 이용하는 유틸리티의 효과를 확대할 수 있다.

이 장에서 유틸리티는 함수를 실행한다.
커먼리습에서 매크로처럼 표현식에 적용하기 위해 많은 것을 작성하는 것은 자연스러운 것이다.
매크로 계층은 15장의 일부 연산자와 중첩된다. 하지만 우리가 매크로를 통해서만 이러한 함수를 호출할지라도, 함수로 수행할 수 있는 작업의 부부능ㄹ 아는 것은 중요하다.

5.1 Common Lisp Evolves
커먼리습은 본래 몇 쌍의 보완 함수(Complementary functions)를 제공한다.
remove-if, remove-if-not 함수가 이런 한 쌍이다. 만약 pred가 하나의 인수인 predicate(술어)라면

(remove-if-not #'pred lst)
;; 이건 아래와 같다.
(remove-if #'(lambda (x) (not (pred x))) lst)

하나의 인자로 주어진 함수를 다양화함으로써, 우리는 다른 하나의 효과를 복제할 수 있다.
CLTL2에서는 다음과 같은 경우를 위한 새로운 함수를 포함한다.
complement함수는 predicate(술어)p를 취하여 항상 반대값을 반환하는 함수를 반환한다.
p가 true를 반환하면, complement(보수)는 false를 반환하고 그 반대도 마찬가지이다.

(remove-if-not #'pred lst)
;; 아래와 같다.
(remove-if (complement #'pred) lst)

complement함수와 함께라면 if-not함수를 계속 사용할 이유가 없다.
실제로 CLTL(p.391)에서 deprecated 되었다고 말한다. 그들이 커먼리습에 남아있다면 오로지 호환성을 위해서일 것이다.
새로운 complement 연산자는 중요한 빙산의 일각이다. : (함수를 반환하는 함수: functions which return functions)

이것은 오랫동안 Scheme의 관용구에서 중요한 부분이었다.
Scheme은 함수를 lexcial closure로 만드는 첫번째 리스프였고, 리턴 값으로 함수를 가지는 것을 흥미롭게 보았다.
dynamically scoped Lisp가 함수를 반환 할 수 없는 것은 아니다.
아래의 함수는 dynamic이나 lexcial scope 둘다 동일하게 작동한다.

(defun joiner (obj)
  (typecase obj
    (cons #'append)
    (number #'+)))

객체를 취하고, 이것의 타입에 따라 객체를 더하는 함수를 반환한다.
우리는 숫자들이나, 리스트들에 작동하는 join 함수를 다형성을 적용시켜 작동하게 할 수 있을 것이다.

(defun join (&rest args)
  (apply (joiner (car args)) args))

그러나 상수 함수(constant functions)를 반환하는 것은 동적스코프가 수행 할 수 있는 작업의 한계다.
동적스코프가 할 수 없는 것은 런타임에 함수를 빌드하는 것이다.
joiner는 두 가지 함수 중 하나를 반환 할 수 있지만 두 가지 선택으로 고정되어 있다.
이전에 우리는 렉시컬 스코프를 사용하여 함수를 리턴하는 함수를 본 적이 있다.

(defun make-adder (n)
  #'(lambda (x) (+ x n)))

make-adder를 호출하면 인수로 주어진 값에 따라 동작(바뀌는!) 클로저(closure)가 생성된다.

> (setq add3 (make-adder 3))
#Interpreted-Function BF1356
function to add such objects together. We could use it to define a polymorphic join function that worked for numbers or lists: 
(defun join (&rest args)
  (apply (joiner (car args)) args))
However, returning constant functions is the limit of what we can do with dynamic scope. What we can't do (well) is build functions at runtime; joiner can return one of two functions, but the two choices are fixed. 
On page 18 we saw another function for returning functions, which relied on lexical scope: 
(defun make-adder (n)
  #'(lambda (x) (+ x n)))
Calling make-adder will yield a closure whose behavior depends on the value originally given as an argument: 
> (setq add3 (make-adder 3))
#Interpreted-Function BF1356
> (funcall add3 2)
5

렉시컬 소코프(Lexical scope)에서, 단순히 상수 함수 그룹을 선택하는 대신!, 런타임에서 새로운 클로저를 생성할 수 있다.
동적 스코프(Dynamic scope)를 사용하면 이런건 불가능하다.
complement가 어떻게 작성될 것인지를 생각해보면, 이것 역시 closure를 리턴해야 한다는 것을 알 수 있다.

(defun complement (fn)
  #'(lambda (&rest args) (not (apply fn args))))
;; not을 안에 붙여서 함수를 생성 하도록하는데 fn을 머금는 클로저로 함수를 뱉는다. 
;; (이것은 렉시컬 스코프라 가능한 것)

complement에 의해 반환되는 함수는 complement가 호출될 때 변수 fn의 값을 사용한다.
그러므로, 상수 함수 그룹을 선택하는 대신 'complement'는 모든 함수의 역함수를 사용자-정의(custom-build) 할 수 있다.

> (remove-if (complement #'oddp) '(1 2 3 4 5 6))
(1 3 5)

함수를 인수로 전달할 수 있다는 것은 추상화를 위한 강력한 도구입니다.
함수를 반환하는 함수를 작성하는 기능으로 우리는 함수를 최대한 활용할 수 있다.
나머지 절에서는 기능을 리턴하는 유틸리티의 몇 가지 예를 제시한다.