I train my labs to Master Hunter level and I use food.I have never once used food to train my dog. Again the book I referenced above is completely against that. Using treats implys that there is some sort of negotiation with the dog. In my opinion that is not what you want. You want to be the leader or alpha member of your dogs pack. Your dog needs to obey you because you told it to. Not because you asked it to and it will get a treat.
Yes it is absolutely possible for praise to be the reward. It is also harder to train that way but is much more worth it. Judging by how it sounds you want to train I cant recommend Julie Knutson to you enough. Also I think you have the advantage of having a lab. They are so forgiving in training mistakes and so eager to please. I could talk about labs all day.