There is no paradigm shift; in both cases a CPU is executing the software/firmware.
Firmware and software are the same thing; the only distinction is in how it's stored. Software is typically stored on a mass-storage device (e.g., disk drive) and loaded into volatile memory (e.g., DRAM) before being executed. It's easy to change software, by simply replacing the file containing it with a different one.
Firmware is typically stored in nonvolatile memory (e.g., FLASH) connected more-or-less directly to the CPU. It's harder to modify (hence the "firm") and it may or may not be transferred to a different memory for execution.
Really, the operation of a computer with an "operating system" is fundamentally no different from your description of firmware. Remember, the OS itself is just another piece of software — or more likely, a huge collection of mutually-dependent pieces of software. At the lowest level, the CPU is still sitting in a loop of some sort, waiting for things to do. It's just that that loop is buried inside the OS.
As often with such definitions, we agree in most cases, but there is no really firm boundary between what is firmware and what isn't. Firmware is
- stored permanently (except for some knowledgeable person who can change it ...)
- not intended to be changed (except ...)
- operates on the processor without the help of other software (except ... you get it?)
As to data that is interpreted by a (firmware) interpreter: this is not often done in a professional setting, because it makes the product more expensive: more memory, CPU power, etc. is needed to achieve the same end goal. It is however sometimes used in hobbyist setting, often with a Basic interpreter in flash, and a (tokenized) Basic application stored in eeprom (or in Flash too). Check for instance the PICAXE and the various Basic stamps.
IMO in such a setting both the Basic interpreter and the Basic application should be called firmware.
An interesting use of a firmware interpreter that interprets stored code (which should IMO be considered firmware too) is the XBOX 360 startup. This excellent talk describes it in some detail.
Below MSalters wonders whether FPGA code / configuration data should be considered firmware.
In the aspects that matter most (it is information that is changeable late in the production process, but it is not intended to be changed at will by the end user) FPGA bits behave like firmware. That makes the question whether it is firmware according to any definition moot. The important point is that it can (and should) be written, handled and managed like firmware. (If it walks and quacks like a duck, is it a duck?)
Don't bother with definitions when they are not useful. Is microcode firmware? Does representation matter? Does context matter? Are the ROM bits for an IWM firmware?
Vaxquis' comment to OP's question prompted me to read the wiki article he links to. IMO the definition of firmware given there (persistent memory and program code and data stored in it) is troublesome. IMO the maps stored in a car navigation system are data, not firmware, no matter how they are stored (according to the wiki they should be firmware). And the apps in your iPhone or Android phone are applications, not firmware (according to the wiki they too should be firmware).
Best Answer
A computer program which is stored on a hard drive and loaded into a PC to be executed is often referred to as software. It is not permanently loaded into the memory chips connected to the CPU. A new copy of the program can be loaded onto the hard drive, and the next time the program is run the new version will be loaded and run.
Embedded computers are the ones that control a lot of the electronics that run our daily lives, but which we never see. They are in microwave ovens, cruise controls, TVs, and of course smartphones. A modern car has more than a hundred embedded computers (called microcontrollers). A microcontroller can cost as little as a quarter in production quantities.
Embedded computers almost never have a hard drive (some have SD cards, which are used like hard drives, but not for loading programs). Instead, the software is programmed, or burned into the microcontroller chip. So there is no loading of the program, it just runs from where it is. Programs for embedded CPU's like this are called firmware, rather than software, because historically it was much harder to change the program. That is not so much the case now, but the name stuck.
So you have the progression Hardware -> Firmware -> Software. Hardware is the circuitry and PCB board etc., that cannot be changed after it reaches the consumer's hands. Software is dynamic, and can be instantly updated and loaded into memory and run. Firmware is somewhere in-between, it acts like software, and can be updated albeit not as easy; but once it is, in a way it becomes part of the hardware.
Historically, firmware has been located in one of several kinds of memories described below. All of these are non-volatile (they retain their content when power is removed).
All of the above except for PROMs are still in use today. ROMs are used for program storage where the volume is high, and costs must be kept as low as possible -- an example is singing greeting cards. ROMs are the cheapest of any memory type used on computers.
Way back "then" (1970's), chips were programmed by taking them out of a socket on the PCB, putting the chip into a stand-alone programmer, burning the new firmware onto the chip, and replacing it on the board. Then turning power on to the board, and seeing if the program ran correctly. There was no mechanism for setting breakpoints etc. A lot of debugging was done by sending debug output to a terminal.
If you had to fix a mistake, if it was a small change sometimes it was easier to just patch the binary rather than go through the whole compile-link cycle (which could take 10 minutes or more -- these were often floppy-based development systems).
ICSP (In Circuit Serial Programming) was a huge improvement. It meant it was no longer necessary to remove the CPU chip from the board to program it. This was a necessary change, since the newer microcontrollers were coming out in SMD (Surface Mount Device) packages which cannot easily be socketed. The processor chip is connected to a header on the board, which is in turn connected to a programmer via a cable, which is connected to a PC over a USB cable.
Besides being able to update the chip over this interface, ICSP also provides a full debugging interface for the developer, for setting breakpoints, single-stepping, etc.
In addition to ICSP, a lot of microcontroller chips today can update themselves in situ. They do this by putting a small program in a protected area of program memory (so they won't accidentally overwrite themselves), then a new program is downloaded to the chip, and it updates the main program by writing to the flash. After the update is complete, the CPU is reset and the new version of the program is executed. This feature is sometimes called FOTA -- Firmware Over the Air). Apple uses it, for example, to upgrade the version of iOS on their iPhones and iPads.
In addition to referring to the programs that are actually executed by the CPU, software and firmware can refer to the code that the programmer writes, e.g. he wrote the software or she wrote the firmware. The terms can also be used as adjectives, as in software listing or firmware programmer.
In relation to firmware, you will also encounter the term assembler code. This is when the programmer writes code that matches the actual machine instructions executed by the CPU. The code is still considered to be part of the firmware. When microprocessors first came out, this was very common (usually because high level compilers weren't available or they weren't very good, or the processor's memory was too small), and often the entire program would be in assembly. Now assembly code is seldom used, and the entire firmware program is usually written in C or occasionally C++ or some other higher level language.