This demo shows how to create a procedural fire in a fragment program. The cool thing is that this is achieved in only 8 instructions.
I did something similar in RenderMonkey during my time at ATi. That DX9 HLSL shader was fairly complex though and had many parameters you could tune. In an application you have more flexibility however, so large parts of the calculations can be preprocessed on the CPU. By carefully tuning the parameters passed to the shader I could reduce the number of instruction quite a lot.
Executable