В этой статье рассказывается о создании модели для параллельного программирования (ПП).
Необходимость в создании языка для ПП возникла после того как появились возможности написания программ для многопроцессорных систем и появления в архитектурах современных процессорах нитей(threads). Причём программисты и общественная культура программирования оказалась неготовой к написанию П-программ, так как обычный процедурный подход для ПП привёл к тому, что программист больше не мог логически держать под контролем все процессы и недооценивал побочные эффекты, которые дают параллельные процессы. Очень плохую роль в этом играет привычка писать простые детали программ не задумываясь о том что они будут работать уже в других условиях.
Чтобы программировать стало реально, нужно поменять стиль программирования и научиться программировать заново. Взять трёхтомник Кнута, просмотреть, закрыть и забыть. ;)
Один из способов организации вычислений подсказывает сама жизнь. Люди очень давно пользуются этой системой для управления большими организациями. Создаётся иерархия управления, на верху управляет один, редко два-три человека, которые непосредственно задают задачи своим менеджерам, те в свою очередь решают поставленные задачи с помощью привлечения своих служащих.
Хорошо организованные структуры при этом для ускорения выполнения задачи делают так: все подзадачи, которые можно выполнять параллельно поручаются отдельным служащим, а те что требуют определённой пошаговости выполнения поручаются одному человеку, который занимается только контролированием правильностью пошаговости выполнения задач своими служащими.
Примером плохой организации может служить советская система получения различных документов, при которой не существует лица кроме самого человека, которому нужна какая-то бумажка, которое принимало бы от человека только запрос на получение документа и само контролировало строгую пошаговость штампов и справок. При отсутствии такого сервиса мы имеем систему, при которой для прохождения отдельного шага нужны все справки о том, что мы прошли предыдущие шаги. Эту систему можно сравнить со стилем программирования с использованием семафоров (документ) для синхронизации процессов (чиновников).
Система которая имеет структуру выражается в том, что отдельный узел управления выполняет маленькую часть всей работы и не вмешивается во внутреннюю работу своих служащих.
Таким образом встал вопрос о кандидате - языке, который бы больше всего подходил для расширения до ПП. Перепробовав различные стили программирования стало ясно, что к выше означенным требованиям идеально подходит функциональный стиль, а именно язык Лисп.
Лисп (Lisp) - также известный как (((Lots of (Idiotic (Silly (Parentheses)))))) (множество идиотских вложенных скобок) начал своё применение лишь как экспериментальная модель для теории лямбда-исчисления. Чтобы на этом языке можно было запрограммировать все обще-рекурсивные функции по Черчу (а этот класс совпадает с классом всех алгоритмов, которые можно задать с помощью машины Тьюринга) в него достаточно задать возможность к рекурсии, проверке на нуль-объект и элементарными операциями над объектами в области которых будут действовать функции. Так появился Чистый Лисп (Pure Lisp).
Объекты Лиспа задаются как либо атомы, либо структуры атомов. Атом - по определению неделимый объект. Конкретно в Лиспе единой структурой атомов был выбран список и язык получил свое название LISt Processing (обработка списков).
Функция - это отображение из поля объектов в поле объектов.
Сложные функции получаются из элементарных с помощью конкатенации, которая необходима в теории лямбда-исчислении.
В применении принципа Фон Неймана - единства данных и программ создатели языка пошли ещё дальше и создали синтаксис, при котором форма записи функции была такой же как и форма записи данных, и в зависимости от потребностей интерпретировалась как функция либо как данные.
Определение функции в Common Lisp-е выглядит так:
(defun fname arglist body), где arglist представляет собой список из формальных имён аргументов и ключевых слов. Ключевые слова выглядят так: &rest, &optional, &environment, … Все эти ключевые слова используются для интерпретации: какую часть фактических параметров функции присваивать каким формальным параметрам. Так как способ вычислений аргументов является составляющей функции и при другом порядке вычислений это был бы уже другой алгоритм, то логичным было бы добавить ключевые слова, например &concurrent и ¶llel, затем заключить соответствующие параметры в скобки.
Например, функция func от трёх аргументов x, y, z требует, чтобы они вычислялись в таком порядке: (z параллельно (x затем y)). Это можно записать так:
(defun func (¶llel (z &concurrent (x y))) body)
Теперь рассмотрим как можно записать вычисление параллельно нескольких функций, часть которых выполняется пошагово. Для пошагового выполнения в Лиспе существует функция progn,
(progn func1 … funcn)
которая вычисляет все функции funci пошагово и как результат возвращает значение последнего выражения. Соответственно определяем форму parallelprogn, которая вычисляет подфункции в параллельном режиме, а результат возвращает nil.
Далее возможность к распараллеливанию существует в моменте между вычислением аргументов и выполнением тела функции. Иногда происходит возвращение результата из функции, при этом она ни разу не считала значение нескольких аргументов. В этом случае полезно было бы запускать выполнение функции и вычисление аргументов в параллельном режиме , а при попытке функцией считать значение невычисленного аргумента останавливать процесс до получения результата.
Берём в Лиспе функцию apply, которая вычисляет применение некоторой функции к списку аргументов и создаём параллельный аналог parallelapply, который выполняет вычисления вышеописанным способом. Здесь появляется одна ловушка.
Мощность языка Лисп заключается в единстве задания программ и данных. Это даёт возможность писать алгоритмы, которые создают другие алгоритмы, которые затем и вычисляются. Но порядок вычисления аргументов с телом функции является составляющей самой функции, а форма parallelapply вычисляла бы всё параллельно, не обращая внимания на то, какую функцию ему приходится выполнять, так как она может быть создана динамически в процессе работы программы.
Значит и этот порядок вычислений нужно задавать на уровне определения функции.
Например так:
Нормальная функция -
(defun func args body)
и безымянная -
(lambda args body)
моментальная функция -
(paralleldefun func args body)
и безымянная -
(parallellambda args body)
При таком расширении языка Лисп становится сложнее программировать, исправление же готовых программ с помощью добавлений директив о порядке вычислений становиться практически невозможным. Проще уже всё писать с нуля.
Теперь пришла пора вспомнить о Чистом Лиспе, где тип вычислений очевидно определялся структурой программы - красиво и естественно.
Убедившись в том, что использовать уже написанные программы на каком-либо языке для усовершенствования к параллельному исполнению невозможно, я окончательно отказался от идеи расширения языков.
Хотелось бы иметь такое средство выражения алгоритмов, при котором сама структура записи очевидно определяла порядок вычислений. Таким образом мои поиски привели к функциональному языку:
Lisp2D - это экспериментальный функциональный язык, созданный для изучения техники параллельного программирования.
Функции в этом языке - это отображения из множества объектов в множество объектов.
Объект - либо атом либо структура объектов.
Атом - неделимый объект, может быть разных типов: числа, символы, строки, массивы, функции. Также есть типы, состоящие из одного объекта: true - логическая правда, nil - ничего.
Структура - это пара ссылок на другие объекты. Первый (головной) элемент обозначается first, второй (хвостовой) - rest.
Список - это пары, соединённые специальным образом: (a . (b . (… . ( z . nil))…) и обозначаются: (a b … z).
Интерпретатор принимает объект с консоли или из файла, вычисляет его и возвращает результат.
Результатом атома будет само значение атома, за исключением символов. Если с символом связано какое либо значение в текущем окружении, то возвращается это значение, иначе возникает ошибка интерпретатора и возвращается nil.
Если на вход интерпретатора подаётся структура объектов, то эта структура воспринимается как запуск функции с аргументами. В головной части должен быть объект, второй элемент это функция, в хвостовой части должен находиться список аргументов.
(object function arg1 arg2 … argn)
Порядок вычисления функции и самих аргументов зависит от вызываемой функции и задаётся во время её определения.
На месте function может стоять символ, функция или структура функций.
Если function - символ то берётся функциональное значение символа из текущего функционального окружения и это значение применяется к окружению. При отсутствии функционального значения происходит ошибка интерпретатора и возвращается nil.
Определить функциональное значение для символа можно функцией defmethod.
(имя-типа defmethod name arglist body)
Функция может быть встроенной или лямбда-вызовом. Лямбда-вызов - это определение функции без имени.
(lambda arglist body)
Интерпретатор вычисляет параллельно все аргументы.
arglist - список формальных имён аргументов, которые связываются с фактическими значениями и имеют действие только во время выполнения тела body. Извне этой формы значения формальных параметров недоступны.
Порядок подачи аргументов для функции должен соответствовать порядку в arglist
(object name x1 y1 z1 t1 a1)
С помощью описанного метода регулировки порядка вычислений программисту существенно проще программировать параллельные программы, так как большую часть синхронизации берёт на себя интерпретатор. Например параллельное вычисление аргументов функции с последующим присваиванием значений формальным параметрам функции скрывает в себе точку синхронизации окончания вычисления всех аргументов. Автоматическое приостановка процесса для ожидания значения аргумента скрывает в себе весь процесс проверки готовности результата и остановка/запуск процесса. В большинстве случаев при практическом программировании можно обойтись без специальных системных функций таких как wait - остановка процесса до определения значения, lock, unlock - дополнительные функции для доступа к разделяемым данным. Их использование засоряет текст программы и затрудняет понимание работы всего процесса.
Программирование с непосредственным управлением синхронизацией процессов и совместным пользованием данными требует такого же искоренения как в своё время был искоренён принцип управления пошаговости работы программы с помощью goto. Появились структуры while, for, do, until, которые по сути скрывали в себе необходимые команды управления.
Подобность большинства стилей программирования процедурному облегчает трансляцию программ в машинный код, но ещё раз подчёркивает их несостоятельность дать программисту необходимый инструментарий для ПП.
Я надеюсь данная статья поможет в осмыслении проблем ПП всем, кто этим интересуется.