wiki:Bootstrapping8

Recap

The basis is just these few special forms and primitive procedures lambda define if quote unquote quasi-quote unquote-splicing cons car cdr null? apply The big idea is that everything else, up to an object system could be defined out of these lisp forms.

Another, even bigger idea is that we like to be able to reason about our code in the same way as we reason about this or that form of Calculus - using the Substitution Model enhanced with environments, which gives us the notion of a scope for symbols we use to denote values.

Like in Math, we are imagining that each time we write the symbol 3 which refers to the concept of Number 3 we think that evey time we are referring to the very same Number 3 - as many symbols 3 we had, that many references to the same value we got.

Same goes for bindings - associations between a symbol and a value. Once bound symbols cannot be rebound. When we bind the symbol x to the value of a Number 3 denoted by the symbol 3, as we said above, every time we see x it is the very same x.

According to the Substitution Model, we could replace every occurrence of the symbol x in our code to the symbol 3 without changing semantics of our code. Like in calculus, one could substitute equal for equal without breaking assertions.

As long as we have no assignment (or overwriting of values) we are sound. Once we change a value, we are in a mess. One should introduce a different binding instead or shadow the existent binding with a new one (within a scope).


There is an illustration of the principles described above.

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

(define foldl (lambda (f a xs)
                (if (null? xs)
                  a
                  (foldl f (f a (car xs)) (cdr xs)))))

Use foldl for commutative or left-associative binary operations
Use foldr for right-associative binary operations

Function composition - the way to chain procedures

(define compose (lambda (f g)
                  (lambda (x)
                    (f (g x)))))

(define flip (lambda (f)
               (lambda (x y)
                  (f y x))))

Mapping - applying a procedure to each element of a given list.

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

Appending (putting two lists together)

(define append (lambda (xs ys)
                 (foldr cons ys xs)))

Actually, append must take variable number of arguments

Filtering

(define (filter f xs)
   (foldr (lambda (x xs) (if (and (not (null? x)) (f x)) (cons x xs) xs)) '() xs))

Partial application

(define partially (lambda (f . as)
                    (lambda xs
                      (apply f (append as xs)))))

Concatenation (grouping)

(define concat (partially foldr append '()))

foldl1

(define (foldl1 f xs)
  (if (null? xs)
    (error "foldl1 on '()")
    (foldl f (car xs) (cdr xs))))

foldr1

(define (last? xs)
   (and (not (null? xs)) (null? (cdr xs))))

(define (foldr1 f xs)
   (cond ((null? xs) (error "foldr1 on '()"))
         ((last? xs) (car xs))
         (else (f (car xs) (foldr1 f (cdr xs))))))

These are fundamentals.

Notice how we are using nothing but application and composition of procedures to define a new procedures.

(define copy (partially foldr cons '()))

(define concat (partially foldr append '()))

(define reverse (partially foldl (flip cons) '()))

(define sum (partially foldl + 0))
(define product (partially foldl * 1))

(define maximum (partially foldl1 max))
(define minimum (partially foldl1 min))

; necessery wrapping
(define andl (partially foldl (lambda (x y) (and x y)) #t))
(define orl (partially foldl (lambda (x y) (or x y)) #f))

; algebra
((compose (partially map 1+) (partially map square)) '(1 2 3))

(define (all? f xs)
   ((compose andl (partially map f)) xs))

(define (any? f xs)
   ((compose orl (partially map f)) xs))

(define (elem x xs)
   (any? (partially eq? x) xs))

(define (take n xs)
  (cond ((<= n 0) '())
        ((null? xs) '())
        (else (cons (car xs) (take (- n 1) (cdr xs))))))

TODO:

partition p xs = foldr (select p) ([],[]) xs

select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

There is no for loops with updating of state variables. The *folding of a list* with boundary checking is encapsulated in the folding procedures and then reused (the DRY principle). This is the best way of programming - declarative composition, like in mach or music.

There are naive streams, out of the same building blocks. This illustrates the beauty of ADTs and the way to *embed* a DSL within a Lisp.

(define-syntax stream-cons
    (syntax-rules ()
        ((_ x xs)
            (cons x (delay xs)))))

(define (stream-cdr xs)
    (force (cdr xs)))

(define (stream-map f xs)
    (stream-cons (f (car xs)) (stream-map f (stream-cdr xs))))

(define (stream-filter f xs)
    (if (f (car xs))
        (stream-cons (car xs) (stream-filter f (stream-cdr xs)))
        (stream-filter f (stream-cdr xs))))

(define (stream-take n xs)
    (if (<= n 0)
        '()
        (cons (car xs) (stream-take (- n 1) (stream-cdr xs)))))

(define (repeat x)
    (stream-cons x (repeat x)))

(define (iterate f x)
    (stream-cons x (iterate f (f x))))

(define (replicate n x)
    (stream-take n (repeat x)))

(stream-take 5 (stream-filter odd?
    (stream-map (lambda (x) (* x x)) (iterate (lambda (x) (+ x 1)) 1))))
Last modified 3 years ago Last modified on Feb 27, 2017, 1:07:41 PM
Note: See TracWiki for help on using the wiki.