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
Last revisionBoth sides next revision
teaching:cc4101:tareas:2015-2:tarea2 [2015/10/01 00:33] – [(3.0) Interpretación sobre conjuntos finitos] racruzteaching:cc4101:tareas:2015-2:tarea2 [2015/10/13 10:17] – [(1.3) Optimización] 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>
  
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 142: 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) 
 +</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? 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>   - (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>
 > (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 166: 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 183: 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 =====