리스프

Kodumaro의 원래 게시물에서.



LISP는 1958년부터 전체 프로그래밍 언어 제품군을 시작한 John McCarthy의 사양입니다. 1930년대에 λ-calculus의 작업에서 나온 공식 시스템인 Alonzo Church을 기반으로 하며 대부분 숫자 대신 기호 데이터를 처리하도록 설계되었습니다. 명령형 언어의 표준.

LISP는 "목록 처리"를 의미하며 목록은 사양 기본 구조입니다. 코드 자체로서의 모든 데이터는 목록으로 표시됩니다.

예를 들어 1과 2의 합은 다음과 같습니다.

(+ 1 2)

+ , 1 및 2 요소 목록입니다. 이 목록은 car(머리) 및 cdr(꼬리) 함수에 의해 처리됩니다.

(+ . (1 2))

car 및 cdr는 IBM 704 명령으로 LISP가 가장 먼저 개발된 시스템입니다. CAR은 "등록번호 주소 부분의 내용"을 의미하고 CDR은 "등록번호 감소 부분의 내용"을 의미합니다.

머리는 람다 함수를 나타내고 꼬리는 매개 변수를 나타냅니다. 이 경우 함수는 매개변수의 합계를 반환하는 '+ 입니다.

LISP 제품군에서 가장 중요한 언어는 Common Lisp , Emacs LISP , Scheme 및 Clojure 입니다.

세 가지 LISP 언어에서 계승 구현을 살펴보겠습니다. 공통의 첫 번째 Lisp:

(defun factorial (n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))

R⁵RS(체계)에서:

(define factorial
  (lambda (n)
    (if (zero? n)
      1
      (* n (factorial (- n 1))))))

클로저에서:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

계획

Scheme은 그 자체로 하나의 가족이 되었으며, 다양한 구현뿐만 아니라 다양한 언어 변형도 포함하여 다양한 변형이 있습니다.

가장 중요한 변형은 Guile , MIT Scheme 및 Racket(이전의 PLT 체계)입니다.

Racket은 RAD이라는 IDE, DrRacket이라는 WYSIWYG 인터페이스 빌더 및 PLT 인터프리터를 포함하는 전체MrEd Designer 플랫폼입니다.

인터프리터는 R⁵RS , R⁶RS , PLT , Lazy Racket 및 even C 을 지원합니다.

예를 들어 Racket의 계승은 다음과 같습니다.

!#racket

(define factorial
  (λ (n)
    [if (zero? n)
      1
      (* n (factorial (- n 1)))]))

해시뱅 라인은 Racket이 처리해야 하는 언어를 알려줍니다.

R⁵RS: #!r5rs

R⁶RS: #!r6rs

PLT: #!racket

게으른 라켓: #!lazy

씨: #!planet jaymccarthy/c

어큐뮬레이터

Accumulator는 tail-call optimisation(TCO)을 활용하여 스택 오버플로를 처리하기 위한 기능적 프로그래밍 설계 패턴입니다.

팩토리얼을 다시 살펴보겠습니다. 단계는 현재 값에 이전 값의 팩토리얼을 곱한 값으로 정의됩니다. 중지는 0의 계승이며, 이는 1과 같습니다.

n! = n × (n-1)!
0! = 1

위의 PLT 구현을 살펴보면 마지막 호출 ID'*를 볼 수 있습니다. TCO를 활성화하려면 factorial이어야 합니다.

이를 가능하게 하려면 누산기 구동 함수가 있어야 하므로 factorial는 다음과 같이 됩니다.

(define factorial
  (λ (n)
    *factorial* n 1))

누산기 기반 버전( *factorial* )은 원래 매개변수와 누산기를 수신하고 누산기가 중지되면 누산기를 반환해야 합니다.

(define *factorial*
  (λ (n acc)
    [if (zero? n)
      acc
      (*factorial* (- n 1) (* acc n))]))

이제 마지막 호출은 *factorial*이며 TCO를 활성화합니다.

게으른 평가

대량의 계산된 데이터를 처리하는 가장 효율적인 접근 방식은 lazy evaluation 또는 필요에 따라 호출하는 것입니다. Haskell 예를 들어 요청에 따라 호출을 평가하여 무한 목록을 만들 수 있습니다.

fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Than on은 필요한 만큼의 요소만 취할 수 있습니다.

take 10 fib

약속

Lazy Racket은 Haskell과 유사한 방식으로 약속을 사용하여 평가를 지연시킵니다.

게으른 함수의 평가는 '!! 함수로 수행됩니다.

따라서 게으른 계승은 다음과 같습니다.

#!lazy

(provide factorial)

(define *factorial*
  (λ (n acc)
    [if (zero? n)
      acc
      (*factorial* (- n 1) (* acc n))]))

(define factorial
  (λ (n)
    (*factorial* n 1)))

그리고 다음을 호출하여 평가할 수 있습니다.

(!! [map (λ (n) `(,n ,(factorial n))) '(0 1 2 3 4 5)])

결과는 다음과 같습니다.

'((0 1) (1 1) (2 2) (3 6) (4 24) (5 120))