A quick comparison of Euclid’s Algorithm in Haskell, Rust, and D

I recently procured a copy of Graham Hutton’s most excellent book, “Programming in Haskell” (2nd Edition). I had earlier worked through the first edition, and that is the book that really opened my eyes to the power of Haskell! Having become a bit rusty with my Haskell, I decided to work through the second edition book (which is considerably larger and more comprehensive). As part of that exercise, I decided to use a lazy weekend afternoon to code up Euclid’s GCD Algorithm in Haskell, Rust and in D. Just for a quick visual comparison of how the languages look. Here’s how they look:

First off, the Haskell version, which is the best looking one in my opinion:

Macushla:Playground z0ltan$ cat Euclid.hs
module Main where

euclid :: Int -> Int -> Int
euclid m n | m <= 0 && n <= 0 = error "GCD works for positive numbers only"
           | m == n = m
           | m < n = euclid m (n-m)
           | otherwise = euclid (m-n) n

main :: IO ()
main = do putStrLn "Enter the first number: "
          x <- getLine
          putStrLn "Enter the second number: "
          y <- getLine
          let x' = read x :: Int
          let y' = read y :: Int

          putStrLn $ "The GCD of " ++ x
                     ++ " and " ++ y
                     ++ " is " ++ show (euclid x' y')

Macushla:Playground z0ltan$ ghc Euclid.hs
[1 of 1] Compiling Main             ( Euclid.hs, Euclid.o )
Linking Euclid ...
Macushla:Playground z0ltan$ ./Euclid
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

Here’s the Rust version (a bit uglier, but the Pattern Matching is quite nice):

Macushla:Playground z0ltan$ cat euclid.rs
use std::io;
use std::str::FromStr;
use std::cmp::Ordering;

fn get_number(prompt: &str) -> u32 {
    println!("{}", prompt);

    let mut input = String::new();

    io::stdin().read_line(&mut input)
        .expect("no input!");

    u32::from_str(input.trim()).unwrap()
}

fn main() {
    let x = get_number("Enter the first number: ");
    let y = get_number("Enter the second number: ");

    println!("The GCD of {} and {} is {}", x, y, euclid(x, y));
}

fn euclid(m: u32, n: u32) -> u32 {
    assert!(m > 0 && n > 0);

    match m.cmp(&n) {
        Ordering::Equal => m,
        Ordering::Less => euclid(m, n-m),
        Ordering::Greater => euclid(m-n, n),
        }
}
Macushla:Playground z0ltan$ rustc euclid.rs && ./euclid
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

And finally, here is the D version – clean, succinct, and a pleasure to read as always:

Macushla:Playground z0ltan$ cat euclid.d
import std.stdio: readln, writeln, writefln;

uint get_number(string prompt) {
    writeln(prompt);

    import std.conv: to;
    import std.string: chomp;

    return readln().chomp().to!(uint);
}

void main() {
    uint x = get_number("Enter the first number: ");
    uint y = get_number("Enter the second number: ");

    writefln("The GCD of %s and %s is %s", x, y, euclid(x, y));
}

uint euclid(uint m, uint n) {
    assert(m > 0 && n > 0);

    if (m < n) {
        return euclid(m, n-m);
    } else if (m == n) {
        return m;
    } else {
        return euclid(m-n, n);
    }
}
Macushla:Playground z0ltan$ dmd -run euclid.d
Enter the first number:
12
Enter the second number:
18
The GCD of 12 and 18 is 6

One thing is for sure. Aside from syntactic differences, most modern languages are all converging in terms of paradigms and features. Hell, even keeping languages like Haskell and Idris aside, most mainstream languages are also converging on the syntactical front! Anyway, this was a fun little exercise on a slow afternoon. I personally like the Haskell version best , followed by the D version, and then finally the Rust version (ruined by the somewhat ugly I/O syntax). What do you think?

A quick comparison of Euclid’s Algorithm in Haskell, Rust, and D

A simple guessing game in D

This short post is inspired by the recent spate of languages introducing themselves through a small game program. As such, here is a version of the guessing game in D.

The objective of the game is very simple – there is a secret number randomly generated per game (in the range [1, 100] for simplicity), and the user has to guess the number to exit the game.

I also wanted to get a bit more practice with the de facto package cum dependency manager for D, dub.

Let’s start off by creating the project:

Macushla:MiniProjects z0ltan$ dub init guessing_game
Package recipe format (sdl/json) [json]: json
Name [guessing_game]: 
Description [A minimal D application.]: A simple guessing game in D
Author name [Timmy Jose]: 
License [proprietary]: MIT
Copyright string [Copyright © 2017, Timmy Jose]: 
Add dependency (leave empty to skip) []: 
Successfully created an empty project in '/Users/z0ltan/Rabota/ProgrammingLanguages/D/MiniProjects/guessing_game'.
Package successfully created in guessing_game

By default, dub also creates a .gitignore file in the root directory of the new project/package.

Here’s how the layout of the default configuration looks like:

Macushla:MiniProjects z0ltan$ cd guessing_game/
Macushla:guessing_game z0ltan$ tree .
.
├── dub.json
└── source
    ├── app.d

1 directory, 2 files

The dub.json file contains the basic configuration metadata for the project, and is for consumption by dub. Its initial contents are the data entered during the creation of the project.

A sample file, app.d is created inside the source directory. These can all be customised, of course.

Okay, so let’s create a new file to contain our guessing game code as a module.

Macushla:MiniProjects z0ltan$ touch source/guessing_game.d

All right, time to code up the game. Here are the contents of source/guessing_game.d

module guessing_game;

import std.stdio;

public void playGame() 
{
	import std.random: uniform;

	immutable uint secretNumber = uniform(1, 101);
	uint guesses = 0;

	writeln("\nLet's play a guessing game. Your task is to guess the secret number (between 1 and 100, inclusive)...");

	import std.conv: ConvException;

	while (true) {
		try {
			uint guess = getNumber("Enter your guess: ");

			++guesses;
			if (guess == secretNumber) {
				writefln("You win! You took %s guesses.", guesses);
				break;
			} else if (guess < secretNumber) {
				writeln("Too small!");
			} else {
				writeln("Too big!");
			}
		} catch (ConvException ex) {
			writeln("Did not get valid input. Try again...");
		}
	}
}


uint getNumber(string prompt) 
{
	writeln(prompt);

	import std.conv: to;
	import std.string: chomp;
		
	return readln().chomp.to!uint;
}

As you can see, this program is trivially readable for anyone who’s worked with C, C++, or indeed Java. The interesting bits to note would be the module system, as well as selective imports of module’s functions inside local lexical scopes.
Thankfully, D comes with a built-in module, std.random in its standard library (Phobos), and we can use the uniform function to generate our random number.

Another interesting bit to note is the following snippet of code:

return readln().chomp.to!uint;

The to! is a template function that is extremely powerful. It can be used to convert almost any type to any other type. In case the conversion fails though, this template function will throw a std.conv.ConvException exception. Note that D does not have checked exceptions (in Java-speak), only unchecked exceptions.

Also note the exception handling mechanism, which is extremely similar to that of Java.

Finally, observe the declaration of playGame as public. The helper function getNumber in source/guessing_game.d, by contrast is private, and not accessible outside the module in which it is defined.

Okay, so this is the guessing game logic. Now let’s take a look at our game’s entry point, source/app.d

import guessing_game;

void main()
{
	guessing_game.playGame();	
}

All we do is import the guessing_game module and then invoke playGame. Note that we could also have written this module like so:

import guessing_game: playGame;

void main() 
{
      playGame();
}     

Let’s try out the game!

Macushla:guessing_game z0ltan$ dub run
Performing "debug" build using dmd for x86_64.
guessing_game ~master: building configuration "application"...
Linking...
Running ./guessing_game 

Let's play a guessing game. Your task is to guess the secret number (between 1 and 100, inclusive)...
Enter your guess: 
50
Too small!
Enter your guess: 
hello
Did not get valid input. Try again...
Enter your guess: 
-1
Did not get valid input. Try again...
Enter your guess: 
75
Too small!
Enter your guess: 
88
Too big!
Enter your guess: 
81
Too big!
Enter your guess: 
78
You win! You took 5 guesses.
A simple guessing game in D

Goodbye Rust, and Hello, D!

After quite a bit of thought and consideration, I have decided to abandon my study of Rust, and move on to D.

I had been learning Rust for a while now, and I have become quite comfortable with it, but there are a few reasons that prompted me to move on to another systems language that would suit me better. Now while D is by no means perfect, I found the following advantages already:

  • A very consistent and intuitive (to me) core language. I have been learning it for only a couple of days now, and I’ve had quite a few “wow, it works exactly as I expected” moments already.
  • Very welcoming and helpful community that actually focuses on the technical side of things rather than getting sidetracked by social causes
  • A wide variety of compilers (DMD, GDC, LDC) targeted for both gcc and LLVM.
  • A stupendously fast compilation cycle. For small programs, I have found
    the compilation times to be on par with Go’s
  • A much saner syntax (in my very early estimation) that actually is quite readable (Rust’s syntax is not quite so readable for anything less-than-trivial in my opinion), and finally
  • Arrays (arguably the most important data structure) are actually sane, consistent, and very much logically intuitive in D unlike the mess that’s C (and C++).
  • Extremely powerful metaprogramming capabilities (an area I am particularly interested in)
  • A much much safer language than C++ while being much more programmer-friendly than Rust. Rust in that sense offloads the whole mental load of memory management onto the developer (and not in a crazy fun way like C or C++).

My use-cases for a systems programming language are quite simple, really – I don’t intend to do OS-level development (at least not in the foreseeable future), and so the GC dependency of D does not affect me in that sense. My research as well as my interactions with the wonderful folks over at forum.dlang.org have convinced me though that even with the GC, performance is still topnotch for a wide variety of systems-level programming.

As part of my learning process (just two days in to be exact), I thought of implementing two programs just to test out the waters before I dived in, and both of them were implemented with much less hassle (infinitely so to be honest), and they just worked beautifully the first time!

Insertion Sort

This is a barebones implementation of Insertion Sort in D:

// insertion_sort.d
import std.stdio;

void insertionSort(int[] arr) {
    foreach(i; 1..arr.length) {
        int key = arr[i];
        int j = cast(int)i-1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

void main() {
    int[] array = [100,-199,0,20,2,3,4,5,0,0,1,200];
    
    writefln("Before sorting: %s", array);
    
    insertionSort(array);
    
    writefln("After sorting: %s", array);
}

And here’s a test run:

sh-4.3$ dmd -run insertion_sort.d                                                                                                                                                   
Before sorting: [100, -199, 0, 20, 2, 3, 4, 5, 0, 0, 1, 200]                                                                                                              
After sorting: [-199, 0, 0, 0, 1, 2, 3, 4, 5, 20, 100, 200]  

Simple, and elegant! In fact, this code is directly readable to and understandable by anyone who has even the least bit of familiarity with C, C++, Java, or any member of the extended ALGOL family!

A line number closure

For my second program, I wanted to try out the line number closure (courtesy Hoyte) in D. As it turns out, either D is very logically designed, or my mind is quite attuned to D (or perhaps both!). It was quite pleasurable to be honest. Of course, at this stage, I have no idea if the code is idiomatic D or not. Anyway, let’s have some fun!

// line_closure.d
import std.stdio;

void delegate() getLineClosure() {
    int lineNum = 0;
    
    void printLineNumber() {
        lineNum++;
        
        writefln("Current line: %s", lineNum);
    }
    
    return &printLineNumber;
}

void main() {
    void delegate() x = getLineClosure();
    
    foreach(i; 0..5) {
        x();
    }
    writeln();
    
    void delegate() y = getLineClosure();
    
    foreach(j; 0..3) {
        y();
    }
}

and let’s take it for a spin:

sh-4.3$ dmd -run line_closure.d                                                                                                                                           
Current line: 1                                                                                                                                                           
Current line: 2                                                                                                                                                           
Current line: 3                                                                                                                                                           
Current line: 4                                                                                                                                                           
Current line: 5                                                                                                                                                           
                                                                                                                                                                          
Current line: 1                                                                                                                                                           
Current line: 2                                                                                                                                                           
Current line: 3    

Beautiful! The code probably deserves a bit of explanation – in D, functions are (as far as I can tell), first-class objects, and we can nest functions inside almost any scope. However, a function that is nested within a function or block scope is given a special name – a delegate. So the return type of the getLineClosure function:

void delegate()

indicates that we are returning a delegate which takes no parameters and returns nothing. Also note that we explicitly return the address of the delegate unlike in C, where the name of the function itself is the function pointer.

For this example to work, the delegate has to be able to capture the local variable, lineNum of course, and so delegates in D essentially function as closures in other Functional Programming languages. Also note the clean syntax of foreach for looping (C style loops are also supported, of course).

In conclusion, one major difference that I observed between Rust and D (I’m much more familiar with Rust, of course) is that I can more fully focus on the problem itself with D whereas with Rust, I have to always be aware of (and worrying about) what I am doing with the bindings/variables in my program, and I don’t think it’s altogether a question of getting familiar and comfortable with that. The ownership and borrowing concepts of Rust are, in and of themselves, trivial. However, the entire onus of managing proper memory behaviour is entirely on the developer. I wonder how much that would actually scale in real life. I suppose we’ll know the answer when people start developing large industry-standard (as much as I despise that term) in Rust.

Goodbye Rust, and Hello, D!