ADD_HELPER

Lx.Ly.Lf.(((COND (ISZERO y)) x) (((f (SUCC x)) (PRED y)) f))

ADD

Lx.Ly.(((ADD_HELPER x) y) ADD_HELPER)

LISP

List Processing

In LISP, everything is a linked list.  Including the language itself.

Objects are lists, and even code is a list.

Everything is a linked list in the sense that you learned about Linked Lists in 122, 201, and 222.  Lists have a head node and an "everything else."  The "everything else" is of course another list.

If I have a list 1->2->3->4->5.

The head of the list is the 1.
And the "everything else" or the "rest" of the list is 2->3->4->5.

The empty list is designated by NIL.

LISP is a functional programming language.

Functions are themselves represented as lists.

(Fname arg1 arg2 arg3 ...) is how we represent functions.  (Rather than f(x,y), LISP uses (f x y).

One advantage (or is it...) of a functional language rather than an iterative language pertains to arithmetic:  There is no concept of order of operations.

3+5*8-2:  In a standard sane language, what does this evaluate to?  41
3+5*8-2:  On an old-fashioned calculator:  62
3+5*8-2:  APL Programming Language:  33

(- (+ 3 (* 5 8)) 2)

(first list) is the head element of the list.  Also (car list).
(rest list) is the rest of the list.  Also (cdr list).

You can nest lists.  Lists can contain other lists.  In fact, this happens a lot.

(cons f r) makes a list with the first element being f and the rest of the list being r.  So, r must be a list.  f is an element for the head.

I can use setf to change the first or rest of an existing list.  This is how we think of "reference parameters" in LISP.

In C, when we pass a pointer to a method, instead the stuff, we can change the stuff by following the pointer.  In C, all parameters are pass-by-value, a copy is made of the parameter, and all changes are made
to the copy.  But if we pass a pointer to the variable, it is the pointer that is copied.  We can still follow the pointer and change the original stuff.

int myfunc (int *a) { *a = 12; return 0;}
myfunc (&myvar);

C++
int myfunc (int &a) {a = 12; return 0;}
myfunc (myvar);


In LISP you might do something like:

(defun myfunc ((setf (first a) 12))
(myfunc (cons (a nil))

Lists serve the purpose of reference parameters.  You use lists for EVERYTHING in LISP.

C:\Users\apoe\Desktop\cs556-01-24w>clisp

C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe"  -K full
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]> (- (+ 3 (* 5 8)) 2)
41
[2]> (+ 3 (* 5 (- 8 2)))
33
[3]> quit

*** - SYSTEM::READ-EVAL-PRINT: variable QUIT has no value
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of QUIT.
STORE-VALUE    :R2      Input a new value for QUIT.
ABORT          :R3      Abort main loop
Break 1 [4]> abort
[5]> (quit)
Bye.

C:\Users\apoe\Desktop\cs556-01-24w>clisp

C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe"  -K full
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]> (1 2 3 4 5)

*** - EVAL: 1 is not a function name; try using a symbol instead
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead.
ABORT          :R2      Abort main loop
Break 1 [2]> abort
[3]> (list 1 2 3 4 5)
(1 2 3 4 5)
[4]> (setf a (list 1 2 3 4 5))
(1 2 3 4 5)
[5]> a
(1 2 3 4 5)
[6]> (first a)
1
[7]> (rest a)
(2 3 4 5)
[8]> (first (rest a))
2
[9]> (car a)
1
[10]> (cdr a)
(2 3 4 5)
[11]> (cadr a)
2
[12]> (caddr a)
3
[13]> (cadddr a)
4
[14]> (nth list 2)

*** - SYSTEM::READ-EVAL-PRINT: variable LIST has no value
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of LIST.
STORE-VALUE    :R2      Input a new value for LIST.
ABORT          :R3      Abort main loop
Break 1 [15]> (quit)
Bye.

C:\Users\apoe\Desktop\cs556-01-24w>clisp

C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe"  -K full
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]> (setf a (list 1 2 3))
(1 2 3)
[2]> (setf b (list 4 5))
(4 5)
[3]> a
(1 2 3)
[4]> b
(4 5)
[5]> (list a b)
((1 2 3) (4 5))
[6]> (length a)
3
[7]> (length b)
2
[8]> (setf c (list a b))
((1 2 3) (4 5))
[9]> c
((1 2 3) (4 5))
[10]> (length c)
2
[11]> (length (first c))
3
[12]> (length (rest c))
1
[13]> (length (first (rest c)))
2
[14]> (setf d (cons a b))
((1 2 3) 4 5)
[15]> (length d)
3
[16]> (setf e (cons 10 (cons 9 (cons 8 (cons 7 (cons 6 nil))))))
(10 9 8 7 6)
[17]> (setq z (list nil nil))
(NIL NIL)
[18]> z
(NIL NIL)
[19]> (length z)
2
[20]> (setf y (cons nil nil))
(NIL)
[21]> (first nil)
NIL
[22]> (rest nil)
NIL
[23]> (car nil)
NIL
[24]> (cdr nil)
NIL
[25]> (caddddddddddddddddddddr nil)

*** - EVAL: undefined function CADDDDDDDDDDDDDDDDDDDDR
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION 'CADDDDDDDDDDDDDDDDDDDDR).
RETRY          :R2      Retry
STORE-VALUE    :R3      Input a new value for (FDEFINITION 'CADDDDDDDDDDDDDDDDDDDDR).
ABORT          :R4      Abort main loop
Break 1 [26]> abort
[27]> (caddddddddddr nil)

*** - EVAL: undefined function CADDDDDDDDDDR
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION 'CADDDDDDDDDDR).
RETRY          :R2      Retry
STORE-VALUE    :R3      Input a new value for (FDEFINITION 'CADDDDDDDDDDR).
ABORT          :R4      Abort main loop
Break 1 [28]> abort
[29]> (caddr nil)
NIL
[30]> (cadddr nil)
NIL
[31]> (caddddr nil)

*** - EVAL: undefined function CADDDDR
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION 'CADDDDR).
RETRY          :R2      Retry
STORE-VALUE    :R3      Input a new value for (FDEFINITION 'CADDDDR).
ABORT          :R4      Abort main loop
Break 1 [32]> quit
[33]> (+ 1 nil)

*** - +: NIL is not a number
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead.
ABORT          :R2      Abort main loop
Break 1 [34]> (quit)
Bye.

C:\Users\apoe\Desktop\cs556-01-24w>clisp

C:\Users\apoe\Desktop\cs556-01-24w>"C:\Program Files\clisp-2.49\clisp.exe"  -K full
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]> (setf a (1 2 3 4 5))

*** - EVAL: 1 is not a function name; try using a symbol instead
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead.
ABORT          :R2      Abort main loop
Break 1 [2]> abort
[3]> (setf a (list 1 2 3 4 5))
(1 2 3 4 5)
[4]> a
(1 2 3 4 5)
[5]> (setf (first a) 17)
17
[6]> a
(17 2 3 4 5)
[7]> (setf (rest a) (list 4 2))
(4 2)
[8]> a
(17 4 2)
[9]> (< 4 7)
T
[10]> (> 4 7)
NIL
[11]> (= 5 5)
T
[12]> (!= 5 5)

*** - EVAL: undefined function !=
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION '!=).
RETRY          :R2      Retry
STORE-VALUE    :R3      Input a new value for (FDEFINITION '!=).
ABORT          :R4      Abort main loop
Break 1 [13]> abort
[14]> (<> 5 5)

*** - EVAL: undefined function <>
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION '<>).
RETRY          :R2      Retry
STORE-VALUE    :R3      Input a new value for (FDEFINITION '<>).
ABORT          :R4      Abort main loop
Break 1 [15]> abort
[16]> (not (= 5 5))
NIL
[17]> (/= 5 5)
NIL
[18]> (/= 4 5)
T
[19]> (if (= 1 2) (list 1 2 3 4 5) (list 6 7 8 9 10))
(6 7 8 9 10)
[20]> (load "nth.lisp")
;; Loading file nth.lisp ...
** - Continuable Error
DEFUN/DEFMACRO(NTH): #<PACKAGE COMMON-LISP> is locked
If you continue (by typing 'continue'): Ignore the lock and proceed
The following restarts are also available:
SKIP           :R1      skip (DEFUN NTH # ...)
RETRY          :R2      retry (DEFUN NTH # ...)
STOP           :R3      stop loading file C:\Users\apoe\Desktop\cs556-01-24w\nth.lisp
ABORT          :R4      Abort main loop
Break 1 [21]> abort
[22]> (load "nth.lisp")
;; Loading file nth.lisp ...
;; Loaded file nth.lisp
T
[23]> (setf a (1 2 3 4 5 6 7 8 9 10))

*** - EVAL: 1 is not a function name; try using a symbol instead
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead.
ABORT          :R2      Abort main loop
Break 1 [24]> abort
[25]> (setf a (list 1 2 3 4 5 6 7 8 9 10))
(1 2 3 4 5 6 7 8 9 10)
[26]> (nth a 0)

*** - NTH: (1 2 3 4 5 6 7 8 9 10) is not a non-negative integer
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead.
ABORT          :R2      Abort main loop
Break 1 [27]> abort
[28]> (poe-nth a 0)
1
[29]> (poe-nth a 8)
9
[30]> (reverse a)
(10 9 8 7 6 5 4 3 2 1)
[31]> (= nil nil)

*** - =: NIL is not a number
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead.
ABORT          :R2      Abort main loop
Break 1 [32]> abort
[33]> (equals nil nil)

*** - EVAL: undefined function EQUALS
The following restarts are available:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION 'EQUALS).
RETRY          :R2      Retry
STORE-VALUE    :R3      Input a new value for (FDEFINITION 'EQUALS).
ABORT          :R4      Abort main loop
Break 1 [34]> abort
[35]> (append (list 1 2 3) (list 4))
(1 2 3 4)
[36]> (load "nth.lisp")
;; Loading file nth.lisp ...
;; Loaded file nth.lisp
T
[37]> a
(1 2 3 4 5 6 7 8 9 10)
[38]> (poe-reverse a)
(10 9 8 7 6 5 4 3 2 1)
[39]> a
(1 2 3 4 5 6 7 8 9 10)
[40]> (poe-reverse a)
(10 9 8 7 6 5 4 3 2 1)
[41]> (load "nth.lisp")
;; Loading file nth.lisp ...
;; Loaded file nth.lisp
T
[42]> (poe-reverse nil)
NIL
[43]> (load "nth.lisp")
;; Loading file nth.lisp ...
;; Loaded file nth.lisp
T
[44]> (poe-reverse a)
(10 9 8 7 6 5 4 3 2 1)
[45]>