Search code examples
functional-programmingproceduresicp

Difference between procedure and data in functional programming?

I'm a newbie in functional programming. I'm reading SICP book. I'm confused with the terms using for procedure & data.

what are the difference between procedure & data? Are they really same?

Any help would be appreciated. Thanks.

Solution

  • A compound procedure is one that is made up of one or more other procedures. That's an easy, straightforward definition, but it becomes a little tricker when we try to apply the same reasoning to data.

    I believe the example Harold Abelson gives in the lecture is something along the lines of:

    This is paraphrasing from memory – Harold Abelson, I hope I've done you justice here.

    Imagine we were to make a +rat procedure that took 4 numbers: numer1, numer2, denom1, and denom2. Calling it might look like:

    ;; naively add two rational numbers
(+rat numer1 denom1 numer2 denom2)

    Now imagine if we wanted to expand this further to support multiplication, you would continue to have to introduce more variables for each rational number

    ;; add then multiply
(define rat1 (+rat numer1 denom1 numer2 denom2))
(*rat (numer rat1) (denom rat2) numer3 denom3)

    This is getting really messy really quick. What if we could treat our rational number data like we do simple number data? What if we didn't have to always consider the individual components (numer and denom)? What if we could deal with our rational numbers as compound data ?

    ;; add two rational numbers
(define m (make-rat 3 4))
(define n (make-rat 5 6))
(+rat m n)

;; add then multiply
(define o (make-rat 1 2))
(*rat (+rat m n) o)

    Now we can express our computations in a much better way. Compare this to adding whole numbers

    (+ 1 2)
(* (+ 1 2) 3)

    We can reason about these expressions very easily. There's no need for us to be concerned with the individual components (numer and denom) of our rational numbers, we can work directly with the compound data. This lifts an incredible burden on us as our program continues to expand in complexity.

    ;; naive procedure
(define (+rat n1 d1 n2 d2)
  (make-rat (+ (* n1 d2)
               (* n2 d1))
            (* d1 d2)))

;; compound data procedure
(define (+rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

    In the non-naive implementation, the procedure expects x and y to be values that were constructed with make-rat – or at the very least, they must have valid numer and denom selectors. Writing the procedure this way means we can pass compound data around – instead of simple, separate pieces – and pick it apart inside our procedures as necessary.

    paraphrasing from memory; source: SICP Lecture 2B: Compound Data

    Anyway, you're right to be asking the question. The very fact that compound procedures and compound data have similar looking syntax means that we've effectively blurred the lines between code and data.

    Mind explosion: code is data; data is code.

    Keep reading SICP. It changed my life.

    Bonus Soda !

    This idea of data as code is very interesting to me. I never questioned things like Objects and Arrays when I studied other languages. But when I studied SICP, thinking about data differently, I questioned cons, car, and cdr – what are they exactly?

    Ultimately, how they're implemented doesn't matter. If we're just concerned about these 3 procedures, we have to think about the contract they fulfill …

    - - - - Contract - - - -

For any x and y

  (car (cons x y)) is x

  (cdr (cons x y)) is y

- - - - - - - - - - - - -

    It wasn't until I studied Lambda Calculus that I saw one of the most beautiful things I've ever seen. I'll show you here in Scheme …

    (define (cons x y)
  (lambda (p) (p x y)))
  
(define (car p)
  (p (lambda (x y) x)))
  
(define (cdr p)
  (p (lambda (x y) y)))

(println (car (cons 'x 'y))) ;; => 'x
(println (cdr (cons 'x 'y))) ;; => 'y

    What! Where's the "pair"? Where's the "list"? Where's the container for the data? Where is the data stored? It's right there in the code.

    code is data; data is code.

    Of course that's probably not how cons, car, and cdr are actually implemented, but we've fulfilled the contract and we could start building all sorts of really cool stuff with this. We've made a data structure out of nothing but lambdas – pulled out of thin air !