wiki:Ch4

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''

Last modified 2 years ago Last modified on Sep 3, 2017, 7:28:48 AM
Note: See TracWiki for help on using the wiki.