- Annonce

L'algorithmique du Knuth-Plass
by Didier Verna 07 Dec '23

07 Dec '23

Chers tous, j'ai le plaisir de vous annoncer une visioconférence en français sur le « Knuth-Plass », l'algorithme de mise en forme / justification de paragraphes de TeX. Cette conférence aura lieu le 11 Janvier 2024 à 20h, dans le cadre des exposés mensuels de l'association GUTenberg. La page d'annonce avec le résumé est disponible à cette adresse: https://www.gutenberg-asso.fr/11-janvier-2024-Expose-sur-l-algorithme-de-Kn… Au plaisir de vous y télé-retrouver... -- Resistance is futile. You will be jazzimilated. Other sites: http://www.didierverna.info

1 0

Soutenance de thèse de Anissa Kheireddine
by akheireddine 06 Dec '23

06 Dec '23

Bonjour, J'ai le plaisir de vous inviter à la soutenance de ma thèse intitulée : "Contributions au Bounded model-checking basé sur SAT La soutenance sera présentée en français. Elle aura lieu le mardi 19 décembre 2023 à partir de 10h00 (heure de Paris), en Amphi 401, EPITA, 14-16 Rue Voltaire, 94270 Le Kremlin-Bicêtre. Vous êtes cordialement invité au pot qui suivra. Composition du jury: Rapporteur: Vijay Ganesh, Professeur, GT, Georgia Institute of Technology. Rapporteur: Ahmed Bounekkar, Maître de Conférences, ERIC, Université Claude Bernard Lyon 1. Examinatrice: Laure Petrucci, Professeure, LIPN, Université Sorbonne Paris Nord. Examinatrice: Emmannuelle Encrenaz, Professeure, LIP6, Sorbonne Université. Directeur: Souheib Baarir, Enseignant-Chercheur, LRE, EPITA. Encadrant: Étienne Renault, SiPearl. Résumé : Les systèmes informatiques sont devenus omniprésents dans notre vie quotidienne. Garantir la fiabilité et la robustesse de ces systèmes est une nécessité absolue. La Vérification de Modèles (Model Checking) est l'une des approches dédiées à cette fin. Son objectif est de prouver l'absence de défaillances ou d'identifier d'éventuelles erreurs. Le model checking se décline en plusieurs techniques. Parmi celles-ci, on trouve la Vérification de Modèles Bornée (Bounded Model Checking - BMC), une technique qui repose sur la satisfiabilité booléenne (SAT). L'idée centrale derrière le BMC est de vérifier qu'un modèle, limité à des exécutions bornées par un entier k, satisfait sa spécification, définie comme un ensemble d'expressions logiques temporelles. Dans cette approche, les comportements du système sont exprimés sous forme de problèmes SAT. Contrairement à d'autres méthodes de vérification formelle, le BMC basé sur SAT n'est généralement pas sensible au problème de l'explosion de l'espace d'états, ce qui peut poser problème lors de la conception de systèmes impliquant des millions de variables et de contraintes. Cependant, le compromis réside dans la complexité temporelle, car les problèmes SAT sont connus pour être NP-complets. Au cours des dernières décennies, d'importantes avancées ont été réalisées dans la résolution séquentielle de problèmes SAT. Ces développements se sont principalement concentrés sur l'utilisation d'informations dynamiques, acquises lors du processus de résolution (par exemple, l'apprentissage de clauses binaires) ou d'informations statiques, extraites de la structure inhérente du problème SAT (par exemple, la structure en communauté). Toutefois, moins d'attention a été accordée aux informations structurelles du problème initial. Par exemple, lorsque qu'un problème BMC est réduit à une formule booléenne, des données cruciales sont perdues lors de la traduction. Comme le souligne cette thèse, la réintégration de ces informations perdues peut considérablement améliorer le processus de résolution. Ce travail explore des moyens d'améliorer la résolution de problèmes BMC basés sur SAT, tant dans des contextes séquentiels que parallèles, en exploitant et en valorisant les informations pertinentes extraites des caractéristiques inhérentes du problème. Cela peut impliquer l'amélioration d'heuristiques génériques existantes ou la décomposition efficace de la formule en partitions. Cordialement, Anissa Kheireddine

1 0

[CfP] 17th European Lisp Symposium, May 6-7 2024, Vienna, Austria
by Didier Verna 30 Nov '23

30 Nov '23

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 17th European Lisp Symposium Call for Papers May 6-7 2024 Federal Computing Center, Vienna, Austria https://www.european-lisp-symposium.org/2024 Sponsored by EPITA ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Important Dates ~~~~~~~~~~~~~~~ - Submission deadline: Feb. 2 2024 - Author notification: Mar. 24 2024 - Final papers due: Apr. 14 2024 - Symposium: May 6-7 2024 Scope ~~~~~ The European Lisp Symposium is a premier forum for the discussion and dissemination of all aspects of design, implementation, and application of any of the Lisp dialects, including Common Lisp, Scheme, Emacs Lisp, Clojure, Racket, ACL2, AutoLisp, ISLISP, Dylan, SKILL, Hy, Shen, Carp, Janet, uLisp, Picolisp, Gamelisp, TXR, and so on. We encourage everyone interested in Lisp to participate. The European Lisp Symposium invites high quality papers about novel research results, insights and lessons learned from practical applications, and educational perspectives. We also encourage submissions about known ideas as long as they are presented in a new setting and/or in a highly elegant way. Topics include but are not limited to: - context-, aspect-, domain-oriented and generative programming - macro-, reflective-, meta- and/or rule-based development approaches - language design and implementation - language integration, inter-operation, and deployment - development methodologies, support, and environments - educational approaches and perspectives - experience reports and case studies This year, we suggest an emphasis on best practices, approaches, and technologies for building highly recursive and self-adapting architectures, in particular for AI, ML, tool integration and instruction generation, using dynamic programming languages. Technical Program ~~~~~~~~~~~~~~~~~ We invite submissions in the following forms. * Papers: technical papers of up to 8 pages that describe original results or explain known ideas in new and elegant ways. * Experience reports: papers of up to 6 pages describing a successful use of a Lisp dialect and/or analyzing obstacles that have kept it from working in practice. * Tutorials: abstracts of up to 4 pages for in-depth presentations about topics of special interest. * Demonstrations: abstracts of up to 4 pages for demonstrations of tools, libraries, and applications. All submissions should be formatted following the ACM SIGS guidelines and include ACM Computing Classification System 2012 concepts and terms. Submissions should be uploaded to Easy Chair, at the following link http://www.easychair.org/conferences/?conf=els2024. Note: to help us with the review process please indicate the type of submission by entering either "paper", "demo", or "tutorial" in the Keywords field. Programme Chair ~~~~~~~~~~~~~~~ Giuseppe Attardi, University of Pisa, Italy Local Chair ~~~~~~~~~~~ Philipp Marek, BRZ, Vienna, Austria Virtualization Team ~~~~~~~~~~~~~~~~~~~ Georgiy Tugai, Configura, Sweden Michał Herda, Poland Yukari Hafner, Shirakumo.org, Switzerland -- Resistance is futile. You will be jazzimilated. Jazz site: http://www.didierverna.com Other sites: http://www.didierverna.info

1 0

SAT competition parallel track medal
by Souheib Baarir 08 Jul '23

08 Jul '23

Hi all, I am delighted to announce that our participation in the International Parallel SAT Competition 2023 (https://satcompetition.github.io/2023/) with our tool Painless (https://www.lrde.epita.fr/wiki/Painless) has resulted in us being awarded the bronze medal ! Regards, Souheib.

1 0

Final Call for Participation - ELS 2023, 16th European Lisp Symoisium
by Didier Verna 06 Apr '23

06 Apr '23

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 16th European Lisp Symposium In-Cooperation-With: ACM SIGLAN Call for Participation April 24-25, 2023 Startup Village, Amsterdam, Nederlands https://www.european-lisp-symposium.org/2023 Sponsored by EPITA, DIRO, MLPrograms, Franz Inc., and SISCOG ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Recent News ~~~~~~~~~~~ Registrer now. Early bird discount closing soon! Keynote details now available. Important Dates ~~~~~~~~~~~~~~~ - Final papers due: April 9, 2023 - Early registration deadline: April 9, 2023 - Symposium: April 24-25, 2023 Scope ~~~~~ The European Lisp Symposium is a premier forum for the discussion and dissemination of all aspects of design, implementation, and application of any of the Lisp dialects, including Common Lisp, Scheme, Emacs Lisp, Clojure, Racket, ACL2, AutoLisp, ISLISP, Dylan, SKILL, Hy, Shen, Carp, Janet, uLisp, Picolisp, Gamelisp, TXR, and so on. We encourage everyone interested in Lisp to participate. The European Lisp Symposium invites high quality papers about novel research results, insights and lessons learned from practical applications, and educational perspectives. We also encourage submissions about known ideas as long as they are presented in a new setting and/or in a highly elegant way. Topics include but are not limited to: - context-, aspect-, domain-oriented and generative programming - macro-, reflective-, meta- and/or rule-based development approaches - language design and implementation - language integration, inter-operation, and deployment - development methodologies, support, and environments - educational approaches and perspectives - experience reports and case studies Keynotes ~~~~~~~~ ##### Artificial Intelligence: a Problem of Plumbing? -- Gerald J. Sussman, MIT CSAIL, USA We have made amazing progress in the construction and deployment of systems that do work originally thought to require human-like intelligence. On the symbolic side we have world-champion Chess-playing and Go-playing systems. We have deductive systems and algebraic manipulation systems that exceed the capabilities of human mathematicians. We are now observing the rise of connectionist mechanisms that appear to see and hear pretty well, and chatbots that appear to have some impressive linguistic ability. But there is a serious problem. The mechanisms that can distinguish pictures of cats from pictures of dogs have no idea what a cat or a dog is. The chatbots have no idea what they are talking about. The algebraic systems do not understand anything about the real physical world. And no deontic logic system has any idea about feelings and morality. So what is the problem? We generally do not know how to combine systems so that a system that knows how to solve problems of class A and another system that knows how to solve problems of class B can be combined to solve not just problems of class A or class B but can solve problems that require both skills that are needed for problems of class A and skills that are needed for problems of class B. Perhaps this is partly a problem of plumbing. We do not have linguistic structures that facilitate discovering and building combinations. This is a fundamental challenge for the programming-language community. We need appropriate ideas for abstract plumbing fittings that enable this kind of cooperation among disparate mechanisms. For example, why is the amazingly powerful tree exploration mechanism that is used for games not also available, in the same system, to a deductive engine that is being applied to a social interaction problem? I will attempt to elucidate this problem and perhaps point at avenues of attack that we may work on together. ##### Hedy: Gradual, Multi-Lingual, and Teacher-Centric Programming Education -- Felienne Hermans, Vrije Universiteit Amsterdam, Nederlands When kids learn to program they often use either a visual language like Scratch, or a textual language like Python. While visual languages are great for the first steps, children and educators often want to move on to textual languages. However, early on, a textual language and its error messages can be scary. Hedy aims to bridge this gap with a programming language that is gradual, using different language levels. In level 1, there is hardly any syntax at all; printing is done with: print hello! At every level, new syntax and concepts are added, so learners do not have to master everything at once. Hedy builds up to a subset of Python including conditions, loops, variables, and lists. To make learning as accessible as possible, Hedy also allows for the use of localized keywords, f.e in Spanish: imprimir Hello! Hedy (www.hedy.org) was launched in early 2020 and over 5 million Hedy progams have been created to date, and has been translated into 46 languages. ##### A Language-Based Approach to Programming with Serialized Data -- Michael Vollmer, School of Computing, University of Kent, UK It is common for software running today to use object representations fixed by the language runtime system; both the Java and Haskell runtimes dictate an object layout, and the compiler must stick to it for all programs. And yet when humans optimize a program, one of their primary levers on performance is changing data representation. For example, an HPC programmer knows how to pack a regular tree into a byte array for more efficient access. Unfortunately, this is error-prone, making it an undesirable way to achieve performance optimization at the expense of safety and readability. Furthermore, whenever a program receives data from the network or disk, rigid insistence on a particular heap layout causes an impedance mismatch we know as deserialization. Data represented in memory has pointers and arbitrary, sparse layout, while data on disk is packed contiguously, so data must be transformed from one form to another and back. Programming with serialized data is a technique for unifying the in-memory and on-disk representations of data, where the serialized form is used both on-disk and in-memory. This technique allows data processing programs to skip the deserialization/reserialization steps by operating directly on the data in its serialized form. It also represents a principled approach to optimizing programs by compacting data representations, which increases locality and minimizes indirection. In this talk, I will present a programming language, LoCal, for programming with serialized data. I will also describe Gibbon, an experimental compiler that automatically transforms functional programs to operate on serialized data. ##### Run-Time Verification of Communication Protocols in Clojure -- Sung-Shik Jongmans, Open Universiteit, Nederlands To simplify shared-memory concurrent programming, languages have started to offer core support for high-level communications primitives, in the form of message passing though channels, in addition to lower-level synchronization primitives. Yet, a growing body of evidence suggests that channel-based programming abstractions also have their issues. The Discourje project aims to help programmers cope with channels and concurrency bugs in Clojure programs, based on dynamic analysis. The idea is that programmers write not only implementations of communication protocols in their Clojure programs, but also specifications. Discourje then offers a run-time verification library to ensure that channel actions in implementations are safe relative to specifications. Programme Chair ~~~~~~~~~~~~~~~ Stefan Monnier, DIRO, Université de Montréal, Canada Programme Committee ~~~~~~~~~~~~~~~~~~~ Mark Evenson, not.org, Austria Marco Heisig, Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany Ioanna Dimitriou, Igalia S.L., Germany Robert Smith, HRL Laboratories Mattias Engdegård Marc Feeley, Université de Montréal, Canada Marc Battyani, FractalConcept Alan Ruttenberg, National Center for Ontological Research, USA Nick Levine, RavenPack, Spain Ludovic Courtès, Inria, France Matthew Flatt, University of Utah, USA Irène Durand, Université Bordeaux 1, France Jay McCarthy, Brigham Young University, USA Ambrose Bonnaire-Sergeant, Cisco Christopher League, Long Island University, NY, USA Pascal Costanza, Intel, Belgium Christian Queinnec Local Chair ~~~~~~~~~~~ Breanndán Ó Nualláin, Machine Learning Programs, Nederlands -- Resistance is futile. You will be jazzimilated. Lisp, Jazz, Aïkido: http://www.didierverna.info

1 0

Paper accepted at iceccs'2023.
by Souheib Baarir 05 Apr '23

05 Apr '23

Dear all, I'm happy to annonce that I have a paper accepted at iceccs'2023. Title : An Experience Report on the Optimization of the Product Configuration System of Renault Authors : Hao Xu, Souheib Baarir, Tewfik Ziadi, Siham Essodaigui, Yves Bossu and Lom Messan Hillah Abstract : The problem of configuring a variability model is widespread in many different domains. Renault has developed its technology internally to model vehicle diversity. This technology relies on the approach known as knowledge compilation to explore the configurations space. However, the growing variability and complexity of the vehicles' range hardens the space representation problem and may impact performance requirements. This paper tackles these issues by exploiting symmetries that represent isomorphic parts in the configuration space. The extensive experiments we conducted on datasets from Renault show our approach's robustness and effectiveness: the achieved gain is a reduction of 52.13% in space representation and 49.81% in processing time on average.in processing time on average.

1 0

Paper accepted at ELS 2023
by Jim Newton (lrde) 03 Apr '23

03 Apr '23

Dear all, it's my pleasure to announce that I have a new paper accepted at ELS 2023, the 16th European Lisp Symposium, to be held by the end of this month in Amsterdam. Title and abstract below… An Elegant and Fast Algorithm for Partitioning Types We present an improvement on the Maximal Disjoint Type Decomposition algorithm, published previously. The new algorithm is shorter than the previously best known algorithm in terms of lines of code, and performs better in many, but not all, bench marks. Additionally the algorithm computes meta data which makes the Brzozowski derivative easier to compute--easier in terms of accuracy and computation time. Another advantage of this new algorithm is its resilience in light of limited subtypep implementations.

1 0

Paper accepted at ELS 2023
by Didier Verna 03 Apr '23

03 Apr '23

Dear all, it's my pleasure to announce that I have a new paper accepted at ELS 2023, the 16th European Lisp Symposium, to be held by the end of this month in Amsterdam. Title and abstract below... A MOP-Based Implementation for Method Combinations In traditional object-oriented languages, the dynamic dispatch algorithm is hardwired to select and execute the most specific method in a polymorphic call. In CLOS, the Common Lisp Object System, an abstraction known as "method combinations" allows the programmer to define their own dispatch scheme. When Common Lisp was standardized, method combinations were not mature enough to be fully specified. In 2018, using SBCL as a research vehicle, we analyzed the unfortunate consequences of this under-specification and proposed a layer on top of method combinations designed to both correct a number of observed behavioral inconsistencies, and propose an extension called "alternative combinators". Following this work, SBCL underwent a number of internal changes that fixed the reported inconsistencies, although in a way that hindered further experimentation. In this paper, we analyze SBCL's new method combinations implementation and we propose an alternative design. Our solution is standard-compliant so any Lisp implementation can potentially use it. It is also based on the MOP, meaning that it is extensible, which restores the opportunity for further experimentation. In particular, we revisit our former "alternative combinators" extension, broken after 2018, and demonstrate that provided with this new infrastructure, it can be re-implemented in a much simpler and non-intrusive way. -- Resistance is futile. You will be jazzimilated. Lisp, Jazz, Aïkido: http://www.didierverna.info

1 0

Accepted paper at TUG 2023
by Didier Verna 14 Mar '23

14 Mar '23

Dear all, I'm happy to announce that the following paper has been accepted at the TUG 2023 conference, Bonn, July 14-16 2023. Interactive and Real-Time Typesetting for Demonstration and Experimentation Abstract: In general, typesetting experimentation is not a very practical thing to do. WYSIWYG typesetting systems are very reactive but do not offer highly configurable algorithms, and TeX, with its separate development / compilation / visualization phases, is not as interactive as its WYSIWYG competitors. Being able to experiment with typesetting algorithms interactively and in real-time is nevertheless desirable, for instance for demonstration purposes, or for rapid prototyping and debugging of new ideas. We present ETAP (Experimental Typesetting Algorithms Platform), a tool written to ease typesetting experimentation and demonstration. ETAP currently provides several paragraph justification algorithms, all with many configuration options such as kerning, ligatures, flexible spaces, sloppiness, hyphenation, etc. The resulting paragraph is displayed with many visual hints as well, such as paragraph, character, and line boxes, baselines, over/underfullness hints, hyphenation clues, etc. All these parameters, along with the desired paragraph width, are adjustable interactively through a GUI, and the resulting paragraph is displayed and updated in real-time. But ETAP can also be used without, or in conjunction with the GUI, as a scriptable application. In particular, it is able to generate all sorts of statistical reports or charts on the behavior of the various algorithms, for instance, the number of over/underfull boxes per paragraph width, the average compression or stretch ratio per line, whatever else you want. This allows you to quickly demonstrate or evaluate the comparative behavior or merits of the provided algorithms, or whichever you may want to add to the pool. -- Resistance is futile. You will be jazzimilated. Lisp, Jazz, Aïkido: http://www.didierverna.info

1 0

Séminaire IMAGE mer. 15/03 : Parsing 2D pour l'analyse de documents (B. Coüasnon)
by Joseph Chazalon 14 Mar '23

14 Mar '23

Bonjour à tous, je suis heureux de vous inviter au séminaire du mercredi 15 mars prochain, qui aura lieu de 11h à 12h en amphi 0 (Paris, KB). Bertrand était mon encadrant de doctorat et j'ai travaillé sur le système qu'il présentera (qui a bien évolué depuis). Je pense qu'il pourra intéresser les curieux de l'équipe automates aussi, pour l'usage assez extrême des compilateurs et des grammaires qui est fait (grammaire bi-dimensionnelles avec un analyseur codé en lambda prolog qui a la capacité de déplacer non linéairement sa tête de lecture sur la surface à analyser en fonction du contexte passé). Si la récursion gauche ne vous fait pas peur, venez jeter un œil. Je pense qu'il pourrait aussi intéresser les curieux côté IA car ma motivation derrière cette invitation est de démarrer un travail visant à bricoler l'architecture des décodeurs de transformeurs pour améliorer les deep parsers dont les premiers résultats sont assez époustouflants. Et bien entendu, pour ceux qui s'intéressent à l'analyse d'images (de documents), ce système est un cas d'école. Lien Teams pour celles et ceux à distance : https://teams.microsoft.com/l/meetup-join/19%3apzIZ9vVKzWORw57NZInOVyAH2uKq… En espérant vous voir nombreux, Joseph ======================================================================= Invité : Bertrand Coüasnon (INSA Rennes/IRISA) Titre : DMOS-PI : un système complet d’analyse interactive de collections de documents Résumé : DMOS-PI est un système de reconnaissance de collections de documents qui s’appuie sur une description visuelle des documents grâce à des grammaires bidimensionnelles, combinées à des méthodes d’apprentissage profond. Il permet également la modélisation de collections de documents, une formalisation d’interactions asynchrones entre l’analyse des pages et les saisies manuelles, et une transformation des informations unitaires rencontrées dans les pages en des séquences de ces informations unitaires, le tout étant intégré progressivement par une analyse itérative des pages. Cette combinaison produit une fiabilisation des informations reconnues s’appuyant sur les redondances rencontrées dans les collections de documents et permet d’envisager la construction de systèmes auto-adaptatifs. Ce système a été validé sur une très grande variété de documents : des formulaires administratifs anciens, de la presse ancienne, des documents récents dégradés, des listes de cotations boursières du XIXe et XXe siècle, des partitions musicales anciennes… =======================================================================

1 1