Pesquisa e desafios abertos em Teoria da Linguagem de Programação

32

No espírito de algumas discussões gerais como esta , estou abrindo este tópico com a intenção de reunir opiniões sobre quais são os desafios em aberto e os tópicos mais importantes da pesquisa em linguagens de programação . Espero que a discussão possa trazer à tona opiniões sobre o futuro da pesquisa em linguagens de programação.

Acredito que esse tipo de discussão ajudará novos pesquisadores, como eu, interessados ​​em PL, bem como aqueles que já estão um pouco envolvidos.

bellpeace
fonte
7
wiki da comunidade?
Suresh Venkat
2
Eu acho que realmente melhoraria esta questão e quem responderia se você citasse ou resumisse o texto da pergunta "Fronteiras do TCS". O escopo esperado das respostas a esta pergunta não é claro, enquanto a outra pergunta é mais precisa sobre o que esperava.
Vijay D
quando fiz esta pergunta no stackoverflow há algum tempo ... recebi votos negativos e minha pergunta foi encerrada!
Rorschach

Respostas:

23

Penso que o objetivo geral da teoria de PL é reduzir o custo da programação em larga escala, melhorando as linguagens de programação e o ecossistema técnico em que as linguagens são usadas.

Aqui estão algumas descrições de alto nível, um tanto vagas das áreas de pesquisa de PL que receberam atenção constante e provavelmente continuarão a fazê-lo por um tempo.

  • A maioria das pesquisas em linguagem de programação foi feita no contexto da computação seqüencial e, até agora, discutimos discutivelmente um conjunto de recursos disponíveis na maioria das linguagens de programação modernas (por exemplo, funções de ordem superior, inferência (parcial) de tipos, correspondência de padrões , ADTs, polimorfismo paramétrico) e são bem compreendidos. Ainda não existe um consenso sobre os recursos da linguagem de programação para computação simultânea e paralela.

  • Relacionado ao ponto anterior, o campo de pesquisa de sistemas de digitação viu grande parte de sua atividade em computação seqüencial. Podemos generalizar este trabalho para encontrar disciplinas de digitação tratáveis ​​e úteis que restringem a computação simultânea e paralela?

  • Como um caso especial do ponto anterior, a correspondência de Curry-Howard relaciona a teoria da prova estrutural e a programação funcional, levando à transferência sustentada de tecnologia entre ciência da computação e (fundamentos da) matemática, com, por exemplo, a teoria do tipo de homotopia como um exemplo impressionante. Existem muitas dicas tentadoras que podem ser estendidas para (algumas formas de) computação simultânea e paralela.

  • A especificação e verificação de programas amadureceram muito nos últimos anos, por exemplo, com assistentes interativos de prova como Isabelle e Coq, mas a tecnologia ainda está longe de ser utilizável em larga escala na programação diária. Ainda há muito trabalho a ser feito para melhorar esse estado de coisas.

  • Linguagens de programação e tecnologia de verificação para novas formas de computação. Estou
    pensando aqui em particular na computação quântica e nos mecanismos computacionais de inspiração biológica, veja, por exemplo, aqui .

  • Unificação. Existem muitas abordagens para linguagens de programação, tipos, verificação, e às vezes se sente que há muita sobreposição entre elas e que há uma abordagem mais abstrata esperando para ser descoberta. Em particular, é provável que os mecanismos computacionais de inspiração biológica continuem nos dominando.

Um problema da pesquisa de PL é que não há problemas em aberto, como a questão P / NP, em que podemos dizer imediatamente se uma solução proposta funciona ou não.

Martin Berger
fonte
11
se posso acrescentar, computação quântica e linguagens de programação quântica, mesmo que a computação quântica não esteja acontecendo, o estudo de como alguns conceitos de programação podem ser transferidos nesse modelo de computação é interessante, se nada mais, programação em linguagem natural, programação difusa, e mesmo cálculo física de programação e física (a programação directamente na matéria, para além do nível molecular)
Nikos M.
11
@NikosM. Concordo, QC é um grande negócio e fortemente investigado. Este artigo mostra uma conexão surpreendente entre os fundamentos da mecânica quântica e a teoria da linguagem de programação, desenterrada apenas pela abstração.
Martin Berger
Bom, talvez uma pergunta poderia resolver esses tipos de relações formais (ou não formais)
Nikos M.
11

Deixe-me listar algumas suposições que limitam a pesquisa em linguagem de programação. É difícil evitar isso porque eles sentem que são uma parte essencial do que são as linguagens de programação ou porque explorar alternativas seria "não mais o design da linguagem de programação". Com cada suposição, listo seus efeitos limitantes.

  1. Programas são construções sintáticas.

    • Programadores reais nunca usariam iPads para construir código-fonte. E mesmo que o fizessem, nunca poderiam ser tão eficientes quanto no Emacs, Eclipse, NetBeans, XCode, etc.
    • A pesquisa de formas alternativas de construção de programas não é o design da linguagem de programação, mas o design da interface gráfica do usuário ou a educação (cf. Scratch).
  2. Um programa parcialmente gravado não pode ser executado.

    • No mínimo, o erro de tempo de execução ocorre quando a execução chega a uma parte ausente.
    • Que benefício poderia ter na execução de programas inacabados?
  3. Os programas são sobre dar instruções aos computadores.

    • O design da linguagem de programação não tem nada a dizer sobre como escrever e organizar leis. aparelhos.
    • As bactérias não escrevem programas.
  4. Programar é como criar e não pode ser feito por pessoas comuns.

    • As pessoas comuns não conhecem a sintaxe, os conceitos, as ferramentas, portanto não podem escrever programas.
    • Mesmo se tentarmos tornar possível que pessoas comuns escrevam programas, elas só poderão escrever coisas triviais.

Eu acho que poderia continuar.

Andrej Bauer
fonte
2
James: excelente, informarei minha tia. Martin: esse é precisamente o tipo de coisa que estou falando - a programação não-textual não foi estabelecida de maneira convincente porque a comunidade de PL não está levando isso a sério, porque não foi estabelecida de forma convincente. Mas parece-me bastante óbvio que os humanos não foram feitos para digitar palavras nas telas. Somos bons em jogar coisas e colher mirtilos.
Andrej Bauer
11
@AndrejBauer Como argumento científico, "é bastante óbvio para mim" não está além da melhoria. Se você olhar para a história dos sistemas de escrita, das quais as linguagens de programação são apenas um exemplo recente, sua trajetória histórica se afastou da escrita logográfica. Talvez nossa capacidade de analisar seqüências de caracteres seja mais relevante do que mirtilos. A escrita alfabética evoluiu ao longo de milênios, por isso é improvável que contenha erros enormes e facilmente corrigíveis. Dito isso, estou feliz em acreditar que podemos fazer melhor do que as strings lineares baseadas em ASCII. Eu acho que vai demorar um pouco antes de nós.
Martin Berger
11
O objetivo da minha resposta é "pensar fora da caixa". Examinar suposições ocultas na pesquisa em PL e ver como elas limitam o potencial da pesquisa em PL.
Andrej Bauer
4
@AndrejBauer, acho que limitar o escopo ao POPL é um erro - muito desse tipo de trabalho é feito no OOPSLA, ICSE ou CHI. O POPL não está interessado, a menos que haja uma nova abordagem formal, mas o POPL não é toda a comunidade de PL.
Sam Tobin-Hochstadt
2
@DominicMulligan: claro, essas são todas as idéias muito bem-vindas. Com meus comentários, estou tentando mudar a percepção do que é programação. Portanto, se as idéias teóricas puderem ser bem utilizadas na prática (com o que quero dizer que programadores "comuns" as usarão na vida cotidiana), então vencemos.
Andrej Bauer
0

Há um problema que tenho me perguntado. Não tenho idéia se isso se qualifica como um desafio aberto.

O conhecimento matemático tem crescido constantemente com o tempo. Os fundamentos teóricos, conceitos, notações e provas evoluíram ao longo dos séculos. Os matemáticos conseguiram a agregação sem necessariamente verificar sua consistência global de maneira sistemática e formal a qualquer momento (embora houvesse tentativas de fazê-lo).

Devemos esperar que as linguagens de programação e as bibliotecas de programas se agregem e evoluam de maneira semelhante ao longo do tempo. Que tipo de ferramentas poderia ajudar a gerenciar a agregação de resultados e bibliotecas de programação, a fim de mantê-los consistentes e efetivamente utilizáveis ​​por todos, pois os computadores podem ser mais formais e exigentes quanto à consistência. Temos que refazer as bibliotecas para cada nova linguagem de programação. Por que devemos escolher uma linguagem porque ela possui as bibliotecas corretas para o aplicativo pretendido, e não para suas qualidades intrínsecas como meio de programação?

Em um tópico diferente, você pode encontrar idéias na seguinte pergunta: As linguagens de programação estão se tornando mais como as linguagens naturais? Sei que a idéia pode não atrair muitos cientistas teóricos da computação, mas ainda pode ser útil analisando questões diferentes ou de um ponto de vista diferente. Estou longe de concordar com muitas das idéias postadas, mas é para isso que serve a discussão.

babou
fonte
A consistência é exagerada.
Andrej Bauer
11
Eu posso ver que não há muito acordo sobre essa sugestão, por mais modesta que seja. Ainda assim, pode ser mais útil, pelo menos para mim, ter algumas palavras explicativas sobre o porquê. Caso eu não estivesse clara, nunca quis dizer que a matemática poderia ser inconsistente, apenas que ela não era (necessariamente) agregada com meios consistentes (os historiadores diriam melhor). Do ponto de vista do CS, posso estar errado em relação à dificuldade de agregação (nunca fiz nenhum trabalho técnico sobre isso), mas estou apenas relacionando a experiência do usuário e o ponto de vista comumente ouvido, indiretamente prejudicial aos idiomas produzidos pelo TCS.
babou
11
Bem, minha observação é principalmente sobre o fato de que consistência é uma idéia de tudo ou nada, enquanto na realidade a maioria dos softwares é "quase sempre consistente". E, no entanto, usamos e achamos útil. Por que então os teóricos são obcecados com o que parece ser um conceito praticamente inatingível e idealista demais? Parece melhor poder quantificar a consistência de uma maneira menos trivial.
Andrej Bauer
@AndrejBauer - Obrigado por responder. Estou um pouco surpreso com a sua declaração, aplicada ao que escrevi. Nada ali suporta alguma forma de consistência absoluta, mas apenas um desejo de uma abordagem viável que tornasse a agregação possível e significativa em um contexto em evolução. Principalmente consistente como você diz, pode ser. Encontrar o que consistente deveria significar para o propósito fazia parte da ideia, e eu não estava sugerindo nenhuma resposta, trivial ou não. Nunca fui um teórico obcecado e não vejo pela sua resposta onde poderíamos estar em desacordo.
babou
11
Eu acho que estava apenas reclamando de "teóricos puros", só isso. Por favor, me ignore.
Andrej Bauer
0

houve uma tremenda inovação e explosão nas linguagens de programação dos lados teórico e aplicado ao longo do século passado; no entanto, pode-se argumentar que esse é um evento singular / único na história da computação, semelhante a uma "explosão evolutiva" (veja também "por que existem tantas linguagens de programação?" no cs.se) e, portanto, o futuro não será como o passado a esse respeito. no entanto, existem algumas tendências atuais de longo prazo identificáveis ​​em play / under development.

  • Complexidade de programação / software e as maneiras de gerenciar / minimizar / mitigar / reduzir é um tópico que sempre influenciou o design da linguagem e é possivelmente ainda mais significativo na era atual, com sistemas de software muito grandes / complexos bastante comuns. esse era um aspecto importante da lógica do projeto de OOP, mas agora temos sistemas de OOP altamente complexos! A ponderação focalizada levou a clássicos no campo, como o mítico mês-homem de Brooks, que de muitas maneiras ainda é uma perspectiva muito válida, possivelmente ainda mais relevante do que quando foi escrita.

  • paralelismo. há uma mudança no hardware em direção a um maior paralelismo (por exemplo, multicore etc) e o aumento da velocidade do clock não é mais suficiente para aumentar o desempenho. essa mudança ocorreu em meados da década de 2000 e está tendo uma grande influência na pesquisa / design de idiomas. o paralelismo sempre foi um tópico, mas tem uma nova proeminência / urgência: existe um amplo pensamento / consenso de que o paralelismo é excessivamente complicado e difícil na programação e talvez diferentes abordagens teóricas possam aliviar parte disso. uma boa referência a isso: O cenário da pesquisa em computação paralela: uma visão de Berkeley

  • datamining / big data . estes estão influenciando o design da linguagem de programação. Também novas direções na arquitetura do banco de dados estão afetando / impactando as linguagens de programação.

  • a supercomputação tem um impacto significativo no design da linguagem e também se sobrepõe ao paralelismo e datamining / big data, por exemplo, a novas linguagens como o MapReduce .

  • programação visual / fluxo de dados . houve um aumento nesses tipos de "linguagens" (em certo sentido, a programação visual está, de muitas maneiras, realmente desacoplar a programação das "linguagens"). também forte polinização cruzada com paralelismo.

  • AI . esse é mais um curinga de longo alcance e não está muito claro no momento como afetará as linguagens e a programação de computadores, mas provavelmente será muito substancial. no passado [de uma forma diferente], levava a idiomas inteiros como o prólogo . uma indicação inicial de como pode ser aplicada com resultados impressionantes é Algoritmos Genéticos / Programação Genética .

uma referência que pode ter algumas idéias úteis na linha do "futuro das linguagens de programação", Beyond Java by Tate. ele pondera (embora de forma controversa) que talvez o Java (indiscutivelmente uma das linguagens de programação mais sofisticadas / abrangentes existentes) esteja começando a mostrar sua idade e há sinais precoces de novas linguagens / abordagens surgindo para ocupar seu lugar a longo prazo.

vzn
fonte