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을 넣을 수 있다.
그리고 주어진 값을 넣으면 링크드인의 자격증명에 보이기 시작한다.

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
리스프 프로그램에서 흔히 볼 수 있는 또 다른 재귀 패턴이 있다. 서브트리의 재귀
이 패턴은 중첩 리스트로 시작하여 car와 cdr을 모두 재귀적으로 사용하려는 경우에 나타남.

lisp 리스트는 다재다능한 구조이다. 리스트는 시퀀스, 세트, 매핑, 배열 및 트리를 나타낼 수 있다.
리스트를 트리로 해석하는 몇 가지 방법이 있다. 가장 보편적인 것은 왼쪽 가지가 car이고 오른쪽 가지가 cdr인 이진 트리로 간주하는 것이다.
;; Figure 5.7: Lists as trees.
(a . b) 
(a b c) 
(a b (c d))
만약 리스트가 아래와 같은 형태로 고려되면 쉽게 해석할 수 있다.
(a b c) = (a . (b . (c . nil))) 
(a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))
어떠한 형태의 리스트도 2진트리로 해석될 수 있다. copy-list와 copy-tree와 같은 공통 리스프 함수의 쌍 간의 구별을 돕는다.
전자는 리스트를 시퀀스로 간주하고 복사한다. 만약 리스트에 서브리스트(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 define flat 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구현체를 봐보자.
(defun our-copy-tree (tree)
  (if (atom tree)
      tree
      (cons (our-copy-tree (car tree))
            (if (cdr tree) (our-copy-tree (cdr tree))))))

[on lisp] 5.2 Orthogonality (직교성)

5.2 Orthogonality (직교성)

An orthogonal language is one in which you can express a lot by combining a small number of operators a lot of different ways.
직교 언어는 많은 다른 방식으로 소수의 연산자를 결합하여 많은 것을 표현할 수 있는 언어이다.

장난감 블록은 서로 직각이다. 플라스틱 모델 키트는 전혀 직각이 아니다.
complement의 가장 큰 장점을 언어를 보다 직관적으로 만든다.
complement 이전, Common Lisp는 remove-if, remove-if-not 혹은 subst-if, subst-if-not 같은 함수 쌍들이 있었다.
이제는 complement를 통해 그들 중 절반이 없어도 일이 가능하다.

setf 매크로 또한 Lisp의 직교성을 향상시킨다.
이전의 Lisp방언은 종종 데이터 읽기와 쓰기를 위한 함수 쌍을 가지고 있었다.
예를들어, property-lists에서는 속성을 설정하는 한 가지 기능과 그 속성에 대해 질의 하는 다른 기능이 있다.
Common Lisp에는 후자만 있다. 속성을 설정하려면 setf와 함께 사용하면 된다.
;; Figure 5.1: Returning destructive equivalents.
(setf (get 'ball 'color) 'red)

(defvar *!equivs* (make-hash-table))

(defun ! (fn)
  (or (gethash fn *!equivs*) fn))  ;; 해시맵에 들어간 함수를 가져온다.

(defun def! (fn fn!) 
  (setf (gethash fn *!equivs*) fn!))  ;; 파괴적인 해시맵을 가져와서 fn의 키값에 fn!를 넣는다.
우리는 Common Lisp를 더 작게 만들지는 못하겠지만, 거의 비슷한 것을 할 수 있다: use a smller subset of it(더 작은 부분 집합을 사용하라)
complement함수와 setf함수 같이 새로운 operator(연산자)를 정의하면 이 목표를 달성하는데 도움이 될까?
기능을 쌍으로 그룹화하는 방법은 적어도 한 가지 더 있다.(반대기능을 하는 걸로 그룹핑하는 것 외에 다른방식으로 그룹핑할 수도 있다.)
remove-if와 delete-if, reverse와 nreverse, append와 nconc와 같이 많은 기능이 파괴적인 버전(desctructive version)을 쌍으로 제공한다.
이렇게 파괴적인,비파괴적인 함수를 대응(쌍)으로 연산자를 정의함으로써, 파괴함수를 직접 참조하지 않아도 된다.

Figure 5.1은 파괴적인 대응(쌍) 개념을 지원하는 코드를 포함하고있다.
일단 *!equivs*는 글로벌 변수이며 (make-hash-table)로 파괴적인 함수에 매핑된다.
느낌표(!)는 파괴적인 동등을 반환한다.
def!는 그것들을 설정한다.
!(bang)연산자의 이름은 Scheme규약에 따온 것인데 !가 사이드이펙트를 생성한다는 것이다.
자 이제 우리가 정의를 해보자.
(def! #'remove-if #'delete-if)
;; 이제 아래처럼 할 필요없이
(delete-if #'oddp lst)
;; 아래처럼 사용한다.
(funcall (! #'remove-if) #'oddp lst)
;; 여기 Common Lisp의 어색함(awkwardness)는 
;; Scheme에서 더 잘 볼 수 있는 생각의 우아함을 숨긴다.
;; 아래가 스킴이 생각하는 무언가인듯. 꽤나 우아하다.
((! remove-if) oddp lst)

특이하게 조립을 한다.
더 큰 직교성 뿐만 아니라, !연산자는 몇 가지 다른 이점을 가지고 있다.
프로그램을 더 선명하게 만든다. 왜냐하면 우리는 즉시 (! #'foo)가 foo와 같지만(여기에는 호출방식도 같고) 파괴적인 것을 볼 수 있다.
또한, 파괴적인 연산자는 소스코드에서 뚜렷하고 인지할 수 있는 형태로 나타나는데,
이것은 우리가 버그를 찾을 때 특별한 주의를 기울여야 하기 때문에 좋다.

function과 destructive counterpart사이의 관계는 일반적으로 런타임 이전에 알려 지므로 정의하는 것이 가장 효율것이다,
'!' 연산자를 정의할 때 매크로로 정의하던가, 혹은 !를 위한 read macro를 제공한다.

2019년 1월 15일 화요일

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

5.5 Recursion on Cdrs
재귀 함수는 lisp에서 매우 중요하기 때문에 이것들 빌드하는 유틸리티가 있어야할 가치가 있다.
이 섹션과 다음 섹션에서는 가장 일반적인 두 가지 유형을 작성하는 함수에 대해 알아보자.
Common Lisp에서 이 함수들을 살짝 어색하게 사용된다.
일단 우리가 매크로의 주제로 들어가게 되면, 우리는 이 기계에 좀 더 우아한 면을 넣는 방법을 알게 될 것이다.
'recursers'를 만드는 매크로는 섹션 15.2, 15.3에서 논의된다.

프로그램에서 반복되는 패턴은 높은 수준의 추상화로 작성될 수 있다는 신호다.
반복되는 패턴은 높은 수준의 추상화로 작성되었을 수 있었다는 신호다.
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))))
구조적으로 이 두 함수는 공통점이 많다.
둘 다 리스트에 cdr를 재귀로 반복 연산을 하고, 동일한 표현식을 각 스텝에 실행한다.
;; Figure 5.5: Function to define flat list recursers.
;; rec 요소별로 실행되어야 할 녀석
;; base 디폴트값.
(defun lrec (rec &optional base)  ;; 함수를 리턴한다.
    (labels ((self (lst)  ;; 재귀함수 이름 self
                   (if (null lst)  ;; lst가 없으면
                       (if (functionp base)  ;; 함수인지 확인하고 실행 후 리턴한다.
                           (funcall base)  ;; 함수실행
                           base)  ;; 그냥 리턴
                           (funcall rec (car lst)  ;; lst의 첫번째를 가져오고 rec를 실행
                                    #'(lambda () ;; 그다음 내용을 함수에 감싼다.
                                              (self (cdr lst)))))))
            #'self))                     
이 패턴은 경험 많은 프로그래머가 생각하기를 멈추지 않고 읽고 사용할 수 있게하는 리스프 프로그램에서 자주보임(?)
패턴을 새로운 추상화에 묶는 방법에 문자는 발생하지 않는다.
하지만 패턴은 모두 동일하다. 이러한 함수를 직접 작성하는 대신 우리를 위해 생성해줄 함수를 작성할 수 있어야 한다.
Figure 5.5는 함수빌더(function-builder)가 있다. lrec("list recurser")
이 빌더는 리스트에서 연속적으로 cdrs를 사용하는데 이렇게 반복되는 부분을 생성할 수 있어야 한다.

lec의 첫번째 인수는 현재 리스트의 car와 두번째 인수는 재귀로 계속 호출 될 수 있는 함수이다.
lrec를 사용하여 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)
lrec의 정의에서는 label를 사용하여 self라는 로컬 재귀 함수를 작성한다.
재귀적일 경우 함수 rec에 두개의 매개변수가 전달된다. 리스트의 현재 car와 재귀 호출을 구현하는 함수를 전달한다.

재귀케이스가 'our-every'와 같은 함수에서 첫번째 인자가 false를 반환하면 바로 그곳에서 멈추고 싶다.
즉, 재귀적일 경우에 전달 된 인수는 값이 아니라 값이어야 하는 함수여야 한다.(값을 원하는 경우)

Figure 4.5는 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.
(defun compose (&rest fns) ;; &rest는 복수의 함수를 매개변수를 받겠다.
    (if fns ;; 함수가 존재한다면
        (let ((fn1 (car (last fns))) ;; 리스트의 마지막 함수 가져오기(compose는 오른쪽부터 합쳐진다)
                   (fns (butlast fns))) ;; 마지막 함수를 제외한 함수 리스트
              #'(lambda (&rest args) ;; fn1 함수가 어떤 매개변수를 받을지 모르니 args로 다 받음
                        (reduce #'funcall fns ;; 하나하나 함수를 누산한다.
                                :from-end t ;; 아 뒤에서 부터 실행하라는 뜻
                                :initial-value (apply fn1 args)))) ;; 첫번째 함수를 초기값으로 실행 
             #'identity)) ;; 함수가 없으면 identity 리턴
              
;; 사용법
(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)
;; 코드리뷰
(defun fif (if then &optional else)
    #'(lambda (x) ; if, then, else를 담은(closure) 람다함수 리턴
              (if (funcall if x) ; if 함수가 참이면
                  (funcall then x) ; then 함수 실행
                  (if else (funcall else x))))) ; else 함수 실행
Figure 5.4는 일반적으로 발생하는 유형의 함수에 대한 몇 가지 다른 생성자를 포함합니다.
두 번째, fint는 다음과 같은 경우입니다.
트루이면 그 상태에서 멈추는 거니까 거기까지만 일을 했다는 것! 특이한 건 그때그때 함수를 실행할 것이겠지?
and이니까 그럴 것이다.(and는 매크로로 보임)
(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를 사용한다.


2019년 1월 10일 목요일

[on lisp] 5.3 Memoizing 캐싱,메모

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


그림 5.2는 일반화 된 memoizing 유틸리티입니다.
memoize 함수를 제공하고, 이전 호출 결과를 저장하는 해시테이블을 포함하는(closure)를 반환한다.
;; Figure 5.2: Memoizing utility.
(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)  ;; 값이 없는 경우 setf로 해시에 가져온 키값에 설정한 값을 넣음
        (apply fn args))))))) ;; setf는 넣은 값 리턴으로 보임.
     
     
> (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)

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

2019년 1월 9일 수요일

[on lisp] 4.8 Density

4.8 Density

만약 당신이 코드가 많은 새로운 유틸리티를 사용한다면, 일부 독자들은 그것이 이해하기 어렵다고 불평할지도 모른다.

아직 Lisp에 능숙하지 않은 사람들은 raw Lisp를 읽는 데만 익숙해질 것이다.
사실 그들은 아직 확장 가능한 언어에 전혀 익숙하지 않을 수도 있다.
그들이 'utility'에 크게 의존하는 프로그램을 볼 때마다
이 언어의 순수한 괴팍함에 작성자가 사적인 언어로 이 프로그램을 쓰기로 결정한 것처럼 보인다.

새로운 연산자(operators)는, 논란이 될 수도 있지만, 프로그램을 읽기 어렵게 만든다.
프로그램을 읽기 전에 그것들을 모두 이해해야 한다.
왜 이런 주장이 잘못되었는지 알기 위해서, 페이지 41을 고려해라.(?? 유틸리티 함수를 만드는 섹션 가라는 말인듯, 왜냐하면 find2가 있음)
만약 당신이 find2를 사용하여 프로그램을 작성했다면, 누군가가 당신의 프로그램을 읽기 전에 이 새로운 유틸리티의 정의를 이해해야 한다고 불평할 수 있다.
글쎄, 만약 당신이 find2를 사용하지 않았다고 가정해보자.
그렇다면, find2의 정의를 이해해야 하는 대신에, 이해해야 할 것이 있을 것이다.
그러면 코드를 읽는 사람은 find2의 기능과 함께 다른 특정한 기능이 있는 함수를 한꺼번에 이해해야 한다.
(서점에서 책을 찾는다 해보면, 서점 도메인에 정의되어 있는 내용과 find2를 한 곳에서 이해해야 한다)
그리고 정확한건 이렇게 섞이면 분리된 것보다 이해하기 어렵다.

그리고 알아야 할 점이 있다.
우리는 지금 예제를 만든 것이기 때문에 새로 만든 유틸리티를 한 번밖에 사용하지 않았따. 유틸리티는 반복적으로 사용하기 위해 만들어진다.
실제 프로그램에서 find2 같은 것과 3~4가지 특수(특정 도메인에만 작동)한 검색 루틴을 이해해야 할 필요가 있을 수 있다.
확실히 전자가 더 쉽다.

그렇다, 상향식-프로그램을 읽으려면 저자에 의해 정의된 모든 새로운 연산자(operator)를 이해해야 한다.
그러나 이거 없이 요구를 충족하며 만들어진 모든 코드를 이해해야 하는 것보다 더 적은 작업일 것이다.

만약 사람들이 '유틸리티'를 사용하면 코드를 읽기가 어렵게 만든다고 불평한다면, 코드를 사용하지 않았다면 어떻게 보일지 알지 못한 것이다.
상향식-프로그래밍은 큰 프로그램인 거와 달리, 작고 심플하게 보이게 한다.
이것은 프로그램이 별로 일을 하지 않는다는 인상을 주고 그것은 읽기 쉽게 보일 수 있다.
경험없는 독자가 더 가까이에서 보았을 때, 이것이 그렇지 않다는 것을 알게되면, 그들은 충격을 받는다.

우리는 다른 분야에서도 동일한 현상을 발견한다. 잘 설계된 기계는 부품을 더적게 차지할 수 있지만, 더 작은 공간에 포장되기 때문에 더 복잡해 보인다.
상향식 프로그램은 개념적으로 밀도가 높다. 그것들을 읽으려면 노력이 필요할지도 모르지만, 상향식으로 짜여지지 않은 것들 만큼은 아니다.

유틸리티 사용을 의도적으로 피할 수 있는 경우가 있다: 작은 프로그램을 짜서 독립적으로 나머지 코드에 배포되야할 녀석입니다.
유틸리티는 일반적으로 2~3회 사용후 자체적으로 비용을 지불하지만(2,3회 쓰이면 괜찮음 만들라) 작은 프로그램에서 유틸리티를 만들어 작성해봤자
그걸 여러번 얼마나 쓸지 장담할 수 없으니 정당화 될 수 없다.

[on lisp] 4.7 Symbols and Strings 심볼과 문자열 사이

4.7 Symbols and Strings
심볼과 문자열은 밀접한 관련이 있다.

reading,printing 함수에 따라 우리는 두 표현을 왔다갔다 할 수 있다.
Figure 4.8은 이 경계에서 작동하는 유틸리티 함수의 예를 보여준다.
;; Figure 4.8: Functions which operate on symbols and strings.
(defun mkstr (&rest args)
  (with-output-to-string (s)
    (dolist (a args) (princ a s))))

(defun symb (&rest args)
  (values (intern (apply #'mkstr args))))

(defun reread (&rest args)
  (values (read-from-string (apply #'mkstr args))))

(defun explode (sym)
  (map 'list #'(lambda (c)
           (intern (make-string 1
                   :initial-element c)))
             (symbol-name sym)))
첫번째 mkstr 함수는 많은 수의 인수를 취하여 출력된 표현을 문자열로 묶는다.
> (mkstr pi " pieces of " 'pi)
"3.1415926535897932385L0 peices of PI"
출력가능한 표현을 할 수 있는 아무 객체가 가능하다. : symbols, strings, numbers even lists
> (mkstr pi " pieces of " 'pi)
> (symb 'ar "Madi" #\L #\L 0)
|ARMadiLL0|
mkstr로 모든 인수들을 묶으라고 한 후, symb는 그 결과 문자열을 intern에게 보낸다.
intern 함수는 Lisp의 전통적인 기호제작자(symbol-builder): 문자열을 받아 그 문자열을 인쇄하는 심볼을 찾거나 새로운 심볼을 생성한다.

모든 문자열은 심볼의 출력이름(print-name)이 될 수 있으며, 심지어 소문자나 매크로 문자(괄호)같은 것들도 포함된다.
심볼이름이 이런 기괴한 것들이 포함되어 있을 경우, 아래와 같이 수직 막대 내에서 출력된다.
> (let ((s (symb '(a b))))
(and (eq s '|(A B)|) (eq s '\(A\ B\))))
T

reread는 symb의 일반화이다. 여러 객체를 한번에 받아 출력하고 다시 읽는다.
symb와 같이 심볼을 리턴할 수 있지만 읽을 수 있는 다른 무언가를 리턴할 수도 있다.

Read-macro는 심볼의 이름의 일부로 취급되는 대신, (예를들어)|a:b|를 보면 현재 패키지 안에 |a:b|라는 심볼을 찾는 것이 아니라.
|a:b|는 a 패키지 안에 b라고 읽어진다. 또한 보다 일반적인 함수는 더 까다롭다. 'reread'는 해당 Lisp구분이 적절하지 않으면 에러를 생성한다.

마지막 함수 explode는 함수를 받아서 심볼 리스트를 반환한다.
> (explode 'bomb)
(B O M B)

2019년 1월 8일 화요일

[on lisp] 4.6 I/O 입출력

4.6 I/O
Figure 4.7은 I/O 유틸리티의 세 가지 예를 보여준다.
이러한 유틸리티의 필요성은 프로그램마다 다르다.
;; Figure 4.7: I/O functions.
(defun readlist (&rest args)
  (values (read-from-string
       (concatenate 'string "(" 
                         (apply #'read-line args)
                      ")"))))

(defun prompt (&rest args)
  (apply #'format *query-io* args)
  (read *query-io*))     

(defun break-loop (fn quit &rest args)
  (format *query-io* "Entering break-loop.~%")
  (loop
    (let ((in (apply #'prompt args)))
      (if (funcall quit in)
       (return)
          (format *query-io* "~A~%" (funcall fn in))))))
여기 4.7은 대표적인 샘플일 뿐이다. 첫 번째는 사용자가 괄호없이 표현식을 입력 할 수 있게 하려는 경우다.
입력 행(a line of input)을 읽고 그것을 리스트로 리턴한다.

>(readlist)
Call me "Ed"
(CALL ME "Ed")
값을 호출하면 하나의 값만 반환.

prompt 함수는 질문, 읽기, 대답을 결합한다.
> (prompt "Enter a number between ~A and ~A.~%>> " 1 10)
Enter a number between 1 and 10.
>> 3
3

마지막으로 break-loop는 리습의 toplevel(REPL같은거)을 모방한 것이다.
두 개의 함수과 &rest 인수를 취하여, 프롬프트에 반복적으로 제공된다.
두 번째 함수가 입력에 대해 false를 반환하면 첫 번째 함수가 입력에 적용된다.
> (break-loop #'eval #'(lambda (x) (eq x :q)) ">> ")
Entering break-loop.
>> (+ 2 3)
5
>> :q
:Q
이것이 커먼리습 벤더들이 일반적으로 런타임 라이센스를 주장하는 이유이다.
만약 eval을 런타임에 실행할 수 있는 경우, 어떤 Lisp프로그램에도 Lisp가 포함될 수 있다.
(If you can call eval at runtime, then any Lisp program can include Lisp.)

[on lisp] 4.5 Mapping 매핑

4.5 Mapping
리습에서 또 널리 사용되는 녀석들이 있다. 이걸 매핑 함수라고 한다. 일련의 인수(시퀀스)에 함수를 적용시키는 함수다.
Figure 4.6은 새로운 매핑 함수의 몇가지 예를 보여준다.

(defun map0-n (fn n)
  (mapa-b fn 0 n))
  
(defun map1-n (fn n)
  (mapa-b fn 1 n))

(defun mapa-b (fn a b &optional (step 1))
  (do ((i a (+ i step))
       (result nil))
      ((> i b) (nreverse result))
   (push (funcall fn i) result)))

(defun map-> (fn start test-fn succ-fn)
  (do ((i start (funcall succ-fn i))
       (result nil))
      ((funcall test-fn i) (nreverse result))
    (push (funcall fn i) result)))
 
(defun mappend (fn &rest lsts)
  (apply #'append (apply #'mapcar fn lsts)))

(defun mapcars (fn &rest lsts)
  (let ((result nil))
    (dolist (lst lsts)
   (dolist (obj lst)
     (push (funcall fn obj) result)))
 (nreverse result)))

(defun rmapcar (fn &rest args)
  (if (some #'atom args)
      (apply fn args)
   (apply #'mapcar
          #'(lambda (&rest args)
              (apply #'rmapcar fn args))
    args)))
하... 보기만 해도 머리가 지끈하다. 하나하나 봐보자.
처음 세개의 함수는 편하게 사용하기 위해 만든 것인가보다.
(The first three are for applying a function to a range of numbers without having to cons up a list to contain them.)
보아하니 매개변수로 넘겨주기 귀찮아서, 0부터 n까지의 range를 매개변수로 줄 때 사용한다는 것 같다.
잘 보면 map0-n는 0부터 n까지 map1-n는 1부터 n까지임을 확인할 수 있다.
> (map0-n #'1+ 5)
(1 2 3 4 5 6)
> (map1-n #'1+ 5)
(2 3 4 5 6)
이 주 map0-n과 map1-n는 사실 mapa-b를 이용하여 숫자 범위가 만들어지고 있다.
> (mapa-b #'1+ -2 0 .5) ;; -2부터 0까지 .5 단위로 커지는 range
(-1 -0.5 0.0 0.5 1.0)

;; 코드구경
(defun mapa-b (fn a b &optional (step 1))
  (do ((i a (+ i step))  ;; do (i::인덱스 a::시작점 (+ i step)::업데이트
       (result nil))     ;; 끝나면 리턴할 녀석 nil은 초기값
      ((> i b) (nreverse result)) ;; 시작할 index의 값이 b(마지막)값보다 크면 반대로 돌아야 하니까 result를 nreverse
   (push (funcall fn i) result)))  ;; result 값에 반복문 돌면서 함수 실행후 result에 넣음.
mapa-b보다 더 일반적인 map->가 있다. 이 매핑은 숫자만이 아닌 모든 종류의 객체 시퀀스에 사용할 수 있다.
(defun map-> (fn start test-fn succ-fn)
  (do ((i start (funcall succ-fn i)) ;; succ-fn로 인덱스를 바꿈
       (result nil)) ;; 리턴값
      ((funcall test-fn i) (nreverse result)) ;; test-fn로 끝났는지 확인하고 result 리턴
    (push (funcall fn i) result))) ;; result에 fn를 실행하여 넣는다.
보면 알겠지만 인덱싱을 하던 i가 꼭 숫자일 필요조차 없다. 업데이트나 터미널인지 확인하는 것도 따로 함수를 넣는다.
그렇다면 mapa-b또한 이 유틸리티 함수를 이용하여 재구현해보자.
(defun mapa-b (fn a b &optional (step 1))
  (map-> fn  ;; 요소별로 실행할 함수
         a   ;; 시작숫자
   #'(lambda (x) (> x b))  ;; 끝날 숫자 확인 
   #'(lambda (x) (+ x step)))  ;; 인덱스 업데이트 방법
효율성을 위하여, 빌트인 mapcan함수는 파괴적이다(수정을한다).
(defun our-mapcan (fn &rest lsts)
  (apply #'nconc (apply #'mapcar fn lsts)))
mapcan은 nconc와 함께 리스트를 연결하기 때문에, 첫번째 인수에서 리턴된 리스트를 새로 만들거나, 다음에 변경할 때 해당 리스트가 변경될 수 있다.
단순히 다른 곳에 저장된 리스트을 반환했다면 mapcan을 사용하는 것은 안전하지 않았을 것이다.
대신 우리는 리턴된 리스트를 append로 연결해야 했다. 이러한 경우 mappend는 비파괴적인 mapcan의 대안을 제공한다.

다음 유틸리티, mapcars 함수,는 여러 목록에 함수를 매핑하는 경우사용된다.
우리에게 두 개의 숫자리스트가 있고, 제곱근의 단일 리스트를 얻고 싶다면?
(mapcar #'sqrt (append list1 list2))
하지만 여기서 실행되는 conses는 불필요한 일이다. 우리는 list1, list2를 append하여 즉시 결과를 폐기한다.
mapcars를 사용하면 다음과 같은 결과를 어등ㄹ 수 있다.
(mapcars #'sqrt list1 list2)

;; 코드를 보자.
(defun mapcars (fn &rest lsts)
  (let ((result nil)) ;; 일단 리턴할 result를 nil로
    (dolist (lst lsts) ;; lsts를 lst란 이름으로 순회
   (dolist (obj lst)  ;; lst를 obj란 이름으로 순회
     (push (funcall fn obj) result)))  ;; funcall로 fn에 obj를 넣어서 실행 후 result에 push
 (nreverse result)))  ;; 뒤집어서 던짐.
이러면 우리는 매개변수를 던질때 굳이 cons를 하여 던질 필요가 없다.

Figure4.6의 마지막 함수는 tree를 위한 mapcar다.
rmapcar는 "recursive mapcar"의 줄인말이다. mapcar는 평평한 리스트에서 작동하며, 이녀석은 tree에서 작동한다.
(rmapcar #'princ '(1 2 (3 4 (5) 6) 7 (8 9))) 
123456789
(1 2 (3 4 (5) 6) 7 (8 9))

> (rmapcar #'+ '(1 (2 (3) 4)) '(10 (20 (30) 40)))
(11 (22 (33) 44))


;; 코드구경
(defun rmapcar (fn &rest args)  ;; args가 트리 (&rest인걸보니 여러개 들어올 수 있음)
  (if (some #'atom args)  ;; 하나만 들어왔다면
      (apply fn args)  ;; 바로 하나만 실행해버림
   (apply #'mapcar  ;; 아니라면 mapcar 실행
          #'(lambda (&rest args)
              (apply #'rmapcar fn args))  ;; 재귀를 실행할 람다 생성
    args)))  ;; apply는 마지막 매개변수가 list여야 한다. 이 list들은 추가적인 매개변수들로 적용된다.
;; http://n-a-n-o.com/lisp/cmucl-tutorials/LISP-tutorial-20.html apply 내용출처

나중에 이것들을 실제로 쓸 것이다.
CLTL2에서 소개된 새로운 시리즈의 매크로들은 기존의 리스트 매핑 기능을 어느 정도 쓸모없게 만들었따.
(mapa-b #'fn a b c)
이녀석은 아래처럼 바뀐다.
(collect (#Mfn (scan-range :from a :upto b :by c)))
뭐야 Mfn는 모나드를 말하는 건가?
뭐 여튼 이런게 있다고 한다.

2019년 1월 7일 월요일

[on lisp] 4.4 Search 탐색

4.4 Search

이 절에는 리스트를 탐색하는 함수의 몇 가지 예가 수록되어있다.
커먼리습은 이것을 위해 풍부한 빌트인 연산자를 제공하지만, 일분 작업들은 여전히 어렵거나, 적어도 효율적으로 수행하기 어렵다.

일단 우리는 그 전에 리스트 안에 리스트들을 모두 순회하는 함수들을 알아보자. 이전에는 최상위 리스트 (1차원)만을 매개변수로 받았지만
이번에는 다르다. 아래처럼 실행이 될 것이다.
flatten은 평평하게 만드는 것이고, prune(가지치다) evenp인 녀석은 없애버린다.
> (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))
유틸리티 코드의 소스를 보자.
Figure 4.3: Doubly-recursive list utilities.

(defun flatten (x)
  (labels ((rec (x acc)
  (cond ((null x) acc)  ;; x가 끝나면 acc리턴
        ((atom x) (cons x acc))  ;; x가 cons가 아닌 요소 하나라면 acc와 cons로 합침. 그리고 리턴
        (t (rec (car x) (rec (cdr x) acc))))))  ;; 나머지: 나머지요소와 acc를 마저 재귀돌리고 다 돌리면 첫번째 요소와 합친다.
    (rec x nil)))  ;; acc 는 nil로 시작한다.
;; 보면 알겠지만 안으로 계속 들어가면서 car으로 빼내서 acc에 계속 더한다.

(defun prune (test tree)
  (labels ((rec (tree acc)
  (cond ((null tree) (nreverse acc)) ;; 1. tree가 더이상 없다면 리턴
        ((consp (car tree))  ;; 2. tree가 cons다 더 있다.
         (rec (cdr tree)  ;; 2.2 나머지 트리를 남겨서 재귀를 돌림.
       (cons (rec (car tree) nil) acc))) ;; 2.1 하나짜리는 따로 (rec (car tree) nil) 로 보내서 (funcall test...) 에 들어가도록 하여 테스트를 진행한다. 
        (t (rec (cdr tree)
         (if (funcall test (car tree))
      acc  ;; 테스트에 맞으면 누산기 리턴
    (cons (car tree) acc))))))) ;; 틀리면 누산기에 더해서 리턴
    (rec tree nil)))

이제 다음 유틸리티 소스들을 구경해보자.
before함수는 리스트에서 한 개체가 다른 개체보다 먼저 발견되는지 여부를 알려준다.
> (before 'b 'd '(a b c d))
(B C D)  ;; b가 d앞에 있는지

;; 아래처럼 적당히 얼버무려서 raw Lisp로 풀 수도 있다.
> (< (position 'b '(a b c d)) (position 'd '(a b c d)))
하지만 뒤에 코드는 비효율적이며 에러가 나기 쉽다. 비효율적인 이유: 우리는 두 객체를 모두 찾을 필요가 없다. 둘 다 순회하다가 한놈만 찾으면 게임은 끝난다. 에러나기 쉬운 이유: 만약 객체가 리스트가 아닌 경우, nil이 '<'계산을 위한 매개변수로 들어올 것이다. before의 특이한 점은 옵셔널 값이 있다는 점이다. 그래서 값이 없으면 기본값으로 비교를 하고 커스텀을 하려면 다른 함수를 넣으면 된다. 이 녀석은 test라는 이름에 매핑된다.
(defun find2 (fn lst)
  (if (null lst)
    nil
    (let ((val (funcall fn (car lst))))
      (if val
     (values (car lst) val)
     (find2 fn (cdr lst))))))

(defun before (x y lst &key (test #'eql))
  (and lst
    (let ((first (car lst)))
   (cond ((funcall test y first) nil)
         ((funcall test x first) lst)
         (t (before x y (cdr lst) :test test))))))
     
(defun after (x y lst &key (test #'eql))
  (let ((rest (before y x lst :test test)))
    (and rest (member x rest :test test))))

;; :test -- a designator for a function of two arguments that returns a generalized boolean.
(defun duplicate (obj lst &key (test #'eql))
  (member obj (cdr (member obj lst :test test)) 
   :test test))

(defun split-if (fn lst)
  (let ((acc nil))
    (do ((src lst (cdr src)))
 ((or (null src) (funcall fn (car src)))
  (values (nreverse acc) src))
      (push (car src) acc))))
before에 첫번째 인수가 두번째 인수보다 먼저 나오면 참이다. (원래 그러려고 만든거다)
즉, 두번째 인수가 리스트에서 전혀 보이지 않아도 참이다.
> (before 'a 'b '(a))
(A)
after를 호출하면 정확히 알 수 있다. 이 테스트에서는 두 인수가 모두 리스트안에 있어야 한다.
일단 이걸 이해하려면 member에 대해 알아야 한다. 아래처럼 동작한다.
(member 2 '(1 2 3)) ; (2 3)
(member 2 '((1 . 2) (3 . 4)) :test-not #'= :key #'cdr) ; ((3 . 4))

> (after 'a 'b '(b a d))
(A D)
> (after 'a 'b '(a))
NIL
duplicate함수는 중복되는 것이 생기면 그곳에서 멈추고 cons를 뱉는다. 그러면 뒤에 연결된 아이들도 보일 것이다.

좀 더 까다로운 언어 디자이너들은 Common Lisp가 거짓과 빈 리스트를 모두 나타내기 위해 nil을 사용한다는 것에 충격을 받는다.
때로는 문제를 일으키기도 하지만(14.2 참조, 나중에 보자), 중복과 같은 기능에서 편리하다.

마지막의 member함수는 어떤 조건에 따라 리스트를 나눈다.
> (split-if #'(lambda (x) (> x 4)) '(1 2 3 4 5 6 7 8 9 10))
(1 2 3 4)
(5 6 7 8 9 10)
리턴이 2개가 되고 하나를 출력하려 하면 첫번째 것만 보인다.


Figure4.4를 넘어가서 Figure4.5 를 보자.
;; Figure 4.5: Search functions which compare elements.
(defun most (fn lst)
  (if (null lst)
    (values nil nil)
    (let* ((wins (car lst))
        (max (funcall fn wins)))
      (dolist (obj (cdr lst))
     (let ((score (funcall fn obj)))
       (when (> score max)
         (setq wins obj
            max score))))
      (values wins max))))

(defun best (fn lst)
  (if (null lst)
    nil
    (let ((wins (car lst)))
      (dolist (obj (cdr lst))
     (if (funcall fn obj wins)
       (setq wins obj)))
      wins)))

(defun mostn (fn lst)
  (if (null lst)
      (values nil nil)
    (let ((result (list (car lst)))
       (max (funcall fn (car lst))))
      (dolist (obj (cdr lst))
     (let ((score (funcall fn obj)))
     (cond ((> score max)
            (setq max score
                  result (list obj)))
        ((= score max)
            (push obj result)))))
      (values (nreverse result) max))))
Figure4.5 에는 다른 종류의 검색 기능을 포함한다.

첫번째, most함수, 한 번에 하나의 요소만 확인한다. 리스트와 점수를 매길함수를 주면, 가장큰 스코어를 낸 요소를 리턴한다.
아래 테스트에서는 중복된 값이 있으면 먼저된 녀석이 리턴된다.
> (most #'length '((a b) (a b c) (a) (e f g)))
(A B C)
3

;; 코드를 구경하자.
(defun most (fn lst)
  (if (null lst)  ;; lst가 없으면, nil nil을 뱉는다.
      (values nil nil)
    (let* ((wins (car lst))     ;; lst의 첫번째를 뽑는다.
    (max (funcall fn wins)))   ;; 첫번째의 값을 점수매겨서 max에 넣어본다.
      (dolist (obj (cdr lst))     ;; lst의 나머지를 반복문 돌린다.
     (let ((score (funcall fn obj)))  ;; 나머지 값 하나하나를 점수 매긴다.(score)
       (when (> score max)     ;; 만약 max보다 score가 크면
         (setq wins obj        ;; wins에는 큰 녀석의 요소와
            max score))))   ;; max에는 score값는 넣는다.
      (values wins max))))        ;; 끝나면 리턴한다.

좀 더 일반적인 검색은 best에서 보여주고 있다.
이 유틸리티는 함수와 리스트를 받는다. 그런데 여기서 함수는 꼭 두개의 인수를 받는 predicate이어야 한다.
이 predicate으로 나머지를 이긴 녀석을 리턴한다.
> (best #'> '(1 2 3 4 5))
5

;;역시 코드를 파보자.
(defun best (fn lst)
  (if (null lst)  ;; 없으면 nil
    nil
    (let ((wins (car lst)))  ;; lst의 첫번째 값을 일단 받아서 시작할 거다.
      (dolist (obj (cdr lst))  ;; lst의 나머지를 obj라는 요소에 하나하나 담아서 반복문 실행
     (if (funcall fn obj wins)  ;; fn(predicate)에 obj,wins를 넣어서
       (setq wins obj)))  ;; 트루면 값을 바꾼다.
      wins)))  ;; 이긴놈을 리턴한다.

마지막으로 mostn을 보자.
함수와 리스트를 받아서 가장큰 스코어를 가진 요소들을 리스트로 리턴한다.
> (mostn #'length '((a b) (a b c) (a) (e f g)))
((A B C) (E F G))

;; 코드구경
(defun mostn (fn lst)
  (if (null lst)  ;; 없으면 nil
      (values nil nil)
    (let ((result (list (car lst)))  ;; 첫번째 값을 리스트로 감쌈
       (max (funcall fn (car lst)))) ;; 첫번째 값의 점수를 매기고 그걸 임시로 max에 넣음
      (dolist (obj (cdr lst))  ;; 나머지부터 dolist로 실행 
     (let ((score (funcall fn obj)))  ;; 요소를 점수매겨 score에 넣음
     (cond ((> score max)  ;; score가 max보다 크면
            (setq max score  ;; max를 score로 대체
                  result (list obj)))  ;; result를 (list obj)로 대체
        ((= score max)  ;; score == max 면
            (push obj result)))))  ;; result에 값을 추가.
      (values (nreverse result) max))))

[on lisp] 4.3 Operations on Lists 리스트 연산자

4.3 Operations on Lists

"Lisp"는 "List Processing"이라는 유래처럼 list는 lisp의 메인 자료구조이다.
그러나 이 역사설 사실에 현혹되지 말자. Polo셔츠가 Polo를 위한 것이 아닌 것처럼 고도로 최적화된 Common Lisp프로그램에서 리스트는 더이상 볼 수 없다.

적어도 컴파일 타임에는 여전히 리스트일 것이다.
가장 정교한 프로그램(리스트를 런타임에 적게 사용하는 것)은 매크로 확장을 생성할 때 컴파일 시간에 (줄어든 런타임시간에 비례하여) 더 많이 사용한다.
그러므로 비록 현대 방언에서 리스트의 역할이 줄어들지라도, 리스트 연산은 여전히 리습에서 큰 부분을 차지한다.
;; Figure 4.1: Small functions which operate on lists.
(proclaim '(inline last1 single append1 conc1 mklist))

(defun last1 (lst)
  (car (last lst)))

(defun single (lst)
  (and (consp lst) (not (cdr lst))))

(defun append1 (lst obj)
  (append lst (list obj)))

(defun conc1 (lst obj)
  (nconc lst (list obj)))

(defun mklist (obj)
  (if (listp obj) obj (list obj)))
첫번째로 last1, 리스트의 마지막 요소를 반환한다. 빌트인 함수는 마지막 요소가 아니라 목록의 마지막 cons를 반환한다.
대부분의 경우 마지막 요소를 얻기 위해 (car (last ...))를 사용한다. 그런 경우를 위해 새로운 유틸리티를 쓸 가치가 잇는가?
있다!, 빌트인 연산자 중 하나를 효과적으로 대체할 수 있다면 그렇다!
last은 오류 검사를 하지 않는다. 일반적으로 이 책의 코드는 오류검사를 하지 않는다. 부분적으로 이것이 예제를 더 명확하게 만든다.
그리고 짧은 유틸리티의 경우 오류 검사를 하지 않는 것이 합리적이다. 만약 아래와 같은 문제를 만났다 하자.
> (last1 "blub")
>>Error: "blub" is not a list.
Broken at LAST...
에러는 last에서 잡힐 것이다. 유틸리티가 작을 때, 추상화된 레이어가 너무 얇아서 투명 해지기까지 한다.
얇은 얼음층을 통해 그 밑에 일어난 일을 알 수 있듯이, last1같은 유틸리티 또한 그 밑에 있는 함수에서 발생하는 오류를 보는데 문제가 없다.


함수 single은 리스트의 요소가 하나인지 아닌지를 확인한다.
리습 프로그램에선 이 테스트를 꽤 자주 할 필요가 있다. 아래처럼 쓰다보나, 처음에는 영어로 된 자연스러운 벙역으로 바꾸고 싶었을 것이다.
(= (length lst) 1)
이런 식으로 쓰여 있으면, 이 테스트는 아주 비효율적일 것이다.
우리는 첫 번째 요소를 지나치자마자 이것이 하나만 있는지 아닌지 알 수 있다. 그런데 length를 쓰다니? 아주 비효율적이다. single이 훨씬 낫다.

다음으로 append1과 conc1이다.
둘다 새로운 요소를 리스트 마지막에 붙인다. conc1는 파괴적으로 (수정한다는 말)
이러한 함수는 아주 작지만 자주 필요하기 때문에 정의할 가치가 있다. 실제로, append1은 이전의 lisp방언에 미리 정의되어 있다.

(적어도) Interlisp에는 미리 정의되어 있는 mklist라는 것도 있다.
이녀석은 어떤 것이 정말로 list인지 확인한다. 많은 리습 함수는 단일 값 또는 리스트로 반환하기 위해 작성된다.
그런데 이 모든 것들을 리스트로 반환하도록 하는 것이다. (괜찮다)

만약에 lookup이라는 함수가 있다고 하자. 데이터라고 불리는 리스트의 모든 요소에 대해 조회를 호출하여 결과를 수집한다고 하자.
우린 다음처럼 쓸 것이다.
(mapcan #'(lambda (d) (mklist (lookup d)))
 data)
이러면 전부 리스트로 반환되서 수집될 것이다.

좀 더 긴 예제를 둘러보자.
;; Figure 4.2: Larger functions that operate on lists.
(defun longer (x y)
  (labels ((compare (x y)
      (and (consp x)
    (or (null y)
        (compare (cdr x) (cdr y))))))
    (if (and (listp x) (listp y))
 (compare x y)
      (> (length x) (length y)))))

(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
 (if val (push val acc))))
    (nreverse acc)))

(defun group (source n)
  (if (zerop n) (error "zero length"))
  (labels ((rec (source acc)
  (let ((rest (nthcdr n source)))
    (if (consp rest)
        (rec rest (cons (subseq source 0 n) acc))
      (nreverse (cons source acc))))))
    (if source (rec source nil) nil)))
그림 4.2에서는 좀 더 큰 리스트 유틸리티의 예제가 주어졌다.

첫 번째는, longer 함수, 추상화뿐만 아니라 효율성의 관점에서도 유용하다.
두 시퀀스를 비교하여 더 길 경우에 참을 리턴한다.
우리가 두 리스트를 비교할 때, 아래처럼 적는 경우가 있다.
(> (length x) (length y))
위 코드는 두 리스트의 전체 길이를 전부 순회해야 하기 때문에 비효율적이다.
한 리스트가 다른 리스트보다 훨씬 더 길다면, 그 길이의 차이를 건너는 만큼 그 노력이 낭비가 될 것이다.
병렬로 두개의 리스트가 넘어가면서 비교하는 것이 더 빠르다.
longer 안에는 재귀가 실행되고 있다. compare라는 lambda가 labels로 이름 붙여져 있다.
이녀석으로 하나하나 비교하고 재귀로 그 다음 요소를 비교한다.
longer함수는 길이를 비교하는 함수이기 때문에, 길이를 인수로 줄 수 있는 모든 것에 대해 작동해야 한다.
하지만 길이를 병렬로 비교할 수 있는 녀석은 리스트인 경우에만 적용된다. 내부 함수(internal function)는 두 인수가 모두 목록인 경우에만 호출된다.

다음 함수, filter를 알아보자.

빌트인 remove-if-not은 연속적인 cdrs에서 동일한 기능을 가진 find-if를 호출했을 때 반환될 수 있는 모든 값을 반환하지 않는다.
이와 유사하게 필터는 목록의 연속 cdrs에 대해 일부 반환된 것을 반환한다.
(remove-if-not #'evenp '(1 2 3 4 5 6))
;; (2 4 6)

(filter #'(lambda (x) (if (numberp x) (1+ x))) '(a 1 2 b 3 c d 4))
; (2 3 4 5)
filter함수에게 함수와 리스트를 주면, 매개변수로 받는 함수가 리스트의 요소 하나하나에 적용되면서 그 값이 non-nil이 아닌 것들의 리스트를 리턴받는다.
filter함수는 섹션2.8에서본 "tail-recursive functions"가 사용한 누산기(acccumulator)를 사용하고 있다는 것을 유의하자.
잠깐 2.8을 구경해보자.
;; 2.8 Tail Recursion
(defun our-length (lst)
  (labels ((rec (lst acc)
  (if (null lst)
      acc
    (rec (cdr lst) (1+ acc)))))
    (rec lst 0)))
사실, tail-recursive한 함수를 작성하는 목적은 컴파일러가 filter 형태의 코드를 생성하도록 하는 것이다.
필터의 경우, 간단한 반복 정의는 꼬리 재현보다 더 간단하다.
필터의 정의에서 push와 nreverse의 조합은 리스트를 누적하는(accumulate) 표준 lisp 관용구이다.
코드를 자세히 봐보자. filter 코드에는 신기하게 재귀가 없다.
컴파일러는 이렇게 변경을 시도 한다는 것 같다.
누산기 acc를 정의하고, dolist를 이용하여 lst의 요소들을 순회한다.
funcall을 이용하여 요소(x) 하나하나를 순회하여 실행하여 val로 지정하고,
if 문으로 val이 non-nil인지 확인 하면 누산기 acc에 push한다.
그리고 뒤집는다. nreverse는 값을 파괴적으로 뒤집는다. 꽤나 빠르게
(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
 (if val (push val acc))))
    (nreverse acc)))

Figure 4.2의 마지막 함수를 보자. group함수는 리스트를 그룹핑하여 서브리스트에 넣는것이다.
group함수에게 리스트 l과 숫자n을 보내면, l의 요소가 길이 n의 서브리스트로 분류된 새로운 리스트가 반환된다.
나머지는 마지막 서브리스트에 들어간다.
따라서 두 번째 인수로 2를 지정하면 다음과 같은 목록이 나온다.
> (group '(a b c d e f g) 2)
((A B) (C D) (E F) (G))
이 함수는 tail-recursive한 함수를 만들기 위해 다소 복잡한 방식으로 짜졌다.
신속한 프로토타이핑의 원칙은(The principle of rapid prototyping)은 개별 기능뿐만 아니라 전체 프로그램에도 적용된다.
flatten같은 함수를 작성할 때 가장 간단한 구현으로 시작하는 것이 좋다.
그 다음, 간단한 버전이 작동하면 필요에 따라 효율적인 tail-recursive나 iterative 버전으로 바꿀수 있다.
만약 초기 버전으로 충분하다면, 초기 버전은 그것의 행위를 코멘트로 남겨놓아야 하며, 이것이 무엇을 대체하는 행위인지 코멘트를 남겨야 한다.

group의 정의는 하나 이상의 오류를 검사한다는 점에서 일반적이지 않다. 이렇게 체크하지 않으면 두번째 인수에 0이 오면 무한 재귀로 보내버린다.

어떤 면에서, 이 책의 예들은 일반적인 Lisp 예제와 다르다. 각장을 서로 독립적으로 만들기 위해서, 코드의 예들은 가능한 한 원시 Lisp로 쓰여졌다.
group 함수는 매크로를 정의하는데 매우 유용하기 때문에 이후 여러 장에서 다시 나타난다.
나가기전에 group을 파해쳐보자.
(defun group (source n)
  (if (zerop n) (error "zero length"))  ;; 1. 길이 0이면 끝
  (labels ((rec (source acc)
  (let ((rest (nthcdr n source)))  ;; 자르고 남은 뒷부분을 rest로 
    (if (consp rest)  ;; rest가 cons인지 확인 
        (rec rest (cons (subseq source 0 n) acc))  ;; acc(누산기)에 앞에 자른 n개의 그룹을 cons로 더한다. 그리고 rest와 acc를 재귀돌린다.
      (nreverse (cons source acc))))))  ;; 마지막에 파괴적인 reverse로 반대로 리턴
    (if source (rec source nil) nil)))  ;; 2. source가 없으면 nil

;; cons와 nreverse를 좀 더 확인해보자.
(cons '(1 2 3) '((a b c)))
; ((1 2 3) (A B C))
(nreverse (cons '(1 2 3) '((a b c))))
; ((A B C) (1 2 3))

2019년 1월 6일 일요일

[on lisp] 4.2 Invest in Abstraction (추상화에 투자)

4.2 Invest in Abstraction (추상화에 투자)

간결함이 지혜 영혼이라면, 그것은 효율성과 함께 좋은 소프트웨어의 본질이다.

프로그램의 작성,유지보수의 비용은 그 길이에 따라 증가한다.
만약 다른 부분이 동일하다면, 프로그램은 짧은 수록 좋다.

이런 관점에서 보면, 유틸리티의 작성은 자본지출로 간주되어야 한다.
find-books를 유틸리지 find2로 교체함으로써, 우리는 많은 코드 라인을 직면하게 된다.

하지만 우리는 더 짧게 만들었다고 말할 수도 있게 되는데, 유틸리티 코드의 길이는 현재 프로그램에 자본지출로 부과되지 않을 것이다.
(왜냐하면 범용적이기 때문이라고 생각함)
이것은 단순히 Lisp의 확장을 자본지출로 취급하는 것은 단지 회계속임수가 아니다.
유틸리티들은 다른 파일로 분리될 수 있다. 이것들은 우리가 프로그램 작업을 할 때, 우리의 시각을 혼란스럽게 만들지 않을 것이고,
우리가 나중에 돌아와서 프로그램의 어떤 곳을 변경하려 할 때, 참여하지 않을 것이다.(다시 한번, 유틸리티는 범용적이다)

자본 지출로서, 유틸리티는 더 많은 관심이 필요하다.
잘 짜는 것이 중요하다. 이것들은 반복적으로 사용될 것이기 때문에, 부정확성이나 비효율성이 배가 될 것이다.(잘못짜면)
이런 추가적인 관심은 디자인에 반영되어야 한다. (설계시 주의해야 한다.)
유틸리티는 당면한 문제가 아니라 일반적인(범용) 경우를 위해 만들어져야 한다.

마지막으로, 여타 다른 자본 지출과 마찬가지로, 우리는 유틸리티를 만드는데 서두를 필요가 없다.
새로운 연산자로 사용하려고 생각하고 있지만, 그것을 정말로 원하는건지 확신하지 못한다면,
일단 작성하되, 현재 사용하고 있는 (도메인에)특정한 프로그램 또한 남겨놔라.
나중에 다른 프로그램에서 새 연산자를 사용하면 서브루틴에서 유틸리티로 승격하여 일반적으로 접근 가능하도록 할 수 있다.
(뭐 헬퍼 펑션을 만든다는 말인듯?)

유틸리티 'find2는 좋은 투자로 보입니다.
7줄을 자본지출하여, 즉시 7줄의 비용절감을 한다.
유틸리티는 처음 사용했을 때 이미 그 대가를 치뤘다.

가이스틸은 다음과 같이 썼다.
"간결성에 대한 우리의 자연스러운 경향에 협력해라"
"cooperate with our natural tendency towards brevity"

'우리는 프로그래밍 구성의 비용은 그것이 서경(書痙: 글씨를 너무 많이 써서 생기는 손의 통증)의 양에 비례한다고 믿는다.
(그러니까 우리가 키보드질 많이 하는 것이 비용이라고 하는 것 / 여기서 '믿는다'는 열렬한 신념이 아니라 무의식적인 경향을 말한다)
사실 이것이 언어설계자가 염두해야할 나쁜 심리 원칙은 아니다.
우리는 덧셈이 저렵하다고 생각한다. 왜냐하면 우리는 "+"라는 한글자로 구분할 수 있기 때문이다.
아무리 어떤 A의 구성이 비싸다고 믿어라도, 그것이 우리의 작문 노력을 반으로 줄인다면, 싼 구성보다 A의 구성을 선호할 것이다.

모든 언어에서 "간결성을 향한 경향"은 새로운 유틸리티로 배출하지 않으면 문제를 일으킬 것이다. (요구를 말하는지 욕구를 말하는지?)
가장 짧은 숙어가 가장 효율적인 숙어는 이기는 드물다.
만약 당신이 한 리스트가 다른 리스트보다 긴지 여부를 알고 싶다면, 원시 Lisp는 우리에게 뭔가 작성하기를 유혹할 것.(아래처럼)
(> (length x) (length y))
여러 리스트에 함수를 매핑하려면, 먼저 함수를 다음처럼 결합해야 한다.
(mapcar fn (append x y z))   ;; append로 결합
이런 예는 우리가 비효율적으로 처리하는 상황이 오면 유틸리티를 작성하는 것이 중요하다는 것을 알려준다.
적잘한 유틸리티로 강화된 언어는 우리가 더 많이 추상화하여 프로그램을 만들 수 있다.
이러한 유틸리티가 적절히 정의되면, 보다 효율적인 유틸리티를 작성하게 될 것이다.

유틸리티 모음을 사용하면 확실히 프로그래밍이 쉬워진다. 하지만 이것들은 그 이상을 할 수 있다: 더 나은 프로그램으로 만들 수 있다.
요리사 같은 뮤즈(예술가)들은 재료가 보이면 바로 행동을 취한다.
이것이 예술이들이 그들의 스튜디오에 많은 도구와 재료를 갖고 싶어하는 이유다.
그들은 (가지고 오는데) 준비가 필요한 것을 가까이에 가지고 있다면 새로운 것을 시작할 가능성이 많다는 것을 안다.
상향식 프로그래밍에도 동일한 현상이 나타난다.
일단 당신이 새로운 유틸리티를 짰다면, 당신은 그것을 생각했던 것보다 더 많이 사용하고 있는 당신을 발견할 것이다.

다음 섹션에서는 유틸리티 함수의 여러 클래스를 설명한다.
이것들이 lisp에 추가될 수 있는 모든 종류의 기능을 대표하지는 않는다.
그러나 예로서 주어진 모든 유틸리티는 실제로 그들의 가치를 증명한 것들이다.

2019년 1월 4일 금요일

[on lisp] 4. Utility Functions 유틸리티 함수

4. Utility Functions
리스프 연산자에는 세 가지 유형이 있다.
1. 함수 2. 매크로 3. special form (우리가 쓸 수 없는 것)
이번 장에서 우리는 새로운 함수를 이용하여 리스프를 확장하는 기술을 설명한다.
여기서 기술은 보통 하던 것과 다르다.
이런 함수들에 대해 알아야할 중요한 점은 이것들이 어떻게 짜여지는 것이 아니라 어디에서 왔는가 이다.(어떤 생각에서 만들어지는지)

리스프의 확장은 여타 다른 리습 함수를 만드는 것과 동일한 기술을 이용한다.
이 확장에서 어려운 부분은 어떻게 쓸지를 결정하는 것이 아니라. 어떤 녀석을 확장할 지다.

4.1 Birth of a Utility
간단한 형태로, 상향식 프로그래밍은 누가 당신의 리스프를 설계했던간에 사후평가하는 것을 의미한다.(??)
당신이 프로그램을 짜는 동시에, 당신의 프로그램을 쉽게 쓸 수 있게 해주는 연산자를 또한 추가한다.
이런 연산자(operator)를 유틸리티라고 한다.

"유틸리티"라는 용어는 정확한 정의를 가지고 있지 않다.
코드의 한 부분이 별도의 어플리케이션이라고 보기에는 너무 작고, 어떤 특정 프로그램의 부분으로 고려하기에는 너무 범용적인 경우 "유틸리티"라 한다.
예를들어, 데이터베이스 프로그램은 유틸리티가 아니라 목록에서 단일작업을 수행하는 기능이 될 수 있다.

대부분 유틸리티는 리습이 이미 가지고 있는 매크로와 함수와 닮았다.(범용적이니까)
실제로 많은 커먼리습의 빌트인 오퍼레이터는 유틸리티로 시작된 녀석들이다.
함수 remove-if-not 같이 목록(리스트)에서 특정 predicate을 만족하는 모든 요소를 삭제하는 기능 또한 개별 프로그래머에게 정의되었던 녀석이다.

유틸리티를 쓰는 법을 배우는 것은 그것을 쓰는 기술이라기보다는 그것을 쓰는 습관을 배우는 것으로 더 잘 설명될 것이라 한다.
상향식 프로그래밍(Bottom-up programming)은 프로그램을 짜는 것과 동시에 프로그래밍 언어를 짜는 것이다.
이것을 잘하려면 어던 오퍼레이터가 현재 프로그램에 부족한지 알아내는 섬세한 감각을 개발해야 한다.
당신은 프로그램을 보고 이렇게 말할 수 있어야 한다. "Ah, what you really mean to say is this"
직관적으로 이해할 수 있어야 한다는 말인듯?

예를들어보자, nicknames라는 함수가 있다고 하자. 이름을 매개변수로 받아서 이것에서 파생되는 모든 닉네임들을 리스트로 뱉는다 해보자.
어떻게 우리는 리스트에 있는 모든 이름들의 닉네임을 받을 수 있을까?
우린리습을 배웠으니 아래처럼 할 것이다.
(defun all-nicknames (names)
  (if (null names)
      nil
   (nconc (nicknames (car names))
          (all-nicknames (cdr names)))))
좀 더 경험있는 리스프 프로그래머라면, "mapcan"이라는 걸 쓸 것이다.
====
mapcan - function &rest lists+ => concatenated-result
====
출처 http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm
이제 위에 "mapcan"을 쓰면 아래식으로 끝난다.
(mapcan #'nicknames people)
일전에 정의했던 all-nicknames는 바퀴를 재발명한 것이다. 하지만 그것만이 문제는 아니다.
범용연산자로 할 수 있는 일이 특정 함수에 묻혀버린 것이다.
여기서 "mapcan"은 이미 존재하는 녀석이다. 이걸 아는 사람들은 "all-nicknames"라는 함수를 보기 불편할 것이다.
상향식 프로그래밍에 능숙하다는 것은 누락된 연산자가 아직 만들어지지 않았을 때 똑같이 불편함을 느끼는 것이다.
당신은 "당신이 원하는 것은 x다"라고 말할 수 있어야 하고, 동시에 x가 무엇이어야 하는지 알 수 있어야 한다.

리스프 프로그래밍은 필요로 하는 새로운 유틸리티를 분리하는 일도 포함된다.
이 절의 목적은 이러한 유틸리티가 어떻게 생성되는지 보여주는 것이다.

아래 코드를 보자. 'towns심볼은 근처에 있는 town들을 리스트로 가지고 있다. 그리고 가까운 것이 먼저나오는 순서로 정렬되어 있다.
#'bookshops 함수는 도시 안에 bookshop의 리스트를 리턴한다. 만약 우리는 서점이 있는 가장가까운 도시를 찾는다면
지은이는 이렇게 적을거라 한다.
(let ((town (find-if #'bookshops towns))) ;; bookshops 함수 한번
  (values town (bookshops town)))  ;; bookshops 함수 두번
하지만 위 코드는 아름답지 않다. find-if가 #'bookshops의 리턴값이 non-nil인 것을 찾는다. 이 리턴값에 따라 재.계.산. 된다.
만약 #'bookshops이 아주 비싼(시간이 걸리는) 호출이라면, 이 코드는 문제가 있다. 이런 불필요한 일을 없애기 위해 아래처럼 바꾸자.
(defun find-books (towns)
  (if (null towns)
      nil
      (let ((shops (bookshops (car towns))))  ;; let으로 이제 bookshops는 한번만 실행된다.
           (if shops  ;; 내용이 있는지 확인
     (values (car towns) shops)  ;; 있으면 바로 리턴
        (find-books (cdr towns))))))  ;; 없으면 리스트의 다음 타자로 재귀
이제는 필요 이상의 계산이 없이 원하는 것을 얻을 수 있다.

그런데 이런종류의 검색을 종종 할 것같은 생각이 든다. (이럴때 유틸리티로 분리를 하는 것)
여기서 우리가 원하는 건 find-if와 some을 이 합쳐진 것이다. 성공적인 요소와 테스트 함수에서 반환한 값을 리턴하는 녀석!
(defun find2 (fn lst)
  (if (null lst)
      nil
      (let ((val (funcall fn (car lst))))
           (if val
        (values (car lst) val)
        (find2 fn (cdr lst))))))
잘보면 find-books와 find2는 아주 비슷하다.
find2가 find-books의 골격이라고 보면 될 것 같다.
이제 사용해보자.
(find2 #'bookshops towns)
이것이 리습의 독특한 특징중 하나이다. 함수가 매개변수로 중요한 역할을 하는 것.
이것이 왜 리습이 상향식 프로그래밍(bottom-up programming)에 잘 맞는지 말할 수 있는 이유 중 하나다.
함수를 매개변수로 던져서 어떤 함수의 살을 붙일 수 있다면, 함수의 골격을 추상화 하는것이 쉬워진다.

프로그래밍을 입문 할 때, 추상화를 하면 중복된 노력을할 필요가 없다고 한다.
첫번째 레슨은 : Don't wire in behavior
예를들어 하나 또는 두 개의 상수에 대해 동일한 작업을 수행하는 두 함수를 정의하는 대신 단일 함수를 정의하고 상수를 인수로 전달하라.

lisp에서는 함수를 매개변수로 전달할 수 있기 때문에 아이디어를 더 잘 수행할 수 있다.
앞서 보여준 두 예제 모두. 특정 기능을 위한 함수에서 좀 더 일반적인 함수로 변형되었다. (함수를 매개변수로 넘기는 방식을 이용하여)

첫번째경우에는 미리 정의된 mapcan을 이용하였고, 두번째 경우에는 find2를 이용하였다. 둘다 원칙은 같다.

"범용 함수와, 구체적인 함수를 혼합하는 대신 범용함수를 정의하고 구체적인 것을 매개변수로 넣어라."

이 내용을 신중하게 적용하면 원칙에 따라 훨씬 더 우아한 프로그램을 만들어낼 수 있다.
이것이 상향식 디자인(bottom-up design)을 강요하는 유일한 이유는 아니지만, 주요한 이유중 하나이다.
이 챕터에서 정의되는 32개의 유틸리티에서 18개는 함수형 매개변수를 받는다.

2019년 1월 3일 목요일

[on lisp] 3.4 Interactive Programming

3.4 Interactive Programming

함수형 방식은 단순히 이뻐보여서 제시하는 것이 아니라. 일을 더 쉽게 할 수 있도록 한다.
리습의 동적 환경에서 함수형 프로그램은 비정상적인 속도로 작성되며 동시에 매우 신뢰할 수 있는 코드를 생산한다.

리스프에서 디버그는 비교적 쉽다.
오류의 원인을 추적하는 많은 정보를 런타임에서 이용할 수 있다.
하지만 더 중요한 것은 테스트를 쉽게 할 수 있다는 것이다.
컴파일 후 테스트를 하는 작업을 항상 같이 한번에 해야 할 필요가 없다.
toplevel 루프에서 함수를 개별적으로 호출해서 테스트를 할 수 있다.

Incremental testing은 리스프 스타일이 그것을 이용하기 위해 진화해왔기 때문에 아주 귀중하다.
함수형 스타일로 짜여진 프로그램은 하나의 함수가 하나의 기능으로 이해될 수 있으며,
읽는 사람의 관점에서 이것은 아주 큰 장점이다.

하지만 함수형 스타일은 또한 incremental testing에 아주 잘 맞는다.
(아까 위에서 설명했듯이) 함수형 스타일로 짜여진 프로그램은 한번에 한가지의 함수(기능)을 테스트할 수 있다.

함수가 외부 상태를 조회하거나 수정하지 않으면, 버그는 즉시 나타난다.(바로 알 수 있다는 말)
이런 기능은 오로지 리턴값으로만 바깥 세상에 영향을 미친다.
그러므로 우리는 우리가 짠 코드를 더 믿을 수 있게 된다.

순련된 리스프 프로그래머는 실제로 테스트하기 쉽게 프로그램을 설계한다.
1. 그들은 몇가지 side-effect를 분리하려고 노력한다. 많은 부분을 순수 함수형 스타일로 작성할 수 있도록 한다.
2. 만약 side-effect를 수행해야 하는 함수의 경우, 최소한 함수적 인터페이스(functional interfaces)로 제공한다.
3. 각 기능에 잘 정의된 단일 목적을 제공한다.

리스프에서는 테스트가 단일로 toplevel loop로 즉각 알 수 있기 때문에 피드백이 아주 빠르다.
리스프에서 개발은 (다른 언어와 마찬가지로) 쓰기와 테스트의 순환이다.
하지만 리스프는 그 주기가 아주 짧다. 하나의 함수 혹은 여러 함수들의 부분이라해도 그렇다.

만약 해당 함수를 짜고 테스트를 돌려서, 에러가 나면 어디서 발생했는지 바로 안다. (마지막으로 쓴 곳)
간단하게 들리겠지만, 이 원칙은 상향식 프로그래밍을 가능하게 하는 것이다.
이것은 리습 프로그래머들이 기존 개발 방식에서 자유와 자신감을 준다. (오래된 계획 후 구현의 하향식 개발방식)

1.1절에서 상향식 설계가 진화하는 과정이라 강조했다. 당신은 그 안에 프로그램을 짜면서 언어를 만들어내는 것이다. (쌓아 올라가는 것)
이런 접근법은 당신이 낮은 수준의 코드를 신뢰하는 경우에만 작동할 수 있다. (아래부분이 믿을만해야 한다는 말)
당신이 마주치는 모든 버그는 언어 자체가 아니라 당신의 어플리케이션에서 발생한 버그라고 가정할 수 있어야 한다.

[on lisp] 3.3 Functional Interfaces

3.3 Functional Interfaces

어떤 사이드이팩트는 다른 것들보다 나쁘다.
예를들자. 이 함수는 nconc를 호출한다.
(defun qualify (expr)
  (nconc (copy-list expr) (list 'maybe)))
이것은 참조 투명성을 유지한다. 같은 인수를 넣으면 항상 같은 값을 반환할 것이다. (리스트를 수정하고 있다고는 하지만 새로 복사를 하기 때문에 상관없다.)
그러므로 호출자의 관점에서는 이건 순수 함수형 코드일 것이다.
우리는 이전에서 본 bad-reverse와 같다고 할 수 없다. (실제 매개변수를 변경하고 있는 녀석과는 다르다.)

모든 사이드이팩트를 나쁘게 다루는 것 보다. 이런 경우들과는 구별이 되도록 해야겠다.
비공식적으로, 아무도 소유하지 않은 것을 수정하는 것은 무해하다 말할 수 있다.
예를 들어, 위에 nconc는 무해하다. 왜냐하면 매개변수로 받은 expr는 새롭게 만들어져서 더해졌기 때문이다.
새롭게 만들어진 이 녀석은 아무도 소유할 수 없었다.

일반적으로, 우리는 소유권에 대해 함수가 아닌, 함수의 호출에 대해 이야기 해야 한다.
아래 코드에서 아무도 변수 x를 소유하지 않고 있다
(let ((x 0))
  (defun total (y)
    (incf x y)))
이 호출의 영향은 다음 호출에서 나타날 것이다.
따라서 다음의 규칙을 따라야 한다: 주어진 호출은 고유하게 소유하는 것을 안전하게 수정할 수 있어야 한다. (나머지 내용은 그냥 넘어...)

[on lisp] 3.2 Imperative Outside-In 명령형 뒤집기

3.2 Imperative Outside-In

함수형 프로그래밍의 목적은 명령형 프로그래밍과 대조될 때 더 명확하게 드러난다.
함수형 프로그램은 당신이 무엇을 원하는지 말한다. 명령형 프로그램은 당신이 무엇을 해야 하는지 말한다.

비교를 해보자면
함수형 프로그램은 "Return a list of a and the square of the first element of x"라고 말한다.
(defun fun (x)
  (list 'a (expt (car x) 2)))
명령형 프로그램은 "Get the first element of x, then square it, then return a list of a and the square"라고 말한다.
(defun imp (x)
  (let (y sqr)
    (setq y (car x))
    (setq sqr (expt y 2))
    (list 'a sqr)))

명령형 에서 함수형으로 변환하는 트릭이 있다.
그 트릭은 명령형 프로그램은 함수형 프로그램이 안에서 밖으로 변형된 것이며
함수형 프로그램은 명령형 프로그램이 밖에서 안으로 변형된 것이라 해보자.

첫번째로 우리가 주목해야 하는 것은 let 내부에 있는 y, sqr의 생성이다.
이것은 나쁜일이 따라올 거라는 징조다. 런타임에 eval을 하는 것처럼 초기화 되지 않은 변수들은 거의 필요하지 않다.
하여 일반적으로 프로그램 내 질병의 징후로 취급해야 한다.

이러한 변수들은 프로그램을 자연스러운 모양(natural shape)으로 되지 않도록 고정시키는 핀처럼 쓰인다.
일단 이것들은 넘어가고 함수의 마지막으로 가보자.
명령형에서 가장 마지막에 실행되는 녀석은 함수형에서는 가장 바깥쪽에서 실행된다.

그러므로 우리가 할 일의 첫번째 단계는, 마지막 호출을 잡은 채로 프로그램의 나머지를 안에 집어 넣는 것이다!
마치 셔츠를 뒤집는 것처럼. 해보자.
마지막에 있는 값 (list 'a sqr)을 잡은 채로 나머지 내용을 안에 넣는 것이다.
(list 'a sqr)
;; sqr을 안에 넣는다.
(list 'a (expt y 2))
;; 이제 y도 안에 넣는다.
(list 'a (expr (car x) 2))
;; 명령형이 함수형으로 변경되었다.
필자 말로는 이 최종결과가 이전 초기버전보다 낫다고 한다.
기존 명령형 코드를 보면, 우리는 리턴을 하는 마지막 표현식 (list 'a sqr)을 만나게 되는데
sqr이 어디서 왔는지 알 수 없기 때문에 즉각적으로 명확히 할 수 없다.
이제 변형된 리턴코드는 로드맵처럼 제시되어 있다.

이 기법은 더 큰 기능에 적용되면서 가치가 높아진다.
사이드이팩트를 수행하는 함수에조차 그렇지 않은 부분을 정리할 수 있다.

2019년 1월 2일 수요일

[on lisp] 3.1 Functional Design 함수형 프로그래밍

3. Functional Programming
이전 장에서는 리스프와 리스프 프로그램 모두 하나의 원재료로 만들어졌음을 알려줬다. (함수)
여타 다른 건축 자재처럼, 이것들의 품질은 우리가 만드는 것들의 종류와 방식까지 모두 영향을 미친다.

3.1 Functional Design
객체의 특징은 그것이 뭐로 만들어졌는지에 영향을 받는다.
목조건물과 석조건물은 다르다. 목조건물로 할 수 없는 것을 석조건물은 할 수 있다. 그 반대도 마찬가지다.
멀리서 건물을 볼 때, 그것이 나무인지 돌인지는 확인할 수 없어도, 건물의 전체적인 모양을 보고 그것이 무엇으로 만들어졌는지 알 수 있다.

Lisp함수의 특성은 Lisp 프로그램의 구조에 그와 상응하는 영향을 미친다.

Functional programming means writing programs which work by returning values instead of by performing side-effects.
함수형 프로그래밍은 사이드이펙트를 만드는 대신 값을 리턴하는 방식으로 프로그램을 짜는 것이다.

사이드이펙트는 파괴적인 객체변환(rplaca함수를 사용: cons의 car를 치환)과, 변수를 할당하는 것이다.(setq)
사이드이펙트가 더 적고, 국지적일경우(범위가 작아질 경우), 프로그램의 읽기, 테스트, 디버그가 쉬워진다.
리스프 프로그램이 항상 이런 스타일로 작성된 것은 아니지만, 시간이 흐르면서 리스프와 함수형 프로그래밍은 분리될 수 없게되었다.

예를들어, 다른 언어와 다른 것을 보여줄 것이다.
리스트를 역순으로 만들고 싶다고 하자.

리스트를 역순으로 변.경.하는 함수를 짜는대신에, 우리는 리스트를 받고 똑같은 요소를 가진 리스트를 리턴하는 함수를 만들자. (물론 역순)
(defun bad-reverse (lst)
  (let* ((len (length lst))
  (ilimit (truncate (/ len 2))))
    (do ((i 0 (1+ i))
  (j (1- len) (1- j)))
 ((>= i ilimit))
      (rotatef (nth i lst) (nth j lst)))))
(setq lst '(a b c))
(bad-reverse lst) ; NIL
lst ; (C B A)

(bad-reverse '(1 2 3 4 5))  ;; ?? !!
이름부터 bad-reverse다. 이건 리스트를 새로 받아서 변.경.하는 함수를 짠 것이다.
리턴 값은 뭔가? NIL 내가 원하는 값과는 관련이 없다.
이건 리스프의 스타일이 아니다.
더 알아야 할 점은 이런 추함은 전염된다는 것이다. 이런 함수는 나중에 사용하는 사람에게도 해를 끼치ㅐㄴ다.
그리고 사용하는 사람도 함수적인 프로그래밍을 할 수 없게 만든다. 기능적 제한을 만들어주는 꼴이다.

새로 만들어보자.
(defun good-reverse (lst)
  (labels ((rev (lst acc)
  (if (null lst)
      acc
   (rev (cdr lst) (cons (car lst) acc)))))
   
 (rev lst nil)))
(setq lst '(a b c))
(good-reverse lst) ; (C B A)
lst ; (A B C)
이렇게 하면 아주 함수적으로 만든것이다.

이 책의 저자는 사람의 특징을 판단할 때 그의 머리스타일을 보고 판단할 수 있다고 생각했다 한다.
이것이 사실이던 아니던 리스프 프로그램에서는 사실이다.
Functional Program은 imperative Program과는 다른 형태를 가지고 있다.

함수형 프로그램의 구조는 전적으로 표현식 내에 인수들의 구성(방식)으로 표현된다.

인수들이 (인덴트로) 들쑥날쑦하기 때문에, 함수적인 코드는 들여쓰기에서 더 많은 움직임이 있다.
함수적코드는 페이지 위에 액체 같고, 명령형코드는 단단하고 나무토막 같다.
(뭐 함수형 코드가 더 유동적으로 보이고, 명령형 코드는 덜 유동적이라 자유롭지 않다는 말인듯? 중요하지 않은 내용이므로 고민말고 넘어감)

심지어 멀리서 봐도, bad-reverse와 good-reverse의 형태는 어떤 것이 더 나은 프로그램인지 암시한다.
(확실히 함수형 프로그램은 들여쓰기가 계속 생겨서 마구마구 움직이는 것 같지만 명령형 코드는 들여쓰기가 없고 목재마냥 직사각형을 보이고 있다.)
비록짧지만 good-reverser가 더 효율적이다. O(n) instead of O(n2).

커먼리습에는 가실 reverse 기능을 내장하고 있다.
(setq a '(1 2 3))

(print (reverse a))

(print a)
이 기능은 기존 내용을 변경하지 않고 새로 리턴한다. 그러므로 반약에 a를 변경하고 싶다면? 새로 값을 넣어야 한다.
(setq a (reverse a))
good-reverse와 bad-reverse의 차이에서 간과한 점은 bad-reverse는 "cons"를 하지 않는다는 것이다.
새로운 list structure를 만드는 것이 아니라. 기존 리스트에 실행된다. 이런건 아주 위험할 수 있다.
리스트는 다른 곳에서 사용될 수도 있다. 하지만 효율성을 고려할 때 필요한 상황이 있을 수 있다.
... 중략 ...
함수형 프로그래밍은 일반적으로 좋은 생각이다. 특히 Lisp에서, 왜냐하면 Lisp은 이것을 제공하기 위해 진화해왔기 때문이다.

[on lisp] 2.8 Tail-Recursion 꼬리재귀

2.8 Tail-Recursion

재귀는 자기자신을 호출하는 거다.
꼬리재귀는 자기자신을 호출할 때, 콜스택이 바닥나지 않도록 미리 일을 해놓는다고 한다.
아래 내용은 꼬리재귀가 아니다.
(defun our-length (lst)
  (if (null lst)
      0
    (1+ (our-length (cdr lst)))))
왜냐하면 재귀호출에서 리턴을 할 때, 1+이라는 함수에게 넘겨야 하기 때문이다.
아래는 꼬리재귀다.
(defun our-find-if (fn lst)
  (if (funcall fn (car lst))
      (car lst)
   (our-find-if fn (cdr lst))))
왜냐하면 재귀호출의 값이 즉시 리턴되기 때문이다.

꼬리재귀는 꽤나 중요한데, 이런 재귀호출을 루프로 변환해주도록 컴파일러들이 디자인되어 있다.
이런 우아한 재귀호출을 사용하면서도 함수를 호출하는 오버헤드를 느낄 수 없게 된다.
이정도의 최적화면 재귀호출가 루프를 대신할 정도는 된다고 할만 하다.

꼬리재귀가 아닌 함수는 종종 꼬리재귀로 변형하기 위해서 accumulator를 내부에 넣어서 상태를 기록하도록 한다.
(defun our-length (lst)
  (labels ((rec (lst acc)
                (if (null lst)
        acc
     (rec (cdr lst) (1+ acc))))))
  (rec lst 0))
여기 acc를 보면 계속 1+로 1을 더하면서 재귀를 실행한다. 이렇게 누산기를 넣어서 재귀를 하는 거다.
그리고 acc를 마지막에 리턴할 거다.
커먼리습 컴파일러는 이런 꼬리재귀를 최적화 할 수 있다. 하지만 이게 디폴트인 경우는 드믈다.
파일 맨 위에 아래 내용을 적어라.
(proclaim '(optimize speed))
꼬리재귀와 타입선언으로 커먼리습 컴파일러는 코드가 C언어만큼 (혹은 더 빠르게) 코드를 생성한다.
Richard Gabriel 이라는 사람이 소개한 예제를 적는다.
1부터 n까지 더하는 함수이다.
(defun triangle (n)
  (labels ((tri (c n)
  (declare (type fixnum n c))
  (if (zerop n)
      c
    (tri (the fixnum (+ n c))
         (the fixnum (- n 1))))))
    (tri 0 n)))
(print (triangle 10))
아래처럼 acc를 이용하여 꼬리재귀를 이용한다.
declare,type을 이용하여 타입을 지정하는 것으로 보인다.

[on lisp] 2.7 Local Functions 로컬변수처럼 함수쓰기

2.7 Local Functions

람다표현식을 사용할 때, defun을 사용할 때는 직면하지 않았던 문제에 직면하게 된다.
람다표현식은 이름이 없기 때문에 자기 자신을 부를 방법이 없다.
그래서 커먼리습에선 재귀를 람다만으로 구현할 수 없다.

예를들면
(mapcar #'(lambda (x) (+ 2 x)) '(2 5 7 3))  ;; (4 7 9 5)
만약 여기서 재귀함수를 넣고 싶다면?
(mapcar #'copy-tree '((a b) (c d e)))
이렇게 그냥 넣으면 된다. 하지만 람다는?
label이라는 녀석을 사용하면 된다.
(labels ((inc (x) (1+ x))) (inc 3))  ;; 4
labels는 let의 함수버전이라고 생각하면 된다.
(defun count-instances (obj lsts)
  (labels ((instances-in (lst)
    (if (consp lst)  ;; list면
        (+ (if (eq (car lst) obj) 1 0) ;; obj와 같냐 틀리냐고 1,0으로 나뉘고  
    (instances-in (cdr lst)))  ;; 재귀적으로 나머지 리스트를 다시 호출해서 obj('a)가 몇개 있는지 확인한다.
      0)))  ;; 리스트가 아니면 0
    (mapcar #'instances-in lsts)))
    
(print (count-instances 'a '((a b c) (d a r p a) (d a r) (a a))))
;; 각 리스트에 'a가 몇개 있는지
;; 1 2 1 2
이렇게 쓸 수 있다.
라벨링을 일단 하고 사용할 함수에 그 녀석을 넣으면 된다.

[on lisp] 2.6 Closures 클로저 사용하기

2.6 Closures

커먼리습은 lexical scope이기 때문에, 함수를 free variable을 포함하여 정의할 수 있다.
free variable을 포함하여 정의를 하면 시스템은 함수가 정의된 시점에 해당 변수에 바인딩된 녀석을 찾고 사본을 저장해야 한다.

이런 함수와 변수바인딩의 조합을 closure(클로저)라고 한다.
클로저는 커먼리습에서 너무 만연하여 자신도 모른체 사용하고 있을 수도 있다.


Every time you give mapcar a sharp-quoted lambda-expression containing free variables, you're using closures.
mapcar에 #'(lambda ...)에 free variable이 포함된 것을 봣다면 지금까지 closure를 쓴것이다.

예를들어, 리스트를 받아서 특성 숫자를 각 요소에 더하는 함수를 만든다고 하자.
(defun list+ (lst n)
  (mapcar #'(lambda (x) (+ x n))
          lst))
(list+ '(1 2 3) 10)
list+를 자세히 보면 closure가 적용된 것을 알 수 있다.
잘 보면 lambda 함수 안에 n은 free variable이다. 이 녀석은 둘러쌓인 환경(defun list+ ...)에서 바인딩 된다.
이렇게 함수를 매핑하는 곳에는 왠만하면 closure가 있다.

Closure는 렉시컬 스코프에서 쓰이는 로컬변수의 상태라고 생각해보자.(블로거 생각)
이런 로컬 변수를 사용하는 경우를 보자.
(let ((counter 0))
  (defun new-id () (incf counter))  ;; incf 는 counter를 1 증가시킨다. 
  (defun reset-id () (setq counter 0)))
위의 두 함수를 counter 변수를 공유한다.
첫번째는 counter를 +1 하고 두번째 함수를 counter를 0으로 변경한다.
이렇게 두 함수가 같은 변수로 연결될 수 있다.
이처럼 local state와 함께 함수를 리턴하는 것은 아주 유용한 기술이다.
(defun make-adder (n)
  #'(lambda (x) (+ x n)))
이렇게 하면 free-variable n은 make-adder의 매개변수에 바인딩 되고 그 카피본과 함께 함수를 리턴된다.
리턴된 함수를 n을 가지고 있게 되는 것이다.
(setq add2 (make-adder 2)
function :LAMBDA (X) (+ X N)
(funcall add2 5)
7
위에서 make-adder에서 리턴된 내부 상태는 변경되지 않는다. 하지만 우리는 가능하게 할 수 있다.
(defun make-adderb (n)
  #'(lambda (x &optional change)
      (if change
       (setq n x)
    (+ x n))))
(setq addx (make-adderb 1))
(funcall addx 3) ;; 4
;; change optional
(funcall addx 100 t)
(funcall addx 3) ;; 103

클로저 덩어리를 리턴하는 것도 가능하다.
당연히 함수를 일반 객체처럼 쓸 수 있으니, 리스트에 넣어서 빼쓰는 거라든게 해시맵에 저장하는 거라든가 모든게 가능할 것이다.

[on lisp] 2.5 Scope 렉시컬 스코프

2.5 Scope

커먼리습은 lexically scoped Lisp이다. 스킴이라는 언어가 lexical scope를 가장 오래전부터 가진 언어다.
그전까지는 모두 dynamic scope를 고려하여 만들어졌었다.

lexical과 dynamic scope의 차이는 free variables를 어떻게 다룰 것인지를 구현한 방식에 따라 다르다.
아무것도 바인딩 되지 않은 symbol을 우리는 free하다고 한다.
(let ((y 7))
  (defun scope-test (x)
    (list x y)))
여기 defun 안에 있는 변수를 보자. x는 매개변수로 연결되어 있지만 y는 free하다.
free variable은 값이 뭐가 되야 할지 명확하지 않다.
bound variable(여기서는 x)에서는 불확실성이 없다. scope-test가 실행되면 x값은 인수로 전달될 것이다.
하지만 y는 어디에서 받는가? 이것이 스코프 규칙에 따라 달라진다.

dynamic scoped Lisp에서 free variable은 scope-test를 실행할 때 찾는다.
함수호출의 체인을 반대로 돌아보면서 확인한다. (콜스택을 확인한다는 말인듯)
(let ((y 5))
  (scope-test 3)) ;; (3 5)
이게 dynamic scope이다. 위에 y는 7로 연결되어 있지만, dynamic scope에서는 실행한 순간 바인딩 되어 있는
녀석을 보기 때문에 의미 없어지고 y=5로 바인딩 된다.

Lexically scoped Lisp에서는 함수호출체인을 뒤로 둘러보는 것이 아니라.
함수가 정의된 순간에 포함된 환경을 둘러본다. 그러면 y=7이 바인딩 될 것이다.
(let ((y 5))
  (scope-test 3)) ;; ( 3 7)
5를 설정한게 전혀 쓸모가 없어진 것이다.

이 기능은 다음 섹션에서 보여줄 새로운 프로그래밍 기술을 가능하게 해준다.(클로저)

[on lisp] 2.4 함수를 프로퍼티처럼 땡겨쓰기

2.4 Functions as Properties

동물의 유형에 따라 다른 행동을 하도록 만들어보자.
대부분 언어에서는 case 문을 이용할 것이다.
리스트에서도 가능하다.

(defun behave (animal)
  (case animal
    (dog (wag-tail)
      (bark))
 (rat (scurry)
   (squek))
 (cat (rub-legs)
   (scratch-carpet))))
여기 dog, rat, cat에 따른 일들을 정의했다.
만약 새로운 타입의 동물이 필요하다면? 케이스문을 나열할건가?
대부분 타입은 시간이 지나면 계속 추가된다. 이 책에서는 다른 방식을 추천한다.
이 방식은 어떨까?
(setf (get 'dog 'behavior)
      #'(lambda ()
       (wag-tail)
    (bark)))
이렇게 lookup테이블을 만드는데 거기에다가 함수를 담는 것이다.
실행은 어떻게 하는지 보자.
(defun behave (animal)
  (funcall (get animal 'behavior)))
이렇게 케이스문을 없애버렸다. 이렇게 하면 이제 behave함수는 변경될 이유가 없다.
lookup 테이블에 함수만 추가하면 된다.
보니까 저 위에 get 함수는 'dog 안에 behavior를 가져오는 것 같다.

[on lisp] 2.3 함수 매개변수

2.3 Functional Arguments
함수를 객체처럼 쓴다는 말은, 매개변수로 다른 함수에 던질 수도 있다는 말이다.
이 기능은 리스프의 상향식 프로그래밍에서 중요한 역할을 한다.

함수를 객체로 허용하는 언어는 이것을 호출하는 기능을 제공해야 한다.
일반적으로 "apply"라는 함수에 두개의 매개변수(함수, 매개변수리스트)를 보내서 실행한다.

(+ 1 2)
(apply #'+ '(1 2))
(apply (symbol-function '+) '(1 2))
(apply #'(lambda (x y) (+ x y)) '(1 2))

커먼 리스프에서는 첫번째 야규먼트가 리스트로 들어가고 뒤에 매개변수들이 cons로 뒤에 붙는다.
그래서 아래와 같은 것도 가능하다.
(apply #'+ 1 '(2))
이러면 3이 나온다.

만약 매개변수가 리스트로 들어오는 것이 맘에 들지 않는다면, funcall을 사용하면 된다.
(funcall #'+ 1 2)
많은 빌트인 함수들은 함수를 매개변수로 받는다.
가장 빈번하게 사용되는 곳은 함수매핑이다.
예를들어 mapcar는 2개 이상의 매개변수를 받는다.
함수와 하나 혹은 그 이상의 리스트들을 받아서 각 리스트 요소에 함수를 적용시킨다.
(mapcar #'(lambda (x) (+ x 10)) '(1 2 3))
(mapcar #'+
        '(1 2 3)
  '(10 100 1000))
sort, remove-if 기능도 마찬가지다.
(sort '(1 4 2 5 6 7 3) #'<)
(remove-if #'evenp '(1 2 3 4 5 6 7))
아래 remove-if 기능을 살펴보자.
(defun our-remove-if (fn lst)
  (if (null lst)
      nil
   (if (funcall fn (car lst))
       (our-remove-if fn (cdr lst))
    (cons (car lst) (our-remove-if fn (cdr lst))))))
여기서 주목해야 할 점은 fn에 #'(sharp-quote)가 없이 사용되고 있다는 점이다.
함수는 객체이고, 해당 변수는 일반 변수처럼 함수를 가질 수 있다.
그러니까 #'(sharp-quote)는 심볼(이름)에서 함수를 빼낼때 사용되는 것이다.

[on lisp] 2.2 defining function 커먼리스프의 #'

2.2 Defining Functions
(defun double (x) (* x 2))
이렇게 하면 만들어짐.

커먼리스프에서 심볼은 클로저와 다르게 하나의 심볼에 함수와 값이 동시에 저장될 수 있다.
(setq double 2)

(double double)
4
double에서 변수값, 함수를 따로 어떻게 구분지어 뽑아내려면
(symbol-value 'double)
(symbol-function 'double)
#'double 
하지만 함수도 또한 변수처럼 사용될 수 있다.
(setq x #'append)
(eq (symbol-value 'x) (symbol-function 'append))
T
내부적으로는 defun은 첫번째 매개변수(함수 이름)의 symbol-function의 자리에 이름없는 함수를 만들어서 연갈한다고 생각하면 된다.
(defun double (x) (* x 2))
(setf (symbol-function 'double)
  #'(lambda (x) (* x 2)))
대부분 심볼을 넘길 때, 함수임을 명확하게 하기 위해서 #'(sharp qoute)를 심볼 앞에 붙여서 넘긴다.