Главная проблема — это разработать хорошую виртуальную машину. Это не так легко, как кажется: она должна одновременно подходить для языка, быть простой в использовании и тривиальной в реализации. На выбор есть множество вариантов: стековые машины, регистровые, основанные на деревьях, графах — в общем, всё, что душе угодно. (Здесь мы сначала выбираем язык ассемблера, а затем подгоняем под него архитектуру машины.) В этом случае сравнение программ сводится к сравнению соответствующих им машинных кодов или же хода их исполнения машиной. Так как в итоге всё упирается в работу вычислительной машины, виртуальной или реальной, то подобный способ определения языка называется операционной семантикой.
Но у данного способа есть врождённый недостаток: ему необходима специальная вычислительная машина; иными словами, формальная теория вычислений.

Программа — это, прежде всего, функция, преобразующая входные данные в выходные. В этом случае не требуется сложная машина: математика веками оттачивала такой способ «исполнения программ», называя его «применением функций». Таким образом, идея состоит в том, чтобы преобразовать программу в функцию (из определённого множества функций). Подобная функция называется денотацией программы. Теперь остаётся только определить вышеупомянутое множество.
Если в качестве такой теории взять какую-нибудь простую, всем понятную концепцию, то можно избавиться от поддержки зоопарка всевозможных машин. Для наших целей прекрасно подойдёт λ-исчисление. Его аксиомы настолько просты, что их толкование не вызывает никаких разногласий. Таким образом, семантику языка программирования можно понимать как способ перевода программ в соответствующие денотации. Этот процесс, между прочим, тоже можно представить как функцию.