Исследования и открытые проблемы в теории языка программирования

32

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

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

колокольня
источник
7
сообщество вики?
Суреш Венкат
2
Я думаю, что это действительно улучшит этот вопрос и тех, кто на него ответит, если вы процитируете или суммируете текст вопроса «Границы TCS». Ожидаемый объем ответов на этот вопрос неясен, в то время как другой вопрос является более точным относительно того, что он ожидал.
Виджай Д
когда я задал этот вопрос на stackoverflow некоторое время назад ... я получил отрицательные голоса, и мой вопрос был закрыт!
Роршах

Ответы:

23

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

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

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

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

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

  • Спецификация и проверка программ в последние годы значительно выросли, например, с помощью интерактивных помощников по проверке, таких как Изабель и Кок, но технология все еще далека от того, чтобы ее можно было использовать в широком масштабе в повседневном программировании. Еще многое предстоит сделать, чтобы улучшить это положение дел.

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

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

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

Мартин Бергер
источник
1
если я могу добавить, квантовые вычисления и квантовые языки программирования, даже если квантовые вычисления не происходят, но изучение того, как некоторые концепции программирования могут быть перенесены в эту модель вычислений, интересно, если ничего другого, программирование на естественном языке, нечеткое программирование, и даже физические вычисления и физическое программирование (программирование непосредственно на материю, за пределами молекулярного уровня)
Никос М.
1
@NikosM. Я согласен, КК имеет большое значение и тщательно расследуется. Эта статья демонстрирует удивительную связь между основами квантовой механики и теорией языка программирования, обнаруженную только посредством абстракции.
Мартин Бергер
Хорошо, может быть, вопрос может касаться таких формальных (или не формальных) отношений
Никос М.
11

Позвольте мне перечислить некоторые предположения, которые ограничивают исследование языка программирования. С ними трудно оторваться, потому что они чувствуют, что являются неотъемлемой частью того, о чем говорят языки программирования, или потому что исследование альтернатив будет «больше не проектированием языка программирования». С каждым допущением я перечисляю его ограничивающие эффекты.

  1. Программы являются синтаксическими конструкциями.

    • Настоящие программисты никогда не использовали бы iPad для создания исходного кода. И даже если бы они это сделали, они никогда не могли бы быть такими эффективными, как с Emacs, Eclipse, NetBeans, XCode и т. Д.
    • Исследование альтернативных способов конструирования программ - это не дизайн языка программирования, а либо графический дизайн пользовательского интерфейса, либо образование (ср. Scratch).
  2. Частично написанная программа не может быть выполнена.

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

    • Языковой дизайн программирования ничего не говорит о том, как писать и организовывать законы. apliances.
    • Бактерии не пишут программы.
  4. Программирование - это как инжиниринг, и оно не может быть сделано обычными людьми.

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

Я думаю, что я мог бы продолжить.

Андрей Бауэр
источник
2
Джеймс: отлично, я сообщу своей тете. Мартин: это именно то, о чем я говорю - нетекстовое программирование не было убедительно установлено, потому что сообщество PL не воспринимает это всерьез, потому что оно не было убедительно установлено. Но мне кажется совершенно очевидным, что люди не созданы для того, чтобы печатать слова на экранах. Мы хорошо разбрасываем вещи и собираем чернику.
Андрей Бауэр
1
@AndrejBauer Как научный аргумент, «это совершенно очевидно для меня» не выходит за рамки улучшения. Если вы посмотрите на историю систем письма, из которых языки программирования являются лишь недавним примером, их историческая траектория была далека от логографического письма. Может быть, наша способность разбирать строки более актуальна, чем черника. Буквенное письмо развивалось на протяжении тысячелетий, поэтому маловероятно, что оно содержит массивные, легко исправляемые ошибки. Тем не менее, я рад, что мы можем добиться большего успеха, чем линейные строки на основе ASCII. Думаю, пройдет немного времени, прежде чем мы это сделаем.
Мартин Бергер
1
Суть моего ответа - «мыслить нестандартно». Изучить скрытые предположения в исследовании ЛП и увидеть, как они ограничивают потенциальные возможности исследования ЛП.
Андрей Бауэр
4
@AndrejBauer, я думаю, что ограничивать область применения POPL - ошибка - большая часть такого рода работы выполняется в OOPSLA, ICSE или даже в CHI. POPL не заинтересован, если нет нового формального подхода, но POPL - это не все сообщество PL.
Сэм Тобин-Хохштадт
2
@DominicMulligan: конечно, это все очень полезные идеи. Своими комментариями я пытаюсь изменить восприятие программирования. Таким образом, если теоретические идеи могут найти хорошее применение на практике (я имею в виду, что «обычные» программисты будут использовать их в повседневной жизни), то мы победили.
Андрей Бауэр
0

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

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

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

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

Babou
источник
Согласованность переоценена.
Андрей Бауэр
1
Я вижу, что по этому, хотя и скромному, предложению нет особого согласия. Тем не менее, было бы более полезно, по крайней мере для меня, иметь несколько объяснительных слов о том, почему. В случае, если мне было неясно, я никогда не хотел сказать, что математика может быть противоречивой, только то, что она не (обязательно) объединяется с непротиворечивыми средствами (историки скажут лучше). С точки зрения CS, я могу ошибаться в отношении сложности агрегации (я никогда не занимался какой-либо технической работой над этим), но я имею в виду только взаимодействие с пользователем и общепризнанную точку зрения, косвенно вредную для языков, создаваемых TCS.
Бабу
1
Что ж, мое замечание касается главным образом того факта, что согласованность является идеей «все или ничего», тогда как в действительности большинство программных продуктов «в основном согласованно». И все же мы используем это и находим это полезным. Почему же тогда теоретики одержимы идеей, которая кажется практически недостижимой и слишком идеалистической? Казалось бы, лучше иметь возможность количественно оценить последовательность менее тривиальным способом.
Андрей Бауэр
@AndrejBauer - Спасибо, что ответили. Я немного удивлен вашим заявлением применительно к тому, что я написал. Ничто из этого не поддерживает какую-то форму абсолютной согласованности, а лишь пожелание какого-либо работоспособного подхода, который сделал бы агрегирование возможным и значимым в развивающемся контексте. В основном последовательный, как вы говорите, может сделать. Нахождение того, что последовательно должно означать для этой цели, было частью идеи, и я не предлагал никакого ответа, тривиального или иного. Я никогда не был одержимым теоретиком, и я не вижу из твоего ответа, где мы можем быть в ссоре.
Бабу
1
Я думаю, что я просто разглагольствовал о "чистых теоретиках", вот и все. Пожалуйста, игнорируйте меня.
Андрей Бауэр
0

за последнее столетие произошли огромные инновации и взрыв в языках программирования с прикладной и теоретической сторон, однако можно было бы доказать, что это единичное / разовое событие в истории вычислительной техники, подобное "эволюционному взрыву" (см. также «Почему так много языков программирования?» на cs.se), и поэтому будущее в этом отношении не будет таким, как прошлое. однако есть некоторые идентифицируемые долгосрочные текущие тенденции в разработке / разработке.

  • Сложность программирования / программного обеспечения и способы управления / минимизации / смягчения / уменьшения - это тема, которая всегда влияла на дизайн языка и, возможно, даже более значима в нынешнем веке, когда очень большие / сложные программные системы встречаются довольно часто. это было основным аспектом обоснования проектирования ООП, но теперь у нас очень сложные системы ООП! сосредоточенное размышление об этом привело к классике в области, такой как Мифический человеко-месяц Бруксом, который во многих отношениях все еще является очень важной перспективой, возможно, даже более актуальной, чем когда она была написана.

  • параллелизм. происходит смещение аппаратного обеспечения в сторону большего параллелизма (например, многоядерности и т. д.), и увеличения тактовой частоты уже недостаточно для повышения производительности. этот сдвиг произошел примерно в середине 2000-х годов и оказывает большое влияние на исследования / дизайн языка. Параллелизм всегда был темой, но он имеет новую приоритетность / срочность, и существует широко распространенное мнение / консенсус, что параллелизм слишком сложен и труден в программировании, и, возможно, различные теоретические подходы могут смягчить некоторые из них. хороший рефлекс по этому вопросу: исследование параллельных вычислений: взгляд из Беркли

  • обработка данных / большие данные . они влияют на дизайн языка программирования. Кроме того, новые направления в архитектуре баз данных влияют на языки программирования.

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

  • визуальное / потоковое программирование . возросло число этих типов «языков» (в некотором смысле визуальное программирование во многих отношениях фактически отделяет программирование от «языков»). также сильное перекрестное опыление с параллелизмом.

  • AI . это более дальний подстановочный знак, и сейчас не очень понятно, как это повлияет на компьютерные языки и программирование, но, вероятно, оно будет очень существенным. в прошлом [в другой форме] это приводило к целым языкам, таким как пролог . Ранним признаком того, как его можно применять с поразительными результатами, является Генетические алгоритмы / Генетическое программирование .

ссылка, которая может иметь некоторые полезные идеи в духе «будущего языков программирования», Beyond Java by Tate. он размышляет (хотя и спорные) , что может быть Java (возможно , один из самых сложных / комплексных языков программирования в наличии) начинает показывать свой возраст , и есть первые признаки новых языков / подходы , возникающие заполнить его место в долгосрочной перспективе.

оборота взн
источник