I am a programming languages and type theory researcher from Prague, currently working at the Faculty of Mathematics and Physics at Charles University (CUNI).
๐งฎ I am interested in systems for formal reasoning, programming languages and mathematical logic. I build small programming languages, theorem provers, and other systems related to PLT concepts.
Outside work, I like to take photos on film. I develop film and process the photos myself. I also design 3D printable devices that help me with that.
๐ธ Also here's my current favorite image.
I sometimes write about what I learned to my digital notepad.
I design free, open-source 3D printable alternatives to commercial devices for film photography.
๐๏ธ gravity holder V1 ๐๏ธ
a film holder for DSLR scanning
๐งต spooler ๐๏ธ
a film bulk loader
Here are some of my past research projects. I mostly do PL, TT, logic, and formal reasoning related ones.
Detour ๐ ๐
A research prototype behind our HATRA'24 (SPLASH) paper Don't Call Us, We'll Call You.
Small Fitch-style FOL checker in Haskell, with automated proof search over user-declared syntax and induction.
Show example snippet
module demo
syntax N = Zero
| Suc(N)
judgment sum = Sum(N, N, N)
rule schema sum-zero for all objects (n : N) :
|
|-------------------------------------- sum-zero
| Sum(Zero, n, n)
rule schema sum-suc for all objects (m : N), (n : N), (o : N) :
| Sum(m, n, o)
|-------------------------------------- sum-suc
| Sum(Suc(m), n, Suc(o))
theorem zero-plus-one : Sum(Suc(Zero), Zero, Suc(Zero))
prove Sum(Suc(Zero), Zero, Suc(Zero))
Resin ๐บ ๐ท
A small automated theorem prover for First Order Classical Logic built on resolution. The resolution machinery follows the Handbook of Practical Logic and Automated Reasoning, supplemented by background from Artificial Intelligence: A Modern Approach (chapters 7โ9); the structure of the implementation reflects those texts.
Show example snippet
constants: zero .
aliases : 0 = zero
, 1 = suc(0) .
axioms: โ n Plus(0, n, n)
, โ n m r Plus(n, m, r) ==> Plus(suc(n), m, suc(r))
, โ n Times(0, n, 0)
, โ n m r a [Times(n, m, r) โง Plus(r, m, a) ==> Times(suc(n), m, a)]
, Fact(0, 1)
, โ n pr r [Fact(n, pr) โง Times(suc(n), pr, r) ==> Fact(suc(n), r)]
.
theorem fact-0-is-1 : Fact(0, 1) .
theorem fact-1-is-1 : Fact(1, 1) .
theorem exists-fact-for-1 : โ n Fact(n, 1) .
Plover ๐น
Plover is a small automated theorem prover based on a logic language like Prolog. The main idea is to replace Minilog's depth-first search strategy with a complete one.
The main difference the complete search strategy makes is that the language can productively answer queries like nat(A). for a knowledge base like the following:
Show example snippet
nat(s(N)) :- nat(N).
nat(z).Minilog ๐ธ
Minilog is an implementation of a small logic programming language. The primary purpose of it is to present a simple abstract machine that can be easily implemented in any language and can serve as an aid when making the intuition about how such a language works.
I have designed the abstract machine and written a short description, Implementing Relational Language, of it for (not only) my students to learn about how such a language works.
It is meant to inspire and offer a starting point to them should they decide to implement a small subset of Prolog as their course project.
Show example snippet
plus(z, N, N).
plus(s(N), M, s(R)) :- plus(N, M, R).
times(z, _, z).
times(s(N), M, A) :- times(N, M, R), plus(R, M, A).
fact(z, s(z)).
fact(s(N), R) :- fact(N, PR), times(s(N), PR, R).Glask ๐ป
Glask is a statically typed, lazy, pure functional language in the spirit of Haskell, written as my master's thesis (CTU FIT,
2022). Built on three papers โ Mark P Jones's Typing Haskell in Haskell,
Simon Peyton Jones et al.'s Practical Type Inference for Arbitrary-Rank Types,
and Peterson & Jones's Implementing Type Classes โ it features constraint-based bidirectional type
inference, higher-rank polymorphism, type classes with dictionary-passing elaboration, higher-kinded data types, and
user-defined prefix/infix/postfix operators resolved by my own variation of Dijkstra's shunting-yard algorithm.
Show example snippet
``` infixl 6 + infixl 6 - infixl 7 * infixl 7 / infix 4 == infixr 5 :class Num a where (+) :: a -> a -> a (-) :: a -> a -> a (*) :: a -> a -> a
instance Num Int where (+) x y = int#+ (x, y) (-) x y = int#- (x, y) () x y = int# (x, y)
class Div a where (/) :: a -> a -> a
instance Div Int where (/) x y = int#/ (x, y)
class Eq a where (==) :: a -> a -> Bool
instance Eq Int where (==) x y = int#== (x, y)
data Bool = True | False
not True = False not False = True
mod :: Int -> Int -> Int mod x y = x - (x / y) * y
divides :: Int -> Int -> Bool divides d n = mod n d == 0
from :: Int -> [Int] from n = n : from (n + 1)
filter :: (a -> Bool) -> [a] -> [a] filter _ [] = [] filter p (x : xs) = if p x then x : filter p xs else filter p xs
sieve :: [Int] -> [Int] sieve (p : xs) = p : sieve (filter (\ x -> not (divides p x)) xs)
primes :: [Int] primes = sieve (from 2)
</details>
### [Frea](https://github.com/jalivert/frea) :chestnut:
Small programming language with HM type inference, higher-kinded types, and lazy evaluation.
Implemented as an AST interpreter in Haskell.
<details>
<summary>Show example snippet</summary>
```haskell
module Main where
{ data Result a
= None
| Some a
; let
{ zero n = (n == 0)
; dec n = (n - 1)
; rec fact n = if (zero n)
then 1
else (n * (fact (dec n)))
} in (Some (fact 5))
}
Lambda-pie ๐ฑ
A version of the implementation described in A Tutorial Implementation of a Dependently Typed Lambda Calculus by Lรถh, McBride, and Swierstra. The dependently typed core (ฮปฮ ) follows the paper's bidirectional Haskell implementation and the simply typed (ฮปโ) and System F (ฮป2) checkers reuse that same architecture with their own type languages. Each calculus additionally gets a concrete parser and an interactive REPL on top of the core.
Show example snippet
``` ฮปฮ >> (lambda t x -> x) :: (forall (t :: *) . (forall (x :: t) . t)) (ฮป t -> (ฮป x -> x)) :: (ฮ t :: * . (ฮ x :: t . t)) ```Lambdulus ๐ฒ
Lambdulus is an interactive learning environment for the untyped lambda calculus. It began as my bachelor thesis Implementation of lambda expressions evaluator and later became a paper I and my supervisor presented at SPLASH-E'19 Lambdulus: Teaching Lambda Calculus Practically. Lambdulus has been used at FIT CTU since the autumn 2019 as a teaching aid for ฮป-calculus.