A continuación se muestra una lista de temas sugeridos para la presentación final del curso.

Indicaciones:

• Esta lista es solo de referencia y están libres de escoger otro tema que propongan bajo acuerdo previo con el profesor
• Los recursos que se listan a continuación de la descripción de cada tema también son de referencia. El objetivo de estos recursos es que sirvan como punto de partida
• Se espera que apliquen lo aprendido en el curso en sus presentaciones, por ejemplo mostrar reglas de tipo, reglas de reducción, etc
• Cada presentación es individual
• Las presentaciones deben durar máximo 20 minutos
• Las fechas de las presentaciones son Junio 24 y 26

Los sistemas de tipos lineales pertenecen a la familia de sistemas de tipo subesctructurales donde una o más reglas estructurales están ausentes. En particular los sistemas de tipos lineales permiten “exchange”, pero no “weakening” o “contraction”. Esto quiere decir que cada variable de un programa debe ser usada exactamente una vez. Estos sistemas son generalmente usados para controlar recursos de sistema, como archivos, memoria o locks.

• Linear Types Can Change the World: pdf
• Advanced Topics in Types and Programming Languages
  1. Substructural properties, type rules, operational semantics, progress + preservation.
  2. pages 3-16 (16-36: extensions and variations)

Los tipos de pertenencia permiten clasificar objetos con una propiedad de pertenencia. Esto permite limitar la visibilidad de las referencias a los objetos, restringiendo el acceso fuera de su límites de encapsulación. Estos tipos son mayoritariamente empleados para manejo de alias, y eliminar data-races y deadlocks.

• https://www.cs.cornell.edu/courses/cs711/2005fa/papers/cpn-oopsla98.pdf
• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.1645&rep=rep1&type=pdf

Los liquid types permiten enriquecer tipos de un programa con predicados lógicos decidibles, los cuales permiten especificar y automatizar la verificación de propiedades semanticas de tu código. Un ejemplo característico del uso de estos tipos, es chequear estáticamente que no se produzcan divisiones por cero en un programa.

• Paper original de Liquid Types: http://goto.ucsd.edu/~rjhala/liquid/liquid_types.pdf
• Liquid Types en Haskell: https://goto.ucsd.edu/~nvazou/refinement_types_for_haskell.pdf
• Liquid Haskell in the Real World: http://goto.ucsd.edu/~nvazou/real_world_liquid.pdf

WebAssembly es un lenguaje bytecode de bajo nivel y portable. Fue diseñado inicialmente para reemplazar Javascript en los navegadores web, pero ahora puede ser usado en cualquier otro contexto. WebAssembly está pensado para ser el posible objetivo de compilación de lenguajes de alto nivel como C o Rust.

• Formal overview: https://dl.acm.org/citation.cfm?id=3062363
• homepage: https://webassembly.org/

Los tipos graduales permiten la suave transición entre el chequeo estático y el chequeo dinámico, basada en la precisión de las anotaciones de tipos introducidas por los programadores. Esto permite obtener los beneficios de lenguajes estáticamente tipados como Java, Scala, Haskell, y Ocaml, y lenguajes dinámicamente tipados como Javascript, Python, y Ruby.

• Paper original (Gradual Typing for FP): pdf
• blog post de Siek: https://wphomes.soic.indiana.edu/jsiek/what-is-gradual-typing/
• Gradual Typing for Objects: pdf
• Abstracting Gradual Typing: pdf

Las políticas de flujo de información (information-flow policies) permiten clasificar entidades de un programa con distintos niveles de seguridad, para especificar confidencialidad o integridad. Los tipos de seguridad (security types) permiten enforzar information-flow policies de manera estática en tiempo de compilación.

• Programming Languages for Information Security
  • http://www.cis.upenn.edu/~stevez/papers/Zda02.pdf
  • Type rules, operational semantics, and noninterference
  • Pure: pages 23-37
  • Mutable references: 38-49

Los session types son mayoritariamente usados en programación orientada a las comunicaciones, donde los programas pueden ser chequeados estáticamente para ver si respetan ciertos protocolos de comunicación.

• https://www.di.fc.ul.pt/~vv/papers/honda.vasconcelos.kubo_language-primitives.pdf
• Overview más gentil: http://www.di.unito.it/~dezani/papers/sto.pdf

En lenguajes simples como el lambda cálculo simplemente tipado, se permite que términos dependan en variables (funciones). En lenguajes como System F, existe otro tipo de abstracción donde se permite que términos dependan ahora en tipos (abstracciones de tipo). Los lenguajes con tipos dependientes son lenguajes donde se permite ahora que los tipos dependan de términos del mismo lenguaje.

• Advanced Topics in Types and Programming Languages
  • Dependant Types chapter
  • pages 45 - 86
• Dependent ML: www.cs.bu.edu/fac/hwxi/academic/papers/JFPdml.ps
• Coq o F* (ver más abajo)

Los sistemas de efectos permiten trackear los efectos secundarios que puede tener un programa, como por ejemplo imprimir en pantalla, leer y escribir en la memoria, tirar una excepción, etc. Los sistemas de tipos y efectos, como su nombre lo indica, combinan tipos y efectos para controlar de manera estática el uso de efectos en un programa.

• A Generic Type-and-Effect System: https://archive.alvb.in/msc/11_infomtpt/papers/generic-type-and-effect-system_Millstein.pdf

Rust es un lenguaje de programación de software de sistemas que se focaliza en “safety”, especialmente para concurrencia segura. Rust es sintácticamente muy parecido a C++, pero esta designado con un rico sistema de tipos que permite un manejo seguro de la memoria y a la vez muy buen desempeño al no contar con un recolector de basura.

• https://www.rust-lang.org/
• https://plv.mpi-sws.org/rustbelt/popl18/paper.pdf

Scala es un lenguaje de programación que mezcla programación funcional con programación orientada a objetos. Tiene un sistema de tipos rico y su código fuente es compilado a bytecode para la JVM, lo que permite la interoperabilidad con cualquier libreria Java. Su uso conocido más popular es el de Twitter, los cuales cambiaron su infraestructura de Ruby a Scala.

• Formal: http://lampwww.epfl.ch/~odersky/papers/mfcs06.pdf
• Práctico: https://www.scala-lang.org/docu/files/ScalaOverview.pdf

F* es un lenguaje de programación funcional con efectos, orientado a la verificación de programas. El sistema de tipos de F* incluye tipos dependientes, efectos monádicos, refinement types entre otros. F* permite la extracción de código a OCaml, F#, C, WASM o ASM. F* está siendo actualmente usado para implementar una versión verificada de todo el stack HTTPS (proyecto Everest), el cual incluye la implementación de TLS 1.2 y 1.3.

• https://fstar-lang.org/#papers

Coq es un lenguaje funcional con tipos dependientes y un demostrador de teoremas interactivo. Permite el ingreso de proposiciones matemáticas, las cuales son chequeadas mecánicamente, ayuda a construir demostraciones formales, y extrae programas certificados a lenguajes como OCaml, Haskell y Scheme. Aunque no es un demostrador de teoremas automático, incluye varias tácticas de demostraciones que ayudan en la construcción de ellas.

• https://coq.inria.fr/