kouzdra (kouzdra) wrote,
kouzdra
kouzdra

Categories:

Примерчик к завершаемости AKA ""всем похер"

Я уже упоминал, что лет 10+ назад я умел "подвешивать" сановский компилятор Джавы. Ну так я проверил - оно все как было так и осталось: вот это:

public class test {
    public static void main(String[] args) {
        // Prints "Hello, World" in the terminal window.
        System.out.println("Hello, World");
    }

    public static class C<A,B> { }
    public static <T> C<T,T> f (T a) { return null; }

    public static void g () {
        String a = "";
        int i = f (f (f (f (f (f (f (f (  f (f (f (f (f (f (f (f (  f (f (f (f (f (f (f (f (a)))))))) )))))))) ))))))));
    }

}

по крайней мере мою eee-шку заставляет уйти в себя минимум на несколько минут. Если оно все-таки за разумное время* на нормальной машинке пройдет - ну добавьте еще пачку вложенных вызовов.

Так вот
1) задача компиляции жабского кода разрешима (это кажется в приступе научного онанизма даже доказали)

2) сановский компилятор скорее всего этим свойством обладает (афайк никто даже не пытался доказывать - бо траху много, на грант не сделаешь - а толку никакого от слова совсем)

3) вероятно задача разумным образом ограничена по сложности для любого входа (а вот это afaik никто не доказывал)

4) а вот свойством (3) сановский компилятор не обладает - см. пример

А теперь главное - (4)

- всем давно известно
- по крайней мере в части type inference тут никакой экспоненциальной сложности по существу нет - просто у них "написали как проще"
- данная дыра всем, кто в теме, давно известна
- ВСЕМ ПОХЕР - потому что не мешает

Вот именно "ВСЕМ ПОХЕР" и есть характеристика реальной прикладной значимости науки про "разрешимость" - точно также всем похер на неразрешимость языка С++ (убрать это было бы можно - но зачем?): нет - у нее как и у любой не вполне тривиальной маттеории есть приложения слабо связанные с той задачей на решение которой теория претендовала - но то уже отдельная тема.
*) хотя, замечу, даже несколько минут компиляции на одну такую строчку в реальном продакшене "разумным временем" особо не является - потому как оно конечно решит - но анноить будет постоянно.
Subscribe

Recent Posts from This Journal

  • От кармы не уйдешь

    Подумалось тут что Москва хоть и не входила формально в улус Джучи (АКА "Золотая Орда") по духу и культуре и роли в политике была вполне ордынской. А…

  • Это уже смешно:

    В Москве и области с 19 июля отменяется система QR-кодов для посещения ресторанов и кафе. В столице разрешили работу ночных клубов, баров и…

  • Это уже щедрин какой-ектто:

    Бибися про какой-то умучанный от кровавой гебни "Проект": Один из самых нашумевших материалов "Проекта" был посвящен акционеру банка "Россия"…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 60 comments

Recent Posts from This Journal

  • От кармы не уйдешь

    Подумалось тут что Москва хоть и не входила формально в улус Джучи (АКА "Золотая Орда") по духу и культуре и роли в политике была вполне ордынской. А…

  • Это уже смешно:

    В Москве и области с 19 июля отменяется система QR-кодов для посещения ресторанов и кафе. В столице разрешили работу ночных клубов, баров и…

  • Это уже щедрин какой-ектто:

    Бибися про какой-то умучанный от кровавой гебни "Проект": Один из самых нашумевших материалов "Проекта" был посвящен акционеру банка "Россия"…