Ссылки на все разделы проекта:

1. Функциональная Потоковая Машина с параллельными вычислениями. Введение (http://tadviser.ru/a/121275)
2. Единая структура данных и программ (http://tadviser.ru/a/149691)
3. Функционирование ФПМ. Выражения языка програмирования (http://tadviser.ru/a/149691)
4. Потоки и их обработка в структуре выражения (http://tadviser.ru/a/150588)
5. Микропрограммирование функций (http://tadviser.ru/a/153069)
6. Программа, как управляемый поток выражений (http://tadviser.ru/a/153069)
7. Макроопределения пользовательских функций(http://tadviser.ru/a/157631)

Известный писатель-фантаст Сергей Лукьяненко выступит на TAdviser SummIT 28 ноября. Регистрация 5.6 т

Как и ранее, при формальном описании лексем здесь используется метасимволика Бэкуса-Наура. Дополнительно в скобки [] заключается часть описания, которую можно опускать (исключать). В скобки {} заключается любое число раз (включая 0) повторяемая часть описания. Под частью лексемы – элементом структуры в скобках %% указываются его Свойства согласно п.2.3

7. Макроопределения пользовательских функций

Пользователь вводит определения собственных функций в виде подпространств (п.3.1) следующего вида:

  <Имя функции>:(<макроопределение функции>
      %.|1%
		    {,<аргумент по умолчанию>}			(7-1)
		)

или  в отсутствие аргументов по умолчанию проще:

   <Имя функции>:<макроопределение функции> 			   

   <макроопределение функции>::= <выражение>
   <аргумент по умолчанию>::= <выражение>

Таким образом, макроопределение является обычной структурой в определении п.2.1 с доступом к нему по имени, как и к значению любого подпространства (переменной). Согласно п.3.6 в любом вычисляемом (функцией $Eval, р.6) выражении могут присутствовать вызовы определяемой самим пользователем функции:

 <Имя функции [подпространства(7-1)]>(<аргумент>{,<аргумент>}) (7-2)
 <аргумент>::= <выражение>

Отличительной особенностью макроопределения вводимой пользователем функции от прочих выражений является возможность многократного использования в качестве любых (кроме корня!) узлов его структуры примитивов (параметров) настройки _A, _B, …, _Z - фактически ссылок на соответствующие по порядку аргументы в (7-2). Выполняющая любое выражение функция (a) $Eval подменяет вызовы (7-2) их макроопределениями, разыскиваемыми по именам функций - именам подпространств согласно п.2.6. В найденном макроопределении функции параметры (примитивы) настройки _A - _Z в выражении – макроопределении функции подменяются соответствующими аргументами � выражениями из ее вызова (7-2). В отсутствие такого аргумента в вызове (7-2) выбирается аналогичный по порядку аргумент по умолчанию

из (7-1), в отсутствие которого значение искомого аргумента принимается равным # со свойством %#% (неопределенным, п.2.3).

Следует обратить внимание на следующие моменты:

1) Как и в случае встроенных макроопределений (п.3.5, п.4.1.2.2, п.4.3.2.1) физически описанная подмена в выражениях вызова функции ее макроопределением и ссылок _A - _Z в макроопределении указываемыми им аргументами НЕ производится! - Неявно эта подмена происходит непосредственно при развертке выражения макроопределения в Структуру Активаций (СА), реализуемой коллективом микро-ЭВМ (микропроцессоров), где при развертке СА указываемые ссылками _A - _Z выражения – аргументы разворачиваются в соответствующие ветки (поддеревья) СА.

    Исключения:

a) В макроопределении ссылки _A - _Z НЕ действуют в качестве аргументов генератора *Lit и воспринимаются как обычные атомы
b) Указываемые ссылками параметры (_<идентификатор>) непосредственно подставляются вместо ссылок в макроопределения

2) Параметры _a - _z возвращают унарные R-значения аргументов вызова (7-2) или (7-1) по умолчанию. Примитив _Args возвращает R-значение слоя аргументов из (7-2). Эти примитивы обычно используются для анализа корректности аргументов пользовательской функции

3) Как и при обычном доступе к подпространству по его имени-индексу (п.2.6) поиск макроопределения функции пользователя по ее имени (имени-индексу подпространства) из вызова (7-2) производится сначала в пространстве (а) $Eval (п.2.6), исполняющей выражение с вызовом (7-2) функции и обрабатывающей ее макроопределение. И точно также в отсутствие там этой функции (макроопределения) она ищется в пространстве (b) $Eval, вышестоящей по уровню иерархии в СА над $Eval (a) и исполнявшей выражение с $Eval (a) и т.д. вверх по уровням иерархии дерева СА

4) Указываемые в вызове (7-2) 'прозрачные' аргументы $NoOut, _Out (п.4.1), _Sum (п.4.2), _Tout, _If и _Scale (п.4.2, п.4.3) невидимы ссылками _A - _Z и автоматически наследуются (используются) корневой функцией описываемого макроопределением выражения при его развертке в СА.

5) Напомним, что аргумент – литерал в (7-1) и (7-2) согласно концепциям ФПМ (р.3) является примитивом (микро-ЭВМ в СА), генерирующим унарное (единственный элемент со свойством %~;%, НЕ поток) значение

6) Корневой (и не только!) функцией выражения – макроопределения может быть $Eval (р.6), выполняющая поток выражений и определяющая собственное пространство с подпространствами

7) Выражение макроопределения в (7-1), как и выражения – аргументы в (7-1) и (7-2) могут использовать встроенные макроопределения (п.3.5, п.4.3.2.1 и др.)

8) Выражение макроопределения в (7-1), как и выражения – аргументы в (7-1) и (7-2) могут содержать вызовы макроопределений других пользовательских функций, однако в последовательности таких вызовов исходное

макроопределение (вызов) не может повторяться, что контролируется функцией $Eval

Приводимые далее примеры макроопределений некоторых общеупотребительных в различных областях стандартных функций призваны продемонстрировать и возможности параллельных вычислений, причем как на уровне потоков в генерируемых из макроопределений выражениях пользовательских функций, так и на уровне их микропрограмм (р.5)

7.1. Вычисления факториалов

  Fact(<Количество[n]> [,<чет/нечет>]) – в отсутствие <чет/нечет> генерирует ряд
      1!, 2!, 3!, 4!, …, n! (1, 3, 6, 24, …).
Признак <чет/нечет> (любое четное или нечетное целое!) пропускает на выход функции только, соответственно, факториалы четных или нечетных значений их аргументов i=1,2,…. В любом случае n - количество элементов выходного потока функции Fact. По умолчанию аргументы принимают значения, соответственно, 1 и # (неопределенное значение).

Макроопределение:

Fact:(*Row(From:1,All:_A,X:_B,
	   _Par(All:{_If(%.9+~,%,`!%\.%->!`,_Go),`0->!`}
		  X:{`All->$a`,_If(%.9+%,`All*2;++;->All`)}
	   	),
	   {_If(%%,_Go),`$a=$n`,_if(%=%,_Break),
	    `$i`,_if(%.9~0%,`$i+1;*!;->!`),`X`,
	    _if(%.92%,`$i+1`,_if(%.92%,_Go),_Skip)
	    _if(%.9~2%,`$i+1`,_if(%.9~2%,_Go),_Skip)
   	   } 
	  ),1,#
     )

Комментарий:

Макроопределение Fact здесь строится на базе генератора *Row и в качестве параметра All (количество генерируемых значений ряда, п.4.1.2) принимается ссылка _A на выражение - аргумент пользовательской функции Fact. Второй параметр X отсутствует в определении *Row и вводится дополнительно, что НЕ возбраняется согласно п.3.4.1. Этому параметру присваивается значение второго аргумента (чет/нечет) пользовательской функции Fact (макроса), либо он отсутствует и является неопределенным (#). В соответствии с п.3.4.1.2 примитив _Par организует обработку этих параметров, поступающих в регистре '!' калькулятора _Calc:

  Целочисленное НЕ равное 0 значение All (ссылка _A) без слоя нормально принимается: выделяется атом, иначе All принимается равным 0, тем самым исключая выдачу результатов на выход функции. В люом случае полученное значение All сохраняется в регистре $a калькулятора _Calc. В случае целочисленного положительного X (выдача факториалов четных или нечетных значений) значение All удваивается и к нему добавляется (операция ++) 1.

Следом за обработкой параметров функции следует ряд операций (в скобках {}) собственно по выполнению функции Fact: Вначале контролируется завершение операций, когда число $n сформированных на выходе значений достигает требуемого исходным значением All ($a) и в этом случае операция _Break вызывает завершение операций. Формула '$i' читает в регистр '.' число циклов операций и если оно отлично от 0, то предшествующее значение результата '!' умножает на ($i+1), вычисляя очередное значений факториала (%i+1)! и помещая его в регистр '!'.

Если параметр X не является четным или нечетным целым, то вычисленное значение регистра '!' отправляется на выход. Иначе если четности X и ($i+1) НЕ совпадают, то операцией _Skip полученный результат пропускается: не выдается на выход и $n НЕ увеличивается на 1.

Примеры:

	Fact(6,2) генерирует ряд чисел 2!, 4!,  6!, 8!, 10!,  12! 
	Fact(6,1) генерирует ряд чисел 1!, 3!,  5!, 7!,  9!,  11!  
	Fact(6)   генерирует ряд чисел 1!, 2!,  3!, 4!,  5!,  6! 
	Fact(6,`Abc`) генерирует ряд чисел 1!, 2!, 3!, 4!, 5!, 6! 

7.2. Вычисления степеней

  Degree(<основание[ степени]>,<к-во[n]>[,<чет/нечет>][,0]) – в отсутствие <чет/нечет> и далее 0 (4-й аргумент) генерирует ряд основания в последовательности степеней:
      1, 2, 3, 4, …, n.
Признак <чет/нечет> (любое четное или нечетное целое!) пропускает на выход функции только, соответственно, степени с четными или нечетными значениями их показателей n=1,2,…. В случае 0 - значение 4-го аргумента генерация начинается с 0-й степени. В любом случае n - количество элементов выходного потока функции Degree. По умолчанию аргументы принимают значения, соответственно, 1,1,# (неопределенное значение) и 1.

Degree:(*Row(From:1,Base:_A,All:_B,X:_C,Y:_D,
	     _Par(All:{_If(%.9+~,%,`!%\.%->!`,_Go),`0->!`}
		 Base:{_If((%.9~,%,%./~,%),`!%\./%->!`,_Go),_Break}
		    X:{`All->$a`,_If(%.~9+%,_Go),`All*2;++;->All`},
		    Y:{_If(%.90~,%,_Go),`1->!`}
		),
	     {`$n=$a`,_if(%=%,_Break),
	      `Y`,_if(%9~0%,`Base*!;->!`),
	      `X`, 
	      _if(%.92%,`$i+Y`,_if(%.92%,_Go),_Skip) 
	      _if(%.9~2%,`$i+Y`,_if(%.9~2%,_Go),_Skip)
	     }
	   ),1,1,#,1
      )

Пример генерации потока степеней с основанием 2:

   Degree(2,5)     - 2, 4, 8, 16, 32

   Degree(2,5,1)   - 2, 8, 32, 128, 512  (нечетные степени)

   Degree(2,5,2,0) - 1, 4, 16, 64, 256  (четные степени, начиная с 0-й)

7.3. Вычисления известных функций посредством степенных рядов

    Ниже используются разложения функции в ряды, приведенные в [1].

7.3.1. Вычисление Exp(X) - экспоненты

Exp(<переменная>) – Вычисление функции exp(x) с погрешностью НЕ хуже 0.0001 [1]

Макроопределение:

   Exp:$Sync(Degree(_A, 20),Fact(20),Sum:0.0,Err:0.0001,
	     {_If(%%,`$S%!%->!,!++`,_Go),
	     `a/b;$S+=.;=Err`,_if((%<%,%=%),_End),`%%->!`
	     }
            )

Комментарий:

1) Корневая функция $Sync макроопределения синхронно обрабатывает генерируемые пользовательскими функциями Degree (п.7.2) и Fact (п.7.1) , соответственно, ряды степеней 1, 2 и т.д. переменной (ссылка _A) и факториалов 1!, 2!,…. Стандартный параметр Sum задает исходное значение регистра $S (Сумматора). Дополнительный параметр Err - погрешность вычислений.

2) Операция _If по завершению кортежей - потоков от Degree и Fact (отсутствие свойств у регистра '!') помещает результат вычислений из $S в регистр '!', дополняя его свойства свойством %!% и увеличивая значение последнего на 1 (операция ++).

3) Иначе отношение a/b (a и b - nэлементы очередного кортежа от Degree и Fact) пополняет сумматор $S и затем сравнивается с Err. Если a/b меньше или равно Err, то операция _End закрывает входные потоки от Degree и Fact, вызывая повторно операцию (2). Иначе регистр '!' сбрасывается до не имеющего свойств и тем самым блокируется выдача его значения на выход функции. Это же действие можно было инициировать операцией _Skip.

Примеры: <br /><br />
   Exp(1) возвращает  2.71828 с округлением по последнему знаку. При 
          этом МПК обработал 8 кортежей

   Exp(2) возвращает  7.38904 с округлением по последнему знаку. При 
          этом МПК обработал 11 кортежей

7.3.2. Вычисление Sin(X) – синуса

Sin(<переменная>) – Вычисление функции sin(x) с погрешностью не хуже 0.0001 [1]

Макроопределение:

   Sin:$Sync(Degree(_A, 20,1),Fact(20,1),Sum:0.0,Err:0.0001,
	     {_If(%%,`$S%!%->!`,_Go),
	     `$n->!;a/b`,_If(%.92%,$S+=.),_If(%.9~2%,$S-=.),
	      `.=Err`,_if((%<%,%=%),_End),`%%->!`
	     }
            )

Главное отличие от макроопределения Exp (п.7.3.1) в генерации рядов (Degree) с нечетными степенями n=1,3,5,… и нечетными 'n' с факториалами 'n!'. В случае нечетного значения регистра $n (количество принятых и уже обработанных кортежей) из содержимого регистра S вычитается отношение a/b (регистр ‘.’). Наконец, первая операция _If НЕ увеличивает содержимое регистра $S на 1.

  Примечание: Аналогично без особых проблем можно организовать вычисление других тригонометрических функций, а также интегральных синуса и косинуса.

7.4. Вычисления известных функций посредством цепных дробей

Используется метод [2] представления функции подходящей дробью, получаемой из соответствующей цепной дроби с заданным числом циклов – звеньев. Этот метод предпочтительнее тем, что число циклов вычислений (звеньев цепной дроби) определяет погрешность вычислений, слабо зависящую от значения аргумента вычисляемой функции. Именно потому этот метод использовался микропрограммами одной из первых отечественных ЭВМ ‘Промiнь’. И потому погрешность , как параметр, отсутствует в последующих макроопределениях функций.

7.4.1. Вычисление Exp(X) - экспоненты

Вычисляющая Exp(X) подходящая дробь (выражение) из цепной в 5 циклов имеет вид [2]:

      (1680+840x+180x^2+20x^3+x^4) / (1680-840x+180x^2-20x^3+x^4),

где ^ - операция возведения ‘x’ в степень.

Exp(<переменная>) – Вызов пользовательской функции exp(x)

Макроопределение:

 Exp:$Sync($Sync(Degree(_A,5,#,0,_Out(Dg:)),
 		 *Stream(1680, 840, 180,20,1,_Out(Str:{`$n`,_if(%.9~2%,`!%9~+%->!`)})
		 {_If(%%,`$S%!%->!`,_Go),`a*b;$S+=.;%%->!`}
		),
	   $Sync(Dg:Chanal,Str:Chanal,Sum:0.0,
		 {_If(%%,`$S%!%->!`,_Go),`a*b;$S+=.;%%->!`}
		),
	   _If(%~%,`a/b;->!`)
	  )

Комментарий:

1) !-я внутренняя (аргумент) $Sync посредством своих аргументов Degree и *Stream формирует потоки, соотвественно, степеней X (ссылка _A макоопределения) от 0 до 4 и коэффициентов от 1680 до 1, используемых как в числителе, так и знаменателе подходящей дроби. Потому функции Degree и *Stream снабжены дополнительными выходами (примитив _Out), соотвественно, Dg и Str для передачи формируемых потоков второй внутренней (макроопределение) функции $Sync по одноименным каналам (Chanal). При этом выход Str снабжен операциями меняющего знак '+' на отрицающий его (%9~+%) знак '-' у каждого второго элемента потока (требования знаменателя подходящей дроби)

2) Операции обоих внутренних $Sync идентичны: элементы 'a' и 'b' получаемых синхронно потоков переменожаются (кортеж) и произведение добавляется к $S в исходном состоянии равном 0.0 (Sum:0.0). По окончанию потоков $S переправляется на выход

3) Внешняя $Sync обрабатывает выходы (2) внутренних (аргументы) $Sync - единственный кортеж, деля выход 1-го ('a') на выход второго ('b'), используя для этого единственную операцию _If (3-й аргумент)

Внимание! Особенность приведенного макроопределения в том, что вычисление числителя и знаменателя подходящей дроби выполняется параллельно и главное теми же средствами Degree и *Stream.

Примеры:

   Exp(1) возвращает  2.718282  с округлением по последнему знаку. 

   Exp(2) возвращает  7.3889  с округлением по последнему знаку. 

7.4.2. Вычисление Tg(X) – тангенса

Здесь с не меньшей чем в п.7.4.1 точностью достигается результат относительно простой подходящей дробью:

    (945 *X – 105*X*3 + X^5) / (945 – 420*X^2 + 15*X^4)

Tg:$Sync($Sync(Degree(_A,3,1),
		*Stream(945, -105,1),
		{_If(%%,`$S%!%->!`,_Go),`a*b;$S+=.;%%->!`}
	      ),
	 $Sync(Degree(_A,3,2,0),
		*Stream(945,-420,15),_
		{_If(%%,`$S%!%->!`,_Go),`a*b;$S+=.;%%->!`}
	      )
	 _If(%~%,`a/b;->!`)
       )

В отличие от п.7.4.1 коэффициенты и степени полиномов в числителе и знаменателе различные: в числителе - нечетные (3-й аргумент - 1), а в знаменателе четные (3-й аргумент) степени да еще, начинающиеся с 0 (0 - 4-й аргумент). Потому каждая внутренняя (аргумент) $Sync имеет (входы) собственные аргументы *Degree и *Stream, выполняются параллельно и независимо друг от друга – асинхронно. В отличие от п.7.4.1 отсутствует 'Sum:0', поскольку регистры $S устанавливаются в 0 по умолчанию стандартного параметра Sum (п.3.4.1.1)

7.5. Вычисление тангенса значений из потока

Tgs(<поток значений [X1, X2,…]>) – возвращает поток значений Tg(X1) , Tg(X2),…

Макроопределение:

    Tgs:$Eval(Lit(Tg(!Data()),_A)

Комментарий:

1) 1-й аргумент функции $Eval (р.10) в качестве литерала (аргумент Lit, п.3.2) определяет унарное (единственное) значение – выражение, а второй аргумент – ссылка (_A) на исходный (аргумент Tgs) поток обрабатываемых этим выражением данных

2) Функция Data согласно п.3.2 извлекает очередной элемент потока, указываемого ссылкой ‘_A’ и функция !Form приводит его к числовому атому.

3) Полученный числовой атом в (2) передается пользовательской функции Tg (п.7.4.2) в качестве аргумента

4) Контроль корректности элементов исходного потока $Tgs, выполняемый функцией $Eval, может оказаться недостаточным. В этом случае нужно в приведенном макроопределении исключить функцию !Form, дополнив аргументы функции $Eval прозрачным аргументом вида:

   b:{<операции по контролю потока значений [X1, X2,…]>}

Внимание! В обрабатываемых $Eval кортежах меняется только значение очередного элемента потока и потому развертка в СА выражения – первого аргумента $Eval производится только при обработке первого кортежа

Примеры:

Tgs(*Stream(1,2,3) возвращает поток значений Tg(1), Tg(2), Tg(3)
Tgs(*Num(4,0.1, 1.1)) возвращает: Tg(1.1), Tg(1.2), Tg(1.3), Tg(1.4)

7.5. Генерация и заполнение ячеек матриц

Матрицу можно рассматривать как иерархическую структуру, введенную п.2.1: слой из строк (первый уровень), строка из колонок (2-й уровень) и т.д. Следовательно, введенных предыдущими разделами встроенных функций и примитивов достаточно для генерации и обработки матриц. Однако вводимые здесь макроопределения пользовательских функций по созданию и заполнению матриц призваны сделать эти операции привычными для пользователей при использовании их в вычислениях, причем, с контролем этих операций, например границ матрицы. Одновременно демонстрируется возможность ускорения этих операций распараллеливанием их выполнения.

7.5.1. Генерация матриц

1) Одномерная матрица (вектор) создается следующей функцией:

    Vector(<К-во элементов>[,<содержимое ячеек>])

Макроопределение:

Vector:$Async(*Row(All:_A,FROM:_B,
		   _Par(All:{_If(%.9+~,%,`!%\.%->!`,_Go),`0->!`}
		  ),Sum:(),
	      Out:{_If(%~%,`<-!;$S+=.`,_Skip),`$S->!`}
	     )

При этом *Row генерирует поток из одинаковых All структур (содержимое ячеек), включая неопределенное значение в отсутствие второго параметра функции Vector. Функция $Async определяет стандартный параметр Sum (исходное значение $S) как пустой слой и потому на главном выходе Out операцией '+=' слой $S пополняется копией (<-) очередного элемента с потокового входа функции $Async. По окончании этого потока итоговое $S (вектор) возвращается на выход $Async

2) Двумерная матрица создается следующей функцией:

        Matrix2(<К-во строк>,
               <К-во колонок[- ячеек в строке]>
               [,<содержимое ячеек>]
              ) 

Макроопределение: <br />

	Matrix2:(Vector(_A,Vector(_B,_C)),2,2,#)

По аналогии можно определить функции Matrix3 и.т.д.

3) Рассмотрим возможность параллельного создания и заполнения частей большой матрицы размером M x N. Разобьем такую матрицу на две размерами M1 x N и M2 x N так, что M=M1+M2.
Выражение

  $Async(*Sel(Matrix2(< M1 >,< N >),Out:`!%@%->!`),
         *Sel(Matrix2(< M2 >,< N >),Out:`!%@%->!`),
	 Sum:(),
	 Out:{_If(%~%,`$S+=!`,_Skip),`$S->!`}
        )

посредством $Async (п.4.3.3) организует асинхронное (параллельное) заполнение матриц M1 x N и M2 x N неопределенными значениями # (по умолчанию). При этом также параллельно из каждой из этих матриц на верхнем уровне иерархии выделяются генератором *Sel (операции приведения регистра '!' на выходе Out) R-значения (ссылки УКА и УКС) строк и поступают в произвольном порядке в изначально пустой слой $S (параметр Sum).
Нетрудно разделить исходную матрицу M x N на большее (чем 2) количество частей, заполняемых параллельно и, следовательно, более эффективно, как и построить макроопределение функции, все это осуществляющее.

Вместо заключения:

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

Используемая литература:

_1. Э. Маделунг. Математический аппарат физики, справочное руководство.
     `Наука`, 1968, стр.85-87
_2,. Э. Денисова, А.Кучер. Основы вычислительной математики. Санкт-
      Петербургский университет ИТ, Механики и Оптики, 2010, стр.24-25

Используемые сокращения:

ФПМ	- функциональная потоковая машина
р.5	- раздел 5 проекта ФПМ
п.2.3	- пункт 3 раздела 2
СА	- Структура Активаций – реализующий выражение языка (суперпозицию
 	  функций) коллектив соответствующим образом связанных микро-ЭВМ, 
 	  каждая из которых  реализует отдельную функцию или примитив 
 	 (калькулятор) _Calc
ДРП	- динамически распределяемая память, над которой функуционируют 
 	  микро-ЭВМ СА
БП	- блок ДРП, выделяемый под атом или слой структуры
УКА	- указатель (ссылка на БП) атома (п.2.3)
УКС	- указатель (ссылка на БП)  слоя (р.2)