[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)를 심볼 앞에 붙여서 넘긴다.

[javascript] Object.create 함수로 크로스 브라우저 호환성 보완 - 05

/*
Object.create 함수로 크로스 브라우저 호환성 보완
*/

(function () {
  if(!Object.create) {
    Object.create = (function () {
      function F() {}
      return function (o) {
        F.prototype = o;
        return new F();
      }
    })();
  }
});

[javascript][prototype] ECMA의 class와 extends를 통한 상속 - 04

/* 
class와 extends를 통한 상속
자바스크립트의 new기능의 모호함을 해소하기 위해
ECMA6에서는 class와 extends를 정의한다.
*/

class Person {
  constructor() {
    this.name = "anonymous";
  }
}

class User extends Person {
  constructor() {
    super();
    this.name = "User";
  }
}

var user1 = new User();
console.log(user1 instanceof Person);
console.log(user1 instanceof User);
console.log(user1.constructor); // [Class: user]

[javascript][prototype] Object.create과 new 키워드로 생성자의 연결이 깨지지 않도록 - 03

/* Object.create와 new 키워드 조합 
Object.create과 new 키워드를 조합하여 생성자의 연결이 깨지지 않도록 해보자.
*/

function Person() {
  this.name = "unknown";
}

function User() {
  this.name = "user";
}

// 두 번째 매개변수는 키는 속성명으로 
// 새로 만든 객체에 추가될 속성 설명자(descriptor)를 지정합니다.
// writable option defaults to false.
// https://stackoverflow.com/questions/7757337/defining-read-only-properties-in-javascript
User.prototype = Object.create(Person.prototype, {
  constructor: { // Person.prototype.constructor 는 이제 읽기전용이다. 
    value: User  // 왜냐하면 기본이 writable = false 이다.
  }
})

var myuser = new User();
console.log(myuser instanceof User);
console.log(myuser instanceof Person);
console.log(myuser.constructor);

이 녀석은 이전

[javascript][prototype] 자바스크립트 프로토타입 맛보기 -02

function Car() {
  this.wheel = 4;
  this.beep = "BEEP";
}

Car.prototype.go = function () {
alert(this.beep);
  };

function Truck() {
  this.wheel = 6;
  this.beep = "TRUCK!!";
}

Truck.prototype = new Car();

function SUV() {
  this.beep = "SUV!!";
}
SUV.prototype = new Car();

var truck = new Truck(),
suv = new SUV();

console.log(truck.wheel);  // 6
console.log(suv.wheel);  // 4
console.log(truck.beep);  // TRUCK!!
console.log(suv.beep);  // SUV!!

Car라는 객체를 프로토타입에 넣어보니
Truck과 Suv 는 go라는 함수를 공통으로 사용할 수 있으며, 특히 SUV의 경우 wheel을 정의하지 않았지만
Car에 정의되어 있는 wheel = 4로 바퀴갯수 프로퍼티를 가질 수 있게 되었다.

[js] Object.create을 사용한 자바스크립트 상속 - 01

// 실제로는 Object.create 이라는 함수가 있다. 더글라스 크락포드가 주장했던 함수형태

Object.my_create = function(o) {
  function F() {};
  F.prototype = o;  // O는 처음부터 prototype역할을 하는 녀석일 것이다.
  return new F(); 
}

function Person(name) {
  this.name = name;
}

Person.prototype = {
  yell: function() {
    alert("My name is " + this.name);
  }
};

var u = Object.my_create(Person.prototype); // prototype을 넘기는 것을 주의하자.

u.name = "U";
u.yell();  // alert
/*
이렇게 Object.create 함수를 통해 객체를 생성하면 
개발자가 new 키워드를 사용하지 않고 함수 호출로 객체가 생성된다.

new 키워드를 사용할 때와는 달리 전체적으로 소스에 생성자의 개념이 사라지고 (new가 없으니까)
객체의 인스턴스와 인스턴스 간의 상속을 강조하는 것이 Object.create의 특징 (???)
*/

[js] 자바스크립트 상속기존의 자바스크립트 상속과 그 이면 - 00

function Person() {
  this.name = "anomymous";
  this.sayHello = function() {
    console.log(this.name + "!!");
  };
}

function Nam() {
  this.name = "Nam";
}
Nam.prototype = new Person();

var nam = new Nam();
nam.sayHello();
console.log(nam instanceof Nam);  // true
console.log(nam instanceof Person);  // true

console.log(nam.constructor);  // ?? Nam이 아니라 Person!!
/*
생성자 속성은 객체가 가지고 있는 것이 아니라. 프로토타입이 가지고 있다.
객체는 내부 링크로 프로토타엡에 있는 생성자 속성을 참조한다.

지금 Nam프로토타입은 
그런데 new Person()으로 원래 객체(여기선 Nam)의 생성자를 가지고 있는 프로토타입을 덮어씌우면
Nam의 생성자는 연결고리를 잃는다. (원래 Nam의 생성자는 function Nam() {...} 을 가리키고 있어야 한다.)

따라서 nam.constructor를 실행하면 [Function: Person] 이 나온다.
뭐 잘 작동하기는 하지만 연결이 끊어진다는 것은 좋은 것이 아니다.
*/

괜찮은 링크.
https://medium.com/@bluesh55/javascript-prototype-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-f8e67c286b67