I had fun poking around SML so I thought I'd keep it up. I thought it might be revealing to try some rudimentary parsing over strings to get a sense of what the language makes easy or not so easy.
I know that the ML family of languages is supposed to be great for writing compilers and interpreters but I'm not so ambitious that I plan on jumping into anything so advanced just yet. Instead I thought I'd set my sights a little lower and try turning some typical structured data into parsed data structures. For want of a better example let's consider how to parse something like:
POST /users HTTP/1.1
Host: example.com
Content-Type: application/x-www-form-urlencoded
Content-Length: 49
name=FirstName+LastName&email=bsmth%40example.comSince this is only for my own edification and entertainment I'm going to aim to turn the above into something like this:
type request = {
path : string,
headers : (string * string) list
}I'm going to ignore the actual request body, figuring if I can manage the above it is probably more of the same. While I did go searching for a complete specification on HTTP requests it is a bit much for my modest goals so I'm also referencing this MDN page.
The first order of business seems then to be splitting out the
request body (which we will ignore) from the data we care about in
the form of control data and header fields. I've been calling this
control data and header fields a "preamble", I'm not sure if there
is a more typical name for it but it is a pretty simple job to
identify it. It is everything that precedes ␍␊␍␊
fun extract_preamble substr =
let
val (preamble, rest) = Substring.position "\r\n\r\n" substr
in
if Substring.isEmpty rest
then
NONE
else
SOME preamble
end
I've heard enough about the wonderful simplicity of option types in
ML languages that I can't say no to my first opportunity to use
them. Besides the funny all caps typing (which has tripped me up
multiple times already when I mistakenly type None) they aren't
especially interesting beyond being straighforward to use without
any real ceremony involved. One quirk to point out, there are
remarkably few operations on the String type that I found use for
and instead ended up reaching for the Substring type. I haven't dug
too deep into the what and why of this decision but guess it might
be akin to a stringview or slice in other languages. Producing a
Substring from a String is as simple as: Substring.full "some
string".
With just the control data and header fields in hand I want to switch to per-line processing. That calls for splitting out the present substring into a list of substrings:
fun split_crlf_lines substr =
if Substring.isEmpty substr
then
[]
else
let
val (line, rest) = Substring.position "\r\n" substr
in
(* cons onto the recursive call after stripping \r\n *)
(* basis library says of: triml k s
If k is greater than the size of the substring, an empty substring is returned *)
line :: split_crlf_lines (Substring.triml 2 rest)
end
The way Substring.position works is that it it chops in
two the string up to the point of the searched string, without
including it, basically:
- val (first, second) = Substring.position "^" (Substring.full "split this in two^based on some character, say the caret ^") ;
val it = (-,-) : substring * substring
- Substring.string first ;
val it = "split this in two" : string
- Substring.string second ;
val it = "^based on some character, say the caret ^" : string
This nearly as simple a recursive case as they come but I really
need to ease into things because I definitely am feeling the
slightly alien nature of the syntax. Here :: is cons
and serves to build the list from the head down and the recursion is
over the remainder (sub)string, less two leading characters (␍␊).
Leaving aside the control data for a moment I want to write a function that can similarly split up a header field between the "key" and "value" or left-hand-side and right-hand-side. It is very similar except there is an additional need to clean up the string data found within the fields, trimming leading and trailing whitespace from the values.
fun split_header_kv substr =
let
val (key, value) = Substring.position ":" substr
val trim_ws = fn s => Substring.dropr Char.isSpace (Substring.dropl Char.isSpace s)
in
if Substring.isEmpty value
then
NONE
else
(* seems a little weird to produce the string here but
maybe logical enough that it's generating a return value *)
SOME ((Substring.string key),
(Substring.string (trim_ws (Substring.triml 1 value))))
end
Here I'm reusing String.position but adding a helper
function to trim whitespace before introducing another Option to
handle the potential absence of any headers or potential malformed
data. I chose to turn the Substrings back into plain Strings on the
return rather than propagating Substrings into the interface laid
out as part of the request type.
Given the above means of producing lines of header data (admittedly it is control data and header data but let's ignore that for a little while longer) and a function to extract key-value pairs from a single line of the header it is time for a function to parse all of the headers:
fun parse_headers substr_list =
case substr_list
of [] => SOME []
| line :: rest =>
case split_header_kv line
of NONE => NONE (* failure type instead of silently skipping bad data *)
| SOME kv => case parse_headers rest
of NONE => NONE
| SOME kvs => SOME (kv :: kvs)
Here the code starts to look a little exciting again because the
pattern matching in SML is neat but takes some getting used to. The
absence of header fields isn't considered a failure and is handled
first to produce an empty list. The :: cons operator
can be used in destructuring during pattern matching, here it is
peeling off the first element of the list before handing it into a
nested case expression which itself has a nested case expression
using the remainder of the list(!!). The way the innermost case
expression performs a list building operation using values from the
outer expressions is a little mind bending. I'm not sure this is at
all idiomatic but it does appear to work. I will admit I
have no intuition for how this is compiled or evaluated, in
something like scheme or common lisp it isn't too hard to understand
recursion's stack effects but I haven't grasped it here.
With all of these helper functions in place all that is left is stitching them together, along with a means to split out the control data from the header fields. Given the potential to pattern match on a list destructuring it made sense to me to do all of this at once. Having written it out though I'm not sure it doesn't motivate a slightly more verbose or discrete approach because this one looks pretty gnarly:
fun parse str =
case extract_preamble (Substring.full str) of
NONE => NONE
| SOME preamble => case split_crlf_lines preamble
of control_line :: header_lines => (case (Substring.tokens Char.isSpace control_line,
parse_headers header_lines)
of ([method, path, version],
SOME headers) => SOME { path = (Substring.string path),
headers = headers }
| _ => NONE)
| _ => NONE
At the start we can see the invocation
to extract_preamble and how it is given a freshly
created Substring. The intention is for this function to receive the
raw text of an HTTP request and turn it into the structured
record. Given the potential for malformed data this method also
returns an Option and as a consequence has multiple potential return
points for NONE. In the case though that a preamble was found it is
passed to split_crlf_lines which pattern matches the
list destructuring into the first line of control data and the
remainder list of header data.
The innermost case expression is a little wild looking and I turned
up this form while looking for a better way of writing what was
previous two nested case expressions. There's a need to split up the
control data as well as parse the header fields. Those are unrelated
operations though so instead of nesting there is this tuple form in
which both operations are run and then matched. The call
to Substring.tokens will split "POST /users
HTTP/1.1" into ["POST", "/users",
"HTTP/1.1"]. The curly braces are just a record type
construction using the key names "path" and "headers".
Having actually written out the above and being forced to look at that awful nested case expression has me vaguely annoyed. I've gone back to try rewriting it into a different form that is less confusing. I'm not sure I've really got it but first tried extracting the innermost case expression into another function, like this:
fun parse str =
let
fun build_request parts =
case parts of
([method, path, version], SOME headers) =>
SOME { path = Substring.string path, headers = headers }
| _ => NONE
in
case extract_preamble (Substring.full str) of
NONE => NONE
| SOME preamble =>
case split_crlf_lines preamble
of control_line :: header_lines =>
build_request (Substring.tokens Char.isSpace control_line, parse_headers header_lines)
| _ => NONE
endAnd then I found there is an abbreviated form of function definitions that kind of inlines the pattern match without the need of an explicit case expression. With that syntactic sugar it can look like this:
fun parse str =
let
fun build_request ([method, path, version], SOME headers) =
SOME { path = Substring.string path, headers = headers }
| build_request _ = NONE
in
case extract_preamble (Substring.full str) of
NONE => NONE
| SOME preamble =>
case split_crlf_lines preamble
of control_line :: header_lines =>
build_request (Substring.tokens Char.isSpace control_line, parse_headers header_lines)
| _ => NONE
endThat at least fits better on the screen and has less silly parentheses required.
With the bulk of the work done I wanted to figure out how to wrap all of this up into a module or similar because I've heard positive things about the module system. I don't know that I'll experience much of that here but it is worth a shot.
I think the first thing I need is a "signature" which seems to be akin to an interface. Interestingly I can export my custom type but don't have to externalize anything about it, for example this seems like a working signature:
signature HttpRequestParser = sig
type request
val parse : string -> request option
endIf I then wrap all my code up under a structure like this:
structure HttpRequestParser :> HttpRequestParser = struct
...
endThings technically work.
I say technically because it is possible to parse an HTTP message
but there is no means to do anything with the returned
type request. I think this may be partly a result of
the :> qualifier I've used on the structure which
serves to make the structure "opaque". The exact meaning of "opaque"
is a little hard to grasp, going only
off the SML97
specification which explains in terms like: "With opaque
matching, types in the resulting structure will be abstract, to
precisely the degree expressed in sigexp".
Instead the signature should include some functions to poke at the data and then those functions need to be written into the structure along with the rest of the code:
signature HttpRequestParser = sig
type request
val parse : string -> request option
val path : request -> string
val headers : request -> (string * string) list (* mostly for debugging *)
val header : request -> string -> string option
endTwo of these are comically simple, it is only interesting how the module can externalize the custom type without accessors into that data. Here's the path and headers "getters":
fun path ({path, ... } : request) = path
fun headers ({headers, ... } : request) = headers
The notable thing is how the function argument needs to be annotated
with a type in order to identify or resolve what looks like an
anonymous(?) record properly to the type checker. Without it the
compiler (I've since learned sml is in fact a full
compiler and is just very fast, no interpreter here) shrugs and says
something like:
http-request-parser.sml:83.1-83.29 Error: unresolved flex record
(can't tell what fields there are besides #path)The above is probably more useful with more complicated records or matching, it is also sufficient seemingly to name all the fields in the argument record like:
fun path {path, headers} = path
fun headers {path, headers} = headersThe final accessor function is the most interesting, it is a kind of "get value by key" for the header fields and is going to be case insensitive:
fun header r s =
let
val lower = String.map Char.toLower
in
case List.find (fn (k, _) => lower k = lower s) (headers r)
of SOME (_, v) => SOME v
| NONE => NONE
end
Probably the most interesting bit is the currying in the definition
of lower, which is turning a function that takes a
function and a string and turning it into a function that takes a
string. Otherwise it is performing a string match on the list of
string tuples that make up the headers.
Using it all looks something like this, where I've put the signature
and structure into a file http-request-parser.sml and
then issued use "http-request-parser.sml";
interactively:
- val raw = "GET /hola HTTP/1.1\r\nHost: example.com\r\nAccept: */*\r\nCookie: c-is-for-cookie\r\n\r\n<html>" ;
val raw =
"GET /hola HTTP/1.1\r\nHost: example.com\r\nAccept: */*\r\nCookie: c-is-for-c#"
: string
- val r = HttpRequestParser.parse raw ;
val r = SOME - : HttpRequestParser.request option
- HttpRequestParser.path (Option.valOf r) ;
val it = "/hola" : string
- HttpRequestParser.headers (Option.valOf r) ;
val it =
[("Host","example.com"),("Accept","*/*"),("Cookie","c-is-for-cookie")]
: (string * string) list
- HttpRequestParser.header (Option.valOf r) "Cookie";
val it = SOME "c-is-for-cookie" : string option
- HttpRequestParser.header (Option.valOf r) "X-Something-Else";
val it = NONE : string option
Notably, I'm not really sure how I'm supposed to be interacting with
these Option types in an interactive session where I don't really
want to write out a bunch of pattern
matching. Option.valOf serves to unwrap it so I can at
least print things more easily.
This was an entertaining exercise. Playing around with Standard ML is fun for how foreign some of the approaches are but the results are pleasing to me. It has been ages since I felt quite so new to a language which is a nice change of pace. There are certainly fewer functions out of the box for string handling with Standard ML than in something like Python but the pieces broadly seem well considered and I haven't yet felt too constrained in at least this simple exercise.