# Idealized world

Primitives and special forms

• LAMBDA, DEFINE, IF, NOT, AND, OR, ERROR
• '(), NULL?
• CONS, CAR, CDR, PAIR?
• QUOTE, UNQUOTE, UNQUOTE-SPLICING, DEFINE-SYNTAX (defmacro)

Naive assumptions

• Cons-ing is an efficient operation.
• Non tail-call recursion is OK.
• Stack space is unlimited.
• Dotted-lists do not exist.
• Only fixed-arity procedures.

Esoteric Lisp expressions:

```((lambda (x) x) (lambda (x) x))
;Value 13: #[compound-procedure 13]

(define id ((lambda (x) x) (lambda (x) x)))

((lambda xs xs))
;Value: ()

(define list (lambda xs xs))
```

ASSERT

```(define-syntax :assert
(syntax-rules ()
((ASSERT condition . extra)
(IF (NOT condition)
(ERROR "Assertion failed:" 'condition . extra)))))
```

Laws

`'()` is NOT a Pair - it is an Atom - it has no structure

```1 ]=> (pair? '())
;Value: #f
```

`'()` is a List

```1 ]=> (list? '())
;Value: #t
```

Pair is NOT a List (it is an Improper list or a Dotted List)

```1 ]=> (list? (cons 1 2))
;Value: #f
```

However a proper List is a Pair

```1 ]=> (pair? '(1))
;Value: #t
```

Beautiful, recursive, fixed-arity procedures on proper Lists.

In Common Lisp `'()` is BOTH an Atom and a List (and obviously not a Pair)

```(define (atom? x)
(not (pair? x)))
```

Assuming no Dotted Lists

```(define (list? xs)
(or (null? xs) (pair? xs)))
```

Beautiful and naive recursive `length`

```(define (length xs)
(if (null? xs)
0
(+ 1 (length (cdr xs)))))
```

`append`

```(define (append xs ys)
(if (null? xs)
ys
(cons (car xs)
(append (cdr xs) ys))))
```

and `map`

```(define (map f xs)
(if (null? xs)
'()
(cons (f (car xs))
(map f (cdr xs)))))
```

as one might easily see `map` of `id` produces a copy, because `map` conses

```(map (lambda (x) x) '(1 2 3))
;Value 13: (1 2 3)
```

or

```copy  =  map id
```

There is `for-each` for side-effects

```(define (for-each f xs)
(if (not (null? xs))
(begin (f (car xs))
(for-each f (cdr xs)))))
```

with Common Lisp style `unless` - with implicit `progn`

```(define-syntax :unless
(syntax-rules ()
((unless condition form ...)
(if (not condition)
(begin form ...)))))
```

it looks even more beautiful

```(define (for-each f xs)
(unless (null? xs)
(f (car xs))
(for-each f (cdr xs))))
```

membership predicate

```(define (member? x xs)
(cond ((null? xs) #f)
((eq? x (car xs)) #t)
(else (member? x (cdr xs)))))
```

;;; Common Lisp style `member` which returns the form

```(define (member x xs)
(cond ((null? xs) #f)
((eq? x (car xs)) (car xs))
(else (member x (cdr xs)))))
```

classic `filter` in an classic old-school style

```(define filter (lambda (f xs)
(cond ((null? xs) '())
((f (car xs)) (cons (car xs)
(filter f (cdr xs))))
(else (filter f (cdr xs))))))
```

and classic recursive right-fold or `reduce`

```(define foldr (lambda (f z xs)
(if (null? xs)
z
(f (car xs) (foldr f z (cdr xs))))))
```

so we could define `map` in terms of it, encapsulating traversal

```(define (map f xs)
(foldr (lambda (x xs) (cons (f x) xs)) '() xs))
```

Happy, Happy! Joy, Joy''