はてなブックマーク

Introduction Dictionary passing Type classes as macros Intensional type analysis The pioneering work of Stefan Kaes Brief bibliography Canonical structures: (type-class) overloading resolution as logic programming Stretching Type Classes: Unusual applications and arguments about type classes in Haskell Introduction Computational abstractions -- higher-order functions, continuations, modules, proce

Introduction Classical monads Free Monad Profitable cheating Freer Monad Definitional interpreters for effects Performance Conclusions Introduction Writing Monad (and now, Applicative and Functor) instances and making sure the monad laws hold are a big part of defining a monad and even a bigger part in exponentially procreating monad tutorials. We argue that all these instances are boilerplate --

Haskell is not a dependently-typed language -- at least it was not designed that way. Nevertheless, even Haskell98 admits some form of dependent types, enough to statically prevent the annoying ``head of empty list'' error. After multi-parameter type classes with functional dependencies were introduced, it was quickly (Hallgren, 2001) realized that we can compute with types. HList (2004) has lifte

Modular, composable, typed optimizations in the tagless-final style Optimizations of tagless-final embedded DSLs are possible after all. They are typed and patently type-preserving. We present the optimization framework inspired by the normalization-by-evaluation and demonstrate that tagless-final optimizations are also modular, convenient and composable. We contrast them with the optimizations ov

We describe Cartwright and Felleisen's modular and compositional approach to effects, discuss extensions and present its implementations in Haskell. The principal ideas, in the words of Cartwright and Felleisen, are: ``An effect is most easily understood as an interaction between a sub-expression and a central authority that administers the global resources of a program.'' ``an effect can be viewe

The so-called ``tagless-final'' style is a method of embedding domain-specific languages (DSLs) in a typed functional host language such as Haskell, OCaml, Scala or Coq. It is an alternative to the more familiar embedding as a (generalized) algebraic data type. It is centered around interpreters: Evaluator, compiler, partial evaluator, pretty-printer, analyzer, multi-pass optimizer are all interpr

The so-called ``tagless-final'' style is a method of embedding domain-specific languages (DSLs) in a typed functional host language such as Haskell, OCaml, Scala or Coq. It is an alternative to the more familiar embedding as a (generalized) algebraic data type. It is centered around interpreters: Evaluator, compiler, partial evaluator, pretty-printer, analyzer, multi-pass optimizer are all interpr

General-purpose algorithms and data structures, illustrated in Haskell. Part II Reflection without Remorse: A conceptual sequence as a tangible and efficient data structure Pure functional, mutation-free, efficient double-linked lists Total stream processors and their applications to all infinite streams Sparse Grids: multi-dimensional interpolation, approximation and integration Fast computation

Higher-order, Typed, Inferred, Strict ACM SIGPLAN ML Family Workshop Thursday September 4, 2014, Gothenburg, Sweden (immediately following ICFP and preceding OCaml Users and Developers Workshop) News Dec 5, 2015 The post-proceedings with the extended versions of the selected ML Family and OCaml 2014 workshop submissions are published as EPTCS 198 Sep 10, 2014 The video record of all presentations

BER MetaOCaml is a conservative extension of OCaml for ``writing programs that generate programs''. BER MetaOCaml adds to OCaml the type of code values (denoting ``program code'', or future-stage computations), and two basic constructs to build them: quoting and splicing. The generated code can be printed, stored in a file -- or compiled and linked-back to the running program, thus implementing ru

Type equality predicates: from OverlappingInstances to overcoming them Type equality predicates decide if two types are equal and return the result of the comparison as a type-level boolean. A type equality predicate ought to be total for ground types, that is, types with no free type variables. A more general type matching predicate compares the shape of two types, their top-level type constructo

How OCaml type checker works -- or what polymorphism and garbage collection have in common There is more to Hindley-Milner type inference than the Algorithm W. In 1988, Didier Rémy was looking to speed up the type inference in Caml and discovered an elegant method of type generalization. Not only it is fast, avoiding scanning the type environment. It smoothly extends to catching of locally-declare

We argue against call/cc as a core language feature, as the distinguished control operation to implement natively relegating all others to libraries. The primitive call/cc is a bad abstraction -- in various meanings of `bad' shown below, -- and its capture of the continuation of the whole program is not practically useful. The only reward for the hard work to capture the whole continuation efficie

Implementations of delimited control in OCaml, Haskell, Scheme Delimited Control in OCaml, Abstractly and Concretely OCaml A direct implementation of delimited continuations for byte- and native-code OCaml Executable direct denotational semantics of multiprompt delimited control Haskell Three new monad transformers for multi-prompt delimited control Delimited continuations with effect typing, full

Introduction The first monad tutorial and the `programmable semicolon' Landin's IO monad in modern eyes Other Landin's discoveries References Introduction Monads turned out a convenient tool to represent and reason about computational effects -- such as IO, mutable state and exceptions -- in lambda calculi. In particular, monads let us clearly separate evaluation-order--insensitive simplifications

Zipper: a derivative of a data structure or of its mapping Zipper from any Traversable Zipper-based file server/OS Delimited continuations in operating systems Double-generic zipWith, for any number of any collections Zipping through several data structures to compare and annotate them Zippers with several holes Generic crossover: zipping two zippers Zipper: a derivative of a data structure or of

Introduction Simplistic GADTs in OCaml GADTs Towards open GADTs: extensible evaluator for a typed object language Generics for the OCaml masses This is joint work with Jeremy Yallop. Introduction First-class modules introduced in OCaml 3.12 make type constructors first-class, permitting type constructor abstraction and polymorphism. It becomes possible to manipulate and quantify over types of high

Spreadsheets and Matlab are popular because they let domain experts write down a problem in familiar terms and quickly play with potential solutions. Natural-language semanticists have a better tool. It displays truth conditions, infers types, simplifies terms, and computes yields. Its modularity facilities make it easy to try fragments out, scale them up, and abstract encoding details out of sema

The first course on typed tagless-final embeddings of domain-specific languages has been presented at the Spring School on Generic and Indexed Programming (SSGIP) <http://www.comlab.ox.ac.uk/projects/gip/school.html> at Wadham College, Oxford, UK on 22nd to 26th March 2010. This page collects the notes for the course in the form of the extensively commented Haskell and OCaml code. Lecture Notes In

The first course on typed tagless-final embeddings of domain-specific languages has been presented at the Spring School on Generic and Indexed Programming (SSGIP) <http://www.comlab.ox.ac.uk/projects/gip/school.html> at Wadham College, Oxford, UK on 22nd to 26th March 2010. This page collects the notes for the course in the form of the extensively commented Haskell and OCaml code. Lecture Notes In

Parametric polymorphism is the parameterization of a term by a type, permitting the term to be used in differently-typed contexts. Types of polymorphic terms contain universal quantification. For the sake of inference and ease of type checking, mainstream functional programming languages restrict where in the type the quantifiers may appear and what they quantify over. The Hindley-Milner system, o

Lambda abstractions in C++ vs. Scheme This article is to exhibit lambda abstractions in C++ in comparison with those of traditional functional languages (e.g., Scheme). The article will try to demonstrate that "applicable values" in C++ not only look similar to their functional cousins. They are equal in meaning as well. The same can be said for currying. This article will not prove that C++ and S

Stream processing defines a pipeline of operators that transform, combine, or reduce (even to a single scalar) large amounts of data. Characteristically, data is accessed strictly linearly rather than randomly and repeatedly -- and processed uniformly. The upside of the limited expressiveness is the opportunity to process large amount of data efficiently, in constant and small space. Introduction

Finally we see the agreement with our expectations. Iterative deepening now needs only 2MB (down from 56MB in the first try) to compute the first 100 Pythagorean triples. We may now try bigger searches. We have seen that lazy evaluation is a trade-off, which may be hurtful in some cases, in particular, in search problems over huge data structures, where it is often beneficial to recompute the resu