의 장점은 무엇 letrec?

Question

을 읽는 동안"노련한 음모"나는 너를 학습하기 시작했에 대 letrec.이해가 그것이 무엇(중복될 수 있습 Y-연결자)그러나 이 책에서 사용하는 대신 반복되는 이미 defined 기능에서 운영하는 인수를 정적 남아 있습니다.

예를 들어 오래된 기능을 사용하여 defined 기능을 반복되는 그 자체에(nothing special):

(define (substitute new old l)
  (cond
    ((null? l) '())
    ((eq? (car l) old)
      (cons new (substitute new old (cdr l))))
    (else
      (cons (car l) (substitute new old (cdr l))))))

지금에 대한 예는 같은 기능을 사용하여 letrec:

(define (substitute new old l)
  (letrec
    ((replace
      (lambda (l)
        (cond
          ((null? l) '())
          ((eq? (car l) old)
           (cons new (replace (cdr l))))
          (else
           (cons (car l) (replace (cdr l))))))))
(replace lat)))

고객께서는 약간 더 길고 읽기가 어렵지 않아요 왜 그들이 알고 다시 쓰기 기능을 사용하는 책 letrec.거기에 속도를 향상할 때 반복을 통해 정적 변수 이 방법은 하지 않기 때문에 계속 전달 it??

이 표준 방법에 대한 기능과 함께 인수를 유지 정적 하지만 인수 감소(이러한 반복으로 아래의 요소 목록)?

일부 입력에서 경험이 많은 웹 페/LISPers 도움이 될 것이다!

Answer 1

따라서 가독성 문제를 다루는 몇 가지 답변이 있습니다. 그러나 불분명 한 한 가지 질문은 성능 문제가 있는지 여부입니다. 얕은 표정으로, 그것은 letrec 이름이 지정된 버전let 루프에 통과 할 인수가 적기 때문에 하나 (실제로 동일)가 더 빠르야합니다. 그러나 실제로 컴파일러는 일반 버전의 루프가 변경되지 않은 첫 두 인수를 전달하고 첫 번째 반응 루프로 전환한다는 것을 알아내는 것처럼 등 뒤에서 모든 종류의 최적화를 수행 할 수 있습니다. 특정 시스템에 숫자를 표시하는 대신 4 가지 버전을 시간에 실행할 수있는 PLT 모듈이 있으며 다른 변형을 시도하기 위해 더 쉽게 추가 할 수 있습니다. 짧은 요약은 내 컴퓨터에서 명명 된 것입니다.let 버전은 약간 더 빠르며 꼬리 수익성을 높이면 전반적인 이점이 더 커집니다.

#lang scheme

;; original version
(define (substitute1 new old l)
  (cond [(null? l) '()]
        [(eq? (car l) old) (cons new (substitute1 new old (cdr l)))]
        [else (cons (car l) (substitute1 new old (cdr l)))]))

;; letrec version (implicitly through a named-let)
(define (substitute2 new old l)
  (let loop ([l l])
    (cond [(null? l) '()]
          [(eq? (car l) old) (cons new (loop (cdr l)))]
          [else (cons (car l) (loop (cdr l)))])))

;; making the code a little more compact
(define (substitute3 new old l)
  (let loop ([l l])
    (if (null? l)
      '()
      (cons (let ([fst (car l)]) (if (eq? fst old) new fst))
            (loop (cdr l))))))

;; a tail recursive version
(define (substitute4 new old l)
  (let loop ([l l] [r '()])
    (if (null? l)
      (reverse r)
      (loop (cdr l)
            (cons (let ([fst (car l)]) (if (eq? fst old) new fst)) r)))))

;; tests and timings

(define (rand-list n)
  (if (zero? n) '() (cons (random 10) (rand-list (sub1 n)))))

(for ([i (in-range 5)])
  (define l   (rand-list 10000000))
  (define new (random 10))
  (define old (random 10))
  (define-syntax-rule (run fun)
    (begin (printf "~a: " 'fun)
           (collect-garbage)
           (time (fun new old l))))
  ;; don't time the first one, since it allocates a new list to use later
  (define new-list (substitute1 new old l))
  (unless (and (equal? (run substitute1) new-list)
               (equal? (run substitute2) new-list)
               (equal? (run substitute3) new-list)
               (equal? (run substitute4) new-list))
    (error "poof"))
  (newline))

Answer 2

당신에 대해 특정 예를 들어:개인적으로 찾기 letrec 버전을 쉽게 읽:을 정의하는 재귀 도우미 기능과 당신의 몸에서 최고 수준의 함수입니다.의 주된 차이점은 두 가지 형태는 letrec 형식을 지정할 필요가 없는 정적 인수 또 다시 재귀는 전화를 찾을 것을 깨끗합니다.

만약 코드를 컴파일을 피하고,전달하의 정적 인수에는 각 재귀적 함수 호출에도를 제공하는 작은 성능 이점 이 경우 이 호출을 방지하는 데 사본을 인수로 새로운 스 프레임입니다.는 경우 재귀적 함수 호출에 꼬리 위치는 컴파일러는 영리 수 있습을 피하기 위해 충분히 복사는 인수에 스택니다.

마찬가지로 경우에는 코드 해석,적은 수의 인수에서 재귀 통화가 빠르게 할 수 있습니다.

더 일반적으로,하나의 주요 장점 letrec, 는 것이라고는 생각하지 않는다는 사실을 허용한 상호 재귀 함수 정의에 있습니다.나는 아주 경험과 계획,하지만 지금까지 제가 이해하기로는,이것은 하나의 주요 특징 letrec 양식에 비해 예: define.

Answer 3

우선 letrec 버전은 전역 이름이 다른 것으로 재설정되어 있어도 기능을 사용할 수 있습니다.

(define substitute
  ; stuff involving letrec
  )

(define sub substitute)
(set! substitute #f)

그 다음에 sub 여전히 작동하지만 비와는 그렇지 않을 것입니다.letrec 버전.

성능과 가독성에 관해서는, 후자는 아마도 맛의 문제 일 것입니다. 반면, 전자는 관찰 할 수 없어야합니다 (그러나 나는 이것을 주장 할 자격이 없지만 어쨌든 구현에 의존적입니다).

또한 실제로 이름을 사용했습니다 let 몸소:

(define (substitute new old lat) ; edit: fixed this line
  (let loop (
             ; whatever iteration variables are needed + initial values
            )
    ; whatever it is that substitute should do at each iteration
    ))

이런 식으로 더 읽을 수 있습니다. ymmv.