Learning Clojure

Search This Blog

Loading...

Sunday, December 6, 2015

Define Macro


;; When I say

(def a (* 4 5)) ;-> #'user/a

;; I'd rather the repl told me that I'd just assigned the value 20 to
;; something rather than that I'd just assigned something to user/a

a ;-> 20

;; A macro for this is easy

(defmacro define [var expr]
  `(let [tmp# ~expr]
     (def ~var tmp#) tmp#))

(define a (* 4 5)) ;-> 20

;; I'd also like to be able to say, in a scheme-like manner

'(define (square x) (* x x))

;; meaning
(defn square [x] (* x x)) ; #'user/square

;; So I can modify my define macro so:

(defmacro define [var expr]
  (cond (symbol? var)  `(let [tmp# ~expr] (def ~var tmp#) tmp#)
        (list? var)  `(defn ~(first var) ~(into [] (rest var)) ~expr)))

(macroexpand '(define a (* 20 20))) ;-> (let* [tmp__1986__auto__ (* 20 20)] (def a tmp__1986__auto__) tmp__1986__auto__)
(macroexpand '(define (square x) (* x x))) ;-> (def square (clojure.core/fn ([x] (* x x))))

(define a (* 20 20)) ; 400
(define (cube x) (* x x x)) ;-> #'user/cube
(cube 20) ;-> 8000

;; I must say, I haven't actually tried this in practice yet, but it looks like it might work

(define (random-error)
  (+ (rand) -0.5)) ;-> #'user/random-error

(random-error) ;-> -0.28442993770155234
(random-error) ;-> 0.2911519817783499
(random-error) ;-> -0.4037254523155406

(define bell (/ (reduce + (repeatedly 10 random-error)) 10)) ;-> 0.015416035491431623

;; I'm sure someone will let me know if it's broken.

;; This is a bit sub-optimal:
(define square (fn[x] (* x x))) ; #function[user/eval8586$tmp--8558--auto----8587]

;; Any suggestions for improvements?

Sunday, November 29, 2015

Contract Programmer Seeks Job in Cambridge (£500 reward)

I'm looking for a job, and as usual I'll pay a commission of £500 to anyone who can find me a good one.

Details here: http://johnlawrenceaspden.blogspot.co.uk/2015/11/contract-programmer-seeks-job-in.html

CV here: http://www.aspden.com

Obviously Clojure is a speciality, and I'd love a Clojure job, but I can program in all styles.

My other favourite languages are C, Python, and ML. All of them seem to hit a sweet spot where they're just the best tool for certain tasks.

If you're a local company using Java, who might be interested in giving Clojure a try, I'd love to try to show you what all the fuss is about.

Sunday, November 22, 2015

An Introduction to the Lambda Calculus


;; Done Twice as a "Dojo" at Villiers Park on Thursday 19th March 2015
;; To groups of about 15 ultra-clever teenagers who were thinking about doing Computer Science at university

;; The first group got as far as higher order functions in an hour.

;; The second group went a bit faster, and we had a bit more time, about an hour and a half,
;; and so we got right to iterative-improve and finding square roots of anything using it.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Environment DrRacket (version 6.1)
;; Language R5RS (Revised Revised Revised Revised Revised Report on the Algorithmic Language Scheme)
;; One person sits at the computer, one person helps them, the rest tell them what to do
;; Every time they achieve something significant, rotate audience->copilot->pilot->audience
;; Notes on back of hand: 
(define crib 
  '( 2 3 + (+ 2 3) lambda define square < #t #f if abs Heron average improve make-improver error good-enough good-enough-guess iterative-improve ))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Introduction to the Lambda Calculus

;; More precisely, an introduction to the algorithmic language Scheme, which is what you get if you start with 
;; the lambda calculus and you trick it out with some extra stuff that often comes in handy, true and false and if 
;; and define and also some types of numbers, like integers and fractions, and adding, and multiplying.

;; You can build all that stuff starting from scratch with just lambda, and it's a nice thing to do if you want 
;; to understand how it all works, but I reckon you're already ok at that sort of thing. 

;; So we'll start from something that can do basic arithmetic, and we'll learn how to find square roots of things.

;; This is an evaluator. You can ask it the values of things.

2
3
+

;; We can apply the procedure to the two numbers

(+ 2 3)


;; Can you tell me the square of 333?

(* 333 333)

;; The brackets mean (work out the value of the things in the brackets, and then do the first thing to the other things)

;; So what do you get if you add the squares of 3 and 4?

(+ (* 3 3) (* 4 4))


;; We have procedures for * and + , but if we ask the evaluator what & means, or what square means
;; it will just say 'I have no clue'.

;; It might be nice if we had a procedure for squaring things

;; How you make a procedure is with this thing called lambda, which is sort of a rewriting sort of thing.

;; Try (lambda (x) (* x x)), which means 'make me a thing which, when I give the thing x, gives me the value of (* x x) instead' 

(lambda (x) (* x x))

;; #<procedure>, it says, which is very like what you get when you type in +, and it says #<procedure:+>.

;; So we hope we've made a procedure like + or *

;; How shall we use it to get the square of 333?

((lambda (x) (* x x)) 333)

;; Now obviously, typing out (lambda (x) (* x x)) every time you mean square is not brilliant, 
;; so we want to give our little squaring-thing a name.

(define square (lambda (x) (* x x)))

;; Now how do we find the square of 333?

(square 333) ; 110889

;; So lambda is allowing us to make new things, to turn complicated procedures into simple things 

;; and define is allowing us to give things names

;; So now let's make a procedure that takes two things, and squares them both, 
;; and adds the squares together, and let's call it pythag

(define pythag 
  (lambda (x y) 
    (+ (square x) (square y))))

(pythag 3 4)

;; OK, great, now can you figure out how the procedure < works?

( < 3 4)
( < 4 3)
( < 3 4 6)
( < 3 4 2)

;; Notice that these #t and #f things are things that the evaluator knows the value of:
;; They're called true and false.

#f
#t

;; So now the last piece of the puzzle:

;; if takes three things:

(if #t 1 2) ;1
(if #f 1 2) ;2

;; So we've got numbers and *,+,-,/, and we've got #t #f and if, and we've got lambda, and define

;; And so all the stuff we've got above, we can think of it as a reference manual for a little language.

;; We can build the whole world out of this little language.

;; That's what God used to build the universe, and any other universes that might have come to His mind.
;; And we can use it too.

;; Here's the manual

2
*
(* 2 3)
(define forty-four 44)
forty-four
(lambda (x) (* x x))
((lambda (x) (* x x)) 3)
(if (< 2 3) 2 3)

;; And if we understand these few lines, then we understand the whole thing, and we can fit the little pieces together like this:

(define square (lambda (x) (* x x)))
(square 2)

;; So now I want you to use the bits to make me a function, call it absolute-value, which if you give it a number gives you back
;; the number, if it's positive, and minus the number, if it's negative.

(define absolute-value (lambda (x) (if (> x 0) x (- x))))

(absolute-value 1)
(absolute-value -3)
(absolute-value 0)

;; So I've taught you most of the rules for Scheme, which is a sort of super-advanced lambda calculus, and so if you understand 
;; the bits above, then you've got the hang of the lambda calculus plus some more stuff.

;; And it's a bit like chess. The rules of chess are super-simple, you can explain them to babies, 
;; like Dr Polgar did to Judit and her sisters.
;; But that doesn't make the babies into good chess players yet. They have to practise.

;; How are we doing for time? We've done the whole of the lambda calculus, plus some extra bits. We should feel pretty smug.

;; (In both cases, this had taken about 35 minutes)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Let's do a little practice exercise. Like a very short game of chess, now I've explained most of the rules.

;; So once upon a time there was this guy, believe it, called 'Hero of Alexandria'.

;; Or sometimes he seems to have been called 'Heron of Alexandria', like Hero was the short version, 
;; like he was sometimes called Jack and sometimes called John.

;; Whatever, Hero invented the syringe, and the vending machine, and the steam engine, and the windmill, and the rocket, 
;; and the shortest path theory of reflection of light, and did some theatre stuff, 
;; and he was like Professor of War at the big library in Alexandria.

;; You get the impression that if Alexandria had lasted just a little bit longer, 
;; the whole industrial revolution would have kicked off right there, and the Romans would have walked on the moon in about AD400.

;; And we'd all be immortal, and live amongst the stars. So you should take the fall of the Roman Empire *very* personally.

;; And one of his things was a way of finding the square roots of numbers, 
;; which is so good that it was how people found square roots right up until the invention of the computer.

;; So I'm going to explain that method to you, and you're going to explain it to this computer, and then you can get the computer
;; to calculate square roots for you, really fast. And after that you're only a couple of steps away from cracking the 
;; Enigma codes and winning the second world war and inventing the internet and creating an artificial intelligence 
;; that will kill us all just 'cos it's got better things to do with our atoms. I'm not joking.

;; So careful.... What I've just given you is the first step on the path that leads to becoming a mighty and powerful wizard.
;; And with great power comes great something or other, you'll find it on the internet, so remember that.

;; PAUSE

;; So imagine you want to find the square root of 9. And you're a bit stuck, so you say to your friend, "What's the square root of nine?", and he says it's three.

;; How do you check?

(* 3 3)

;; Bingo. There's another way to check

(/ 9 3)

;; That's what it means to be the square root of something. If you divide the something by the square root, you get the square root back.

;; But what if your friend had said "err,.. 2 or something?"

(/ 9 2)

;; Notice that the number you put in is too low, but the number you got back is too high.

;; So Heron says, let's take the average.

;; So we need an average function

(define average (lambda (a b) (/ (+ a b) 2)))

(average 2 (/ 9 2)) ; 3 1/4

;; three and a quarter, that's like a much better guess, it's like you'd found a cleverer friend.

;; so try again.

(average 3.25 (/ 9 3.25)) ; 3.009615...

;; and again 

(average 3.0096 (/ 9 3.0096)) ; 3.0000153..

(average 3.0000153 (/ 9 3.0000153)) ; 3.000000000039015

;; So you see this little method makes guesses at the square root of nine into much better guesses.

;; We see that this is kind of a repetitive type thing, and if you see one of those, your first thought should be, 
;; I wonder if I can get the computer to do that for me?

;; Can you make a function which takes a guess at the square root of nine, and gives back a better guess?

(define improve-guess (lambda (guess) (average guess (/ 9 guess))))

;; I'd better show you how to format these little functions so that they're easier to read

(define improve-guess 
  (lambda (guess) 
    (average guess (/ 9 guess))))

;; The evaluator doesn't notice the formatting, and it makes it a bit more obvious what's getting replaced by what.

(improve-guess 4) ; 3 1/8
(improve-guess (improve-guess 4)) ; 3 1/400
(improve-guess (improve-guess (improve-guess 4))) ; 3 1/960800

;; We all know what the square root of nine is, let's look at a more interesting number, two. 
;; It's a bit of an open question whether 'the square root of two' is a number, or whether it's just a noise 
;; that people make with their mouths shortly after you show them a square and tell them about Pythagoras' theorem.

;; Pythagoras used to have people killed for pointing out that you couldn't write down the square root of two.

;; I've got a bit of a confession to make. 

;; Someone's already explained to this computer how to find square roots

(sqrt 9)          ; so far so good!
(sqrt 2)          ; 1.4142135623730951   hmmm. let's check.

(square (sqrt 2)) ; 2.0000000000000004

;; So it turns out that this guy's just said, if you can't come up with the square root of two, just lie, and come up with something
;; that works, close as dammit. 

;; Which is like, bad practice, and tends to lead to Skynet-type behaviour in the long run.

;; So let's see what Hero would have said about it.

;; We need a new function that makes guesses better at being square roots of two.
;; It's a bit dirty, but let's just call that improve-guess as well.

;; That's called redefinition, or 'mutation', and it's ok when you're playing around, 
;; but it's a thing you should avoid when writing real programs, because, you know, Skynet issues.

;; Hell, no-one ever got more powerful by refraining from things.

(define improve-guess 
  (lambda (guess) 
    (average guess (/ 2 guess))))

;; Anyone make a guess? 

(improve-guess 1) ; 1 1/2

;; Any good?

(square (improve-guess 1)) ; 2 1/4

;; How wrong?

(- (square (improve-guess 1)) 2) ; 1/4

;; OK, I want you to notice that we've just done the same thing twice

(define improve-guess-9 (lambda (guess) (average guess (/ 9 guess))))
(define improve-guess-2 (lambda (guess) (average guess (/ 2 guess))))

;; Now whenever you see that you've done the same thing twice, and there's this sort of grim inevitability 
;; about having to do it a third time someday, you should think:

;; Hey, this looks like exactly the sort of repetitive and easily automated task that computers are good at.

;; And so now I want you to make me (and this is probably the hard bit of the talk...) a function which 
;; I give it a number and it gives me back a function which makes guesses at square roots of the number better.

(define make-improve-guess
  (lambda (n)
    (lambda (guess)
      (average guess (/ n guess)))))

;; And now we can use that to make square root improvers for whatever numbers we like

(define i9 (make-improve-guess 9))

(i9 (i9 (i9 (i9 1)))) ; 3 2/21845


(define i2 (make-improve-guess 2))

(i2 (i2 (i2 (i2 1)))) ; 1 195025/470832

;; The first group got this far in about an hour, which was all we had time for, and then we stopped and I waffled for a bit.

;; Now how good are our guesses, exactly?

(- 2 (square (i2 (i2 (i2 (i2 1))))))

;; We could totally make a function out of that:

(define wrongness (lambda (guess) (- 2 (square guess))))

(wrongness (improve-guess 1)) ; -1/4
(wrongness (improve-guess (improve-guess 1))) ; -1/144
(wrongness (improve-guess (improve-guess (improve-guess 1)))) ; -1/166464
(wrongness (improve-guess (improve-guess (improve-guess (improve-guess 1))))) ; -1/221682772224

;; So we're getting closer! When should we stop? Let's say when we're within 0.00000001

(define good-enough? (lambda (guess) (< (absolute-value (wrongness guess)) 0.00000001)))

(good-enough? (improve-guess (improve-guess 1)))  ; #f

(good-enough? (improve-guess (improve-guess (improve-guess (improve-guess 1))))) ; #t

;; Now, we're doing a bit too much typing for my taste.

;; What we want to do is to say:

;; I'll give you a guess. If it's good enough, just give it back. If it's not good enough, make it better AND TRY AGAIN.

;; This is the hard bit. We need to make a function that calls itself.

;; Go on, have a go

(define good-enough-guess 
  (lambda (guess)
    (if (good-enough? guess) guess
        (good-enough-guess (improve-guess guess)))))


(good-enough-guess 1) ; 1 195025/470832

;; YAY VICTORY!


;; The second group got this far in about an 1hr 10 mins, but they all still seemed keen and we didn't have to stop, so:

;; Now this is as much of the talk as I'd written,
;; but actually we've got the time to go a little bit further, if your brains haven't totally exploded, and you might like the next bit, 
;; because it makes a nice punchline to the whole thing:

;; There's a pattern here, and it's called iterative-improve

;; And iterative improvement is everywhere in the world, for instance you probably got shown the Newton-Raphson solver at school, 
;; which is a thing which can find roots of all sorts of equations very fast, and it works like this, you have an initial guess, and 
;; Newton Raphson is a way of making a guess into a better guess, and you need to know when the answer is good enough so you can stop.

;; Or this morning I had a shower, and I got in the shower and I turned the water on to just a random position and it was too hot, so I turned the handle
;; a bit the other way and it was a bit too cold, so I turned it back just a bit and then it was ok so I stopped.

;; And that's the same pattern, and you see this sort of thing all over, it is how you solve big matrices and so on and so forth.

;; And we have just discovered this pattern, which is kind of a fundamental building block when you're writing programs, like a for loop is another basic pattern.

;; So let's see if we can make a function that takes a guess and a way of improving guesses and a way to tell if we're done yet, and gives us back an answer.

(define iterative-improve
  (lambda (guess improve good-enough?)
    (if (good-enough? guess) guess
        (iterative-improve (improve guess) improve good-enough?))))

(iterative-improve 1 (make-improve-guess 2) good-enough?) ; 1 195025/470832



;; This was where we stopped the second session. Here's some waffle:



;; And I think now you can see that we've abstracted a pattern here that will come in handy for the sorts of things that we're trying to do.

;; That's what this talk has really been about, how to build a language which allows you to solve the problems that you're interested in.

;; So I'd like to tidy up the program that we've just written, and put it into the sort of form that I'd have written it in, if I'd been solving this problem
;; and I'd played around for a bit and found what I thought was a nice expression of the ideas that we've been talking about.

(define square (lambda (x) (* x x)))

(define absolute-value (lambda (x) (if (> x 0) x (- x))))

(define make-improve-guess
  (lambda (n)
    (lambda (guess)
      (average guess (/ n guess))))) ; this bit is Heron's method

(define make-good-enough? 
  (lambda (n tolerance) 
    (lambda (guess)
      (> tolerance
         (absolute-value (- n (square guess)))))))
 
(define iterative-improve
  (lambda (guess improve good-enough?)
    (if (good-enough? guess) guess
        (iterative-improve (improve guess) improve good-enough?))))

(define make-square-root
  (lambda (guess tolerance)
    (lambda (n)
      (iterative-improve guess (make-improve-guess n) (make-good-enough? n tolerance)))))


;; We can use these bits to make the sort of square root we usually find provided:
(define engineer-sqrt (make-square-root 1.0 0.00000000000001 ))

(engineer-sqrt 2)

;; And here's what we might use, if we needed really good square roots for some reason:
(define over-cautious-engineer-square-root (make-square-root 1 1/1000000000000000000000000000000000000000000000000000000000000000000))

(over-cautious-engineer-square-root 2)

;; And I hope you can see this this program is actually built of lots of tiny simple pieces, 
;; all of which you can understand, and most of which you'll be able to reuse in other contexts.

;; In particular, iterative-improve is a terribly general thing which you can use in lots of ways.

;; And it might have taken us a while to write, although we wrote it as part of a learning-the-language finger-exercise, 
;; but we never have to write it again. It works and it will keep working and we've got in the bank now.

;; Here's the take-home message:

;; If you've got a problem, build yourself a language to solve the problem in. 

;; To do that, you need to start with a language that allows you to abstract what you do into simple pieces
;; which are easy to understand, so that you can see that they're right and they aren't too snarled up with 
;; the little details of the problem you're working on at the moment.

;; And you need a language that allows you to combine the little pieces easily
;; to make new pieces that solve the problem that you're trying to deal with.

;; And there's a sense in which all computer languages are just this lambda calculus.

;; We've done all this in Scheme, which is lambda calculus plus some extra stuff.

;; There's nothing we've done here that can't be done in python, or in ruby, or in perl or in haskell or in lisp.

;; What distinguishes these languages is what extra stuff has already been added to them. 

;; But if a language is good enough, and none of the usual features have actually been taken away, 
;; which does happen sometimes, then if there's anything missing that you need you can always add it yourself.

;; And then you can use the language that you have to build the language that you need.

;; In a sense, making languages is itself an iterative improvement process. 

;; And the big questions are always:

;; How do we make things better? What's good enough? When are we done?





















;; Postscript


;; I'll show you a trick now. We've been using it all along and nobody noticed, 
;; but it's the sort of thing that looks like magic, and I don't like magic unless I can cast the spells myself.

(good-enough-guess 1)   ; 1 195025/470832
(good-enough-guess 1.0) ; 1.4142135623746899

;; This is called 'contagion'. There are really two types of numbers.

;; Numbers that look like 432/123 are called 'exact', or 'vulgar fractions'
;; Numbers that look like 1.4142 are called 'inexact', or 'approximate', or 'floating point', or 'decimal fractions'

;; The first type are the sort of numbers that children learn about in school, and that mathematicians use.

;; And the second type are the sort of numbers that engineers use, and they're actually quite a lot more complicated and fuzzy
;; than the exact type. They just sort of work like 'if it's very close, then it's good enough'.

;; The way most computers think about them, they keep about sixteen digits around, and if you want more than that, tough luck.

;; But for some purposes they're better, for instance they're easier to read, and it's a bit of a matter of taste.

;; If you multiply or add an inexact number to an exact number, the answer is always inexact.
;; You can't unapproximate something.

(/ 1 3)   ; 1/3
(/ 1.0 3) ; 0.3333333333333333

;; We all know that 1/3 isn't really 0.33333333333333

;; Mathematicians worry about that sort of thing. Engineers don't. Sometimes aeroplanes crash. Mostly they don't.











Sunday, February 15, 2015

Destructuring Clojure Maps


;; Destructuring Clojure's Maps

;; I can never ever remember how this works, so here is a note to self:

((fn [{a :a}] a) {:a 1}) ; 1

;; And by let-lambda isomorphism

(let [{a :a} {:a 1}] a) ; 1

;; Why on earth is the syntax the wrong way round? Why can't {:a a} match {:a 1}?

;; Similarly

((fn [{a :a b :b}] [a b]) {:a 1 :b 2}) ; [1 2]

(let [{a :a b :b} {:a 1 :b 2}] [a b]) ;  ; [1 2]

;; And with the common pattern where the variables are like the keys:

((fn [{:keys [a b]}] [a b]) {:a 1 :b 2}) ; [1 2]

(let [{:keys [a b]} {:a 1 :b 2}] [ a b ]) ; [1 2]


;; We can destructure recursively (although we may not be wise to if we keep forgetting how it works!)

((fn [{a :a {c :c d :d} :b}] [a c d]) {:a 1 :b {:c 2 :d 3}}) ; [1 2 3]

(let [{a :a {c :c d :d} :b} {:a 1 :b {:c 2 :d 3}}] [a c d]) ; [1 2 3]

;; And we can remember the keys entire on which we have recursed, so:

(let [{a :a {c :c d :d :as b} :b}
      {:a 1 :b {:c 2 :d 3}}]
  [a b c d]) ;-> [1 {:c 2, :d 3} 2 3]


;; Finally a 'real' example, a ring request map containing parameters and a session, both of
;; which have substructure

(def ring-request
  {:params {:action "a" :key "k" :spurious "sp"}
   :session {:data "d" :state "s"}
   :irrelevant "irr"})

;; So the parameters we're interested in look like
{:params {:action :key} :session {:data :state}}

;; And we can extract all the pieces, naming each part, like so:

(defn process-request [{{action :action key   :key   :as params } :params
                        {data   :data   state :state :as session} :session :as request}]
  (println action)
  (println key)
  (println data)
  (println state)
  (println params)
  (println session)
  (println request))

(process-request ring-request)
;; a
;; k
;; d
;; s
;; {:key k, :action a, :spurious sp}
;; {:state s, :data d}
;; {:irrelevant irr, :params {:key k, :action a, :spurious sp}, :session {:state s, :data d}}

Sunday, October 19, 2014

A Classic Puzzle


;; A Classic Puzzle

;; This problem, my sources inform me, can be solved by pre-school
;; children in 5-10 minutes, by programmers - in 1 hour, and by
;; mathematicians ... well, check it yourself! :)

(def input (quote ("8809" "7111" "2172" "6666" "1111" "3213" "7662" "9313" "0000" "2222" "3333" "5555" "8193" "8096" "7777" "9999" "7756" "6855" "9881" "5531")))

(map classic input) ;-> (6 0 0 4 0 0 2 1 4 0 0 0 3 5 0 4 1 3 5 0)

;; What is:
(classic "2581")

;; What is classic ?

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Just to make it a bit easier to read

(map (juxt identity classic) input) ;-> 

["8809" 6]
["7111" 0]
["2172" 0]
["6666" 4]
["1111" 0]
["3213" 0]
["7662" 2]
["9313" 1]
["0000" 4]
["2222" 0]
["3333" 0]
["5555" 0]
["8193" 3]
["8096" 5]
["7777" 0]
["9999" 4]
["7756" 1]
["6855" 3]
["9881" 5]
["5531" 0]



Thursday, June 26, 2014

I Wish I'd Written This

Nothing specifically  to do with clojure, but I figure that a fair number of readers of this blog must love algorithms and visualizations, and this:

http://bost.ocks.org/mike/algorithms/

is one of the best things I've ever read on those subjects. I really wish I'd written this! Or even was capable of writing this.

Tuesday, May 20, 2014

Planes In Space : Random Sampling


;; My recursion tells me that n planes can divide space into
;; 2, 4, 8, 15, 26, and finally 42 regions.

;; But I'd like some sort of empirical confirmation of this result.

;; Forms in 3-space can be represented as ordered sets of three numbers
(def a-form [1 2 3])

;; As can vectors
(def a-point [2 3 5])

;; And we evaluate the form on the vector
(defn contract [form vector]
  (reduce + (map * form vector)))
;; (or if you prefer, take the dot product, or contract the tensors)

(contract a-form a-point) ;-> 23

;; Any plane can be defined in terms of a 1-form and a number.  
(def a-plane {:form [1 2 3] :val 4})

;; Now if we have a plane or a vector, we can evaluate the form on the
;; vector, and compare the result with the value. This tells us which
;; side of the plane the vector is on.

(defn side [plane point]
  (- (contract (plane :form) point) (plane :val)))


(side a-plane [2 3  5]) ;-> 19  (this point is on the positive side)
(side a-plane [2 3 -5]) ;-> -11 (on the negative side)
(side a-plane [2 3 -4/3]) ;-> 0N (in the plane itself)


;; Ok, now we need a way of taking vectors and forms at random. 
;; The cauchy distribution is easy to sample from and has nice fat tails

(defn cauchy[]
  (Math/tan (* Math/PI (- (rand) 0.5))))

(repeatedly 20 cauchy) ;-> (-0.43989542100474244 -0.6517139433588255 1.58518947555566 0.001268073580101198 3.6164981498788262 0.44928717656825584 0.3365831420089349 0.4646894211443393 0.8802485518044282 1.8146747880005754 0.1608864471756546 -0.23538854021056904 8.836583912257565 3.8174659241864703 0.5387819323291936 -0.18830386363467239 -1.0430272980416788 0.3310448308016341 -0.10735190850334911 0.3426157380908667)

(defn make-point []
  (repeatedly 3 cauchy))

(defn make-plane []
  {:form (repeatedly 3 cauchy) :val (cauchy)})

(make-point) ;-> (33.032354006369815 -29.428219536044043 -37.796430533111334)
(make-plane) ;-> {:form (-45.36910184399889 -1.6741101969009575 9.952054197916382), :val 0.9505471630252558}

(def points (repeatedly #(make-point)))
(def planes (repeatedly #(make-plane)))

;; And we'll need a function to tell us the sign of a number
(defn sign[x]
  (if (< x 0) '- '+))

(map sign [ -1 -2 -3 0 -0.5 1.3]) ;-> (- - - + - +)

;; Now if we take a set of planes and a point, 
(defn sig [point planes]
  (for [p planes] (sign (side p point))))

;; We can check which side of each plane the point is on
(sig (first points) (take 3 planes)) ;-> (+ - +)

;; Every different region gives a different signature. 
;; The more planes, the more signatures.

(count (frequencies (take 10 (map #(sig % (take 1 planes)) points)))) ;-> 2
(count (frequencies (take 10 (map #(sig % (take 2 planes)) points)))) ;-> 4
(count (frequencies (take 10 (map #(sig % (take 3 planes)) points)))) ;-> 6
(count (frequencies (take 10 (map #(sig % (take 4 planes)) points)))) ;-> 7
(count (frequencies (take 10 (map #(sig % (take 5 planes)) points)))) ;-> 7
(count (frequencies (take 10 (map #(sig % (take 6 planes)) points)))) ;-> 7

;; But the more planes we have, the smaller the smallest regions are
;; and thus the chance of a point falling in every one goes down.


;; The more points we take, the more likely we are to get one in every region

(count (frequencies (take 100 (map #(sig % (take 1 planes)) points)))) ;-> 2
(count (frequencies (take 100 (map #(sig % (take 2 planes)) points)))) ;-> 4
(count (frequencies (take 100 (map #(sig % (take 3 planes)) points)))) ;-> 7
(count (frequencies (take 100 (map #(sig % (take 4 planes)) points)))) ;-> 11
(count (frequencies (take 100 (map #(sig % (take 5 planes)) points)))) ;-> 18
(count (frequencies (take 100 (map #(sig % (take 6 planes)) points)))) ;-> 21

(count (frequencies (take 1000 (map #(sig % (take 1 planes)) points)))) ;-> 2
(count (frequencies (take 1000 (map #(sig % (take 2 planes)) points)))) ;-> 4
(count (frequencies (take 1000 (map #(sig % (take 3 planes)) points)))) ;-> 8
(count (frequencies (take 1000 (map #(sig % (take 4 planes)) points)))) ;-> 15
(count (frequencies (take 1000 (map #(sig % (take 5 planes)) points)))) ;-> 26
(count (frequencies (take 1000 (map #(sig % (take 6 planes)) points)))) ;-> 38

(count (frequencies (take 10000 (map #(sig % (take 1 planes)) points)))) ; 2 
(count (frequencies (take 10000 (map #(sig % (take 2 planes)) points)))) ; 4 
(count (frequencies (take 10000 (map #(sig % (take 3 planes)) points)))) ; 8 
(count (frequencies (take 10000 (map #(sig % (take 4 planes)) points)))) ; 15 
(count (frequencies (take 10000 (map #(sig % (take 5 planes)) points)))) ; 26 
(count (frequencies (take 10000 (map #(sig % (take 6 planes)) points)))) ; 40 

(count (frequencies (take 100000 (map #(sig % (take 1 planes)) points)))) ; 2 
(count (frequencies (take 100000 (map #(sig % (take 2 planes)) points)))) ; 4 
(count (frequencies (take 100000 (map #(sig % (take 3 planes)) points)))) ; 8 
(count (frequencies (take 100000 (map #(sig % (take 4 planes)) points)))) ; 15
(count (frequencies (take 100000 (map #(sig % (take 5 planes)) points)))) ; 26
(count (frequencies (take 100000 (map #(sig % (take 6 planes)) points)))) ; 41

(count (frequencies (take 1000000 (map #(sig % (take 1 planes)) points)))) ; 2
(count (frequencies (take 1000000 (map #(sig % (take 2 planes)) points)))) ; 4
(count (frequencies (take 1000000 (map #(sig % (take 3 planes)) points)))) ; 8
(count (frequencies (take 1000000 (map #(sig % (take 4 planes)) points)))) ; 15
(count (frequencies (take 1000000 (map #(sig % (take 5 planes)) points)))) ; 26
(count (frequencies (take 1000000 (map #(sig % (take 6 planes)) points)))) ; 42 

;; I'm painfully conscious of having stopped the experiment at the
;; exact point where I got the answer I expected. But my poor little
;; computer is not going to be up to running this for 10000000 points.

;; But this can't just be coincidence, surely?








Followers