Que dicas gerais você tem para jogar golfe em Prolog? Estou procurando idéias que possam ser aplicadas para codificar problemas de golfe em geral que sejam pelo menos um pouco específicos para o Prolog (por exemplo, variáveis de uma letra não são específicas para o Prolog para reduzir o tamanho dos programas).
Indique nas suas dicas se é específico para uma implementação do Prolog (por exemplo, embutidos específicos do SWI-Prolog)
Poste apenas uma dica por resposta ou uma lista de dicas que estão intimamente relacionadas à mesma idéia principal.
prolog
tag é meio inútil. A menos que tenhamos um desafio Interpret Prolog, não precisamos dele.Respostas:
Usar operadores para nomes de predicados
É possível atribuir operadores de predicados como nomes, desde que o operador seja um dos operadores predefinidos (listados aqui ) e ainda não esteja definido como predicado. Isso economiza alguns bytes ao definir e chamar o predicado, uma vez que os predicados do operador não precisam ser gravados na
name(arg1,arg2,etc..)
forma normal e podem ser chamados conforme o esperado com os operadores.Para um e dois predicados de argumento, eles podem fornecer os nomes de operadores unários e binários, respectivamente. Para predicados de aridade mais altos, ainda podemos evitar parênteses usando a correspondência de padrões. Por exemplo, se tivermos um predicado
A+B+C:-...
, o Prolog usará suas regras de precedência e associatividade do operador para transformá-lo em(A+B)+C:-...
um predicado de operador no qual o primeiro argumento é correspondido ao padrãoA+B
. Ou então,A-B+C*D:-...
que se torna(A-B)+(C*D)
o primeiro argumento com o padrão correspondenteA-B
e o segundo com o padrão correspondenteC*D
.Exemplos
A saída será
X = 5.
Experimente Online!
Corolário
Desde a DCGs são açúcar sintático para predicados, eles também podem receber operadores para nomes. Isso funciona como esperado ao chamá-los como DCGs de um DCG ou usando os
phrase
predicados ou outros projetados para funcionar com DCGs. Ao chamá-los como predicados, parênteses são necessários (por exemplo,A+B-->...
devem ser chamados como+(A,B,...)
), pois os predicados do DCG levam dois argumentos adicionais para suas listas de diferenças. Para operadores nomeados DCGs com mais de dois argumentos usando correspondência de padrão de operador, é importante garantir que, ao chamá-lo como um predicado, os operadores correspondentes ao padrão sejam distribuídos corretamente.Dar nomes de operadores a DCGs que não usam argumentos adicionais pode ser útil se você precisar chamá-los em seu programa, pois poderá fazê-lo sem usar parênteses. É necessário cuidado, pois pode ocorrer o que você salva entre parênteses, para perder com o espaçamento adicional necessário para analisar operadores adjacentes.
Exemplos
A saída será
Experimente online!
Ressalvas
Com os operadores unários
+
e-
, o Prolog interpretará+20
ou-20
como números em vez de uma chamada para um+/1
ou-/1
predicado. Os predicados dados como unários+
ou-
como nomes ainda podem ser chamados pelo número usando parênteses (+(20)
,-(20)
). Se é desejável evitar bytes extras entre parênteses, outros operadores unários, como\
,$
, etc., podem ser utilizados como nomes vez.A combinação de correspondência de padrões e predicados nomeados pelo operador não é totalmente isenta de falhas. Se você tiver dois predicados que têm o mesmo operador que o nome e, com o padrão correspondente, um é estritamente mais geral que o outro, o mais geral pode ser chamado primeiro ou se o menos geral falhar (dependendo da ordem na origem) . Por exemplo, no exemplo acima, se
A-B+C*D
não corresponder à sua entrada, o Prolog tentará chamarX+Y
. Isso resultará em um erro porque élength/2
necessárioY
que seja um número inteiro que não será, pois estará no formatoC*D
. Isso pode ser evitado simplesmente certificando-se de que não há dois predicados com o mesmo operador que o nome ou, se isso falhar, usando cortes e ordenação cuidadosa da origem.fonte
Tente colocar todos os casos possíveis em uma única regra
A maneira limpa de programar no Prolog é declarar várias regras para o mesmo predicado. Por exemplo, um predicado para reverter uma lista com um acumulador ficaria assim:
Em Code-golf, podemos remover a primeira regra e adicionar a
;
no final da segunda regra para codificar o final da recursão:Sabemos que a primeira condição
r(T,[H|Z],R)
falhará se T estiver vazio, ou seja, se a recursão precisar terminar e, portanto, poderemos adicionar nossa rescisão como uma cláusula ou depois dela.O mesmo princípio funciona em muitas situações. Observe, porém, que às vezes é mais curto declarar outra regra, em vez de fazer isso.
fonte
Um truque que é frequentemente útil: use restrições CLP (FD) para aritmética inteira para obter predicados que podem ser usados automaticamente em várias direções, evitando condições e ramificações e variantes dedicadas.
Use B-Prolog ou GNU Prolog, onde essas restrições estão disponíveis imediatamente, sem a necessidade de carregar nenhuma biblioteca.
fonte
library(clpfd)
que estará disponível como uma biblioteca pré - carregada ou pelo menos carregada automaticamente também no SWI-Prolog. Pode levar alguns anos até que a aritmética declarativa seja totalmente compreendida e apreciada por todos os usuários, que já acumularam décadas de experiência com recursos desatualizados e de baixo nível. Quanto mais você usa e defende o CLP (FD), mais cedo o obteremos por padrão. Até lá, você pode simplesmente colocar:- use_module(library(clpfd)).
seu~/.swiplrc
e apenas declarar que está usando essa "variante" do SWI-Prolog.Use operadores aritméticos como construtores de tupla e pares de contras
Se você precisar passar uma única estrutura que consiste em dois ou mais valores, a coisa mais óbvia a ser usada é uma lista, por exemplo,
[A,B]
. Isso é realmente detalhado, no entanto.Existe uma alternativa. Os valores de prólogo podem armazenar uma estrutura aninhada praticamente arbitrária, que não é avaliada. Aqui está um exemplo mostrando como isso funciona:
member(A,B)
é apenas uma tupla nomeada nessa situação, e a parte externamember
(que é uma chamada de função) está tratando-a como tal.Embora as tuplas nomeadas sejam bastante úteis na programação Prolog sem golfe, elas podem parecer ainda mais detalhadas do que a abordagem da lista. No entanto, podemos usar praticamente caracteres arbitrários no nome do construtor de tupla (supondo que eles estejam corretamente citados); em vez de algo fofo
member
ou um único personagema
, podemos fazer algo assim:Aqui, nossos construtores de tupla são
'-'
e'/'
. E é interessante observar o que a impressora bonita fez com eles; está usando notação infix para as tuplas. Isso é realmente conciso e analisa da mesma maneira que faria uma operação aritmética comparável. (Isso também explica por que a aritméticais
não usa=
; aA = 1+2
unificaçãoA
com a tupla'+'(1,2)
, portanto, é necessária uma sintaxe separada para realmente avaliar a expressão aritmética não avaliada.) Como um construtor de tupla precisa ser chamado de algo , você também pode usar um caractere que tenha uma concha sintaxe (e como bônus,-
e/
também são algumas das opções mais comuns no código não-golfe quando eles desejam um construtor de tupla descartável rápido em vez de algo significativo, da mesma maneira quei
é frequentemente usado como uma variável de loop, portanto, é inteiramente razoável usá-lo em sua entrada e saída, se você desejar uma tupla por algum motivo).'-'
e'/'
são boas escolhas para construtores de tuplas porque eles têm uma precedência útil e bem comportada, permitindo que você escreva literalmente as tuplas de forma concisa. No entanto, observe que você não precisa se preocupar com precedência quando valores intermediários são produzidos dentro do programa. O Prolog mantém as tuplas armazenadas como uma árvore, e não como código-fonte, e as impressoras bonitas podem produzi-las sem ambiguidade:Como a sintaxe da tupla é muito concisa (
f(A,B)
não é menor quef(A-B)
), é possível substituir vários argumentos de predicados por tuplos sem nenhum custo, o que significa que, se um predicado precisar passar dois ou mais de seus argumentos para outro predicado, é possível transformá-los em uma tupla e apenas passar a tupla (embora isso exija a alteração de todas as chamadas para o predicado, além do próprio predicado, para usar uma combinação apropriada de construtores e vírgulas de tupla).Outra vantagem dessa sintaxe é se você precisar usar listas internamente (em vez de interoperar com predicados padrão); uma lista é basicamente apenas um conjunto de células contras aninhadas e uma célula contras é apenas uma tupla com construtor
'.'
, como pode ser visto aqui:Se seu código usa listas "manualmente", pode fazer muito sentido usar um construtor de tupla menos volumoso que
'.'
. Uma escolha comum para mim é representar uma célula contras como'/'(Tail,Head)
(porque é a mais legível que você pode obter na saída de depuração sem desperdiçar caracteres). Observe que você provavelmente também desejará seu próprio[]
equivalente; você poderia usar[]
mas tem dois bytes e há muitos átomos de um byte (todas as letras minúsculas) que você pode usar.Então, por exemplo, a seguinte lista:
pode ser convertido em uma representação manual no mesmo número de caracteres como este:
ao mesmo tempo em que
[H|T]
obtém a vantagem de que as correspondências de padrões no estilo agora podem ser escritas de maneira mais concisaT/H
, e um teste contra a lista vazia como um pouco,x
e não mais[]
. (Claro, isso vem com a desvantagem óbvia de quemember
,append
etc., não vai trabalhar nesta representação.)fonte
-
e/
. Estes já são átomos perfeitamente normais..
, desde que os seguintes caracteres não sejam%
um layout nem um.Sintaxe mais curta para listas de listas e uma maneira de declarar mapas
Você pode salvar bytes em listas de listas. Se você tiver uma lista
[[1,2],[3,4]]
, poderá declará-la como[1:2,3:4]
, o que salva 4 colchetes = 4 bytes. Observe que você pode usar algo diferente de:
(por exemplo^
).1:2
não é realmente uma lista nesse caso (enquanto[1,2]
era), é representada internamente como:(1,2)
. Portanto, você não pode usar predicados que funcionam em listas nas sublistas que usam dois pontos.Este truque é usado principalmente para declarar mapas, ou seja, uma lista de chaves com valores anexados a eles. Por exemplo, se você quiser declarar um mapa
M
que contenha a ortografia de um dígito em inglês e francês, poderá fazer algo assim:Você pode, por exemplo, recuperar elementos do mapa com um predicado interno como
member/2
. Por exemplo, se você quiser que o dígito e a palavra em inglês correspondam a'Quatre'
inM
, você pode:fonte
[[1,2],[3,4]]
como1*2+3*4
, que é+(*(1,2),*(3,4))
e, portanto, também usar apenas um byte em que você precisaria de dois para abrir e fechar parênteses."abc"
em vez de[a,b,c]
Um truque interessante: quando você precisar falhar , use algo equivalente a falso / 0 , mas mais curto, como:
fonte
\+!
como um 3 bytes maneira estranha ao fracasso que na verdade não dispara o corte!
(ver este para isso ). Eu não acho que é possível falhar em menos de 3 bytes.\+!
colas à esquerda para outros caracteres gráficos, enquanto0=1
colas à esquerda para nomes.Reutilizar um predicado com diferentes modos de chamada
Por exemplo, você pode analisar e imprimir uma estrutura com o mesmo predicado, uma vez com um argumento variável e outra vez com um termo básico. Eu usei essa abordagem em Make the Stretchy Snakes Kiss . Isso não é possível em todos os desafios, é claro.
fonte