일기:2024년 10월 7일

Posted on October 7, 2024

Deriving Recursive Programs

The Smaller-Subproblem Principle
If we can reduce a problem to a smaller subproblem, we can call the procedure that solves the problem to solve the subproblem.1

예제

스킴에서 리스트 길이를 계산하는 프로시저는 아래와 같이 정의할 수 있다.

;; list-length : List -> Int
;; usage: (list-length l) = the length of l
(define list-length
  (lambda (lst)
    (if (null? lst)
      0
      (+ 1 (list-length (cdr lst))))))

리스트 \(n\)번째 원소를 알아내는 프로시저는 다음과 같이 정의한다.

;; nth-element : List X Int -> SchemeVal
;; usage: (nth-element lst n) = the n-th element of lst
(define nth-element
  (lambda (lst n)
    (if (null? lst)
      (report-list-too-short n)
      (if (zero? n)
        (car lst)
        (nth-element (cdr lst) (- n 1))))))

(define report-list-too-short
  (lambda (n)
    (eopl:error 'nth-element
      "List too short by ~s elements.~%" (+ n 1))))

위 코드에서 프로시저 eopl:error를 사용하려면 Racket 패지키 eopl을 사용해야 한다.2

macOS에서 Racket을 설치하려면 터미널에 아래와 같이 입력한다.

brew install racket

Racket 패키지 eopl을 설치하려면 다음과 같이 입력한다.(예제가 많아서 그런지 의존성도 많고 패키지 설치 시간도 오래 걸린다.)

raco pkg install eopl

Racket 패키지를 가져오려면 프로시저 require를 사용한다.

(require eopl)

  1. Essentials of Programming Languages, 12쪽.↩︎

  2. https://docs.racket-lang.org/eopl/index.html↩︎