- cons
  the "malloc" of lisp/scheme, like Java new() operator, except the (classes)
  types in Lisp are simpler: built-in/atomic types and cons cells
  takes exactly two arguments

- car

- cdr

- cons cells == pairs

- examples forming and accessing pairs (cons cells)

(define pair1 (cons 1 2))

(car pair1)

(cdr pair1)

(define two-cells (cons 1 (cons 2 nil)))

(define three (list 1 2 3))

Defining pair,getx,gety as an example of a non-list use of cons cells.
The function, pair, is the constructor and getx,gety are accessors.

(define (pair x y)

   (cons x y) )



(define (getx aPair)

  (car aPair) )



(define (gety aPair)

  (cdr aPair) )

Example

(define p (pair 3 7))



(getx p)



(gety p)

Picture of this CONS cell in memory:

  CAR   CDR

+-----+-----+

|     |     |

|  .  |  .---- 7

|  |  |     |

+--|--+-----+

   |



   3

or more simply using a "dot"

. ---- 7



|



3

We can build arbitrary structures with CONS cells;
but again, note that pairs are not lists.

It is customary to make lists using CONS cells; and there are certain
conventions used.

- car
  the head of the list
  the first element of the list

- cdr
  the tail of the list, which is also (usually) a list
  note, tail does not mean the same thing as last element of the list

(cons 1 (cons 2 (cons 3 nil)))

... same as

(cons 1 (cons 2 (cons 3 ())))

. ---- . ---- . ---- ()



|      |      |



a      b      c

nil is atomic
nil is ()
nil is a list, the empty list

The function null? returns a boolean.  This function asks the
question: is my argument null?

> (null? ())

#t

> (null? null)

#t

> (null? (cons 1 2))

#f

> (null? 1)

#f

Draw CONS-CELL pictures of these lists:

()

(a)

((a))

(((a b)))

(a . b)

((a b . c))

(a b . c)

(a b . nil)

(a b . (c))

(a b c . (c d))

(a b c (d) e)

Pairs are used primarily to represent lists.
A list can be defined recursively as either the empty list or a pair whose
cdr is a list.

Precise definition:
 The set of lists is defined as the smallest set X such that

  The empty list is in X.
  If list is in X, then any pair whose cdr field contains list is also in X.


[Note] Dotted Pair vs. CONS function

According to R5RS...

Note that (4 . 5) is the external representation of a pair,
not an expression that evaluates to a pair.

Athough many Scheme environmonts allow dotted pairs on input, if yours doesn't
you can always use (cons 4 5) to create a pair on input.



Try some more examples; Think; try to draw pictures of the in
memory representations and repeat, do more examples until this is well understood.


The boolean function list? asks whether its argument is a list.
Consider the following,

> (list? 1)

#f

> (list? (cons 1 2))

#f

> (list? (cons 1 (cons 2 (cons 3 ()))))

#t

> (list? (cons 1 (cons 2 (cons 3 4))))

#f

> (list? (cons (cons 1 2) (cons (cons 3 4) ())))

#t

The special form, quote, prevents its argument from being evaluated.

> (* 1 2)

2

> (quote (* 1 2))

(* 1 2)

> (1 2)

procedure application: expected procedure, given: 1; arguments were: 2

> (quote (1 2))

(1 2)

The single quote, 'X, presents a convenient alternative syntax for (quote X).

'(* 1 2)

'(1 2)

Quoting symbols is useful when you want a symbols to be data instead of variables bound to some values.

(define a 1)

(define b 2)

(cons a b)

(cons 'a 'b)

(cons 'a 'c) ;; note c is an unbound variable, but OK here because its quoted

Notice that you don't need to quote number literals, because numbers
evaluate to themselves.  The following produce the same result.

(cons 1 2)

(cons '1 '2)

The function, list, makes a list out of its arguments

> (list 3 7)

(3 7)

> (list (* 3 7))

(21)

> (list '(* 3 7))

((* 3 7))

> (list '(* 3 7) (* 4 8) '(5 9))

((* 3 7) 32 (5 9))

> (list '())

(())

> (list null)

(())

> (list? (* 3 7))

#f

> (list? '(* 3 7))

#t 

HINT:
Beginning Scheme programmers may find one method of learning how lists work
is to try to construct lists without use of quote.
In other words, try to use explict cons calls, instead.

For example try,

(cons 1 (cons 2 (cons 3 (cons 4 ()))))

Instead of,

(cons 1 '(2 3 4))

Both of these expressions produce the same result when entered interactively
to Scheme's read-eval-print loop.

When you want to write list expressions that are mostly literal but have some designated holes to be filled in with runtime values, use "quasiquote".

> (define a 4)



> (define b '(5 6))



> (quasiquote (1 2 3))

(1 2 3)



> (quasiquote (1 2 (unquote a) (unquote b) 7))

(1 2 4 (5 6) 7)



> (quasiquote (1 2 (unquote a) (unquote-splicing b)))

(1 2 4 5 6)

The quasi-quote functions also provide convenient alternative syntaxes.

> `(1 2 ,a ,b 7)

(1 2 4 (5 6) 7)



> `(1 2 ,a ,@b 7)

(1 2 4 5 6 7)

Lists and recursion go together.

(define (element? x listarg)

  (and (list? listarg)

       (or (eq? x (car listarg))

           (element? x (cdr listarg)) ) ) )





(element? 1 '(1 2 3))



(element? 3 '(1 2 3))



(element? 3 '())



(element? 3 'foobar)

Discussions re: read-eval-print, PLT scheme, tail recursion vs. while,
accumulators, difference lists.

Accumulators, difference lists.

CPS - continuation passing style

  main idea: forces all calls to be tail recursive

  if there is additional work to be done after the call,then instead rewrite so
  as to pass the additional work onto the recusive call.

  May require introducing extra loop variables (args for the recusive call)

  Can always rewrite using CPS

  tail recusion is easily optimized into while loop.

For comparison, here are some Ruby examples illustrating tail recursion:

int fact(int i) {

  if (i == 1) then

    return 1;

  else

    int tmp := fact(i-1);

    tmp := tmp * i;      // need to do multiplication - more work after call

    return tmp;

  endif

}

Rewritten using "result" accumulator (or CPS)

# Ruby solution using tail recursion.



def fact(i)

  return fact_iter(i, 1);

end





def fact_iter(i, result)

  if (i == 1)

    return result

  else

    return fact_iter(i-1, result*i)

  end

end



print fact(5)

REWRITTEN AS LOOP

#Ruby solution as a loop.



def fact_loop(i)

  result = 1

  while (i != 1)

    i, result = i-1, result*i

  end



  return result

end



print fact_loop(5)

  delay and force in Scheme

  delay "promises" an expression to maybe evaluate later sometime

  force evaluates and memoizes the result

Nice example from the text.

(define naturals

  (letrec ((next (lambda (n) (cons n (delay (next (+1 n)))))))

    (next 1)))



(define head car)



(define (tail stream)

  (force (cdr stream)))

Alternatively, equivalent definition:

(define tail (lambda (stream) (force (cdr stream)))