A Rational number class in Ruby

As is my custom when learning a new language, I implement a basic custom Rational class in Ruby:

# implementation of a Rational number class in Ruby

module MyRational
    class Rational
        attr_reader :numerator, :denominator

        def initialize(num, denom = 1)
            if denom == 0
                raise "Denominator cannot be 0 for a rational number"
            end
            
            @numerator = num
            @denominator = denom

            normalize
        end

        
        # += etc all come for free when the basic operator is overloaded!
        def +(other)
            @numerator = @numerator * other.denominator + @denominator * other.numerator
            @denominator = @denominator * other.denominator

            normalize
            self
        end
        

        def -(other)
            @numerator = @numerator * other.denominator - @denominator * other.numerator
            @denominator = @denominator * other.denominator

            normalize
            self
        end

        
        def *(other)
            @numerator = @numerator * other.numerator
            @denominator = @denominator * other.denominator

            normalize
            self
        end

        
        def /(other)
            @numerator = @numerator * other.denominator
            @denominator = @denominator * other.numerator

            normalize
            self
        end


        def to_s
            if @denominator == 1
                @numerator.to_s
            else
                @numerator.to_s + "/" + @denominator.to_s
            end
        end

        
        # generics class methods
        def self.+(f, s)
            n = f.numerator * s.denominator + f.denominator * s.numerator
            d = f.denominator * s.denominator
            
            Rational.new(n, d)
        end

        def self.-(f, s)
            n = f.numerator * s.denominator - f.denominator * s.numerator
            d = f.denominator * s.denominator
            
            Rational.new(n, d)
        end


        def self.*(f, s)
            n = f.numerator * s.numerator
            d = f.denominator * s.denominator
            
            Rational.new(n, d)
        end


        def self./(f, s)
            n = f.numerator * s.denominator
            d = f.denominator * s.numerator
            
            Rational.new(n, d)
        end


        private

        def gcd(x, y)
            if y == 0
                x
            else
                gcd(y, x%y)
            end
        end

        
        def normalize()
            g = gcd(@numerator, @denominator)

            @numerator /= g
            @denominator /= g
        end
    end
end

Taking it for a test spin:

irb(main):003:0> load "my_rational.rb"
load "my_rational.rb"
=> true
irb(main):004:0> x = MyRational::Rational.new(1,2)
x = MyRational::Rational.new(1,2)
=> #<MyRational::Rational:0x007fd02a09bc88 @numerator=1, @denominator=2>
irb(main):005:0> y = MyRational::Rational.new(3,4)
y = MyRational::Rational.new(3,4)
=> #<MyRational::Rational:0x007fd02a0a21a0 @numerator=3, @denominator=4>
irb(main):006:0> x += y
x += y
=> #<MyRational::Rational:0x007fd02a09bc88 @numerator=5, @denominator=4>
irb(main):007:0> puts x
puts x
5/4
=> nil
irb(main):008:0> x -= y
x -= y
=> #<MyRational::Rational:0x007fd02a09bc88 @numerator=1, @denominator=2>
irb(main):009:0> puts x
puts x
1/2
=> nil
irb(main):010:0> x *= y
x *= y
=> #<MyRational::Rational:0x007fd02a09bc88 @numerator=3, @denominator=8>
irb(main):011:0> puts x
puts x
3/8
=> nil
irb(main):012:0> x /= y
x /= y
=> #<MyRational::Rational:0x007fd02a09bc88 @numerator=1, @denominator=2>
irb(main):013:0> puts x
puts x
1/2
=> nil
irb(main):014:0> MyRational::Rational.+(x, y)
MyRational::Rational.+(x, y)
=> #<MyRational::Rational:0x007fd02a0bad90 @numerator=5, @denominator=4>
irb(main):015:0> puts MyRational::Rational.+(x, y)
puts MyRational::Rational.+(x, y)
5/4
=> nil
irb(main):016:0> puts MyRational::Rational.-(x, y)
puts MyRational::Rational.-(x, y)
-1/4
=> nil
irb(main):017:0> puts MyRational::Rational.*(x, y)
puts MyRational::Rational.*(x, y)
3/8
=> nil
irb(main):018:0> puts MyRational::Rational./(x, y)
puts MyRational::Rational./(x, y)
2/3
=> nil

Of course, operations like number op rational, rational op number, where “op” is an operation will not work. These could be added by extending the number classes, etc, and also adding support in the class methods, but perhaps there is a better way that I will learn when I improve my Ruby knowledge! For now, the more I use Ruby, the more I like it!

A Rational number class in Ruby

Hoyte’s Line Number closure in a few choice languages

Douglas Hoyte, in his excellent (if a bit fanatical) book, “Let over Lambda” gives a simple and pithy example to demonstrate the concept of closures – little anonymous functions that can capture variables in the environment in which the closure was created.

The example is very simple – create a mini-logging facility by capturing a variable representing the current line number (initially set to 0), incrementing it for every invocation of the closure, and printing it out.

An implementation in Common Lisp might look so –

(defun get-line-logger ()
  (let ((line-num 0))
    #'(lambda (id)
        (incf line-num)
        (format t "[~a] Line number: ~d~%" id line-num))))


(defun logger-demo ()
  (let ((logger-1 (get-line-logger))
        (logger-2 (get-line-logger)))
    (flet ((f (id logger)
             (dotimes (i 5)
               (funcall logger id))
             (terpri)))
      (f "logger-1" logger-1)
      (f "logger-2" logger-2))))

Sample run:

CL-USER> (logger-demo)
[logger-1] Line number: 1
[logger-1] Line number: 2
[logger-1] Line number: 3
[logger-1] Line number: 4
[logger-1] Line number: 5

[logger-2] Line number: 1
[logger-2] Line number: 2
[logger-2] Line number: 3
[logger-2] Line number: 4
[logger-2] Line number: 5

NIL

As expected, we can not only capture local variables in the lexical environment during the time of the closure’s creation, but also modify them independently of any other instances of the closure. This is what makes is a proper closure. Also note that the capture is automatically done (whether we actually use the variables or not is irrelevant).

The Racket version is, unsurprisingly, almost identical not only in syntax, but also semantics:

#lang racket

(define (get-line-logger)
  (let ([line-no 0])
    (lambda (id)
      (set! line-no (+ 1 line-no))
      (fprintf (current-output-port)"[~a] Line number: ~a~%" id line-no))))

(define (logger-demo)
  (let ([logger-1 (get-line-logger)]
        [logger-2 (get-line-logger)])
    (letrec ([f (lambda (id logger)
                  (do
                      ((i 0 (+ i 1)))
                      ((= i 5))
                    (logger id))
                  (newline))])
      (f "logger1" logger-1)
      (f "logger2" logger-2))))

And the behaviour is exactly the same:

hoyte-closure.rkt> (logger-demo)
[logger1] Line number: 1
[logger1] Line number: 2
[logger1] Line number: 3
[logger1] Line number: 4
[logger1] Line number: 5

[logger2] Line number: 1
[logger2] Line number: 2
[logger2] Line number: 3
[logger2] Line number: 4
[logger2] Line number: 5

Racket is, in some ways, more elegant than even Common Lisp. I especially love the part where lambdas don’t need any funcallS or applyS to make them run (unlike in Common Lisp). Still, pretty much a branch off the same family tree.

Moving on, let’s try the same in Java, shall we?

import java.util.function.Function;

public class HoyteClosure {
    private static Function<String, Void> getLineLogger() {
        int lineNum = 0;

        return (String id) -> { lineNum++; System.out.printf("[%s] Line number: %d\n",
                                                                 id, lineNum); return null; };
    }

    private static void invokeLogger(String id, Function<String, Void> logger) {
        for (int i = 0; i < 5; i++) {
            logger.apply(id);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Function<String, Void> logger1 = getLineLogger();
        Function<String, Void> logger2 = getLineLogger();

        invokeLogger("logger1", logger1);
        invokeLogger("logger2", logger2);
    }
}

Okay, looks good. However, if we try to run it, we run into issues immediately:

Timmys-MacBook-Pro:Java8 z0ltan$ javac HoyteClosure.java 
Timmys-MacBook-Pro:Java8 z0ltan$ javac HoyteClosure.java 
HoyteClosure.java:7: error: local variables referenced from a lambda expression must be final or effectively final
        return (String id) -> { lineNum++; System.out.printf("[%s] Line number: %d\n",
                                ^
HoyteClosure.java:8: error: local variables referenced from a lambda expression must be final or effectively final
                                                                 id, lineNum); return null; };
                                                                     ^
2 errors

The problem is that Java really does not have real closures. The lambda support in Java 8 is just syntactic sugar for the good old anonymous class which can read local variables in the environment, but cannot modify them. So what can we do?

To make Java happy, we can create a new object for every logger instance i.e., use instance variables in lieu of local variables so that the modification of local variables is not an issue any more:

import java.util.function.Function;

public class HoyteClosureModified {
    static class Closure {
        private int lineNum;
        
        private  Function<String, Void> getLineLogger() {
            return (String id) -> { lineNum++; System.out.printf("[%s] Line number: %d\n",
                                                                 id, lineNum); return null; };
        }
    }

    private static void invokeLogger(String id, Function<String, Void> logger) {
        for (int i = 0; i < 5; i++) {
            logger.apply(id);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Function<String, Void> logger1 = new Closure().getLineLogger();
        Function<String, Void> logger2 = new Closure().getLineLogger();

        invokeLogger("logger1", logger1);
        invokeLogger("logger2", logger2);
    }
}

Taking it for a test spin, we get:

Timmys-MacBook-Pro:Java8 z0ltan$ javac HoyteClosureModified.java
Timmys-MacBook-Pro:Java8 z0ltan$ java -cp . HoyteClosureModified
[logger1] Line number: 1
[logger1] Line number: 2
[logger1] Line number: 3
[logger1] Line number: 4
[logger1] Line number: 5

[logger2] Line number: 1
[logger2] Line number: 2
[logger2] Line number: 3
[logger2] Line number: 4
[logger2] Line number: 5

It’s not the same though, is it? The whole point of using a closure was so that we wouldn’t have to do this explicit management of state ourselves. As such, Java doesn’t really have full-blown closures, just a poor man’
s version of it. Better luck next time, Java.

Finally, the same using Ruby. As I have said before, Ruby feels remarkably like a Lisp despite the syntactic differences.

module HoyteClosure 
    class Demo
        def self.get_line_logger
            line_no = 0

            lambda do |id|
                line_no += 1
                puts "[" + id + "] Line number: " + line_no.to_s
            end
        end

        def self.logger_demo(id, logger)
            5.times {
                logger.call(id)
            }
            puts ""
        end

        def self.main
            logger1 = get_line_logger
            logger2 = get_line_logger

            logger_demo("logger1", logger1)
            logger_demo("logger2", logger2)
        end
    end
end

And the final test run:

irb(main):009:0> load "./hoyte_closure.rb"
load "./hoyte_closure.rb"
=> true
irb(main):010:0> HoyteClosure::Demo.main
HoyteClosure::Demo.main
[logger1] Line number: 1
[logger1] Line number: 2
[logger1] Line number: 3
[logger1] Line number: 4
[logger1] Line number: 5

[logger2] Line number: 1
[logger2] Line number: 2
[logger2] Line number: 3
[logger2] Line number: 4
[logger2] Line number: 5

=> nil

Short, non-idiomatic, and sweet!

Hoyte’s Line Number closure in a few choice languages

Solutions to Chapter 2 exercises, ANSI Common Lisp (2nd Edition)

Problem 1

;; (+ (- 5 1) (+ 3 7)) => (+ 4 (+ 3 7)) => (+ 4 10) => 14

;; (list 1 (+ 2 3)) => (list 1 5) => (1 5)

;; (if (listp 1) (+ 1 2) (+ 3 4)) => (if nil (+ 1 2) (+ 3 4)) => (+ 3 4) => 7

;; (list (and (listp 3) t) (+ 1 2)) => (list (and nil t) (+ 1 2)) => (list nil (+ 1 2))
;; => (list nil 3) => (nil 3)

Problem 2

;; Expression 1

(cons 'a (cons 'b (cons 'c nil)))

;; Expression 2

(cons 'a '(b c))

;; Expression 3

(cons 'a (cons 'b '(c)))

Problem 3

(defun my-fourth (lst)
  (car (cdr (cdr (cdr lst)))))

(defun my-fourth% (lst)
  (cadddr lst))

Problem 4

(defun greater-of-two (x y)
  (if (> x y)
      x
      y))

Problem 5

;; enigma checks if a non-empty list contains at least one ‘nil’ element.

;; mystery returns the zero-based index of the first parameter in the second parameter (which is a
;; list) otherwise nil.

Problem 6

;; car
;; or
;; apply (funcall would return (1 nil))

Problem 7

(defun any-element-is-list (lst)
  (if (null lst)
      nil
      (or (listp (car lst)) (any-element-is-list (cdr lst)))))

(defun any-element-is-list% (lst)
  (let ((res nil))
    (dolist (obj lst)
      (setf res (or res (listp obj))))
    res))

Problem 8

(defun print-dots-recursive (n)
  (if (= n 0)
      (format t "~%")
      (progn
        (format t ".")
        (print-dots-recursive (- n 1)))))

(defun print-dots-iterative (n)
  (do
   ((i 0 (+ i 1)))
   ((= i n) (format t "~%"))
    (format t ".")))


(defun count-a-recursive (lst)
  (if (null lst)
      0
      (if (eql 'a (car lst))
          (+ 1 (count-a (cdr lst)))
          (count-a (cdr lst)))))

(defun count-a-iterative (lst)
  (let ((count 0))
    (dolist (obj lst)
      (if (eql 'a obj)
          (setf count (+ 1 count))))
    count))

Problem 9

;; The problem with the iterative summit is that the “remove” function returns a new list with
;; the specified element removed, but does not touch the original list (no side-effects).

(defun summit (lst)
  (setf lst (remove nil lst))
  (apply #'+ lst))

;; The problem with the recursive version of summit is that there is no stopping condition! This
;; means that summit keeps looping forever even after the list has become empty.

(defun summit (lst)
  (if (null lst)
      0
      (let ((x (car lst)))
        (if (null x)
            (summit (cdr lst))
            (+ x (summit (cdr lst)))))))

;; cleaner version

(defun summit (lst)
  (if (null lst)
      0
      (if (null (car lst))
          (summit (cdr lst))
          (+ (car lst) (summit (cdr lst))))))
Solutions to Chapter 2 exercises, ANSI Common Lisp (2nd Edition)

Implementing a Rational type in Rust

Following my tradition of writing a rational number class/struct/type in a new programming language, I will develop a very basic module for rationals in Rust in this brief post.

First off, let’s create a new project to store our rational number type in.

Project setup

We create the project using the canonical way – using Cargo. Since we’re interested in building a library, we don’t pass in the --bin flag.

In case you are not familiar with Cargo, all you need to know is that it is the de facto build and dependency management tool for Rust projects. In terms of dependency management in particular, we specify the dependencies inside the Cargo.toml file, and Cargo takes care of downloading the library (and its dependencies, and their dependencies, and so on), builds them, and caches the libraries for future use by other projects (usually inside $HOME/.cargo).

Timmys-MacBook-Pro:Rust z0ltan$ cargo new rationals
     Created library `rationals` project
Timmys-MacBook-Pro:Rust z0ltan$ cd rationals

The following files and directories must have been automatically created for you:

Timmys-MacBook-Pro:rationals z0ltan$ tree
.
├── Cargo.toml
└── src
    └── lib.rs

1 directory, 2 files

So far so good! Now, since we would need to test the functionality, let’s create a test folder, and create a tests.rs file in that folder.

Timmys-MacBook-Pro:rationals z0ltan$ mkdir tests
Timmys-MacBook-Pro:rationals z0ltan$ touch tests/tests.rs
Timmys-MacBook-Pro:rationals z0ltan$ tree
.
├── Cargo.toml
├── src
│   └── lib.rs
└── tests
    └── tests.rs

2 directories, 3 files

Excellent! Now let’s get on to the code.

The Code

Top

Since the code itself is not very large, I thought it best to present the code in its entirety first, and then go about explaining the pertinent portions that do need explaining.

Insert the following code into src/lib.rs.

use std::fmt;
use std::ops::{ Add, Sub, Mul, Div };
use std::cmp::{ PartialEq, Eq };


#[derive(Clone, Copy, Debug)]
pub struct Rational {
	x: i32,
	y: i32,
}

impl Rational {
	fn gcd(x: i32, y: i32) -> i32 {
		if y == 0 {
			x
		} else {
			Rational::gcd(y, x%y)
		}
	}
	
	pub fn new(x: i32, y: i32) -> Rational {
		assert!(y != 0);

		let g = Rational::gcd(i32::abs(x), i32::abs(y));

		Rational {
			x: x/g,
			y: y/g,
		}
	}
}


impl fmt::Display for Rational {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
		if self.y == 1 {
			write!(f, "{}", self.x)
		} else {
			write!(f, "{}/{}", self.x, self.y)
		}
	}
}

// to allow equality checks
impl PartialEq for Rational {
	fn eq(&self, other: &Rational) -> bool {
		(self.x == other.x) && (self.y == other.y)
	}
}

impl Eq for Rational {}


// All the add traits
impl Add for Rational {
	type Output = Rational;

	fn add(self, other: Rational) -> Rational {
		Rational::new(self.x * other.y + self.y * other.x, self.y * other.y)
	}
}

impl Add<i32> for Rational {
	type Output = Rational;

	fn add(self, other: i32) -> Rational {
		Rational::add(self, Rational::new(other, 1))
	}
}

impl Add<Rational> for i32 {
	type Output = Rational;

	fn add(self, other: Rational) -> Rational {
		Rational::add(Rational::new(self, 1), other)
	}
}

// All the sub traits
impl Sub for Rational {
	type Output = Rational;

	fn sub(self, other: Rational) -> Rational {
		Rational::new(self.x * other.y - self.y * other.x, self.y * other.y)
	}
}

impl Sub<i32> for Rational {
	type Output = Rational;

	fn sub(self, other: i32) -> Rational {
		Rational::sub(self, Rational::new(other, 1))
	}

}

impl Sub<Rational> for i32 {
	type Output = Rational;

	fn sub(self, other: Rational) -> Rational {
		Rational::sub(Rational::new(self, 1), other)
	}
}

// All the mul traits
impl Mul for Rational {
	type Output = Rational;

	fn mul(self, other: Rational) -> Rational {
		Rational::new(self.x * other.x, self.y * other.y)
	}
}

impl Mul<i32> for Rational {
	type Output = Rational;

	fn mul(self, other: i32) -> Rational {
		Rational::mul(self, Rational::new(other, 1))
	}
}

impl Mul<Rational> for i32 {
	type Output = Rational;

	fn mul(self, other: Rational) -> Rational {
		Rational::mul(Rational::new(self, 1), other)
	}
}


// All the div traits
impl Div for Rational {
	type Output = Rational;

	fn div(self, other: Rational) -> Rational {
		Rational::new(self.x * other.y, self.y * other.x)
	}
}

impl Div<i32> for Rational {
	type Output = Rational;

	fn div(self, other: i32) -> Rational {
		Rational::div(self, Rational::new(other, 1))
	}
}

impl Div<Rational> for i32 {
	type Output = Rational;

	fn div(self, other: Rational) -> Rational {
		Rational::div(Rational::new(self, 1), other)
	}
}

Explanatory notes: Top

The code is, as usual, straightforward. We define a struct (Rust does not have the concept of classes, but structS cover the basic use-cases of a class) called Rational to define our new type.

We then “implement” various traits (loosely speaking, similar to Java’s interfaces, but much more powerful) that add on features for our new type. The #[derive(Clone, Copy, Debug)] bit is called an “attribute” (again, loosely speaking, similar to Java’s annotations). This tells the Rust compiler that we wish this new data type to be cloneable, copyable, and well, debuggable (which means that the compiler will figure out a default way of displaying a Rational object).

We first implement the main functionality for the Rational type itself (impl Rational {), and provide a default constructor called new. We also define a private (which is the default mode, unless override by the pub keyword) function, gcd, which is used to reduce a Rational number to its normalised form. For instance, 2/6 is represented as 1/3 internally.

We then implement the Display trait (impl fmt::Display for Rational {). This is simply to allow us to print the Rational number in a custom way.

Now comes an interesting bit – in order to allow our custom type to be comparable (say, using the == operator), we need to implement the Eq trait. In Rust, however, this trait does nothing other than to define implementing the PartialEq trait, which specifies partial equality. The details are not important for this example though, and implementing PartialEq works fine for this demo.

Finally, we need to fill out the actual logic of various operations on rational numbers: addition, subtraction, multiplication, and division are covered here. The problem though is this – there are three basic combinations that come within this context:

  • Operations between two Rational numbers
  • Operations between a Rational number and an integer, and
  • Operations between an integer and a Rational number

A further complication arises in Rust specifically due to the fact that Rust is very very particular about the type of each variable/value. For example, even though the following types all represent signed integers – i8, i16, i32, i64, they are not interchangeable. Couple this with the fact that we don’t really have a common type or trait like Integer to cover all these types (yet another irksome quirk of Rust), covering all possible combinations of Rational number interoperation with integers would be a combinatory explosion!

To keep things sane, I have restricted usage to the default integer type – signed32-bit integers (i32).

As such, we have three different categories (as discussed above) of traits being implemented in this sections to cover all the use-cases:

  • Operations between two Rational numbers: This is handled by the following trait implementations –
    impl Add for Rational { 

    ,

    impl Sub for Rational { 

    ,

    impl Mul for Rational { 

    , and

    impl Div for Rational { 
  • Operations between a Rational number and an i32: This scenario is handle by the following implS –
    impl Add<i32> for Rational { 

    ,

    impl Sub<i32> for Rational { 

    ,

    impl Mul<i32> for Rational { 

    , and

    impl Div<i32> for Rational { 

    . As you can see, the operator overloading traits are generic to a great extent.

  • Operations between an i32 and a Rational number: This final use-case is covered by the following implS –
    impl Add<Rational> for i32 { 

    ,

    impl Sub<Rational> for i32 { 

    ,

    impl Mul<Rational> for i32 { 

    , and

    impl Div<Rational> for i32 { 

    .

    The interesting thing to note here is that we can implement traits even for built-in types like i32‘s! However, of course, this extra functionality is restricted to our rationals crate and its clients. It would be a nightmare if these changes were visible throughout the codebase!

  • You might have already realised it by now, based on the above, that Rust supports operator overloading. Just like Kotlin, however, it severely restricts the operators that you can overload, and the mechanism for overloading an operator is by implementing the corresponding trait(s) that represents that functionality (Talk about nice consistency!). I feel that this strikes a nice balance between the approach taken by C++ (where you can basically overload whatever you want, wherever you want), and that taken by Java (no operator overloading at all!). For anyone shaking his head at the latter, I dare you to try using the java.math.BigInteger class in any non-trivial program without getting severe depression!

    Note that the standard operator overloading traits are defined in the std::ops module of the standard Rust library.

    So there you go, the actual logic involved in this example is so trivial that I am skipping it altogether. What’s more interesting is the way in which it can be implemented in Rust.

    Now, let’s give it a spin, and assure ourselves that all is well with our implementation!

    Demo

    Top

    The following test code goes inside tests/tests.rs. One of the beauties of Cargo is that it can pick up all tests in any arbitrary path inside the Cargo project.

    extern crate rationals;
    
    
    #[cfg(test)]
    mod rationals_tests {
    	use rationals::Rational;
    
    
    	// Rationals with Rationals
    
    	#[test]
    	pub fn add_two_rationals() {
    		let r1 = Rational::new(1, 3);
    		let r2 = Rational::new(2, 6);
    
    		assert_eq!(Rational::new(2, 3), r1+r2);	
    	}
    
    	#[test]
    	pub fn sub_two_rationals() {
    		let r1 = Rational::new(1, 3);
    		let r2 = Rational::new(2, 6);
    
    		assert_eq!(Rational::new(0, 1), r1-r2);
    	}
    
    	#[test]
    	pub fn mul_two_rationals() {
    		let r1 = Rational::new(1, 3);
    		let r2 = Rational::new(2, 6);
    
    		assert_eq!(Rational::new(1, 9), r1*r2);
    	}
    
    	#[test]
    	pub fn div_two_rationals() {
    		let r1 = Rational::new(1, 3);
    		let r2 = Rational::new(2, 6);
    
    		assert_eq!(Rational::new(1, 1), r1/r2);
    	}
    
    
    	// Rationals with i32
    
    	#[test]
    	pub fn add_i32_to_rational() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(7, 3), r1+num);
    	}
    
    	#[test]
    	pub fn sub_i32_from_rational() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(-5, 3), r1-num);
    	}
    
    	#[test]
    	pub fn mul_rational_with_i32() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(2, 3), r1*num);
    	}
    
    	#[test]
    	pub fn div_rational_by_i32() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(1, 6), r1/num);
    	}
    
    
    	// i23 with Rationals
    
    	#[test]
    	pub fn add_rational_to_i32() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(7, 3), num+r1);
    	}
    
    	#[test]
    	pub fn sub_rational_from_i32() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(5, 3), num-r1);
    	}
    
    	#[test]
    	pub fn mul_i32_with_rational() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(2, 3), num*r1);
    	}
    
    	#[test]
    	pub fn div_i32_by_rational() {
    		let r1 = Rational::new(1, 3);
    		let num = 2i32;
    
    		assert_eq!(Rational::new(6, 1), num/r1);
    	}
    }
    

    As you can see, we have defined a new module, rational_tests to hold our tests, and also declared the rationals crate as an external dependency (even if it’s within the same project in this case, it’s conceptually separated from out current test crate).

    We bring in that dependency using extern crate rationals;

    Let’s give it a go!

    Timmys-MacBook-Pro:rationals z0ltan$ cargo test
       Compiling rationals v0.1.0 (file:///Users/z0ltan/Rabota/Projects/Rust/rationals)
        Finished debug [unoptimized + debuginfo] target(s) in 0.33 secs
         Running target/debug/deps/rationals-0e91f0c33cf32122
    
    running 0 tests
    
    test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured
    
         Running target/debug/tests-9da87246cfd0777c
    
    running 12 tests
    test rationals_tests::add_two_rationals ... ok
    test rationals_tests::div_two_rationals ... ok
    test rationals_tests::mul_i32_with_rational ... ok
    test rationals_tests::div_i32_by_rational ... ok
    test rationals_tests::div_rational_by_i32 ... ok
    test rationals_tests::mul_rational_with_i32 ... ok
    test rationals_tests::add_i32_to_rational ... ok
    test rationals_tests::add_rational_to_i32 ... ok
    test rationals_tests::mul_two_rationals ... ok
    test rationals_tests::sub_i32_from_rational ... ok
    test rationals_tests::sub_rational_from_i32 ... ok
    test rationals_tests::sub_two_rationals ... ok
    
    test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured
    
       Doc-tests rationals
    
    running 0 tests
    
    test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured
    

    Wonderful!

    Closing comments

    Top

    Rust so far has been a pleasure to work with. It has its own quirks – no function overloading, a very convoluted way of doing basic I/O, and very strict borrow semantics (even in some cases where it is absolutely safe, the borrow checker will not allow uses), but overall, it is very well designed indeed.

    Prior to Rust, I had tinkered a bit with Nim, and I absolutely loved that language, but unfortunately, the language became more complicated and less consistent as soon as one began attempting to use it in real-world scenarios. I don’t see the same dissonance in Rust (so far). Yes, Rust is definitely much more verbose than Nim, but for the most part, despite its strengths as a Systems-level language, Rust feels like a very high-level language indeed that has a very strong and consistent overarching architecture.

    What I love about Rust thus far – traits (I can’t believe how useful they really are!), its quirky error handling (very Go-esque at first glance, but much more powerful in my opinion. Also, most mainstream imperative languages are moving towards Functional style error handling –

    Optional<T>

    in Java, for instance), its speed (sans garbage collection!), wonderful thread support (how I wish thread interruption was built into the Thread type itself, though), operator overloading (albeit limited), its extremely powerful pattern matching (every language needs this, especially Common Lisp!), and of course, the safety guarantees.

    I’m sure I’ll be using Rust a lot more in the near future, and not just for tooling purposes.

Implementing a Rational type in Rust

Implementing Insertion sort in Rust (and it kinda sucked)

So I’m still learning Rust, and I decided to implement a naive version of the Insertion Sort algorithm as laid out in CLRS. I didn’t realise that it was going to be a bit of an exercise in frustration. Well, first let’s take a look at the code, and then do some analysis on it.

Here’s the C++ version:

#include <iostream>

using namespace std;

void insertion_sort(int arr[], int n)
{
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int j = i-1;

		while (j >= 0 && (arr[j] > key)) {
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}
}

int main()
{
	int arr[] = { 10, -20, 1, 2, 6, 7, 99, 100, 0, 100 };

	insertion_sort(arr, 10);

	for (int& i : arr) {
		cout << i << " ";
	}

	cout << endl;

	return 0;
}

Take it for a spin:

Timmys-MacBook-Pro:my_sort z0ltan$ g++ -Wall -o insertion_sort insertion_sort.cpp -std=c++11
Timmys-MacBook-Pro:my_sort z0ltan$ time ./insertion_sort 
-20 0 1 2 6 7 10 99 100 100 

real	0m0.005s
user	0m0.001s
sys	0m0.003s

Nice! And here’s the Rust version:

pub fn insertion_sort(arr: &mut Vec<i32>) {
	for i in 1..arr.len() {
		
		let key = arr[i];
		let mut t:i32 = (i-1) as i32;
		let mut j = i-1;

		while arr[j] > key {
			arr[j+1] = arr[j];
			
			if t < 0 {
				break;
			}

			if j != 0 {
				j = j-1;
			}

			t = t-1;
		}

		j = (t+1) as usize;
		arr[j] = key;
	}
}


pub fn main() {
	let mut numbers = vec!(10, -20, 1, 2, 6, 7, 99, 100, 0, 100);

	insertion_sort(&mut numbers);

	for num in numbers {
		print!("{} ", num);
	}

	println!("");
}

And here’s the output from a test run:

Timmys-MacBook-Pro:src z0ltan$ rustc insertion_sort.rs
Timmys-MacBook-Pro:src z0ltan$ time ./insertion_sort
-20 0 1 2 6 7 10 99 100 100 

real	0m0.005s
user	0m0.002s
sys	0m0.002s

Great. Now compare the code in the sorting function in C++ and in Rust. The reason why the Rust version is so much more verbose (and filled with ugly casting and checks inside the while loop) is because of the type-safety that Rust provides.

Indexing in C++ and in Java is done using intS, even unsigned ones, and the compilers don’t really enforce any checks on that. So the same code (as in the C++ version) would work fine in Java as well.

In Rust, however, indexing is done using a “unsigned integer pointer size” type called usize. This means that we can’t do something like

   j -= 1;

inside the while loop in the Rust version. My issue is this – the compiler enforces nothing during compile time (aside from warning that a check like j >= 0 would be redundant), and it fails at runtime (as expected). Well, that explains the horrible hack of creating another mutable local variable, t to actually check when j goes 1 below 0 (as is required by this algorithm).

So far, I can’t say that I am overly impressed by Rust. I have seen the compiler miss a lot of clear checks that it could have done. For instance:

x == 1;

when I intended to do

x -= 1;

It shouldn’t be an error, but clearly there can be a warning since it’s basically doing nothing, being a statement than an expression. This may seem like picking at straws, but I wonder if Rust’s safety guarantees aren’t as valuable as the overheads of dealing with the Borrow Checker, and having to massively refactor the code, when business logic changes, to satisfy the Borrow Checker.

So far, what I’ve liked best about Rust is how easy it is to interact with C. C++ support is still far off since Rust does not really have the concept of a class (structS come close), and also name-mangling, but the basic use cases are extremely well-covered and well-designed.

I intend to so some small projects in Rust. Perhaps I will have a better idea of the actual ROI of Rust.

 

Implementing Insertion sort in Rust (and it kinda sucked)

Calling native code from Rust – a very simple example!

I have been playing around with Rust for a bit, and so far so good! I think that people make a bit too much of the whole complexity of the Ownership, Borrowing, and Lifetimes concepts. However, I did find the documentation (in the Rust Book, as also in Rust By Example) on Lifetimes to be not only very sparse, but more confusing than helpful. That part could certainly do with some work.

Niko Matsakis has started a small site to help explain some core concepts which I found to be interesting, useful, and fun! You can find them here:Into Rust. It is still a work in progress, and hopefully they will add many more videos – especially on Lifetimes, Unsafe, and I/O (which is a a bit of a bugbear for me right now).

In any case, for this short tutorial, I will attempt to demonstrate how your custom C++ library may be invoked from Rust. Well, let’s get on with it!

Setting up the native library

Just to make things interesting, let us have a native library that takes in a vector of numbers, sorts them in non-increasing order, and returns them to the caller.

Let’s define the C++ functionality in a file called sorting.cpp, with the declaration in the header file sorting.h:

#ifndef __SORTING_H__
#define __SORTING_H__ "sorting.h"

#include <iostream>
#include <functional>
#include <algorithm>

#ifdef __cplusplus
extern "C" {
#endif
  void interop_sort(int[], size_t);
#ifdef __cplusplus
}
#endif
#endif
#include "sorting.h"

void interop_sort(int numbers[], size_t size)
{
  int* start = &numbers[0];
  int* end = &numbers[0] + size;

  std::sort(start, end, [](int x, int y) {  return x > y; });
}

Let’s wrap this up in a nice static library called libmysorting.a (note that I am building this on a macOS system. Please consult your local OS’ documentation for details specific to your platform):

Timmys-MacBook-Pro:Rust_C_Interop z0ltan$ g++ -Wall -std=c++14 -c sorting.cpp
clang: warning: treating 'c' input as 'c++' when in C++ mode, this behavior is deprecated

Timmys-MacBook-Pro:Rust_C_Interop z0ltan$ ar rc libmysorting.a sorting.o
Timmys-MacBook-Pro:Rust_C_Interop z0ltan$ ls
libmysorting.a	sorting.cpp	sorting.h	sorting.o

And just to make sure that no name-mangling has occurred during the process:

Timmys-MacBook-Pro:Rust_C_Interop z0ltan$ nm -gU libmysorting.a 

libmysorting.a(sorting.o):
0000000000000000 T _interop_sort

Okay, looks like everything is in order. Now let’s move on to the Rust bit.

Calling the native library from Rust

To use the library from Rust, let’s create a new Cargo project called sorting_demo:

Timmys-MacBook-Pro:Rust_C_Interop z0ltan$ cargo new --bin sorting_demo
     Created binary (application) `sorting_demo` project

Timmys-MacBook-Pro:Rust_C_Interop z0ltan$ cd sorting_demo

Timmys-MacBook-Pro:sorting_demo z0ltan$ ls
Cargo.toml	src

Now we need to have a way to link the native library into our Rust project. For simplicity’s sake, let’s use the simplest approach:

Timmys-MacBook-Pro:sorting_demo z0ltan$ cp ../libmysorting.a .

Timmys-MacBook-Pro:sorting_demo z0ltan$ ls
Cargo.lock	Cargo.toml	libmysorting.a	src		target

All we did here is to copy libmysorting.a into the root of the Rust project, and set the LD_LIBRARY_PATH environment variable to ensure that the linker can find the library.

Now that that’s set up, let’s write up the logic to link the static library from Rust code. Put the following code inside src/main.rs

#[link(name = "mysorting")]
extern {
    fn interop_sort(arr: &[i32;10], n: u32);
}

pub fn sort_from_cpp(arr: &[i32;10], n: u32) {
    unsafe {
        interop_sort(arr, n);
    }
}

fn main() {
    let my_arr = [100, 200, -99, 34, 56, -656, 99, 94, 84, 89];

    println!("Before sorting...");
    println!("{:?}\n", my_arr);

    sort_from_cpp(&my_arr, 10);

    println!("After sorting...");
    println!("{:?}", my_arr);

}

All right. Now all that remains is to see if this whole setup actually works!

Test spin

Timmys-MacBook-Pro:sorting_demo z0ltan$ cargo run
   Compiling sorting_demo v0.1.0 (file:///Users/z0ltan/Rabota/Blogs/Rust_C_Interop/sorting_demo)
    Finished debug [unoptimized + debuginfo] target(s) in 0.29 secs
     Running `target/debug/sorting_demo`
Before sorting...
[100, 200, -99, 34, 56, -656, 99, 94, 84, 89]

After sorting...
[200, 100, 99, 94, 89, 84, 56, 34, -99, -656]

Nice! So it all works as expected. The array has been correctly sorted in non-increasing order.

Explanation: The code is pretty much self-explanatory. First up we link the static library using the #[link(name = "mysorting")] directive (similar to annotations in other languages). This allows Rust to seek out a library named libmysorting.a or libmysorting.dylib.

Then we simply define the equivalent C++ function, interop_sort along with matching Rust types for the signature (note how we can use an array slice, &[i32;10] to match up with the C array, int arr[10]. Likewise, the size of the array is an unsigned integer, so we declare that to be of type u32. The whole native function itself is wrapped up inside an extern block. There are various options for the extern, and it defaults to extern "C". This block keyword is used to signify foreign code in Rust.

Finally, it’s good practice to wrap up the unsafe function inside a safe Rust function which is what we did with the sort_from_cpp function.

And there you go! A bare minimum working example of calling C++ (or indeed C) code from Rust. A special note here: as we can see, we defined a C interface for the C++ code to avoid name-mangling. If this were not done so directly in the C++ code, we could still have defined a C wrapper (as we have done in other interop examples) and have a callback function from C to the C++ code. That would work as well.

Calling native code from Rust – a very simple example!

Interop mini-series – Calling C and C++ Callbacks from Java (Part 4)

Continuing from the last post, I will show how we can use JNA to allow C (and C++) code to invoke callback functions implemented in pure Java.

In case you are a bit rusty on callbacks, I have a whole series of posts on that, as part of this series. Feel free to check those out, starting with Callbacks.

Let’s jump right into it then!

Contents

  1. Demo
  2. Conclusion

Demo

For this demo, let’s pick a very simple example. (This is the same example as covered in the post covering Common Lisp callbacks from C/C++ code.).

We have a person type which has the following slots/fields – name, gender, and age. From our Java code, we want to instantiate an instance of person, and then use a function in a native library, prefix_name to append either “Mr.” or “Miss” in front of the person’s name, depending on the value of the gender slot (0 for female, anything else for male).

First we define the interface for the native library (in callback_demo.h):

#ifndef __CALLBACK_DEMO_H__
#define __CALLBACK_DEMO_H__ "callback_demo.h"

typedef struct person {
    char* name;
    int gender;
    int age;
} person;

#ifdef __cplusplus
extern "C" {
#endif
    void prefix_name(person*, void (*)(person*));
#ifdef __cplusplus
}
#endif
#endif

We then write the code containing the prefix_name function that will invoke our callback function (in callback_demo.c):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "callback_demo.h"

#define MAXSIZE 50

char* concatenate_names(const char* prefix, char* name)
{
    int len = strlen(prefix) + strlen(name) + 1;

    char* full_name = (char*)malloc(len * sizeof(char));

    if (full_name != NULL) {
        char* cp = full_name;

        while (*prefix != '\0')
            *cp++ = *prefix++;

        *cp++ = 0x20;

        while (*name != '\0')
            *cp++ = *name++;
   
         *cp = '\0';

        return full_name;
    }
   return name;
}
   

void prefix_name(person* p, void (*cb)(person*))
{
    const char* MISTER = "Mr.";
    const char* MISS = "Ms.";
    char* res = NULL;

    // 0 - female, anything else male
    res = p->gender == 0 ? concatenate_names(MISS, p->name) :
                           concatenate_names(MISTER, p->name);
    strcpy(p->name, res);
    
    (*cb)(p);
}

void sample_callback(person* p)
{
    printf("%s, %s, %d\n", p->name, p->gender == 0 ? "Female" : "Male", p->age);
}

int main()
{
    person rich;

    rich.name = (char*)malloc(MAXSIZE * sizeof(char));
    strcpy(rich.name, "Rich");
    rich.gender = 1;
    rich.age = 49;

    prefix_name(&rich, &sample_callback);
    
    return 0;
}

Explanation: The code is relatively straightforward. As can be seen from the header file, prefix_name is the entry point to the library (and the one which gets invoked from the Java code).

The prefix_name function takes an instance of the person structure as well as a callback function. Note the signature of the callback function:

void (*)(person*).

This callback function expects to be passed a modified instance of the person instance that is the first parameter of the prefix_name function.

The logic is very simple – simply check for the gender field, and then depending on whether it is 0 or some other way, update the name field of the person instance by prepending “Miss” or “Mr.” respectively.

Finally, the callback function cb is invoked, passing control back to the client code.

All right, now we compile the code into a library, libcallbackdemo.dylib:

Timmys-MacBook-Pro:Demo z0ltan$ clang -dynamiclib -o libcallbackdemo.dylib callback_demo.c

Timmys-MacBook-Pro:Demo z0ltan$ ls
callback_demo.c		callback_demo.h		libcallbackdemo.dylib

Excellent!

The Java code to plug into the native libraries surprisingly concise and simple (in CallbackDemo.java):

import com.sun.jna.Library;
import com.sun.jna.Native;
import com.sun.jna.Callback;
import com.sun.jna.Platform;
import com.sun.jna.Structure;

import java.util.List;
import java.util.Arrays;

public class CallbackDemo {
    private static final String lib;

    static {
        if (Platform.isMac())
            lib = "libcallbackdemo.dylib";
        else if (Platform.isWindows())
            lib = "libcallbackdemo.dll";
        else
            lib = "libcallbackdemo.so";
    }

    public interface CallbackDemoLib extends Library {
        CallbackDemoLib INSTANCE = (CallbackDemoLib)Native
                                    .loadLibrary(lib, CallbackDemoLib.class);

        interface PrefixCallback extends Callback {
            void print(Person person);
        }

        void prefix_name(Person person, PrefixCallback func);
    }

    public static class Person extends Structure {
       public String name;
       public int gender;
       public int age;

        @Override
        public List<String> getFieldOrder() {
            return Arrays.asList(new String[] {"name", "gender", "age"});
        }
    }

    public static void main(String[] args) {
        CallbackDemoLib.PrefixCallback callback = new CallbackDemoLib.PrefixCallback() {
                                                        @Override
                                                        public void print(Person person) {
                                                            System.out.format("Name: %s, Gender: %s, Age: %d\n",
                                                                person.name, person.gender == 0 ? "Female" : "Male",
                                                                person.age);
                                                        }
                                                    };

        Person rich = new Person();
        rich.name = "Rich";
        rich.gender = 1;
        rich.age = 49;

        Person vigdis = new Person();
        vigdis.name = "Vigdis";
        vigdis.gender = 0;
        vigdis.age = 28;

        CallbackDemoLib.INSTANCE.prefix_name(rich, callback);
        CallbackDemoLib.INSTANCE.prefix_name(vigdis, callback);
    }
}

And the output:

Timmys-MacBook-Pro:Java-to-C z0ltan$ javac -cp "./:./jna.jar" JavaToC.java

Timmys-MacBook-Pro:Java-to-C z0ltan$ java -cp "./:./jna.jar" JavaToC
System information:
Arch: x86_64, Model: MacBookPro11,2, Memory: 16GB, CPUs: 8, Logical CPUs: 8

10 25 -100 199 0 1 1 98 99 100 
-100 0 1 1 10 25 98 99 100 199 

Perfect! Now let’s do a brief rundown on the Java code.

Explanation: The modus operandi is very similar to that used for normal interaction with native libraries.

We define an interface CallbackDemoLib that holds proxies for the native functions in the libcallbackdemo.dylib shared library. This library exposes a single function prefix_name that expects a pointer to a person struct instance, and a callback function.

To implement the callback function, we declare another interface PrefixCallback that contains a single method print. Note that this name can be any name that you desire. The only contract is that the signature of this method should match that of the callback defined in the native function.

The native prefix_name function expects a callback that takes a pointer to a person instance. In Java, this maps nicely to a Person class. This class does have to extend the JNA class Structure.

The Person class, which maps exactly onto the native person struct needs to have one overridden method getFieldOrder(). This is important because other JNA cannot determine the layout of the object to map onto the native struct. So, in this example, we take care to ensure that the field order is specified exactly in this order – name, gender, and age. What would happen if we had mixed the order around? Let’s try that and see.

First let’s swap out the name and age fields:

public static class Person extends Structure {
       public String name;
       public int gender;
       public int age;

        @Override
        public List<String> getFieldOrder() {
            return Arrays.asList(new String[] {"age", "gender", "name"});
        }
    }

And the output:

Timmys-MacBook-Pro:C-to-Java z0ltan$ java -cp "./:./jna.jar" CallbackDemo
#
# A fatal error has been detected by the Java Runtime Environment:
#
#  SIGSEGV (0xb) at pc=0x00007fff94886132, pid=1232, tid=2823
#
# JRE version: Java(TM) SE Runtime Environment (9.0+131) (build 9-ea+131)
# Java VM: Java HotSpot(TM) 64-Bit Server VM (9-ea+131, mixed mode, tiered, compressed oops, g1 gc, bsd-amd64)
# Problematic frame:
# C  [libsystem_c.dylib+0x1132]  strlen+0x12
#
# No core dump will be written. Core dumps have been disabled. To enable core dumping, try "ulimit -c unlimited" before starting Java again
#
# An error report file with more information is saved as:
# /Users/z0ltan/Rabota/Blogs/Cffi/JNA/C-to-Java/hs_err_pid1232.log
#
# If you would like to submit a bug report, please visit:
#   http://bugreport.java.com/bugreport/crash.jsp
# The crash happened outside the Java Virtual Machine in native code.
# See problematic frame for where to report the bug.
#
Abort trap: 6

It crashed the whole darned JVM! Hmmm… before we speculate on what’s happening, let’s try another variation – swapping the gender and age fields:

public static class Person extends Structure {
       public String name;
       public int gender;
       public int age;

        @Override
        public List<String> getFieldOrder() {
            return Arrays.asList(new String[] {"name", "age", "gender"});
        }
    }

And the output:

Timmys-MacBook-Pro:C-to-Java z0ltan$ java -cp "./:./jna.jar" CallbackDemo
Name: Mr. Rich, Gender: Male, Age: 49
Name: Mr. Vigdis, Gender: Female, Age: 28

Eh? So what’s going on here? My deduction is that this is because of the memory layout that JNA needed to do to accommodate the native person struct. In the first case, we swapped out two fields of different types whereas in the second case, the swapped fields were the same size, and so it did not affect the memory layout – it was still in the same order – String, int, and int.

So it’s appears like the name of the fields don’t matter as much as the actual data types they represent (makes sense) even if JNA does do checks to ensure we can’t give names different from the actual field names. To test out this hypothesis, let’s try out one more variation and see if that crashes the JVM again – let’s swap out name and gender instead this time:

public static class Person extends Structure {
       public String name;
       public int gender;
       public int age;

        @Override
        public List<String> getFieldOrder() {
            return Arrays.asList(new String[] {"gender", "name", "age"});
        }
    }

And the output?

Timmys-MacBook-Pro:C-to-Java z0ltan$ java -cp "./:./jna.jar" CallbackDemo
#
# A fatal error has been detected by the Java Runtime Environment:
#
#  SIGSEGV (0xb) at pc=0x00007fff94886132, pid=1247, tid=2823
#
# JRE version: Java(TM) SE Runtime Environment (9.0+131) (build 9-ea+131)
# Java VM: Java HotSpot(TM) 64-Bit Server VM (9-ea+131, mixed mode, tiered, compressed oops, g1 gc, bsd-amd64)
# Problematic frame:
# C  [libsystem_c.dylib+0x1132]  strlen+0x12
#
# No core dump will be written. Core dumps have been disabled. To enable core dumping, try "ulimit -c unlimited" before starting Java again
#
# An error report file with more information is saved as:
# /Users/z0ltan/Rabota/Blogs/Cffi/JNA/C-to-Java/hs_err_pid1247.log
#
# If you would like to submit a bug report, please visit:
#   http://bugreport.java.com/bugreport/crash.jsp
# The crash happened outside the Java Virtual Machine in native code.
# See problematic frame for where to report the bug.
#
Abort trap: 6

And just taking a peek at the crash file:

---------------  S U M M A R Y ------------

Command Line: CallbackDemo

Host: MacBookPro11,2 x86_64 2200 MHz, 8 cores, 16G, Darwin 15.6.0
Time: Wed Sep  7 10:41:53 2016 IST elapsed time: 0 seconds (0d 0h 0m 0s)

---------------  T H R E A D  ---------------

Current thread (0x00007f9e3080c000):  JavaThread "main" [_thread_in_native, id=2823, stack(0x000070000011a000,0x000070000021a000)]

Stack: [0x000070000011a000,0x000070000021a000],  sp=0x0000700000218b00,  free space=1018k
Native frames: (J=compiled Java code, j=interpreted, Vv=VM code, C=native code)
C  [libsystem_c.dylib+0x1132]  strlen+0x12
C  [libcallbackdemo.dylib+0xcc6]  concatenate_names+0x26
C  [libcallbackdemo.dylib+0xe28]  prefix_name+0x68
C  [jna5393012570626767002.tmp+0xe134]  ffi_call_unix64+0x4c
C  0x00007000002195c8

Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
j  com.sun.jna.Native.invokeVoid(JI[Ljava/lang/Object;)V+0
j  com.sun.jna.Function.invoke([Ljava/lang/Object;Ljava/lang/Class;Z)Ljava/lang/Object;+29
j  com.sun.jna.Function.invoke(Ljava/lang/reflect/Method;[Ljava/lang/Class;Ljava/lang/Class;[Ljava/lang/Object;Ljava/util/Map;)Ljava/lang/Object;+249
j  com.sun.jna.Library$Handler.invoke(Ljava/lang/Object;Ljava/lang/reflect/Method;[Ljava/lang/Object;)Ljava/lang/Object;+348
j  com.sun.proxy.$Proxy0.prefix_name(LCallbackDemo$Person;LCallbackDemo$CallbackDemoLib$PrefixCallback;)V+20
j  CallbackDemo.main([Ljava/lang/String;)V+63
v  ~StubRoutines::call_stub

siginfo: si_signo: 11 (SIGSEGV), si_code: 1 (SEGV_MAPERR), si_addr: 0x0000000000000000

Indeed – it looks like the strlen is being attempted on an int! No wonder it crashed and burnt.

However, I have a suspicion that this behaviour might again differ depending on the platform. So the takeaway here is – always use the field names (with the correct types) in the same order as in the native struct.

Conclusion

Top

The JNA library is extremely useful because it is pure Java (unlike JNI, which is hardly convenient to use). In addition, as we have seen in the last post and in the current post, the APIs for JNA are very well-designed indeed.

I would recommend exploring further using the resources mentioned in the References section of the last post.

Next up, a small mini-project as the conclusion of this interop mini-series – a less-than-trivial essay at embedding a JVM instance within Common Lisp! Stay tuned.

Interop mini-series – Calling C and C++ Callbacks from Java (Part 4)

Interop mini-series – Calling C and C++ code from Java (Part 3)

In this post and the next, I will show how we can use the JNA (Java Native Access) library to perform the same interop operations as demonstrated in the first three parts of this mini-series (check them out!).

Contents

  1. The JNA library
    1. Installation
  2. Demo
    1. Building the C library
    2. Building the C++ library
    3. Demo run
  3. References

The JNA library

The JNA (Java Native Access) library is an alternative to using JNI in order to interop with C and C++ shared libraries. While JNI is a real pain to get right, JNA abstracts away all the gory details so that the developer can focus on the functionality instead of boilerplate.

Interestingly, JNA itself uses JNI stubs internally, connecting with the libffi library. (A link has been provided in the References section). This is why the library works across multiple platforms, and is still relatively lightweight.

Installation

JNA comprises of two Jar files – jna.jar and jna-platform.jar. jna.jar provides the core APIs while jna-platform contains the aforementioned stubs to interact with libffi.

For instance, the Mac OS X specific bits are secreted away in com.sun.jna.darwin/libjnidispatch.jnilib inside jna-platform.jar. Likewise for other platforms.

You can either download the JNA jars directly and use them, or use use Maven to integrate JNA functionality in your project. Again, I have provided all the links in the References section.

Demo

Top

For this demo, we will first see how the two native libraries (which our Java code will be using) are created, and then we will use them both in the same example.

The first library, libsysteminfo.dylib uses pure C code, whereas the other library, libnumbersorting.dylib uses C++ code with a C wrapper (the reason will be explained in the relevant section).

Building the C library

Top

For the C example, I decided to use use the native library to get some useful system information – architecture type, model name, memory, number of cpus, and the number of logical cpus (cores).

Note that this example works only in Mac OS X. For Linux, the sysctlbyname function can be replaced by sysctl with appropriate changes. For Windows, you will have to check which kernel call provides the same functionality.

We will use the sysctlbyname function to extract these values.

Let’s define the header file first (in system_info.h):

#ifndef __SYSTEM_INFO_H__
#define __SYSTEM_INFO_H__ "system_info.h"

#include <sys/types.h>
#include <sys/sysctl.h>

#ifdef __cplusplus
extern "C" {
#endif

char* get_machine();
char* get_model();
int64_t get_memory();
int32_t get_ncpu();
int32_t get_nlogicalcpu();

#ifdef __cplusplus
}
#endif
#endif

And the corresponding C implementation (in system_info.c:

#include <stdio.h>
#include "system_info.h"

#define MAXSIZE 210

char* get_machine()
{
    static char machine[MAXSIZE];
    size_t len = sizeof(machine);

    sysctlbyname("hw.machine", &machine, &len, NULL, 0);

    return machine;
}

char* get_model()
{
    static char model[MAXSIZE];
    size_t len = sizeof(model);

    sysctlbyname("hw.model", &model, &len, NULL, 0);

    return model;
}

int64_t get_memory()
{
    int64_t mem;
    size_t len = sizeof(mem);

    sysctlbyname("hw.memsize", &mem, &len, NULL, 0);

    return mem;
}

int32_t get_ncpu()
{
    int32_t cpu;
    size_t len = sizeof(cpu);

    sysctlbyname("hw.ncpu", &cpu, &len, NULL, 0);

    return cpu;
}


int32_t get_nlogicalcpu()
{
    int32_t logical_cpu;
    size_t len = sizeof(logical_cpu);

    sysctlbyname("hw.logicalcpu", &logical_cpu, &len, NULL, 0);

    return logical_cpu;
}

int main(int argc, char* argv[])
{
    printf("%s, %s, %lld, %d, %d\n", 
            get_machine(),
            get_model(),
            get_memory(),
            get_ncpu(),
            get_nlogicalcpu());

    return 0;
}

Let’s compile it into a shared library (in this case, Clang + LLVM on Mac OS X. For other compilers such as gcc proper, check the relevant documentation):

Timmys-MacBook-Pro:c_demo_system_info z0ltan$ clang -dynamiclib -o libsysteminfo.lib system_info.c

Timmys-MacBook-Pro:c_demo_system_info z0ltan$ ls
libsysteminfo.lib	system_info.c		system_info.h

Building the C++ library

Top

This is the more interesting bit for more than one reason! In this example, let’s try and sort an array of integers using the native library.

Again, let’s write the interface out first (in number_sorting.h):

#ifndef __NUMBER_SORTING_H__ 
#define __NUMBER_SORTING_H__ "number_sorting.h"

void callback_function(int[], int);

extern "C" {
    void sort_numbers(int[], int);
}
#endif

Looks good, but what’s the deal with the callback_function? We’ll get to that in just a monent. For now, let’s flesh out the functionality for this interface (in number_sorting.cpp:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

void sort_vector(std::vector<int>&, int[], int);

void callback_function(int array[], int size)
{
    std::vector<int> vec(size);

    sort_vector(vec, array, size);

    int i = 0;
    for (std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); it++)
        array[i++] = *it;
}
    

template <typename T>
void display_elements(const std::vector<T>& vec)
{
    for (std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;
}


void sort_vector(std::vector<int>& v, int numbers[], int count)
{
    for (int i = 0; i < count; i++)
        v[i] = numbers[i];

    display_elements(v);

    std::sort(v.begin(), v.end(), [](int x, int y) { return x < y; });
}

int main()
{
    std::ios_base::sync_with_stdio(false);

    int sample[] = { 1, 2, 0, -1, 3, 199, 200, 110, -234, 12345 };

    callback_function(sample, sizeof(sample)/sizeof(sample[0]));

    for (int i = 0; i < (int)sizeof(sample)/sizeof(sample[0]); i++)
        std::cout << sample[i] << " ";
    std::cout << std::endl;

    return 0;
}

Hmmm, this seems a bit too convoluted for this simple example? Why all the indirection? The reason will become crystal clear once we define the corresponding C file (in number_sorting.c) as well:

#include "number_sorting.h"

void sort_numbers(int numbers[], int n)
{
    callback_function(numbers, n);
}

Explanation: The reasons why we need both number_sorting.c and number_sorting.cpp, both of which implement the same interface, number_sorting.h
are two-fold:

  1. Since we are using some C++-only features such std::vector , std::sort, and C++11 lambdas, we need to invoke them in a separate function
  2. And the more important reason – C++’s pernicious name-mangling

Now, if we had simply written the entire sorting functionality using integer arrays and sorted using with C-like constructs (say, qsort, or a manually written sorting function), we wouldn’t need all this indirection, and we could have simply written the header as:

#ifndef __NUMBER_SORTING_H__ 
#define __NUMBER_SORTING_H__ "number_sorting.h"

extern "C" {
    void sort_numbers(int[], int);
}
#endif

and provided the implementation in number_sorting.cpp alone. That would have worked out fine. However, because we use all those C++ template constructs as well as functional constructs, if we had used this same header file, we would have got a name-mangling issue, and the function would not be visible to the Java client! (note: there are tools such as JNAerator which can help resolve name mangling issues, but that is beyond the scope of this tutorial).

To get around this, we write a C wrapper (number_sorting.c) which simply invokes the C++ function callback_function defined in number_sorting.cpp. Now you may think that we could have simply embedded callback_function inside the definition of sort_numbers in the C++ file alone, but that would not work either. Check out the reference “How to mix C and C++” in the “References section” for more details.

All right, let’s compile the code and generate the shared library:

Timmys-MacBook-Pro:c++_demo_sorting z0ltan$ clang++ -std=c++11 -stdlib=libc++ -dynamiclib -o libnumbersorting.dylib number_sorting.c number_sorting.cpp
clang: warning: treating 'c' input as 'c++' when in C++ mode, this behavior is deprecated

Timmys-MacBook-Pro:c++_demo_sorting z0ltan$ ls
libnumbersorting.dylib	number_sorting.c	number_sorting.cpp	number_sorting.h

Timmys-MacBook-Pro:c++_demo_sorting z0ltan$ nm -gU libnumbersorting.dylib 
0000000000000a10 T __Z11sort_vectorRNSt3__16vectorIiNS_9allocatorIiEEEEPii
0000000000000730 T __Z17callback_functionPii
0000000000000c00 T _main
0000000000000700 T _sort_numbers

We can also see that the function sort_numbers has not been subjected to name-mangling.

Demo Run

Top

The Java code to plug into the native libraries is surprisingly concise and simple (in JavaToC.java):

import com.sun.jna.Native;
import com.sun.jna.Platform;
import com.sun.jna.Library;

public class JavaToC {
    public interface SystemInfoLib extends Library {
        SystemInfoLib INSTANCE = (SystemInfoLib)Native.loadLibrary("libsysteminfo.dylib",
                                    SystemInfoLib.class);

        String get_machine();
        String get_model();
        long get_memory();
        int get_ncpu();
        int get_nlogicalcpu();
    }

    public static native void sort_numbers(int[] numbers, int count);

    static {
        Native.register("libnumbersorting.dylib");
    }

    public static void main(String[] args) {
        System.out.println("System information:");
        System.out.format("Arch: %s, Model: %s, Memory: %dGB, CPUs: %d, Logical CPUs: %d\n\n",
            SystemInfoLib.INSTANCE.get_machine(),
            SystemInfoLib.INSTANCE.get_model(),
            SystemInfoLib.INSTANCE.get_memory()/ (1024*1024*1024),
            SystemInfoLib.INSTANCE.get_ncpu(),
            SystemInfoLib.INSTANCE.get_nlogicalcpu());

        int[] numbers = new int[]{10, 25, -100, 199, 0, 1, 1, 98, 99, 100};
        
        sort_numbers(numbers, numbers.length);
           
        for (int n : numbers) {
            System.out.format("%d ", n);
        }
        System.out.println();
    }
}

And the output:

Timmys-MacBook-Pro:Java-to-C z0ltan$ javac -cp "./:./jna.jar" JavaToC.java

Timmys-MacBook-Pro:Java-to-C z0ltan$ java -cp "./:./jna.jar" JavaToC
System information:
Arch: x86_64, Model: MacBookPro11,2, Memory: 16GB, CPUs: 8, Logical CPUs: 8

10 25 -100 199 0 1 1 98 99 100 
-100 0 1 1 10 25 98 99 100 199 

Perfect! Now let’s do a brief rundown on the Java code.

Explanation: There are basically two main ways in which to use JNA to load the native library:

    1. Implement an interface that extends the Library interface, use Native.loadLibrary() to load the specific library for your platform. The JNA class Platform provides some helper methods and static fields for this purpose.
      You can then include the declarations for the native methods inside your interface. Note that the names of the methods must exactly match those in the native library.

 

  1. The other way (preferred if you are only interested in a few functions) is to load the native library statically using a static block and the Native.register method.
    Along with this, you also need to declare the functions of interest as static native methods. Take care to ensure that the names again match with those defined inside the native library.

In the given example, both approaches have been amply demonstrated – libsysteminfo.dylib is loaded using the first approach since there are quite a few functions that I am interested in using.

On the other hand, since there is only a single function the libnumbersorting.dylib native library, it’s more convenient to load it a static native method instead.

Pay special attention to the data types used in the declarations of the methods. Just like with cffi, the data types match quite nicely with the native types in most cases. Refer to the documentation for more specific type declarations.

In the next post, we will see how to write callback functions in Java that can be invoked by functions from inside native libraries.

References

Top

Some useful links for the JNA library:

Interop mini-series – Calling C and C++ code from Java (Part 3)

Interop mini-series – Calling C and C++ Callbacks from Common Lisp (Part 2c)

This post picks up on the first part of this interop mini-series (Calling C and C++ from Common Lisp). I recommend checking out that post first in order to make sense of this one.

Contents

  1. Intent
  2. Demo
  3. Useful functions
  4. Conclusion

Intent

The scope of this post is to cover interop with C and C++ code from Common Lisp using callbacks. In case you are not sure about what callbacks are, please check the first part of this post out – Callbacks special.

We will continue to use the cffi library for our demo here as well.

Demo

Top

For this demo, let’s pick a very simple example.

We have a person type which has the following slots/fields – name, gender, and age. From our Common Lisp code, we want to instantiate an instance of person, and then use a function in a native library, prefix_name to append either “Mr.” or “Miss” in front of the person’s name, depending on the value of the gender slot (0 for female, anything else for male).

First we define the interface for the native library (in callback_demo.h:

#ifndef __CALLBACK_DEMO_H__
#define __CALLBACK_DEMO_H__ "callback_demo.h"

typedef struct person {
    char* name;
    int gender;
    int age;
} person;

#ifdef __cplusplus
extern "C" {
#endif
    void prefix_name(person*, void (*)(person*));
#ifdef __cplusplus
}
#endif
#endif

We then write the code containing the prefix_name function that will invoke our callback function (in callback_demo.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "callback_demo.h"

#define MAXSIZE 50

char* concatenate_names(const char* prefix, char* name)
{
    int len = strlen(prefix) + strlen(name) + 1;

    char* full_name = (char*)malloc(len * sizeof(char));

    if (full_name != NULL) {
        char* cp = full_name;

        while (*prefix != '\0')
            *cp++ = *prefix++;

        *cp++ = 0x20;

        while (*name != '\0')
            *cp++ = *name++;
   
         *cp = '\0';

        return full_name;
    }
   return name;
}
   

void prefix_name(person* p, void (*cb)(person*))
{
    const char* MISTER = "Mr.";
    const char* MISS = "Ms.";
    char* res = NULL;

    // 0 - female, anything else male
    res = p->gender == 0 ? concatenate_names(MISS, p->name) :
                           concatenate_names(MISTER, p->name);
    strcpy(p->name, res);
    
    (*cb)(p);
}

void sample_callback(person* p)
{
    printf("%s, %s, %d\n", p->name, p->gender == 0 ? "Female" : "Male", p->age);
}

int main()
{
    person rich;

    rich.name = (char*)malloc(MAXSIZE * sizeof(char));
    strcpy(rich.name, "Rich");
    rich.gender = 1;
    rich.age = 49;

    prefix_name(&rich, &sample_callback);
    
    return 0;
}

Explanation: The code is relatively straightforward. As can be seen from the header file, prefix_name is the entry point to the library (and the one which gets invoked from the Common Lisp code).

The prefix_name function takes an instance of the person structure as well as a callback function. Note the signature of the callback function:

void (*)(person*).

This callback function expects to be passed a modified instance of the person instance that is the first parameter of the prefix_name function.

The logic is very simple – simply check for the gender field, and then depending on whether it is 0 or some other way, update the name field of the person instance by prepending “Miss” or “Mr.” respectively.

Finally, the callback function cb is invoked, passing control back to the client code.

All right, now we compile the code into a library, libcallbackdemo.dylib:

Timmys-MacBook-Pro:Demo z0ltan$ clang -dynamiclib -o libcallbackdemo.dylib callback_demo.c

Timmys-MacBook-Pro:Demo z0ltan$ ls
callback_demo.c		callback_demo.h		libcallbackdemo.dylib

Excellent!

Now we focus on the Common Lisp bit. This part is relatively straight forward. Let’s see the code in action first, and then a bit of explanation.

First the code that calls the native library function, prefix_name (in c-to-lisp.lisp):

;;;; Demonstrating how Common Lisp can invoke functions in C or C++ code, which then themselves invoke a callback function written in Common Lisp.
;;;; This helps in those cases when Common Lisp needs to make use of some 
;;;; functionality present in a native library which is written using callbacks.

(require 'cffi)

(defpackage :c-to-lisp-user
  (:use :cl :cffi))

(in-package :c-to-lisp-user)


;;; Callback demo - first define the foreign library
;;; containing the function which takes a callback function.

(define-foreign-library libcallbackdemo
  (:darwin "libcallbackdemo.dylib")
  (:unix "libcallbackdemo.so")
  (t (:default "libcallbackdemo.dylib")))

(use-foreign-library libcallbackdemo)

;;; define Common Lisp equivalent of the C structure
(defcstruct person
  (name :string)
  (gender :int)
  (age :int))


;;; define the implementation of the callback
(defcallback print-prefixed-person :void
    ((ptr (:pointer (:struct person))))
  (with-foreign-slots ((name gender age) ptr (:struct person))
    (format t "Name: ~a, Gender: ~a, Age: ~d~%"
            name
            (if (zerop gender) "Female" "male")
            age)))


;;; invoke the callback in the C library with a new instance of
;;; a person object
(defun test-callback ()
  (with-foreign-object (rich '(:struct person))
    (setf (foreign-slot-value rich '(:struct person) 'name) "Rich"
          (foreign-slot-value rich '(:struct person) 'gender) 1
          (foreign-slot-value rich '(:struct person) 'age) 49)
    (foreign-funcall "prefix_name"
                     :pointer rich
                     :pointer (callback print-prefixed-person)
                     :void))
  (with-foreign-object (vigdis '(:struct person))
    (setf (foreign-slot-value vigdis '(:struct person) 'name) "Vigdis"
          (foreign-slot-value vigdis '(:struct person) 'gender) 0
          (foreign-slot-value vigdis '(:struct person) 'age) 28)
    (foreign-funcall "prefix_name"
                     :pointer vigdis
                     :pointer (callback print-prefixed-person)
                     :void)))

;;; unload the foreign library
(close-foreign-library 'libcallbackdemo)

And the output:

C-TO-LISP-USER> (test-callback)
Name: Mr. Rich, Gender: male, Age: 49
Name: Ms. Vigdis, Gender: Female, Age: 28
; No value

Explanation: This code is also quite simple. We begin by defining the native library, and then loading it.

Next, we define the callback function using the cffi:defcallback macro. The defined callback function, print-prefixed-person uses a pointer to a person instance (which is returned by the prefix_name function inside libcallbackdemo.dylib), and so need to define the person structure first.

For that, we use another macro, cffi:defcstruct. As you can see, there is simply an exact representation of the structure defined in callback_demo.h albeit in a Lispy manner.

cffi:with-foreign-slots is a very important macro that destructures its pointer argument into the supplied slots. Note that the slot names must be the same as that provided in the person structure defined in the Common Lisp code. Note the use of cffi:foreign-slot-value instead of cffi:mem-aref as in the previous post. The rule of thumb is this – use cffi:foreign-slot-value when accessing slots, and use cffi:mem-aref when accessing atomic types.

Finally, we actually invoke the prefix_name function from test_callback. We create two instances of the person structure, and then we pass the callback function in the foreign-funcall invocation using the macro cffi:callback.

cffi:callback simply returns a pointer which is what the prefix_name function in libcallbackdemo.dylib requires. The cycle is complete!

As we can see from the output, the names are prepended with the correct suffix.

Basic useful functions

Top

Here is the summarised list of the additional functions that were used in the demo:

  • cffi:defcstruct
  • cffi:defcallback
  • cffi:with-foreign-slots
  • cffi:foreign-slot-value
  • cffi:callback

Conclusion

Top

The cffi library is a very powerful and well-designed library for dealing with native libraries. It is also quite vast, and I would most definitely recommend browsing through the official manual for further examples, and also for usage patterns for your specific needs.

Next up, I will demonstrate interop between C (and C++) and Java using the JNA library, which is far superior to the alternative of using pure JNI. That will be also be in two parts.

Interop mini-series – Calling C and C++ Callbacks from Common Lisp (Part 2c)

Interop mini-series – Callbacks special! (Common Lisp special) (Part 2b)

This is a continuation of the previous post callbacks interlude. I decided to give the section pertaining to Common Lisp its own post as I think there is some good educational value in this part itself.

We carry on from where we left off last time. We continue with the same squaring number callback example.

As a quick refresher, the idea is to implement a synchronous callback scenario. The function client invokes another function squarify which squares the passed value and invokes a callback function callback.

How it’s done in Common Lisp

Let’s start off with our first attempt to implement the solution in Common Lisp.

;;;; Callback demo using the squarify example.

(defpackage :callback-demo-user
  (:use :cl))

(in-package :callback-demo-user)

(defun callback(n)
  (format t "Received: ~d~%" n))

(defun squarify(n cb)
  (funcall cb (* n n)))

(defun client ()
  (let ((n (progn
             (princ "Enter a number: ")
             (read))))
    (squarify n #'callback)))
CALLBACK-DEMO-USER> (client)
Enter a number: 19
Received: 361
NIL

That’s the direct equivalent of all the demos shown so far. However, since Common Lisp is a functional language (albeit not as pure as, say, Scheme or Haskell), we can certainly do better!

In most Functional Programming languages, higher order functions are usually deployed to do the job. So let’s see if we can cook up something nicely functional like function composition.
Here’s a first attempt:

(defun client()
  (funcall #'(lambda (n)
               (format t "Received: ~d~%" n))
           (funcall #'(lambda (n)
                        (* n n))
                    (funcall #'(lambda ()
                                 (princ "Enter number: ")
                                 (read))))))

Which produces:

CALLBACK-DEMO-USER> (client)
Enter number: 19
Received: 361
NIL

As expected! Now, as you may know, funcall simply takes a function and some arguments (optional), and applies the function to those arguments. In this case, we simply compose them in the proper order so that the types match up: read a number -> square it -> print message.

However, let’s work our way to a generic compose function that simulates the behaviour of Haskell’s composition operator. The previous function can be improved by defining a new version that composes the three functions in the mentioned order (so as to match types):

The compose function:

(defun compose (fn gn hn)
  #'(lambda (&rest args)
      (funcall fn (funcall gn (apply hn args)))))

And the client to test it:

(defun client ()
  (funcall (compose #'(lambda (x)
                        (format t "Received: ~d~%" x))
                    #'(lambda (x)
                        (* x x))
                    #'(lambda ()
                        (princ "Enter a number: ")
                        (read)))))

And the output is the same:

CALLBACK-DEMO-USER> (client)
Enter a number: 19
Received: 361
NIL

So what’s changed? Well, taking inspiration from the nested funcall function, we defined compose to invoke the functions in the proper order – first read the number, and then square it, and then finally print it! (Remember that the functions are composed in reverse order in which they are entered).

Note that the last function invocation is done using apply instead of funcall because &rest args produces a list of arguments, and funcall does not work with that (unless the function definition takes a list itself as a parameter, but that is not the general case, and apply works very well with lists and destructures them correctly.

How can we make this generic enough though? We notice the pattern – we invoke apply on the innermost function call, but we use funcall for the rest of the function call chain. This means that we must handle two cases – if there is a single function passed in, we should simply use apply on that, and if not, we should take care to chain them up as discussed. This lends itself to a nice recursive definition as shown next.

The updated compose function:

(defun compose (&rest funcs)
  (labels ((f (funcs args)
             (if (null (cdr funcs))
                 (apply (car funcs) args)
                 (funcall (car funcs) (f (cdr funcs) args)))))
    #'(lambda (&rest args)
        (f funcs args))))
)

And the test client for it:

(defun client ()
  (funcall (compose #'(lambda (x)
                        (format t "Received: ~d~%" x))
                    #'(lambda (x)
                        (* x x))
                    #'(lambda ()
                        (princ "Enter number: ")
                        (read)))))

And the output:

CALLBACK-DEMO-USER> (client)
Enter number: 19
Received: 361
NIL

Explanation: What we do is simply generalise the three-function version of compose into a generic function. For this we, define an internal function f that takes the supplied functions and the arguments as input.

f then recursively decomposes the function applications. The base condition (stopping condition) is when there is only one function left. The (if (null (cdr funcs)) bit then takes care to return the only apply call that we need, and that is of course, applied to the args argument.

As the recursion unwinds the call stack, successive funcallS are applied at each stage. This is exactly in line with the algorithm discussed at the end of the last section.

Now we are almost home and dry! Pay special attention to the order in which the lambda equivalents of the functions are entered in the client function. They are applied in the following order – callback, squarify, and then client.

We could stop here, but there’s one more change that we can make. The current version of compose works absolutely as expected, but the intuitive order of supplying functions is the opposite of what we could expect as a user. The expected order would be, in English, “read in the number, square it, and then print out a message indicating that the number was received”.

Let’s fix that last bit for out final version of compose.

Final version of compose:

;;; final version of compose
(defun compose(&rest funcs)
  (labels ((f (funcs args)
             (if (null (cdr funcs))
                 (apply (car funcs) args)
                 (funcall (car funcs) (f (cdr funcs) args)))))
    #'(lambda (&rest args)
        (f (reverse funcs) args)))))

And the corresponding test code:

;;; test out the final version of compose
(defun client ()
  (funcall (compose #'(lambda ()
                        (princ "Enter a number: ")
                        (read))
                    #'(lambda (x)
                        (* x x))
                    #'(lambda (x)
                        (format t "Received: ~d~%" x)))))

And now let’s test out and see if it works!

CALLBACK-DEMO-USER> (client)
Enter a number: 19
Received: 361
NIL

Success!

The only difference is this line: (f (reverse funcs) args). We simply reverse the order of the received functions while passing it to the recursive function f, and the rest of the code remains exactly the same!

And, of course, this is purely functional! Sweet, ain’t it?

The compose function could be optimised in multiple ways – converting it to an iterative version for instance, but conceptually, this works exactly as advertised.

Conclusion

This post illustrates why I love Common Lisp! Even as I make my journey through the world of Common Lisp, my admiration for it only grows. If there is some feature that we would like to incorporate into the language, it can be done in a just a few lines of code! No other language truly comes close in terms of expressiveness and extensibility.

Interop mini-series – Callbacks special! (Common Lisp special) (Part 2b)