r3 - 14 Sep 2006 - 22:03:41 - Sergej ZnamenskijYou are here: TWiki >  Refaldevel Web > PatternMatching

Методы оптимизации сопоставления с образцом

Несколько примеров

Примеры взяты из работы С. А. Романенко "Реализация Рефала-2".

Пример

Re : e1 '+' e2 '*' e3
Эквивалентно двум последовательным перестановкам:
Re : e1 '+' eX, eX : e2 '*' e3
Если при некотором решении первой перестановки, сопоставление в целом заканчивается неудачей, то оно закончится неудачей и для любого большего решения первой перестановки.

Поэтому исходная перестановка также эквивалентна такой последовательности:

\? Re : e1 '+' eX \! eX : e2 '*' e3
Т.е. цикл подбора значения e2 может быть вынесен из цикла подбора значения e1.


Пример

Re1 : eA '+' eB, Re2 : eX '+' eY
Если вторая перестановка не имеет решения, то сопоставление в целом потерпит неудачу при любом решении первой перестановки.

Поэтому исходная последовательность эквивалентна следующей:

\? Re1 : eA '+' eB \! Re2 : eX '+' eY
Т.е. цикл подбора значения eX может быть вынесен из цикла подбора значения eA.

-- Anton Orlov - 13 Mar 2005


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

Пусть проектируется типовое выражение

     1 3 4  5 2  6 7  8
L = ( eA + eB ) eX + eY

Над элементами выражения указаны их проекционные номера.
Если удлинение eX терпит неудачу, то E можно представить в виде Е = ( Е1 ) Е2, где eA + eB спроектировано на E1, а проектирование eX + eY на E2 невозможно. Значит, E2 не содержит + на нулевом уровне скобок, и удлинение eA ничего не меняет.


Пусть


L = e1 e2 .... eN * e0

E = AAA ... AAA

L содержит N открытых e-переменных, E имеет длину l. При проектировании L на E требуется O(lN) удлинений. После описанной оптимизации потребуется o(l) удлинений.


В следующем примере описанная выше оптимизация неприменима.

Пусть

    1  3  4  5 2  6  7  8
L = ( e1 sX e2 ) e3 sX e4
        
E = ( + * ) * * *
Сначала e1 примет пустое значение, sX станет равно +. После этого проектирование e3 sX e4 на * * * потерпит неудачу. e1 примет значение +, sX примет значение *, проекторование успешно закончится. Оптимизация невозможна из-за того, что подвыражения e1 sX e2 и e3 sX e4 содержат общую переменную sX. То же для выражения e1 sX e2 sX e3
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r3 < r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback