LINUX.ORG.RU

Доказана невозможность статического парсинга Perl 5

 , неразрешимость, ,


0

0

Формально доказана неразрешимость задачи статического синтаксического анализа Perl 5. В опубликованном доказательстве задача парсинга программы на Perl сводится к задаче остановки, которая, как известно любому школьнику, неразрешима.

Этот факт имеет важное практическое значение — он означает что в общем случае выяснить, что будет делать та или иная программа на Perl, возможно только выполнив саму программу. Методы статического анализа бессильны. Возникают ли подобые проблемы в Perl 6 — неизвестно.

Статьи (pdf): [1], [2], [3].

>>> Подробности

Ответ на: комментарий от yk4ever

> Следование стандартам - один из критериев, который отличает тру профессионала от всякой хни из-под ногтей.

Ну так стандартам, а не писание на конкретном языке же. Любой текст на Перле можно прогнатть через перлтиди с любыми стандратными параметрами, будет стандартней некуда.

Gukl ★★★
()
Ответ на: комментарий от anonymous4

>Ну первая же ссылка в гугле! http://www.linux.ime.usp.br/~matiello/python-graph/docs/

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

JackYF ★★★★
()
Ответ на: комментарий от KRoN73

>Дык, вопрос в любом случае глупый. Даже вот это: http://balancer.ru/lor/topics/3964656/reports/users-ograph.svg и то не с нуля, как бы, велосипедилось :)

Вообще-то, я спрашивал не и визуализации, а о графах как алгоритмических структурах. pygraph очень беден в плане функциональности. Ещё варианты будут?

JackYF ★★★★
()
Ответ на: комментарий от spaceblock

> А это как

Это копирование ссылки. tel и b указывают на один объект.

yk4ever
()
Ответ на: комментарий от Gukl

> Питон - стандарт уровня ГОСТ, что ли? Чего вдруг?

Для программистов на Питоне - отчасти да. А в случае с Перлом у каждого свой стандарт (ещё хорошо, если хоть какой то стиль всё таки выработан). Это для большинства языков так, просто Перл - особо тяжелый случай. Помогают только жёсткие административные меры, либо фашиствующий парсер. Либо и то и другое.

Hjorn
()
Ответ на: комментарий от Gukl

> Могу вернуть: а как у вас не?

Какого хрена доказывать, что я не верблюд?

На стиль кода в проекте не влияет ни специфика предметной области, ни погода в Занзибаре.

yk4ever
()
Ответ на: комментарий от anonymous4

Задача останова -- определить, потребует алгоритм конечного или бесконечного времени. Если даже есть алгоритмы из бесконечного числа операций, которые на описанной машине завершаются ранее, чем за одну мс, можно еще добавить счетчик тактов (или таймер), определяющий, завершилась ли программа за конечное число тактов.
А вообще да, интересно, если на такой машине запустить "while (i++);" завершится ли оно за конечное время

Xenius ★★★★★
()
Ответ на: комментарий от JackYF

MST в модуле minmax. В модуле accessibility - транзитивное замыкание/компоненты (сильной) связности/точки сочленения/мосты. Работа с вершинами/ребрами - вклассе graph/digraph, в том числе веса и аттрибуты. Что есть транспонирование графа я увы не знаю. Еще вопросы?

winger
()
Ответ на: комментарий от yk4ever

> > Вот за такое убивать надо.

> Сильно выражаешься, задрот. Хочешь встретиться, попробовать на практике реализовать своё предложение, м? Пока у тебя каникулы-то.

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

> А юникс-вэй как сосёт с проглотом последние 20 лет, так и будет продолжать.

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

grusha
()
Ответ на: комментарий от Gukl

>когда вводить классы, я как-нибудь сам разберусь. А пока они не нужны, мне их не надо

Тебе жить как-то мешает принцип "все объект"? Объективные проблемы есть у этого подхода? Можешь не отвечать, оно и так понятно, что цитата -- фагготория типа "что-нибудь сумничать хочется, да что-то неумно как-то получается".

anonymous4
()
Ответ на: комментарий от Gukl

>Я вам, вроде, пока что не тыкал...

That's okay, я не гордый, можешь и на "ты" :)

anonymous4
()
Ответ на: комментарий от spaceblock

Умница, теперь можешь покурить про оператор "is" и применить его к данному куску кода.

anonymous4
()
Ответ на: комментарий от JackYF

>pygraph очень беден в плане функциональности. Ещё варианты будут?

Вообще-то с чего вдруг всем лором тебе должны помогать искать библиотеку для работы с графами? Тем более, ладно бы тебе оно на деле нужно было, а не для троллинга. Если оно тебе действительно надо -- милости просим создавать тред в /d/, излагать суть проблемы, требования к библиотеке, рассмотренные варианты, их недостатки.

anonymous4
()
Ответ на: комментарий от Xenius

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

У тебя явно дилетантское представление о бесконечно больших величинах как о чем-то типа "оооочень много" :)

anonymous4
()
Ответ на: комментарий от winger

>MST в модуле minmax
Принято.

>В модуле accessibility - транзитивное замыкание/компоненты (сильной) связности

Принято.

>Работа с вершинами/ребрами - вклассе graph/digraph, в том числе веса и аттрибуты.

Частично принято. Где удаление атрибутов?

>Что есть транспонирование графа я увы не знаю.

(u, v) -> (v, u) для всех ребёр (u - v)

>Еще вопросы?


Да. Например, как я могу получить список входящих в конкретную вершину ребёр для направленных графов? Исходящих? Увидел digraph::incidents, digraph::neighbors, это они?

Но в целом - спасибо за конкретику, большинство претензий сняты.

Следующий вопрос: как обстоят дела с высокоуровневыми интерфейсами к систему вызову select, к примеру? Как они выглядят?

JackYF ★★★★
()
Ответ на: комментарий от yk4ever

>С точки зрения разработчика ведь одно и то же :]

Здрасьте! Если массив копируется на присовении, то голова должна заботиться о минимазации таких присовений и насыщений кода ссылками на переменные где только можно. Если copy-on-write - то присваивать (а, главное, возвращать из процедур) можно не задумываясь о производительности.

...

Впрочем, голова, всё же, работать должна в любом случае, хоть с копированием, хоть без, хоть с copy-on-write... Но, ИМХО, copy-on-write порождает головной боли меньше :)

KRoN73 ★★★★★
()
Ответ на: комментарий от grusha

> Вот уж не думал кого-то этой фразой удивить - реакция-то какая бурная...

А вы следите за своими словами, следите. В жизни пригодится.

> Юникс-вэй это квинтэссенция известных с древности принципов создания хороших систем, в применении к ПО.

Хорошая система - это система, которая удовлетворяет потребности пользователя. Юникс-вэй, как известно, удовлетворяет потребности программистов.

Мне, как программисту, конечно очень приятно было бы писать ворохи консольных утилиток, да. В душе я юниксоид. Только они мало кому нужны, вот в чём беда.

yk4ever
()
Ответ на: комментарий от anonymous4

Пока тут кто-то троллил, другой человек грамотно отразил большинство моих претензий. Учитесь :)

З.Ы. Атрибуты графа, атрибуты ребёр, сильносвязные компоненты и проверки доступности вершин используются в моём перловом проекте. Так что вопросы были не от балды :)

JackYF ★★★★
()
Ответ на: комментарий от JackYF

>Пока тут кто-то троллил, другой человек грамотно отразил большинство моих претензий.

Я бы и сам с удовольствием поотражал бы, да не очень в предметной области разбираюсь :) Но я по крайней мере сделал за тебя работу по вбиванию "python graph library" в гугл, пока тут кто-то троллил ;)

>как обстоят дела с высокоуровневыми интерфейсами к систему вызову select, к примеру? Как они выглядят?

Хорошо обстоят, прекрасно выглядят. См. документацию: http://docs.python.org/library/select.html

anonymous4
()
Ответ на: комментарий от JackYF

> Частично принято. Где удаление атрибутов?

Напрямую видимо нельзя, но node_attributes возвращает ссылку на список, который можно напрямую модифицировать

> Да. Например, как я могу получить список входящих в конкретную вершину ребёр для направленных графов? Исходящих? Увидел digraph::incidents, digraph::neighbors, это они?

Они, да

>>Что есть транспонирование графа я увы не знаю. >(u, v) -> (v, u) для всех ребёр (u - v)

reverse

Вообще, если в этой либе чего-то не хватает, есть биндинги к boost::graph

ЗЫ. Я питон начал изучать два дня назад. Открыл код этой либы и мне абсолютно все там понятно)

winger
()
Ответ на: комментарий от anonymous4

>Но я по крайней мере сделал за тебя работу по вбиванию "python graph library" в гугл, пока тут кто-то троллил ;)

Я предпочитаю выслушивать аргументы из уст оппонента, а не находить их самому. Иначе можно нарваться на "да ты не то смотришь!". Да и смысл спора теряется ^_^

>Хорошо обстоят, прекрасно выглядят. См. документацию: http://docs.python.org/library/select.html

Да, соглашусь :)

Пожалуй, у меня всё.

JackYF ★★★★
()
Ответ на: комментарий от winger

>ЗЫ. Я питон начал изучать два дня назад. Открыл код этой либы и мне абсолютно все там понятно)

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

JackYF ★★★★
()
Ответ на: комментарий от yk4ever

> Ну смотрите. У инженеров есть стандарты - ГОСТ, ISO и проч. Инженера, который делает не по стандарту - сразу шлют нахрен.

> Внимание, вопрос: почему у программистов должно быть иначе?


Это ж очевидно - они не хотят чтобы их слали нахер.

r ★★★★★
()
Ответ на: комментарий от yk4ever

> А вы следите за своими словами, следите. В жизни пригодится.

Вы не знакомы с культурным контекстом.

> Хорошая система - это система, которая удовлетворяет потребности пользователя. Юникс-вэй, как известно, удовлетворяет потребности программистов.

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

> Мне, как программисту, конечно очень приятно было бы писать ворохи консольных утилиток, да. В душе я юниксоид. Только они мало кому нужны, вот в чём беда.

Знаете, чем юниксоид отличается от виндузятника? Он понимает, что ему нужно. Осознаёт.

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

grusha
()
Ответ на: комментарий от Gukl

>Питон - стандарт уровня ГОСТ, что ли? Чего вдруг? Несколько разные вещи.

Ну вообще-то одинаковые. Всякие стандарты существую дабы один написал а второй понял. Другое дело что важно почему это важно. Если строитель мостов нетак чето поймет - беда будет. А тут беды особой не будет - потому нафик ограничения! Даешь свободу именования переменных!

А то не дай бог гики из ASF продвинут нейминг конвеншен в качестве стандарта - у половины мира зубы вывалятся от венгерской нотации.

r ★★★★★
()
Ответ на: комментарий от r

> Всякие стандарты существую дабы один написал а второй понял.

Прямо всякие? ))) Да, если один из этих двоих, или оба, - компьютер/программа. Стандарты существуют для совместимости интерфейсов. Конечно, если людей использовать как роботов, то да, надо формализовать их взаимодействие.

grusha
()
Ответ на: комментарий от yk4ever

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

<ЧСВ> Вот это нужно было написать в самом начале. Чувак, боюсь перл тут не причем - просто у тебя ещё не вырос моск ! %-) </ЧСВ>

anonizmus
()
Ответ на: комментарий от grusha

>рямо всякие? ))) Да, если один из этих двоих, или оба, - компьютер/программа.

В данном сулчае мы говорим про документацию.

>Стандарты существуют для совместимости интерфейсов.


Точно. Inter-face. Фейсоморда одного инженера к фейсоморде другого.

>Конечно, если людей использовать как роботов, то да, надо формализовать их взаимодействие.


man госты на конструкторскую докумекнтацию и тому подобную фигню.

r ★★★★★
()
Ответ на: комментарий от r

> В данном сулчае мы говорим про документацию.

А я думал, что про код...

> man госты на конструкторскую докумекнтацию и тому подобную фигню.

Да знаю я. Лень чего-то доказывать, спать пора...

grusha
()
Ответ на: комментарий от anonymous4

> фагготория...сумничать хочется, да что-то неумно как-то получается

Черт, я ж на ЛОРе. Хорошо, что напомнили.

Gukl ★★★
()
Ответ на: комментарий от grusha

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

Красноглазиками-то? Да кто их слушает, чего они там буровят.

> Знаете, чем юниксоид отличается от виндузятника? Он понимает, что ему нужно. Осознаёт.

4.2 Юниксоид отличается ЧСВ, красными глазами и задротством. А виндузятники живут нормальной человеческой жизнью.

> Маленьких детей надо учить не таблице умножения и кнопке пуск, а командной строке и скриптам.

Чтоб выросли задротами и не размножались, ога. Пусть нигры размножаются.

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

yk4ever
()
Ответ на: комментарий от anonizmus

> Чувак, боюсь перл тут не причем - просто у тебя ещё не вырос моск !

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

yk4ever
()
Ответ на: комментарий от yk4ever

> На стиль кода в проекте не влияет ни специфика предметной области, ни погода в Занзибаре.

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

Gukl ★★★
()
Ответ на: комментарий от Gukl

>вориться ;) Поэтому предпочитают язык с меньшим количеством возможностей, да.

- доказал что беспросветно глуп

spaceblock
()
Ответ на: комментарий от yk4ever

Понятно, думать не хотим. Человек не должен думать, думать - это задротство.

> > Маленьких детей надо учить не таблице умножения и кнопке пуск, а командной строке и скриптам.

> Чтоб выросли задротами и не размножались, ога. Пусть нигры размножаются.

Чтоб моск иногда работал.

> Сколько раз объяснять: человек делал машины не для того, чтобы у них отсасывать. Интерфейсы машин должны ориентироваться на человека, а не наоборот.

Ну и как кнопка пуск и свалка иконок на рабочем столе ориентируются на человека? Человек делал машины, чтобы меньше работать руками и больше головой.

grusha
()
Ответ на: комментарий от r

Давайте введем Единую Систему Программерской Документации - говнокода станет меньше? Ударим бюрократией по говнокодерству, ага.

grusha
()
Ответ на: комментарий от Gukl

> На стиль кодавлияет договоренность команды, а уж договорится можно хоть о погоде в Занзибаре.

Вам сторонними компонентами не приходилось пользоваться (и адаптировать их) никогда? С удалёнными аутсорсерами не работали?

Эхехе, детсад. "Мы самые умные, сами всё разберёмся, нам никто не нужын!"

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

С меньшим? В перле уже появились list comprehensions и keyword arguments?

yk4ever
()
Ответ на: комментарий от grusha

> Человек не должен думать, думать - это задротство.

Человек должен думать о решении своих задач, а не о командной строке.

> Ну и как кнопка пуск и свалка иконок на рабочем столе ориентируются на человека?

Тыкать пальцем в значки - естественней, чем команды набирать.

> Человек делал машины, чтобы меньше работать руками и больше головой.

Нет. Человек делал машины, чтобы меньше работать вообще.

yk4ever
()
Ответ на: комментарий от grusha

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

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

> Маленьких детей надо учить не таблице умножения и кнопке пуск, а командной строке и скриптам

Бедные маленькие дети, какой хренью их только не пытаются обучать. Теперь ещё и скрипты... Вы хотите превратить школу в инкубатор для сисадминов что ли?

Hjorn
()
Ответ на: комментарий от yk4ever

> Человек должен думать о решении своих задач, а не о командной строке.

Командная строка помогает решать задачи. Лучше пока ничего не придумали.

> Тыкать пальцем в значки - естественней, чем команды набирать.

"Именно то, что наиболее естественно, менее всего подобает человеку." (c) Давайте уж откажемся от письменности и вернемся к наскальным рисункам.

> > Человек делал машины, чтобы меньше работать руками и больше головой.

> Нет. Человек делал машины, чтобы меньше работать вообще.

За счет головы.

grusha
()
Ответ на: комментарий от Hjorn

> Бедные маленькие дети, какой хренью их только не пытаются обучать. Теперь ещё и скрипты... Вы хотите превратить школу в инкубатор для сисадминов что ли?

Я в дошкольном возрасте батники писал, и ничё.

grusha
()
Ответ на: комментарий от yk4ever

> Вам сторонними компонентами не приходилось пользоваться (и адаптировать их) никогда? С удалёнными аутсорсерами не работали?

Это-то здесь при чем?

> list comprehensions и keyword arguments?

Реализуемо на раз, второе даже сам делал в одном проекте (громко сказано, ибо + 1 строчка к функции). Пан любит сахарок? Ну так вам в третьей версии насыпят так, что Питон будет обфусцироваться круче Перла ;)

Gukl ★★★
()
Ответ на: комментарий от yk4ever

> Тыкать пальцем в значки - естественней, чем команды набирать.

Утверждение, требуещее доказательства. Противоположную мысль покойный Джефф Раскин, помнится, обосновал довольно-таки крепко.

Gukl ★★★
()
Ответ на: комментарий от yk4ever

>Моск у меня отличный. Просто мне совершенно лень задрачивать его ублюочным перлом.

Мне кажется тебе надо пойти в менеджеры, толкать ублюдочные проекты на недожабке и дотнете, как раз у тебя то самое нужное количество говна и соплей, думать там кстати не надо вообще, как и мозг задрачивать - главное одеть рубашку подороже и позолоченные часики и китайский верту положить на стол, и пафосно так говорить "клиентам" "рынок сейчас выбирает ЭТО, потому что это модно, глобально и надежно, а ещё (на ухо) я вам такой откатище дам !!! %))

Сначала хотел послать тебя сажать овощи (картошку например) в среднюю полосу, но сразу пришло понимание что это слишком сложно для тебя будет, надо там удобрения разные посыпать, блин... И все такое.. Не приведи Ктулху ещё придецо строить какой нить парник !! Это же пездец. Хотя с другой стороны - наверное можно купить уже готовый.

>код на них я обычно понимаю сходу.

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

anonizmus
()
Ответ на: комментарий от yk4ever

>Тыкать пальцем в значки - естественней, чем команды набирать.

Езжай сажать картошку в среднюю полосу. Ты станешь приносить пользу своей стране. Я знаю, это трудно. Будет. (там надо думать) Но таких как ты в IT быть не должно %-)

anonizmus
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.