Poking Around SML

2026-07-18

I was reading how the grocery store H-E-B actually uses Haskell of all things in production systems and it sent me looking through my bookshelves to dust off my copy of Elements of ML Programming. Haskell still seems a little too exotic in its syntax (too reminiscent of the type craziness I remember in old Scala 2) and the on-ramp to getting started always seems a little off putting. SML though feels downright tiny and while there isn't much in the way of third-party code to use that doesn't matter if I want to try building something from scratch.

Similar in spirit to when I tried implementing a linear congruence generator using Forth, let's try something similar with SML. I'll be using a freshly downloaded copy of Standard ML of New Jersey [Version 110.99.9; 64-bit; November 4, 2025]. It was a breeze to download and install so I can dive right in.

The first thing to note in trying to wrangle an implementation of SHA-1 out of ~~stone knives and bear skins~~ what exists in the SML standard library is the numeric tower and means of addressing bits and bytes directly. SML integers are a bit more flexible than what I'm going to need here and because I'm on a recent version and a modern machine I get (obviously) different answers to a few machine specific questions about their size (compared to Elements):

- Int.maxInt ;
val it = SOME 4611686018427387903 : int option

- LargeInt.maxInt ;
val it = NONE : IntInf.int option

So instead I am going to use "word" from the basis library, which despite the funny syntax and apparently undeclared library (or I guess it is a structure?), doesn't require any kind of opening declaration:

- Word32.+ (0wxFFFFFFFE, 0w1) ;
val it = 0wxFFFFFFFF : Word32.word
-
-Word32.+ (0wxFFFFFFFF, 0w1) ; (* 32 bit word wrap *)
val it = 0wx0 : Word32.word

It isn't really too weird to prefix the word operators with their structure name after rolling my own lousy namespacing with common lisp before. I don't think SML allows for operator overloading and I don't miss it yet. 0w is the prefix for "word" and then 0wx is the prefix for hexadecimal. Let's write a "circular left shift" function (described on page 7 of FIPS-180-1). I'm terribly rusty with my bit shifting so I wrote this python to check against:

>>> MASK_32 = 0xFFFFFFFF

>>> def left_shift(x, n):
...     return (x << n) & MASK_32

>>> def to_bits(x):
...     return format(x, '032b')

>>> x = 0b1000_0000_0000_0000_0000_0000_0000_0001

>>> to_bits(left_shift(x, 1))
'00000000000000000000000000000010'

>>> def circular_left_shift(x, n):
...     n &= 31
...     x &= MASK_32
...     return ((x << n) | (x >> (32 - n))) & MASK_32

>>> to_bits(circular_left_shift(x, 1))
'00000000000000000000000000000011'

Either I haven't found it or SML doesn't have a binary format for words so the above in hex is:

>>> 0x8000_0001 == 0b1000_0000_0000_0000_0000_0000_0000_0001
True

A pretty direct translation then seems to be:

fun circular_left_shift (x, n) =
    let
	val left_part = Word32.<< (x, n)
	val right_part = Word32.>> (x, 0w32 - n)
    in
	Word32.orb (left_part, right_part)
    end

orb is bitwise OR, just one more quirk of the basis library naming scheme. And there's no need to mask because I'm dealing in Word32. I haven't figured out a better way to print the numbers but it is easy enough to verify against the above python:

- circular_left_shift (0wx0001, 0w1) ;
val it = 0wx2 : Word32.word

- circular_left_shift (0wx80000001, 0w1) ;
val it = 0wx3 : Word32.word

The only power function I've seen is in the Math module and has the domain real * real which seems like a fun excuse to write a recusive function:

fun power_two 0 = 1
  | power_two n = 2 * power_two (n - 1)

- power_two 3 ;
val it = 8 : int

- 2 * 2 * 2 ;
val it = 8 : int

- power_two 8 ;
val it = 256 : int

SHA-1 repeatedly deals in 32-bit words so I want a way to get at the 32-bit word of a given index position in an array:

fun word_32_at (arr, i) =
    let
	fun the_byte_after j =
	    let
		val the_byte : Word8.word = Word8Array.sub (arr, i + j)
		(* I don't think there is a path from Word8.word to Word32?? *)
		val as_int : int = Word8.toInt the_byte
	    in
		Word32.fromInt as_int
	    end
	val piece_0 = Word32.<< ((the_byte_after 0), 0w24)
	val piece_1 = Word32.<< ((the_byte_after 1), 0w16)
	val piece_2 = Word32.<< ((the_byte_after 2), 0w8)
	val piece_3 = the_byte_after 3
    in
	Word32.orb (piece_0, Word32.orb (piece_1, Word32.orb (piece_2, piece_3)))
    end

The placeholder values and nesting of Word32.orb makes me itch to try code golfing this a bit but I'm doing my best to resist that urge because I have no idea what I'm doing in SML yet!

Where I did struggle was in naming a few of the functions and decomposing parts so as to not write one single massive function. Partly this is a result of how the specification document is written and you can probably see where I struggled to find different names for "words" given the use of the Basis library:

fun compute_words (arr, base) =
    let
	val out_arr = Array.array (80, 0w0 : Word32.word) (* 80 slots of zeroes *)

	(* Divide M[i] into 16 words W[0], W[1], ..., W[15] where W[0] is the left-most word *)
	fun divide_word i =
	    if i >= 16 then ()	(* funny way of side effecting only *)
	    else
		let
		    val the_word = word_32_at (arr, base + i * 4)
		in
		    Array.update (out_arr, i, the_word) ;
		    divide_word (i + 1)
		end

	(* For t = 16 to 79 let W[t] = circular_left_shift by 1 (W[t-3] XOR W[t-8] XOR W[t-14] XOR W[t-16]) *)
	fun scramble_rest i =
	    if i >= 80 then ()	(* more side effects *)
	    else
		let
		    val w_1 = Array.sub (out_arr, i - 3)
		    val w_2 = Array.sub (out_arr, i - 8)
		    val w_3 = Array.sub (out_arr, i - 14)
		    val w_4 = Array.sub (out_arr, i - 16)
		    val ored_w = Word32.xorb (Word32.xorb (w_1, w_2), Word32.xorb (w_3, w_4))
		    val rotated = circular_left_shift(ored_w, 0w1)
		in
		    Array.update (out_arr, i, rotated) ;
		    scramble_rest (i + 1)
		end
    in
	divide_word 0 ;			(* firsts loop preps 16 *)
	scramble_rest 16 ;		(* second loop 16-79 *)
	out_arr				(* returned mangled array *)
    end

and then:

fun process_block ((h_0, h_1, h_2, h_3, h_4), arr, base) =
    let
	val word_arr = compute_words (arr, base)

	fun round_f_and_k (i, b, c, d) =
	    (*    f[t](B,C,D) = (B ∧ C) ∨ (~B ∧ D)                   ( 0 ≤ t ≤ 19)    *)
	    if i < 20 then
		let val f = Word32.orb (Word32.andb (b, c), Word32.andb (Word32.notb b, d))
		in
		    (f, k1)	(* funky way of returning a tuple *)
		end
	    (*    f[t](B,C,D) = B XOR C XOR D                        (20 ≤ t ≤ 39)   *)
	    else if i < 40 then
		let val f = Word32.xorb (Word32.xorb (b, c), d)
		in
		    (f, k2)
		end
	    (*    f[t](B,C,D) = (B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D)          (40 ≤ t ≤ 59)   *)
	    else if i < 60 then
		let val f = Word32.orb (Word32.orb (Word32.andb (b, c), Word32.andb (b, d)), Word32.andb (c, d))
		in
		    (f, k3)
		end
	    (*    f[t](B,C,D) = B XOR C XOR D                        (60 ≤ t ≤ 79)   *)
	    else
		let val f = Word32.xorb (Word32.xorb (b, c), d)
		in
		    (f, k4)
		end

	fun rounds (i, a, b, c, d, e) =
	    if i >= 80 then (a, b, c, d, e)
	    else
		let
		    (*    TEMP = S_5(A) + f[t](B,C,D) + E + W[t] + K[t]     *)
		    val (f, k) = round_f_and_k (i, b, c, d)

		    (* this looks comically bad... *)
		    val temp = Word32.+ (Word32.+
					 (Word32.+
					  (Word32.+
					   (circular_left_shift (a, 0w5), f),
					   e),
					  k),
					 Array.sub (word_arr, i))
		    val new_e = d
		    val new_d = c
		    val new_c = circular_left_shift(b, 0w30)
		    val new_b = a
		    val new_a = temp
		in
		    rounds (i + 1, new_a, new_b, new_c, new_d, new_e)
		end

	(* known initial state kicks it off *)
	val (a, b, c, d, e) = rounds (0, h_0, h_1, h_2, h_3, h_4)
    in
	(* and the modified state is added back to the initial state *)
	(Word32.+ (h_0, a),
	 Word32.+ (h_1, b),
	 Word32.+ (h_2, c),
	 Word32.+ (h_3, d),
	 Word32.+ (h_4, e))
    end

are no doubt the gnarliest parts but are basically me waffling on how to break down page 10, steps a, b, c, d, and e. Which are written in all of 7 lines of text (with back references to page 5 for the "rounds").

The remaining piece then is section 4 of the reference document, message padding. It is pretty mechanical and a little reminisicent of when I implemented the drunken bishop algorithm. Doing some reading on "why those specific initialized values" is interesting but also leaves me feeling a bit like "if you say so…".

Producing the actual hash function is mostly padding and modulo arithmetic which I find distinctly not fun. The examples found in the appendix are very much appreciated though in trying to wrest the following from the machine:

fun hash (msg : Word8Vector.vector) =
    let
	val byte_length = Word8Vector.length msg
	val bit_length = byte_length * 8

	(* a "1" followed by m "0"s followed by a 64-bit integer are
	   appended to the end of the message to produce padded
	   message of length 512 x n *)

	(* I do not love modulo arithmetic *)
	val zeroes = (56 - (byte_length + 1) mod 64) mod 64
	val total = byte_length + 1 + zeroes + 8 (* 0x80 byte, zeroes, 8 byte length *)

	val mutable_arr = Word8Array.array (total, 0w0)

	(* copyVec to copy the immutable msg vector rather than copy for mutable array *)
	val () = Word8Array.copyVec {src = msg, dst = mutable_arr, di = 0}

	val () = Word8Array.update (mutable_arr, byte_length, 0wx80)

	fun length_byte j =
	    Word8.fromInt ((bit_length div power_two (8 * (7 - j))) mod 256)

	fun put_length j =
	    if j > 7 then ()
	    else
		let in
		    Word8Array.update (mutable_arr, total - 8 + j, length_byte j);
		    put_length (j + 1)
		end

	val () = put_length 0

	val num_blocks = total div 64
	val initial_state = (0wx67452301, (* more magic number c.f. page 10 *)
			     0wxEFCDAB89,
			     0wx98BADCFE,
			     0wx10325476,
			     0wxC3D2E1F0)

	fun loop (i, state) =
	    if i >= num_blocks then state
	    else loop (i + 1, process_block (state, mutable_arr, i * 64))

	val (h_0, h_1, h_2, h_3, h_4) = loop (0, initial_state)

	fun byte_of (h, shift) =
	    Word8.fromInt (Word32.toInt (Word32.andb (Word32.>> (h, shift), 0wxFF)))

	fun word_bytes (h : Word32.word) : Word8.word list =
	    [byte_of (h, 0w24), byte_of (h, 0w16), byte_of (h, 0w8), byte_of (h, 0w0)]

    in
	Word8Vector.fromList (  word_bytes h_0        (* funky list concat syntax *)
				@ word_bytes h_1
				@ word_bytes h_2
				@ word_bytes h_3
				@ word_bytes h_4)
    end

I will admit to nearly givng up several times due to off by one errors. I also think this is probably a great candidate for reflection if I ever learn more about SML. As it stands it felt like I was using mutability escape hatches and bashing things into something roughly procedural-shaped. That being said, it does feel like a bit of a testament to SML's usability that I was at least able to muddle through. While pure functions and better controlling side effects might be the truly enlightened thing to do it was at least possible for me to get things done here.

A final helper function makes it easy to compare this implementation with the examples cited in the appendix:

fun to_hex vec =
    let
	val digits = "0123456789ABCDEF"
	fun hex b =
	    let
		val n = Word8.toInt b
		val high = String.sub (digits, n div 16)
		val low = String.sub (digits, n mod 16)
	    in
		String.implode [high, low] (* very good name for str.join type function *)
	    end
	val byte_list = Word8Vector.foldr (fn (b, acc) => b :: acc) [] vec
    in
	String.concat (map hex byte_list)
    end
end

With a cheeky foldr and a lambda, for some string joinery the final proof that it works looks like this (I'll forgive you if you're a little let down):

- hash (Byte.stringToBytes "abc") ;
val it = - : Word8Vector.vector
-
- to_hex ( hash (Byte.stringToBytes "abc") ) ;
val it = "A9993E364706816ABA3E25717850C26C9CD0D89D" : string

Thoughts

I am absolutely shocked at how readable I found FIPS PUB 180-1. I found it easier to understand than the wikipedia entry describing SHA-1 and it is only 5 pages long (not including the test cases!). I'm actually tempted now to browse around more of these documents to see what else NIST has that might be interesting to read.

On the subject of SML, I'm having a lot of fun. I need to understand better the use of semicolons because I basically didn't use them except in a few cases where I ended up calling multiple functions in a row (after the compiler yelled at me that "operator is not a function". The correct line was linked though so it wasn't too bad I guess). The error messages from SML/NJ don't thrill me but all of my mistakes so far were comprehensible given an error like:

- Math.pow(2, 3) ;
stdIn:42.1-42.15 Error: operator and operand do not agree [overload - bad instantiation]
  operator domain: real * real
  operand:         'Z[INT] * 'Y[INT]
  in expression:
    Math.pow (2,3)

I'm not actually sure what the machinery driving sml is (interpreter? compiler?) but it is so fast that I don't care. The type inference is deep enough that I'm pretty sure all of my annotations were only for my own benefit, which is leaps and bounds ahead of python where I add annotations and there is no guarantee they are even correct. I feel like I need a test harness but suspect, based on the slim standard library and relative paucity of third party libraries, it will be a case where a test framework would only hold you back and you just roll your own.

I found a SHA-1 library on github and will be reading it with interest now that I've got a bit of a handle on the mechanics of the thing. Even at a glance I've got the feeling that mine looks incredibly clumsy (not unexpectedly). It is a really fun language so far though! I think next thing is to figure out the correct declaration for a structure to hold/namespace this and maybe a signature for visibility? Also, having discovered the possibility of creating infix operators I wonder if I can't clean up some of the twistier bit shifting call sites.