Could these be used as Racket definitions for cons, first, and rest?

Question

I am trying to follow along this Racket tutorial:

https://cs.uwaterloo.ca/~plragde/flaneries/TYR/Pure_Functional_Programming.html

and it describes these alternatives to the actual implementations. I know what cons, first and rest do, and I understand how lambda functions work, but I cannot figure out how these successfully implement cons, first and rest.

(define (cons f r) (lambda (b) (if b f r)))
(define (first lst) (lst true))
(define (rest lst) (lst false))

Maybe I have misinterpretted what they are supposed to be. Here is what the tutorial says:

As another example of the use of closures, consider the following "alternative" implementation of the basic list primitives.

Could someone clarify?

Answer 1

#lang racket

(define (cons f r) (lambda (b) (if b f r)))

Here cons has been redefined to be a procedure which takes two arguments f and r, and returns a procedure which takes one argument b. Let's try it:

cons-func.rkt> (define a-cons (cons 1 2))

Now we have called the cons procedure with the values 1 and 2; cons has returned a procedure which we have named a-cons.

cons-func.rkt> a-cons
#<procedure:...ratch/cons-func.rkt:3:19>

Now, a-cons is a procedure that takes a single argument; if that argument is true, then the first of two values passed in the earlier call to cons is returned; if instead the argument to a-cons is false, then the second of the two earlier arguments is returned:

cons-func.rkt> (a-cons true)
1
cons-func.rkt> (a-cons false)
2

There are two values stored in the closure returned by our new cons, and both of them can be retrieved. This is effectively a cons cell. Let's add some sugar to make this nicer to use. Here first and rest just do what we did by hand a moment ago:

(define (first lst) (lst true))

(define (rest lst) (lst false))

Now we can access the two parts of our cons cell in the usual way:

cons-func.rkt> (first a-cons)
1
cons-func.rkt> (rest a-cons)
2

This new implementation of cons cells is not compatible with the old one. For example, we have not redefined car and cdr, and the normal implementation of those procedures will not work with our new cons cells:

cons-func.rkt> (car a-cons)
; car: contract violation
;   expected: pair?
;   given: #<procedure:...ratch/cons-func.rkt:3:19>

We can use our new cons cells to define list:

(define (list . xs)
  (if (null? xs)
      '()
      (cons (car xs)
            (apply list (cdr xs)))))

Here we are cheating a bit, using the dot syntax to capture an arbitrary number of arguments in a list (the regular kind). We use car and cdr to take this list apart (because they work with regular lists), and reassemble it with the new cons into a closure-based list.

cons-func.rkt> (define a-list (list 'a 'b 'c))
cons-func.rkt> a-list
#<procedure:...ratch/cons-func.rkt:3:19>

Here you can see that the list created by our new list procedure, named a-list, is itself a procedure. We can call our first and rest procedures on a-list:

cons-func.rkt> (first a-list)
'a
cons-func.rkt> (rest a-list)
#<procedure:...ratch/cons-func.rkt:3:19>
cons-func.rkt> (first (rest a-list))
'b
cons-func.rkt> (first (rest (rest a-list)))
'c
cons-func.rkt> (rest (rest (rest a-list)))
'()

So, it seems that our closure-based cons cells behave as regular cons cells, though the underlying implementation is not compatible with Rackets own cons and list accessor procedures, and we can use these closure-based cons cells to create closure-based lists. If someone had the time and inclination, they could probably implement a whole Scheme around these closure-based cons cells.

Answer 2

Explanation through the substitution method:

The results you want are

   (first (cons a b))
—> a

and

   (rest (cons a b))
—> b

These are all the requirements for the three primitives.

Now consider (cons x y): replace f and r in the definition of cons with x and y – that is,

    (cons x y)
—>  (lambda (b) (if b x y))

Now, (first (cons x y)) is

    (first (lambda (b) (if b x y)))
—>  ((lambda (b) (if b x y)) true)
—>  (if true x y)
—>  x

and (rest (cons x y)) is

    (first (lambda (b) (if b x y)))
—>  ((lambda (b) (if b x y)) false)
—>  (if false x y)
—>  y

Answer 3

Defining a data structure is a process of 2 steps.

1. defining the axioms of the data structure, i.e. the abstract data structure

2. defining the implementation which must obey the axioms.

Whatever implementation you create is correct as time as the axioms are true in that implementation.

The axioms for the lisp constructor differ from implementation to implementation. In scheme they are so

1. (CAR (CONS x y)) = x

2. (CDR (CONS x y)) = y

Each implementation that creates the functions CONS, CAR, CDR that obey this is correct and can be used as implementation for cons cells contructor.

The things are not so direct however, as the axioms of CONS can interact with other axioms of the system. For example, some systems impose the axiom:

• (EQ (CONS x y) (CONS X Y))

and in this case you need to take care in the implementation such that cons to check if there is already a (X . Y) pair allocated, and not duplicate the memory.

The other answers detail the implementation of cons with functions.