Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
teaching:cc4101:tareas:2015-2:tarea2 [2015/09/30 18:08] – [(3.0) Interpretación sobre conjuntos finitos] racruzteaching:cc4101:tareas:2015-2:tarea2 [2015/10/13 11:07] (current) – [(3.0) Interpretación sobre conjuntos finitos] racruz
Line 1: Line 1:
 ====== Tarea 2 ====== ====== Tarea 2 ======
-__Esto es un draft, todavía no es la tarea oficial!!__ 
 Esta tarea se distribuye con dos ficheros start.rkt y tests.rkt (mediante U-Cursos). Considere las definiciones del archivo start.rkt y escriba sus funciones en él. Escriba sus tests en el archivo test.rkt adjunto. Ambos ficheros deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación! Esta tarea se distribuye con dos ficheros start.rkt y tests.rkt (mediante U-Cursos). Considere las definiciones del archivo start.rkt y escriba sus funciones en él. Escriba sus tests en el archivo test.rkt adjunto. Ambos ficheros deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación!
 Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101. Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.
Line 22: Line 21:
  
 <code scheme> <code scheme>
-(<=> (=> p q) (or (¬ p) q))+(<=> (=> p q) (or (not p) q))
 </code> </code>
  
Line 31: Line 30:
  
 <code scheme> <code scheme>
-(<=> (=> p q) (or p (¬ q)))+(<=> (=> p q) (or p (not q)))
 </code> </code>
  
 El cuál por reglas de reducción no es cierta para todos los casos, pero si es satisfacible El cuál por reglas de reducción no es cierta para todos los casos, pero si es satisfacible
-pues cuando p y q son ambos falsos el predicado es verdadero.+pues cuando ''%%p%%'' y ''%%q%%'' son ambos falsos el predicado es verdadero.
  
 ==== Funciones de primer orden ==== ==== Funciones de primer orden ====
Line 48: Line 47:
 El siguiente listado muestra la grámatica BNF de nuestro lenguaje. El siguiente listado muestra la grámatica BNF de nuestro lenguaje.
 <code> <code>
-<prog> ::= <fun-def>* in <expr>+<prog> ::= (<fun-def>* in <expr>)
  
 <fun-def> ::= (define (<id> <id>) <expr>) <fun-def> ::= (define (<id> <id>) <expr>)
Line 60: Line 59:
          | (=> <expr> <expr>)          | (=> <expr> <expr>)
          | (<=> <expr> <expr>)          | (<=> <expr> <expr>)
-         | (all <id> <Set> <expr>)  +         | (all <id> in <expr> <expr>)  
-         | (exist <id> <Set> <expr>)+         | (exists <id> in <expr> <expr>)
          | (< <expr> <expr>)          | (< <expr> <expr>)
          | (= <expr> <expr>))          | (= <expr> <expr>))
Line 79: Line 78:
 </code> </code>
 El AST que deberá usar para representar dicha gramática se encuentra adjunto (en el fichero start.rkt). Note que la gramática permite =>, <=> y xor como azucares sintácticos (no tienen equivalente directo en el AST). Su parser debe encargarse de reemplazarlas por expresiones equivalentes en el AST adjunto (sin necesidad de crear nuevos nodos, lo cual será verificado).  El AST que deberá usar para representar dicha gramática se encuentra adjunto (en el fichero start.rkt). Note que la gramática permite =>, <=> y xor como azucares sintácticos (no tienen equivalente directo en el AST). Su parser debe encargarse de reemplazarlas por expresiones equivalentes en el AST adjunto (sin necesidad de crear nuevos nodos, lo cual será verificado). 
-  -(0.7) Implemente la función ''%%parse-expr%%'' para parsear expresiones  +  -(0.7) Implemente la función ''%%(parse-expr s-expr)%%'' para parsear expresiones  
-  -(0.3) Implemente la función ''%%parse-prog%%'' para parsear programas+  -(0.3) Implemente la función ''%%(parse-prog s-expr)%%'' para parsear programas <code scheme> 
 +> (parse-prog '((define (add1 x) (+ x 1)) 
 +                in 
 +                (add1 2))) 
 +(program (list (fundef 'add1 'x (plus (id 'x) (num 1)))) (app 'add1 (num 2))) 
 +</code> 
 Considere usar las siguientes expresiones equivalentes para reemplazar =>, <=> y xor: Considere usar las siguientes expresiones equivalentes para reemplazar =>, <=> y xor:
     * ''%%p => q%%'' es equivalente a ''%%¬p v q%%''     * ''%%p => q%%'' es equivalente a ''%%¬p v q%%''
Line 95: Line 100:
     * b) Sea un conjunto P = { ... } de números enteros. Existe un elemento en el conjunto que es primo     * b) Sea un conjunto P = { ... } de números enteros. Existe un elemento en el conjunto que es primo
     * c) Todos los elementos de un conjunto P = { ... } de números enteros son primos      * c) Todos los elementos de un conjunto P = { ... } de números enteros son primos 
-    * e) Para todo par a, b en un conjunto N de naturales se cumple a<sup>2</sup> + b<sup>2</sup> < (a+b)<sup>2</sup>+    * e) Para todo par a, b en un conjunto N de naturales se cumple a<sup>2</sup> + b<sup>2</sup> < (a+b)<sup>2</sup> 
   //Nota: Como los conjuntos (S, P, N) son finitos y definidos por usted, se pueden usar conjuntos auxiliares (estáticamente conocidos) para expresar sus predicados. En caso de que los conjuntos fueran finitos, pero arbitrarios, ¿que necesitaría para poder expresar los predicados b) y c) de manera genérica?//   //Nota: Como los conjuntos (S, P, N) son finitos y definidos por usted, se pueden usar conjuntos auxiliares (estáticamente conocidos) para expresar sus predicados. En caso de que los conjuntos fueran finitos, pero arbitrarios, ¿que necesitaría para poder expresar los predicados b) y c) de manera genérica?//
   - (0.5) Defina la función ''%%(subst expr x val)%%'' que substituye en la expresión ''%%expr%%'' el valor ''%%val%%'' por la variable ''%%x%%'' (preservando el scope léxico). Ejemplos: <code scheme>   - (0.5) Defina la función ''%%(subst expr x val)%%'' que substituye en la expresión ''%%expr%%'' el valor ''%%val%%'' por la variable ''%%x%%'' (preservando el scope léxico). Ejemplos: <code scheme>
-> (subst (parse-expr '(if (< x 1) (% x y) (+ x y))) 'x 1) +> (subst (parse-expr '(if (< x 1) (% x y) (+ x y))) 'x (num 1)) 
-(my-if (lesser 1 (num 1)) (mod 1 (id 'y)) (plus 1 (id 'y))) +(my-if (lesser (num 1) (num 1))  (mod (num 1) (id 'y))  (plus (num 1) (id 'y))) 
-> (subst (parse-expr '(with (x 5) (+ x y))) 'x 1) +> (subst (parse-expr '(with (x 5) (+ x y))) 'x (sub (num 1) (num 2))) 
-(with 'x (num 5) (plus (id 'x) (id 'y))) +(with 'x (num 5) (plus (id 'x) (id 'y)))
 </code> </code>
   - (1.0) Defina la función ''%%(eval-expr expr)%%'' que evalúa una expresión con cuantificadores sobre conjuntos acotados. Utilice la función ''%%subst%%'' en su implementación (para sustituir identificadores por su valor). Recuerde que basta con que para al menos un valor del cuerpo del cuantificador existencial (exists) evalúe a ''%%#t%%'' para que toda la expresión evalúe a ''%%#t%%'', mientras que para el cuantificador universal (all) se requiere que todos los valores del cuerpo sean ''%%#t%%'' para evaluar a ''%%#t%%''. <code scheme>   - (1.0) Defina la función ''%%(eval-expr expr)%%'' que evalúa una expresión con cuantificadores sobre conjuntos acotados. Utilice la función ''%%subst%%'' en su implementación (para sustituir identificadores por su valor). Recuerde que basta con que para al menos un valor del cuerpo del cuantificador existencial (exists) evalúe a ''%%#t%%'' para que toda la expresión evalúe a ''%%#t%%'', mientras que para el cuantificador universal (all) se requiere que todos los valores del cuerpo sean ''%%#t%%'' para evaluar a ''%%#t%%''. <code scheme>
Line 136: Line 141:
                                   (set (1 3 5))                                   (set (1 3 5))
                                   (set (2 4))))))                                   (set (2 4))))))
-(list (num 2) (num 4)) +;Edit: (list (num 2) (num 4)) por: 
-</code> En caso de evaluar un programa que aplique una función no definida deberá lanzar un error "function not defined". Note que ''%%(eval-expr expr)%%'' se debe comportar como ''%%(eval-prog (program expr '()))%%''. En caso de evaluar un programa que use una variable no definida deberá lanzar un error "unbound identifier".  +(list 2 4) 
-  - (0.5) Defina la función ''%%(satisfiable? s-expr)%%'' para determinar si un predicado booleano es satisfacible para algún valor de verdad de sus variables libres. Hint: use el cuantificador de existencialidad sobre las variables libres y el conjunto predefinido ''%%{#t ,#f}%%''. <code scheme>+</code> En caso de evaluar un programa que aplique una función no definida deberá lanzar un error "function not defined". Note que ''%%(eval-expr expr)%%'' se debe comportar como ''%%(eval-prog (program '() expr))%%''. En caso de evaluar un programa que use una variable no definida deberá lanzar un error "unbound identifier".  
 +  - (0.5) Defina la función ''%%(satisfiable? expr)%%'' para determinar si un predicado booleano es satisfacible para algún valor de verdad de sus variables libres. Hint: use el cuantificador de existencialidad sobre las variables libres y el conjunto predefinido ''%%{#t ,#f}%%''. <code scheme>
 > (satisfiable? (parse-expr '(or p q))) > (satisfiable? (parse-expr '(or p q)))
 #t #t
-> (satisfiable? (parse-expr '(and p (: p))))+> (satisfiable? (parse-expr '(and p (not p))))
 #f #f
 > (satisfiable? (parse-expr '(<=> (=> p q) (or p q)))) > (satisfiable? (parse-expr '(<=> (=> p q) (or p q))))
 #t #t
-> (satisfiable? (parse-expr '(<=> (=> p q) (and p (: q)))))+> (satisfiable? (parse-expr '(<=> (=> p q) (and p (not q)))))
 #f #f
 </code> </code>
Line 160: Line 166:
     * ¬¬p <=> p     * ¬¬p <=> p
   Con esto se puede asegurar que en un programa válido, después de las negaciones ¬ no aparecen las expresiones: v, ^, ∀, ∃, ¬. Entiéndase programa válido (a este nivel), aquellos programas que no contienen operaciones invalidas como ''%%(+ #f 1)%%''. Ejemplos: <code scheme>   Con esto se puede asegurar que en un programa válido, después de las negaciones ¬ no aparecen las expresiones: v, ^, ∀, ∃, ¬. Entiéndase programa válido (a este nivel), aquellos programas que no contienen operaciones invalidas como ''%%(+ #f 1)%%''. Ejemplos: <code scheme>
-> (simplify-negations (parse-expr '(¬ (or (¬ p) (¬ q))))) +> (simplify-negations (parse-expr '(not (or (not p) (not q)))))
-(my-and (id 'p) (id 'q)) +
-> (simplify-negations (parse-expr '(¬ (¬ (¬ (or p q))))))+
 (my-and (id 'p) (id 'q)) (my-and (id 'p) (id 'q))
 +> (simplify-negations (parse-expr '(not (not (not (or p q))))))
 +(my-and (my-not (id 'p)) (my-not (id 'q)))
     </code>     </code>
   -(0.5) Defina la función ''%%(simplify expr)%%'' que se encargue de remplazar las siguientes expresiones: ''%%(and #f p)%%'', ''%%(or #t p)%%'', ''%%(¬ #t)%%'', ''%%(¬ #f)%%'', ''%%(or p p)%%'' y ''%%(and p p)%%'' por versiones más simples en el predicado representado por ''%%expr%%''. Asegúrese de utilizar la función ''%%simplify-negations%%'' definida anteriormente para uniformar las expresiones pues el predicado p puede ser arbitrariamente complejo. Hint: use la función ''%%equal?%%'' para verificar igualdad de predicados arbitrariamente complejos. No es necesario verificar permutaciones. <code scheme>   -(0.5) Defina la función ''%%(simplify expr)%%'' que se encargue de remplazar las siguientes expresiones: ''%%(and #f p)%%'', ''%%(or #t p)%%'', ''%%(¬ #t)%%'', ''%%(¬ #f)%%'', ''%%(or p p)%%'' y ''%%(and p p)%%'' por versiones más simples en el predicado representado por ''%%expr%%''. Asegúrese de utilizar la función ''%%simplify-negations%%'' definida anteriormente para uniformar las expresiones pues el predicado p puede ser arbitrariamente complejo. Hint: use la función ''%%equal?%%'' para verificar igualdad de predicados arbitrariamente complejos. No es necesario verificar permutaciones. <code scheme>
Line 177: Line 183:
 (my-or (my-and (id 'p) (id 'q)) (my-and (id 'q) (id 'p)))                     (my-or (my-and (id 'p) (id 'q)) (my-and (id 'q) (id 'p)))                    
 </code> </code>
-  -(0.3) Defina la función ''%%(o-satisfiable? s-expr)%%'' que realiza optmización (usando ''%%simplify%%'') antes de evaluar. De un ejemplo de un predicado que toma mucho más tiempo de evaluar con la función ''%%satisfiable?%%'' que con ''%%o-satisfiable?%%''+  -(0.3) Defina la función ''%%(o-satisfiable? expr)%%'' que realiza optmización (usando ''%%simplify%%'') antes de evaluar. De un ejemplo de un predicado que toma mucho más tiempo de evaluar con la función ''%%satisfiable?%%'' que con ''%%o-satisfiable?%%''
  
 ===== (0.7) Sistema de Tipos ===== ===== (0.7) Sistema de Tipos =====