Podstawy Informatyki

prof. dr hab. Marek Zaionc
dr Katarzyna Grygiel

środa 12:15 - 14:00, sala 0174

Research seminar devoted to problems related to asymptotic densities in logic, computability theory, computational logic, typed lambda calculus, logic programming, logics of programs, functional programming.

Między dokładnością a użytecznością istnieje fascynująca kraina przybliżeń. Podczas wykładu pokażemy, czym jest aproksymacja, dlaczego bez niej nie byłoby ani nowoczesnej nauki, ani komputerów, oraz jak zaskakująco często wystarcza nam odpowiedź „prawie dokładna”, by lepiej zrozumieć świat.

Anna Szymańska

We show how to write generic programs and proofs in Martin-Lof type theory. To this end we consider several extensions of Martin-Lof’s logical framework for dependent types. Each extension has a universes of codes (signatures) for inductively defined sets with generic formation, introduction, elimination, and equality rules. These extensions are modeled on Dybjer and Setzer’s finitely axiomatized theories of inductive-recursive definitions, which also have a universe of codes for sets, and generic formation, introduction, elimination, and equality rules. However, here we consider several smaller universes of interest for generic programming and universal algebra. We thus formalize one-sorted and many-sorted term algebras, as well as iterated, parameterized, generalized, and indexed inductive definitions. We also show how to extend the techniques of generic programming to these universes. Most of the definitions in the paper have been implemented using the proof assistant Alfa for dependent type theory.