Re: MIU in Curry

From: Wolfgang Jeltsch <wolfgang_at_cs.ioc.ee>
Date: Wed, 24 Apr 2013 13:23:34 +0300

Hi Sebastian,

thank you for your answer.

The point is that I *do* use breadth-first search. The last line of my
code uses allValuesBFS. It doesn’t work nevertheless.

Using iterate with the rewrite function, you can compute derivable
strings. This is similar to my function applyRules. However, applyRules
computes finite derivations instead of infinite ones. Furthermore,
applyRules also takes into account the rules that are used.

My applyRules function works very well. The problem only pops up in the
derivation function. There, I use =:= to select all derivations that end
in the desired string, and I use a free variable rules to compute the
applied rules instead of providing them as a function argument.

Would you maybe like to have a look at the derivation function to see
what goes wrong there? This would be very helpful for me, since I have
no clue about where the problem lies.

Best wishes,
Wolfgang

Am Mittwoch, den 24.04.2013, 10:17 +0200 schrieb Sebastian Fischer:
> Hi Wolfgang,
>
> I also wrote a Curry-verision, after reading your post ;) Here it is:
>
> rewrite :: String -> String
> rewrite (x ++ "I") = x ++ "IU"
> rewrite ("M" ++ x) = "M" ++ x ++ x
> rewrite (x ++ "III" ++ y) = x ++ "U" ++ y
> rewrite (x ++ "UU" ++ y) = x ++ y
>
> test :: Int -> [String]
> test n = filter (=="MIU") . take n $ iterate rewrite "MI"
>
> It just uses predefined functions take and iterate to limit the search
> depth but I expect you could also use breadth first search in KiCS2 to
> avoid an explicit limit.
>
> Best,
> Sebastian
>
> On Tue, Apr 23, 2013 at 7:48 PM, Wolfgang Jeltsch <wolfgang_at_cs.ioc.ee> wrote:
> > Hi,
> >
> > I have recently implemented a derivation engine for the MIU system from
> > Douglas Hofstadter’s book “Gödel, Escher, Bach” in Haskell. See my blog
> > post:
> >
> > <http://jeltsch.wordpress.com/2013/04/18/miu-in-haskell/>
> >
> > Now I wanted to implement the same thing in Curry, since this could
> > dramatically simplify the code. I wrote an implementation, which I have
> > attached to this e-mail.
> >
> > Unfortunately when I try out this implementation, it prints at most one
> > solution and then causes heavy use of the swap partition. So if anyone
> > would be interested in looking at the code and giving me hints for
> > improving it, I would be very thankful.
> >
> > Best wishes,
> > Wolfgang
> >
> > _______________________________________________
> > curry mailing list
> > curry_at_lists.RWTH-Aachen.DE
> > http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
> >


_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mi Apr 24 2013 - 15:57:47 CEST

This archive was generated by hypermail 2.3.0 : Do Jun 20 2024 - 07:15:12 CEST