6.001 Recitation #7

          5-minute-problem #5: Pairing with procedures
                       (posed, Fri, 9/19)

A procedure MAKE-PAIR is called a "pairing procedure" if it satisfies the

PAIRING CONTRACT: There are procedures FIRST and SECOND such that
                 (first (make-pair <val0> <val1>)) ==> <val0>
and
                 (second (make-pair <val0> <val1>)) ==> <val1>
for all scheme values <val0>, <val1>.


There is a way to define pairing using only lambda-abstractions and
combinations -- no conditionals, numbers, or anything else.  Here's how:

(define (make-pair val0 val1)
  (lambda (which)
    (which val0 val1)))

So the object which represents the pair of 7 and 9 is the value
of (make-pair 7 9), namely
                       (lambda (which) (which 7 9)).

In A FIVE MINUTE PRESENTATION, supply the definitions of FIRST and SECOND
which fulfill the contract for this last definition of the MAKE-PAIR
procedure.  Carry out a simple substitution model example to illustrate
the way these definitions work.

The presentation should be self-contained, building only on concepts that
the rest of the class would be expected to know at the time of the
presentation.  It would be a good idea to practice the presentation at
least once WITH A TIMER, preferably in front of a friendly, supportive
audience such as a roommate.


                           SOLUTION (presented 9/24)

                (define (first pr)  (pr (lambda (x y) x)))
or in desugared form:
            (define first (lambda(pr) (pr (lambda (x y) x))))

Similarly,
                (define (second pr) (pr (lambda (x y) y)))


To see how these work, first
           (define pair-of-7and9 (lambda (which) (which 7 9)))

Now we do a substitution model calculation for

(first                                pair-of-7and9               )

       ;eval the components of the combination.  The components are the
       ;variables FIRST and PAIR-OF-7AND9 which are evaluated by looking
       ;up their definitions:

((lambda(pr) (pr (lambda (x y) x)) ) (lambda (which) (which 7 9)) )
             |                   |
             ---------------------
                operator body
 |                                 | |                          |
 ----------------------------------- ----------------------------
           operator                            operand


        ;next APPLY the operator value to the operand value, which means:
        ;substitute the operand for the formal parameter PR in the body
        ;of the operator:


            ((lambda (which) (which 7 9)) (lambda (x y) x)) )
             |                          |
             ----------------------------
                    PR was here

        ;since the components of the above combination are both lambda expressions
        ;(which is how we represent compound procedure values), we can immediately
        ;APPLY again:


                  ((lambda (x y) x) 7 9))
                   |              |
                   ----------------
                    WHICH was here

       ;and APPLY again:
                                 7
                                | |
                                 -
                             X was here

So indeed, (first pair-of-7and9) ==> 7.