Programação Funcional e Computação Científica

Peço desculpas se esta é uma pergunta vaga, mas aqui vai:

Nos últimos anos, a programação funcional recebeu muita atenção na comunidade de Engenharia de Software. Muitos começaram a usar linguagens como Scala e Haskell e reivindicaram sucesso em relação a outras linguagens e paradigmas de programação. Minha pergunta é: como especialistas em computação de alto desempenho / computação científica, deveríamos estar interessados ​​em programação funcional? Deveríamos estar participando dessa mini-revolução?

Quais são os prós e os contras da programação funcional no domínio de trabalho SciComp?

Eu fiz apenas um pouco de programação funcional, então, leve essa resposta com um pouco de sal.

Prós:

• A programação funcional parece muito matemática; é um bom paradigma para expressar alguns conceitos matemáticos
• Existem boas bibliotecas disponíveis para verificação formal de programas e prova de teoremas, por isso é possível escrever programas que raciocinem sobre programas - esse aspecto é bom para a reprodutibilidade
• Você pode fazer programação funcional em Python e C ++ através de expressões lambda; você também pode fazer programação funcional no Julia e no Mathematica
• Muitas pessoas não o usam, então você pode ser pioneiro. Assim como houve os primeiros adotantes do MATLAB, Python, R e agora Julia, é preciso haver os primeiros adotantes da programação funcional para que ela entenda

Contras:

• As linguagens que normalmente são consideradas linguagens de programação funcional, como Haskell, OCaml (e outros dialetos ML) e Lisp são geralmente consideradas lentas em relação às linguagens usadas para computação científica com desempenho crítico. OCaml é, na melhor das hipóteses, cerca de metade da velocidade de C.
• Essas linguagens carecem de infraestrutura de biblioteca em comparação com as linguagens comumente usadas na ciência computacional (Fortran, C, C ++, Python); se você deseja resolver um PDE, é muito mais fácil fazê-lo em uma linguagem mais comumente usada na ciência computacional do que em uma que não é.
• Não existe uma comunidade científica de computação usando linguagens de programação funcionais, assim como linguagens procedurais, o que significa que você não terá muita ajuda para aprendê-lo ou depurá-lo, e as pessoas provavelmente vão lhe dar uma porcaria por usá-lo (se você merece ou não)
• O estilo da programação funcional é diferente do estilo usado na programação procedural, normalmente ensinada nas aulas introdutórias de ciência da computação e nas classes do tipo "MATLAB para cientistas e engenheiros"

Eu acho que muitas das objeções na seção "Contras" poderiam ser superadas. Como é um ponto de discussão comum neste site do Stack Exchange, o tempo do desenvolvedor é mais importante que o tempo de execução. Mesmo que as linguagens de programação funcionais sejam lentas, se partes de desempenho crítico podem ser delegadas para uma linguagem processual mais rápida e se os ganhos de produtividade puderem ser demonstrados através do rápido desenvolvimento de aplicativos, vale a pena usá-los. Vale a pena notar aqui que os programas implementados em Python puro, MATLAB puro e R puro são consideravelmente mais lentos que as implementações desses mesmos programas em C, C ++ ou Fortran. Idiomas como Python, MATLAB e R são populares exatamente porque trocam velocidade de execução por produtividade e, mesmo assim, O Python e o MATLAB possuem recursos para implementar interfaces para código compilado em C ou C ++, para que códigos críticos de desempenho possam ser implementados para serem executados rapidamente. A maioria das linguagens possui uma interface de função estrangeira para C, o que seria suficiente para interagir com a maioria das bibliotecas de interesse dos cientistas da computação.

Você deveria estar interessado em programação funcional?

Tudo depende do que você acha legal. Se você é o tipo de pessoa que está disposta a reverter uma convenção e está disposta a evangelizar para as pessoas as virtudes do que quer que você queira fazer com a programação funcional, eu diria que vá em frente . Eu adoraria ver as pessoas fazerem coisas legais com a programação funcional na ciência da computação, por nenhuma outra razão senão provar que todos os pessimistas estão errados (e haverá muitos pessimistas). Se você não é o tipo de pessoa que quer lidar com várias pessoas perguntando: "Por que diabos você está usando uma linguagem de programação funcional em vez de (insira a linguagem de programação processual favorita aqui)?", Então eu não faria isso. não se preocupe.

Tem havido algum uso de linguagens de programação funcionais para trabalhos intensivos em simulação. A empresa de negociação quantitativa Jane Street usa o OCaml para modelagem financeira e execução de suas estratégias de negociação. O OCaml também foi usado no FFTW para gerar algum código C usado na biblioteca. Liszt é uma linguagem específica de domínio desenvolvida em Stanford e implementada no Scala usada para resolver PDEs. A programação funcional é definitivamente usada na indústria (não necessariamente na ciência computacional); resta saber se ele decolará na ciência da computação.

Talvez eu tenha uma perspectiva única disso, porque sou um profissional de HPC com formação científica em computação e também um usuário de linguagem de programação funcional. Não quero equiparar HPC à computação científica, mas há uma interseção considerável, e esse é o ponto de vista que tomo para responder a isso.

É improvável que os idiomas funcionais sejam adotados no HPC no momento, principalmente porque os usuários e clientes do HPC se preocupam genuinamente em atingir o mais próximo possível do desempenho máximo. É verdade que, quando o código é escrito de uma maneira funcional, ele naturalmente expõe o paralelismo que pode ser explorado, mas o HPC não é suficiente. O paralelismo é apenas uma peça do quebra-cabeça na obtenção de alto desempenho; você também deve levar em consideração uma ampla variedade de detalhes de microarquitetura, e isso geralmente requer um controle muito refinado da execução do código, que não está disponível em nenhum linguagens funcionais que eu conheço.

Dito isto, tenho grandes esperanças de que isso possa mudar. Percebi uma tendência de que os pesquisadores estão começando a perceber que muitas dessas otimizações de microarquitetura podem ser automatizadas (até certo ponto). Isso criou um zoológico de tecnologia de compilador fonte a fonte, em que um usuário insere uma "especificação" da computação que deseja que aconteça, e o compilador gera código C ou Fortran, que realiza essa computação com as otimizações e paralelismo necessários para eficientemente use a arquitetura de destino. Aliás, é para isso que as linguagens funcionais estão bem adaptadas: modelagem e análise de linguagens de programação. Não é por acaso que os primeiros grandes adotantes de linguagens funcionais foram os desenvolvedores de compiladores. Com algumas exceções notáveis, ainda não vi isso acontecer, mas as idéias estão lá,

Gostaria de acrescentar um aspecto às outras duas respostas. Além do ecossistema, a programação funcional oferece uma grande oportunidade para execução paralela, como multithreading ou computação distribuída. Suas propriedades inerentes de imutabilidade o tornam adequado para o paralelismo, que geralmente é uma verdadeira dor de cabeça quando se trata de linguagens imperativas.

Como a melhoria no desempenho do hardware nos últimos anos tem se concentrado em adicionar núcleos aos processadores, em vez de aumentar as frequências mais altas, a computação paralela está ficando muito mais popular (aposto que todos sabem disso).

Outra coisa que Geoff menciona é que o tempo do desenvolvedor geralmente é mais importante que o tempo de execução. Eu trabalho para uma empresa que constrói um SaaS intensivo em termos de computação e fizemos um teste de desempenho inicial ao iniciar, colocando C ++ vs Java. Descobrimos que o C ++ forneceu um corte de aproximadamente 50% no tempo de execução em Java (isso era para geometria computacional e os números provavelmente variarão dependendo do aplicativo), mas seguimos o Java de qualquer maneira devido à importância do tempo do desenvolvedor e esperávamos que otimizações e futuras melhorias no desempenho do hardware nos ajudariam a chegar ao mercado. Posso dizer com confiança que, se tivéssemos escolhido o contrário, ainda não estaríamos nos negócios.

Ok, mas Java não é uma linguagem de programação funcional, então o que isso tem a ver com qualquer coisa, você pode perguntar. Bem, mais tarde, quando empregamos mais defensores do paradigma funcional e tropeçamos na necessidade de paralelização, migramos progressivamente partes do nosso sistema para o Scala, que combina os aspectos positivos da programação funcional com o poder do imperativo e combina bem com Java. Isso nos ajudou tremendamente ao aumentar o desempenho do nosso sistema com um mínimo de dor de cabeça e provavelmente continuará a colher benefícios de outros aumentos de desempenho nos negócios de hardware, quando mais núcleos estiverem sobrecarregados nos processadores de amanhã.

Observe que concordo totalmente com os contras mencionados nas outras respostas, mas pensei que a facilitação da execução paralela é um profissional tão poderoso que não poderia deixar de ser mencionado.

Geoff já deu uma boa visão geral das razões pelas quais pouco acrescento além de enfatizar um de seus pontos: ecossistema. Independentemente de você estar defendendo a programação funcional ou qualquer outro paradigma, uma das questões importantes a serem abordadas é que existe uma quantidade incrível de software que todos os outros podem desenvolver e que precisam ser reescritos. Os exemplos são MPI, PETSc ou Trilinos para álgebra linear ou qualquer uma das bibliotecas de elementos finitos - todas escritas em C ou C ++. Existe uma grande quantidade de inércia no sistema, talvez não porque todos pensem que C / C ++ é de fato a melhor linguagem para se escrever software computacional, mas porque muitas pessoas passaram anos de suas vidas criando algo útil para muitas pessoas.

Eu acho que a maioria das pessoas computacionais concorda que há muito valor em experimentar novas linguagens de programação e avaliar sua adequação a esse problema. Mas será um momento difícil e solitário, porque você não poderá produzir resultados competitivos com o que todo mundo está fazendo. Também pode gerar uma reputação de alguém que iniciou a próxima mudança para um paradigma de programação diferente. Ei, levou apenas C ++ cerca de 15 anos para substituir o Fortran!

O resumo rápido é que

1. A computação numérica usa mutabilidade / efeitos colaterais para alcançar a maioria de suas acelerações e reduzir alocações (muitas estruturas de programação funcional possuem dados imutáveis)
2. A avaliação preguiçosa pode ser difícil de usar com códigos numéricos.
3. Ou você está desenvolvendo um pacote em que a queda nos níveis mais baixos de desempenho realmente importa (C / Fortran ou agora Julia) (neles você também pode editar o código do assembler conforme necessário) ou está escrevendo um script que usa essas bibliotecas rápidas então você costuma se preocupar com o tempo de desenvolvimento (e escolhe Julia / MATLAB / Python / R). As linguagens funcionais tendem a ficar em um meio termo estranho, que é útil em outras disciplinas, mas não é tão útil aqui.
4. A maioria dos algoritmos numéricos para equações diferenciais, otimização, álgebra linear numérica etc. é escrita / desenvolvida / comprovada em termos de convergência, ou seja, você tem uma aproximação e deseja obter . O estilo natural para implementar esses algoritmos é um loop. (Existem alguns algoritmos escritos recursivamente como alguns algoritmos multigrid, mas estes são muito mais raros.)x n + $x_n$$x_{n+1}$

Esses fatos juntos fazem com que a programação funcional não pareça necessária para a maioria dos usuários.

Eu acho interessante notar que o uso da programação funcional em Ciência da Computação não é novo. Por exemplo, este artigo de 1990 mostrou como melhorar o desempenho de programas numéricos escritos em Lisp (possivelmente a primeira linguagem de programação funcional) usando avaliação parcial. Este trabalho fez parte de uma cadeia de ferramentas usada em um artigo de 1992 por GJ Sussman (da SICP fame) e J Wisdom, que forneceu evidências numéricas do comportamento caótico do Sistema Solar . Mais detalhes sobre o hardware e o software envolvidos nesse cálculo podem ser encontrados aqui .

R é uma linguagem funcional e também uma estatística (e agora Machine Learning) e, na verdade, a linguagem número 1 para estatísticas. Porém, não é uma linguagem HPC: não é usada para "processamento de números" tradicional, como simulações de física etc. Mas pode ser executada em clusters maciços (por exemplo, via MPI) para simulações estatísticas maciças (MCMC) de aprendizado de máquina.

O Mathematica também é uma linguagem funcional, mas seu domínio principal é a computação simbólica, e não a computação numérica.

Em Julia, você também pode programar em um estilo funcional (próximo ao procedural e ao sabor de OO (multi-despacho)), mas não é puro (as estruturas de dados base são todas mutáveis ​​(exceto as tuplas), embora existam algumas bibliotecas com imutável estruturas de dados funcionais.Mais importante, é muito mais lento que o estilo processual, portanto não é muito usado.

Eu não chamaria Scala de uma linguagem funcional, mas de um híbrido objeto-funcional. Você pode usar muitos conceitos funcionais no Scala. O Scala é importante para a computação em nuvem por causa do Spark ( https://spark.apache.org/ ).

Observe que o Fortran moderno possui alguns elementos de programação funcional: possui uma semântica estrita de ponteiro (ao contrário de C), você pode ter funções puras (sem efeito colateral) (e marcar como tal) e pode ter imutabilidade. Possui até indexação inteligente, onde é possível especificar condições para os índices da matriz. Isso é semelhante a uma consulta e normalmente é encontrado apenas em linguagem de alto nível como R do LINQ em C # ou através de funções de filtro de ordem superior em linguagens funcionais. Portanto, o Fortran não é tão ruim assim, ele tem alguns recursos bastante modernos (por exemplo, co-matrizes) que não são encontrados em muitos idiomas. De fato, nas versões futuras do Fortran, prefiro ver mais recursos funcionais adicionados do que os recursos OO (o que agora é geralmente o caso), porque o OO no Fortran é realmente estranho e feio.

Os profissionais são as "ferramentas" incorporadas a cada linguagem funcional: é tão fácil filtrar dados, é tão fácil iterar sobre os dados e é muito mais fácil encontrar uma solução clara e concisa para seus problemas.

A única desvantagem é que você precisa entender esse novo tipo de pensamento: pode levar algum tempo para aprender o que você precisa saber. Outros no domínio SciComp realmente não usam esses idiomas, o que significa que você não pode obter tanto suporte :(

Se você está interessado em linguagens científicas funcionais, desenvolvi uma https://ac1235.github.io

Aqui estão meus argumentos sobre por que a programação funcional pode e deve ser utilizada para a ciência da computação. Os benefícios são vastos e os contras estão desaparecendo rapidamente. Na minha opinião, há apenas um golpe:

Con : falta de suporte ao idioma em C / C ++ / Fortran

Pelo menos em C ++, esse golpe está desaparecendo - pois o C ++ 14/17 adicionou recursos poderosos para oferecer suporte à programação funcional. Você pode precisar escrever algum código de biblioteca / suporte, mas o idioma será seu amigo. Como exemplo, aqui está uma biblioteca (warning: plug) que faz matrizes multidimensionais imutáveis ​​em C ++: https://github.com/jzrake/ndarray-v2 .

Além disso, aqui está um link para um bom livro sobre programação funcional em C ++, embora não esteja focado em aplicativos científicos.

Aqui está o meu resumo do que acredito ser o profissional:

Prós :

• Correção
• Compreensibilidade
• atuação

Em termos de correção , os programas funcionais são manifestamente bem colocados : forçam você a definir adequadamente o estado mínimo de suas variáveis ​​físicas e a função que avança esse estado no tempo:

int main()
{
    auto state = initial_condition();

    while (should_continue(state))
    {
        state = advance(state);
        side_effects(state);
    }
    return 0;
}

Resolver uma equação diferencial parcial (ou ODE) é perfeita para programação funcional; você está apenas aplicando uma função pura ( advance) à solução atual para gerar a próxima.

Na minha experiência, o software de simulação física é, em geral, sobrecarregado pelo mau gerenciamento do estado . Normalmente, cada estágio do algoritmo opera em alguma parte de um estado compartilhado (efetivamente global). Isso torna difícil, ou mesmo impossível, garantir a ordem correta das operações, deixando o software vulnerável a erros que podem se manifestar como seg-falhas, ou pior, termos de erro que não causam erro no código, mas comprometem silenciosamente a integridade de sua ciência. saída. Tentar gerenciar o estado compartilhado em uma simulação física também inibe a multiencadeamento - o que é um problema para o futuro, pois os supercomputadores estão se movendo em direção a contagens mais altas de núcleo, e o dimensionamento com o MPI geralmente chega a ~ 100k tarefas. Por outro lado, a programação funcional torna trivial o paralelismo de memória compartilhada, devido à imutabilidade.

O desempenho também é aprimorado na programação funcional devido à avaliação lenta dos algoritmos (em C ++, isso significa gerar muitos tipos em tempo de compilação - geralmente um para cada aplicativo de uma função). Mas reduz a sobrecarga de acessos e alocações de memória, além de eliminar o despacho virtual - permitindo que o compilador otimize um algoritmo inteiro vendo de uma vez todos os objetos de função que o compõem. Na prática, você experimentará diferentes arranjos dos pontos de avaliação (onde o resultado do algoritmo é armazenado em cache em um buffer de memória) para otimizar o uso da CPU versus alocações de memória. Isso é bastante fácil devido à alta localidade (veja o exemplo abaixo) dos estágios do algoritmo em comparação com o que você normalmente vê em um módulo ou código baseado em classe.

Os programas funcionais são mais fáceis de entender na medida em que trivializam o estado da física. Isso não quer dizer que sua sintaxe seja facilmente compreendida por todos os seus colegas! Os autores devem ter cuidado ao usar funções bem nomeadas, e os pesquisadores em geral devem se acostumar a ver os algoritmos expressos funcionalmente e não processualmente. Admito que a ausência de estruturas de controle pode ser desagradável para alguns, mas não acho que isso deva nos impedir de ir para o futuro, capazes de fazer ciência de melhor qualidade em computadores.

Abaixo está uma advancefunção de amostra , adaptada de um código de volume finito usando o ndarray-v2pacote. Observe os to_sharedoperadores - esses são os pontos de avaliação que eu aludi anteriormente.

auto advance(const solution_state_t& state)
{
    auto dt = determine_time_step_size(state);
    auto du = state.u
    | divide(state.vertices | volume_from_vertices)
    | nd::map(recover_primitive)
    | extrapolate_boundary_on_axis(0)
    | nd::to_shared()
    | compute_intercell_flux(0)
    | nd::to_shared()
    | nd::difference_on_axis(0)
    | nd::multiply(-dt * mara::make_area(1.0));

    return solution_state_t {
        state.time + dt,
        state.iteration + 1,
        state.vertices,
        state.u + du | nd::to_shared() };
}