Sergey Dmitriev ([info]sergeydmitriev) wrote,
@ 2004-07-08 11:48:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Entry tags:language_oriented_programming

Новый подход к программированию - интервью
Когда я был на JavaOne на прошлой неделе то дал интервью Джеку Хэррингтону - он автор книжки "Code Generation in Action", а также он поддерживает web-site посвященный генерации кода - http://www.codegeneration.net
В этом интервью я немного рассказал о нашем новом продукте Fabrique, но в основном я рассказывал о новом подходе к программированию. Он кстати уже имеет название - Language Oriented Programming.



(Post a new comment)


[info]dr_klm
2004-07-08 05:28 pm UTC (link)
Поздравляю. Я смотрю, идея уже сильно трансформировалась... ;-)))

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

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

Но, как говорится, хозяин-барин... ;-))) Хотя, мне кажется, можно было-бы и эффективнее распорядиться ресурсами... ну ладно...

А вот пивка нам с Вами как нибудь можно было-бы и выпить... Оно, глядишь, может и кое что из моего кода (которого, как заявили в предыдущей записи, я написал мало) Вам могло-бы пригодиться... я даже подозреваю что... ;-)

К.Л.М.

(Reply to this)(Thread)


[info]sergeydmitriev
2004-07-08 07:33 pm UTC (link)
Спасибо за поздравления :-) Трансформировалась скорее не идея а просто понимание как ее описывать. Единственно что изменилось по сравнению с первым постингом это больший упор на генерацию кода (трансформацию моделей), чем на написание интерпретатора моделей. Основная же идея, что необходима среда в которой легко определять любые языки - осталась.
Если честно, я не гонюсь за признанием того что это именно я придумал что-то новое, я вполне сознаю что составляющие описанного подхода уже были давно придуманы. Дело просто в том что я хочу иметь в своих руках такой мощный инструмент - а нет его :-( Вот и приходится делать все самому.
Насчет пивка - мысль хорошая. Вечная проблема в Праге - с кем бы пойти пообедать, я обычно поздно хожу, часиков в 5 - к тому времени обычно все в оффисе пообедали уже. Так что можно созвониться или сосписаться.

(Reply to this)(Parent)(Thread)


[info]dr_klm
2004-07-09 04:23 pm UTC (link)
Поздравления совершенно искренние !

IDE для компиляторов-компиляторов... IDE для редакторов... реализованная сама в себе... Дык это-же Emacs ! ;-)) Любая программа развивается до тех пор, пока у нее не появляется функция чтения электронной почты (© Stallman, по-моему)... ;-))) Шучу, шучу...

Ну... в 17:00 это уже почти ужин... ;-) Но я тоже сова, понимаю... завтракаю в 12:30... YHM на адресе @intellij. Познакомимся, поговорим, разберемся...

Лично меня в последнее время вот эта штука (язык J) очень сильно зацепила.

К.Л.М.

(Reply to this)(Parent)(Thread)


[info]sergeydmitriev
2004-07-11 08:12 pm UTC (link)
Я почитал ваш постинг про язык J, и, похоже у нас с Вами существенное отличие в понимании того, что такое красивая программа или язык, а что нет. При условии конечно что весь постинг не был шуткой. Впрочем, он оказался хорошим поводом продемонстрировать силу language-oriented подхода.
Итак, в моем понимании Ваш пример написанный на языке J выглядит абсолютно ужасно.
Для меня критерий красоты программы это тогда когда она написана абсолютно ясно и максимально близко к тому как задача и ее решение формулировались бы у меня в голове или как бы я ее рассказал на естественном языке другому человеку. У Вас же восторг вызывает стремление написать программу как можно короче.

Давайте рассмотрим Ваш пример подробнее. Стоит задача - найти выпуклую оболочку для заданного множества точек на плоскости. По Вашим же словам:
Алгоритм этот заключается в том, чтобы
1. Отсортировать точки по углам, относительно самой левой из них (которая по определению принадлежит оболочке).
2. А потом, пройдя по образовавшемуся звездообразному контуру последовательно, начиная с левой точки,
2.1 удалить все, угол при которых (относительно внутренности многоугольника) выгнут наружу (>180ˆ).
Result: Те точки, что останутся, будут образовывать вогнутые углы, а значит оболочка получится выпуклой.

Я скопировал здесь Вашу программу, которая реализует этот алгоритм на J:

s =: ({. , }. /: 12"_ o. }. - {.) @ /:~
l =: 11"_ o. [: (* +)/ }. - {.
rr =: (1"_ , (0"_ > 3: l\ ]) , 1"_) # ]
hull =: [: rr^:_ s

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

  Array<Point> ConvexHull(Collection<Point> points) {
     leftPoint = find in points by minimum of p.x
     sortedArray = leftPoint + create Array<Point> from points 
                                                   where element != leftPoint
                                                   sorted by angleToXAxis(element-leftPoint)
     return create Array<Point> from sortedArray
                                where { isFirst || orientation( prevCircled, element, nextCircled) >= 0 }
  }

  long orientation(int a, int b, int c) {
    return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x); 
  }
Некоторые пояснения: Переменные element, isFirst, prevCircled, nextCircled определяются языком работы с коллекциями в соответствующих контекстах.
еlement означает текущий элемент, prevCircled - предыдущий (и последний, если текущий - первый) и т.д.
isFirst - означает, что текущий элемент - первый.
Я считаю что если программа будет записана в таком стиле, то она будет в разы читабельнее соответствующей программы написанной, например, на Java, а уж тем более написанной на языке J.

(Reply to this)(Parent)(Thread)


[info]dr_klm
2004-07-11 10:07 pm UTC (link)
зашел я значит в бар пива попить, проверил почту и был огорошен Вашим комментарием.

О вкусах, конечно, не спорят... и тем более меня не удивляет, что человека, постоянно пишущего на Java или C++, программа на J пугает... ;-)) Так что пропущу, пожалуй, возможность поучавстваовать в дискурсе о красоте...

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

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

J -- универсальный язык и программу вычисления выпуклой оболочки я выбрал для иллюстрации... На J написана масса алгоритмов (просто поищите в интернете, почитайте книжки и статьи на jsoftware.com), для каждого из которых, боюсь, в рамках вашей парадигмы пришлось-бы придумывать собственный язык.

Кроме того, краткие обозначения токенов там совсем не главное, как я неоднократно в тексте и в дискуссии пытался подчекнуть и аргументировать. Можно обозначить ':/' как 'grade_up', а ':/~' как 'sort_up' и программа от этого не станет намного длиннее.

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

К.Л.М.

beer disclaimer: пишу с КПК из бара после второго пива... опечатки прошу простить.

(Reply to this)(Parent)

Ух ты... :) Какая штуковина
[info]aefimov
2004-07-20 06:21 pm UTC (link)
Ктож это придумал, даже всякие извращения на Perl RE не так страшно выглядят...
Бррр.... Я лучше сразу в машшинных кодах напишу :)
Это че такое? :) Язык? :))

Всё я опять люблю Java, несмотря на автобоксинг в 5ой бете :)))

(Reply to this)(Parent)

(продолжение)
[info]sergeydmitriev
2004-07-11 08:24 pm UTC (link)
Я готов поспорить и по поводу краткости языка J.

Краткость выражается по моему мнению не в количестве байтов занимаемых программой, а скорее количеством токенов в программе. То, что некоторые токены занимают несколько символов обычно делается для улучшения восприятия программы человеком. В Вашем же примере на языке J каждый токен занимает один-два символа - только отсюда и идет хваленая краткость.
Если я перепишу код программы в моем варианте используя те же принципы, то полученный результат будет даже короче, чем код на языке J:

l=@f p @b e.x
s=l+@c A<P> @f p @w e!=l @s aX(e-l)
hull=@c A<P> @f s @w f1||(pc.x-e.x)*(nc.y-e.y)>=(nc.x-e.x)*(pc.y-e.y)
Здесь я, правда, сделал inplace подстановку метода orientation() чтобы сравнение было более честным, поскольку Ваш код на J также не определяет такого метода, а также оставил только тело метода - как и у Вас. Здесь я перед каждым ключевым словом поставил символ @ чтобы их можно было отличить от других имен. Если же делать отрисовку графа в MPS, то программа может выглядеть еще короче, потому что символы могут там отличаться также цветом, типом фонта и т.д.

Итак, в результате мы имеем, что такая программа занимает 121 байта против 132 байт на языке J.
Кстати в MPS можно будет поменять первый вид пограммы на второй просто сменив rendering у редактора графа.

(Reply to this)(Parent)(Thread)

;-))
[info]dr_klm
2004-07-11 10:28 pm UTC (link)
Ну, метод "orientation" у меня есть, причем, занимает от отдельную строчку и называется "l". Он производит именно то самое вычисление... и нравится мне меньше всех остальных, потому что не намного короче эквивалента на фортране... но, если подумать, тут ничего удивительного, потому что Фортран как раз и создавался для таких вот линейных формул...

Ну, и как мне Вашу "программу" проверить ? Вдруг Вы ошиблись... и она ("О БОЖЕ !") не работает... ;-) Причем, я точно знаю, что она не работает... и я уже даже намекал почему... ;-))

И еще, замечу, что имен (переменных тоесть, кроме s, l, r, hull) в моей программе нет вообще. Это называется (барабанная дробь, новый термин) -- "функциональное программорование".

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

Кстати, если-бы я записал программу не в функциональной форме (tacit form, как это называется в J) -- она, скорее всего, была-бы еще короче...

К.Л.М.

beer disclaimer: 3 пива.

(Reply to this)(Parent)(Thread)

Re: ;-))
[info]syarzhuk
2005-07-28 07:06 pm UTC (link)
А есть ещё язык HQ9+, хороший

(Reply to this)(Parent)(Thread)

Re: ;-))
[info]dr_klm
2005-07-29 10:20 pm UTC (link)
Хороший то он хороший, но непонятный. ;-) А J понятный. ;-))

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

Вот, например, программа для вычисления средних значений на J в четыре символа:
avg =: +/ % #
Разве не очевидно ? ;-)

К.Л.М.

(Reply to this)(Parent)(Thread)

Re: ;-))
[info]syarzhuk
2005-07-30 02:19 pm UTC (link)
Совершенно неочевидно. Три странных оператор "взять и поделить" "под проценты" "за решётку". И где здесь среднее?

(Reply to this)(Parent)(Thread)

Re: ;-))
[info]dr_klm
2005-07-30 10:58 pm UTC (link)
Ну, все-же знание словаря необходимо для понимания (не в большей степени, чем навязанное Фортраном знание, что "*" -- умножить, "/" -- поделить; это ведь знание Вас не отягощает, являясь в не меньшей степени произвольным ?). На J: поделить -- "%", количество элементов (в массиве) -- "#", сложение -- "+", вставить между (элементами массива) -- "/" (это прилагательное).

Соответственно, глагол avg (при монадном применении) читается как "вставить + между элементами массива (т.е. сложить их) и поделить то что получится на количество элементов в том-же массиве. Дольше рассказать, чем написать "+/ % #"...

К.Л.М.

(Reply to this)(Parent)(Thread)

Re: ;-))
[info]syarzhuk
2005-07-31 12:04 am UTC (link)
Ну, в-нулевых, Фортран мог навязать разве что .LT. Знаки арифметических операций пришли из арифметической же традиции, существовавшей до компьютеров.
Во-первых, "знание словаря необходимо для понимания" далеко не всегда. Мне вот не далее как на прошлой неделе понадобилось написать программу на любимом хозяином этого дневника языке Java. Так вот, несмотря на то, что я этот язык никогда не изучал, программу я написал, параллельно найдя ошибку в Eclipse IDE :) Потому как язык интуитивно понятен практически без словаря. Ваш же язык с односимвольными неинтуитивными операторами (это почему же % - поделить?), вполне возможно, позволяет достичь высокой производительности на определённом классе задач после долгого его изучения. Но мне не так важна моя производительность в данную минуту, как то, чтобы код, написанный мной, я и любой другой мог через несколько лет прочитать, понять и изменить. А с "+/ % #" это никак не пройдёт.

(Reply to this)(Parent)(Thread)

Re: ;-))
[info]dr_klm
2005-07-31 01:35 pm UTC (link)
Ээээ... оно, конечно, создатели Фортрана говорили о тысячелетних корнях своего языка, но фишка в том, что даже сотню лет назад не было ASCII. Произведение в алгебре никакой звездочкой не обозначается, если чем и обозначается, так максимум точкой (или крестиком). Косая в алгебре для обозначения деления используется гораздо реже, чем горизонтальная линия в дроби... То, на что Вы ссылаетесь, по крайней мере, не меньший произвол, чем то, на что ссылаюсь я. И если производные Фортрана Вы изучили раньше, то от этого они не становятся более "очевидными" (в обьективном смысле этого слова). Причем, я хочу подчеркнуть, что речь идет о вашем личном порядке изучения, поскольку APL, из которого происходит J примерно как Java из Фортрана, является ровесником последнего (ну плюс-минус несколько лет).

Понятен, потому что хоть бейсик, хоть С, хоть Паскаль (хоть что-то другое, массово преподаваемое в школах) -- все это от Фортрана лукавого. ;-))

Почему Фортран-подобные императивные языки распространились шире чем производные APL ? Дело в том, что в APL вы говорите -- "что" нужно посчитать, а "как" это сделать -- дело интерпретатора (в этом смысле APL и J гораздо ближе к математической записи чем Фортран). В Фортране, и его производных C, C++, Java у Вас есть возможность детально и жестко расписать процессору последовательность действий. Потому, когда процессоры были медленные императивные языки оказались более востребованными. Ведь "умственные" способности интерпретатора всегда хуже, чем у человека, по крайней мере, на то время точно. А сейчас J, наоборот, набирает популярность...

К.Л.М.

(Reply to this)(Parent)

Re: ;-))
[info]dr_klm
2005-07-31 01:39 pm UTC (link)
Вот, кстати, женщина, которая изобрела Фортран (вернее, несколько языков, прямых предшественников Фортрана, где, собственно, и вводились "звездочки" и "палки"), перед этим, она реализовала первый компилятор вообще.

К.Л.М.

(Reply to this)(Parent)


[info]ait
2004-07-09 08:20 am UTC (link)
Хорошее интервью, Сергей. Спасибо.

(Reply to this)

И это только начало
(Anonymous)
2004-07-10 02:02 pm UTC (link)
Сергей, я не нашел в твоём интервью достаточно важной детали. Я сейчас попытаюсь её изобразить. Начну с аналогии.

Допустим, у нас есть задача поднять или перенести нечто тяжелое. Как мы это можем сделать?

a) приделать к нему удобные ручки (что за чемодан без ручки? :) ), поместить в удобный контейнер (рюкзак), изменить форму (штангу поднять легче, чем булыжник, потому что можно использовать специальную технику штангистов);
б) можно разделить задачу на более мелкие - разобрать предмет (или разбить), и поднять/перенести по частям;
в) использовать рычаг, лебёдку, грузовик, и пр.

Заметьте, все эти три способа можно комбинировать, или использовать отдельно. То есть суммарно - приспособить задачу к человеку (а,б), или использовать усилитель человека (в).

Что этому соответствует в программировании? Чисто схематически, и крайне упрощенно:

а) Ну это языки программирования как таковые - удобный синтаксис. Частично - удобства платформы (GC, проверки границ массива и прочее).
б) ООП. Точнее - начиная с разбиения программы на методы, потом на модули, потом на классы. Параллельно идёт унификация семантики (тоже способ не хуже ООП) - скажем есть операция сложения, или умножения - а над чем она - не суть важно (числа, матрицы и вектора, цвета и пр).
в) усилители интеллекта... тут начиная с системы типов (которая позволяет верифицировать и оптимизировать программу компилятором), и кончая IDE типа idea & eclipse.

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

А)
Ну, такие простые вещи, как автоматическое форматирование (при представлении программы в текстовом виде) или возможность использовать разными программистами разный синтаксис (С-подобный, Паскаль-подобный и пр.) для _отображения_и_редактирования_ одной и той-же программы - это цветочки. Кстати, интересно заметить, что понятие keyword или фиксированный набор операторов - отпадут напрочь.

По поводу domain specific языков. Они, вообще говоря - не панацея. То есть конкретный разработчик лично для себя может что-то такое изобразить, но уже в комманде это сделать будет труднее, а с учётом текучести кадров и необходимости каждого нового обучать этим языкам - вообще мрак. Сама по себе идея хорошая, но, как говорится, надо знать меру. IMHO, самый удобный случай - это когда dsl можно прозрачно использовать в любом месте программы, и более низкоуровневый код - в любом месте dsl-я. Ну вот как есть всякие препроцессоры к С, которые в нём прямо позволяют писать SQL-ные запросы.

Кроме того, кодогенерация - это ненужное. Лишнее и больное. В смысле - кодогенерация _текста_ ненужна, поскольку текста у нас уже не будет. Будет у нас дерево. Вот для него кодогенерация и будет нужна. Простейший вариант, это скажем statement forall для явы. Навороченным вариантом можно назвать, скажем, yacc-овский синтаксис. Обратите внимание - это не кодогенерация которая меняет исходный код программы (это дерево узлов которое является программой). Это кодогенерация в другое дерево. То есть сам пользователь работает именно в терминах forall оператора и этот forall оператор уже генерирует какой-то промежуточный код (который можно либо экспортить в исходники и подавать их на вход javac, либо прямо так в байткод и компилировать). То есть саму программу меняет только программист, а "кодогенерация" - это один из этапов компиляции программы (в байткод или нэйтивный код - не суть важно). Ну, ещё код самой программы может менять "рефакторинг", скажем, можно сделать рефакторинг оператора forall в эквивалентный набор явовских операторов.

(Reply to this)(Thread)

Re: И это только начало
[info]_qwerty
2004-07-13 09:00 pm UTC (link)
Когда Вы говорите ООП, Вы, видимо, хотите сказать "модульное программирование"? Модульность - это возможность разделения программы на концептуальные фрагменты, их классификации и сочленеиия в программу. Модульность во всех существующих языках программирования довольно посредственная. И ООП ничего существенного к ней не добавило.

Кодоненерация, напротив, весьма полезна для:
1. отладки
2. раскрутки
3. во избежание впадания в крайности

(Reply to this)(Parent)

продолжение
(Anonymous)
2004-07-10 02:03 pm UTC (link)
Кстати, после долгих экспериментов мне теперь кажется, что наилучшим способом "храниния" и работы с этим деревом является старый добрый lisp. Ведь lisp по существу имеет самый простой синтаксис - имя функции и аргументы этой функции. Это некий универсальный синтаксис и подход к самому дереву - функция и её аргументы. Этот синтаксис не удобен для редактирования, но в качестве низкоуровневого варианта для отображения дерева и его манипуляцией - мне кажется идеален.

Б)
Я не буду подробно останавливаться на "разделении" программы на более мелкие кусочки. Это вполне полно сделано уже в ООП, хотя и здесь можно много ещё сделать. Для примера приведу такую мысль, что раз мы программу отделили от синтаксиса, и можем синтаксис задавать свободно - точно так-же можно задавать свободно и правила видимости элементов нового языка. Например, можно ввести такое правило видимости для поля класса, что в самом классе оно видно, его можно читать и изменять, а вне класса его можно только читать, но не менять. Как в юниксе права доступа - хозяин может rwx, группа может rw, остальные могут r. Можно идти гораздо дальше, но это тема отдельного большого разговора. Но основная идея - это то, что как можно подключать различные синтаксисы к программе (представленной в виде дерева, а не текста) - так-же можно подключать и различной степени сложности "менеджеры областей видимости и прав доступа". Что-то вроде плагинов.

В)
Долго к этому шли, и это и есть то место, которое у Сергея "пропущено" в интервью.
Итак, что есть усилитель мозгов программиста, например, как это делают нынешние IDE?
А вот как - они тихо, себе на уме, в фоне парсят и компилируют программу, и немедленно показывают текущие ошибки компиляции. Немедленно, а не после того, как программист запустит компиляцию. И это уже много!

Основное время у IDE уходит на то, чтоб в фоне скомпилировать программу. Программа постоянно меняется (редактируется) и IDE постоянно занято перекомпиляцией программы. На это уходят все её силы, и в общем-то современных CPU на это не всегда хватает. Попробуйте открыть скобку и не закрыть её - у eclipse или idea просто крыша поедет - куда-то пропала куча методов, срочно перекомпилируется вся программа и вываливается куча ошибок. И всё потому, что они парсят исходный текст.

Теперь у нас программа хранится в виде дерева, и программист программирует меняя непосредственно это дерево. IDE уже нет нужны парсить текст и тем более нет нужны выявлять изменения в программе по сравнению с предыдущим текстом. Всё уже есть и всё представленно в удобном для анализа виде. Вы редактируете этот узел дерева - и только этот узел дерева поменялся, его не нужно "искать" сравнивая результат предыдущего парсинга+резолвинга и последнего.

(Reply to this)(Thread)

Re: продолжение
[info]_qwerty
2004-07-13 09:08 pm UTC (link)
Вы ошибаетесь, к сожалению, в языках программирования довольно много нелокальных зависимостей. Если делать синтаксический разбор текста умеючи, то он занимает не так много времени. От промежуточного текстового представления всегда можно избавиться, когда и если придет тому время.

(Reply to this)(Parent)

продолжение
(Anonymous)
2004-07-10 02:04 pm UTC (link)
Итак, IDE как-бы становится нечего делать. Ан нет, есть что! Уже существуют разного рода верификаторы и аудиторы программ. Они проверяют её на нетривиальные ошибки - анализируя в целом. Конечно, запустить её, она весь проект компилирует, а потом анализирует, да ещё и делает достаточно сложный анализ - это от 5 минут на небольшом проекте до нескольких часов на приличного размера проекте. Что же мы имеем храня программу в виде дерева? Мы имеем возможность проводить именно этот, сложный, нетривиальный анализ всей программы в целом - и проводить его в реал-тайме. Немедленно. То есть, предположим, анализ уже проведён. Мы знаем о программе всё, в том числе и что от чего зависит. Теперь мы поменяли какой-то узел. Скажем, раньше был метод foo() { return ""; }, а стал foo() { return null; }. Мы поменяли узел "return" и сразу видим - возвращается null, а раньше был не-null. Мы знаем все места, где этот метод используется - и можем быстро (в фоне) проверить эти узлы - не выскочит ли там NullPointerException? Это достаточно примитивный пример, только для демонстрации потенциальных возможностей.

Реально обретут силу, скажем такие технологии, как call by contract - потому как большинство условий контракта (constraints на входящие и выходящие значения) можно будет проверить на стадии компиляции. Можно будет создавать средства для более полного описания программы с последующей их верификацией. То есть вместо комментария "здесь у нас в начале исполнения программы это поле может быть нулём, а после того как мы перейдём к такой-то стадии исполнения - это поле нулём быть уже не должно" - можно будет создавать средства, которые это смогут формально описать и затем в фоне и реалтайме плагин аудита проверит - выполняется ли это условие.

Мне кажется, именно это "усиление" программистских мозгов - именно оно и даст в перспективе наибольший эффект. Безусловно, подобного рода средства анализа создавать будет не просто, и не быстро. Ближайшее улучшение программисткой жизни мы получим от синтаксической свободы. Но в более отдалённом будущем - именно это даст бОльшие возможности для создания более сложных программ, для удешевления их разработки и сопровождения.

(Reply to this)(Thread)

Re: продолжение
[info]_qwerty
2004-07-13 09:14 pm UTC (link)
Инкрементные анализы и компиляция - это, конечно, очень важное преимущество для больших проектов, но, опять-таки, совсем не все анализы (в том числе и потоков данных, который вы используете выше для проверки на null) легко переформулировать в инкрементной форме.

(Reply to this)(Parent)

пример
(Anonymous)
2004-07-11 11:22 pm UTC (link)
Реальный пример использования технологии типа предлагаемой Сергеем.
Фрагмент компилятора. Вообще-то это просто ява, и в ней немножко добавлено.
Синтаксис похож на прологовский, так что основную идею поймать можно.
Барабанная дробь функциональщины здесь не прокатывает, поскольку в оной
функциональщине бэктрэкинг отсутствует. А вот расширение синтаксиса -
позволяет добавить как функциональщину, так и логику и вообще много чего.
Пример реальный, хотя сейчас я бы его мог переписать ещё раза в два компактнее -
попереопределять операторы и пр. Но и так, IMHO, тоже достаточно наглядно.
	rule public resolveMethodR(ASTNode@ node, ResInfo info, KString name, Expr[] args, Type ret, Type tp, int resfl)
		Type@ sup;
		Struct@ defaults;
		Field@ forw;
	{
		checkResolved(),
		trace(Kiev.debugResolve, "Resolving "+name+" in "+this+" for type "+tp+(info.path.length()==0?"":" in forward path "+info.path)),
		{
			node @= methods,
			((Method)node).equalsByCast(name,args,ret,tp,resfl),
			{
				(resfl & ResolveFlags.Static) == 0
			;	(resfl & ResolveFlags.Static) != 0, node.isStatic()
			}
		;	(resfl & ResolveFlags.NoImports) == 0 || isPackage(),
			node @= imported, node instanceof Method,
			((Method)node).equalsByCast(name,args,ret,tp,resfl)
		;	(resfl & ResolveFlags.NoSuper) == 0,
			sup ?= super_clazz,
			sup.clazz.resolveMethodR(node,info,name,args,ret,tp,resfl | ResolveFlags.NoImports)
		;	isInterface(),
			defaults @= sub_clazz,
			defaults.isClazz() && defaults.name.short_name.equals(nameIdefault),
			defaults.resolveMethodR(node,info,name,args,ret,tp,resfl | ResolveFlags.NoSuper )
		;	(resfl & ResolveFlags.NoSuper) == 0,
			isInterface(),
			sup @= interfaces,
			sup.clazz.resolveMethodR(node,info,name,args,ret,tp,resfl | ResolveFlags.NoImports)
		;	(resfl & ResolveFlags.NoForwards) == 0,
			forw @= fields,
			forw.isForward(),
			info.enterForward(forw) : info.leaveForward(forw),
			Type.getRealType(tp,forw.type).clazz.resolveMethodR(node,info,name,args,Type.getRealType(tp,ret),Type.getRealType(tp,forw.type),resfl | ResolveFlags.NoImports)
		}
	}


PS это kiev compiler.

(Reply to this)(Thread)

Re: пример
[info]kouzdra
2004-07-16 12:50 pm UTC (link)
В функциональщие бэктрэкинг обычно (это я для осторожности, думаю, что на самом деле всегда) легко делается с помощью ленивых списков и композиции в монадном стиле.

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

(Reply to this)(Parent)(Thread)

Re: пример
(Anonymous)
2004-07-16 06:05 pm UTC (link)
А кто сказал, во что этот код превращается?
Я не говорил :)
Да, он раскатывается в state machine, но только потому, что в JVM это представление эффективнее. И в любом случае, подобная запись - более удобна и наглядна, чем ручками изображенный список closures или другим подобным способом.

Тут ведь не просто новый синтаксис. Как здесь, так и в примере приведёном Сергеем - новый синтаксис есть лишь удобное отображение некоей новой фишки в языке. Ты говоришь, что тебе нужна другая система типов - а кто мешает её добавить в среду описываемую Сергеем? Ну да, это будет не просто. Добавить нечто кардинально новое в язык - это очень не просто. Но сейчас ты для этого должен написать новый язык программирования, который будет интересен только как коллекционный (в лучшем случае - академический) экземпляр. Имея же подобную среду - этим смогут воспользоваться почти все.
Смогут по двум причинам - а) мы абстрагируемся от синтаксиса, и б) мы до определённой степени абстрагируемся от реализации. Ну вот ещё пример попроще, и понагляднее. Допустим, нам хочется сделать в яве или С или ещё где (где этого нет) switch по строкам. Типа
switch(x) {
case "hello": ...;
case "goodbye": ...;
default: ...;
}
Мы вводим соответствующее описание в граммитику языка, и после этого мы можем писать и отлаживать код в IDE. Так вот - реализация нас тоже, по большому счёту, не очень интересует. Это может быть реализовано на более низком уровне как цепочка if/else, а может быть реализовано через компиляцию кейсов в регулярное выражение, а может ещё как.
Это просто такой конструктор юнного писателя языка программирования. Он может задавать другой синтаксис, может задавать новые операторы, может вводить новые концепции (как с этой близкой к прологу концепции из kiev compiler), может ввеси новую семантику и синтаксис для областей видимости, может добавить новую систему типов, и вообще менять почти всё. И для всего этого ему не прийдётся полностью писать язык с нуля, и не надо будет писать с нуля новую IDE для удобной работы.

(Reply to this)(Parent)(Thread)

Re: пример
[info]kouzdra
2004-07-16 06:23 pm UTC (link)
Я о другом - конструкции с бэктркингом по-моему легко и без геммороя переписываются на Haskell с использованием монад.

У меня вобще есть сильное подозрение, что бэктрекинг - это частный случай монад. Кстати - я бы это с удовольствием проверил - то есть я готов попробовать попереписывать не слишком громоздкие примеры на Haskell. Если найдется что-то, что плохо переписывается - мне будет интересно.

По поводу синтаксиса - я вообще не очень верю в полезность синтаксической расширяемости. Точнее - польза есть, но imho более умеренная, чем можно подумать. В O'Caml ведь возможность делать практически произвольные расширения синтаксиса имеется. Она полезна, но довольно умерено (хотя пока я ей не попользовался - я ее тоже считал очень нужной). Скажем - можно сделать так, чтобы вместо
Array.iter (fun x -> printf "%d " x) myArray
писать
foreach x from myArray do
printf "%d " x
done

Но так ли оно важно?

Более важен не синтаксиис, а семантика, а вот это-то тут полностью остается за кадром.

PS: Есть еще Tcl - он тоже макропроцессор, там вообще почти какой угодно синтаксис можно наописывать. Ну тоже - вроде как-то полезно, но не очень.

PPS: Вот гибкий синтаксический редактор с ala-"идейными" фичами - это полезно, но это другая задача. И опять же - значительная часть рефакторингов завязана на семантику. Скажем в O'Caml поиску предков соотвествует поиск всех супертипов, а subtyping там структурный и типы могут вообще не иметь имени.

(Reply to this)(Parent)

Вот - кстати -
[info]kouzdra
2004-07-16 07:34 pm UTC (link)
---
понагляднее. Допустим, нам хочется сделать в яве или С или ещё где (где этого нет) switch по строкам. Типа
switch(x) {
case "hello": ...;
case "goodbye": ...;
default: ...;
}
----
Я вероятно захочу, чтобы в case можно было писать и имена строковых констант. В результате - помимо самой грамматики необходимо знать типы меток и/или переменной (поскольку от типа зависит генерация - терять обычный switch вероятно жалко). Стало быть в наш фреймворк надо вводить какую-то работу с типами. На этом большая часть прелестей Camlевой расширяемости и обламывается - поскольку цикл по массивам и по спискам должны иметь разное порождение (List.iter и Array.iter - перегрузки в ML нет и ввести ее нельзя по принципиальным соображениям). Собственно - вот проблема - для кажого нового типа своя грамматика для итератора.

(Reply to this)(Parent)(Thread)

Re: Вот - кстати -
[info]_qwerty
2004-07-17 02:55 am UTC (link)
На практике оно может закончиться либо switch_string'ом либо перегрузкой по типу параметра x.

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

Чем чревато наворачивание хитро обрабатываемых атрибутов (типов, перегрузки по типам и, наверняка, подтипов), вполне понятно.

(Reply to this)(Parent)

Re: пример
[info]_qwerty
2004-07-17 03:17 am UTC (link)
Насчет конструктора юннннного писателя языка программирования.

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

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

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

(Reply to this)(Parent)


[info]_qwerty
2004-07-13 09:40 pm UTC (link)
В свете дискуссии об инкрементных преобразованиях программ - поищи
"Incremental evaluation of computational circuits" и
"Alphonse: incremental computation as a programming abstraction".

Ищется в Гугле, лежит в ACM'овской библиотеке. Оно вообще полезно, а Роджер Хувер был одним из главных действующих лиц в Модуле-3 и NaturalBridge jvm.

(Reply to this)


[info]_qwerty
2004-07-27 08:12 pm UTC (link)
http://www.theregister.co.uk/2004/07/27/esmertec_acquires_oovm
Ларс Бак до Сана возился с Сэлфом, в Сане, в частности, сваял сборщик мусора поколениями со скользящим окошком для Ж2МЕ. Потом уехал к себе в Данию, сделал себе мелкую конторку, в которой продолжал возиться с виртуевыми машинами и компиляцией на лету. Из общей среды родил виртуевые машины для Сэлфа, Смолтока и Жабы. Какова именно структура общего промежуточного кода, не знаю. Из него торчат крючки и рукоятки, чтобы легче было средства разработки подцеплять. Теперь вот его Эзмертек купил.

(Reply to this)(Thread)

и?
(Anonymous)
2004-07-28 08:46 pm UTC (link)
А какое это имеет отношение к данной теме?
Я вот из этого самого esmertec-а, и сидел сегодня на его презентации неудержимо зевая.
Вкратце - 99% маркетингового фуфла, и 1% информации. 1% о том, что это Smalltalk. Обрезанный. То, что он раньше занимался Self-ом и Java - к oovm отношения не имеет никакого, кроме его личного опыта по участию в проектах связанных с vm-ками.

(Reply to this)(Parent)(Thread)

Re: и?
[info]_qwerty
2004-07-29 12:01 am UTC (link)
Самое прямое отношение - рефлексирующее промежуточное представление, не привязанное к одному конкретному языку программирования.

Когда человек делает что-то с предметом, на обоих остается соответствующий отпечаток, обычно характерный. А Ларса Бака лично я знаю по его коду в сборщике мусора. Код хорощий и совсем не глупый.

А презентации действительно пофиг.

(Reply to this)(Parent)(Thread)

Re: и?
(Anonymous)
2004-07-29 12:43 am UTC (link)
Код там напрямую привязан к Smalltalk-у, и ни к чему больше. В основном они сделали:
а) оставили на железке от всей VM-ки один интерпретатор
б) делают глобальную оптимизацию кода на хосте, в частности с profile-based инлайнингом
в) умеют апдейтить код и данные на железке через сеть
Собственно, это всё (не считая важных, но нудных деталей типа плагина для eclipse и пр). Остальные "достижения" о которых они рассказывают - только следствие вышеупомянутого, а именно:
а) небольшие требования к памяти - а чего там требовать, если там только интерпретатор без всего остального; а с фортом им слабо было размер VM-ки сравнить :)
б) вдвое быстрей любого явовского интерпретатора - ещё-бы, с глобальной то оптимизацией на хосте; да и не понятно где они эти явовские интерпретаторы брали - если они сравнивали с Sun-овским же KVM - то я когда-то за смешные деньги его Samsung-у в 8 раз ускорил
в) апдейт без перезагрузки системы - ну так на то он и Smalltalk, что там объектами является всё до последнего байта, вся информация есть.
Принципиально они просто сделали хороший оптимизирующий компайлер в свой личный байткод, и тщательно проработали апгрейд "на лету" работающей системы без её остановки. А вот маркетинговый пафос (малые требования, вся из себя ОО) - только для безграмотных менагеров работает, а реально какой-нибудь форт требовал-бы меньше, а какой-нибудь функциональный язык (а-ля OCaml) был-бы много мощнее. Что и обнаружилось не сходя с места, когда упрощённая реализация IP стека сразу подняла требования к памяти с 32 до 128 кб - осталось добавить GUI, и оно потребует больше J2ME :) Собственно, если выкинуть из java столько, сколько они выкинули из Smalltalk-а - она будет не хуже, а может и лучше. Чудес не бывает.

Я не говорю, что он плохой программист. Но принципиально нового (в смысле развития программирования) там ничего нет вообще. Он сам сказал - мы ничего не добавляли, мы только отрезали ненужное для embedded девайсов.
И уж никакого непривязанного к языку представления - там нет и подавно.

(Reply to this)(Parent)(Thread)

Re: и?
[info]_qwerty
2004-07-29 01:30 am UTC (link)
Нет ли технического описания промежуточного кода? Каким образом и в каком смысле он привязан к Смолтоку?

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

в) Чего-то я не понимаю. Вы про какую все-таки ВМ говорите? Если про Смолток, то как сравнивать с Жабьим КВМом? Если же про Жабу, то причем тут Смолток?

Оптимизюче транслировать Жабу в коды Смолтоковской ВМ как-то смысла не сильно много. Стековый интерпретатор на распространенных современных процессорах не может не тормозить из-за архитектурной разницы между интерпретатором и реальным железом. Лучше, чем стандартный жабий код, конечно, сделать можно, но чтобы сильно - что-то сомнительно. Про отдельную кривизну типа отсутствия инициализаторов массивов константами я не говорю.

Если никакого непривязанного к языку представления нет, а есть только низкоуровневое представление сугубо для оптимизючей трансляции из одного байткода в другой, то, действительно, не интересно. Но хотелось бы в этом убедиться.

В смысле же размера ьыдо бы радикальнее сгенерировать код под данное конкретное приложение, снабдить его специально сгенерированным же интерпретатором и заслать для выполнения. Идея старая.

(Reply to this)(Parent)(Thread)

Re: и?
(Anonymous)
2004-07-29 08:57 am UTC (link)
Привязан к Smalltalk-у он очень просто - из исходного кода Smalltalk-а генерируется байткод для Smalltalk VM. Откуда там взятся независимому от языка промежуточному представлению?

К сожалению, мылом обсуждать особенно нечего по двум причинам - а) кода их я ещё не видел (их же только вчера купили, их код ещё в репозитории не появился и я его не видел), и б) поди разберись, не выдам ли я какую страшную тайну :) Но если что - пиши на mkizub at esmertec dot com

Разные языки программирования (в том числе с разными VM) сравниваются очень просто - пишется бенчмарк на обоих языках (какое-нибудь вычисление чисел Фибоначи), и рассказывается о том, как наша платформа круто уделала конкурирующую платформу. Видимо так он и сравнивал по скорости oovm и jvm - правда, исходников самих бенчмарков не приводит :) Хотя основная идея оптимизации интерпретатора у него проглядывается - они используют 20 опкодов для своей VM, а остальные 236 используют для объединения нескольких опкодов в один. То есть в среднем, там где ява исполняет 2 опкода - они исполняют 1.

Откуда у тебя взялось "трансляция из одного байткода в другой" мне не понятно. Они из исходников ST в байткод для ST компиляют, никаких "других" байткодов там нет.

Интерпретатор под каждое конкретное приложение они не делают (он у них на С++ сделан). Но сам набор объединённых байткодов (вот эти 236 штук) - это опять-же profile-based методом они выяснили для типичного приложения. Они подумывают над изготовлением интерпретатора "на лету", но пока сильно сомневаются, что с этого будет заметный эффект.

(Reply to this)(Parent)(Thread)

Re: и?
[info]_qwerty
2004-07-29 05:38 pm UTC (link)
Понятно. Бак с двумя своими шпирантами довел до конца опупею со СтронгТолком. Все оказалось проще, чем в рассказанных мне сплетнях. Да, к теме отношения не имеет и не очень-то интересно.

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

Сжатие со статическим словарем с сохранением исполняемости.


(Reply to this)(Parent)

С понедельника начинаю новую жизнь
(Anonymous)
2004-07-29 07:21 pm UTC (link)
Две недели отпуска сказались, и я выкидываю предыдущую попытку создать такую среду. Второй раз выкидываю... За время отпуска по новому оформилось видение как эту среду делать. Вот где-то так:

bootstrap.

Всё сделано на функциях и узлах. Функция - это типа класса в яве, а узел - это instance этого класса. Но гораздо больше это, конечно, похоже на функциональные языки программирования.

Изначально у нас есть основная функция define и функции для полей define-a - поле (для хранения child узла), ссылка на не-child узел, и список узлов (0 и больше и 1 и больше). Ещё пара примитивных функций - identifier и string. Сама функция define предназначена для определения новых функций. Функции могут иметь предков, то есть это будет множественное наследование. Поля функций имеют "тип", который есть просто имя функции узел которой в это поле можно положить. Саму в себе эту систему (грубо) можно изобразить так:

(define ident () ())
(define string () ())
(define abstract-fld () ((ident name) (fld& define)))
(define fld (abstract-fld) ()) ; child node
(define fld& (abstract-fld) ()) ; reference to on-child node
(define lst* (abstract-fld) ()) ; possible empty list of chld nodes
(define lst+ (abstract-fld) ()) ; 1 or more list of child nodes
(define lst&* (abstract-fld)()) ; possible empty list of references
(define lst&+ (abstract-fld)()) ; 1 or more list of references
(define define (ident name) (lst&* define super) (lst* fld fields))

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

(define java-decl () (fld ident name))
(define java-type-decl (java-decl))
(define java-class (java-type-decl)
(fld& java-class super-class)
(lst&* java-iface super-ifaces)
(lst&* java-decl members))
(define java-iface (java-type-decl)
(lst&* java-iface super-ifaces)
(lst&* java-method-decl members))
(define java-field-decl (java-decl)
(string java-type-decl type))
(define java-method-decl (java-decl)
(string java-type-decl return-type)
(lst* java-param-decl params))
(define java-param-decl (java-decl)
(ident name)
(java-type-decl& type))

После этого мы скажем "скомпилировать", и это просто выведет все define-ед узлы не в вышенарисованном синтаксисе, а в явовском синтаксисе - и это мы отдадить скушать явовскому компилятору, и готово - система сама себя сгенерировала. Правила генерации из define в java-class и java-iface можно, в общем-то, в этом же самом синтаксисе записать. Ну и синтаксис тоже будет в терминах функций и узлов записан, как-же без этого :)

Известная истина - только тот язык программирования является универсальным, который сам себя может скомпилировать. В данном случае - среда программирования сможет "сама себя создать". Чем я с понедельника и займусь :)

(Reply to this)(Thread)

Re: С понедельника начинаю новую жизнь
[info]_qwerty
2004-07-29 07:59 pm UTC (link)
Вообще-то просто нарисована структура деревяхи, причем нельзя сказать, что минимальная. Типы узлов названы функциями.

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

Что означает принадлежность к типу, почему-то не уточняется.

Из узелка торчат ссылочки. Набор ссылочек разбит на группы (идентификация, предки, сыновья, сосед). Ссылочки, видимо, должны обладать некими семантическими свойствами во избежание циклов, но про это ничего не говорится. Идентификация, видимо, тоже должна обладать особыми свойствами, про нее ничего не говорится тоже.

Уже видны какие-то непонятные амперсанды и звездочки, смысл которых не объясняется. Подозреваю худшее :)

А каковы были две предыдущие попытки?

(Reply to this)(Parent)(Thread)

Re: С понедельника начинаю новую жизнь
(Anonymous)
2004-07-29 09:47 pm UTC (link)
Типы уз