Android + Scheme
Got my first Android app working. Great that I could use Scheme to write native apps for this platform! (Thanks to Anand for letting me know that this is possible).
Got my first Android app working. Great that I could use Scheme to write native apps for this platform! (Thanks to Anand for letting me know that this is possible).
Started adding Backus' FP
primitives to Niue. Progress is
slow, sleep is overtaking me :–). A stack language is an apt vehicle
for FP as you get function composition and implicit argument passing
for free. Here is the famous inner-product example in Niue:
[ transpose '* apply-to-all '+ reduce ] 'inner-product ; 1 2 3 6 5 4 inner-product . => 28
This is how the call to inner-product got expanded:
1 2 3 6 5 4 transpose ( => 1 6 2 5 3 4 ) '* apply-to-all ( => (1 * 6) (2 * 5) (3 * 4) => 6 10 12 ) '+ reduce ( => (6 + 10 + 12) => 28 )
An interesting “language implementation exercise”!
Proficient programmers who are adept in a variety of paradigms and
languages recognize Design Patterns
as missing language
features. A new revelation
dawned on me today – a Design Pattern could be devised to work around
a wily language feature as well! I came to this realization after
reading about the Null Object
pattern. An entire
section of the book Object-Oriented Reengineering
Patterns
is dedicated to this topic, underlining the fact that the more
patterns you have in your code, the less expressive and
ill-designed the language you are using. Sometime back I wrote an
article on why NULL should
be removed from languages. If I had known about the Null Object
pattern then I would’ve saved some time by not writing this article,
as the existence of this pattern itself is a more convincing argument against the
case of NULL.
The notion of amortization is important in situations where we care
only about the total running time of a group of operations and don’t
care about the running time of each individual operation. For
instance, given a sequence of n operations, we may wish to bound the
total running time of the sequence by O(n) without insisting that each
individual operation run in O(1) time. We might be satisfied if a few
operations run in O(log n) or even O(n) time, provided the total cost
of the sequence is only O(n). The following implementation of aQueue
exploits the idea of amortization and provides O(1) snoc (insert)
and remove operations. This is achieved by using two internal lists,
one to represent the front of the queue and the other to represent the
tail. The implementation contains no mutable operation, so it can be safely shared by
concurrent processes without explicit synchronization:
(define (mk) (cons null null))
(define front car)
(define rear cdr)
(define (apply-invariant q)
(if (and (null? (front q))
(not (null? (rear q))))
;; reverse eats up the credits accumulated
;; by the elements in the list.
(cons (reverse (rear q)) null)
q))
;; Every snoc adds a credit of one to the new element.
(define (snoc q e)
(apply-invariant (cons (front q) (cons e (rear q)))))
(define (head q)
(if (not (null? (front q)))
(caar q)
null))
(define (tail q)
(if (not (null? (front q)))
(apply-invariant (cons (cdr (front q)) (rear q)))
(apply-invariant (cons null (rear q)))))
(define (remove q)
(if (not (null? (front q)))
(apply-invariant (cons (cdr (front q)) (rear q)))))Sample usage:
> (define q (snoc (snoc (snoc (mk) 1) 2) 3)) > q => ((1) 3 2) > (front q) => (1) > (tail q) => ((2 3)) > (snoc q 4) => ((1) 4 3 2) > (remove q) => ((2 3)) > (remove (remove q)) => ((3))
Every function except tail takes O(1) worst-case time, but tail
takes O(n) worst-case time. How is this cost amortized over time? This
is done by assigning each element of the rear list a credit of 1.
Every snoc into a non-empty queue takes one actual step and
allocates a credit to the new element of the rear list, for an
amortized cost of two.
Every tail that does not reverse the rear list takes one actual step
and neither allocates nor spends any credits, for an amortized cost of
one. Finally, every tail that does reverse the rear list takes m + 1
actual steps, where m is the length of the rear list, and spends the
m credits contained by that list, for an amortized cost of m + 1 -
m = 1.
Reference: Purely Functional Data Structures by Chris Okasaki
Just made sure that I haven’t forgotten how to sort :–) First let me do it quick:
(define (qsort e)
(if (or (null? e) (<= (length e) 1)) e
(append (append (qsort (filter (cdr e) (lambda (x) (<= x (car e))))) (list (car e)))
(qsort (filter (cdr e) (lambda (x) (> x (car e))))))))This next version of qsort tries to get rid of the two passes to
filter the list but that made the code lengthier:
(define (qsort e)
(if (or (null? e) (<= (length e) 1)) e
(let loop ((left null) (right null)
(pivot (car e)) (rest (cdr e)))
(if (null? rest)
(append (append (qsort left) (list pivot)) (qsort right))
(if (<= (car rest) pivot)
(loop (append left (list (car rest))) right pivot (cdr rest))
(loop left (append right (list (car rest))) pivot (cdr rest)))))))Here is a version of merge-sort:
(define (split e)
(let loop ((f null) (r null) (i (/ (length e) 2)) (e e))
(if (not (null? e))
(if (> i 0)
(loop (cons (car e) f) r (sub1 i) (cdr e))
(loop f (cons (car e) r) i (cdr e)))
(cons (reverse f) (reverse r)))))
(define (merge a b)
(let loop ((res null) (a a) (b b))
(if (or (not (null? a)) (not (null? b)))
(cond
((and (not (null? a)) (not (null? b)))
(if (> (car a) (car b))
(loop (cons (car b) res) a (cdr b))
(loop (cons (car a) res) (cdr a) b)))
((not (null? a))
(loop (append (reverse a) res) null b))
(else
(loop (append (reverse b) res) a null)))
(reverse res))))
(define (merge-sort e)
(if (or (null? e) (<= (length e) 1)) e
(let* ((halves (split e))
(left (merge-sort (car halves)))
(right (merge-sort (cdr halves))))
(merge left right))))Reading the Turing Award lecture(pdf) by John Backus. This is probably one of the most accessible introductions to functional programming.
Did some FP exercises in Python:
# function is defined as inner_product: # [a,b,c] * [x,y,z] = [(a * x) + (b * y) + (c * z)] def inner_product(x, y): return reduce(add, map(mult, zip(x, y))) # where mult and add are defined as: def mult(x): return x[0] * x[1] def add(x, y): return x + y # in a FP language, + and * are first-class functions, so we don't # need to specially def them. #test >>> inner_product([1, 2, 3], [6, 5, 4]) 28
Contrast this with the imperative equivalent, where we have to say how to do it, not what to do:
def inner_product(x, y): c = 0 n = len(x) for i in range(n): c = c + x[i] * y[i] return c
The imperative inner_product operates on “state” and one should mentally execute the code to understand it. In contrast, the functional version specifies how we want to transform the data to produce an expected result. This is closer to how we visualize the solution for a given problem. For instance, consider how the FP inner_product evaluated the sample input:
zip([1, 2, 3], [6, 5, 4]) => [(1,6), (2, 5), (3, 4)]map(mult, [(1,6), (2, 5), (3, 4)]) => [6, 10, 12]reduce(add, [6, 10, 12]) => 28Here is a function to multiply matrices, in functional style:
def matrix_mult(m, n): return map(lambda(e): map(lambda(k): reduce(add, map(mult, k)), e), # inner_product() without zip :-) cross_zip(m, n)) # where cross_zip is defined as: def cross_zip(x, y): n = zip(*y) return map(lambda(e): map(lambda(k): zip(e, k), n), x) # test > m = [[1, 2, 3], [4, 5, 6]] > n = [[10, 20], [30, 40], [50, 60]] > print matrix_mult(m, n) [[220, 280], [490, 640]] > m = [[0, -1, 2], [4, 11, 2]] > n = [[3, -1], [1, 2], [6, 1]] > print matrix_mult(m, n) [[11, 0], [35, 20]] > print matrix_mult(n, m) [[-4, -14, 4], [8, 21, 6], [4, 5, 14]] > m = [[8, 9], [5, -1]] > n = [[-2, 3], [4, 0]] > print matrix_mult(m, n) [[20, 24], [-14, 15]]
Next step: redefine matrix_mult() directly in terms of inner_product() …
