This is a series of blog entries that introduce three devices written using the yield operator for Scheme. Previously I had the following entries that described the requisite features of a complete yield operator and an implementation of such a yield operator for Scheme.

 

Yield the Magnificent

Yield Implementation for Scheme

 

Trampolines, Pipelines and Pi are programming devices or constructs that are built on top of the yield and purely the functional subset of Scheme.

 

There are many ways one can look at the power provided by the yield operator. One way to look at the yield is that it is a call-tree walker. It can move information up and down the call tree. If the yield implementation is sufficiently flexible, it can walk up and down several call-trees which exist concurrently.

 

Another way to look at the yield is to think of it as adding input and output capabilities to a function in functional system. A function during the process of computing its value changes state, creates temporary variables etc. When the result or return value of the function is computed the state of the function collapses and the value is returned. Yield offers a way for functions to do input and out with other functions while they maintain state. More about this later.

 

Trampolines

I want to start off by introducing the simplest of the three devices, the trampoline – sometimes I refer to this construct as the trampoline process as well. (Note: The name trampoline is used only in the context of the yield based programming device I describe here and is not a logical extension of other trampoline constructs you may have encountered before.)

 

The trampoline was introduced to address the following scenario – in a purely functional context what is the meaning of a parameter code block that is passed to an iterator cannot affect the caller’s state. Such a parameter code block is always a closure, in a functional context. On invoking a closure, the closure cannot maintain or modify state in the caller without resorting to some sort of a side effecting operation such as an assignment.

 

The trampoline packages such a computational effect so that the programmer need not think in non-functional terms when using the yield. Instead of using a set! or an assignment as the computational effect, the trampoline device uses a jump as the computational effect.

 

To illustrate what I mean, one has to look at the relation ship between the caller and a yielding callee in an imperative language. The flow of control is almost always as follows for a Ruby or C# yield (yes, I am abstracting out many details here) –

1. caller calls iterator, control transfers to iterator
2. iterator does some computation and produces a values, yields it
3. control transfers to caller,
4. caller does something with the value – this something is usually a side effect
5.  caller returns a value to iterator, control transfers back to iterator
6. steps 2 to 6 can repeat any number of times till the iterator returns.

 

The problem with this functional programming land is that the there is no use in yielding the value if the caller cant to anything with it – an alternative is pass an environment back and forth between the caller and iterator or some such thing, which is always tedious to manage.

 

The trampoline does the following. The trampoline becomes the caller for two functions, both of which are iterators that concurrently maintain state. One iterator place the role of the caller in the imperative case and the other one plays the role of the callee. Since the function playing the roles of the caller is an iterator, its free to maintain any sort of local state it chooses.

 

The trampoline device is a simple device, but to see the correct analogy that argues its purpose is a little tricky. Another way to look at a trampoline is to look at it as two iterators such that when one yields control passes to the other and when the other yields control passes back to the first. The process terminates when one of the two iterators terminate.

 

 

Here is an example of code that uses the trampoline. When the trampoline process terminates, a list of values that are the return (or last yielded values) of both iterators is returned.

 

This is an iterator that adds values that it gets yielding the current sum at any point.

(define adder

  (lambda-iter ()

     (let loop ((s 0))

       (loop (+ s (yield s))))))

 

This is an iterator that yields the first ‘n’ Fibonacci numbers

(define fibonacci

  (lambda-iter (n)

    (let loop ((a 1)(b 1)(n n))

      (if (not (zero? n))

          (begin

            (yield a)

            (loop b (+ a b) (sub1 n)))))))

 

To sum the first n Fibonacci numbers, one create a simple trampoline between the iterators

(printf "Sum = ~a~n"

        (cadr (trampoline-process (fibonacci 10) (adder))))

 

The cadr is there because the trampoline returns a list of two values, the last value obtained from the Fibonacci and the last value obtained from the adder. We are interested in the sum yielded by the adder and so we take the cadr.

 

The trampoline process that is implemented in the library that I have shared below is a slight generalization of this idea – the generalization being that the trampoline process can take any number of iterators as arguments creates a circular list of control transfer using yield. While having two iterators in a trampoline can be thought of as the equivalent of an imperative caller and callee, there is no simple parallel I can think of for three of more iterators in a trampoline. Below is a diagram of trampoline with three iterators.

 

 

I frequently use a trampoline while programming in scheme using yield. While it may not be easy to see why trampolines are useful just by using a simple example like the above, they useful in managing code complexity when each of the iterators involved has to do a non trivial computation.

 

As an example I wrote a CPS transformer for a subset of scheme last semester, at the heart of which was a trampoline. One iterator would recursively walk down the source expression tree and would yield out values. The other iterator would reconstruct a CPSed expression. So it gives you the conceptual clarity of writing a two pass CPSer while in effect only one pass happens. (Of course I could mash both the analysis and construction phases into one big hairy ball of mutually recursive functions, but that would not let me focus on one problem at a time and possible build them up as reusable iterator components. This of course was a little non traditional and might not have been easy on the evaluator of the assignment).

 

Download Sources for Yield, the Trampoline and the Sample Code above.

 

In the next related entry I hope to discuss the Pipeline device (aka the Pipe device).

 

What is the Y combinator? I have seen lots of discussions on the web but nothing that seemed like a simple explanation of how it works or why it is needed. I finally understood the Y combinator a few days back and a lot of things snapped in place. So here I will try and explain it from my perspective. In this entry I am taking liberties with various syntaxes – please bear with me.

 

This is the Y-combinator for a normal order lazy language –

Y = \f.((\x.(f (x x))) (\x.(f (x x))))

 

(Here, the ‘\’ denotes a lambda). Scheme is an applicative order language and the above combinator cannot be used as such in scheme because it will lead to an infinite expansion. More on this later.

 

Let’s start from some basics – say we are writing a mathematical expression and we said

a = a + 1

While the above means something in imperative programming languages (like C), it does not mean anything in mathematics.

 

Now say I want to write the factorial function in mathematics, I would say something like this

fact(0) = 1

fact(n) = n * fact(n-1)

And this definition is perfectly valid. However you notice that it is similar to the a = a + 1 expression in the sense that in describing the value of something, we refer to that very thing.

 

This general principle, called a recursive definition, has a problem in the context of pure functions (like the lambda calculus). The problem is as follows – a function is a nameless entity – the only named entities that a function can use are function’s parameters (the variables introduced by the function itself) or parameters of a parent function that it is define in the scope of.

 

For example

(lambda (x y)

      ; can use x and y here

      (lambda (a)

            ; can use a, x and y here

      )

)

 

Now for a recursive definition, a function needs to be able to refer to itself (or like we say in some languages, a functions needs to ‘call’ itself).

 

So, the only way that one can define a recursive function would be to receive the function itself as one of the functions arguments. Think about this for a bit – if you are not used to programming in a language where you can pass a function, or return a function as though it were a value (similar to how you treat an integer), then this might be a hard idea. If you are from a programming background that wherein you are used to ‘higher order’ programming, then I am only stating the obvious here. (The general idea with higher order programming is that functions are first class values, like integers – which means that they can be passed as arguments, returned from functions, stored in data structures etc).

 

So we define a function such that it takes an additional argument which is itself.

Lets say

 

factorial0(factorialx, n) = if n == 0 then 1 else n * factorialx(factorialx, n -1)

factorial(n) = factorial0(factorial0, n)

Does this make sense? If it does not, then don’t bother read further. You notice that the factorial0 function takes 2 arguments one of which is the function itself.

 

Let me rewrite this in scheme-style syntax

(let ((factorial0 (lambda (fact, n)

                    (if (zero? n)

                        1

                        (* n (fact fact (sub1 n)))))))

 (let ((factorial (lambda (n)

                    (factorial0 factorial n))))

      ; I can use factorial here

  ))

 

Make sense? Ok, so now let me write the interesting function factorial0 as a nested lambda as follows -

(lambda (fact) (lambda (n)

(if (zero? n) 1 (* n ((fact fact) (sub1 n)))))

 

You notice that fact is applied to fact, to generate the inner lambda which is then invoked with n-1.

 

So now, suppose one has a handy function of the following form

omega = (lambda (x) (x x))

 

One can define factorial as follows

 (let ((factorial

       (omega (lambda (fact)

                (lambda (n)

                  (if (zero? n)

                      1

                      (* n ((omega fact) (sub1 n)))))))))

  ; use factorial here

  )

 

There you go – so now we have a way of defining recursive function definitions even if your language did not directly allow a recursive definition.

 

So why do we need the Y combinator? You notice that in the definition of factorial we had to do something that looks very strange in the definition of the function – we call the function omega to return a function that we can call. The Y combinator does away with this for us.

 

To start thinking about the Y combinator, think about things this way – suppose the parameter ‘fact’ was already ‘(omega fact)’ then we wouldn’t have to call omega inside the definition of factorial correct. Right?

 

If we wanted that we simply need to rewrite omega this way right –

(lambda (x) (x (x x)))

Such that the first parameter is already applied to itself. But then this is not enough, because when the recursive call is made, the second time the parameter is only fact and not (fact fact) or (omega fact). Well, so we can fix this by having one more level in the definition of omega, such that omega looks like this –

(lambda (x) (x (x (x x))))

 

But then the third time this would not be the correct parameter… ideally we need an infinite application of x, because we don’t know how many times the function will call itself. In other words the omega should look a little like this

(lambda (x) (x (x (x (x (x … ))))

 

This is exactly what the Y combinator does. To see how it does this consider OMEGA defined as

OMEGA = (omega omega)

(or expanding for little omega we get)

OMEGA = ((lambda (x) (x x)) (lambda (x) (x x)))

 

If you haven’t seen this before, look at this device for a bit – do you see how it is infinite self application? If you do then consider the following

((lambda (x) (f (x x))) (lambda (x) (f  (x x)))

It doesn’t matter what f is right now, but see what this does. After one reduction this would look like this -

(f (term term))

Where term = (lambda (x) (f (x x)))

The second reduction would look like this and so on

(f (f (term term)))

(f (f (f (term term))))

 

This, if you notice is similar to what we required earlier, where instead of ‘f’ we used ‘x’.

 

This is the basic mechanism for the Y combinator. And the Y combinator is simply

Y = (lambda (f) ((lambda (x) (f (x x))) (lambda (x) (f  (x x)))

 

So how do we define a recursive function using the Y? Here is factorial

(let ((factorial (Y (lambda (fact)

                      (lambda (n)

                        (if (zero? n)

                            1

                            (* n (fact (sub1 n)))))))))

  ; use factorial here

 )

 

Nice?

 

Now in the beginning I said that this Y is the Y for the last normal order language. Scheme is applicative order and non lazy. What that means is that  if you use the Y combinator defined above in scheme, during the definition of factorial it will try to do the infinite expansion and will never terminate.

 

Instead one just eta-expands the definition to get the applicative order Y combinator. Suppose you say that term is (lambda (x) (f (lambda (y) ((x x) y))))

And we define the combinator as

Y = (lambda (f) (term term))

Then we have the applicative order Y that is usable from scheme and other applicative order languages.

Look at its expansion to see what I mean

(f (lambda (y) ((term term) y))

So the first parameter to ‘f’ (recursive function we are interested in is a lambda – the application inside the lambda is done only if f calls it.

 

Let me define both the Y combinators described here in lambda form

Y = \f.((\x.(f (x x)) (\x.(f (x x)))

Y = \f.((\x.(f (\y ((x x) y))) (\x.(f (\y ((x x) y))))

 

Once you see why the Y combinator is needed and you understand omega – its easy to see what the Y is and how it useful in defining recursive functions in a mathematically pure way.

 

The Y combinator is described as a fixed point function or combinator. The idea is that is lets a function describe its behavior in terms of itself until the function reaches a fixed point – like in the case of factorial the function reaches 0 and does not need to recurse any more.

 

References –

http://en.wikipedia.org/wiki/Y_combinator

http://www.dreamsongs.com/NewFiles/WhyOfY.pdf

 

Though I myself had looked at the Y many times before I never really understood it until I had to write recursive functions in the pure lambda calculus and I used omega to do it. I then happened to mentioned to Prof Friedman that I did not understand the Y and in a minute he set my thinking right.

 

I understand that in the description above I have taken some liberties with syntax and something are described in a hand wavy sort of way. However if you have suggestions about how I can better explain this, let me know. Of course I require that you understand scheme style syntax and higher order programming (at least minimally).

 

Some context –

 

The other day in Prof Dan Friedman’s Advanced Programming Languages class we had an assignment where we had to write a lambda calculus interpreter that did non deterministic application and we had to write the factorial in it. Also, reduction was to continue even if the top level term was value.

 

As a consequence of working on this we were expected to discover a method of encoding numbers using pure lambda terms. A really long time back Alonzo Church (creator of the lambda calculus) created an encoding now called the Church numerals. I created the following set when working on the factorial problem.

 

t = \a.\b.a     true

f = \a.\b.b     false

 

zero = \x.t

zero? = \x.(x f)

 

s = \x.\b.((b x) b)      successor

p = \x.(x t)             predecessor

 

(Like in Haskell the ‘\’ represent lambda). So we have a way of saying zero, we have a way of checking if a number is zero and we have the ability to add one and subtract one. That gives us all the natural numbers including zero.

 

If you notice, the predecessor define above returns a value that is an invalid number when applied to zero. An alternate ‘type safe’ definition is the following –

p = \x.(((zero? x) x) (x t))

 

Here (p zero) is zero.  

 

Now you may think that that’s not great way of implementing numbers – its inefficient etc. Yes that’s true, but remember that the lambda calculus is a formal system, it’s a mathematical formalism and hence has no notion of cost. In the study of formal systems (other than the study of their complexity) we are interested in asking questions about what the system can do and cannot do. The above encoding I believe is equivalent to the encoding of Church numerals.

 

Following the definition of numbers, I can define ‘add’ in the following obvious way -

add = (Y \add.\a.\b.(((zero? a) b) ((add (p a)) (s b)))

 

Here ‘Y‘ is the fixed point Y combinator and this is equivalent to

add(a, b)  { if a == 0 then return b else return add(a - 1, b + 1) }

 

Similarly one can define ‘mul’ and ‘factorial’ as well.

 

I went ahead and defined operators so that I have scheme/lisp style lists. I am told that there are very similar to Church’s definitions.

 

cons =  \x.\y.\b1.\b2.((b1 f) ((b2 x) y))

car =   \ls.((ls #f) #t)

cdr =   \ls.((ls #f) #f)

null =  \x.x

null? = \ls.(ls #t)

 

Hence we have –

(null? null) -> #t

(car null) -> undefined

(cdr null) -> undefined

(car (cons a b)) -> a

(cdr (cons a b)) -> b

 

Can you shoot yourself in the foot using these definitions? Of course you can – but if you are careful you can write meaningful programs as well. To do other sorts of checks, like to prevent us from doing (s cons) we need some kind of type system or validations rules – but these are not relevant to the discussion of the pure lambda calculus.

 

Here is a basic lambda calculus reference - http://en.wikipedia.org/wiki/Lambda_calculus

Here is a Church encoding reference - http://en.wikipedia.org/wiki/Church_numeral

 

Some quotes and thoughtlets collected over the years. Some are my own, though I don’t know which ones exactly – over time it has all got mixed up in my head.

 

From Roshan to language designers of the future, on the topic of programming language types:

If it looks like a duck, and quacks like a duck, we have at least to consider the possibility that we have a small aquatic bird of the family anatidae on our hands.

(adapted from Douglas Adams).

 

I just fixed the last bug!

 

Any sufficiently advanced bug, is indistinguishable from a feature.

-- quoting Prof Andrew Lumsdaine, Advanced Operating Systems (P536)

 

Marvin: "I am at a rough estimate thirty billion times more intelligent than you. Let me give you an example. Think of a number, any number."

Zem: "Er, five."

Marvin: "Wrong. You see?"

The mattress was much impressed by this and realized that it was in the presence of a not unremarkable mind.

-- Douglas Adams, Life, the Universe and Everything

 

Life! Don't talk to me about life.

 

Ok, so what the answer?

Its 5,1,1,3,2…

No, no, no, I don’t like it..

You don’t like it?

It doesn’t mean anything, what does it mean?

Now that’s a different question.

-- solving the universe selection problem, Quantum Programming

 

When all you have is a hammer, every problem looks like a nail.

 

Would you like tea or coffee?

Mathematician: Yes.

-- quoting Michel Salim

 

What do you mean its third party fault? I can’t get my work done and you are partying?

 

It’s an idea so simple, that understanding it messes your mind.

-- adapted from Dan Friedman, Principles of Programming Languages

 

Creating a great language doesn’t involve assuming that your users are less smart than you.

 

The language that you use defines what you can most easily think of. Languages instill patterns of thought. Certain languages make difficult the understanding of certain ideas.

 

A novice was trying to fix a broken lisp machine by turning the power off and on.

Knight, seeing what the student was doing spoke sternly- "You can not fix a machine by just power-cycling it with no understanding of what is going wrong."

Knight turned the machine off and on.

The machine worked.

-- AI Koan

 

Lambda the ultimate.

-- Dan Friedman

 

The only law in physics that we know of that has a direction with respect to time is that of entropy.

-- QP class, B629 Computer Science, Indiana University

 

Accept it. We are Labor.

 

A style makes explicit what a language makes implicit.

-- Dan Friedman

 

What I was coming to is that its something that cant be expressed in the lambda calculus.

But that’s obvious.

-- quoting Amr Sabry

 

Science is a way of trying not to fool yourself. The first principle is that you must not fool yourself, and you are the easiest person to fool.

-- Richard Feynman

 

This is not even wrong.

-- Amr Sabry

 

There exists no formal method to convert an informal argument into a formal one.

-- quoting Amr Sabry

 

There exists no reversible classical function that coverts a quantum superposition into a classical state.

-- above paraphrased by Roshan

 

Misguided rambling from Roshan: Computer Science to Physics and Back Again

There exists no formal method to convert an informal argument into a formal one. This is roughly equivalent to the second law of thermodynamics - the total entropy of any isolated thermodynamic system tends to increase over time, approaching a maximum value. This is also our only formal notion of the quantity called time. Here the law is rephrased as follows and things brings out its directional property with respect time, more clearly - It is not possible for heat to flow from a colder body to a warmer body without any work having been done to accomplish this flow. Energy will not flow spontaneously from a low temperature object to a higher temperature object. This is roughly equivalent to saying that there is not no notion of a partial computation without a notion of sequencing with respect to time – this is the ‘.’ (dot) sequencing operator of the pi calculus. The lambda calculus does not define sequencing. Are all closed systems pi-systems?

 

Don’t worry, we are just playing games.

 

Summary of the known laws of the fictitious universe –

- There exists at least one notion of fundamental duality. Using this all other forms of duality can be derived.

- There exists at least one notion of self referential quantification. Using this all forms of self referential quantification can be derived.

- There exists an order of relationship of things among themselves. There exists an order of relationship of events among themselves. In other words there exists at least one notion of ordering or sequencing.

  

The Tao that can be described in words is not the true Tao

The Name that can be named is not the true Name.  

From non-existence were called Heaven and Earth

From existence all things were born.

In being without desires, you experience the wonder

But by having desires, you experience the journey.

Yet both spring from the same source and differ mostly in name.

This source is called "Mystery"

Mystery upon Mystery,

The womb giving birth to all of being. (1)

- Tao Te Ching, as translated by John R Mabry

 

All consistent axiomatic formulations of number theory include undecidable propositions ...

Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved ...

- Gödel Escher Bach, Douglas Hofstadter

 

Thirty spokes join together at one hub,

But it is the hole in the center that makes it operable.

Clay is molded into a pot,

But it is the emptiness inside that makes it useful.

Doors and windows are cut to make a room,

It is the empty spaces that we use.

Therefore, existence is what we have,

But non-existence is what we use. (11)

- Tao Te Ching, as translated by John R Mabry

 

The impossible did not bother him unduly. If it could not possibly be done, then it must be done impossibly. The question was how?

-- Long Dark Tea-time of the Soul, Dirk Gently.

 

((lambda (x) (x x)) (lambda (x) (x x)))

 

If you're going to tell a lie, tell a big one (then nobody will believe it's a lie.)

-- Joseph Goebbels

 

Is there a name that describes a situation where all parties involved, despite understanding fully or partly the true nature of the situation, choose to play a role until an outcome of the situation presents itself in such a way that it cannot be held the sole responsibility of any of the parties involved?

 

Why can’t we all just get along?

 

The average celebrity meets, in one year, ten times the amount of people that the average person meets in his entire life.

-- Jack Nicholson.

 

Deep down, I'm pretty superficial.

-- Ava Gardner

 

 “One day an evil magician flew over his house and – “

“Just a minute, “ interrupted the king (who was very practical). ‘I didn’t know that magicians could fly!”

“Most of them don’t,” she replied, “but this one did.”

“But how could he?” asked the king. 

“Because he was a flying magician,“ she replied.

“Oh, that explains it,” he said. “Go on!”

-- Raymond Smullyan

 

I agree with you, its just that I am not willing to admit it.

 

I searched for one of my favorite quotes and found this page. I laughed my guts out for sometime - http://www.corsinet.com/braincandy/explain.html

 

Fortune has me well in hand, armies 'wait my command

My gold lies in a foreign land buried deep beneath the sand

The angels guide my ev'ry tread, my enemies are sick or dead

But all the victories I've led haven't brought you to my bed

You see, everybody loves me, baby, what's the matter with you?

Won'tcha tell me what did I do to offend you?

-- Don McLean, “Everybody Loves me, Baby”

 

Ph.D. Haskell programmer - ate so many bananas that his eyes bugged out, now he needs new lenses!

-- Evolution of a Haskell Programmer

(I nearly died laughing on this one – these days I have been trying to understand monads in the context of computational effects and CPS. If you don’t get the reference look here, Erik Meijer’s classic on the ‘Point Free Style’ - http://citeseer.ist.psu.edu/meijer91functional.html)

 

I almost made a (potentially) very expensive mistake today. I have been hoping to buy a digital SLR for a while now and in the past few weeks that seems to be the only thing that on my mind. Most people around me are a little wary getting into a conversation with me these days because the only thing I could talk about was the camera I was hoping to buy.

 

After a lot of ruminations between going Canon or Nikon I finally decided to go with the Canon EOS 350d a.k.a. the Canon Digital Rebel XT. Now I cant really afford this stuff, and it a rather tight stretch to get myself one of these considering my present status of un-rich grad student.

 

I am also no novice to using the web and to using computers, so I was so stumped by how I forgot the cardinal rule of doing anything on the web – never believe a webpage. Unless you know the entities behind the webpage and you trust their reputation to serve your purpose – never ever ever trust a webpage.

 

Case in point, this is what you see when you Google for the Digital Rebel XT:

 

I took a walk down to the nearest camera shop and I mentioned to the friendly gentleman there about how the website prices are about 450$ when he is charging me about 800$. Here came the first piece of news – he says that if you have a Canon USA warranty, in other words if something happens and you want Canon to fix it for you, then there is no way that the camera can cost so less. It must be some international warranty which you may have to ship back to the country of origin.

 

So I take a look at the website again and the website says that it has a USA warranty – very explicitly. So I feel considerably relieved. I however wanted to check out one or two of the lenses I was interested in getting and so I visited the shop again and I mentioned this fact to the person there. He stuck by what he said – he said that yes they might offer a warranty to you in the US, but it will not be Canon’s warranty. It will be someone else’s.

 

What? Now I was going to spend what is presently a non trivial amount of money for me so I put things together and I decided to call the online store I was planning to buy from.

 

I was feeling a little pressurized into getting this purchase done because Canon is offering some interesting mail in rebates which multiply when you get multiple items in combination and so I was planning to through in a decent lens with image stabilization and such.

 

So I call the store and I had to hold onto the line for a whole 20+ mins. Hmm hmm… what are these guys an airline booking service? And finally I get a most disinterested sounding guy. I ask about the warranty and yes, the shopkeeper I had been talking to was right. This was not a Canon warranty. ‘If something happens, who will be fixing the camera?’ ‘My technicians will work on it’ and that gets me thinking – gee, if I have to hold so long to just speak to one of them how hard will it be for me to get them to fix something for free? And then he says it – ‘my technicians have been fixing these for the last 50 years’. What??? And then a sentence or two later he hangs up while I was in mid sentence. Nice.

 

So the whole conversation was a little like being hit buy a snowball when you are busy picking your nose. I kind of snapped out of my self hypnotized state of mind and I did what I should have done first – search for reviews on the seller.

 

Every website I could find had people expressing very strong negative opinions about these guys. I search for some of the other sellers offering similar prices – they all had similar comments. What???

 

I remember the shopkeeper I was talking to mention that they cant be authorized Canon dealers because there is no way that they could get the cameras so much cheaper from Canon.

 

So finally, let me point some fingers –

This is the seller I was looking at and the one that I called up –

http://www.infinitiphoto.com/

(Yes they have a reasonably nice looking webpage).

 

Here are some others -

http://www.bestpricecameras.com

http://www.geniuscameras.com

http://www.usaphotonation.com/

 

Here are some seller review pages –

http://www.reviewcentre.com/reviews87615.html

http://forums.photographyreview.com/showthread.php?t=10678

http://www.dcresource.com/forums/archive/index.php/t-7031.html

http://www.dcresource.com/forums/archive/index.php/t-72.html

http://www.price.com/vendor_review_display.html?vid=-2147483120

http://forums.photographyreview.com/showthread.php?t=10918

and so on, there are many pages out there that tell similar stories.

 

Well this was a clincher –

http://www.resellerratings.com/seller9662.html

 

Moral of the story – make sure that you search for the seller when buying online always. If in doubt call them up, maybe even multiple times. This is a handy website that gives you seller information –

http://www.resellerratings.com/

More practically, simply search the web for “review <seller name>”.

 

Ensure that you are not going for opinion bases of 5 or 6 reviews. Averaging over 100s of reviews is decent. Another thing that you could do, is use resellerratings.com or similar to search for the product to see which sellers give you a good price.

 

And before I change the topic, some good information. I have heard good opinions by word of mouth and in terms of reviews about B&H. They are on the average a little higher in cost than the cheapest semi-reputable seller you can find.

http://www.bhphotovideo.com/

I have heard good things about Adorama.com as well.

 

If you are looking for Canon EOS lenses to buy, take a look at this link (thank you Deepak for pointing at this). This is a good starting point for a beginner in digital SLR photography and is a beginners guide to lenses for the Canon EOS series –

http://bobatkins.com/photography/digital/10d300dlenses.html

 

 

Finally, now that I have broken free of my obsession (for a while) I was trying to think of why I got so convinced into buying this, without doubting the seller and other things. The last time I bought a camera online I was very careful. I have two ideas in this regard and they are a little touchy, but here they are –

 

What changed since the last time I bought my Sony P150 that caused me not to scrutinize the seller as much? One answer – Google. See people form an emotional bond with their search engine – it is their bringer of information, of right information, of truth. It is not an intellectual bond, it is bond formed out of the force of habit. So when something shows up ‘on top’ on google – I think that that information is credible (for some values of credible). If any of the shoddy sellers above were ranked first or second on Google, that would be true. But, they were sponsored links and they were right on top on Google.

 

When a link is on top by paying for it, of course its not credible. Of course, Google never does vouch for the credibility of the people who it sells ad space to as well. While all of that is correct, the point is that being on top on Google is a powerful selling force. It can slip past the best of us. The same goes for Google’s Froogle – I don’t think any form of paid advertising is involved there though.

 

Can Google do something about this? Should they check credibility of the ads they host – I don’t think they can if they want to sell ads in bulk the way they do now. I think this is hard for anyone on top – be it Google or MSN or anyone else. But if they don’t, there will be more like me who trust Google ranking and information finding abilities to magically lend credibility to their sponsored links.

 

However, here is an opinion – if you plan to be a popular website on which resellers can rely on to sell their goods, then you need to have a credibility system in place. Something like Amazon’s seller feedback and buyer assurance. How much do you think I am going to value sponsored links on Google in the future? Maybe on the whole, advertising on websites would take a big boost, if there was a credibility system.

 

 

The second point I wanted to make is one that is best described using Ken Thompson’s ‘Trusting Trust’. How can you trust or mistrust one website based on another? What if the review site you are looking at is faking it? What if someone is trying to make one of the above sites look bad by posting fake reviews? Or is someone trying to make their own site look good?

 

There is, in my understanding, no way out of this. One almost always ends up implicitly or explicitly trusting one system to make a judgment about another, like KT demonstrated in his Turing award lecture.

http://www.acm.org/classics/sep95/

 

The only thing you can do is mitigate the possibility of being cheated is by looking at several review sites and by calling up your potential sellers. I can’t think of very much else.

 

 

Finally, if you are from one of the sort sellers this is what I have to say - get smarter. If I were you and I still wanted to defraud an occasional gullible customer, I would minimally do the following –

- Have more fake reviews in my support

- Sound more endearing on the phone

(despite the bad reviews, a good phone conversation and the price would have got me). You see going on top on google gives you a much larger window of opportunity to get at customers than you realize. Think a little bit – there are many many things you can do. Of course, you will eventually get caught or get sued – but I am assuming you are willing to entail that risk considering some of the reviews I read.

 

As of now I am not buying my Rebel XT, it a little outside of my budget. But I guess the prices will come down and my budget will go up, in time.

I had been to Chicago the last week of 2005. This visit, being my first trip outside of Bloomington to see the ‘the real US’ as some people tell me. Considering that I had pretty much flown into Indianapolis in the middle of the night and that I had stayed at Bloomington all semester I pretty much had not seen any more of the US than most Indians had in the movies.

 

One of the many reasons that I was looking forward to seeing Chicago was that I was looking forward to seeing some of what was considered ‘big’ in American terms. I don’t know if this is easy to understand, but back in India what most people who visit US for the first time tell me is that the thing they notice most is how much larger everything is. Larger stores, larger roads, larger people, larger potatoes etc etc

 

Well Bloomington, didn’t spook me out in that way – it was all too beautiful to be scary. Bloomington seems like it has sprung straight out of an Enid Blyton novel, for those of us who grew up reading Enid Blyton novels (no I didn’t, I just happened to make certain observations about those who did. So there.).

 

Chicago was well, uummhh… large. I was kind of spooky to be surrounded by all there large buildings and one was walking along the streets staring up at a partitioned sky. I also remember noticing how on the average people looked more harangued than folk back at Bloomington. And also how everything was so much more hurried. People seemed also seemed more necessitated to fend for themselves instead of the ‘you first, no you first’ courtesy of Bloomington. I also remember thinking that with buildings like that the only thing that the place lacks is Godzilla to go tearing between – just to complete the picture. Many things were more expensive, or at least it was considerably easier to find yourself more expensive things that it was in Bloomington where most college students would not have much use of finding themselves lots of expensive things. There were also many poor people on the streets, many holding up signs that said something like “I am just Hungry”.

 

But anyway, that’s not what this post is about. This post is about the St Pauli Girl. Chicago can wait, I didn’t know I’d have much to say about it.

 

Of all the pictures I took in Chicago, the one that seemed to catch my attention the most is this random picture I took of a neon sign in a shop window. The St Pauli Girl:

 

 

I don’t know what it is, but that picture held a certain inexplicable appeal. It even stayed my wallpaper for sometime. See, I am not much of beer person, then why? I do have googd friends who really like beer, but not me. Not yet.

 

I finally decided to google for it and sure enough, I found my explanation. Now for the benefit of my below 18 readers who are trying to understand the true nature of all of computer science from reading my blog, I shall not quote these here, instead I shall provide the links here.

 

Scroll down and read the section titled Don't Fear the Reaper

http://www.purpleroom.com/travel/kenn6.htm

 

and

http://beer.emptyfree.com/index.php?p=7

 

Cheers! Hic!

 

For sometime in the last semester I had an interesting problem to work on. One approach that we expected would help us solve the larger problem was to search for XOR ordered matrices that were unitary. (A unitary matrix is one whose complex conjugate is also its inverse).

 

A xor ordered matrix is simply one that could be generated by the following code snippet:

syms = %w(a b c d e f g h i j k l m n o p q r s t)

v = 8

v.times{|m|

      v.times{|n|

            printf("%s ", syms[n^m])

      }

      puts ""

}

 

Here are 2x2, 4x4, 8x8 and 16x16 XOR matrices (obtained by changing the value of v) -

a b

b a

 

a b c d

b a d c

c d a b

d c b a<