lisp-java-d.dd

Ddoc

$(COMMUNITY Lisp vs. Java... D?,

<center>
$(I by Lionello Lunesu, Oct. 18th 2006)
</center>

        <p>Two weeks ago, Josh Stern posted an
	$(LINK2 http://www.digitalmars.com/d/archives/digitalmars/D/Lisp_vs._C_not_off-topic_42717.html, interesting link)
	on the
	<a href="http://www.digitalmars.com/d/archives/digitalmars/D/index.html">digitalmars.D newsgroup</a>.
	The link pointed to a
	<a href="http://userpages.umbc.edu/~bcorfm1/C++-vs-Lisp.html">page describing a programming challenge</a>
	that was originally used in a 
            study in which 38 C, C++ and Java programmers were asked to write versions of a 
            program to compare Java and C++ efficiency.
        </p>

        <p>Many other programmers had taken up the challenge since. In <a href="http://www.norvig.com/java-lisp.html">
                one such comparison</a>, Lisp turned out to be a clear winner over Java and 
            C++ when comparing development time and lines of code, with the record standing 
            at about 2 hours, with 45 non-comment non-blank lines. For C++, the shortest 
            development time was 3 hours and the
	    shortest program had 107 lines of code.
	</p>
        <p>With some time to spare, I thought I should give it a try myself. Although I'm a 
            C++ programmer myself (and have been for 10 years now), I thought it would be a 
            great opportunity to test my skills in the <a href="http://www.digitalmars.com/d/">D 
                programming language</a>.</p>
        <p>I had not looked at the other implementations and only read the <a href="http://www.flownet.com/ron/papers/lisp-java/">
                original problem statement</a>. It took me <strong>1 hour and 15 minutes</strong>, 
            from reading the statement to finishing the program. The program was just 55 
            lines long (remember, the
	    shortest C++ entry
	    had 107 lines), not counting blank 
            lines, comments, assertions, unittests, contracts and trailing curly brackets 
            (similar to Lisp).
        </p>
        <p>The program basically had to do this: read all words from a dictionary file; for 
            each letter there was a corresponding digit (like the letters on a phone); 
            using this mapping, read phone numbers from another text file and print all 
            possible combinations of words for that phone number. Check the link above for 
            more details.</p>
        <p>What made implementing this task so easy in D? I just happened to have every 
            construct I needed at hand. Some of the goodies used, are:</p>
        $(UL 
            $(LI Assertions, contracts and unittests)
            $(LI Built-in arrays and strings, with easy slicing)
            $(LI Built-in associative array)
            $(LI Garbage collection)
            $(LI Type deduction and foreach)
            $(LI Nested functions)
            $(LI Returning (reference to) a array from a function)
        )
        <p>During the actual programming I did not have to stop and think about anything. 
            The program evolved automatically, once I thought of the actual container for 
            the dictionary. It turned out that the $(SINGLEQUOTE winning) Lisp version was storing the 
            dictionary in a similar manner.</p>
        <h2>Compiling</h2>
        <p>To test the program yourself, first download the <a href="http://www.flownet.com/ron/papers/lisp-java/dictionary.txt">
                dictionary.txt</a> and <a href="http://www.flownet.com/ron/papers/lisp-java/input.txt">
                input.txt</a>. Then, <a href="http://www.digitalmars.com/d/download.html">download 
                the latest D compiler</a>. To compile,
		copy-paste the D code into a newly created file
		phoneno.d, and compile it with:
        </p>
$(CONSOLE
dmd -run phoneno.d
)

---------------------
// Created by Lionello Lunesu and placed in the public domain.
// This file has been modified from its original version.
// It has been formatted to fit your screen.
module phoneno;     // optional
import std.stdio;   // writefln     
import std.ctype;   // isdigit     
import std.stream;  // BufferedFile

// Just for readability (imagine char[][][char[]])    
alias char[] string;
alias string[] stringarray;

/// Strips non-digit characters from the string (COW)
string stripNonDigit( in string line ) 
{
    string ret;
    foreach(uint i, c; line) {
        // Error: std.ctype.isdigit at C:\dmd\src\phobos\std\ctype.d(37) 
        // conflicts with std.stream.isdigit at C:\dmd\src\phobos\std\stream.d(2924)
        if (!std.ctype.isdigit(c)) {
            if (!ret)
                ret = line[0..i];    
        }    
        else if (ret)
            ret ~= c;    
    }    
    return ret?ret:line;
}

unittest {
    assert( stripNonDigit("asdf") == ""  );
    assert( stripNonDigit("\'13-=2 4kop") ==  "1324"  );
}

/// Converts a word into a number, ignoring all non alpha characters  
string wordToNum( in string word )
{
// translation table for the task at hand
const char[256] TRANSLATE =    
    "                                "  // 0   
    "                0123456789      "  // 32     
    " 57630499617851881234762239     "  // 64   
    " 57630499617851881234762239     "
    "                                "
    "                                "
    "                                "    
    "                                ";
    string ret;
    foreach(c; cast(ubyte[])word)
        if (TRANSLATE[c] != ' ')
            ret ~= TRANSLATE[c];
    return ret;
}

unittest {
 // Test wordToNum using the table from the task description.
 assert( "01112223334455666777888999" ==
   wordToNum("E | J N Q | R W X | D S Y | F T | A M | C I V | B K U | L O P | G H Z"));
 assert( "01112223334455666777888999" == 
   wordToNum("e | j n q | r w x | d s y | f t | a m | c i v | b k u | l o p | g h z"));
 assert( "0123456789" == 
   wordToNum("0 |   1   |   2   |   3   |  4  |  5  |   6   |   7   |   8   |   9"));
}

void main( string[] args )
{
    // This associative array maps a number to an array of words.    
    stringarray[string]    num2words;

    foreach(string word; new BufferedFile("dictionary.txt" ) )
        num2words[ wordToNum(word) ] ~= word.dup;        // must dup

    /// Finds all alternatives for the given number
    /// (should have been stripped from non-digit characters)
    stringarray _FindWords( string numbers, bool digitok )
    in {
        assert(numbers.length >  0);    
    }    
    out(result) {
        foreach (a; result)
            assert( wordToNum(a) == numbers );
    }    
    body {
        stringarray ret;
        bool foundword = false;
        for (uint t=1; t<=numbers.length; ++t) {
            auto alternatives = numbers[0..t] in num2words;
            if (!alternatives)
                continue;
            foundword = true;
            if (numbers.length >  t) {
                // Combine all current alternatives with all alternatives     
                // of the rest (next piece can start with a digit)              
                foreach (a2; _FindWords( numbers[t..$], true     ) )
                    foreach(a1; *alternatives)
                       ret ~= a1 ~ " " ~ a2;
            }
            else    
                ret ~= *alternatives;    // append these alternatives
        }
        // Try to keep 1 digit, only if we're allowed and no other
        // alternatives were found
        // Testing "ret.length" makes more sense than testing "foundword",
        // but the other implementations seem to do just this.
        if (digitok && !foundword) { //ret.length == 0  
            if(numbers.length >  1) {
                // Combine 1 digit with all altenatives from the rest    
                // (next piece can not start with a digit)          
                foreach (a; _FindWords( numbers[1..$], false ) )
                    ret ~= numbers[0..1] ~ " " ~ a;
            }    
            else    
                ret ~= numbers[0..1];    // just append this digit             
        }    
        return ret;
    }

    /// (This function was inlined in the original program) 
    /// Finds all alternatives for the given phone number 
    /// Returns: array of strings 
    stringarray FindWords( string phone_number )
    {
        if (!phone_number.length)
            return null;
        // Strip the non-digit characters from the phone number, and
        // pass it to the recursive function (leading digit is allowed)
        return _FindWords( stripNonDigit(phone_number), true );    
    }    
    
    // Read the phone numbers     
    foreach(string phone; new BufferedFile("input.txt"   ) )
        foreach(alternative; FindWords( phone ) )
            writefln(phone, ": ", alternative );
}
---------------------

)

Macros:
	TITLE=Lisp vs. Java... D?
	WIKI=LispVsJavaVsD
	CATEGORY_OVERVIEW=$0
	COPYRIGHT=