sentencia - reglas en prolog
Prolog: manejo de datos binarios con DCG (4)
Para ser un poco más explícito que lo que puedo en un comentario, tomando como ejemplo el análisis de un entero y la conversión de un entero a una cadena, se podría decir:
foo_parse(Number) -->
digits(Ds),
{ number_codes(Number, Ds) }.
foo_generate(Number) -->
{ number_codes(Number, Ds) },
Ds.
Podrías evitar esto teniendo un "guard" var(Number) para la primera de las dos cláusulas, completo con su propio corte, etc., pero no estoy seguro de que sea mucho más fácil escribir, leer o usar. Los dos DCG probablemente serán llamados desde diferentes contextos de todos modos.
Entonces, para su caso, generar sería algo así como:
fourbit_fourbit_generate(High, Low) -->
{ D is (High << 4) + Low },
[D].
Solo es mi opinión.
Me parece que uno debería ser capaz de procesar datos binarios con DCG en una lista de bytes. Sin embargo, para que funcione en general, uno tiene que usar operaciones a nivel de bit, lo que significa que está involucrado is/2 , lo que significa que el orden de instanciación es un problema, lo que puede confundir el uso de los DCG tanto para analizar como para generar. La idea aquí es serializar / deserializar los datos binarios, pero creo que este ejemplo es lo suficientemente simple como para ilustrar el problema.
Déjame ilustrar con algún código. Supongamos que tengo un protocolo binario. Quiero leer dos enteros de 4 bits de un byte. Mi ingenuo yo prueba esto:
two_four_bit_ints(High, Low) -->
[B],
{
High is B >> 4,
Low is B // 0xF
}.
Esto parece funcionar para el análisis:
?- phrase(two_four_bit_ints(H,L), [255]).
H = L, L = 15.
?- phrase(two_four_bit_ints(H,L), [0]).
H = L, L = 0.
?- phrase(two_four_bit_ints(H,L), [15]).
H = 0,
L = 15.
?- phrase(two_four_bit_ints(H,L), [240]).
H = 15,
L = 0.
Pero esto no va a generar:
?- phrase(two_four_bit_ints(15,15), [X]).
ERROR: is/2: Arguments are not sufficiently instantiated
?- phrase(two_four_bit_ints(15,15), X).
ERROR: is/2: Arguments are not sufficiently instantiated
No estoy seguro de qué hacer. Me estoy preparando para que alguien grite "Use clpfd ", pero no parece ser compatible con las operaciones de cambio de bits, y me preocupa el efecto de rendimiento de invocar un sistema tan poderoso en el medio del código de bajo nivel.
Como no veo muchos ayudantes para binarios, ¿hay alguna otra forma más preferida de hacer extracción / codificación binaria en Prolog? Solo estoy usando SWI por ahora, así que estoy feliz de aceptar sugerencias que no son portables para ISO, pero si es portátil también es bueno. Esperaba encontrar a alguien que hubiera portado algo parecido a la sintaxis bit de Erlang, pero no tuve ninguna suerte buscando.
Una mejor compatibilidad con los datos binarios sería una función muy agradable de tener en Prolog. Sin embargo, la naturaleza relacional de Prolog hace que una solución general sea bastante difícil. Entonces enfrenta una decisión seria: o mapea alguna biblioteca de otros idiomas directamente en Prolog, ignorando así la naturaleza relacional de Prolog (e idealmente evitando todas las fronteras con errores limpios de creación de instancias) o opta por un enfoque más relacional.
Al optar por una solución más relacional, puede utilizar las bibliotecas existentes como library(clfd) o implementar el mecanismo de restricción completo usted mismo. Con algunas restricciones inteligentes, puede salirse con la suya con un enfoque mucho más simple, pero dudo que esto vaya a funcionar. Las compensaciones se encuentran en áreas de corrección y eficiencia. Tenga en cuenta que los sistemas clpfd en SICStus o SWI necesitaron literalmente décadas para alcanzar su nivel de calidad.
No importa qué camino tomará, algunas observaciones:
Eficiencia de la library(clpfd)
library(clpfd) en SWI-Prolog se ha optimizado específicamente para ser (en algunos casos) comparable en rendimiento al tradicional (is)/2 . Para ver esto, compila la regla:
list_len([_|Es], N0) :- N0 #> 0, N1 #= N0-1, list_len(Es, N1).
y mira el código generado con el listing(list_len) :
list_len([_|C], A) :-
( integer(A)
-> A>=0+1
; clpfd:clpfd_geq(A, 1)
),
( integer(A)
-> B is A+ -1
; clpfd:clpfd_equal(B, A-1)
),
list_len(C, B).
Efectivamente, los incorporados para expresiones evaluables como (is)/2 y (>=)/2 se usan para aquellos casos que corresponden directamente a esas operaciones primitivas.
Sin embargo, para simular completamente las operaciones de desplazamiento de bits, necesitaría (div)/2 que actualmente solo es compatible con la library(clpfd) pero no con SWI. Entonces algún dolor de cabeza extra lo esperaría aquí. Pero siempre que use valores no negativos no firmados, no debería surgir ningún problema. Para cambios generales, necesitará (^)/2 que es compatible con SWI, pero no con SICStus.
Y aquí está la versión CLPFD:
two_four_bit_ints(High, Low) -->
[B],
{ B in 0..255,
Low in 0..15,
High in 0..15,
B #= Low + High*16
}.
Tenga en cuenta que su programa original define involuntariamente el comportamiento en situaciones no deseadas, como B = -1234 , B = 1+1 . Podría agregar between(0, 255, B) pero luego obtendría enumeraciones combinatorias (léase: explosiones) fácilmente.
Las implementaciones actuales de la library(clpfd) podrían mejorarse significativamente para tales casos aún más, pero para mejorarlas, ¡hay que usarlas!
E / S y pio
ISO Prolog admite operaciones de E / S elementales en
- bytes (
get_byte/1), - códigos (
get_code/1), y - caracteres (
get_char/1).
Si desea usar DCG, seguramente querrá usar la library(pio) . Actualmente, la library(pio) de SWI library(pio) solo admite codes .
esto puede funcionar
two_four_bit_ints(High, Low) -->
[B],
{
integer(B) % suggestion by @false, instead of nonvar(B)
-> High is B >> 4,
Low is B // 0xF
; B is (High << 4) // Low
}.
recuerde, un DCG es simplemente un Prolog, pero puede verlos como gramáticas semánticas ejecutables.
En SWI-Prolog, ahora se admiten muchas operaciones bit a bit en CLP (FD).
Por favor, intente lo siguiente con la última versión de Git. Basta con reemplazar (is)/2 por (#=)/2 en su código:
two_four_bit_ints(High, Low) --> [B], { High #= B >> 4, Low #= B // 0xF }.
Sus primeras 4 consultas de ejemplo funcionan exactamente como antes y deben ser aceptablemente eficientes:
?- phrase(two_four_bit_ints(H,L), [255]). H = L, L = 15. ?- phrase(two_four_bit_ints(H,L), [0]). H = L, L = 0. ?- phrase(two_four_bit_ints(H,L), [15]). H = 0, L = 15. ?- phrase(two_four_bit_ints(H,L), [240]). H = 15, L = 0.
Tenga en cuenta que las restricciones CLP (FD) se compilan directamente a los predicados de bajo nivel si se usan en modos que también son compatibles con la aritmética primitiva.
Un beneficio del uso de restricciones CLP (FD) es que las otras 2 consultas ahora también funcionan:
?- phrase(two_four_bit_ints(15,15), [X]). 15#=X//15, 15#=X>>4. ?- phrase(two_four_bit_ints(15,15), X). X = [_G1048], 15#=_G1048//15, 15#=_G1048>>4.
Al menos puedes usar esto para seguir razonando.
De hecho, la consulta más general ahora también funciona:
?- phrase(two_four_bit_ints(A,B), X). X = [_G1270], A#=_G1270>>4, B#=_G1270//15.
Es posible realizar propagaciones más potentes en algunos casos. Examinaré esto tan pronto como surja la necesidad.