Pavel Alaev (alaev) wrote,
Pavel Alaev
alaev

23. Теория алгоритмов и языки программирования

Человек, долгое время работающий с разными языками программирования, в конце концов, вполне возможно, задастся вопросом о том, какими они вообще могут быть. В частности, какими должны быть минимальные требования к инструменту, чтобы он имел право называться языком программирования.

Ясно, что в нём должны быть какие-то средства для организации ввода-вывода. Иначе компьютер с таким языком окажется бесполезен. Более общо, в нём должны быть предусмотрены механизмы взаимодействия со всеми основными компьютерными компонентами - клавиатурой, экраном, сетью, жёстким диском, принтером и т.д. Если эти функции возложены в первую очередь на операционную систему (а сейчас это так и есть), то в языке должны присутствовать подходящие средства общения с системой.

Все эти задачи, однако, носят достаточно технический характер - всё сводится к придумыванию максимально удобных способов передачи данных, соответствующих специфике оборудования. Для экрана наиболее хорош обычный посимвольный вывод, для диска - работа с файлами, для клавиатуры - обработка внезапно приходящих от неё прерываний. В современных языках придумано много ещё более тонких и изящных хитростей для решения этих задач.

Второе же требование, очевидно, состоит в том, чтобы компьютеру было что выводить - чтобы он обладал достаточными алгоритмическими возможностями. Но что понимать под "достаточными"? Хороший ответ состоит в том, что он должен быть способен вычислить любую функцию на натуральных числах, которая вообще может быть вычислена на каком-нибудь компьютере, при условии что в его распоряжение будет предоставлена неограниченно наращиваемая (в принципе) память. Дело в том, что с жёстко фиксированной памятью класс таких функций довольно тривиален.

Согласившись с таким подходом, мы естественным образом приходим к основному понятию абстрактной теории алгоритмов - к классу вычислимых функций. Иногда их ещё называют рекурсивными, или (более точно) частично рекурсивными функциями. Математики изучают этот класс давно, и изучили весьма основательно. Забавно, что для решения задачи о вычислении любой функции нужно чрезвычайно мало - можно обойтись лишь возможностью заводить переменные, принимающие значения из множества натуральных чисел, и четырьмя командами: прибавлением 1 к переменной, вычитанием 1 из переменной, оператором "go to" и условным оператором самого примитивного вида "if x=0 then goto ...". Не нужно даже оператора присваивания - он выражается через них. Чтобы оператор go to работал, нужна ещё возможность присваивать командам какие-то метки.

То есть всё богатство современных языков программирования сводится лишь к облегчению труда программистов, и вряд ли представляет особый интерес для теории алгоритмов. Понимание этого факта, возможно, может помочь программистам взглянуть более философски на особенности конкретных языков.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 1 comment