scheme - programa - parentesis balanceados python

Esquema, ¿Cuándo usar símbolos en lugar de cadenas?

Question

Me disculpo de antemano por mi inglés primitivo; Haré todo lo posible para evitar errores gramaticales y cosas por el estilo.

Hace dos semanas decidí refrescar mi conocimiento de Scheme (y sus publicaciones) mientras implementaba material matemático que obtuve entre manos, específicamente, Lenguas regulares de un curso sobre teoría de autómatas y computación en el que estoy inscrito.

Hasta ahora, he estado representando alfabetos como listas de símbolos en lugar de

1. listas de caracteres porque quiero tener letras de tamaño variable.
2. listas de cadenas porque de alguna manera siento que es poco elegante.

No tengo experiencia y me gustaría saber tu opinión sobre esta opción en particular. ¿Los símbolos están reservados para algún tipo particular de tarea y con esto estoy abusando de ellos? Cualquier comentario sobre esto es muy apreciado porque estoy buscando orientación.

En un alcance adicional, también habrá tiempo para implementar el conjunto de todas las palabras posibles sobre un alfabeto, que es infinito. Estaba pensando en limitar el conjunto por el tamaño máximo de palabras permitido. De nuevo, ¿es esta una buena práctica o debería optar por las transmisiones? Siento que las transmisiones serían un mejor enfoque, pero todavía no las aprendí, así que no sé realmente cuáles son las implicaciones de su uso.

De todos modos, cualquier sugerencia o comentario es bienvenida. Realmente aprecio el tiempo que tomó para leer mis dudas. ¡Ten un buen fin de semana!

Answer 1

La simple diferencia es que los símbolos son extremadamente baratos de comparar. Uno puede usar eq? para comparar dos símbolos como idénticos. Esto se debe a que durante el tiempo de compilación, el compilador esencialmente enumerará todos los símbolos con un número, por lo que solo está comparando números enteros, una operación de máquina muy económica.

Esto significa que dos símbolos son idénticos si y solo si están compuestos de los mismos caracteres. No hay forma de distinguir dos símbolos que tienen los mismos caracteres en el código, son constantes, son los mismos objetos, al igual que 3 y 3 .

Sin embargo, dos cuerdas pueden ser diferentes objetos que residen en diferentes lugares de la memoria, y para compararlas es necesario comparar cada carácter por separado para una coincidencia.

Así que los símbolos deberían, y se usan a menudo para esto, por ejemplo, considerar:

(assq ''symb  ''((foo 1 2 3) (bar symb) (symb "match")))

Esto devuelve la lista (symb "match") esto es tan barato como comparar:

(assq 4  ''((0 1 2 3) (1 symb) (4 "match")))

Que devuelve la lista (4 "match") . Sin embargo, cuando se utilizan cadenas de caracteres como assq ya no es suficiente, ¿cuál usa la eq? assoc debe usar el procedimiento de comparación, en lugar de assoc , que usa el equal? procedimiento, que es mucho más costoso ya que compara recursivamente la estructura. La implementación anterior es en realidad lo suficientemente barata como para ser utilizada a menudo como una forma de modelar matrices asociativas y entornos en intérpretes, aunque ciertamente no es un acceso aleatorio.

Editar: como preguntaste en las transmisiones:

El estándar Scheme admite un buen par, una es una función llamada force , la otra, es una forma especial llamada delay . Efectivamente, qué

(delay (+ 1 2 3))

O cualquier otro código en lugar de (+ 1 2 3) devuelve es una llamada ''promesa'', retrasa el cálculo de la respuesta en esa promesa, pero promete que el resultado será idéntico cuando se evalúe a ese 6 que lleguemos allí . Esto puede parecer bastante inútil, pero digamos que el resultado depende de alguna variable, que puede modificarse:

(define x 4) ; x is bound to 4.
(let ((promise (delay (+ 2 x)))) ; evaluating the expression now would result into 6, but we delay it.
  (set! x 5) ; we change the value of x.
  (display (force promise)) ; displays 7
  (set! x 6) ; change it again
  (force promise) ; ALSO displays 7, not 8
)

Se vuelve aparente que la promesa se evalúa solo una vez, y cuando se vuelve a forzar, arroja el mismo valor que cuando se evaluó la primera vez.

Esto es lo que normalmente se usa en las transmisiones, o ''listas infinitas'' conceptuales. El cdr de la lista en este caso es una promesa para el resto de la lista que se fuerza cuando se recupera, ya que de lo contrario se convertiría en un cálculo no determinante, por ejemplo, comúnmente definimos:

(define (stream-cdr x) (force (cdr x))) ; it forces that promise to evaluate it.
; and optionally
(define stream-car car) ; same

Como este no puede evaluar su argumento, debe ser una forma especial:

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons x y)
     (cons x (delay y))))

Su compilador o intérprete de esquemas ahora traducirá cada ocurrencia de (stream-cons xy) en (cons x (delay y)) para cualquier x e y arbitrario.

Entonces, como un ejemplo simple, ahora que nuestra evaluación se demora hasta que la necesitemos, podemos crear una lista infinita de ceros:

(define zero-stream (stream-cons 0 zero-streams))

Una lista hecha a sí misma, que seguramente nunca terminaría si no hubiéramos usado una secuencia, inútil, pero muestra la idea. Solo podemos usar stream-cdr una y otra vez en esto sin llegar a una lista vacía, simplemente obtenemos la misma ''lista infinita de 0'' de nuevo.

Un ejemplo más práctico sería la lista de todos los números de Fibonacci, que es algo más complejo:

(define fibs 
  (stream-cons 0 (stream-cons 1
    (stream-map + fibs (stream-cdr fibs))))

Stream-map es el análogo del mapa normal, su definición es bastante compleja, pero estoy seguro de que puedes buscarla, genera una transmisión en sí misma. Entonces `(stream-map (lambda (xy) (+ 1 xy)) pone a cero ceros) generaría una corriente completamente llena de uno. La corriente de fibs se define recursivamente en sí misma. Los primeros dos elementos se dan y el resto se calcula a partir de dos flujos que simplemente resultan ser fibs y la corriente-cdr de fibs en sí.