Foro de elhacker.net

Hola!

En una facultad de Madrid me he encontrado pinchado en el panel este original reto...
Está en inglés, pero creo que se entiende...

• El primer problema pide demostrar que el programa dado acaba
• El segundo dice que cuando acabe, el sistema sacará la llamada correspondiente al assert.  :o :o

Alguna propuesta ? :o :o :o

El segundo ejemplo no debería parar y el assert(1) no debería fallar.

Saludos,

- El FOR requiere de ( Sentencia; Condicion; Sentencia ), tengo entendido de que las Sentencias pueden quedar vacías, lo he visto mucho en javascript.

-- En el primer caso es un bucle que no se cumple, la condición es 0 o FALSE

-- En el segundo caso el bucle en infinito y nunca llega a ejecutarse el assert(1)

- Entonces pienso que el libro se refiere a un problema de compilación, pero mi compilador MinGW no me ha dado ningún problema. Algo así como decir que se está importando tal cosa y no se está usando, o se ha detectado un bucle infinito, o se ha detectado una sentencia de código ( assert(1) ) que nunca se ejecutará debido x razón, etc.

---

- También me parece sospechoso ese ; al final del FOR, supongo que dependiendo del tema del libro, podría estar explicando que el ; da por finalizado el Bucle en esa misma línea y no ejecuta nada más, es decir, ese FOR no tiene cuerpo a ejecutar:

for ( sentencia, condicion, sentencia ) ;
 
for ( sentencia, condicion, sentencia )
  cuerpo a ejecutar
 
for ( sentencia, condicion, sentencia ) {
  cuerpo a ejecutar
}
 
for ( sentencia, condicion, sentencia ) ;
  esta sentencia no pertenece al FOR y es independiente
 
for ( sentencia, condicion, sentencia ) ; {
  esta sentencia no pertenece al FOR y es independiente
}
 

Al primer ejemplo no le veo mucha complicación, un <for> se ejecuta mientras la condición (segundo campo del <for>) sea verdadera (1). Los campos de inicialización (primer campo) y actualización (tercer campo) pueden quedarse vacíos como es el caso aunque siempre se ha comentado que no es una buena práctica ya que en otros lenguajes no está permitido este uso.
Se ejecuta el <for> y como la condición es falsa (0) termina y sale.

En cambio, en el segundo ejemplo es todo lo contrario, el <for> no termina nunca ya que la condición es siempre verdadera (1) y como ya ha comentado EdePC, como el <for> acaba en punto y coma (;) la instrucción del <assert(1)> no se ejecutará nunca ya que no pertenece al cuerpo del <for> y este genera un bucle infinito.

El primer caso a mí me parece lo mismo; para el segundo lo único que se me ocurre es que alguien ha estado jugando con <assert>, así que si yo también...

#include <stdio.h>
#include <string.h>
 
#define __FILENAME__ (strrchr(__FILE__, '\\') ? strrchr(__FILE__, '\\') + 1 : __FILE__)
 
#define assert(expression) (void)((!(expression)) || (mostrar(#expression, __FILENAME__, (unsigned)(__LINE__), __func__), 0))
 
#define for(a) while(0)
 
void mostrar(const char* message, const char* file, int line, const char* function)
{
    printf("%s: %s:%i: %s: Assertion \'%s\' failed\n", function, file, line, function, message);
}
 
int main()
{
    for( ;1; );
 
    assert(1); 
}

Chicos, gracias por vuestras repuestas.
  Loretz, muy buena tu exhibición, pero el ejercicio que propones no cumple lo que dice, porque YA es otro fichero fuente del que se propone...

Creo que hay que hacerlo sobre el mismo contenido del original y lo que me choca más... se supone que no vale argûir "Alguien ha jugado con el assert, pues yo también...", porque el sistema ha de ser compatible ANSI-C/ISO-C, o sea, el assert tiene que hacer lo que se espera de él...

Os digo mis progresos:

• Es un absurdo esperar a que acabe un programa que no acaba. Todo el mundo está de acuerdo en que el bucle es infinito.
• Es un absurdo esperar que assert falle cuando el parámetro sea 1, ya que sólo falla cuando vale 0, según el ANSI-C/ISO-C

No hay manera de relacionar estos absurdos entre sí? Me huelo que "por aquí va la tostada", rollo lógica....

En cuanto tenga algo os lo paso...

Esto son temas de sobra conocidos en teoría de compiladores.

El primer tema a considerar: Los bucles infinitos versa que si el incremento es 0 y el valor inicial es igual al valor final, no es un bucle infitio, en otro caso si:
       bucle infinito = ((inc = 0) and (inicio <> final))
...y si el cuerpo está vacío (como es el caso), o no existe dentro una sentencia de escape del bucle (si existe, deberá examinarse también). Lógicamente en tiempo de compilación...
       Por eso no se cumple en el primer caso y sí en el segundo.

Los bucles infinitos de este modo, en realidad pueden ser tomados como bucles incondicionales (tipo do...loop) y han sido la solución para lenguajes en los que no existen otro tipo de bucles que no sean condicionados por una expresión aritmética pero que si admiten una sentencia de salida del mismo controlados por algún 'if then else'.

El segundo tema a considerar: En teoría de compiladores se trata en la optimización de código, para eliminar código redundante o código inaccesible. Código inaccesible es aquel que nunca se va a ejecutar, caso por ejemplo como:

El compilador detectará que si a x se el asigna la constante 20, no puede tener de inmediato la contante 0, luego todo el código dentro del condicional incluído el condicional, puede ser omitido.
Piénsese que los condicionales 'if then', a efectos prácticos pueden considerarse bucles de 0 ó 1 ciclos.

Desde el momento en que entras en un bucle infinito, el código que venga detrás se vuelve inaccesible, que es lo que pasa en el segundo ejemplo.

Hola NEBIRE
Esta propuesta no vale. Estás describiendo un caso muy partícular de bucles "for", los que se parecen /ajustan al patrón de Pascal

Pero en el caso de C que se da, que variables hay?, cual es el valor inicial y/o final?
En C, el bucle for es tan versátil/expresivo como el while.

EScrito de otro modo, en el primer caso hay que explicar por qué el bucle C, acaba:

while (0) ; 

Aqui no hay duda de que no hay valores iniciales, ni finales.... Solo constantes.

Yo lo veo una proposición más filosófica que práctica.
Ya de por sí la premisa, sobre el segundo fuentes, es falsa porque ese bucle no terminan nunca, al tener en la condición un 1 y por tanto siempre será cierta. Pero en ese mismo fuente se podría considerar que 1 es falso ya que ese valor detiene el bucle y, además, hace saltar al assert. Y ya que el 1 del for y el 1 del assert son diferentes por ser dos objetos diferentes pero con el mismo símbolo (es decir, no son una posición de memoria que por alguna razón ajena al programa ha cambiado, sino que realmente es 1) entonces 1 es 0.
En ese supuesto, imposible por otra parte, sí que se llegaría a la solución propuesta.

Exacto MAFUS! Lo has clavado!


Bueno, creo que ya lo tengo, chicos. Me han ayudado un poco por ahí... Y cuando lo entiendes, es una pura broma.... :D :D :D :D

La cuestión tiene que ver no tanto con C, como con dos aspectos de la algoritmia:

• la terminación de un programa
• la corrección parcial, que nos dice que si acaba, (notese la cursiva) entonces el programa computa lo que se espera de él.  

Las dos cuestiones son ciertas. Empiezo por la más extraña, la segunda, la del bucle infinito.

• Según el estandar ANSI-C, asssert solo falla cuando la evaluación del parámetro da 0 (false). En nuestro caso, assert(1), cuando 1==0, lo que es un absurdo  :o :o
• Según el estandar ANSI-C, el bucle acaba cuando la parte del discriminante da 0 (false) . En nuestro for( ; 1; ), caso, cuando 1==0 , (en terminos prácticos, nunca)   :D :D
• O sea, que cuando el bucle acabe, (no dice que acabe, dice que cuando acabe, esto es importante!) se cumplirá   1==0, lo que es la condición para que assert(1) falle.  :D :D :D :D

 :D :D :D :D Esta bien el enigma... A nadie engaña por decir que esperando lo suficiente, el assert(1) fallará... Eso sí, tiene que esperar lo suficiente, por los siglos de los siglos...

Formalmente, pura lógica...

El primer problema, que todos veíamos que acababa, también es parecido...pero ahora si nos interesa demostrar que efectivamente acaba, y nos da igual lo que pase al acabar.

En los libros de algoritmia se dice que para que un bucle acabe (terminación) tenemos que idear una quota definida positiva en el punto antes de evaluar la condición de salida  (un invariante). Como no hay variables, escogemos como quota C(n)=0... Esta quota tiene que disminuir cada vuelta, es decir 0 < 0, lo que es un absurdo.
Como va a disminuir cada vuelta, si nunca entra? Bueno, seg'un el estandar ANSI entra cuando la evualuación de la guarda es  distinta de 0, nuestro caso for( ; 0 ; ) , cuando 0!=0 (o sea nunca).

El resultado es que cuando 0!=0 entonces ocurrirá que 0 < 0. No dice que 0!=0, sino que cuando 0!=0, absurdo, entonces 0<0 (otro absurdo). Genial!  Pura lógica.

Míralo como quieras, el caso es que el compilador al final tiene que reducir cualesquiera sean las expresiones que contiene cada parte a una única salida, sea un valor constante o variable, al final tiene que ser una gramática no ambigua, sino tendría diferentes interpretaciones y desde hace décadas, se conocen algoritmos para descubrir ambigüedades en las gramáticas.

Así puedes encontrar descrito el bucle for en estos o parecidos términos (he omitido las producciones de otras sentencias de iteración que no vienen al caso):
ejemplo 1:
     stmt = for '(' [ assg ] ';' [ expr ] ';' [ assg ] ')' stmt ';'
https://www2.cs.arizona.edu/~debray/Teaching/CSc453/DOCS/cminusminusspec.html

el metasímbolo '[lo que sea]' expresa que es omitible.

ejemplo 2:
     <iteration-statement> ::= for ( {<expression>}? ; {<expression>}? ; {<expression>}? ) <statement> ;
https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm

el metasímbolo: '?' denota 0, 1 o más repeticiones.
...para eso existe la especificación de un lenguaje.
Todo lenguaje está descrito en determinados términos, hasta hace poco más de una década la notación BNF (BNF-E), se ha demostrado muy práctica, y más recientemente han salido otros modelos que son simples modificaciones del mismo.
Las especificaciones en prosa ( https://frama-c.com/download/acsl_1.2.pdf (la sección 2.4.2 resulta muy ilustrativa), aunque igualmente muy útiles, rara vez resultan tan claras como las dadas formalmente. Lo usual es que se den ambas al mismo tiempo, la prosa explica los detalles que se dan formalmente.
Así todo lenguaje de programación consta de producciones de hecho cualquier lenguaje de programación se considera una gramática libre de contexto, y se suele resumir en una tupla de 4 elementos...
L = {P, T, R, S)
Donde 'P' son todos los símbolos no terminales, variables o producciones de la gramática.
'T', son los símbolos terminales, tokens, componentes léxicos de la gramática.
'R' son las reglas de producciones, la expresión de todas las producciones.
y 'S' es el símbolo inicial, al que resume todo el lenguaje, esto es que representa: 'pertenece al lenguaje', 'es válido para este lenguaje'...

Se habla de producciones, donde cada producción no es ni más ni menos que la equivalencia resumida (como las dos línea arriba expuestas (son parciales)), a la que luego el analizador sintáctico tendrá que recurrir para determinar si es correcto y se ajusta a la descripción o no. No puede haber ambigüedades, así que tu suposición "hay que explicar por qué el bucle C, acaba", está fuera de toda necesidad de suposición. Aunque los componentes sean omitibles, y el analizador sintáctico lo de por válido luego falta el análisis semántico, que será quien se encargue de revisar lo que no puede ser fijado en reglas o resultan excesivamente complejas o previamente no se dispone de toda la info para determinar sus valores. ...y al caso concreto, un compilador debiera prever el caso de un bucle infinito en situaciones sencillas (esas lo son), o si no está adecuadamente programado, caer en dicho bucle infinito y no llegar a finalizar el análisis sintáctico (caso de derivaciones por la derecha). Lo cual siempre dependerá de la implmenetación de cada compilador en específico, y de la incorrecta interpretación de la especificación del lenguaje o en su defecto de un posible error en la propia especificación.

Ojo: No digo que tu razonamiento falle por lado alguno, tan solo digo, que resulta mucho más simple de entender si se recurre a la especificación del lenguaje. En analizador semántico, (si el sintáctico no está mal programado), debe rellenar tales datos antes o después, de tal modo que cuando le toque analizarlo (al semántico), pueda discernir si es o no un bucle infinito, y la regla se resume en la descripción que dí más arriba. Uno puede darle todas las vueltas que quiera, pero el compilador da solo las necesarias.

Una proposición falsa implica a todas las proposiciones, verdaderas o falsas. Que uno se encuentre con una aparente consistencia puede favorecer el entusiasmo pero no aporta prueba de nada; lamentablemente la pura lógica no se conmueve con expresiones emocionales :)

Pero bueno, este es tu acertijo y tus reglas. Por mí está bien, como digas.

Ejem, ejem.... Veo que has entendido parcialmente el razonamiento: de premisas falsas se llega conclusiones falsas. Es decir, el enigma podría decir que después de acabar el bucle infinito se podía llegar a cualquier cosa: que 2=2, 23=11+25, que la raíz de dos es un número racional.... Tanto verdaderas como falsas... En latín


Pero no es de recibo desacreditar mi razonamiento por la "sorpresa", o "entusiasmo" en aras a la rigurosidad implacable de la lógica... El razonamiento es absolutamente válido y correcto. Lo que no sería es decir que se concluye que 1==0.

En ningún caso se ha probado que 1=0. Fíjate bien: En el enunciado el autor marcó on terminating the program, realzando al terminar el programa.... Cosa que no ocurre nunca, y por tanto, solo ocurre "en el infinito", lo que puede dar lugar a una contradicción, según el estándar C: 1=0. A partir de ahí, como tú dices, se puede sacar lo que quieras, en particular que assert(1) fallara.

Creo que es compatible con mostrar una reacción de asombro ante  un razonamiento riguroso y objetivo. Sin "smileys" se encuentra la prueba entre etiquetas geshi...

De todas formas, gracias loretz por tu comentario. ;)