Re: Smap: Collecting small programs

From: David Powers <david.powers_at_flinders.edu.au>
Date: Wed, 29 Oct 2014 23:22:12 +0000

On 29 Oct 2014, at 10:54 pm, Michael Hanus <mh_at_informatik.uni-kiel.de<mailto:mh_at_informatik.uni-kiel.de>> wrote:

On 10/29/2014 12:10 AM, David Powers wrote:
...
I would also propose to put up some programs that test the definition of
the language and/or have different behaviour under the different Curry systems.

What do you have in mind? Different Curry systems differ in their
computational power, e.g., KiCS2 supports various search strategies
and is sometimes "lazier" than PAKCS, but the computed results,
if they are computed, should be the same.
...
Best regards,

Michael


There are four things that have come up in my play with Curry (as a Logic Programmer) with various qsort variations - all four occur in a difference list version that implements median of medians for true O(nlogn) qsort without O(n^2) worstcase, but the first can be illustrated in a simpler context. (I don’t have access to a working curry install right now though and these examples were created and run a year or two ago: I was looking to replace Prolog and address limitations of Prolog.)
The differences are as to which/whether results are produced, which clearly is a matter of search strategy.
But I also had in mind syntactic/semantic limitations that seem unnecessarily restrictive, and derestricted implementations.

1. Some things I expected in relation to let/where didn’t work but seem to fit syntactic/semantic definitions.

This example is a three-way quicksort where I was surprised that the first version doesn’t work as it is well defined, as illustrated by splitting the problem pattern into separate wheres - I think this should be handled/extended:

qsort list =
  let
part _ [] = ([], [], [])
part p (x:xs) | x <p = (x:ls,es,gs)
| x==p = (ls,x:es,gs)
| x >p = (ls,es,x:gs)
sort [] = []
sort xs_at_(p:_) = sort ls ++ es ++ sort gs
(ls,es,gs) = part p xs
  in sort list

qsort list =
  let
part _ [] = ([], [], [])
part p (x:xs) | x <p = (x:ls,es,gs)
| x==p = (ls,x:es,gs)
| x >p = (ls,es,x:gs)
  where (ls,es,gs) = part p xs
sort [] = []
sort xs_at_(p:_) = sort ls ++ es ++ sort gs
  where (ls,es,gs) = part p xs
  in sort list

2. The operator precedences don’t have enough granularity - I wanted a precedence of 4.5 for difference lists
3/4. There are issues relating to free variables and unification models that prevent translation from Prolog.
These don’t work correctly under any model I have tried and give different results for different systems/models.
I think the issues with free would not be a problem if unification implemented occur check.
But it’s a while since I looked at this… I tried rev on smap without success…
Even adding in ensureNotFree doesn’t help as all disjunctions can suspend…
I do have a working (sicstus/swipl) Prolog version of this!

infixr 4 # -- this should really be 4.5 above =:= below ++ and :
              -- also pattern not allowed at top level without brackets

data DList a = [a] # [a] -- a list and a list suffix (acts as nil if free)


-- rangequicksort with DList - incorporating quicksearch and median of medians

sort cmp list lr hr = (slist (srt (dlist list) lr hr))
  where
        srt (_#_) lo hi | hi < lo || hi < 1
                            = y#y
                            where y free
        srt (x#z) lo hi | z =:= x
                            &> lo <= hi
                            = y#y
                            where y free
        srt (xs#n) lo hi | ensureNotFree xs =:= (p:qs)
                            & lo <=: hi
                            & (ls#es) =:= srt (l#[]) (lo) (hi)
                            & (es#gs) =:= sbr (e#[]) (lo-lc) (hi-lc)
                            & (gs#gn) =:= srt (g#[]) (lo-lc-ec) (hi-lc-ec)
                            = ls#gn
                            where (l#[],e#[],g#[],lc,ec,gc) = prt p (xs#n)
                                  p, qs, ls, es, gs, gn free



        prt _ (x#z) | z =:= x
                            = (l#l, e#e, g#g, 0, 0, 0)
                            where l,e,g free
        prt p (xs#n) | ensureNotFree xs =:= (x:qs)
                            = case cmp x p of LT -> (x:l#ln,e#en,g#gn,lc+1,ec,gc)
                                                  EQ -> (l#ln,x:e#en,g#gn,lc,ec+1,gc)
                                                  GT -> (l#ln,e#en,x:g#gn,lc,ec,gc+1)
                            where (l#ln,e#en,g#gn,lc,ec,gc) = prt p (qs#n)
                                  x, qs free
                            = case cmp x p of LT -> (x:l#ln,e#en,g#gn,lc+1,ec,gc)
                                                  EQ -> (l#ln,x:e#en,g#gn,lc,ec+1,gc)
                                                  GT -> (l#ln,e#en,x:g#gn,lc,ec,gc+1)
                            where (l#ln,e#en,g#gn,lc,ec,gc) = prt p (qs#n)
                                  x, qs free


        sbr (_#_) lo hi | hi < lo
                            = y#y
                            where y free
        sbr (x#z) lo hi | z =:= x
                            &> lo <= hi
                            = y#y
                            where y free
        sbr (xs#n) lo hi | ensureNotFree xs =:= (p:qs)
                            &> 1 < lo && lo <= hi
                            = sbr (qs#n) (lo-1) (hi-1)
                            where p, qs free
        sbr (xs#n) lo hi | ensureNotFree xs =:= (q:qs)
                            & lo <=: 1 & 1 <=: hi
                            & (es#en) =:= sbr (qs#n) lo (hi-1)
                            = (q:es#en)
                            where q, qs, es, en free

dlist [] = (x#x)
      where x free
dlist (x:xs) = (x:xd)#xn
      where xd#xn = dlist xs


slist ([]#[]) = []
slist (xl#xn) | ensureNotFree xl =:= (x:xs)
      = x:slist (xs#xn)
      where x, xs free



app (a#b) (c#n) | b =:= c = (a#n)

rev (m#n) | n =:= m
     = (m#n)
rev (m#n) | ensureNotFree m =:= (h:t) & (r#h:rn) =:= (rev (t#n))
     = (r#rn)
     where h, t, r, rn free


qsort xs = qsort [x|x<-xs,x<p] ++ [x|x<-xs,x==p] ++ qsort [x|x<-xs,x>p]
        where p = rqsmed xs

rqsort xs = sort compare xs 1 len
        where len = length xs

rqsmed xs = sort compare xs mid mid
        where len = length xs
              mid = ((len+1)//2)



rqsrng xs = sort compare xs
        where len = length xs


any comments appreciated

cheers,
David



_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Thu Oct 30 2014 - 17:59:35 CET

This archive was generated by hypermail 2.3.0 : Mon Sep 16 2019 - 07:15:08 CEST