미분하는 프로그램 1

semmal의 이미지

Structure Interpretation of Computer Programs는 프로그래밍 입문서입니다.

입문서인데도 불구하고 프로그래밍 전반에 대한 기본 개념과 고급 기술까지 방대한 분야를 설명하고 있습니다.

책을 따라가다보면 여러가지 예제를 만나게 되는데, 그 수준은 입문서라고 보기 힘들정도의 고난이도를 자랑합니다.

지금 만드는 미분하는 프로그램은 그나마 쉬운 편에 속하죠.

Scheme과 같은 Lisp계열의 언어는 정말 막강한 기능이 있는데, symbolic data라는 것을 쓸 수 있다는 겁니다.

물론 ruby나 다른 언어도 symbol이라는 형태를 지원하기는 합니다만, 문법 등의 문제 때문에 Lisp이나 Scheme만큼의 강력한 성능을 내지는 못합니다.

아래 미분하는 프로그램에서는 이 symbolic data를 써서 문제를 쉽게 해결합니다.

Scheme의 강력함에 한번 빠져~ 봅시다~

; symbolic data가 들어오면 미분합니다. 지금은 더하기와 곱하기 밖에 지원하지 않습니다.
; 참고로 미분 공식은 d(u + v)/dx = d(u)/dx + d(v)/dx, d(u * v)/dx = u*(dv/dx) + v*(du/dx) 입니다.
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))
 
(define (variable? x) (symbol? x))
 
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))
 
(define (make-sum a1 a2) (list '+ a1 a2))
 
(define (make-product m1 m2) (list '* m1 m2))
 
(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))
 
(define (addend s) (cadr s))
 
(define (augend s) (caddr s))
 
(define (product? x)
  (and (pair? x) (eq? (car x) '*)))
 
(define (multiplier p) (cadr p))
 
(define (multiplicand p) (caddr p))
 
; 여기서 부터 문제
 
(deriv '(+ x 3) 'x)
;답 (+ 1 0)
 
(deriv '(* x y) 'x)
;답 (+ (* x 0) (* 1 y))
 
(deriv '(* (* x y) (+ x 3)) 'x)
;답 (+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+  x 3)))

댓글

Bini의 이미지

개인적으로 함수형언어에 관심이 많이 있읍니다.
그런데 scheme, lisp 은 모릅니다.
심볼릭테이타에 대해서 설명을 부탁드려도 될까요?
제가 배우고 있는 언어에서 구현이 가능할지 해보고 싶어서요.

semmal의 이미지

제가 알기로는 심볼릭데이터가 있는 걸로 압니다.

Haskell의 경우에는 algebraic data type에서 data constructor를 써서 심볼릭 데이터를 나타낼 수 있습니다.

ML에도 비슷한 기능이 있었던 걸로 기억하구요.

Erlang이나 다른 언어는 자세히 보지 못해서 잘은 모르겠습니다.

함수형 언어는 아니지만 심볼이 있는 Ruby의 경우에는 거의 string과 차이가 없는 듯이 보이구요.

SICP의 관점에 따르자면 심볼은 그저 심볼이 나타내는 "어떤 것"을 데이터로 보겠다고 하는 것에 불과합니다.

즉, 심볼은 어떤 것을 추상하는 "문법"일 뿐, 심볼 자체에는 큰 의미가 없다고 생각합니다.

단지 이 예제를 심볼이 없는 다른 언어에서 짠다면, 그리 간단한 일이 되지는 않을 것은 분명해보입니다.

제가 질문을 제대로 이해하고 답한 건지 모르겠네요.

------------------------------
How many legs does a dog have?

------------------------------
How many legs does a dog have?

lawch의 이미지

언젠가는 SCIP나 HTDP를 읽어봐야지 벼루고 있었는데
semmal님의 글만 잘 따라가면 되겠군요 ^_^

semmal의 이미지

이미 프로그래밍을 어느정도 하신다면 SICP는 몰라도 HTDP는 별로 학습 효과가 없을 것 같습니다. HTDP는 정말 기본중의 기본이라서요.

------------------------------
How many legs does a dog have?

------------------------------
How many legs does a dog have?

lawch의 이미지

기본서라면 그냥 빨리 대강 한번이라도 읽어 봐야겠군요.
알려주셔서 감사합니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.