• tags :: lispfunctional programmingScheme

Some of my examples are written in Emacs Lisp, as at the time I hadn't installed a Scheme interpreter. It doesn't make a huge difference.

1. Toys

• an atom is a simple element, separated by spaces

• a list is a series of atoms, surrounded by parentheses

• s-expression :: an atom or a list

• car retrieves first element of list

  (car '(123))
  

  
  123
  
  

• cdr retrieves everything besides the first element of a list

  (cdr '(a b c))
  

• cons adds an atom to the front of a list

  (cons 100 '(a b c))
  (cons '(a b) '(c d))
  

• null tests for empty lists

  (null ())
  

  
  t
  
  

• atom tests for atoms

  (atom 123)
  

  
  t
  
  

• eq tests equality for non-numeric atoms

  (eq 'a 'b)
  

• always ask null? first!

• this chapter serves as a good introduction to recursion and tracing through lisp programs

3. Cons the Magnificent

• cons is for building lists

• important: when building lists from lists, figure out what the first element looks like, then recur over the cdr of the rest of the list

(defun firsts (l)
    (cond
    ((null l) '())
    (t (cons (car (car l)) (firsts (cdr l)) ))))

(firsts '((a b) (c d))) ;; => (a c)

5. Oh My Gawd: It's full of Stars

• In Scheme (and other Lisps?) a * suffix means "repeat this throughout the list." More specifically, it means to recur on the car of the list.

  For example:

  (rember* 'sauce ((tomato sauce) bean sauce)) ;; => ((tomato) bean)
  (rember 'sauce ((tomato sauce) bean sauce)) ;; => ((tomato) bean sauce)
  

• The first commandment says that, when recurring, you must ask between two to three questions. For a list of atoms, it's "~null?~" and "~else~", and for S-expressions, it's "~null?~", "~atom? (car l)~", and "~else~"

• The fourth commandment says that, when recurring, you must change at least one argument. When traversing over a list, decrement the list using cdr

• The sixth commandment is very important: "simplify only after the function is correct"

6. Shadows

• The Seventh Commandment :: Recur on the subparts that are of the same nature

• An attempt at value (for only +) in Emacs Lisp:

  (defun my-value (nexp)
    (cond
     ((atom nexp) nexp)
     ((eq (car (cdr nexp)) '+) (+ (value (car nexp)) (value (car (cdr (cdr nexp))))))
     (t nexp)))
  
  (my-value '(1 + 2))
  

  
  3