CODEWITHSUNDEEP
compilationcoqtranslateagda
user5775230
user5775230

Reputation:

Translating Coq Definitions to agda?

I'm wondering if there is a systematic way to interpret Coq Definitions as agda programs. I'm working through translating part of programming foundations and am not able to get the tUpdate function to work below. Why is this failing. The coq code is commented.

--Definition total_map (A : Type) := string -> A.

totalMap : Set → Set
totalMap A = String → A

-- Definition t_empty {A : Type} (v : A) : total_map A :=
-- (fun _ => v).

tEmpty : {A : Set} (v : A) → totalMap A
tEmpty = λ v x → v

-- Definition t_update {A : Type} (m : total_map A)
-- (x : string) (v : A) :=
-- fun x' => if eqb_string x x' then v else m x'.

tUpdate : {A : Set} (m : totalMap A) (x : String) (v : A) → Set 
tUpdate m x v = λ x' → (if (x == x') then v else m x')

The lambda term produces the below error

(x' : String) → A !=< Set of type Set
when checking that the expression
λ x' → if x == x' then v else m x' has type Set

Is this a correct general schema for doing this translation, e.g., is this translation sound and complete?

Edit:

I realized update was supposed to return a map, but i'm confused as it coq can seemingly infer this while agda can't? I'd still welcome a more general answer to the latter question.

tUpdate : {A : Set} (m : totalMap A) (x : String) (v : A) → totalMap A
tUpdate m x v = λ x' → (if (x == x') then v else m x')

Upvotes: 1

Views: 261

Answers (1)

Jesper
Jesper

Reputation: 2945

Coq and Agda are both based on very roughly the same dependent type theory, so in theory it would be possible to take the proof term generated by a Coq script and translate it into an Agda program. However, there are many small (and not so small) differences, e.g. Coq's impredicative Prop, cumulativity, differences in the termination checkers, ect, that would make such a translation difficult or impossible.

However, what you're asking for here isn't really an automatic translator but rather a set of rules for translating Coq to Agda by hand. Since many basic features can be mapped one-to-one, this process is much more straightforward. However, any use of tactics in the Coq code you'll either have to translate to an explicit proof term in Agda or write your own Agda reflection macros (since there is no full tactic library for Agda yet).

To answer the specific problem you encountered here: Agda did not try to infer the return type of the tUpdate function because you already specified it to be Set yourself. If you want Agda to infer it for you, you can simply replace the return type with an underscore _ (which works fine in this case):

tUpdate : {A : Set} (m : totalMap A) (x : String) (v : A) → _
tUpdate m x v = λ x' → (if (x == x') then v else m x')

Upvotes: 3

Related Questions