De quantas maneiras posso escrever fatorial para Scheme?

Linguagens malignas afirmam que linguagens de programação funcionais são "linguagens fatoriais de escrita". Isso geralmente é definido como a linguagem Haskell, mas começaremos com a linguagem funcional que influenciou bastante o Haskell e um subconjunto das ferramentas de programação funcional de muitas outras linguagens - a linguagem Scheme. No mínimo, map e, for-each , filter e reduce , além de apply e eval chegou às nossas linguagens de programação favoritas, se não do Scheme, a partir daí.

Considere algumas maneiras possíveis de escrever cálculos fatoriais. Ao mesmo tempo, você recebe uma espécie de ode à linguagem de programação Scheme. Eu acho que essa linguagem maravilhosa merece.

Eu tenho 10 opções para escrever definições de funções, que podem ser reduzidas a 3 métodos principais de cálculo: o processo computacional linear recursivo tradicional, iteração, geração de uma sequência de números, seguido pela multiplicação por convolução. Proponho considerar essas opções com mais detalhes. Ao longo do caminho, consideraremos: otimização da recursão da cauda, ​​funções de ordem superior e metaprogramação, cálculos adiados, listas sem fim, memorização, uma maneira de criar uma variável estática no esquema e macros de higiene.

Para experimentos, usamos o bom e velho esquema de dialetos R5RS e o princípio popular da arte "meios mínimos - impressões máximas".

Todos os exemplos de esquema foram preparados no DrRacket 6.2 no modo R5RS. As medições de tempo de execução foram feitas no Guile 2.0 no ambiente do OpenSUSE Leap 15 OS.

Para começar, você pode usar uma definição recursiva de fatorial e simplesmente reescrever a fórmula no esquema:

 (define (factorial-classic n) (if (zero? n) 1 (* n (factorial-classic (- n 1))))) 

O resultado foi uma definição de uma função (em termos de Scheme - um procedimento, embora de fato seja uma função) para calcular o fatorial, que pode ser visto em inúmeros guias de programação, começando com o livro imortal de H. Abelson e D. Sassman "Estrutura e interpretação de programas de computador" .

Você pode ler e entender esse código assim: fatorial $$$n$ está ai $$$1$ se $$$n = 0$ caso contrário - $$$n \ cdot (n-1)!$ . Assim, esse código corresponde à definição recursiva de fatorial, adotada na matemática. A única coisa que não verificamos afiliação $$$n$ números não negativos.

Sendo recursivo, o código acima contém uma restrição óbvia ao valor $$$n$ : os dados da chamada recursiva se acumularão na pilha até $$$n$ não atingirá 0. Isso pode causar um estouro de pilha em geral $$$n$ .

Como posso remover esta restrição? É necessário otimizar a recursão da cauda: reescreva o código para que a chamada recursiva se torne cauda (ou seja, a última no procedimento). Isso permitirá que o intérprete do esquema execute a otimização - substitua a computação recursiva pela iterativa.

Se você usar as recomendações dos autores do livro acima, poderá obter o seguinte:

 (define (factorial-classic-tco n) (define (iteration product counter) (if (> counter n) product (iteration (* product counter) (+ counter 1)))) (iteration 1 1)) 

Este código é um exemplo comum e, começando com o livro "A estrutura e interpretação de programas de computador", é nele que a otimização da recursão da cauda é geralmente explicada.

Foi um clássico. Mas Scheme é a própria flexibilidade, é possível escrever a mesma coisa de uma maneira fundamentalmente diferente? E de preferência ainda mais curto? Por exemplo, de acordo com a entrada $$$n! = 1 \ cdot 2 \ cdot 3 \ cdot ~ \ cdots ~ \ cdot n$ formar uma sequência de $$$1$ antes $$$n$ (ou de $$$n$ antes $$$1$ ) e depois recolhê-lo por multiplicação? Felizmente, em Scheme, isso é bastante simples, graças ao procedimento de apply interno, que aplica um procedimento com um número arbitrário de argumentos à lista:

 (define (iota n) (define (iteration sequence i) (if (> in) sequence (iteration (cons i sequence) (+ i 1)))) (iteration '() 1)) (define (factorial-fold n) (apply * (iota n))) 

O esquema é famoso por sua conveniência para cálculos simbólicos devido à "unidade de código e dados" (como costumam dizer sobre os idiomas da família Lisp). Usamos esse recurso: formamos uma expressão para calcular o fatorial de um número $$$n$ e depois calcule:

 (define (factorial-eval n) (define expression `(* ,@(iota n))) (eval expression (interaction-environment))) 

O símbolo “aspas simples” significa quase-cotação. Sem quase-citação, a obtenção de uma expressão para cálculos adicionais poderia ser obtida usando o código (cons '* (iota n)) . Uma citação simples (cotação, cotação) significa que * deve ser substituído na expressão exatamente como um nome (símbolo), e não o valor correspondente (aqui - o procedimento). Então, com $$$n = 3$ nós obtemos (* 3 2 1) . Esta lista é uma expressão no esquema. Seu valor pode ser realizado em um ambiente adequado, o melhor de tudo - em um ambiente (interaction-environment) ambiente de (interaction-environment) contendo os procedimentos internos e os procedimentos definidos por nós no programa. Na verdade, é isso que fazemos no corpo da avaliação factorial-eval .

O esquema suporta computação adiada. Haskell, que foi fortemente influenciado pelo Scheme, usa um modelo de cálculo lento, ou seja, não calcula o valor da expressão até que o resultado desses cálculos seja reivindicado. Isso permite que os programas tenham estruturas de dados tão peculiares quanto listas intermináveis. Se apenas a parte necessária para cálculos adicionais for retirada, o programa não será executado em ciclos:

 ghci> take 4 [1 ..] [1,2,3,4] 

A expressão [1 ..] gera uma lista infinita de números inteiros. A expressão take 4 obtém os 4 primeiros elementos dessa lista. Como os itens de lista subsequentes permanecem não reivindicados, eles não são calculados.

Na Haskell, obtendo $$$n!$ de uma lista interminável, você pode escrever assim

 factorials :: [Integer] factorials = next 0 1 where next n fact = let n' = n + 1 in fact : next n' (fact * n') factorial :: Integer -> Integer factorial n = factorials !! fromIntegral n 

 ghci> take 7 $ factorials [1,1,2,6,24,120,720] ghci> factorial 6 720 

Usando algumas formas de delay / force do esquema force vamos tentar fazer algo semelhante. A palavra-chave delay cria uma promessa para avaliar o valor de uma expressão. A palavra force chave force instrui a executar esses cálculos, o valor resultante é calculado e armazenado. Após o acesso repetido, novos cálculos não são executados, mas o valor calculado anteriormente é retornado.

Nos idiomas da família Lisp, as listas são construídas a partir de pares. Para construir listas infinitas, introduzimos o tipo de “par lento” - um par no qual o primeiro elemento é o valor calculado e o segundo é a promessa de calcular o valor. Para fazer isso, precisamos suplementar a "trindade sagrada" das línguas da família Lisp ( cons , car , cdr ) com suas versões preguiçosas:

 (define-syntax lazy-cons (syntax-rules () ((_ first second) (cons first (delay second))))) (define lazy-car car) (define (lazy-cdr lazy-pair) (force (cdr lazy-pair))) 

O construtor do par lazy-cons é implementado como uma macro. Isso é feito para evitar o cálculo do valor do segundo elemento do par ao criá-lo.

A idéia é criar uma lista interminável de valores e, em seguida, extrair dela o que você precisa. Para fazer isso, defina a versão lenta do procedimento para obter o elemento pelo índice:

 (define (lazy-list-ref lazy-list index) (if (zero? index) (lazy-car lazy-list) (lazy-list-ref (lazy-cdr lazy-list) (- index 1)))) (define (generate-factorials) (define (next nn!) (define n+1 (+ n 1)) (lazy-cons n! (next n+1 (* n! n+1)))) (next 0 1)) 

Aqui n! e n+1 são os nomes das variáveis. No esquema, em comparação com outros idiomas, existem muito poucos caracteres que não podem ser usados ​​nos identificadores.

Observe que os fatores geradores de gerador de lista infinita não contêm uma maneira de sair da recursão. No entanto, ele não será executado em loop, pois quando for chamado, apenas o cabeçalho da lista será calculado, enquanto a cauda será representada por uma promessa de calcular o valor.

Agora você pode definir $$$n!$ como chegar $$$n$ th elemento da lista de fatoriais:

 (define lazy-factorials (generate-factorials)) (define (factorial-lazy n) (lazy-list-ref lazy-factorials n)) 

Isso funciona. Ao mesmo tempo, se fatores de números diferentes forem calculados em uma sessão do intérprete, os cálculos ocorrerão mais rapidamente do que nas versões estritas, porque alguns dos valores da lista lenta já serão calculados.

A propósito, o código no Scheme é muito próximo ao do Haskell. Então, a declaração de recebimento !! corresponde aproximadamente ao procedimento lazy-list-ref construtor da lazy-list-ref : corresponde a lazy-cons . Do mesmo modo, porque Haskell, apesar de professar um modelo de cálculo preguiçoso, no entanto, diferentemente do delay / force no Esquema, ele não se lembra dos valores calculados.

A propósito, para aumentar a produtividade, você pode aplicar a memorização de valores já calculados - memorização. Armazenaremos os valores calculados em uma lista associativa, na qual as chaves são números e os valores são seus fatoriais. Quando chamado, examinaremos a lista em busca de valores já calculados. Se o valor estiver na lista, retornaremos esse valor armazenado. Se o valor não estiver na lista, vamos calculá-lo, colocá-lo na lista e somente então devolvê-lo. Para garantir que essa lista esteja sempre com a função chamada e não no ambiente global, coloque-a em uma variável estática:

 (define factorial-memoized (let ((memo '())) (lambda (n) (let ((memoized (assq n memo))) (if memoized (cadr memoized) (if (zero? n) 1 (let ((computed (* n (factorial-memoized (- n 1))))) (set! memo (cons (list n computed) memo)) computed))))))) 

 (define proc (let ((static-var initial-value)) (lambda args ...))) 

 (define count (let ((n 0)) (lambda () (set! n (+ n 1)) n))) 

 (define count ((lambda (n) (lambda () (set! n (+ n 1)) n)) 0)) 

Essa implementação também promete ganhos de desempenho, calculando repetidamente fatoriais de vários números em uma sessão de intérprete.

Obviamente, a otimização da recursão da cauda também é possível aqui:

 (define factorial-memoized-tco (let ((memo '())) (lambda (n) (define (iteration product counter) (cond ((> counter n) product) (else (set! memo (cons (list counter product) memo)) (iteration (* product counter) (+ counter 1))))) (iteration 1 1)))) 

“Por que essas danças com um pandeiro?”, Pode o leitor dizer. Nas linguagens de programação imperativas, a mesma coisa é escrita de forma simples - através de um loop, ela funciona rapidamente e sem custos desnecessários de memória. O esquema possui um subconjunto para programação imperativa, também possui um meio para organizar loops - uma forma especial de do . O procedimento para calcular o fatorial, escrito com sua ajuda, pode ser assim:

 (define (factorial-do n) (define product 1) (do ((i 1 (+ i 1))) ((> in) product) (set! product (* product i)))) 

A construção do é bastante versátil, e é por isso que não é muito legível. Não é melhor organizar seu próprio ciclo em um estilo imperativo? As macros ajudarão com isso:

 (define-syntax for (syntax-rules () ((_ (variable init test step) . body) (let loop ((variable init)) (if test (begin (begin . body) (loop step))))))) 

Graças à otimização da recursão da cauda pelo intérprete, obtemos um loop com o qual estamos acostumados em linguagens de programação imperativas. Ao otimizar a recursão da cauda, ​​a pilha não aumentará.

Definindo fatorial usando for :

 (define (factorial-for n) (define product 1) (for (i 1 (<= in) (+ i 1)) (set! product (* product i))) product) 

 for → _ i → variable 1 → init (<= in) → test (+ i 1) → step (set! product (* product i)) → body 

 (define (factorial-for n) (define product 1) (let loop ((i 1)) ;   (if (<= in) ;  (begin (begin (set! product (* product i))) ;  (loop (+ i 1))))) ;  for product) 

Há outra opção que se parece com o imperativo for loop - com o procedimento interno for-each procedimento:

 (define (factorial-for-each n) (define product 1) (for-each (lambda (i) (set! product (* product i))) (iota n)) product) 

Grande e poderosa linguagem Scheme! E o desempenho?

Usaremos o GNU Guile para medir o desempenho - nesse ambiente, você pode medir o tempo necessário para avaliar uma expressão de maneira mais simples.

O Guile funciona da seguinte maneira: compila o código-fonte do programa no bytecode, que é então executado pela máquina virtual. Esta é apenas uma das implementações e uma das várias maneiras possíveis de executar um programa Scheme, existem outras: Racket (usa compilação JIT), Chicken Scheme (usa uma interpretação ou compilação “honesta” em um subconjunto de C), etc. Obviamente, as limitações e o desempenho dos programas nesses ambientes podem variar um pouco.

Vamos fazer medições com um certo valor $$$n$ . O que deveria ser $$$n$ ? Então, com o qual o maior $$$n$ será capaz de "lidar" com as opções propostas. Com as configurações padrão do Guile 2.0, em um PC com Intel Core i5 e 4 GB de RAM, obtive o seguinte:

A partir daqui, testes de desempenho foram realizados em $$$n = 8 \, 000$ . Os resultados são apresentados na tabela abaixo, onde $$$t_ {run}$ - prazo de entrega $$$t_ {GC}$ - tempo de execução do coletor de lixo em segundos.
Para todos os procedimentos, exceto os preguiçosos e os memorizados, são obtidos os menores valores de tempo de execução e o tempo correspondente do coletor de lixo, obtidos após três lançamentos no $$$n = 8 \, 000$ .
Para procedimentos memorizados e preguiçosos, o tempo de execução da primeira chamada é indicado e, em seguida, a menor das três chamadas.

Temos 4 opções que podem trabalhar com grandes $$$n$ . At $$$n = 100 \, 000$ eles têm os seguintes tempos de cálculo e coleta de lixo:

Você pode ver que com não muito grande $$$n$ o mais rápido e, ao mesmo tempo, o mais curto é o primeiro. A mesma opção corresponde totalmente à definição matemática de fatorial. A opção de otimização da recursão da cauda não é muito inferior a ela no desempenho. Ambas as opções são idiomáticas recomendadas pelos autores do idioma. A conclusão é bastante óbvia: a menos que especificado de outra forma, a abordagem, que é "típica" para a linguagem, é preferida, pelo menos para a primeira implementação de um algoritmo ou método.

Ao mesmo tempo, a linguagem Scheme nos permitiu escrever muitas opções para implementar a computação fatorial usando um conjunto muito limitado de primitivas (as "médias mínimas - impressões máximas"). Portanto, apesar de sua idade venerável e não muito difundida, essa linguagem ainda pode ser recomendada para a programação de pesquisas: parece que você pode implementar qualquer coisa nela de qualquer maneira (e de qualquer maneira) conveniente .