Earn extra honor and gain new allies!
Honor is earned for each new codewarrior who joins.
Learn more

Just testing whether it is possible to "cheat" using the stack internally maintained by the computer to "implement" stack operations (between calls) in NASM.

Conclusion: It doesn't seem to be possible - at least with the way I did it, I got a segfault during the first call to stack_push() which just attempts to push its second argument to the internal stack and returns to the caller, let alone the pop and peek operations. There also doesn't seem to be a reliable way to check whether the internal stack is empty. Thus, it should be safe to translate my recent Stacks kata into NASM.

global stack_push, stack_pop, stack_peek ; , stack_is_empty
section .text
stack_push:
  push rsi
  ret
stack_pop:
  pop rsi
  ret
stack_peek:
  pop rsi
  push rsi
  ret

Yes and no. A queue can be implemented using one explicit stack by leveraging the technique of recursion in the "dequeue" operation but note that recursion is handled internally by a function call stack; hence, technically, there are still two stacks at work ;)

class Queue {
  constructor() {
    this._stack = []; // We will be using this array as a stack - only
    // its push and pop operations will ever be called
  }
  enqueue(data) {
    this._stack.push(data);
  }
  dequeue() {
    if (this._stack.length === 1)
      return this._stack.pop();
    else {
      var tmp = this._stack.pop(), result = this.dequeue();
      this.enqueue(tmp);
      return result;
    }
  }
}
Data Structures
Algorithms
Binary Search Trees
Trees
Binary
Maps

Map/Dictionary/Associative Array as a binary search tree of entries

Suggested reading: Binary Search Tree - Wikipedia

Last time we saw how the map/dictionary/assoc array datatype can be implemented as a linked list of entries. We also noted how this implementation is seldomly used in real-world applications due to its sheer inefficiency for pretty much every operation.

So is there a way to make this data type more efficient? As it turns out, using a different data structure can really make an impact on the runtime complexity of operations on maps. One particular data structure that suits maps pretty well is the binary search tree (BST). A binary search tree is a special case of a binary tree where when one traverses its elements pre-order (left -> value -> right), the sequence of elements are in order. When the BST is perfectly balanced (i.e. all its branches have the same depth), its insertion, lookup and deletion operations are all logarithmic in time (O(log n)) because for every level you advance through the tree, you can effectively discard half of the tree. Another advantage of using a BST in our map is that we can implement a function converting the map into an iterator (if we wish to iterate through our key-value pairs in the map) such that the sequence of elements in the iterator are guaranteed to arrive in-order. However, the major drawback of (ordinary) BSTs is that if the elements are inserted in-order (or in reversed order), it degenerates into a linked list so its operations become O(n) again. Furthermore, if one inserts elements randomly into a BST, its operations converge towards an O(sqrt n) time complexity which is significantly less efficient than O(log n).

If only there were a way to ensure that our BST is sufficiently balanced at all times ... ;)

Code
Diff
  • #include <stddef.h>
    
    typedef struct {
      // Denotes a key-value pair of integers, e.g. 7 => 34
      int key, value;
    } Entry;
    
    typedef struct node_t {
      // A node of a binary (search) tree - the internal implementation of our map
      Entry *entry;
      struct node_t *left, *right;
    } Node;
    
    typedef struct {
      // Our map datatype, implemented as a simple wrapper around our BST
      // This allows us to insert elements to a map by object reference and
      // reserves NULL for indicating an invalid reference to a Map (instead
      // of an empty map)
      Node *root;
    } Map;
    
    int map_get(const Map *map, int key) {
      // Retrieves the corresponding value for a given key in a map
      // Assumption: The given key-value pair in the map exists
      const Node *nd = map->root;
      while (nd->entry->key != key)
        nd = key < nd->entry->key ? nd->left : nd->right;
      return nd->entry->value;
    }
    
    void map_set(Map *map, int key, int value) {
      // Adds the key-value pair to the map if no entry with the given key exists;
      // otherwise modifies the value of the entry with the given key to the given value
      if (map->root == NULL) {
        map->root = malloc(sizeof(Node));
        map->root->entry = malloc(sizeof(Entry));
        map->root->entry->key = key;
        map->root->entry->value = value;
        map->root->left = map->root->right = NULL;
      } else {
        Node *nd = map->root;
        while (nd->entry->key != key) {
          const Node *tmp = key < nd->entry->key ? nd->left : nd->right;
          if (tmp == NULL)
            break;
          nd = tmp;
        }
        if (nd->entry->key == key)
          nd->entry->value = value;
        else if (key < nd->entry->key) {
          nd->left = malloc(sizeof(Node));
          nd->left->entry = malloc(sizeof(Entry));
          nd->left->entry->key = key;
          nd->left->entry->value = value;
          nd->left->left = nd->left->right = NULL;
        } else {
          nd->right = malloc(sizeof(Node));
          nd->right->entry = malloc(sizeof(Entry));
          nd->right->entry->key = key;
          nd->right->entry->value = value;
          nd->right->left = nd->right->right = NULL;
        }
      }
    }
    
    void map_remove(Map *map, int key) {
      // Removes the key-value entry from the map with the given key
      // Assumption: The key-value pair in the map exists
      if (map->root->entry->key == key) {
        if (map->root->right == NULL) {
          Node *tmp = map->root->left;
          free(map->root->entry);
          free(map->root);
          map->root = tmp;
        } else if (map->root->left == NULL) {
          Node *tmp = map->root->right;
          free(map->root->entry);
          free(map->root);
          map->root = tmp;
        } else if (rand() % 2) {
          Node *parent = map->root, *child = parent->left;
          while (child->right != NULL) {
            parent = child;
            child = child->right;
          }
          if (parent->left == child)
            parent->left = child->left;
          else
            parent->right = child->left;
          map->root->entry->key = child->entry->key;
          map->root->entry->value = child->entry->value;
          free(child->entry);
          free(child);
        } else {
          Node *parent = map->root, *child = parent->right;
          while (child->left != NULL) {
            parent = child;
            child = child->left;
          }
          if (parent->left == child)
            parent->left = child->right;
          else
            parent->right = child->right;
          map->root->entry->key = child->entry->key;
          map->root->entry->value = child->entry->value;
          free(child->entry);
          free(child);
        }
      } else {
        Node *nd_parent = map->root, *nd = key < nd_parent->entry->key ? nd_parent->left : nd_parent->right;
        while (nd->entry->key != key) {
          nd_parent = nd;
          nd = key < nd->entry->key ? nd->left : nd->right;
        }
        if (nd->right == NULL) {
          if (nd_parent->left == nd)
            nd_parent->left = nd->left;
          else
            nd_parent->right = nd->left;
          free(nd->entry);
          free(nd);
        } else if (nd->left == NULL) {
          if (nd_parent->left == nd)
            nd_parent->left = nd->right;
          else
            nd_parent->right = nd->right;
          free(nd->entry);
          free(nd);
        } else if (rand() % 2) {
          Node *parent = nd, *child = parent->left;
          while (child->right != NULL) {
            parent = child;
            child = child->right;
          }
          if (parent->left == child)
            parent->left = child->left;
          else
            parent->right = child->left;
          nd->entry->key = child->entry->key;
          nd->entry->value = child->entry->value;
          free(child->entry);
          free(child);
        } else {
          Node *parent = nd, *child = parent->right;
          while (child->left != NULL) {
            parent = child;
            child = child->left;
          }
          if (parent->left == child)
            parent->left = child->right;
          else
            parent->right = child->right;
          nd->entry->key = child->entry->key;
          nd->entry->value = child->entry->value;
          free(child->entry);
          free(child);
        }
      }
    }
  • 11 #include <stddef.h>
    22
    33 typedef struct {
    4- // A key-value pair of integers
    4+ // Denotes a key-value pair of integers, e.g. 7 => 34
    55 int key, value;
    66 } Entry;
    77
    88 typedef struct node_t {
    9- // A node in a linked list - internal implementation of a Map
    10- Entry *entry; // The current entry in our map
    11- struct node_t *next; // The rest of our map
    9+ // A node of a binary (search) tree - the internal implementation of our map
    10+ Entry *entry;
    11+ struct node_t *left, *right;
    1212 } Node;
    1313
    1414 typedef struct {
    15- // Outer map wrapper (to hide interal implementation and
    16- // reserve `NULL` for representing an invalid map reference instead of an empty map)
    15+ // Our map datatype, implemented as a simple wrapper around our BST
    16+ // This allows us to insert elements to a map by object reference and
    17+ // reserves NULL for indicating an invalid reference to a Map (instead
    18+ // of an empty map)
    1717 Node *root;
    1818 } Map;
    1919
    2020 int map_get(const Map *map, int key) {
    21- // Returns the corresponding value to the key in the map
    22- // Assumption: the key is present in the map
    23- // (querying a nonexistent key yields undefined behavior)
    24- const Node *n = map->root;
    25- while (n->entry->key != key)
    26- n = n->next;
    27- return n->entry->value;
    23+ // Retrieves the corresponding value for a given key in a map
    24+ // Assumption: The given key-value pair in the map exists
    25+ const Node *nd = map->root;
    26+ while (nd->entry->key != key)
    27+ nd = key < nd->entry->key ? nd->left : nd->right;
    28+ return nd->entry->value;
    2828 }
    2929
    3030 void map_set(Map *map, int key, int value) {
    31- // Adds the key-value pair to the map if not present;
    32- // otherwise reassigns it at the corresponding entry
    33- Node *n = map->root;
    34- while (n != NULL && n->entry->key != key)
    35- n = n->next;
    36- if (n != NULL)
    37- n->entry->value = value;
    38- else {
    39- Node *tmp = map->root;
    32+ // Adds the key-value pair to the map if no entry with the given key exists;
    33+ // otherwise modifies the value of the entry with the given key to the given value
    34+ if (map->root == NULL) {
    4040 map->root = malloc(sizeof(Node));
    4141 map->root->entry = malloc(sizeof(Entry));
    4242 map->root->entry->key = key;
    4343 map->root->entry->value = value;
    44- map->root->next = tmp;
    39+ map->root->left = map->root->right = NULL;
    40+ } else {
    41+ Node *nd = map->root;
    42+ while (nd->entry->key != key) {
    43+ const Node *tmp = key < nd->entry->key ? nd->left : nd->right;
    44+ if (tmp == NULL)
    45+ break;
    46+ nd = tmp;
    47+ }
    48+ if (nd->entry->key == key)
    49+ nd->entry->value = value;
    50+ else if (key < nd->entry->key) {
    51+ nd->left = malloc(sizeof(Node));
    52+ nd->left->entry = malloc(sizeof(Entry));
    53+ nd->left->entry->key = key;
    54+ nd->left->entry->value = value;
    55+ nd->left->left = nd->left->right = NULL;
    56+ } else {
    57+ nd->right = malloc(sizeof(Node));
    58+ nd->right->entry = malloc(sizeof(Entry));
    59+ nd->right->entry->key = key;
    60+ nd->right->entry->value = value;
    61+ nd->right->left = nd->right->right = NULL;
    62+ }
    4545 }
    4646 }
    4747
    4848 void map_remove(Map *map, int key) {
    49- // Removes an entry from the map with the given key
    50- // Assumption: The given key-value pair exists
    51- // (attempting to delete a nonexistent entry yields undefined behavior)
    52- // This also implies that the map cannot be empty
    67+ // Removes the key-value entry from the map with the given key
    68+ // Assumption: The key-value pair in the map exists
    5353 if (map->root->entry->key == key) {
    54- Node *tmp = map->root->next;
    55- free(map->root->entry);
    56- free(map->root);
    57- map->root = tmp;
    70+ if (map->root->right == NULL) {
    71+ Node *tmp = map->root->left;
    5858 } else {
    59- Node *parent = map->root, *child = parent->next;
    60- while (child->next != NULL && child->entry->key != key) {
    61- parent = child;
    62- child = child->next;
    6363 }
    64- parent->next = child->next;
    65- free(child->entry);
    66- free(child);
    6767 }
    6868 }
Data Structures
Algorithms
Linked Lists
Lists
Maps

Map/Dictionary/Associative Array as a linked list of entries

Related article: Associative Array - Wikipedia

Many modern and/or popular programming languages such as Python, Java and C++ (and even some not-so-modern and/or popular languages such as Objective-C) provide a built-in datatype (either natively or in a built-in library) which maintains association between keys and values, commonly known as a map/dictionary and sometimes less known as an associative array (in languages such as PHP). However, for simpler and/or older languages such as C, such convenient data types do not exist. So, is it possible to define your own map/dictionary/assoc-array datatype in such languages? Of course - it all just boils down to data structures and algorithms (and perhaps some simple wrappers to hide your implementation from the user). Perhaps the easiest way to implement your own map data type is by using a linked list of key-value entries which will be demonstrated in this Kumite but the downside is that pretty much every operation you perform on your map (be it insertion, query or deletion) will have O(n) time complexity, i.e. the time taken to execute the operation varies directly with the number of entries in the map. The related Wikipedia article (link posted above) says that insertion should be an O(1) operation (since you could insert the key-value pair at the head of the list) but only if it is assumed that the key does not already exist in the map; otherwise, problems may arise if one attempts to iterate through the map.

This map implementation is seldomly used in real-world applications (and not even provided in built-in libraries of languages such as Java) due to its inefficiency and is only considered if the map is expected to be very small.

#include <stddef.h>

typedef struct {
  // A key-value pair of integers
  int key, value;
} Entry;

typedef struct node_t {
  // A node in a linked list - internal implementation of a Map
  Entry *entry; // The current entry in our map
  struct node_t *next; // The rest of our map
} Node;

typedef struct {
  // Outer map wrapper (to hide interal implementation and
  // reserve `NULL` for representing an invalid map reference instead of an empty map)
  Node *root;
} Map;

int map_get(const Map *map, int key) {
  // Returns the corresponding value to the key in the map
  // Assumption: the key is present in the map
  // (querying a nonexistent key yields undefined behavior)
  const Node *n = map->root;
  while (n->entry->key != key)
    n = n->next;
  return n->entry->value;
}

void map_set(Map *map, int key, int value) {
  // Adds the key-value pair to the map if not present;
  // otherwise reassigns it at the corresponding entry
  Node *n = map->root;
  while (n != NULL && n->entry->key != key)
    n = n->next;
  if (n != NULL)
    n->entry->value = value;
  else {
    Node *tmp = map->root;
    map->root = malloc(sizeof(Node));
    map->root->entry = malloc(sizeof(Entry));
    map->root->entry->key = key;
    map->root->entry->value = value;
    map->root->next = tmp;
  }
}

void map_remove(Map *map, int key) {
  // Removes an entry from the map with the given key
  // Assumption: The given key-value pair exists
  // (attempting to delete a nonexistent entry yields undefined behavior)
  // This also implies that the map cannot be empty
  if (map->root->entry->key == key) {
    Node *tmp = map->root->next;
    free(map->root->entry);
    free(map->root);
    map->root = tmp;
  } else {
    Node *parent = map->root, *child = parent->next;
    while (child->next != NULL && child->entry->key != key) {
      parent = child;
      child = child->next;
    }
    parent->next = child->next;
    free(child->entry);
    free(child);
  }
}

Alternative Function Syntax

Just discovered this by looking at a few Fortran code examples online, but it seems that in as early as Fortran 95 (perhaps even earlier!), functions can be defined in at least two ways.

The traditional way:

function FUNCTION_NAME(PARAMETER) ! or parameters
  PARAMETER_TYPE :: PARAMETER
  RETURN_TYPE :: FUNCTION_NAME ! or explicit result variable
  ! Function body
end function FUNCTION_NAME

And the second (perhaps more C-like) way:

RETURN_TYPE function FUNCTION_NAME(PARAMETER)
  PARAMETER_TYPE :: PARAMETER
  ! Function body
end function FUNCTION_NAME

Of course, with either syntax, it is possible to add modifiers such as pure, recursive or result(RESULT_VAR).

module Solution
  implicit none
contains
  integer pure function add(a, b) result(c)
    integer, intent(in) :: a, b
    c = a + b
  end function add
end module Solution

Type Initializers

When you define a derived data type in GNU Fortran, you are automatically given a type initializer which allows you to initialize an instance of your derived data type in one go. One can think of a type initializer as a primitive type of constructor. However, custom-defined constructors weren't available until Fortran 2003 so it may not be available in GNU Fortran (which is an extension of the Fortran 95 standard).

module Solution
  implicit none
  type Vec3D ! A three-dimensional vector
    integer :: x, y, z
  end type Vec3D
  type(Vec3D) :: v = Vec3D(1, 2, 3) ! Using the type initializer provided by Fortran
end module Solution

Dynamic Memory Allocation by using C library malloc() function

It is possible to allocate memory dynamically in NASM (obviously, otherwise how would it be possible in C and other higher-level languages?) and the easiest way to do it is probably by relying on the C library function malloc().

global one_two_three
extern malloc ; C library function malloc()
section .text
one_two_three:
  mov rdi, 12 ; size_t bytes_required = 3 * sizeof(int) == 12 (because sizeof(int) == 4 on CW)
  call malloc ; int *result = malloc(bytes_required)
  mov dword [rax], 1 ; result[0] = 1 (`dword` means "double word" where 1 word = 2 bytes)
  mov dword [rax + 4], 2 ; result[1] = 2
  mov dword [rax + 8], 3 ; result[2] = 3
  ret ; return result
Advanced Language Features
Fundamentals

Pointers

Fortran has basic support for pointers. A pointer is a rather primitive type of reference - it is essentially a memory address (associated with a given type) which is said to "point to" the data it is referencing. Unlike C/C++/ObjC, Fortran does not support pointers to pointers, function pointers, arrays of pointers or pointer arithmetic but it is still sufficient to allow us to define simple recursive datatypes such as linked lists or binary trees.

To declare a pointer:

integer, pointer :: p ! `p` is a non-associated integer pointer

To associate a pointer to a target:

! The `target` annotation is required for a pointer to point to it
! Otherwise, `n` is just another ordinary integer
integer, target :: n = 42
integer, pointer :: p => n ! `p` is now associated with `n`

To dereference a pointer:

integer, target :: n = 42
integer, pointer :: p => n ! `p` points to `n`
p = 100 ! `p` is automatically dereferenced and its target `n` set to 100

To associate a pointer to another target:

integer, target :: m = 100, n = 42
integer, pointer :: p => n ! `p` points to `n`
p => m ! `p` now points to `m` instead

To make two (or more) pointers point to the same target:

integer, target :: n = 42
integer, pointer :: p1, p2
p1 => n ! `p1` points to `n`
p2 => p1 ! `p2` now points to the TARGET of `p1` which is `n`
! REMEMBER: `p2` does NOT point to `p1` - pointers
! to pointers are not permitted in Fortran

To define a null pointer (i.e. one that does not reference any data):

integer, pointer :: p => null()

To allocate memory for a pointer instead of pointing it to a pre-existing target:

integer, pointer :: p
allocate(p) ! Allocate memory under pointer (just sufficient for one integer)
! Do something with `p`.  Make sure `p` doesn't point to anything else
! before it is deallocated (otherwise a memory leak will occur)!
deallocate(p) ! Free the memory under the pointer

To check whether a pointer is associated with a target:

associated(p) ! Checks whether `p` is associated with a target
! Evaluates to the corresponding logical value
! (.true. if associated, .false. otherwise)

The main code example in this Kumite involves derived data types.

module Pointers
  implicit none
  type Node ! A node of a singly linked list
    integer :: data
    type(Node), pointer :: next
  end type Node
end module Pointers

Operator Overloading

In Fortran, operator overloading is done via interfacing. The syntax is almost identical to overloading procedures except the name of the alias is replaced by operator (OPERATOR) (where OPERATOR is a placeholder for the actual operator).

Unlike some programming languages such as Haskell, operators to be overloaded cannot contain arbitrary symbols (or a sequence thereof). Only the following operators and types of operators can be overloaded/defined:

  • Symbol / symbol combinations already defined as operators in Fortran (e.g. +, -, *, /, ==, /=, etc.)
  • .OPERATOR_NAME. where OPERATOR_NAME may only contain English letters (not even numbers, not even underscore)

Operators can be unary or binary or both (of the form OPERATOR OPERAND or OPERAND_1 OPERATOR OPERAND_2) depending on whether the function(s) implementing it accept one or two arguments. However, for operators intrinsic to Fortran (such as * or /), the functions implemeting their overloads may only accept as many arguments as they were originally defined (e.g. you cannot overload * to accept only one operand).

Note that operators must be pure in Fortran, i.e. they are not permitted to mutate their operands. Therefore, functions implementing the overloaded operator must be declared pure (or if not, at least all input parameters must be declared intent(in)).

module OperatorOverloading
  implicit none
  private :: realRecip, cmplxRecip ! Hide implementation details of overloaded operator
  interface operator (.recip.) ! Operator for finding the reciprocal
  ! (i.e. multiplicative inverse) of a number
    module procedure realRecip, cmplxRecip
  end interface
contains
  pure function realRecip(x)
    real, intent(in) :: x
    real :: realRecip
    realRecip = 1.0 / x
  end function realRecip
  pure function cmplxRecip(z)
    complex, intent(in) :: z
    complex :: cmplxRecip
    cmplxRecip = cmplx(1, 0) / z
  end function cmplxRecip
end module OperatorOverloading

Just a simple C function void say_hello() written in NASM v2.11.x which prints Hello World! to the console.

global say_hello
section .text
say_hello:
  mov eax, 4 ; system call for write (for Linux)
  mov ebx, 1 ; file handle 1 is STDOUT
  mov ecx, message ; memory address of output buffer
  mov edx, msgLen ; size of output buffer in bytes
  int 0x80 ; invoke OS to do the write
  ret ; Return to the caller

section .data ; Read-only data
message db "Hello World!", 10 ; message = "Hello World!\n"
msgLen equ $-message ; msgLen = strlen(message)
Interfaces
Basic Language Features
Object-oriented Programming
Fundamentals

Interfacing

In Fortran modules, it is possible to "overload" a prodecure with several variants, each accepting different types/numbers of arguments through interfacing. An interface is essentially a named alias to one or more defined procedures. For example, when we first introduced functions, our add function was only capable of accepting two default (32-bit) integers and compute its sum (as a 32-bit integer). What if we wanted our add function to work on reals as well? Or complex numbers? In that case, all we have to do is to define three separate functions and implement them accordingly - let's call them addIntegers, addReals and addComplexNumbers. After that, we alias them all under the same name add through interfacing which is achieved by using the interface keyword and has the following syntax (ALL_CAPS denote placeholders):

interface ALIAS_NAME
  module procedure PROC_1, PROC_2, ..., PROC_N
end interface ALIAS_NAME

The interface is always placed at the top section of the module, i.e. before the contains keyword:

module InterfacingExample
  implicit none
  ! Our interface
  interface add
    ! The `addIntegers`, `addReals` and `addComplexNumbers`
    ! functions should all be aliased number the name `add`
    module procedure addIntegers, addReals, addComplexNumbers
  end interface add
contains
  pure function addIntegers(a, b) result(c)
    integer, intent(in) :: a, b
    integer :: c
    c = a + b
  end function addIntegers
  pure function addReals(a, b) result(c)
    real, intent(in) :: a, b
    real :: c
    c = a + b
  end function addReals
  pure function addComplexNumbers(a, b) result(c)
    complex, intent(in) :: a, b
    complex :: c
    c = a + b
  end function addComplexNumbers
end module InterfacingExample

Now let's test it in our program:

program Main
  use InterfacingExample
  implicit none
  print *, add(1, 2) ! > 3 (perhaps with padding)
  print *, add(3.5, 4.5) ! > 8.0 (perhaps with padding)
  print *, add(cmplx(3, -4), cmplx(2, 1)) ! > (5.0, -3.0) (perhaps with padding)
end program Main

Our alias works as expected. However, at this point, you might be wondering if the functions are still accessible through their original names (e.g. addIntegers). If that is the case then your doubts are well-founded - the functions are still accessible through their original names (which may not be desirable). To hide the original names of the functions and expose only the alias, simply declare the original function names as private the same way you would variables/constants:

module InterfacingExample
  implicit none
  private :: addIntegers, addReals, addComplexNumbers
  ! Our interface
  interface add
    ! The `addIntegers`, `addReals` and `addComplexNumbers`
    ! functions should all be aliased number the name `add`
    module procedure addIntegers, addReals, addComplexNumbers
  end interface add
contains
  pure function addIntegers(a, b) result(c)
    integer, intent(in) :: a, b
    integer :: c
    c = a + b
  end function addIntegers
  pure function addReals(a, b) result(c)
    real, intent(in) :: a, b
    real :: c
    c = a + b
  end function addReals
  pure function addComplexNumbers(a, b) result(c)
    complex, intent(in) :: a, b
    complex :: c
    c = a + b
  end function addComplexNumbers
end module InterfacingExample
module InterfacingExample
  implicit none
  private :: addIntegers, addReals, addComplexNumbers
  ! Our interface
  interface add
    ! The `addIntegers`, `addReals` and `addComplexNumbers`
    ! functions should all be aliased number the name `add`
    module procedure addIntegers, addReals, addComplexNumbers
  end interface add
contains
  pure function addIntegers(a, b) result(c)
    integer, intent(in) :: a, b
    integer :: c
    c = a + b
  end function addIntegers
  pure function addReals(a, b) result(c)
    real, intent(in) :: a, b
    real :: c
    c = a + b
  end function addReals
  pure function addComplexNumbers(a, b) result(c)
    complex, intent(in) :: a, b
    complex :: c
    c = a + b
  end function addComplexNumbers
end module InterfacingExample
Functions
Control Flow
Basic Language Features
Fundamentals
Recursion
Algorithms
Computability Theory
Theoretical Computer Science

Fortran Procedures - Subroutines

In a previous Kumite, I mentioned that there are two types of procedures in Fortran:

  1. Functions - These evaluate to a given value which is returned to the caller (for further computation by other parts of the program, for example)
  2. Subroutines - These only perform a set of actions and do not evaluate to any value

This Kumite aims to demonstrate how to define and invoke a Fortran subroutine.

A Fortran subroutine is in fact declared/defined in the same way as a function except the function keyword (in both the first and last lines) are replaced with subroutine. Pretty much everything else that holds for functions also holds for subroutines, with the exception of a lack of return value (and therefore result(<res_var>) annotation is not permitted). You can even declare a subroutine as recursive (and/or even pure)!

module Solution
  implicit none
contains
  recursive subroutine print1ToN(n)
    integer :: n
    if (n > 0) then
      call print1ToN(n - 1) ! NOTE: See explanation below code example
      print "(I0)", n
    end if
  end subroutine print1ToN
end module Solution

When invoking a subroutine, the syntax is slightly different - you have to add the call keyword in front of the subroutine name, like such:

program TestCases
  use Solution
  implicit none
  call print1ToN(10)
  ! > 1
  ! > 2
  ! > ... (you get the idea ;) )
  ! > 10
end program TestCases
module Solution
  implicit none
contains
  recursive subroutine print1ToN(n)
    integer :: n
    if (n > 0) then
      call print1ToN(n - 1) ! NOTE: See explanation below code example
      print "(I0)", n
    end if
  end subroutine print1ToN
end module Solution
Functions
Control Flow
Basic Language Features
Fundamentals
Recursion
Algorithms
Computability Theory
Theoretical Computer Science

Fortran Procedures - Recursive Functions

In my last Kumite you learned how to declare and define a function in Fortran. If you were interested in it, you may have done some experimentation on defining a few of your own. Some of you might even have attempted to define a recursive function in Fortran using the syntax shown in the last Kumite. For example, you might have tried to find the sum of the first n positive integers recursively:

module Solution
  implicit none
contains
  function sum1ToN(n) result(sum)
    integer :: n, sum
    if (n <= 0) then
      sum = 0
    else
      sum = n + sum1ToN(n - 1)
    end if
  end function sum1ToN
end module Solution

However, if you attempted to compile and execute this module (with an accompanying program), you would've seen an error message similar to the following: Error: Function 'sum1ton' at (1) cannot be called recursively, as it is not RECURSIVE. In fact, you can define a recursive function in Fortran, but you need to add the recursive modifier to the beginning of your function declaration in order to do so:

module Solution
  implicit none
contains
  recursive function sum1ToN(n) result(sum)
    integer :: n, sum
    if (n <= 0) then
      sum = 0
    else
      sum = n + sum1ToN(n - 1)
    end if
  end function sum1ToN
end module Solution

Now, when we define our program using this module and test our sum1ToN function, everything works as expected:

program TestCases
    use Solution
    implicit none
    print "(I0)", sum1ToN(10) ! > 55
end program TestCases

The recursive keyword can also be used in conjunction with the pure keyword to specify a pure function that has the capacity to invoke itself recursively.

module Solution
  implicit none
contains
  pure recursive function sum1ToN(n) result(sum)
    integer, intent(in) :: n
    integer :: sum
    if (n <= 0) then
      sum = 0
    else
      sum = n + sum1ToN(n - 1)
    end if
  end function sum1ToN
end module Solution
module Solution
  implicit none
contains
  pure recursive function sum1ToN(n) result(sum)
    integer, intent(in) :: n
    integer :: sum
    if (n <= 0) then
      sum = 0
    else
      sum = n + sum1ToN(n - 1)
    end if
  end function sum1ToN
end module Solution
Functions
Control Flow
Basic Language Features
Fundamentals

Fortran Procedures - Functions, Pass By Reference and Purity

In Fortran it is possible to define reusable sets of instructions that either perform a given action / actions or evaluate to a certain value (or do both) which are called procedures. There are two main types of procedures:

  1. Functions - These eventually evaluate to a certain value which can then be used by the caller. They can be pure (i.e. do not cause any side effects, more on that later) or impure (causing side effects and/or modifying the state of the program in the process).
  2. Subroutines - These only perform a given set of actions and do not evaluate to any value. Subroutines may also be pure/impure.

This Kumite demonstrates how to define and use a function.

A function (and in fact any procedure) can be defined in any module/program (it does not matter which, the declaration syntax is identical in both cases) by placing them at the bottom half of the module/procedure. To do that, the given program/module has to be split into exactly two sections using the contains statement/keyword in between. The top section contains all of the variable declarations and statements of the program/module, while the bottom section contains all of the procedure definitions:

module FunctionExample
  implicit none
  ! Top section - contains all variable declarations/definitions
contains
  ! Bottom section - contains all function and subroutine
  ! (i.e. procedure) definitions
end module FunctionExample

Then, under the contains statement, we declare and define our function using a function declaration of the form function <fn_name>(<var_1>, <var_2>, ..., <var_n>). We end our function definition using end function <fn_name> and our function body goes between these two lines. For example, if we want to declare and define an add function that adds two integers, our module would look like this:

module FunctionExample
  implicit none
  ! Variable declarations
contains
  function add(a, b)
    ! TODO
  end function add
end module FunctionExample

If you've paid any amount of attention to my previous Kumite then it should've occurred to you by now that Fortran is a statically typed language, i.e. each variable has a fixed type that cannot be changed at runtime. However, our function declaration shown above didn't assign any types to the parameters a and b (which we want to be integers). So, how to declare their types? Fortunately, it's very simple and straightforward - just declare them at the top of the function body like you would global variables at the start of a program/module!

module FunctionExample
  implicit none
  ! Variable declarations
contains
  function add(a, b)
    integer :: a, b
  end function add
end module FunctionExample

In our add function, we would like to compute the sum of the integers a and b and return the corresponding integer value to the caller. Unfortunately, there is no return keyword in Fortran so how is it done? In Fortran we must store the result we want to return to the caller in a variable with an identical name to the function name which is add in this case. Our result is anticipated to be an integer so we need to declare the type of add as well:

module FunctionExample
  implicit none
  ! Variable declarations
contains
  function add(a, b)
    integer :: a, b
    integer :: add
  end function add
end module FunctionExample

Then, we simply assign the result of adding a and b to add:

module FunctionExample
  implicit none
  ! Variable declarations
contains
  function add(a, b)
    integer :: a, b
    integer :: add
    add = a + b
  end function add
end module FunctionExample

Now our function declaration/definition is complete and we can use it in our program as desired.

program MyProgram
  use FunctionExample
  implicit none
  print "(I0)", add(3, 5) ! > 8
end program MyProgram

Using a custom variable name for the returned result

What if you don't want to use the function name to store the returned result? For example, instead of add = a + b, you want to do c = a + b and have c store the result to be returned. All you have to do is modify the function declaration to function <fn_name>(<var_1>, <var_2>, ..., <var_n>) result(<result_var>) and subsequently the affected variable declarations:

module FunctionExample
  implicit none
  ! Variable declarations
contains
  function add(a, b) result(c)
    integer :: a, b
    integer :: c
    c = a + b
  end function add
end module FunctionExample

Procedure arguments in Fortran are passed by variable reference, not by value or object reference

Unlike many modern programming languages such as C, Java or Python, procedure (and hence function) arguments in Fortran are passed by variable reference. This means that if you reassign the values of arguments within your function, the passed in variable itself will be affected.

module FunctionExample
  implicit none
contains
  function add(a, b) result(c)
    integer :: a, b
    integer :: c
    a = a + b ! Argument `a` is assigned the value of the result
    c = a ! Result variable `c` assigned the new value of `a`
  end function add
end module FunctionExample
program MyProgram
  use FunctionExample
  implicit none
  integer :: m = 3, n = 5

  ! > m = 3, n = 5
  print "(A4, I0, A6, I0)", "m = ", m, ", n = ", n

  ! > add(m, n) = 8
  print "(A12, I0)", "add(m, n) = ", add(m, n)

  ! This segfaults
  ! print "(I0)", add(3, 5)

  ! > m = 8, n = 5
  print "(A4, I0, A6, I0)", "m = ", m, ", n = ", n
end program MyProgram

Therefore, in Fortran, one must be careful not to assign any new values to existing parameters (unless there is a good reason to do so deliberately).

Pure Functions

A pure function is one that does not mutate its input in any way and does not depend on and/or change the state of the program when it is executed/evaluated. Due to Fortran's pass-by-variable-reference, it is easy to make a mistake and mutate the value of argument variables passed in and therefore violate this rule. Fortunately, Fortran has native syntactical support for these types of functions - simply prepend the function declaration with the pure keyword: pure function <fn_name>(<v1>, <v2>, ..., <vn>) result(<rv>).

By explicitly declaring your function as pure, Fortran enforces compile-time restrictions on the type declarations of all the parameters to ensure that all parameters are declared in a way that their value cannot be reassigned. This means that we need to modify the parameter declarations by adding a comma, followed by intent(in) after the type name (and before the ::) - this tells the Fortran compiler that the values of the parameters are read-only:

module FunctionExample
  implicit none
contains
  pure function add(a, b) result(c)
    integer, intent(in) :: a, b
    integer :: c
    c = a + b
  end function add
end module FunctionExample

Now we can use the add function with the guarantee that it will never mutate its inputs:

program MyProgram
  use FunctionExample
  implicit none
  integer :: m = 3, n = 5
  print "(I0)", add(m, n) ! > 8
  print "(I0)", add(3, 5) ! Works - no segfault :)
  print "(I0)", m ! > 3
  print "(I0)", n ! > 5
end program MyProgram
module FunctionExample
  implicit none
contains
  pure function add(a, b) result(c)
    integer, intent(in) :: a, b
    integer :: c
    c = a + b
  end function add
end module FunctionExample

Just a quick test to see how Preloaded works with GNU Fortran on Codewars ...

module Solution
  use Preloaded
  implicit none
  integer :: n = answer - 42 ! n = 0
end module Solution
Loading more items...