%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% bubble.dtr
% D. Gibbon, U Bielefeld
% 11 Jan 1997
% Contents:
% A. DESCRIPTION
%    1. Possible linguistic use
%    2. Method
%    3. Algorithm
%    4. I/O declaration
%    5. I/O example
%    6. ZDATR statistics
%    7. Comments
% B. COMMENTED CODE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% A. DESCRIPTION
%
% 1. Possible linguistic use: Evaluation in Optimality Theory
%
% 2. Method: Naive bubble sort.
%
% 3. Algorithm:
%    proc bubble(sequence)
%    if sorted(sequence)
%       then output(copy(sequence))
%       else bubble(permute(sequence))
%
%    Data type: atom sequence.
%
%    Special feature: Subdomains sorted separately (here char and bit).
%
% 4. I/O declaration:
%    # hide Permute Sorted? Copy.
%    # show
%    < c c c b b b a a a b b b c c c>
%    < 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1>
%    < 1 1 1 0 0 0 1 1 0 1 0 1 c c c b b b a a a b b b c c c >
%    .
%
% 5. I/0 example:
%    Bubble:< c c c b b b a a a b b b c c c > = a a a b b b b b b c c c c c c .
%    Bubble:< 1 1 1 0 0 0 1 1 0 1 0 1 > = 0 0 0 0 0 1 1 1 1 1 1 1 .
%    Bubble:< 1 1 1 0 0 0 1 1 0 1 0 1 c c c b b b a a a b b b c c c >
%     = 0 0 0 0 0 1 1 1 1 1 1 1 a a a b b b b b b c c c c c c .
%    The I/O example is in a separate procedural declaration file for
%    ZDATR. These lines can be uncommented for other DATR implementations.
%
% 6. ZDATR statistics (Linux, 486 75 Mhz Compaq 420c notebook):
%    `# show' inputs
%      <X Y>, <X X Y Y>, <X X X Y Y Y>, <X X X X Y Y Y Y>
%     for X = 1 1 1 1 1 1 1 1 1 1, Y = 0 0 0 0 0 0 0 0 0 0
%     Results clearly show the complexity curve:
%     -------------------------------------
%     Inferences  : 570
%     Active[sec] : 0.13
%     Queries/sec : 7.61
%     Inf./sec    : 4338.49
%     Inf./Queries: 570.00
%     -------------------------------------
%     Inferences  : 2035
%     Active[sec] : 1.08
%     Queries/sec : 0.93
%     Inf./sec    : 1890.42
%     Inf./Queries: 2035.00
%     -------------------------------------
%     Inferences  : 4400
%     Active[sec] : 4.39
%     Queries/sec : 0.23
%     Inf./sec    : 1003.08
%     Inf./Queries: 4400.00
%     -------------------------------------
%     Inferences  : 7665
%     Active[sec] : 12.43
%     Queries/sec : 0.08
%     Inf./sec    : 616.72
%     Inf./Queries: 7665.00
%     -------------------------------------
%
% 7. Comments:
%    - The algorithm is well-known, and standard variants can easily
%      be implemented.
%    - I am not sure if the bubble sort has been implemented in DATR before.
%      Surely Lionel Moser must have done it way back when, if no-one else,
%      but there is no sort implementation in my DATR theory collection.
%    - The implementation was tested with ZDATR.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% B. COMMENTED CODE
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Declaration of sequence element domain

# vars $VAR: a b c 1 0 .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Main
% proc bubble(sequence)
% if sorted(sequence)
%    then output(copy(sequence))
%    else bubble(permute(sequence))
% Comment: the use of the `lop' device enables functional programming 
%          without catastrophic recursive path extension.
%          In this version, `softlop' (the unmatching atom) is used;
%          destructive `hardlop' is implemented in some DATR versions.
%          The semantics of `softlop' and `hardlop' differ wrt on the fly
%          variables: `softlop' matches these, `hardlop' doesn't, hence
%          the variable declaration.

Bubble:
 <>             == <if Sorted?>
 <if sorted>    == Copy:<>
 <if unsorted>  == < Permute:<> softlop > .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Called by main
% Generates one bubble train
% proc permute(sequence)
% if gt(car,cadr)
%    then conc(cadr,permute(car|cddr))
%    else conc(car,permute(cdr))

Permute:
 <>     ==
 <$VAR>    == $VAR <> 
% Permute char domain:
 <b a>  == a <b>  
 <c a>  == a <c>
 <c b>  == b <c>
% Permute bit domain:
 <1 0>  == 0 <1> .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Called by main
% Tests (un)sortedness, immediate exit
% proc sorted?
% if empty
%    then sorted
%    else if gt(car,cadr)
%            then unsorted
%            else sorted?(cdr)

Sorted?:
 <>      == sorted
 <$VAR>  == <>
 <b a>   == unsorted
 <c a>   == unsorted
 <c b>   == unsorted
 <1 0>   == unsorted .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Called by main
% I/O identity function
% proc copy (sequence)
% if empty
%    then nil
%    else conc(car,copy(cdr))

Copy:
 <>       ==
 <$VAR>   == $VAR <> .

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%