It depends on the situation, but I generally think in terms of pure (recursive) functions and types. This then usually provides me with a reasonably quick mapping to my preferred languages (e.g. ML or Haskell), as well as providing a reasonably simple way of mapping back to languages like Java or C or PHP or whatever else I might be called upon to write occasionally.
Interestingly, I've spent a some extended blocks of time working inside theorem provers. I find that it requires me a bit of time to switch to and from that style of thinking.
Well, I think it's reasonably intuitive to think that way. It basically involves asking yourself the questions - "what types of values am I interested in?" "what types of results do I expect?" and finally "how do I get from input to output?"
I think most programmers probably think it reasonably similar terms - it's just that having working in STLC or a high-level functional language gives you some mental machinery that doesn't rely on decomposing this thought process into some concrete syntax from a programming language.
(incidentally, this is one of the reasons why I think there is a lot of value in learning the Lambda calculus early in a computer science education).
having worked in... a high-level functional language gives you some mental machinery that doesn't rely on decomposing this thought process into some concrete syntax
This is what we are really talking about when we claim that reading, e.g., SICP will make you a better programmer even if you don't work in Lisp.
SICP is not a book about Scheme. It's a book about computation that happens to use Scheme. And it is resolutely abstract, encouraging you to think in non-linguistic terms. One of the bits I remember best was near the beginning, when they talk about the shapes of computational processes -- iterative processes have a different shape from recursive processes. Now I use that sort of mental picture all the time.
The goal is to think about software like a mathematician thinks about math. If you're thinking in a language, it's like the way I thought about math when I was nine years old -- to the extent that I knew what a mathematician was, I thought it was someone who was really really good at the long division algorithm. Someone who could subtract really fast!
I kinda skipped SICP (I had already been programming for a long time before it even occurred to me that there might be texts available that attempted to teach "computational thinking" rather than just individual languages), but having browsed it since, I always recommend it to anyone who wants to learn programming (or HtDP, which also seems to cover similar ground).
Interestingly, I've spent a some extended blocks of time working inside theorem provers. I find that it requires me a bit of time to switch to and from that style of thinking.