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 Do Okt 30 2014 - 17:59:35 CET