Badania i otwarte wyzwania w teorii programowania języków

32

W duchu takich ogólnych dyskusji, jak ta , otwieram ten wątek z zamiarem zebrania opinii na temat otwartych wyzwań i gorących tematów w badaniach nad językami programowania . Mam nadzieję, że dyskusja może nawet ujawnić opinie na temat przyszłości badań w językach programowania.

Wierzę, że ten rodzaj dyskusji pomoże nowym badaczom-studentom, takim jak ja, zainteresowanym PL, a także tym, którzy są już nieco zaangażowani.

bellpeace
źródło
7
wiki społeczności?
Suresh Venkat
2
Myślę, że naprawdę poprawiłoby to pytanie i tych, którzy na nie odpowiedzieliby, gdyby zacytowali lub podsumowali tekst pytania „Frontiers of TCS”. Oczekiwany zakres odpowiedzi na to pytanie jest niejasny, natomiast drugie pytanie jest bardziej precyzyjne na temat tego, czego się spodziewało.
Vijay D
kiedy jakiś czas temu zadałem to pytanie przy przepływie stosów ... Mam negatywne opinie i moje pytanie zostało zamknięte!
Rorschach

Odpowiedzi:

23

Myślę, że ogólnym celem teorii PL jest obniżenie kosztów programowania na dużą skalę poprzez poprawę języków programowania i ekosystemu technicznego, w którym używane są języki.

Oto kilka ogólnych, nieco niejasnych opisów obszarów badawczych PL, na które zwrócono uwagę i prawdopodobnie będą to robić przez jakiś czas.

  • Większość badań nad językiem programowania została przeprowadzona w kontekście obliczeń sekwencyjnych i do tej pory zapewne skupiliśmy się na rdzeniu funkcji dostępnych w większości współczesnych języków programowania (np. Funkcje wyższego rzędu, wnioskowanie o typie (częściowe), dopasowanie wzorca , ADT, parametryczny polimorfizm) i są dobrze rozumiane. Jak dotąd nie ma takiego konsensusu w sprawie funkcji języka programowania do obliczeń równoległych i równoległych.

  • W odniesieniu do poprzedniego punktu, w dziedzinie badań nad systemami typowania większość działalności koncentrowała się na obliczeniach sekwencyjnych. Czy możemy uogólnić tę pracę w celu znalezienia praktycznych i przydatnych dyscyplin pisania, które ograniczą równoczesne i równoległe obliczenia?

  • Jako szczególny przypadek z poprzedniego punktu, korespondencja Curry'ego-Howarda dotyczy teorii dowodu strukturalnego i programowania funkcjonalnego, prowadząc do trwałego transferu technologii między informatyką i (podstawami) matematyki, na przykład imponującą teorię typu homotopii. Istnieje wiele kuszących wskazówek, które można rozszerzyć na (niektóre formy) obliczeń współbieżnych i równoległych.

  • Specyfikacja i weryfikacja programów bardzo się rozwinęły w ostatnich latach, np. Z interaktywnymi asystentami dowodowymi, takimi jak Isabelle i Coq, ale technologia ta wciąż jest daleka od możliwości zastosowania na dużą skalę w codziennym programowaniu. Wciąż jest wiele do zrobienia, aby poprawić ten stan rzeczy.

  • Języki programowania i technologia weryfikacji dla nowych form obliczeń. Myślę
    tu w szczególności o obliczeniach kwantowych i biologicznych mechanizmach obliczeniowych, patrz np . Tutaj .

  • Zjednoczenie. Istnieje wiele podejść do języków programowania, typów, weryfikacji, a czasem wydaje się, że zachodzi na siebie wiele nakładek i że istnieje jeszcze bardziej abstrakcyjne podejście, które czeka na odkrycie. W szczególności, mechanizmy obliczeniowe inspirowane biologicznie prawdopodobnie nadal nas przytłaczają.

Jednym z problemów badań PL jest to, że nie ma jednoznacznych otwartych problemów, takich jak pytanie P / NP, w których możemy od razu stwierdzić, czy proponowane rozwiązanie działa, czy nie.

Martin Berger
źródło
1
jeśli mogę dodać, obliczenia kwantowe i języki programowania kwantowego, nawet jeśli obliczenia kwantowe nie mają miejsca, to badanie tego, w jaki sposób można przekazać niektóre koncepcje programowania w tym modelu obliczeniowym, jest interesujące, jeśli nic innego, programowanie w języku naturalnym, programowanie rozmyte, a nawet obliczenia fizyczne i programowanie fizyczne (programowanie bezpośrednio na materii, poza poziomem molekularnym)
Nikos M.
1
@NikosM. Zgadzam się, że QC to wielka sprawa i dokładnie zbadana. Ten artykuł pokazuje zaskakujący związek między podstawami mechaniki kwantowej a teorią języka programowania, odkrytą jedynie przez abstrakcję.
Martin Berger,
Fajnie, może pytanie mogłoby dotyczyć tego rodzaju formalnych (lub nieformalnych) relacji
Nikos M.
11

Pozwól mi wymienić kilka założeń, które ograniczają badania nad językiem programowania. Trudno jest oderwać się od nich, ponieważ czują, że są istotną częścią języków programowania lub dlatego, że odkrywanie alternatyw nie byłoby już „projektowaniem języka programowania”. Przy każdym założeniu wymieniam jego ograniczenia.

  1. Programy są konstrukcjami składniowymi.

    • Prawdziwi programiści nigdy nie używaliby iPadów do konstruowania kodu źródłowego. A nawet gdyby tak było, nigdy nie byłyby tak wydajne, jak Emacs, Eclipse, NetBeans, XCode itp.
    • Badania nad alternatywnymi sposobami konstruowania programów nie obejmują programowania języka programowania, ale graficznego interfejsu użytkownika lub edukacji (por. Scratch).
  2. Częściowo napisany program nie może zostać wykonany.

    • Przynajmniej błąd czasu wykonywania występuje, gdy wykonanie przechodzi do brakującej części.
    • Jakie korzyści może mieć prowadzenie niedokończonych programów?
  3. Programy polegają na udzielaniu instrukcji komputerom.

    • Projektowanie języka programowania nie ma nic do powiedzenia na temat pisania i organizowania przepisów. urządzenia.
    • Bakterie nie piszą programów.
  4. Programowanie jest jak inżynieria i nie może być wykonywane przez zwykłych ludzi.

    • Zwykli ludzie nie znają składni, pojęć, narzędzi, więc nie mogą pisać programów.
    • Nawet jeśli spróbujemy umożliwić zwykłym ludziom pisanie programów, będą oni mogli pisać tylko trywialne rzeczy.

Myślę, że mógłbym kontynuować.

Andrej Bauer
źródło
2
James: doskonale, poinformuję ciotkę. Martin: Właśnie o tym mówię - programowanie nietekstowe nie zostało przekonująco ustanowione, ponieważ społeczność PL nie traktuje tego poważnie, ponieważ nie zostało przekonująco ustalone. Wydaje mi się jednak oczywiste, że ludzie nie zostali stworzeni do pisania słów na ekranach. Jesteśmy dobrzy w rzucaniu i zbieraniu jagód.
Andrej Bauer
1
@AndrejBauer Jako naukowy argument, „To dla mnie całkiem oczywiste” nie podlega żadnej poprawie. Jeśli spojrzysz na historię systemów pisania, których języki programowania są tylko najnowszym przykładem, ich trajektoria historyczna była daleka od pisania logistycznego. Może nasza zdolność do parsowania łańcuchów jest ważniejsza niż jagody. Pisanie alfabetyczne ewoluowało przez tysiąclecia, więc jest mało prawdopodobne, że zawiera masywne, łatwe do naprawienia błędy. To powiedziawszy, cieszę się, że możemy lepiej niż ciągi liniowe oparte na ASCII. Myślę, że minie trochę czasu, zanim to zrobimy.
Martin Berger,
1
Celem mojej odpowiedzi jest „myśleć nieszablonowo”. Aby zbadać ukryte założenia w badaniach PL i zobaczyć, jak ograniczają potencjalne badania PL.
Andrej Bauer
4
@AndrejBauer, I think limiting the scope to POPL is a mistake -- lots of this kind of work is done at OOPSLA, or at ICSE, or even at CHI. POPL isn't interested unless there's a novel formal approach, but POPL isn't the whole PL community.
Sam Tobin-Hochstadt
2
@DominicMulligan: sure, these are all very welcome ideas. With my comments I am trying to change the perception of what programming is. So if the theoretical ideas can be put to good use in practice (by which I mean that "ordinary" programmers will use them in daily life), then we have won.
Andrej Bauer
0

There is one problem I have been wondering about. I have no idea whether it qualifies as an open challenge.

Wiedza matematyczna stale rośnie z czasem. Teoretyczne podstawy, koncepcje, zapisy i dowody ewoluowały na przestrzeni wieków. Matematycy zarządzali agregacją, niekoniecznie sprawdzając jej globalną spójność w systematyczny i formalny sposób w dowolnym momencie (choć próbowano to zrobić).

We should expect programming languages and program libraries to aggregate and evolve similarly over the time. What kind of tools could help manage aggregation of programming results and libraries so as to keep them consistent and effectively usable by all, as computers can be more formal and demanding regarding consistency. Do we have to redo the libraries for each new programming language. Why should we have to choose a language because it has the right libraries for the intended application rather than for its intrinsic qualities as a programming medium?

On a different topic, you might find ideas in the following question: Are programming languages becoming more like natural languages? I realize that the idea may not appeal to many theoretical computer scientists, but it may still be useful by looking at different issues or from a different point of view. I am far from agreeing with many of the ideas that were posted, but that is what discussion is for.

babou
źródło
Concistency is over-reated.
Andrej Bauer
1
I can see there is not much agreement on this, however modest, suggestion. Still, it might be more helpful, at least to me, to have a few explanatory words as to why. In case I was unclear, I never meant to say that mathematics could be inconsistent, only that it was not (necessarily) aggregated with consistent means (historians would tell better). From a CS point of view, I may be wrong regarding the difficulty of aggregation (I never did any technical work on this), but I am only relating user experience and commonly heard point of view, indirectly detrimental to languages produced by TCS.
babou
1
Well, my remark is mostly about the fact that consistency is an all-or-nothing idea, whereas in reality most software is "mostly consistent". And yet we use it and find it useful. Why then are theoreticians obsessed with what seems to be a practically unattainable and too idealistic a concept? It would seem better to be able to quantify consistency in some less trivial way.
Andrej Bauer
@AndrejBauer - Thank you for replying. I am a bit surprised by your statement, as applied to what I wrote. Nothing there supports some form of absolute consistency, but only a wish for some workable approach that would make aggregation possible and meaningful in an evolving context. Mostly consistent as you say, might do. Finding what consistent should mean for the purpose was part of the idea, and I was not suggesting any answer, trivial or otherwise. I have never been an obsessed theoretician, and I do not see from your answer where we could be at odds.
babou
1
I think I was just ranting about "pure theoreticians", that's all. Please ignore me.
Andrej Bauer
0

there has been a tremendous innovation and explosion in programming languages from applied and theoretical sides over the last century, yet a case might be made that this is a singular/one-time event in the history of computing, similar to an "evolutionary explosion" (see also "why are there so many programming languages?" on cs.se), and that therefore the future will not be like the past in this respect. however there are some identifiable long-range current trends in play/under development.

  • Programming/software complexity and ways of managing/minimizing/mitigating/reducing it is a topic that has always influenced language design and is possibly even more significant in the current age with very large/complex software systems quite common. it was a major aspect of OOP design rationale yet now we have highly complex OOP systems! focused pondering of it has led to classics in the field such as Mythical man-month by Brooks which in many ways is still a very valid perspective, possibly even more relevant than when it was written.

  • parallelism. there is a shift in hardware toward greater parallelism (eg multicore etc) and clock speed increases are no longer sufficient to increase performance. this shift happened around the mid 2000s and is having a major influence on language research/design. parallelism was always a topic but it has a new foremost prominence/urgency, and there is some widespread thinking/consensus that parallelism is overly complicated and difficult in programming and maybe different theoretical approaches could alleviate some of this. a nice ref on this: The Landscape of Parallel Computing Research: A View from Berkeley

  • datamining/big data. these are influencing programming language design. also new directions in database architecture are rippling/impacting programming languages.

  • supercomputing has a significant impact on language design and also overlaps with parallelism and datamining/big data eg with new languages like MapReduce.

  • visual/dataflow programming. there has been an increase in these types of "languages" (in a sense visual programming is in many ways actually decoupling programming from "languages"). also strong cross-pollination with parallelism.

  • AI. this is more of a longrange wildcard and its not very clear right now how it will impact computer languages and programming but its probably going to be very substantial. in the past [in a different form] it led to entire languages like prolog. an early indication of how it can be applied with striking results is Genetic Algorithms/Genetic Programming.

a reference that might have some helpful ideas along the lines of "future of programming languages", Beyond Java by Tate. he ponders (albeit controversially) that maybe Java (arguably one of the most sophisticated/comprehensive programming languages in existence) is starting to show its age and there are early signs of new languages/approaches emerging to fill in its place in the long term.

vzn
źródło