*To*: Ondřej Kunčar <kuncar at in.tum.de>, cl-isabelle-users at lists.cam.ac.uk, Andreas Lochbihler <andreas.lochbihler at inf.ethz.ch>*Subject*: Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping*From*: Christian Sternagel <c.sternagel at gmail.com>*Date*: Fri, 25 Oct 2013 13:50:27 +0900*In-reply-to*: <52693A88.3060209@in.tum.de>*References*: <5268E404.9050304@gmail.com> <1382607313.2510.16.camel@lapbroy33> <5268EF80.6040002@in.tum.de> <5269241A.1080902@gmail.com> <52693A88.3060209@in.tum.de>*User-agent*: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0

Dear Andreas and Ondřej,

Afterwards I manually proved that match_term_list E σ = Option.map Mapping.lookup (match_term_list' E (Mapping σ))

match_list E = Option.map (subst_of_map undefined ∘ Mapping.lookup) (match_term_list' E Mapping.empty)

data Mapping a b = Assoc_List_Mapping (DAList.Alist a b) | RBT_Mapping (RBT_Mapping2.Mapping_rbt a b) | Mapping (a -> Maybe b); cheers chris On 10/25/2013 12:19 AM, Ondřej Kunčar wrote:

lift_definition gives you a logical definition of the new function. But you have to still provide a code equation for this new function (as it is described in the paper I've already referred to). Then you have two options: A) state the new code equation by yourself and prove it by transfer (Isabelle 2013). B) Since Isabelle 2013-1, there is a limited support for transferring "in the other direction" by the attribute Transfer.transferred. The problem in this solution is that the raw terms for map operations are very general terms like term application (for map lookup) and so on. Andreas showed us in his file a trick that actually Peter Lammich does in his autoref framework, namely rewriting these term applications to an ad-hoc constants by simplifier and then using Transfer.transferred. The question is, of course how, much this solution scale. I am curious to hear some report about that from you. Ondrej On 10/24/2013 03:43 PM, Christian Sternagel wrote:Dear all, Thanks for the useful answers. For my concrete case: does "lift_definition" also work for recursive functions (whith "match_list" is). With my first attempt using "lift_definition" I just got a "wrapper" around the recursive function that changed the type, which doesn't solve the efficiency problem. cheers chris On 10/24/2013 06:59 PM, Ondřej Kunčar wrote:Hi Christian, Peter has already explained the situation in general. I just want to add that Lifting/Transfer can indeed help you a bit in moving your specification from 'a => 'b option to ('a, 'b) mapping. Please see Chapter 4 in our ITP 2013 paper: Data Refinement in Isabelle/HOL. Best, Ondrej On 10/24/2013 11:35 AM, Peter Lammich wrote:Hi Christian. The problem is, that ('a,'b) map is just syntactic sugar for the type 'a => 'b option. The code-generator replacement of types by efficient implementations only works for types represented by a single type-constant (like ('a,'b) mapping or 'a set). Moreover, note that, in general, you do not want to translate all occurences of "'a -> 'b option" by a map implementation, as there are also functions that return option-values, which are intended to be translated as functions. The automatic refinement framework [1] tries to tackle this problem, however, it has to be employed manually before code generation, and usually requires some setup overhead. In order to use Containers, I believe that you should transform your functions to use mapping. Maybe the transfer+lifting package of Brian and Ondra may help you to automate this task. Best, Peter [1]: Peter Lammich, Automatic Data Refinement, Proc. of ITP 2013 On Do, 2013-10-24 at 18:10 +0900, Christian Sternagel wrote:Dear all (especially Andreas ;)), is it possible to automatically get efficient code when code generating a function involving the "('a, 'b) map" type (i.e., "'a => 'b option"). If I import AFP/Containers I can have this for "('a, 'b) mapping" (which is a type-copy of "('a, 'b) map"). But in the actual formalization "('a, 'b) map" is more convenient to use since we have nice syntax like "m x" for lookup and "m (x |-> t)" for update. Since according to the user guide the above is possible w.r.t. "'a set", I was wondering what the obstacle is for "('a, 'b) map" (or maybe I just misunderstood something). More concretely, what is your advice for a function like match_list :: (('f, 'v) term * ('f, 'v) term) list => ('v => ('f, 'v) term option) => ('f, 'v) subst where "match_list E Map.empty" gives a matcher for all equations in "E". Would you change this to use "('v, ('f, 'v) term) mapping" instead, or is there a way to get efficient code as it is? Thanks in advance! cheers chris

**Attachment:
Matching_Test.thy**

**Follow-Ups**:**Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping***From:*Andreas Lochbihler

**References**:**[isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping***From:*Christian Sternagel

**Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping***From:*Peter Lammich

**Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping***From:*Ondřej Kunčar

**Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping***From:*Christian Sternagel

**Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping***From:*Ondřej Kunčar

- Previous by Date: [isabelle] Call for participation: APLAS and CPP 2013
- Next by Date: Re: [isabelle] [isabelle-dev] Partial functions
- Previous by Thread: Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping
- Next by Thread: Re: [isabelle] efficient code for ('a, 'b) map (as opposed to ('a, 'b) mapping
- Cl-isabelle-users October 2013 archives indexes sorted by: [ thread ] [ subject ] [ author ] [ date ]
- Cl-isabelle-users list archive Table of Contents
- More information about the Cl-isabelle-users mailing list