Язык программирования J

jip15-05-2009 15:55jip1924-03-2007 18:07
J (www.jsoftware.com) это современный развитый универсальный язык программирования, ориентированный на сложную обработку данных. Наряду с K (www.kx.com), Nail и несколькими другими является наследником "широко известного в узких кругах" языка APL.

J – очень богатый язык. Его можно годами изучать и использовать, но так и остаться новичком. Этим J резко отличается от более простых языков, таких, как Basic или Java, несколько месяцев работы с которыми могут сделать Вас экспертом. Усилия, требуемые для достижения уровня эксперта по программированию на J, сопоставимы с теми, что требуются, чтобы стать экспертом в программировании на C++. Но вместе с тем, как ни парадоксально это звучит, суть языка J настолько проста и целостна, что можно быстро выучить минимум, достаточный для решения реальных, интересных проблем. Легко выучить Basic или Java в степени, достаточной для решения тривиальных проблем, но ещё легче выучить J в объеме, достаточном для решения более интересных и сложных проблем. Достигнув этого уровня, разработчик окажется только в самом начале пути постижения языка, совершенствования стиля и сложности программирования.

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

Некоторые понятия и соглашения, принятые в языке J [dr-klm].
  • Существительное. Объект для манипулирования: аргумент, параметр, данное.
  • Скаляр, массив, упаковка. Разновидности существительных. Упаковка аналогична понятию структура в языке Си.
  • Глагол. Оператор, операция, обозначение действия. Аналог понятия функция в языке Си. Оценивается на этапе исполнения. Оперирует существительными. Производит существительное.
  • Монадный случай, монада. Частный случай применения глагола к одному аргументу.
  • Диадный случай, диада. Частный случай применения глагола к двум аргументам.
  • Действие, обозначаемое одним и тем же глаголом в монадном и диадном случае, как правило, различно, но часто связано концептуально.
  • Наречие. Оперирует существительным или глаголом. Оценивается на этапе интерпретации. Производит глагол.
  • Союз. Оперирует двумя параметрами: существительными и/или глаголами в любых сочетаниях. Оценивается на этапе интерпретации. Производит глагол.
  • Оценка выражений производится справа налево.
  • Каждая команда занимает одну строку.
  • Всё, что указано после NB. , считается комментарием.
Несколько примеров

J является интерпретируемым языком, поэтому после ввода программы сразу выдается результат её выполнения.

1. Программа "Hello, world!" (1-я строчка - код программы, 2-я - результат её выполнения):
код:
1:
2:
   'Hello, world!'
Hello, world!

2. Вычисление среднего арифметического списка чисел (1-я строчка - определение функции, 2-я - ее вызов, 3-я - результат ее выполнения):
код:
1:
2:
3:
   avg=: +/ % #
   avg 1 2 3 4    NB. вызов функции с аргументом - вектором из четырёх чисел
2.5
Глагол "#" ("сосчитать") считает количество элементов в массиве. Цепочка глагола "+" ("прибавить") и наречия "/" ("между") суммирует элементы массива (выполняет операцию "+" между элементами массива). Глагол "%" ("разделить") делит полученную сумму на полученное количество элементов. Глагол "avg" является цепочкой из трех глаголов, такая цепочка называется вилкой. Применение вилки "Г0 Г1 Г2" к аргументу "y" в виде "(Г0 Г1 Г2) y" эквивалентно "(Г0 y) Г1 (Г2 y)", или, в терминах языка Си: "Г1(Г0(y),Г2(y))".

Несколько примеров использования только что определенного глагола avg:
код:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
   v=: 1 2 3 4    NB. запишем в переменную "v" вектор из 4 чисел

   avg v          NB. вычислим среднее арифметическое элементов вектора "v"
2.5

   avg\ v         NB. вычислим среднее арифметическое префиксов аргумента: "1", "1 2", "1 2 3", "1 2 3 4"
1 1.5 2 2.5

   avg\. v        NB. вычислим среднее арифметическое суффиксов аргумента: "4", "3 4", "2 3 4", "1 2 3 4"
2.5 3 3.5 4

   2 avg\ v       NB. вычислим скользящее среднее внутри окон шириной 2: "1 2", "2 3", "3 4"
1.5 2.5 3.5

   2 avg\. v      NB. вычислим скользящее среднее вне окон шириной 2: "3 4", "1 4", "1 2"
3.5 2.5 1.5

   avg"1 D. 1 v   NB. вычислим производную функции "avg" в каждой точке аргумента
0.25 0.25 0.25 0.25

3. Пример визуализации функции. Нарисуем, например, график использованных выше функций "вычислить среднее префиксов" и "вычислить среднее суффиксов":
код:
1:
2:
3:
  load 'plot'               NB. загрузить пакет рисования диаграмм
  plot (avg\ ,: avg\.) v    NB. вектор "v" подаётся на вход уже знакомой нам цепочке глаголов типа "вилка"
                            NB. (в скобках), результат работы которой передаётся далее глаголу "plot"
Глагол ",:" ("наклеить") склеивает два своих аргумента, формируя из них двустрочный массив. Аргументами ему служат глаголы "avg\" и "avg\.". Эти глаголы в качестве аргумента получают "v".

История языка

J был разработан в 1990 году Кеннетом Айверсоном (Kenneth E. Iverson) и Роджером Хьюи (Roger Hui). Своё название язык получил в честь жены и верной соратницы Айверсона Джин. Кеннет Айверсон также известен как автор языка APL и как теоретик в области программирования и системы математических обозначений, за что в 1979 году был удостоен престижной премии Тьюринга. J был создан на основе языка APL и функциональных языков FP и FL. J был задуман как клон APL, использующий исключительно символы ASCII, поскольку сложная мнемоника APL сдерживала его распространение. Наследник тоже не смог обойтись без сложной нотации, но, в отличие от прародителя, смог найти свою нишу на рынке. В начале разработки J от группы отделился Артур Уитни (Arthur Whitney) и занялся разработкой собственного языка, который он назвал K (тоже весьма интересный и мощный язык).

О реализации

Система J и созданные на ней приложения переносимы, работают на платформах Windows, Unix, Mac и PocketPC как в графическом интерфейсе (Java frontend), так и в командной строке.

Большая часть J реализована на самом себе. Остальная часть написана на C с использованием APL-подобных конструкций. См. код интерпретатора прото-J и прото-K, написанный Артуром Уитни когда он как-то заехал к Кеннету; Айверсону на ланч (это кстати ранний прим;ер генеративного метапрограммирования - прим. [muchandr])

Поддерживаемые типы данных:
  • простые: числовые (булевы, целые, рациональные, с плавающей точкой, комплексные, рациональные произвольного размера) и текстовые (литералы, символы, строки, строки UNICODE);
  • составные: массивы (плотные и разреженные); упаковки; объекты.
Большинство операторов в J полиморфны относительно типов данных.

цитата :
http://dr-klm.livejournal.com/42312.html...=484168#t484168

В J довольно мало возможных ошибочных (не с;;тандартных) ситуаций. Везде, где только можно, операции языка определены так, чтобы уменьшить (или совсем исключить) возможнос;ть возникновения нестандартных ситуаций по ходу выполнения программы. В этом плане отличный пример представляет из себя, упомянутое Вами, деление на ноль. В J это не ошибка, и производит вполне закономерный результат "_" либо "__" (плюс- или минус- бесконечность). И даже деление нуля на ноль в J -- не ошибка, а вполне стандартная математическая операция, результат которой определен (и равен нулю). Поч;ему он определен, и почему определен в J именно так (отличным, кстати, от APL способом) рассматривается в статье E. E. McDonnell: "Zero Divided by Zero". И причина, по которой весь этот сыр-бор был затеян еще Falkoff-ом and Iverson-ом -- именно в том, чтобы не вызывать exceptions по ходу выполнения.

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

Из интернет-репозитария можно загружать дополнительные пакеты программ, обеспечивающие обработку мультимедиа-данных, интерфейсы к базам данных и внешним .dll/.so библиотекам, обработку матриц (интерфейс к библиотеке LAPACK), обработку таблиц Excel, и многое другое

О лицензировании и техподдержке

J бесплатен для установки и распространения. Реализация интерпретатора современной версии языка J закрыта и бесплатна. Существует открытая и бесплатная реализация интерпретатора для ранней версии языка J, а также проект открытой реализации языка, подробности см. в http://www.jsoftware.com/jwiki/Guides/General_FAQ/J_License

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

Ссылки
  1. J Software
  2. Kx Systems
  3. J programming language - Wikipedia
  4. русский перевод словаря языка J от Константина Метлова
  5. Язык программирования J, введение, от него же
  6. muchandr - ЖивойЖурнал (интересно пишет о K, kdb и немного о J)
recvezitor01-01-1970 10:00027-03-2007 10:27
Это новая разновидность MatLab'а или попытка избавиться от Фортрана?
jdoe01-01-1970 10:00027-03-2007 13:58
Тока как-то пугает фраза -
"Его можно годами изучать и использовать, но так и остаться новичком".
по отношению к АПу.
jip16-05-2009 11:46jip527-03-2007 16:17
J vs. MatLab

MatLab и J предоставляют пользователям схожие возможности.

Фундаментальное отличие J от MatLab, по Ричарду Брауну (Richard L. W. Brown), http://portal.acm.org/ft_gateway.cfm?id=...CFTOKEN=6184618 , это наличие наречий и союзов, т.е. функций с фиксированной валентностью: наречия монадны (они применяются к своему левому аргументу), союзы диадны. Благодаря им можно конструировать новые функции.

Возьмем, например, союз &. Запись u&v производит композицию глаголов u и v; ^&2 производит возведение в квадрат привязывая к функции "в степени" правый аргумент 2; 2&^ производит функцию "2-в-степени". Или возьмем наречие /. В J можно из функции + и наречия / сконструировать новую функцию +/ которая суммирует элементы аргумента(ов), в MatLab у этой функции есть эквивалент sum. Но в J можно также сконструировать функцию -/ которая вычитает элементы аргумента(ов), а в MatLab такого эквивалента нет, его надо писать самому.

Оба MatLab и J имеют интерфейс в библиотеку LAPACK. Оба MatLab и J способны обрабатывать массивы любой размерности. Однако в J эта возможность закладывалась изначально, при создании языка и интерпретатора. Matlab же создавался как средство для работы с матрицами, а возможность работы с массивами произвольной размерности была добавлена только в версии 5.0.

У MatLab есть ограничения, связанные с m-файлами: (1) скрипт-файл не может содержать определение функции если сам является определением функции, (2) функции можно создавать только в файлах, а из командной строки нельзя.

Как утверждается в Wikipedia, у Matlab немного путаный синтаксис (например, скобки используются при вызове функций и при индексации в массиве), нет пространств имён, многие функции по-разному обрабатывают векторы и матрицы, индексы в массивах начинаются с 1, затруднена обработка составных типов данных (например, деревьев). [абзац добавлен 2007-09-05]

В отличие от MatLab, в J можно скомбининировать несколько функций без использования промежуточных переменных в роли входных и выходных параметров, и присвоить новой функции имя. Например, определив следующие функции через примитивы:
код:
1:
2:
3:
4:
5:
6:
   of =: @:           NB. над (композиция функций)
   sqrt =: %:         NB. квадратный корень [элементов] аргумента
   sum =: +/          NB. плюс между элементами аргумента
   squares =: *:      NB. в квадрат [элементы] аргумента
   data =: ]          NB. правый аргумент диады (бинарного оператора)
   mean =: sum % #    NB. сумму делить на количество (арифметическое среднее)
можно затем определить новую функцию d вычисления среднеквадратичного отклонения:
код:
1:
   d =: sqrt of sum of squares of (data-mean)
Обработка массивов в J производится без циклов и явного перебора индексов, обычно J-программы вообще не содержат циклов. "Программирование на J представляет из себя компоновку больших блоков, и основное время процессор проводит ВНУТРИ глаголов, а уж там, внутри интерпретатора, все оптимизировано до невозможности, можете не сомневаться." ((c) dr-klm).

Пример. Измерение скорости выполнения и затрат памяти на обработку определенным выше глаголом d массива из 10000 действительных чисел:
код:
1:
2:
3:
4:
5:
6:
   9!:14 ''                    NB. показать версию J
j601/2006-11-17/17:05
   ts =: 6!:2, 7!:2@]          NB. глагол для измерения времени и расхода памяти
   v =: %/ ?. 2 10000 $ 100    NB. вектор из 10000 случайных действительных неотрицательных чисел
   100 ts 'd v'                NB. измерим средние время и расход памяти на 100 вызовов функции d с аргументом v
0.00020071 263168

J vs. Fortran

MatLab появился как попытка предоставить дружелюбный интерфейс к фортрановским пакетам LINPACK и EISPACK. J появился как попытка сделать язык APL более дружелюбным (ладно, ASCII-совместимым ;-) ). Сравнивать J и Fortran трудно, поскольку они относятся к разным направлениям развития языков программирования.
jip07-08-2007 16:00jip227-03-2007 16:45
цитата :
Исходное сообщение от jdoe
Тока как-то пугает фраза -
"Его можно годами изучать и использовать, но так и остаться новичком".
по отношению к АПу.
Я пользуюсь J с перерывами в течение 5 лет, один из моих аппов считал систему из двойных интегральных уравнений, используя при этом mmap. Т.е. я могу решить поставленную задачу, но оцениваю свой уровень в J скорее как "новичок" чем "продвинутый пользователь".

Поскольку кривая вхождения (learning curve) в языках J и K довольно высока, то здешнее понятие "новичок" и "новичок" в, скажем, PHP, находятся на разных уровнях.
recvezitor01-01-1970 10:00027-03-2007 19:27
а J# из этой же области?
Есть в J возможность задавать размерность массива в процессе выполнения а не в процессе компиляции?
jip16-05-2009 11:48jip228-03-2007 10:21
цитата :
Исходное сообщение от recvezitor
а J# из этой же области?
Нет. J#, J++ это другие языки.

цитата :
Исходное сообщение от recvezitor
Есть в J возможность задавать размерность массива в процессе выполнения а не в процессе компиляции?
Есть. Поскольку язык интерпретируемый, стадия компиляции отсутствует, т.е. исходный код одновременно является исполняемым кодом. Пример изменения размерности:
код:
1:
2:
3:
4:
5:
6:
7:
   v =: i. 5      NB. инициализируем переменную v вектором чисел 0 1 2 3 4
   v =: 3 $ v     NB. укоротили вектор до первых трёх элементов: 0 1 2
   v =: 6 $ v     NB. удлинили вектор до 6 элементов, значения циклически берутся из исходного массива: 0 1 2 0 1 2
   v =: 2 3 $ v   NB. переформатировали вектор в матрицу 2 строки на 3 столбца
   v              NB. отобразили v
0 1 2
0 1 2
recvezitor01-01-1970 10:00028-03-2007 13:59
цитата :
Нет. J#, J++ это другие языки

почему так странно? А там у них не возникли проблемы с авторством?
А кто его использует? Только ученые? Он вообще востребован?
Как я понял он нужен для математических вычислений, при этом имеет удобрный интерфейс. Ну и допустим если надо сделать серьезный проект, что лучше использовать J or Fortran?
Есть у него возможность создавать отдельные экзешники?
Его функции можно вызывать из других языков?
jip01-01-1970 10:00028-03-2007 15:34
цитата :
Исходное сообщение от recvezitor
цитата :
Нет. J#, J++ это другие языки

почему так странно? А там у них не возникли проблемы с авторством?
Вроде не слышал, но здесь я не спец. J появился в 1990 году, поэтому проблемы могли возникнуть не у JSoftware, а у Microsoft.

цитата :
Исходное сообщение от recvezitor
А кто его использует? Только ученые? Он вообще востребован?
На главной странице JSoftware перечислены некоторые из них. Язык J не распространён широко, но у него есть свой сегмент пользователей, в т.ч. русскоязычных. Распробовав J, трудно возвращаться к Fortran'у.

цитата :
Исходное сообщение от recvezitor
Как я понял он нужен для математических вычислений, при этом имеет удобрный интерфейс. Ну и допустим если надо сделать серьезный проект, что лучше использовать J or Fortran?
Это Вам выбирать. Ответ зависит от проекта. Особенности программ на J и K. (1) Они очень компактны. (2) Их трудно читать. Для бросового кода и прототипирования они не подходят. (3) Один из знатоков APL как-то сказал что решения на APL (это также относится к J и K) обладают свойствами алмаза - они идеальны, и к ним ни убавить, ни прибавить.

цитата :
Исходное сообщение от recvezitor
Есть у него возможность создавать отдельные экзешники?
J язык интерпретируемый, у таких языков экзешников не бывает. Вы слыхали когда-нибудь о компиляции PHP-скриптов в экзешник? Исполнение скрипта вне среды разработки, естественно, возможно, иначе такой язык никому не будет нужен. Есть возможность блокировки (шифрации?) содержимого файла-скрипта для закрытия исходника.

цитата :
Исходное сообщение от recvezitor
Его функции можно вызывать из других языков?
Да. И наоборот, в J можно вызывать функции из внешних библиотек.
recvezitor01-01-1970 10:00029-03-2007 11:33
цитата :
Исполнение скрипта вне среды разработки, естественно, возможно, иначе такой язык никому не будет нужен

я потому и спросил потому что в матлабе(по крайней мере до 6 версии) запускать программы можно было только из среды разработки.
Честно говоря у меня н возникло большого желания изучать этот язык, по большей части из-за того что он мало распространен и
цитата :
Я пользовался J в течение 5 лет ... но оцениваю свой уровень в J скорее как "новичок" чем "продвинутый пользователь".
jip04-05-2011 11:27jip1225-04-2007 17:33
Поиск локального минимума N-мерной функции
Метод деформируемого многогранника (ткж метод нелинейного симплекса)
Алгоритм: Дж. А. Нелдер и Р. Мид

Find N-dimensional function local minimum
Flexible polyhedron method (aka nonlinear simplex method)
Algorithm: J.A. Nelder and R. Mead


Внимание! При перепечатке ссылка обязательна.

Предисловие

Рассмотрим реализацию на языке J одного вычислительного метода, который изучают в ИФИТе на 3-м семестре. Он применяется для решения задачи безусловной минимизации и относится к классу методов прямого поиска (их ещё называют методами нулевого порядка). В разных источниках его называют по-разному: метод Нелдера-Мида (Nelder-Mead method), метод нерегулярного симплекса, метод деформируемого многогранника, метод деформируемых конфигураций. Без комментариев программа занимает 670 байт. На языке Си можно уложиться в 1100 байт.

Блок-схема

См. http://old.dvgu.ru/temp/igor/teach/Nelde...d_flowchart.gif

Исходный код программы в файле nmm.ijs:

код:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
NB. vSolution =: Solve N ; T ; alpha ; beta ; gamma ; epsilon
Solve =: 3 : 0
  'N T a b g e' =: y
  'c d' =. (T % N * %: 2) * (((%: N + 1) - 1) + (N , 0))
  P =: c (;/ (i. N) +/ 1 0) } 0 (0) } (1 0 + N) $ d
  e NMM ^: _ P
  C
)

NB. P =: e NMM P
NB. execute single algoritm iteration, return new P or y unchanged
NMM =: 4 : 0
  F =: f y
  P =: F /:~ y				NB. sort to force L=:0, H=:N
  C =: (+/ }: P) % N			NB. center point
  chgP ^: ((%: (+/ *: F - f C) % (N + 1)) >: x) y	NB. call chgP if exit condition failed, or return y unchanged
)

NB. P =: chgP any_arg
NB. change P and return it; herein we use sorted y in global var P instead of unsorted y
chgP =: 3 : 0
  F =. F /:~ F				NB. sort to force L=:0, H=:N
  'fH_1 fH' =. _2 {. F			NB. extract last two elements
  NB. form candidates to replace x_H:
  NB. R=reflection, E=expansion, So=outer shrink, Si=inner shrink
  'fR fE' =. f 2 {. 'R E So Si' =. C +"1 (a , (-g) , b , (-b)) */ (C - {: P)
  fS =. f S =. So ]`[ @. (fR < fH) Si	NB. select shrink direction

  chkE =. (fE < fR) *. (fR < {. F)	NB. check for expansion
  chkS =. (fR > fH_1) *. (fS < fH)	NB. check for shrink
  newV =. (chkE + +: chkS) { R , E ,: S	NB. elect candidate vector to replace x_H

  newV (chgR ` chgT @. ((fR > fH_1) *. (fS >: fH))) P
)

chgR =: _1 }				NB. replace last row by x in table y
chgT =: ([: -: ] +"1 {.) : ($: @: ])	NB. halve sum of table y and its 1st row (i.e. reduct),
					NB. ignore left arg. Is equiv. to 'P =: -: P +"1 {. P'

Комментарии к исходнику

Строка # 2
Определить глагол «Solve», который инициализирует необходимые переменные, запускает и останавливает итерации алгоритма, и выводит ответ.

Строка # 3
Распаковать элементы правого аргумента «y» в соответствующие глобальные переменные.

Строка # 4
Вычислить вспомогательные значения.

Шаг # 1. Создать вектор из 2-х элементов.


Шаг # 2. Создать скаляр.


Шаг # 3. Прибавить значение скаляра к элементам вектора.


Шаг # 4. Создать скаляр.


Шаг # 5. Умножить элементы вектора на значение скаляра.


Шаг # 6. Записать элементы вектора в соответствующие локальные переменные.


Строка # 5
Заполнить матрицу координат вершин многогранника «P» начальными значениями.

Шаг # 1. Создать вектор из 2-х элементов.


Шаг # 2. Прибавить значение скаляра к элементам вектора.


Шаг # 3. Создать многомерный массив. Размерность задаёт левый аргумент, значения элементов – правый. В данном случае слева вектор длины 2, поэтому создаётся массив с рангом 2 (двумерный). Элементы вектора задают число элементов массива по каждой размерности. Справа скаляр «d», поэтому элементы массива принимают его значение.


Шаг # 4. Заменить элементы в массиве. Правый аргумент задаёт массив, левый перед глаголом задаёт координаты заменяемых элементов, а самый левый задаёт новые значения. В данном случае заменяются все элементы строки с индексом 0 (ноль в скобках). Самый левый аргумент – скаляр 0, поэтому все элементы строки зануляются.


Шаг # 5. Создать вектор длины N из целых чисел от 0 до N-1.


Шаг # 6. Создать таблицу сложения элементов из левого вектора с элементами правого вектора. В данном случае столбцы формирует вектор «i. N» длины N, а строки – вектор из двух элементов «1 0».


Шаг # 7. Упаковать массив. Это подготовительный этап перед передачей массива глаголу замены элементов. Построчная упаковка заставит глагол воспринимать строки массива как координаты заменяемых элементов другого массива. В данном случае координатами станут векторы длины 2.


Шаг # 8. Заменить элементы в массиве. Правый аргумент задаёт массив, левый перед глаголом – координаты заменяемых элементов, а самый левый – новые значения. В данном случае значение «c» присваивается элементам с координатами, полученными на предыдущем шаге.


Шаг # 9. Записать правый аргумент, полученный на предыдущем шаге, в глобальную переменную «P».


Строка # 6
Запустить итерации алгоритма, вызывая глагол «NMM» с левым аргументом «e» – допустимой точностью, и правым аргументом «P» – координатами вершин многогранника. Глагол «NMM» будет выполняться до тех пор, пока возвращаемое им значение не перестанет меняться (т.е. пока не будет достигнут предел). Псевдокод на языке Си:
код:
1:
2:
3:
while (NMM(e,P) != P) {
  P=NMM(e,P);
}
Строка # 7
Вернуть найденный минимум – точку «C» в виде вектора «С» длины N.

Строка # 8
Конец определения глагола «Solve».

Строка # 12
Определить глагол «NMM», исполняющий одну итерацию алгоритма. В данном случае предполагается, что во входных параметрах «x» и «y» находятся, соответственно, допустимая точность и массив координат вершин многогранника. Глагол возвращает массив координат вершин многогранника – если достигнута заданная точность, то прежний, иначе пересчитанный.

Строка # 13
Обработать входной параметр «y» глаголом «f», и записать результат в глобальную переменную «F». Предполагается, что «y» имеет ранг 2 (является таблицей), а глагол «f» имеет ранг 1. Это определяет способ обработки: аргумент воспринимается как вектор (с элементами - строками таблицы «y»), и глагол обрабатывает каждый его элемент (т.е. каждую строку таблицы «y») индивидуально. Результаты обработки укладываются в вектор длины N+1 (число строк таблицы «y»), и этот вектор выдаётся в качестве результата операции «f у». Псевдокод на языке Си:
код:
1:
2:
3:
for (j=0; j<N+1; j=j+1) {
  F[j]=f(P[j]);
}
Строка # 14
Отсортировать элементы «y» по возрастанию элементов вектора «F» и записать результат в глобальную переменную «P». Параметр «y» является таблицей, значит, сортируются строки. Вектор «F» хранит скаляры - результат применения минимизируемой функции (глагола «f») к каждой точке многогранника (т.е. каждой строке таблицы «y»). Значит, первой строкой массива «P» станет вектор с координатами точки, обеспечивающей минимальное значение функции (т.е. точка «P[L]» окажется в массиве «P» под индексом 0), а последней строкой станет вектор с координатами точки, обеспечивающей максимальное значение функции (т.е. точка «P[H]» окажется в массиве «P» под индексом N).

Строка # 15
Вычислить координаты точки «C» и записать полученный вектор длины N в глобальную переменную «C».

Шаг # 1. Исключить из вектора «P» последний элемент (т.е. последнюю строку «P[H]» таблицы «P»). Останутся только первые N строк с индексами от 0 до N-1.


Шаг # 2. Вставить символ операции «+» между элементами вектора и выполнить операцию. В данном случае просуммировать столбцы таблицы «}: P».

Результатом будет вектор


Шаг # 3. Записать правый аргумент - вектор, полученный на предыдущем шаге, в глобальную переменную «C».


Строка # 16
Вызвать глагол «chgP» с параметром «y» несколько раз, при этом число вызовов определяется значением выражения, зависящего от «x» (т.н. условное выполнение). Псевдокод на языке Си:
код:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
I=count_calls(x);
M=y;
if (I>=0) {
  for (i=0; i<I; i=i+1) {
    M=chgP(y);
  }
} else {
  for (i=I; i<0; i=i+1) {
    M=chgP_inversion(y);
  }
}
return M;
где chgP_inversion() - инверсия глагола «chgP» (т.е. для данного «y» найти «M» такое, что «y=chgP(M)»). Если условное выражение равно 0, то глагол «chgP» не вызывается ни разу и возвращается исходное значение «y».

Шаг # 1. Создать скаляр.


Шаг # 2. Вычислить значение минимизируемой функции (глагол «f») в точке «C».


Шаг # 3. Вычесть значение «f C» из каждого элемента вектора «F».


Шаг # 4. Возвести все элементы вектора в квадрат.


Шаг # 5. Вставить символ операции «+» между элементами вектора и выполнить операцию. В данном случае просуммировать элементы вектора «*: F – f C».

Результатом будет скаляр:


Шаг # 6. Поделить левое выражение на правое. Результатом будет скаляр:


Шаг # 7. Извлечь квадратный корень:


Шаг # 8. Выполнить операцию сравнения «больше либо равно» между левым и правым аргументами. В данном случае сравнить выражение, полученное на предыдущем шаге, со значением параметра «x», хранящего допустимую точность «e». Результатом операции будет 0 («ложь») или 1 («истина»).


Шаг # 9. Вызвать глагол с параметром «y» определённое число раз. В даннном случае глагол «chgP» вызывается 0 или 1 раз в зависимости от того, ложным или истинным было выражение, вычисленное на предыдущем шаге. Результатом команды в первом случае станет само значение «y», во втором - значение, которое вернёт глагол «chgP», вызванный с параметром «y».


Строка # 17
Конец определения глагола «NMM».

Строка # 21
Определить глагол «chgP», меняющий массив «P» координат вершин многогранника для одной итерации алгоритма. Глагол использует в качестве входных данных глобальную переменную «P» и поэтому не нуждается во входных параметрах. Но поскольку глаголов без параметров не бывает, мы объявляем «chgP» монадным, т.е. принимающим один аргумент «y», который проигнорируем. Возвращаемое значение – обновлённый массив координат вершин многогранника.

Строка # 22
Отсортировать элементы глобальной переменной «F» по возрастанию и записать результат обратно в глобальную переменную «F». Вектор «F» хранит скаляры - результат применения минимизируемой функции (глагола «f») к каждой точке многогранника. Значит, первым элементом вектора «F» станет минимальный (т.е. элемент «F_L» окажется в векторе «F» под индексом 0), а последним элементом станет максимальный (т.е. элемент «F_H» окажется в векторе «F» под индексом N). Этим мы синхронизируем порядок значений в «F» с порядком точек в «P».

Строка # 23
Извлечь из вектора «F» два последних элемента и записать их в локальные переменные «fH_1» и «fH». Т.о. самое большое значение «F_H» вектора «F» попадёт в переменную «fH», а значение, большее всех остальных из «F», за исключением «F_H», в переменную «fH_1».

(окончание в следующем сообщении)
jip04-05-2011 11:28jip1226-07-2007 16:35
Строка # 26
Вычислить векторы – кандидатуры на замещение «P[H]»: «R» (отражённый), «E» (растянутый), «So» (сжатый от «P[H]»), «Si» (сжатый к «P[H]»). Чтобы посчитать их одновременно, надо избавиться от зависимости векторов «So» и «E» от вектора «R». Для этого используем тождество: R-C==-(H-C), вытекающее из их определения. Векторы вычисляются по одной и той же схеме, но с разными коэффициентами.

Шаг # 1. Извлечь из вектора «P» последний элемент (т.е. последнюю строку «P[H]» таблицы «P»).


Шаг # 2. Вычесть поэлементно из вектора «С» вектор «P[H]».


Шаг # 3. Сформировать вектор из 4-х элементов: коэффициентов, соответствующих векторам «R», «E», «So» и «Si» соответственно.


Шаг # 4. Создать таблицу умножения векторов, полученных на 3-м и 2-м шагах.


Шаг # 5. Прибавить поэлементно вектор «С» к каждой строке (массиву ранга 1) таблицы умножения, полученной на шаге 4.


Шаг # 6. Записать элементы (строки) матрицы в соответствующие локальные переменные.


Шаг # 7. Извлечь два первых элемента (строки) матрицы, полученной на шаге # 5, т.е. векторы «R» и «E».


Шаг # 8. Вычислить значение минимизируемой функции (глагол «f») в каждом из двух векторов, полученных на шаге # 7, и сформировать из полученных значений вектор длины 2.


Шаг # 9. Записать два скаляра, полученные на шаге # 8, в локальные переменные «fR» и «fE» соответственно.


Строка # 27
Вычислить направление сжатия.

Шаг # 1. Сравнить значения «fR» и «fH». Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 2. Подать полученное значение на вход переключателю «`», содержащему вектор глаголов: «]» (т.е. «вернуть правый аргумент») под индексом 0 и «[» (т.е. «вернуть левый аргумент») под индексом 1. Переключатель запустит глагол, находящийся по указанному индексу.


Шаг # 3. Подать левый и правый аргументы («So» и «Si» соответственно) выбранному глаголу («]» или «[«).


Шаг # 4. Записать выбранный вектор («So» или «Si») в локальную переменную «S».


Шаг # 5. Вычислить значение минимизируемой функции (глагол «f») в векторе «S».


Шаг # 6. Записать полученное значение в локальную переменную «fS».


Строка # 29
Проверить на необходимость растяжения.

Шаг # 1. Извлечь из вектора «F» первый элемент. Т.е. результатом будет скаляр «F_L» - минимальное значение вектора «F».


Шаг # 2. Сравнить значения «fR» и «F_L» операцией «меньше». Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 3. Сравнить значения «fE» и «fR» операцией «меньше». Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 4. Выполнить операцию «логическое И» между результатами шагов ## 2 и 3. Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 5. Записать полученное значение в локальную переменную «chkE».


Строка # 30
Проверить на необходимость сжатия.

Шаг # 1. Сравнить значения «fS» и «fH» операцией «меньше». Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 2. Сравнить значения «fR» и «fH_1» операцией «больше». Результатом будет значение 0 («ложь») или 1 («истина»). Поскольку значение «fH_1» не больше «fH» и не меньше остальных значений вектора «F», то результат операции представляет собой ответ на вопрос «больше ли значение fR всех элементов вектора F не считая элемента F[H]?».


Шаг # 3. Выполнить операцию «логическое И» между результатами шагов ## 1 и 2. Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 4. Записать полученное значение в локальную переменную «chkS».


Строка # 31
Выбрать вектор, который заменит «P[H]».

Шаг # 1. Сформировать таблицу из трёх строк - векторов «R» (индекс «0»), «E» (индекс «1»), «S» (индекс «2»).


Шаг # 2. Вычислить индекс, под которым в этой таблице находится строка с нужным вектором-заменителем. Индекс равен сумме значения переменной «chkE» и удвоенного значения переменной «chkS».


Шаг # 3. Извлечь из таблицы, полученной на 1-м шаге, строку под индексом, полученным на 2-м шаге.


Шаг # 4. Записать полученное значение в локальную переменную «newV».


Строка # 33
Модифицировать матрицу «P», выполнив редукцию или замену строки «P[H]».

Шаг # 1. Сравнить значения «fS» и «fH» операцией «больше либо равно». Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 2. Сравнить значения «fR» и «fH_1» операцией «больше». Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 3. Выполнить операцию «логическое И» между результатами шагов ## 1 и 2. Результатом будет значение 0 («ложь») или 1 («истина»).


Шаг # 4. Подать полученное значение на вход переключателю «`», содержащему вектор глаголов: «chgR» под индексом 0 и «chgT» под индексом 1. Переключатель запустит глагол, находящийся по указанному индексу.


Шаг # 5. Подать левый и правый аргументы («newV» и «P» соответственно) выбранному глаголу («chgR» или «chgT»). Поскольку эта строка последняя в теле глагола «chgP», результат её выполнения становится значением, возвращаемым из глагола.


Строка # 34
Конец определения глагола «chgP».

Строка # 36
Определить вспомогательный глагол «chgR», заменяющий последнюю строку «P[H]» матрицы «P». Глагол принимает на вход два параметра (т.е. является диадным): новый вектор-заменитель (левый параметр) и изменяемую матрицу (правый параметр). Глагол составлен из глагода «}» («заменяя») и существительного «_1» (индекс последнего элемента, равен «-1»).

Строка # 37
Определить вспомогательный глагол «chgT», выполняющий редукцию матрицы «P». Редукцию можно представить как полусумму матрицы «P» со своей строкой «P[L]». Глагол принимает на вход два параметра (т.е. является диадным), но использует только правый: изменяемую матрицу.

Шаг # 1. Определить отдельно монадную (слева) и диадную (справа) версии глагола.


Шаг # 2. Определить диадную версию так: взять правый аргумент (глагол «]»), вызвать (глагол «@:») самого себя (глагол «$:») как монаду, подав на вход один правый аргумент.


Шаг # 3. Начало определения монадной версии: взять первый элемент параметра. Поскольку параметром выступает матрица «P», будет взята её первая строка, т.е. вектор «P[L]».


Шаг # 4. Взять правый параметр.


Шаг # 5. Просуммировать (глагол «+») левый аргумент (результат шага # 4, т.е. матрицу «P») построчно (модификатор «"1») с правым аргументом (результат шага # 3, т.е. вектором «P[L]»).


Шаг # 6. Только после этого (глагол «[:») поделить пополам (глагол «-:») элементы матрицы, полученной на предыдущем шаге.


Шаг # 7. Записать сформированный глагол в глобальную переменную «chgT».



Последние два глагола «chgR» и «chgT» сделаны неявными: они не содержат операторов присвоения «=:» или «=.», и работают как конвейеры, обрабатывающие входные данные по цепочке. Эта особенность стирает грань между ними и обычными встроенными глаголами, позволяя использовать их в выражениях вперемешку друг с другом.

Эквивалент операции «P =: newV chgT P»:



Демонстрация работы

Для тестирования алгоритмов оптимизации обычно используют функции, имеющие овражную структуру, например, функцию Химмельблау (Himmelblau's function), унимодальные функции Розенброка (Rosenbrock function), экспоненциальную, Пауэлла (Powell function):

(вспомогательную J-программу для рисования этих графиков см. в конце сообщения)

Найдём минимумы этих функций. Параметры алгоритма: T==1, alpha==1.0, beta==0.5, gamma==3.0, epsilon==0.001. Запускаем интерпретатор, вводим:
код:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
   NB. загружаем программу
   load '/home/user/j601/user/projects/nmm.ijs'

   NB. задаём тестовые функции
   NB. - унимодальная функция Розенброка, минимум в точке (1,1)
   fRos =: 4 : '(100*(y-x^2)^2)+(1-x)^2'
   NB. - функция Химмельблау, один из минимумов в точке (3,2)
   fHim =: 4 : '(((x^2)+y-11)^2)+(x+(y^2)-7)^2'
   NB. - унимодальная экспоненциальная функция, минимум в точке (1,10)
   fExp =: 4 : '+/ ((+/"1) 1 _5 _1 5 (*"1) ^ (_0.1 * i. 10) */ x , y , 1 10)^2'
   NB.  - унимодальная функция Пауэлла, минимум в точке (0,0,0,0)
   fPow =: (13 : '+/ 1 5 1 10 * 2 2 4 4 ^~ (+/ " 1) (4 4 $ 1 10 0 0 0 0 1 _1 0 1 _2 0 1 0 0 _1) (*"1) y') " 1

   NB. тестируем функцию Розенброка
   f =: fRos/"1
   Solve 2 ; 1 ; 1.0 ; 0.5 ; 3.0 ; 0.001   NB. ищем решение
0.861894 0.740571                          NB. решение найдено за 109 шагов

   NB. тестируем функцию Химмельблау
   f =: fHim/"1
   Solve 2 ; 1 ; 1.0 ; 0.5 ; 3.0 ; 0.001   NB. ищем решение
2.99957 1.99946                            NB. решение найдено за 22 шага

   NB. тестируем экспоненциальную функцию
   f =: fExp/"1
   Solve 2 ; 1 ; 1.0 ; 0.5 ; 3.0 ; 0.001   NB. ищем решение
0.996042 10.073                            NB. решение найдено за 29 шагов

   NB. тестируем функцию Пауэлла
   f =: fPow
   Solve 4 ; 1 ; 1.0 ; 0.5 ; 3.0 ; 0.001   NB. ищем решение
0.0483551 _0.00406391 0.0171749 0.015398   NB. решение найдено за 30 шагов


Визуализация функций

Создадим и запустим в интерпретаторе файл 'funcs-plot.ijs' с таким содержимым:
код:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
require 'plot'
pd 'textfont arial 17 bold'
pd 'textc 500 _10x Двумерные варианты функций для тестирования алгоритмов оптимизации'
pd 'sub 0 0 1000 _40x'
pd 'sub 1 3'
pd 'type contour'
pd 'title функция Розенброка'
pd 'aspect 1'
pd 'contourlevels 10'
pd (i:1.5j50) ([ ; ] ; fRos"0/) (0.5 + i:1j50)
pd 'new'
pd 'type contour'
pd 'title функция Химмельблау'
pd 'aspect 1'
pd 'contourlevels 10'
pd (i:5j50) ([ ; ] ; fHim"0/) (i:5j50)
pd 'new'
pd 'type contour'
pd 'title экспоненциальная функция'
pd 'aspect 1'
pd 'contourlevels 10'
pd (1 + i:1j50) ([ ; ] ; fExp"0/) (10 + i:5j50)
pd 'show'

Тестовые функции имеют общую особенность: они быстро меняются вблизи минимума. Поэтому для лучшего отображения окрестности минимума лучше использовать логарифмическое распределение контуров. Плохая новость: стандартный plot умеет распределять контуры только равномерно. Но есть и хорошая новость: бОльшая часть J реализована на нём самом, и поэтому доступны исходные тексты класса plot. Нам надо слегка поменять файл '/home/user/j601/system/classes/plot/jzplot.ijs': заменить строчку
код:
1:
dat=. (CONTOURLEVELS + 1) * (dat - min) % max - min
на строчку:
код:
1:
dat=. (CONTOURLEVELS + 1) * (_1 + ^. 10) %~ _1 + ^. 2.5e_2 + 10 * (dat - min) % max - min
И все дела.
jip01-01-1970 10:00022-06-2010 17:07
Недавно опубликовал на языке J предварительную версию аддона mt, предназначенного для решения некоторых задач матричной алгебры: преобразования, разложения, сведения к сжатой форме, факторизации, решения уравнений, вычисления матричных функций, оценки числа обусловленности. Разработка длилась 2,5 года.

Аддон реализован на основе алгоритмов известной фортрановской библиотеки LAPACK. Mt является аналогом аддона jlapack, но, в отличие от последнего, не использует оригинальную LAPACK-овскую библиотеку, а реализован на "чистом" Джее. Разумеется, реализована только часть алгоритмов - реализация лапаковской библиотеки целиком вряд ли под силу одному человеку. На текущий момент (версия 0.6.6) на J реализовано 273 существительных, глагола, наречия и союза (или 522 с учётом подпрограмм). Это соответствует 168 процедурам и функциям на Фортране (или 245 с учётом подпрограмм).

И вот сейчас стало возможным приблизительно оценить, насколько код на J компактнее кода на Fortran. Итак:

количество строк на Fortran (с учётом BLAS, без учёта процедур само-тестирования из каталога TESTING, только типы данных D и Z):
- код: 22042
- комментарии: 30025
- всего: 52067

количество строк на J (c учётом процедур само-тестирования):
- код: 1754 (8% от фортрановского)
- комментарии: 10052 (34%)
- всего: 11806 (23%)