информационно-новостной портал
Главная / Статьи / Информатика / Программирование /

Виды вычислений. Карринг. Запоминание

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

  Ленивые вычисления позволяют создавать и обрабатывать цикли-ческие и бесконечные последовательности. Так же вычисления помо-гают избежать лишних вычислений.  Например, элемент(x,s)=редукция(s,l(e,t) если e=x то #T иначе t, #F).

В языке  энергичной семантикой при вычислении выражения элемент(2, '(2 7 1 8)) потребуется полная обработка списка, при использовании ленивых вычислений результат будет получен сразу и поиска элемента в оставшейся части списка не потребуется.

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

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

  Функцию нескольких аргументов можно рассматривать как суперпо-зицию функций одного аргумента. Например, функцию plus=l(x,y) x+y можно интерпретировать как plus=l(x)l(y) x+y. Вызов plus(1,2) интер-претируется как последовательность вызовов (plus(1))(2). Сначала применяется первый аргумент plus(1), в результате получается новая функция l(y)1+y. Эта функция применяется ко второму аргументу (l(y)1+y)(2), и получается окончательный результат 3. Такой способ обработки функции нескольких аргументов называется каррингом.

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

 Запоминание предыд-х значений аргументов, к которым примен-сь

функция, и полученных при этом рез-ов в спец. таблице позволяет

не вычислять рез-т заново для тех же аргументов, а использовать ранее вычисленные рез-ты.

power(n)= если n=0 то 1 иначе power(n-1)+power(n-1) – время выполн.

2^n. Если power мемо-функция, то второй вызов сведется к поиску

соответствующего значения в таблице и не потребуется рекурс. вызов. => время=n+1 вызовов. Запоминание упрощает обработку

бесконечн. структур.

Просмотров: 800 | Дата добавления: 08.02.2016