Coq Lessons

The difference between {x = y} + {x <> y} and x \/ y is whether the result is of type Prop or type Set.

Inductive or (A B:Prop) : Prop :=
| or_introl : A -> A \/ B
| or_intror : B -> A \/ B

See Logic and Specif.

The only feature of Section is to apply all the “Variable”s as implicit first arguments to everything listed in the particular section.

Searching for an element in a list is essentially an existsb operation.

Compare the following theorems:

Theorem C_eq_dec:
forall (x y:C), {x = y} + {x <> y}.
Proof.
intros x y.
decide equality.
apply id_eq_dec.
Qed.

Theorem C_eq_dec:
forall (x y:C), {x = y} + {x <> y}.
Proof.
intros x; case x as [|id_x]; intros y; case y as [|id_y]; eauto.

right; intros H; inversion H.
right; intros H; inversion H.
case (id_eq_dec id_x id_y) as [EQ|NEQ]; [ rewrite EQ; left | right ]; eauto.
intros H; eapply NEQ; inversion H; eauto.
Qed.

The first version uses the decide equality tactic. Note that the ML program can be obtained using “Extraction C_eq_dec.” C_eq_dec is also a function that can now be called. For example, it can appear in a match expression like:

match C_eq_dec c c’ with
| right _ => None
| left  _ => Some (HeapObj c cfll)
end

where left and right constructors are explained in Specif (under Inductive sumbool …).

As for declaring “Heap” as a map, here is the syntax I finally got to work. Apparently the requires are important (using fully qualified names without them did not work).

Require Import Coq.FSets.FMapWeakList.
Require Import OrderedTypeEx.
Module MyModule (Heap:FMapInterface.S with Module E := Nat_as_OT).

Coq Syntax

I’m learning how to use the FMapInterface class of modules in Coq. A search for FMapInterface led me to A Machine Checked Model of Idempotent MGU Axioms For
Lists of Equational Constraints
which had a link to its corresponding Coq script. Poking around in that script led me to the line:

Module Nat_as_MyOT <: UsualOrderedType := Nat_as_OT.

I looked up the meaning of the <: syntax. The reference manual explains that it “starts an interactive module satisfying each” subsequent module type. The ModuleSystemTutorial page also has more information on how modules are used.

Breaking Software

I just got my copy of “How to Break Software” yesterday. I read through the first half today and already caught a couple of issues in the DrRacket IDE. Choose File -> Search in Files and then clear the directory name input and click OK. Some exception window shows up. Next, try setting the font size by dragging the slider in preferences all the way to the left. The program hangs instantly, and the erroneous setting is stored for the next startup. The only way to recover is to manually edit the config file in %appdata%/Racket to save the day.

Longest Common Nonsequential Subsequence

If we need the longest common sub-sequence of two strings but with the caveat that we are only interested in having all the right letters & frequencies, and not their orders, then dynamic programming isn’t really necessary. This boils down to the problem of finding the largest common subset of the two sets of letters in the two strings.

The Fifteen Puzzle

I remember playing the fifteen-puzzle game on our first computer – an 80486 running Windows 3.1. It was a variation that used images instead of numbers, but I still remember how intriguing it was at that age. Well, today is the first time I’ve figured out it’s official name, thanks to some brainstorming with the folks in the lab (& Google, obviously).