Разработчик - реализация
Cтраница 1
Разработчик реализации может дополнительно сократить расходы, связанные с выполнением унификации в период исполнения, надлежащим образом воспользовавшись индексированием процедур, поскольку построение индексных таблиц в период компиляции является ( неявным) частичным согласованием заголовка каждой процедуры с ожидаемым классом вызовов. Попытка унифицировать во время исполнения формальные параметры процедуры с известными фактическими параметрами начинается тогда с информации о том, что некоторое согласование уже было достигнуто благодаря выделению этой процедуры в качестве кандидата для вызова. [1]
Эти возможности предоставляют разработчику реализации широкий простор для оптимизации решаемых программой унификации задач, связанных с обновлением различных сред в стеках и организацией доступа к ним. Так, например, одно из решений, которое нужно принять при разработке программы унификации, касается двух возможностей: следует ли обновлять соответствующие ячейки переменных, как только на некотором шаге цикла будет обновлен список в, или же вместо этого следует хранить присваиваемые значения во временных регистрах. В первом случае при неудачном исходе унификации потребуется определить все эти ячейки и вернуть их в прежнее состояние, тогда как при успешном ее завершении ячейки будут находиться именно в том состоянии, которое нам нужно. Принятие такого рода решений еще больше усложняется при выполнении оптимизаций ( таких как ОПВ), направленных на экономию памяти, когда один фрейм записывается на месте другого. В деталях многие подобные соображения описываются в исследовательской литературе. [2]
 |
Алгоритм управления. [3] |
Вопрос о том, как наилучшим образом обращаться с присваиванием данных переменным программы, долгое время привлекал внимание разработчиков реализаций, и, быть может, на этот вопрос простого ответа не существует. Выбор какого-либо метода заключается в принятии решения относительно того, как сбалансировать соответствующие затраты на построение, хранение, выборку и отбрасывание данных, что в свою очередь связано с тем видом программ, которые, как предполагается, будут исполняться интерпретатором. В этом разделе наиболее важные соображения описываются с помощью ряда простых конкретных примеров исполнения логических программ. [4]
В общем случае на вызов Р ( могут потенциально отвечать несколько процедур, которые называются кандидатами для Рь И теперь разработчику реализации требуется решить, как именно охарактеризовать кандидата. Наиболее простой способ, который приводит также к самой простой, но зачастую и наименее эффективной реализации, - это рассматривать в качестве кандидата для PI всякую процедуру, чье имя соответствует имени вызова PJ; другими словами, не проводить никакого распознавания на основе согласования параметров. [5]
В тех ситуациях, когда программист не желает сам заботиться о координации вызовов и не предлагает интерпретатору никаких руководящих инструкций по этому поводу, общая переменная п вызовах может представлять некоторую проблему для разработчика реализации. С логической точки зрения вызовы р и q должны быть согласованы относительно присваивания переменной х какого-либо значения, и проблема состоит в том, чтобы достичь этого согласования операционно, сохраняя насколько возможно параллелизм исполнения программы. Для уменьшения указанных трудностей обычно используется компромиссный вариант: один из И-параллельных вызовов назначается производителем общей переменной, а все остальные - потребителями. Это делается, исходя из того, что, по всей вероятности, нет достаточных оснований, относящихся к области решения задач, иметь более одного производителя. При другом подходе многочисленные решения И-параллельных вызовов могут вообще не согласовываться ( и тем самым потенциально приносится в жертву полнота) с целью получения более простой организации распределения ресурсов обработки данных. [6]
Отметим, что описанный механизм никогда не приводит к сжатию глобального стека, и поэтому данные, хранимые в этом стеке, имеют гораздо более длительное время жизни, чем те, которые хранятся в его локальном аналоге. Это свойство возлагает дополнительное бремя на разработчика реализации, поскольку в ходе исполнения программы данные из глобального стека могут стать излишними. Само по себе вреда это не наносит, однако если глобальному стеку грозит переполнение и в нем содержится много излишних данных, то, может быть, интерпретатору имеет смысл запустить программу сборки мусора, которая обнаруживает эти данные и отбрасывает их. Хорошо написанная программа, предназначенная для выполнения сборки мусора, будет поглощать много времени, если неудачно выбрана стратегия ее запуска. Более того, составление подобной программы само по себе представляет значительный программистский проект. [7]
Точные детали поиска зависят, разумеется, от разработчика реализации. Предположим, однако, что с этой целью используется некоторый вид схемы индексирования. Исследуя параметры ТВ, интерпретатор среди всех доступных процедур, имеющих соответствующее имя, может выделить некоторое ( быть может, пустое) подмножество тех процедур, которые потенциально отвечают на ТВ. Просматривая этих кандидатов, расположенных в исходном текстуальном порядке, интерпретатор ищет затем первую процедуру, которая ( а) действительно отвечает на ТВ и ( Ь) совпадает с кандидатом СКА или расположена ( в смысле текстуального упорядочения) после него. [8]
Пространство, требуемое интерпретатором для реализации стека в ходе исполнения программы, может вырасти до неприемлемых размеров, если экономному расходованию памяти уделяется недостаточно внимания. За сокращение требуемой интерпретатору в период исполнения памяти, насколько это оказывается практически возможным, ответственность разделяют и программист и разработчик реализации, поскольку ни один из программистов не сможет писать эффективные программы для неэффективного интерпретатора, и ни один из специалистов не может разработать интерпретатор, извлекающий оптимальное поведение из всех мыслимых программ. [9]
Более того, всякая данная формальная система программирования может допускать различные виды параллелизма, каждый из которых предполагает наличие особого способа управления реализующими эту систему процессами. Возможности для параллельного исполнения логических программ распадаются на несколько категорий. К первой категории, оказавшейся довольно приемлемой с точки зрения разработчика реализации, относится ИЛИ-параллелизм, в котором используется тот факт, что когда на активируемый вызов отвечают сразу несколько процедур, их можно вызывать и применять для исследования этого вызова параллельно. Получающиеся в результате параллельные вычисления можно строить независимо, за исключением того случая, когда у них появляются ссылки на одни и те же несвязанные переменные в их общей родительской среде, вследствие чего могут возникнуть конкурирующие присваивания; для устранения этого незначительного препятствия на пути к поистине независимому ИЛИ-параллелизму можно использовать специальные схемы организации стеков. ИЛИ-параллелизм должен сыграть полезную роль при поиске в базах данных, где один запрос может иметь большое число альтернативных решений; это - прямое следствие недетерминизма логических программ в том смысле, что они допускают целое множество вычислений. [10]
Стоит отметить, что ОПВ восстанавливает явно пространство, занятое ненужными ячейками управления и ячейками локальных переменных, однако никогда не приводит к сокращению глобального стека, где накапливаются структурированные данные - он сокращается лишь при выполнении возврата или сборке мусора. С другой стороны, если ОПВ запрограммирована настолько компактно, насколько это возможно для того, чтобы избежать чрезмерного потока данных между фреймами и регистрами, то ОПВ может значительно сократить время обработки, поглощаемое итеративными вычислениями. Воздействие ОПВ на исполнение этой программы заключается в том, что на месте каждого фрейма, за исключением первого, записывается его последователь, и поэтому локальный стек никогда не продолжается дальше позиции 2, тогда как прежде его длина росла пропорционально длине входного списка. Однако второе возможное улучшение - это гораздо более высокая скорость, поскольку разработчик реализации может ( после достаточного анализа и программистских усилий) стянуть унификацию и построение фрейма, возникающих при выполнении каждой операции перезаписи. Получаемое в результате поведение будет во многом подобно поведению традиционной программы, использующей деструктивное присваивание для проведения итерации над одной фиксированной областью памяти и в то же время строящей структурированные выходные данные в другой области; в логической реализации этими областями являются соответственно локальный и глобальный стеки. [11]
В общем случае на вызов Р ( могут потенциально отвечать несколько процедур, которые называются кандидатами для Рь И теперь разработчику реализации требуется решить, как именно охарактеризовать кандидата. Наиболее простой способ, который приводит также к самой простой, но зачастую и наименее эффективной реализации, - это рассматривать в качестве кандидата для PI всякую процедуру, чье имя соответствует имени вызова PJ; другими словами, не проводить никакого распознавания на основе согласования параметров. IV, обычно гораздо более эффективно для хранения и выбора процедур использовать какую-либо схему индексирования, базирующуюся на классификации параметров. Тем не менее важно осознавать, что всякая схема распознавания, которая не соответствует экстремальной стратегии, заключающейся в попытке полностью согласовать ( унифицировать) Pi с заголовками всех имеющихся процедур, будет обычно давать некоторое количество кандидатов, в действительности не отвечающих на вызов PJ, когда дойдет дело до их испытания. Разработчику реализации следует сбалансировать преимущества, достигаемые за счет предварительного сокращения числа унификаций, которые в будущем окажутся неудачными, с непосредственными затратами на применение схем распознавания с целью минимизации множества кандидатов. [12]
Программисту, использующему тот или иной язык программирования, необходимо знать, может ли он позволить себе использование конкретного языка программирования, имея в виду эффективность последнего. Так, наличие определенных возможностей в некотором языке программирования может сделать его мнение эффективным. С другой стороны, наличие дополнительных возможностей требует дополнительных усилий для их реализации. Но при этом те, кто осуществляет реализацию некоторого языка программирования, имея в своем распоряжении непосредственно систему команд ЭВМ, часто могут сделать для эффективности программ, написанных на этом языке программирования, больше, чем программист использующий его для написания этих программ. Если кому-то нужны динамические массивы, то ему нужны именно динамические массивы, независимо от того, какие таблицы фиксированной длины некоторый язык программирования обеспечивает возможность использовать. И если применяемый язык программирования не позволяет использовать динамические массивы, то программист в случае необходимости будет вынужден сконструировать собственный диалект применяемого языка программирования, обеспечивающий такую возможность. При этом накладные расходы скорее всего, окажутся намного больше, чем если бы используемый язык программирования изначально предоставлял такую возможность. Это и понятно, поскольку в распоряжении программиста, в отличие от разработчиков реализации используемого им языка программирования, как правило, отсутствует инструмент, обеспечивающий эффективность реализации. [13]
Страницы: 1