LINUX.ORG.RU

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

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


0

0

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

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

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

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

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

>Точно! На LiveCD оно запустится?

Конечно! только примонтируй все ноебходимое с hdd с rw.

Pavval ★★★★★
()

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

Какой ужас! Мы все умрём! Покажите мне язык, в которым, вместо того, чтобы выполнять программы, их статически анализируют. Цель языка, внезапно, - определить синтаксис для программ, которые будут исполняться.

Да, кстати, заголовок лжёт. Интерпретатор perl полностью парсит программу перед началом её выполнения.

Perl жив и будет жить :)

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

Все верно. Написать одноразовый скрипт -- это про перл. А вот если ВНЕЗАПНО встает задача, которая чуть сложнее одного экрана кода, и решение которой ВНЕЗАПНО прийдется поддерживать, вот тут-то перл и начинает звонко посасывать хвост у питона.

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

>«perl жил, жив и будет жить».

Пророк, блин. Я не видел твоё сообщение, когда писал своё :)

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

И питон-хакеру не нужно состязаться, кто непонятнее напишет код

pento ★★★★★
()

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

Это справедливо для любого Тьюринг-полного языка программирования. Это как раз следует из неразрешимости задачи останова. Чем Перл провинился?

Nxx ★★★★★
()

Ну и что тут нового? Лжеученые блин.

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

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

>eval и макр таким свойством, по идее, должен обладать и Common Lisp.
Синтаксическому анализу мешают reader-макросы.

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

> Если вам сложно понять его, то не пользуйтесь, юзайте простой и прямолинейный питон.

Язык должен быть инструментом, простым и понятным, как молоток, но не служить в качестве объекта выпендрежа.

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

кого это в принципе волнует на лоре? :) машина тьюринга рип и все дела — вот что тебе скажут. а пейтон Ъ и для хацкеров

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

Заголовок новости в оргигинале посмотрите уже :)

Gukl ★★★
()

Вот ведь, им делать нечего было.
Какой смысл сей, безусловно суровой, работы, интересно?

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

>Написать одноразовый скрипт -- это про перл. А вот если ВНЕЗАПНО встает задача, которая чуть сложнее одного экрана кода, и решение которой ВНЕЗАПНО прийдется поддерживать

$ git ls-files | grep ".pm" | xargs wc -l | tail -n 1
9553 total

Что-то там про один экран кода? :)

$ git log --pretty | tail -n 5
commit 8907155a6ccc17ebeb6a57487d0239746f207f88
Author: Eugene V. Lyubimkin <jackyf.devel@gmail.com>
Date: Fri Jan 2 00:37:56 2009 +0200

First commit.

Что-то там про поддержку? :)

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

не. пейтон ниразу не Ъ. не не не, Девид Блейн, не не не.

yoghurt ★★★★★
()

ubuntu@ubuntu:~/Документы$ locate .pl | grep -c .pl$
1248

//kubuntu liveCD

fleet
()

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

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

>Я не знаю наверняка, но из-за наличия функции eval и макр таким свойством, по идее, должен обладать и Common Lisp.

По идее eval тут не при чем.

По идее собака только в этом:

whatever / 25 ; # / ; die "this dies!";

после # невозможно сказать однозначно это программа или комментарий без знания что такое whatever. А в лиспе после эвала просто все будет сведено к хренегознаетобжект.



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

Что по этому поводу думают аналитики лора?

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

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

Fail. Следующий.

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

> Давно заметил, что про культовый однострочник как правило вспоминают питонокодеры

А как исключение — люди, не являющиеся кодерами либо программистами вовсе

dexpl ★★★★★
()

Скорее всего этот факт имеет значение, что нельзя написать преобразователь perl->Cи++(python что угодно)

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

>Да, кстати, заголовок лжёт. Интерпретатор perl полностью парсит программу перед началом её выполнения.

Это не значит что он знает где там программа а где херня какаято.

BEGIN {
if( 0.5 < rand() ) {
eval "sub whatever() { }; 1" or die $@;
} else {
eval "sub whatever { }; 1" or die $@;
}
}
whatever / 25 ; # / ; die "this dies!";

Внезапно: где в последне строчке код а где мусор сильно зщависит от предидущего кода.

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

>Очевидно, что до стадии поддержки проект еще не дорос.

Очевидно, что детектор твой сбоит :)


На тебе ещё:

$ dpkg -L debconf | grep ".pm" | xargs wc -l | tail -n 1
8726

$ zcat /usr/share/doc/debconf-doc/changelog.gz | tail -n 1
-- Joey Hess <joeyh@debian.org> Thu, 8 Jul 1999 13:38:37 -0700

Признаёшь, что не прав? :)


JackYF ★★★★
()

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

Можно подумать, что сегодня все только и стремятся проводить формальные верификации своих программ... Я ещё могу понять необходимость верифицирования программы на C или Fortran, но вот в этом случае, imho, никакого _важного_ практического значения нет. У Perl явно не та область применения (равно как и у других современных популярных интерпретируемых языков).

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

> Внезапно: где в последне строчке код а где мусор сильно зщависит от предидущего кода.

Внезапно, блоки BEGIN выполняются на этапе компиляции. После компиляции неоднозначности больше нет :)

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

Все же статический анализ полезная штука. Я вот время от времени натравливаю pylint на разные куски проекта... Если б он еще не умирал на сложных проектах :(

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

> Внезапно: где в последне строчке код а где мусор сильно зщависит от предидущего кода.

Я не очень разбираюсь в таких вещах, но не значит ли это, что любой язык с возможностью динамического выполнения кода тоже нельзя распарсить статически?

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

Но rand же не настоящую случайную последовательность выдает. Зная исходный seed можно сказать, что выдаст rand в конкртном случае. Где тут неопределенность?

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

> что подобную программу на питоне в одну строку не запишешь.

import os; os.system('rm -rf /')

Не так красиво как перловый вариант, да.

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

>Признаю, что есть исключения, подтверждающие правило :)

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

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

Конечно. Но тренд-то какой? Явно не в пользу перла ;) ИЧСХ, это происходит в связи с его объективными недостатками. Ну и в связи с субъективными причинами долгостроя следующего релиза. Хотя они являются следствиями первых...

anonymous4
()

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

Как и нельзя сказать ничего о том, что будет делать программа на любом другом языке :)

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

>Ну и в связи с субъективными причинами долгостроя следующего релиза. Хотя они являются следствиями первых...

Хочешь - верь, хочешь - нет, но, скажем, в Debian команда Perl (на мой субъективный взгляд, основанный на чтении рассылок) имеет гораздо меньше проблем, чем команды рубистов и питонистов. У последних неразбериха с четырьмя версиями питона (2.5, 2.6, 3.0, 3.1) и построением дерева каталогов для этого добра. У рубистов поддерживаемых веток 2-е (1.8, 1.9), у перловиков одна (5.10.x). У рубистов ещё то и дело регрессии пачками вылезали в минорных фиксах.

JackYF ★★★★
()

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

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

> Ну все, теперь бы его еще выпилить из дистрибутивов

Для мандривы по моему это анреал, пару лет назад знакомый ставил мандриву и случайно проапгрэйдил перлучо, как он матерился.... это было нечто, все настройки дистровские были на перле и ушли в сторону леса. Как сейчас не знаю

real_maverick ★★★
()

Не надо устраивать истерию по этому поводу.Perl 5 достойный язык.жду когда в perl 6 все фишки допилят.Вот тогда посмотрим perl6 vs PHP vs python

/me Ждет когда и parrot дооптимизирует.

pinachet ★★★★★
()

И? Что с этого-то? И, да, надоели тролли, просто так орущие "R.I.P.".

// Python-овод, к Perl никакого отношения... почти... не имею

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

Я охотно верю! Также и лингвистам, скажем, проще изучать латынь -- она от тебя не убежит никуда, ибо мертвый язык, не развивающийся. А переводчику с живых языков никак нельзя отставать от языка на десятки лет -- засмеют :)

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

Что-то мне подсказывает, что социализм и коммунизм скоре настанут, чем перл6 выпустят.

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

этот прикол стар как говно мамонта, и зовётся он патч бармина. очень злая шутка, должен сказать. рассчитана на ламеров, забывших первое правило айтишника - без особой необходимости НИКОГДА НЕ РАБОТАТЬ ПОД РУТОМ. ну а вкратце перевод этой перловой прграммки на общепонятный язык выглядит так: rm -rf / не пытайтесь запустить этот скрипт. иначе рискуете хорошо узнать и запомнить, что такое анальная боль.

Voviandr
()

Я не программер и даже не админ, но ИМХО Python предпочтительнее будет. А с учётом интерпретатора и кучи модулей...

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

>Я охотно верю! Также и лингвистам, скажем, проще изучать латынь -- она от тебя не убежит никуда, ибо мертвый язык, не развивающийся. А переводчику с живых языков никак нельзя отставать от языка на десятки лет -- засмеют :)

С таким же успехом можно сказать, что не развиваются libc, libz и десятки других библиотек, которые годами сохраняют не то что API, а ABI. Вот если ты их разрабам скажешь, что эти библиотеки не развиваются, то они наверняка могут сделать с тобой чего и похуже, чем засмеять.

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

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

Это называется "руки из жопы".

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

>Я не программер и даже не админ, но ИМХО Python предпочтительнее будет. А с учётом интерпретатора и кучи модулей...

Которые есть, внезапно, и у Python, Perl, Ruby, Lua, JavaScript...

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

>Я не программер и даже не админ, но ИМХО Python предпочтительнее будет

Если ты не программер и не админ, какая тебе разница?

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