kaipa | Entries tagged with j

Немного потрахавшись, поставил на Мак Haskell, чтобы понять, с чем его едят. Удивлен скоростью. Эталоном скорости в интерактивном режиме для меня всегда был J. Но тут Хаскель обскакал.

Факториал.

Хаскель (ghci):
let { f 1 = 1 ; f n = n * f(n-1) }

J:
f =: */@(>:@i.), хотя значительнее нагляднее просто */1+i.10000x, подставляя нужное число.

На тысяче разницы не видно.
На десяти тысяч J чуть запинается, а Хаскель -- нет.
На ста тысячах J пыхтел минут 5, а Хаскель вернул секунд за 30.

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

Последние пару недель игрался на Скале с задачами с http://projecteuler.net/, и заодно подсадил на это дело жену. Мне программы писать неинтересно, интересно сделать в пару функциональных строчек в интерпретаторе, благо у Скалы есть консоль, и она хорошо оптимизирует tail-рекурсию. Когда одна из задач в пару скала-строчек не укладывалось, плюнул, и сделал на J в одну. Для J большинство задач просто семечки.

Эйлер 10 (сумма простых чисел, не превышающих 2,000,000):


+/ (#~ <&2000000) p: i.1000000x

Несмотря на то, что уже полгода с J не игрался, принципы все помню, и основное время ушло на поиск глагола для фильтра. Генератор простых чисел в J встроенный, так что по-началу я сгоряча просуммировал все 2,000,000 простых чисел, что тоже заняло всего несколько секунд.

P.S. Скоро мне привезут оригинальные книжки по J, купил остатки на Амазоне, больше там нет.

Одна из самых изящных конструкций в языке J, на мой взгляд, это форк. Работает он так. Пусть x и z -- монадные глаголы (в J функции называются глаголами, которые могут быть монадными, то есть от одного аргумента, и диадными -- от двух), а y -- диадный глагол. Тогда форк (x y z) вычисляется как:

(x y z) a = (x a) y (z a)

Такая конструкция позволяет сэкономить много ненужных повторов и промежуточных переменных. Классический пример -- вычисление среднего:

   (+/ % #) 1 2 3 4
2.5

Здесь три глагола: +/ -- складывает элементы вектора (строго говоря, это глагол '+' и наречие '/' -- "вставка"), % -- деление, и # -- число элементов.

Просто и понятно.

Другая похожая конструкция -- hook или "крючок" -- менее наглядна. Она раскрывается как:

(x y) a = a x y a

Например, вычислим нормированный вектор, используя те же самые глаголы:

   (% +/) 1 2 3 4 5
0.0666667 0.133333 0.2 0.266667 0.333333

Программа на J, на Маке, через ODBC-JDBC bridge забирающая данные с Vertica.

Пока не получилось. Но в процессе выяснил:
- JDBC на J нет, несмотря на схожесть букв :)
- ODBC на Маке через одно место
- ОDBC драйвера Вертики для Мака нет, но они его сделают в следующем релизе
- ODBC-JDBC bridge для Мака есть, но что-то бесплатного я не нашел. Искал не сильно пока.
- Вышел J 7.01, но пока сырой: 64-битная версия у меня не встала, а 32 встала, но не все работает. Хотя как отшлифуют, это будет большой шаг вперед.

Зачем извращаюсь? Хочу понять, удобнее ли J для простенькой прикладной задачи, чем вольфрамовская Matematica. Подготовка не считается.

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

Начал я с самого простого, с выражения, вычисляющего факториал числа. Оно удивительно компактно:

   */1+i.5
120

Несмотря на компактность, выражение состоит из трех функций. "i.5" генерирует вектор от 0 до 4. "1+" прибавляет к каждому элементу вектора единицу, чтобы получить 1..5. А "*/" перемножает элементы вектора. Само выражение -- 6 символов. Для читаемости можно было бы разбавить пробелами, но это необязательно. Наиболее компактное выражение на Скале, которое приходит на ум:

  (1/:(1 to 5))(_*_)

Возможно, на Хаскеле можно написать короче, но я с Хаскелем пока не знаком.

Если же захотеть завернуть выражение J в функцию, то все несколько сложнее и длиннее. Я долго мучался, пока не разобрался, как написать функцию факториала. Все дело в том, что разбор выражения в J право-ассициативный, поэтому a b x вычисляется как a(b(x)). Но если определять функцию f = (a b), то смысл меняется, хотя я до конца не понял, как. Вот короткий пример, прибавление к трем два, а потом умножение на два:

   2&* 2&+ 3
10
   (2&* 2&+) 3
40

Как выражение в скобках получает из трех сорок, я пока не понимаю. Но для того, чтобы получить ожидаемый результат (10), надо явно указывать суперпозицию функций (оператор @):

   (2&*@(2&+)) 3
10

Поэтому в случае с факториалом, функция определяется так:

  f =: */@(1&+@i.)
  f 5
120

Другой вариант -- использовать оператор инкремента ">:". Это не дает выигрыша в случае выражения, но немного короче для функции:

   f =: */@(>:@i.)
   f 5
120

Интересная фича J -- "компиляция" или преобразование функций, которое разворачивает все примитивы в их простейшие выражения. Пример в предыдущем посте с числом "пи" треугольником, "f." -- оператор "компиляции":

  PiTree =: PiTree f.
  PiTree
([: - [: i. -@]) |."0 1 ([: #~ 1: + 2: * i.) ,/. [: ([: ": [: <.@o. 10x"_ ^ ]) [: <: [: *: ]

После "компиляции" программы становятся максимально короткими, но плохо читаемыми. Симплекс-метод для задачи линейной оптимизации программируется несколькими понятными функциями. Но можно и свернуть в одну.

  [-(({~"1<:@{:)-(i.@#@[=<:@{.@]))*/(({~<:@{.)%({~<@<:))

Объяснение и хорошее введение в язык -- здесь

Несколько интересных языков программирования, на которые меня "натолкнул" APL.

A+ -- "живая" реализация APL, о котором я писал вчера. Поддерживает в том числе и ASCII нотацию. Хотя при этом теряется вся красота греческих букв. Очень мощный инструмент для работы с векторами и матрицами, плюс есть встроенные средства визуализации. Вероятно, все же не такой мощный, как MatLab, поскольку A+ в настоящее время явно потерял позиции.

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

Вот пример программы, которая "рисует" пирамидку числа-пи:


pi=: [: ": [: <.@o. 10x"_^]
PiList=: [: pi [: <: [: *: ]
PiTriangle=: ([: #~ odd) ,/. PiList
odd=: 1: + 2: * i.
PiTree=: ([: - [: i. -@]) |."0 1 PiTriangle

PiTree 10

         3         
        141        
       59265       
      3589793      
     238462643     
    38327950288    
   4197169399375   
  105820974944592  
 30781640628620899 
8628034825342117067

Число уровней, понятно, может быть любым.

Joy -- "стековый" язык, наследник идей языка Forth. Особенностью языков такого типа является полное отсутствие переменных и формальных параметров функций. Все происходит на стеке. Жив Joy или нет, неясно, скорее -- нет. Но есть еще несколько стековых языков, таких как Factor или Cat, которые выглядят более живыми. Впрочем, зачем далеко ходить, сам Forth никто в утиль не списывает, он остается живым языком, несмотря на почтенный возраст. Не знаю насчет современных языков, но Форт еще отличался тем, что на нем практически очень трудно было допускать ошибки. Программа на Форте состоит из определения некоторых термов через известные термы. Причем в интерактивном режиме. Поэтому любой терм при определении, во-первых, сразу же проверяется интерпретатором, а во-вторых, проще простого его вызвать и проверить. В Форте можно программировать снизу вверх и сверху вниз, как угодно. Абсолютная гибкость.

Closure -- это достаточно распространенный диалект Лиспа, особенностью которого является интероперабельность с Java: он компилируется в JVM байт-код. Похожим свойством обладает другой функциональный язык -- Scala -- основной мой "инструмент" в настоящее время. Я всегда очень живо реагирую на Лисп, это замечательный язык, позволяющий программировать красиво минимумом средств.

И напоследок -- пример простенькой программки, реализованный на более чем 1300 языках: http://www.99-bottles-of-beer.net

Profile

kaipa

April 2017

S	M	T	W	T	F	S
						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

Syndicate

Style Credit

Style: Mediterranean Peach for Modular by branchandroot
Resources: Nantes

Expand Cut Tags

No cut tags

Page generated Mar. 24th, 2026 08:49 am

Записки на полях

Познание бесконечности требует бесконечного времени

Entries tagged with j

Haskell vs J

ProjectEuler

J-форк

Jизвращение

Еще про J

A+, J, Joy, Closure и другие