ELS 2016, 9th European Lisp Symposium, 9-10 May 2016,
Department of Computer Science, AGH University of Science and Technology, Kraków, Poland.
Francis Sergeraert, Institut Fourier, Grenoble, France.
The power of Common Lisp for functional programming is well known, the key tool being the notion of "lexical closure", allowing the programmer to write programs which, during execution, dynamically generate functional objects of arbitrary complexity. Using this technology, new algorithms in Algebraic Topology have been discovered, implemented in Common Lisp, used, producing homology and homotopy groups so far unreachable. An algorithm is viewed as "tractable" if its theoretical complexity is not worse than polynomial. The study of this complexity for the aforementioned algorithms of Algebraic Topology requires a lucid knowledge of the concrete implementation of these lexical closures. The talk is devoted to a report about a result of polynomial complexity so obtained. The scope of the method is general and in particular no knowledge in Algebraic Topology is expected in the audience.
