- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Andy Jost <Andrew.Jost_at_synopsys.com>

Date: Mon, 5 Jul 2021 17:18:13 +0000

Hi Michael,

Thank you for the explanation. It makes sense, now. Please let me know if I can help in any way (e.g., by contributing or reviewing documentation changes).

-Andy

-----Original Message-----

From: Michael Hanus <mh_at_informatik.uni-kiel.de>

Sent: Monday, July 5, 2021 2:17 AM

To: Andy Jost <ajost_at_synopsys.com>; 'curry_at_lists.RWTH-Aachen.DE' <curry_at_lists.RWTH-Aachen.DE>

Subject: Re: [curry] Re: Recursion in Set Functions

Hi Andy,

after reading your first message, I realized the problem, but I must admit that the documentation is not satisfying. Since set functions are not part of the language syntax but implemented via a library, illegal uses are not immediately shown. For this purpose, the `curry-check` tool performs some checks. Actually, it reports a wrong use of set functions in your first example.

Conceptually, for each n-ary function `f` there is a n-ary set function `f^set` returning the set of values for `f` applied to n argument values. With the set function library, `f^set` is written as (setn f).

For top-level functions, this works as expected, but for local functions there is a problem. Since local functions are just syntactic sugar for top-level functions where additional arguments are passed (by the lambda lifting process), the arity of a local function is not obvious. Therefore, `setn` should never be applied to local functions. Although this property is not checked by the front end of PAKCS, it is checked by curry-check.

Since the semantics of default rules is defined via set functions, they are only processed for top-level functions (i.e., adding them for local functions just define other operations).

Thus, it is reasonable to check also this use by curry-check to avoid such mistakes...future work...

Regards,

Michael

On 04.07.21 21:32, Andy Jost wrote:

*> After more experimentation, I have found the problem only occurs when
*

*> the auxiliary function is declared in a "where" clauses, as was done
*

*> in all of my attempts. If I move all definitions to the file scope,
*

*> the programs work as I expect. The attached program demonstrates this.
*

*>
*

*>
*

*>
*

*> Is this behavior expected? My understanding is that the only
*

*> difference between the two declaration types is name visibility. Am I wrong?
*

*>
*

*>
*

*>
*

*> Perhaps this issue is related to the use of default rules? I didn't
*

*> see any mention, e.g., here
*

*> <https://urldefense.com/v3/__https://www.informatik.uni-kiel.de/*curry
*

*> /tutorial/tutorial.pdf__;fg!!A4F2R9G_pg!KToP9gm5b58_EwlCAbNYGCNKJEtDCHNPPSXKkOeh0vym-4gxan3bNbb-j--QT-Rkz8E$ >, that they must be defined at file scope, but maybe that is necessary?
*

*>
*

*>
*

*>
*

*> -Andy
*

*>
*

*>
*

*>
*

*> *From:* Andy Jost
*

*> *Sent:* Saturday, July 3, 2021 3:44 PM
*

*> *To:* 'curry_at_lists.RWTH-Aachen.DE' <curry_at_lists.RWTH-Aachen.DE>
*

*> *Subject:* Recursion in Set Functions
*

*>
*

*>
*

*>
*

*> Hi,
*

*>
*

*>
*

*>
*

*> I have run into an unexpected (to me) behavior when using set
*

*> functions. I want to write a function that calculates a "penalty"
*

*> that equals the number of times any character repeats three times in a
*

*> string. For example, "aaaa" has penalty two, while "aabaa" has
*

*> penalty zero.
*

*>
*

*>
*

*>
*

*> I thought it might be fun to use a functional pattern, so I wrote the
*

*> following:
*

*>
*

*>
*

*>
*

*> penalty1 (b++[x,x,x]++e) = 1 + penalty1 (b++[x,x]++e)
*

*>
*

*> penalty1'default _ = 0
*

*>
*

*>
*

*>
*

*> Although this works, it scales as the factorial of the longest
*

*> substring of repeated characters.
*

*>
*

*>
*

*>
*

*> I thought I could improve it by introducing a set function and then
*

*> using selectValue to cut down the search space. My idea was to
*

*> recursively remove one character from an arbitrary triple, repeating
*

*> until there are no more triples and counting the iterations. Rather
*

*> than choosing every way to remove a character, I just want to choose
*

*> one of them.
*

*>
*

*>
*

*>
*

*> I tried coding this several ways (below), but each time the result is
*

*> "no value found." I am using PAKCS 3.3.0.
*

*>
*

*>
*

*>
*

*> Is this the expected behavior? Does it suggest a problem with the
*

*> implementation of set functions or with my understanding of them? Can
*

*> anyone point towards a solution using functional patterns? Other
*

*> methods -- e.g., a pure-Haskell solution -- are trivial, so there's no
*

*> need to point them out.
*

*>
*

*>
*

*>
*

*> Thanks,
*

*>
*

*> -Andy
*

*>
*

*>
*

*>
*

*>
*

*>
*

*> penalty2 pw = selectValue $ (set1 aux) pw
*

*>
*

*> where
*

*>
*

*> aux (b++[x,x,x]++e) = 1 + penalty2 (b++[x,x]++e)
*

*>
*

*> aux'default _ = 0
*

*>
*

*>
*

*>
*

*> penalty3 pw = selectValue $ (set1 aux) pw
*

*>
*

*> where
*

*>
*

*> aux (b++[x,x,x]++e) = 1 + aux (b++[x,x]++e)
*

*>
*

*> aux'default _ = 0
*

*>
*

*>
*

*>
*

*> penalty4 pw = let pw' = next pw in if pw' == [] then 0 else 1 +
*

*> penalty4 pw'
*

*>
*

*> where
*

*>
*

*> next pw' = selectValue $ (set1 aux) pw'
*

*>
*

*> aux (b++[x,x,x]++e) = b++[x,x]++e
*

*>
*

*> aux'default _ = []
*

*>
*

*>
*

*>
*

*>
*

*> _______________________________________________
*

*> curry mailing list -- curry_at_lists.rwth-aachen.de To unsubscribe send
*

*> an email to curry-leave_at_lists.rwth-aachen.de
*

*> https://urldefense.com/v3/__https://lists.rwth-aachen.de/postorius/lis
*

*> ts/curry.lists.rwth-aachen.de__;!!A4F2R9G_pg!KToP9gm5b58_EwlCAbNYGCNKJ
*

*> EtDCHNPPSXKkOeh0vym-4gxan3bNbb-j--Q9Mt6Kp0$
*

*>
*

_______________________________________________

curry mailing list -- curry_at_lists.rwth-aachen.de

To unsubscribe send an email to curry-leave_at_lists.rwth-aachen.de

https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de

Received on Di Jul 06 2021 - 09:34:49 CEST

Date: Mon, 5 Jul 2021 17:18:13 +0000

Hi Michael,

Thank you for the explanation. It makes sense, now. Please let me know if I can help in any way (e.g., by contributing or reviewing documentation changes).

-Andy

-----Original Message-----

From: Michael Hanus <mh_at_informatik.uni-kiel.de>

Sent: Monday, July 5, 2021 2:17 AM

To: Andy Jost <ajost_at_synopsys.com>; 'curry_at_lists.RWTH-Aachen.DE' <curry_at_lists.RWTH-Aachen.DE>

Subject: Re: [curry] Re: Recursion in Set Functions

Hi Andy,

after reading your first message, I realized the problem, but I must admit that the documentation is not satisfying. Since set functions are not part of the language syntax but implemented via a library, illegal uses are not immediately shown. For this purpose, the `curry-check` tool performs some checks. Actually, it reports a wrong use of set functions in your first example.

Conceptually, for each n-ary function `f` there is a n-ary set function `f^set` returning the set of values for `f` applied to n argument values. With the set function library, `f^set` is written as (setn f).

For top-level functions, this works as expected, but for local functions there is a problem. Since local functions are just syntactic sugar for top-level functions where additional arguments are passed (by the lambda lifting process), the arity of a local function is not obvious. Therefore, `setn` should never be applied to local functions. Although this property is not checked by the front end of PAKCS, it is checked by curry-check.

Since the semantics of default rules is defined via set functions, they are only processed for top-level functions (i.e., adding them for local functions just define other operations).

Thus, it is reasonable to check also this use by curry-check to avoid such mistakes...future work...

Regards,

Michael

On 04.07.21 21:32, Andy Jost wrote:

_______________________________________________

curry mailing list -- curry_at_lists.rwth-aachen.de

To unsubscribe send an email to curry-leave_at_lists.rwth-aachen.de

https://lists.rwth-aachen.de/postorius/lists/curry.lists.rwth-aachen.de

Received on Di Jul 06 2021 - 09:34:49 CEST

*
This archive was generated by hypermail 2.3.0
: So Jan 23 2022 - 07:15:05 CET
*