Лекция №2 ПРОГРАММИРОВАНИЕ

3.1 Ключевые (основные) вопросы (моменты)

— парадигмы программирования;

— функциональное программирование;

3.2 Текст лекции

3.2.1 Парадигмы программирования

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

Парадигмы в программировании являются способом концептуализации, который определяет, как проводить вычисления и как должна быть структурирована и организована работа вычислительной системы. Этот термин был предложен в 1977 году Томасом Куном (Thomas Kuhn) и затем использован в лекции “Парадигмы программирования” лауреатом премии Тьюринга Робертом Флойдом (R. Floyd). Парадигмы программирования представляют собой совокупность основополагающих идей и подходов, определяющих модели представления данных и их обработки, а также методологии программирования.

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

Язык машины Тьюринга является универсальным языком, несмотря на то, что в нем не определены никакие арифметические операции, отсутствуют определения подпрограмм и другие структуры, стандартные для обычных языков программирования. Машина Тьюринга эквивалентна грамматике с фразовой структурой, то есть грамматике типа 0 в иерархии типов грамматик Ноама Хомского (N. Сhomsky), описанной им в 1956 году. Любое состояние машины Тьюринга можно смоделировать при помощи некоторого вывода грамматики данного типа, однако грамматика с фразовой структурой может быть использована лишь в области теоретических исследований и не имеет большого практического значения для моделирования языков программирования.

Исследование машины Тьюринга приводит к выводу, что не только все существующие компьютеры, независимо от мощности, архитектуры и других особенностей, эквивалентны с точки зрения принципиальной возможности решения алгоритмически разрешимых задач, но и что любой язык программирования, который можно было бы использовать на практике, является универсальным, если проигнорировать ограничения, связанные со временем выполнения и объемом требуемой памяти.

Машина Тьюринга является примером того, что для достижения универсальности не требуется почти никаких аппаратных средств, за исключением неограниченной памяти. Даже чрезвычайно простой набор структур данных и операций оказывается достаточным для вычисления любой функции.

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

Простейший императивный язык может использовать всего два оператора: inc (инкремент) и dec (декремент), каждый из которых определенным образом будет модифицировать значение указанной в нем переменной, и одну управляющую структуру while (z) {…}.

В данном случае операция увеличения inc x (или уменьшения dec y) предполагает представление комбинации двоичных разрядов как числового значения в двоичной системе счисления и означает замену этого значения другой комбинацией битов, представляющей следующее увеличенное (или уменьшенное) на единицу число. Если связанное с переменной y значение равно нулю, то оператор dec y должен оставлять значение этой переменной без изменений.

Управляющая конструкция while (z) {…} будет вызывать повторение любой последовательности операторов, размещенных в фигурных скобках, пока значение переменой z не станет равным нулю.

Любую программу, написанную на этом простейшем языке, можно рассматривать как вычисление функции, входные значения которой представляют собой числовые величины, присвоенные определенным переменным до выполнения программы, а выходные – после ее завершения. Например, если рассмотреть в этом контексте оператор inc x, то можно увидеть, что выполнение этого оператора приводит к вычислению той же функции (функции следования), которая вычислялась в рассмотренной ранее машине Тьюринга.

Аналогичным образом можно рассматривать содержимое входных переменных x,y и выходной переменной z, в представленной ниже программе, которая реализует функцию умножения x∙y:

while (z) { dec z; }

while (x) {

while (s) { dec s; }

while (y) {

inc s;

inc z;

dec y; }

while (s) {

inc y;

dec s; }

dec x; }.

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

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

Модель Чёрча, основанная на частично рекурсивных функциях, привела к созданию высокоуровневых функциональных языков, а каноническая система Поста, предложенная им в 1943 году, аналогично упорядоченным продукциям (формулам подстановок) Маркова, легла в основу систем, ориентированных на правила (продукционных систем).

Дата добавления: 2014-11-24; просмотров: 308; Нарушение авторских прав

Мы поможем в написании ваших работ!