Didier Verna

Strategies in typecase optimization

By Jim Newton, Didier Verna

2018-04-05

In ELS 2018, the 11th european lisp symposium

Abstract

We contrast two approaches to optimizing the Common Lisp typecase macro expansion. The first approach is based on heuristics intended to estimate run time performance of certain type checks involving Common Lisp type specifiers. The technique may, depending on code size, exhaustively search the space of permutations of the type checks, intent on finding the optimal order. With the second technique, we represent a typecase form as a type specifier, encapsulating the side-effecting non-Boolean parts so as to appear compatible with the Common Lisp type algebra operators. The encapsulated expressions are specially handled so that the Common Lisp type algebra functions preserve them, and we can unwrap them after a process of Boolean reduction into efficient Common Lisp code, maintaining the appropriate side effects but eliminating unnecessary type checks. Both approaches allow us to identify unreachable code, test for exhaustiveness of the clauses and eliminate type checks which are calculated to be redundant.

Continue reading

Method combinators

By Didier Verna

2018-03-25

In ELS 2018, the 11th european lisp symposium

Abstract

In traditional object-oriented languages, the dynamic dispatch algorithm is hardwired: for every polymorphic call, only the most specific method is used. ClosClos, the Common Lisp Object System, goes beyond the traditional approach by providing an abstraction known as method combinationsmethod combinations: when several methods are applicable, it is possible to select several of them, decide in which order they will be called, and how to combine their results, essentially making the dynamic dispatch algorithm user-programmable.Although a powerful abstraction, method combinations are under-specified in the Common Lisp standard, and the MopMop, the Meta-Object Protocol underlying many implementations of ClosClos, worsens the situation by either contradicting it or providing unclear protocols. As a consequence, too much freedom is granted to conforming implementations. The exact or intended behavior of method combinations is unclear and not necessarily coherent with the rest of ClosClos.In this paper, we provide a detailed analysis of the problems posed by method combinations, the consequences of their lack of proper specification in one particular implementation, and a MopMop-based extension called method combinatorsmethod combinators, aiming at correcting these problems and possibly offer new functionality.

Continue reading

Lisp, jazz, aikido

By Didier Verna

2018-02-05

In The Art, Science and Engineering of Programming Journal

Abstract

The relation between Science (what we can explain) and Art (what we can’t) has long been acknowledged and while every science contains an artistic part, every art form also needs a bit of science. Among all scientific disciplines, programming holds a special place for two reasons. First, the artistic part is not only undeniable but also essential. Second, and much like in a purely artistic discipline, the act of programming is driven partly by the notion of aesthetics: the pleasure we have in creating beautiful things.Even though the importance of aesthetics in the act of programming is now unquestioned, more could still be written on the subject. The field called “psychology of programming”psychology of programming focuses on the cognitive aspects of the activity, with the goal of improving the productivity of programmers. While many scientists have emphasized their concern for aesthetics and the impact it has on their activity, few computer scientists have actually written about their thought process while programming.What makes us like or dislike such and such language or paradigm? Why do we shape our programs the way we do? By answering these questions from the angle of aesthetics, we may be able to shed some new light on the art of programming. Starting from the assumption that aesthetics is an inherently transversal dimension, it should be possible for every programmer to find the same aesthetic driving force in every creative activity they undertake, not just programming, and in doing so, get deeper insight on why and how they do things the way they do.On the other hand, because our aesthetic sensitivities are so personal, all we can really do is relate our own experiences and share it with others, in the hope that it will inspire them to do the same. My personal life has been revolving around three major creative activities, of equal importance: programming in Lisp, playing Jazz music, and practicing Aikido. But why so many of them, why so different ones, and why these specifically?By introspecting my personal aesthetic sensitivities, I eventually realized that my tastes in the scientific, artistic, and physical domains are all motivated by the same driving forces, hence unifying Lisp, Jazz, and Aikido as three expressions of a single essence, not so different after all. Lisp, Jazz, and Aikido are governed by a limited set of rules which remain simple and unobtrusive. Conforming to them is a pleasure. Because Lisp, Jazz, and Aikido are inherently introspective disciplines, they also invite you to transgress the rules in order to find your own. Breaking the rules is fun. Finally, if Lisp, Jazz, and Aikido unify so many paradigms, styles, or techniques, it is not by mere accumulation but because they live at the meta-level and let you reinvent them. Working at the meta-level is an enlightening experience.Understand your aesthetic sensitivities and you may gain considerable insight on your own psychology of programming. Mine is perhaps common to most lispers. Perhaps also common to other programming communities, but that, is for the reader to decide…

Continue reading

Programmatic manipulation of Common Lisp type specifiers

By Jim Newton, Didier Verna, Maximilien Colange

2017-02-06

In ELS 20217, the 10th european lisp symposium

Abstract

In this article we contrast the use of the s-expression with the BDD (Binary Decision Diagram) as a data structure for programmatically manipulating Common Lisp type specifiers. The s-expression is the de facto standard surface syntax and also programmatic representation of the type specifier, but the BDD data structure offers advantages: most notably, type equivalence checks using s-expressions can be computationally intensive, whereas the type equivalence check using BDDs is a check for object identity. As an implementation and performance experiment, we define the notion of maximal disjoint type decomposition, and discuss implementations of algorithms to compute it: a brute force iteration, and as a tree reduction. The experimental implementations represent type specifiers by both aforementioned data structures, and we compare the performance observed in each approach.

Continue reading

Type-checking of heterogeneous sequences in Common Lisp

By Jim Newton, Akim Demaille, Didier Verna

2016-03-25

In ELS 2016, the 9th european lisp symposium

Abstract

We introduce the abstract concept of rational type expression and show its relationship to rational language theory. We further present a concrete syntax, regular type expression, and a Common Lisp implementation thereof which allows the programmer to declaratively express the types of heterogeneous sequences in a way which is natural in the Common Lisp language. The implementation uses techniques well known and well founded in rational language theory, in particular the use of the Brzozowski derivative and deterministic automata to reach a solution which can match a sequence in linear time. We illustrate the concept with several motivating examples, and finally explain many details of its implementation.

Continue reading

Context-oriented image processing

By Didier Verna, François Ripault

2015-01-01

In Context-oriented programming workshop

Abstract

Genericity aims at providing a very high level of abstraction in order, for instance, to separate the general shape of an algorithm from specific implementation details. Reaching a high level of genericity through regular object-oriented techniques has two major drawbacks, however: code cluttering (e.g. class / method proliferation) and performance degradation (e.g. dynamic dispatch). In this paper, we explore a potential use for the Context-Oriented programming paradigm in order to maintain a high level of genericity in an experimental image processing library, without sacrificing either the performance or the original object-oriented design of the application.

Continue reading

The incredible tale of the author who didn’t want to do the publisher’s job

By Didier Verna

2013-01-01

In TUGboat

Abstract

In this article, I relate on a recent experience of mine: writing a book chapter for a publisher who doesn’t have a clue about typesetting. I confess my futile attempt at using TeX for writing the chapter in question. I describe the hell that descended upon me for daring to do that. I however admit that the hell in question would have been even greater, hadn’t I done so. This article is both a nervous breakdown and a laughter, and I am seeking for the reader’s comfort.

Continue reading

TiCL: The prototype (Star TeX: The next generation, season 2)

By Didier Verna

2013-01-01

In TUGboat

Abstract

At TUG 2012, we presented some ideas about using one of the oldest programming languages (Lisp), in order to modernize one of the oldest typesetting systems (TeX). This talk was mostly focused on justifying the technical fitness of Lisp for this task. This time, we would like to take the opposite view and demonstrate a prototype, from the user’s perspective. This involves showing what a TiCL document could look like, the implications in terms of typesetting vs. programmatic features, and also in terms of extensibility (relate this to class / style authoring).

Continue reading

Extensible languages: Blurring the distinction between DSLs and GPLs

By Didier Verna

2012-09-01

In Formal and practical aspects of domain-specific languages: Recent developments

Abstract

Out of a concern for focus and concision, domain-specific languages (DSLs) are usually very different from general purpose programming languages (GPLs), both at the syntactic and the semantic levels. One approach to DSL implementation is to write a full language infrastructure, including parser, interpreter or even compiler. Another approach however, is to ground the DSL into an extensible GPL, giving you control over its own syntax and semantics. The DSL may then be designed merely as an extension to the original GPL, and its implementation may boil down to expressing only the differences with it. The task of DSL implementation is hence considerably eased. The purpose of this chapter is to provide a tour of the features that make a GPL extensible, and to demonstrate how, in this context, the distinction between DSL and GPL can blur, sometimes to the point of complete disappearance.

Continue reading

Generic image processing with Climb

By Laurent Senta, Christopher Chedeau, Didier Verna

2012-05-01

In ELS 2012, the 5th european lisp symposium

Abstract

We present Climb, an experimental generic image processing library written in Common Lisp. Most image processing libraries are developed in static languages such as C or C++ (often for performance reasons). The motivation behind Climb is to provide an alternative view of the same domain, from the perspective of dynamic languages. More precisely, the main goal of Climb is to explore the dynamic way(s) of addressing the question of genericity, while applying the research to a concrete domain. Although still a prototype, Climb already features several levels of genericity and ships with a set of built-in algorithms as well as means to combine them.

Continue reading

Search

Tags