Transaction ordering dependence problem

octubre 8, 2018octubre 9, 2018 miguelpiniaDeja un comentario

Debido a la naturaleza del entorno de ejecución de los smart contracts, en los que se maneja dinero, existe un incentivo para que existan usuarios maliciosos para los que exploten las debilidades de implementación y obtengan lucro de dichas debilidades.

Consideremos el escenario, donde la blockchain se encuentra en un estado $\Delta$ y hay un bloque nuevo que incluye dos transacciones ( $T_{i}$ y $T_{j}$ ) que invocan a un mismo contrato. En tal escenario, los usuario desconocen cual es el estado en que se encuentra el contrato cuando se aplican la ejecución de su contrato. Por ejemplo, $T_i$ se puede aplicar en el estado $\Delta[\alpha]$ o en el estado $\Delta'[\alpha]$ que es cuando ya se aplicó $T_{j}$ . Esto implica que hay una discrepancia entre el estado que se encuentra el contrato que los usuarios invocan, y el estado actual depende del estado en que se hayan realizado las ejecuciones. Sólo el minero puede determinar el orden en que se ejecutan las transacciones. Esto tiene como consecuencia que el estado del contrato depende del orden en que el minero invocaba a las transacciones. Esto se conoce como Transaction Ordering Dependence (TOD).

TOD tiene puede ser utilizado para realizar ataques al estado de la blockchain de modo que se puedan obtener beneficios del modo en que se ejecutan estas transacciones.

Observemos el siguiente smart-contract que representa una tienda que vende un producto:

contract MarketPlace {
  uint public price;
  uint public stock;
  /.../
  function updatePrice(uint _price) {
    if (msg.sender == owner) price = _price;
  }
  function buy(uint quant) returns (uint) {
    if (quant > stock || msg.value < quant * price) throw;
    stock -= quant;
    /.../
  }
}

A partir del código anterior, supongamos la siguiente ejecución dentro de la blockchain:

$T_{c}$ y $T_{d}$ son transacciones que son invocadas de forma simultanea y son obtenidas por el mismo minero. $T_{c}$ corresponde a la transacción asociada con la compra de un objeto a la tienda y $T_{d}$ es la transacción que actualiza el precio del producto.
El minero mina el bloque que contiene a $T_{c}$ y a $T_{d}$
$T_{c}$ se ejecuta y compra.
$T_{d}$ se ejecuta y actualiza el producto.
Se escribe el estado de la ejecución de las transacciones dentro del bloque y se actualiza el estado $\Delta$ de la blockchain.

En esta ejecución todo funcionó de forma esperada sin que fallara nada. Pero que pasa si consideramos la siguiente ejecución:

$T_{c}$ y $T_{d}$ son transacciones que son invocadas de forma simultanea y son obtenidas por el mismo minero. $T_{c}$ corresponde a la transacción asociada con la compra de un objeto a la tienda y $T_{d}$ es la transacción que actualiza el precio del producto.
El minero mina el bloque que contiene a $T_{c}$ y a $T_{d}$
$T_{d}$ se ejecuta y actualiza el producto.
$T_{c}$ se ejecuta y compra.
Se escribe el estado de la ejecución de las transacciones dentro del bloque y se actualiza el estado $\Delta$ de la blockchain.

En este caso el cliente compró el producto a un precio más caro que el que él esperaba. Esto se traduce en que el dueño se benefició de la forma en que la transacción se ejecutó, aunque esto no fue de forma consiente. ¿Qué pasaría si nos aprovechamos de esta falla?

Veamos un caso más en el que el orden de la ejecución de los contratos puede causar un estado imprevisto en la ejecución bajo TOD. Sea el siguiente código:

contract Puzzle {
  address public owner;
  bool public locked;
  uint public reward;
  byte32 public diff;
  bytes public solution;

  function Puzzle() {
    owner = msg.sender;
    reward = msg.value;
    locked = false;
    diff = bytes(111111);
  }

  function () {
    if (msg.sender == owner) {
      if (locked) throw;
      owner.send(reward);
      reward = msg.value;
    } else {
      if (msg.data.length > 0) {
        if (locked) throw;
        if (sha256(msg.data) < diff) {
          msg.sender.send(reward);
          solution = msg.data;
          locked = true;
        }
      }
    }
  }
}

El contrato anterior recompensa a los usuarios quienes resuelven un acertijo computacional. Sólo si el hash del mensaje enviado por el jugador es menor que una diferencia predefinida, entonces, se paga la recompensa al jugador y se bloquea el contrato para que nadie más intente jugar después.

Igualmente consideremos dos ejecuciones de el contrato Puzzle en una blockchain. La primera ejecución la podemos describir de la siguiente forma:

$T_{d}$ y $T_{j}$ son dos transacciones que son invocadas de forma simultanea y son obtenidas por el mismo minero. $T_{d}$ es la transacción enviada por el dueño del contrato y $T_{j}$ la transacción del usuario que envía una solución válida para reclamar la recompensa.
El minero mina el bloque que contiene a $T_{d}$ y $T_{j}$
$T_{d}$ se ejecuta y actualiza la recompensa.
$T_{j}$ se ejecuta y recibe la nueva recompensa.
Se escribe el estado de la ejecución de las transacciones dentro del bloque se actualiza el estado $\Delta$ de la blockchain.

En este caso el jugador esperaba recibir la recompensa que el observó cuando envió su solución, pero el recibió una recompensa distinta, el cuál pudo haber sido un accidente, pero ¿y si no fue un accidente?

Transaction ordering dependence

octubre 8, 2018octubre 8, 2018 miguelpiniaDeja un comentario

¿Qué sucede cuando un contrato inteligente obtiene varias llamadas similares en el mismo bloque? Consideremos por ejemplo el siguiente Smart Contract:

contract greeter {
    string name;

    function setName(string name_) {
        name = name_;
    }

    function getName() constant returns(string) {
        return name;
    }
}

Entonces, propongamos las siguientes preguntas acerca de la ejecución y evaluación de este contrato inteligente.

¿Que sucede si Bob, Alice y Eve llaman al contrato Greeter y las tres llamadas son ejecutadas en el mismo bloque?: Las tres llamadas podrían invocarse, no necesariamente en secuencia, y el nombre en la última transacción es el que se va a almacenar en el bloque minado.
¿Todos van a obtener la respuesta propia con su propio nombre?: No. La función getName() debería regresar el nombre que se almacenó en el bloque minado, el cuál fue establecido por la última transacción.
¿Va a ejecutarse el contrato tres veces?: Si. La función setName(...) debería de ejecutarse tres veces.

Describamos cuál es el orden y el comportamiento concurrente de múltiples llamadas a un contrato en un bloque minado. Lo primero que hay que observar es que el minero ganador del bloque, es el que va a decidir el orden en que las transacciones son incluidas en el bloque. A partir de esto notemos que si las transacciones son de diferentes direcciones, estas van a ser ejecutadas en un orden arbitrario, pero si las transacciones provienen de una misma dirección, las ejecuciones siempre van a ser ejecutadas en el orden definido por los nonce de las transacciones.

Retomando la cuestión anterior, tenemos que:

La máquina virtual de ethereum debería de llamar setName(...) tres veces, pero la secuencia en que se van a ejecutar las transacciones va a ser ejecutada de forma arbitraria asumiendo que las transacciones provienen de diferentes direcciones (From:, diferentes cuentas).
El campo del nombre va a cambiarse tres veces, pero el nombre en la transacción final debería de ser almacenada en el bloque minado.
Invocaciones a getName() van a devolver el nombre almacenado en el bloque minado.
Invocaciones a getName() desde un smart contract ejecutado en el mismo bloque debería de obtener el valor de cualquiera de las ejecuciones de las transacciones asociadas al contrato Greeter.

Un ejemplo de ejecución de esto sería algo como lo siguiente:

Las transacciones son enviadas en el orden Alice, Bob y Eve.
El minero ganador ejecuta las transacciones en el orden Eve, Bob y Alice.
Un smart contract se ejecuta entre las transacciones de Bob y Alice.
El smart contract invoca getName() regresando Bob.
Después de que el bloque ha sido minado, el nombre almacenado en el bloque es Alice. Cualquier llamada hacia getName() va a regresar Alice.

Ejercicio 1

septiembre 17, 2018septiembre 17, 2018 miguelpiniaDeja un comentario

Una máquina de Turing no-determinista es total si para toda entrada cada una de sus ejecuciones eventualmente se detiene. Demuestra que un lenguaje es decidible si y sólo si existe una máquina de Turing no-determinista total que lo decide.

Demostración

Sea $L(M)$ un lenguaje y $M$ una máquina de Turing.

$\Rightarrow$ Por hipótesis $L(M)$ es decidible, esto implica que existe una máquina de Turing determinista $M$ que lo decide. Y cómo cualquier máquina de Turing determinista es autómicamente no-determinista, entonces, se cumple que dado un lenguaje decidible existe una máquina de Turing no determinista que lo decide.

$\Leftarrow$ Supongamos que existe una máquina de Turing no determinista $N$ que decide $L(M)$ . Esto implica que para cualquier entrada $n \in L(M)$ , todas las ramas de ejecución de $N$ esa siempre termina. Utilizando el teorema que dice que toda máquina de Turing no determinista tiene una máquina de Turing determinista, entonces construimos $M$ una máquina de Turing determinista equivalente a $N$ . $M$ tiene la siguiente forma:

Por hipótesis todas las ramas de $N$ terminan, entonces, si alguna de las ramas de $N$ acepta, entonces $M$ acepta.
Si alguna de las ramas de $N$ rechaza, entonces $M$ rechaza.
No se puede dar el caso de que $N$ no termine (por hipótesis).

Como $N$ siempre termina en todas sus ejecuciones, $M$ siempre va a terminar, siguiendo la construcción anterior. Por lo que por definición, $L(M)$ es decidible por una máquina de Turing no determinista.

$\therefore L(M)$ es decidible $\iff \exists$ MT M no-determinista que lo decide.

Antecedentes de blockchains

septiembre 2, 2018septiembre 2, 2018 miguelpiniaDeja un comentario

Cypherpunks

Esta historia inicia con cypherpunks, resistencia y búsqueda de cambios en el sistema. Los punks, nacen en los años 70’s como una subcultura urbana cuya filosofía se puede resumir en:

«Hazlo tu mismo» ó «Hazlo a tu manera»
Rechaza los dogmas y cuestiona lo establecido
Desprecia las modas y la sociedad de masas.

Los punks siempre han sido caracterizados como la parte rebelde y anti-sistema de la sociedad. Al mismo tiempo en que nacen los punks, la criptografía era utilizada principalmente en secreto por militares y espías, pero todo cambia con la salida al público de dos documentos, el primero que fue publicado por el gobierno estadounidense siendo el Data Encryption Standar, el cuál es un sistema de cifrado simétrico en bloques, así como el trabajo de criptografía de llave pública de Whitfield Diffie y Martin Hellman.

Con estos trabajos, el origen de los cypherpunks viene de la mano del criptografo David Chaum donde desarrolla ideas sobre dinero digital anónimo en el artículo «Security without Identification: Transaction Systems to Make Big Brother Obsolete» y posteriormente con «Untraceable Electronic Cash». Con las ideas planteadas por Shaum y las ideas de Richard Stallman sobre el software libre, un grupo de personas fundan Cygnus Solutions, quienes proveían soporte comercial a software libre. Varios de los empleados de esta empresa fueron «mantenedores» de varios paquetes de software GNU. También fueron activistas que abogaban por la necesidad de la privacidad en la sociedad abierta de la era electrónica. De forma humorística, Jude Milhon (mejor conocida por su pseudonimo St. Jude), acuñe el término cypherpunk.

Los cypherpunks llevaron una lista de distribución de correo, la cuál fue muy activa donde se discutieron temas muy variados, que fueron desde matemáticas, criptografía, ciencias de la computación, discusión política y filosófica, argumentos personas hasta ataques y spam.

Las ideas básicas de este grupo se ṕueden encontrar en el documento «A cypherpunk’s Manifiesto», el cuál fue escrito por Eric Hughes en 1993. Los cypherpunks están dedicadados a la construcción de sistemas anónimos. Defiende la privacidad con criptografía, con sistemas de envio de correo anónimos, con firmas digitales y con dinero electrónico.

El último punto, es lo que posteriormente, junto con la crisis de 2008, daría paso a la creación de las blockchains y las criptomonedas.

Inicio del dinero electrónico, crisis del 2008 y bitcoin

Actualmente para realizar el intercambio de bienes y servicios, hacemos uso de dinero, el cuál es un medio que permite facilitar las transacciones, compra y venta, así como un medio para guardar valor. Este dinero es controlado por un banco central (nacional), con el objetivo de que exista suficiente para que las necesidades de las distintas actividades económicas se satisfagan.

¿Cómo funcionan los pagos en linea?

Cuando compramos un producto en línea, digamos en Amazon, utilizamos tarjetas de débito o crédito para poder pagarlos y que el vendedor en linea nos entregue el producto solicitado.

Los eventos que ocurren durante ese proceso suelen ser:

Llenar el carrito de compras con los productos que queremos comprar
Ingresamos los detalles de la tarjeta de débito o crédito para poder realizar el pago.
Enviar la orden de solicitud.
Amazon toma los detalles de la tarjeta de crédito y confirma con el sistema (sistema financiero que pueden ser bancos, compañías de tarjetas de crédito o algún otro intermediario).
El sistema confirma o cancela tu orden basado en que si hay suficientes fondos disponibles en tu cuenta.

Otro modelo existente es el que propone Paypal, donde funge como un intermediario, es decir, Paypal se sitúa entre tu y el vendedor y actúa como un tercero confiable. Paypal maneja la transacción en su nombre y notifican a Amazon. La ventaja de trabajar con Paypal es que no le proporcionas tus datos de la tarjeta de crédito/débito al vendedor. Sin embargo, es posible que los protocolos de Paypal tengan brechas de seguridad o ataques.

Actualmente es más fácil y cómodo proveer la información de tarjetas de crédito/débito a restaurantes, tiendas en linea y sitios de viaje. Esto debido a que no existen los mismos riesgos de realizar transacciones en linea que en los años 90.

Por otro lado, el tener un intermediario al momento de realizar una transacción, implica que no tienes privacidad acerca de las cosas que estás comprando o consumiendo, además de posibilidades de que existan brechas de seguridad en caso de que los bancos y otras compañías no lleven a cabo metodologías y prácticas de seguridad de forma correcta.

Debido a los riesgos anteriores, algunas personas buscaron tener alternativas al uso de bancos y otras entidades para servir de intermediarios entre particulares.

David Chaum y el doble gasto

En los años 80, se idearon propuestas para tener dinero electrónico, de modo que fuera similar a su equivalente físico, es decir, que tuviera las propiedades similares a las que tiene el dinero, siendo estas:

El banco no sea capaz de rastrear la forma en que lo gastas.
Permitir realizar transacciones offline si tener que esperar por una entidad de terceros para aprovar la transacción.

En los años 80, David Chaum introdujo las primeras ideas sobre dinero digital seguro, a través de primitivas criptográficas conocidas como firmas ciegas. Sus ideas permitían que las personas pudieran obtener dinero digital de un banco y gastarlo de una forma que no sea trazable por el banco o cualquier otro usuario.

Un problema que también se resolvió con las primitivas criptográficas que propuso David Chaum fue el del doble gasto (double spending). Este problema se da debido a la naturaleza del software; es fácilmente duplicar un recurso electrónico digital en las computadoras, entonces, si tuvieramos una moneda digital, sería fácilmente hacer dos o más copias que se pueden distribuir entre las personas.

Una forma de resolver el problema anterior, es el poner números seriales únicos en cada moneda digital y utilizar firmas criptográficas. Cuando una persona recibiera una moneda con tu firma en ella, entonces puede consultar si la moneda no ha sido gastada previamente utilizando el número serial. Así, el receptor pueden decidir si acepta la moneda o la rechaza. Si aceptan la moneda, se registra que ya se gasto en un ledger y así se podría continuar para registrar cuando se gasta una moneda. Este método funciona, pero dificilmente eficiente en escenarios de la vida real. Además de que no elimina la privacidad que se buscaba.

El otro método es el propuesto por David Chaum con las firmas ciegas, en el que se evita el doble gasto. Esta técnica se puede explicar de la siguiente forma:

Supongamos que Alice y Bob están realizando una transacción. Entonces Bob genera una nueva moneda para Alice y Alice elige el número de serie que después verificará el banco, el cuál le servirá para que Alice pueda obtener los recursos de Bob. Ese número de serie no es necesario que Bob lo conozca, Alice le pide a Bob que firme la moneda con el número de serie, entonces, con esto, Alice puede obtener posteriormente los recursos de Bob del banco. Sin embargo, esta técnica funciona, pero aún requiere de un servidor central de una autoridad central como el banco.

En 1989 David Chaum tomo estas ideas y comercializó con ellas para formar su compañía llamada DigiCash. Esta compañía fue pionera en la creación de sistemas y procesamiento de pagos en linea. La implementación del sistema de DigiCash fue llamada Ecash. De manera sorpresiva los bancos querían implementar la tecnología de Chaum. Ecash está basada en los protocolos de Chaum, estos protocolos mantienen a los clientes anónimos e inrastreables, pero no hace lo mismo con los mercaderes, ya que tienen que devolver las monedas tan pronto las reciben, por lo que su anonimidad se pierde. Eventualmente DigiCash cae en la ruina por su falta de convencimiento a los bancos.

Crisis del 2008 y Bitcoin

El problema de la crisis del 2008 en Estados Unidos, es causada por los bancos y el gobierno estadounidense. Al principio, la gente ganaba poco, y lo poco que ganaban lo guardaban en sus casas para mantener sus ingresos. Cuando empezaron a ganar más dinero, era claro que ya no podían seguir guardando sus recursos en casa, debido que podrían perderse o ser robados, por lo que empezaron a depositar sus ingresos en

Criptografía

Las criptomonedas y las blockchains, como ya se mencionó, hacen uso de la criptografía para poder operar de forma correcta de modo que resuelvan los problemas de anonimidad, seguridad y doble gasto. Entonces, para poder entender todos los conceptos asociados con blockchaino, es necesario establecer una serie de conceptos sobre criptografía.

La criptografía moderna aparece después de la segunda guerra mundial con la aparición de las técnicas de la criptografía de llave pública, así como la adopción del FIPS ??? (DES – Data Encryption Standar) como un estandar federal de procesamiento de información por parte de los Estados Unidos, como herramienta de cifrado simétrico, siendo el mecanismo de crifrado más conocido de la historia. Otros métodos de cifrado simétrico son: Triple DES, RC5, IDEA y ????.

Con respecto al cifrado de llave pública, en 1976, los doctores Diffie y Hellman publican New Directions in Cryptography, este artículo introducen el concepto de la llave pública, así como proveer un método ingenioso para el intercambio de llaves de crifrado. La fortaleza de la técnica propuesta reside en la intratabilidad del problema del logaritmo discreto. A pesar de que los autores no proveyeron una implementación, otros autores se basaron en la idea propuestas por Diffie y Hellman para construir otros esquemas de cifrado público. Por ejemplo, Rivest, Shamir y Adleman, en 1978 diseñan el esquema de cifrado de llave pública y de esquema de firmas digitales conocida como RSA (nombrado así por las iniciales de sus autores). La fortaleza de este sistema está basado el problema de la intratabilidad de la factorización de números primos muy grandes. Otro esquema muy conocido basado en el problema de logaritmo discreto, es el que encontró ElGamal en 1985.

Seguridad de la información y criptografía

La criptografía se entiende en términos de problemas relacionados a la seguridad de la información. Por ejemplo, cuando todas las entidades que participan en una transacción, deben tener cierta confidencia que ciertos objetivos asociados con seguridad de la información deben satisfacerse.

Tales objetivos son los siguientes:

Privacidad o confidencialidad
Integridad de los datos
Autenticación o identificación
Autenticación de mensajes
Firmas
Autorización
Validación
Control de acceso
Certificación
Timestamping
witnessing
Recepción
Confirmación
Ownership
Anonimidad
No-repudiación
Revocación

La criptografía va a resolver algunos de estos objetivos.

Definición: La criptografía es el estudio de técnicas matemáticas relacionadas

a aspectos de seguridad tales como confidencialidad, integridad de datos, autenticación de entidades y autenticacíon del origen de los datos.

De las metas descritas en la definición tenemos:

Confidencialidad es un servicio usado para mantener el contenido de la información disponible para aquellos autorizados para tenerla. Secrecía es un término sinónimo con confidencialidad y privacidad.
Integridad de datos es un servicio el cual evita la alteración no autorizado de los datos. Para asegurar integridad de los datos, debe tener la habilidad para detectar la manipulaciónde datos por entidades no autorizadas.
Autenticación es un servicio relacionado a la identificación. Esta función aplica para todos los participantes.
No repudiación es un servicio que previene que una entidad de denegar compromisos o acciones anteriores.

Bibliografía

Pruebas generativas

noviembre 22, 2016noviembre 23, 2016 miguelpiniaDeja un comentario

¿Qué son las pruebas generativas?

Las pruebas generativas son pruebas sobre código que se realizan usando datos «aleatorios» sobre las funciones que nosotros escribimos. La idea es probar estos datos «aleatorios» contra propiedades de la salida deseada de las funciones.

En Clojure existe una biblioteca llamada clojure.test.check, la cuál se encarga de proveer herramientas para construir estas pruebas generativas.

Las pruebas generativas, básicamente se encargan de separar la definición del dominio de entrada respecto al concepto de generadores y validadores.

Pruebas en clojure

Clojure, a través del espacio de nombres clojure.test, provee funciones y macros para realizar pruebas unitarias en sobre las funciones que implementemos en clojure.

Las pruebas en clojure generalmente lucen de la siguiente forma:

(require '[clojure.test :refer [deftest]])
(defn add
  "Realiza la suma de |x| con |y|"
  [x y]
  (+ x y))

(deftest add-x-to-y
  (is (= 5 (add 2 3))))

El ejemplo anterior, es un ejemplo pequeño de como realizar pruebas unitarias en clojure. Pero en ocasiones esto no es suficiente, para esto, se define una nueva forma de probar el código que implementemos utilizando datos generados de forma «aleatoria» para introducirla a nuestras funciones y a partir de las propiedades de la salida, determinar si estas funciones son correctas o no. Este tipo de pruebas se les conoce como pruebas generativas.

El espacio de nombres clojure.test.check (una biblioteca inspirada en Quickcheck de Haskell), provee una serie de funciones y macros para poder crear pruebas generativas sobre el código que nosotros escribimos. Estas pruebas generativas como mencionamos previamente, están sustentadas sobre la prueba de propiedades de las salidas de una función.

Ejemplos de como realizar pruebas generativas usando clojure.test.check las podemos encontrar en la documentación del mismo proyecto, la cuál podemos acceder a través de esta liga.

Aún así se agrega a este documento un ejemplo pequeño como muestra:

(require '[clojure.test.check :as tc]
         '[clojure.test.check.generators :as gen]
         '[clojure.test.check.properties :as prop])

(defn ascending?
  "clojure.core/sorted? doesn't do what we might expect, so we write our own
  function"
  [coll]
  (every? (fn [[a b]] (<= a b))
          (partition 2 1 coll)))

(def property
  (prop/for-all [v (gen/vector gen/int)]
    (let [s (sort v)]
      (and (= (count v) (count s))
           (ascending? s)))))

;; test our property
(tc/quick-check 100 property)

Entendiendo el como usar las pruebas generativas

Del código anterior, se invocan los siguientes espacios de nombres:

(require '[clojure.test.check :as tc]
         '[clojure.test.check.generators :as gen]
         '[clojure.test.check.properties :as prop])

Los cuáles son los encargados de proveer funciones y macros para la generación y prueba de funciones. De estos espacios de nombres podemos observar las siguientes características:

tc: Contiene una única función quick-check que es utilizada probar funciones con valores generados por una función generador.
gen: Contiene funciones para generar datos basados en propiedades.
prop: Provee sugar macros para definir parámetros y funciones para ser probadas por los generadores.

Más info sobre estos espacios de nombres, pueden ser consultados en clojure.test.check

Una vez identificadas los distintos tipos de funciones y macros provistos por clojure.test.check, procedemos a definir una función y una propiedad a probar para esa función.

(defn ascending?
  "clojure.core/sorted? doesn't do what we might expect, so we write our own
  function"
  [coll]
  (every? (fn [[a b]] (<= a b))
          (partition 2 1 coll)))

Lo anterior define una función que verifica que para cada para par dentro de la colección que pasamos como parámetro, esta siempre sea ordenada, i.e. exista un ordenamiento.

Una vez hecho, procedemos a escribir la propiedad:

(def property
  (prop/for-all [v (gen/vector gen/int)]
    (let [s (sort v)]
      (and (= (count v) (count s))
           (ascending? s)))))

La cuál verifica que podamos ordenar una colección y además que dicha colección se encuentra ordenada de forma ascendente. La colección usada es generada por (gen/vector gen/int), la cuál es una combinación de generadores que dice que genere un vector de enteros y lo guarde en una variable v, la cuál después se la pasamos a la forma para evaluar nuestra expresión.

Hecho lo anterior, se utiliza la función tc/quick-check, indicándole el número de muestras a generar, en este caso le decimos que 100 de la siguiente forma:

(tc/quick-check 100 property)

Hasta aquí vamos a detener este artículo introductorio, esperemos que podamos continuar con la generación de bases de datos de batería para probar nuestro código, para ello intentaremos hacer uso de las pruebas generativas de clojure.test.check.

Prettify-symbols-mode

noviembre 4, 2016noviembre 4, 2016 miguelpiniaDeja un comentario

Desde la versión 24.4 de emacs se incluye un nuevo modo llamado prettify-symbols-mode, el cuál esta planeado para remplazar la representación de varios identificadores/símbolos usados en los lenguajes de programación por caracteres más estéticos.

Por ejemplo, en el modo lisp (emacs-lisp también), al escribir la palabra reservada lambda, visualmente se transforma en el símbolo λ, pero que en el texto se sigue conservando la palabra escrita.

Esto permite que escribir en diversos lenguajes tenga una notación un poco más «matemática» y visualmente más estética respecto a escribirlo en otros editores.

Para activar esta características, por ejemplo, en el modo lisp hay que sobreescribir la variable lisp--prettify-symbols-alist de la siguiente forma:

(defconst lisp--prettify-symbols-alist
  '(("lambda"  . ?λ)))

Esto significa que la palabra lambda va a ser remplazada por el simbolo λ. Pero también se puede agregar más remplazos para otros modos:

(add-hook clojure-mode-hook
            (lambda ()
              (push '(">=" . ?≥) prettify-symbols-alist)))

En caso de que queramos activar por defecto prettify-symbols en la mayoría de los modos por defecto de emacs, agregamos la siguiente linea a nuestra configuración de emacs:

(global-prettify-symbols-mode +1)

Clojure Spec

noviembre 1, 2016noviembre 4, 2016 miguelpiniaDeja un comentario

Primero que nada, ¿Qué es clojure spec? Es una biblioteca de clojure que especifica la estructura de los datos, permite la validación de los mismos y puede generar datos a partir del spec.

clojure.spec (o cljs.spec) esta incluida en el core de clojure a partir de la versión 1.9 (aún en estado alpha), así que no es necesario incluir alguna otra biblioteca.

clojure.spec va a permitir que definamos predicados sobre los datos que estamos modelando, permitiendo que estos sean validados en tiempo de ejecución de acuerdo a los predicados definidos. Esto es mucho más poderoso que tener definiciones basadas en tipos.

clojure.spec además permite tener pruebas generativas para probar que las funciones y los datos que definamos funciones de acuerdo a la abstracción de características (predicados) que tenga la información. Se podría decir que clojure.spec tiene los siguientes objetivos de acuerdo a su documentación:

Comunicación
Especificación unificada en varios contextos
Maximizar el apalancamiento a partir del esfuerzo de la especificación
Minimizar la intrusión
Establecer e iniciar un diálogo sobre el cambio de semánticas y compatibilidad.

Lo anterior debería de automatizar lo siguiente:

Validación
Reporte de errores
Destructuring
Instrumentación
Generación de datos de prueba
Generación de pruebas generativas

Todas estas características permiten el desarrollo de software con un alto nivel de certidumbre, ya que evita la necesidad de crear pruebas unitarias (siempre es difícil establecer cuales son los casos interesantes a probar) y permite tener pruebas generativas con casos de prueba generados a partir de la abstracción de características de los datos modelados.

Three More List Manipulation Exercises

octubre 15, 2016 miguelpiniaDeja un comentario

Programming Praxis

We have three more list-manipulation exercises today, for those students midway through their beginning programming course who need practice with linked lists:

Define a function that takes two lists, the second of which is a list of non-negative integers the same length as the first list, and returns a list of elements from the first list, in reverse order, each repeated a number of times as specified by the corresponding element of the second list.
Rearrange the integers in a list so that all the odd numbers appear before all the even numbers, with both odd and even numbers in the same relative order in the output as they were in the input.
Write a function that returns the nth item from the end of a list.

Your task is to write the three specified programs. When you are finished, you are welcome to read or run a suggested solution…

Ver la entrada original 421 palabras más

Two Interview Questions

junio 17, 2016 miguelpiniaDeja un comentario

Programming Praxis

It’s been a while since we had any interview questions. We have two today, since they are so simple:

1) Given a number n, find the smallest 3-digit number such that the product of its digits is equal to n. For example, given n = 100, the solution is 455.

2) Given two arrays, one with n items and one with n+2 items including the same items as the array with n items plus two additional items, find the two additional items. Assume none of the items are duplicates.

Your task is to write solutions to the two interview questions given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

The simplest solution for the first question uses three nested loops, computing the product and returning the…

Ver la entrada original 700 palabras más

Conceptos de código limpio

May 10, 2016junio 13, 2016 miguelpiniaDeja un comentario

Después de observar los cambios que se han ido realizando en los proyectos de código de mis alumnos, me puse a pensar en el concepto de código limpio el cuál para mi significa lo siguiente:

El código limpio es aquel código que es fácil de leer, fácil de entender y muestra un rendimiento óptimo.

¿Pero qué piensan otros programadores acerca del código limpio? para esto, voy a tomar algunas citas del libro Código limpio de Robert C. Martin.

Empecemos con Bjarne Stroustop, desarrollador del lenguaje de programación C++ y autor de The C++ Programming Language

Me gusta que mi código sea elegante y eficaz. La lógica debe ser directa para evitar errores ocultos, las dependencias deben de ser mínimas para facilitar el mantenimiento, el procesamiento de errores completo y sujeto a una estrategia articulada, y el rendimienot debe ser óptimo para que los usuarios no tiendan a estropear el código con optimizaciones sin sentido. El código limpio hace bien una cosa.

Grady Booch, autor de Object Oriented Analysis and Design with Applications

El código limpio es simple y directo. El código limpio se lee como un texto bien escrito. El código limpio no oculta la intención del diseñador si no que muestra nítidas abstracciones y líneas directas de control.

‘Big’ Dave Thomas, fundador de OTI, el padrino de la estrategia Eclipse.

El código limpio se puede leer y mejorar por parte de un programador que no sea su autor original. Tiene pruebas de unidad y aceptación. Tiene nombres con sentido. Ofrece una y no varias formas de hacer algo. Sus dependencias son mínimas, se definen de forma explícita y ofrece una API clara y mínima. El código debe ser culto en función del lenguaje, ya que no toda la información necesaria se puede expresar de forma clara en el código.

Michael Feathers, autor de Working Effectively with Legacy Code.

Podría enumerar todas las cualidades del código limpio pero hay una principal que engloba a todas ellas. El código limpio siempre parece que ha sido escrito por alguien a quien le importa. No hay nada evidente que hacer para mejorarlo. El autor del código pensó en todos los aspectos posibles y si intentamos imaginar alguna mejora, volvemos al punto de partida y sólo nos queda disfrutar del código que alguien a quien le importa realmente nos ha proporcionado.

Después de observar estas citas y algunas más, creo que las características que debe cumplir el código limpio son las siugientes:

Legible
Simple
Elegancia
Eficaz
Óptimo
Con pruebas

Seguro se pueden agregar más características para un código limpio, un buen código.

Computer geek

You know you're brilliant, but maybe you'd like to understand what you did two weeks from now.