blog

In this tutorial, we reimplement several of wc's features in ATS. The core logic (as we shall see) is relatively simple, and we end up with something that's competitive with C with relatively little effort.

First, we will handle the easier bit: counting. ATS provides several functions to stream from a file, namely streamize_fileref_line, streamize_fileref_word, and streamize_fileref_char. Do note that we will use the versions from libats/ML rather than prelude. For some reason there are two different functions named streamize_fileref_line in the standard library, so one must be careful.

Let's get our imports out of the way (they're not particularly interesting):

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"
#include "prelude/DATS/filebas.dats"
#include "libats/ML/DATS/filebas_dirent.dats"
#include "libats/libc/DATS/dirent.dats"
staload "libats/ML/DATS/string.dats"
staload "libats/ML/DATS/filebas.dats"
staload EXTRA = "libats/ML/SATS/filebas.sats"

ATS is a functional programming language, so we will use higher-order functions to simplify the problem in question.

We'll first define count to count streams generated from a file. It will have the following type signature:

fun {a:t@ype}count(s: string, fcount: FILEref -<cloptr1> stream_vt(a)) : int

This takes a function fcount which takes FILEref as an argument and returns a stream_vt(a). For now, you can think of -<cloptr1> as somewhat like -> in Haskell or Idris.

With the type signature in mind, we can express the counting functions like so:

fun line_count(s: string): int =
  count(s, lam x => $EXTRA.streamize_fileref_line(x)) - 1
fun word_count(s: string): int =
  count(s, lam x => $EXTRA.streamize_fileref_word(x)) - 1
fun char_count(s: string): int =
  count(s, lam x => $EXTRA.streamize_fileref_char(x))

This is exactly what we want - we pass in a string containing the filepath, and we get back the relevant information. Now we can return to count, giving it the following implementation:

fun {a:t@ype}count(s: string, fcount: FILEref -<cloptr1> stream_vt(a)) : int =
  let
    var ref = fileref_open_opt(s, file_mode_r)
    val x = case ref of
      | ~Some_vt(x) => 
        begin
          let
            var viewstream = fcount(x)
            var n: int = stream_vt_length(viewstream)
            val _ = fileref_close(x)
          in
            n
          end
        end
      | ~None_vt() => (println!("could not open file at " + s) ; exit(1) ; 0)
    val _ = cloptr_free($UN.castvwtp0(fcount))
  in
    x
  end

There is quite a lot going on here. First, we note that fcount has linear type - we have to free fcount or the compiler will give us a type error. So it turns out -<cloptr1> is not quite the same as ->.

Next, note the use of stream_vt_length. Since stream_vt is a linear type, it must be fully consumed. Indeed, if we had written

var n: int = 0

instead, our program would not typecheck. Thankfully, consuming the value is relatively easy in this example.

The series of motions we go through to open a file should be familiar enough.

We are now ready to handle parsing command-line arguments. Unfortunately (and unsurprisingly), there is no library to do this. The approach will generalize, but it will not be pleasant.

Our first step is to set out some data types for the command-line parser. We'll go for a simple approach, using sum types and record types that will be familiar to anyone with a familiarity with functional programming.

datatype counter =
  | lines
  | words
  | chars
  | unknown
typedef command_line = @{ file_name = Option(string)
                        , to_count = counter
                        }

Our wc clone will be pretty limited in functionality; in particular it will only print one count at a time. We will parse an Option(string) to hold the file name, failing later if none is present.

Next we write some helper functions to modify a command_line record.

fun set_target(acc: command_line, s: string) : command_line =
  let
    val b = case+ acc.file_name of
      | None _ => true
      | _ => false
    val acc_r = ref<command_line>(acc)
    val _ = if b then acc_r->file_name := Some(s)
  in
    !acc_r
  end

This function will take a string, the previous state of command_line, and it will return another command_line. It also prevents us from reading more than one file at once (unlike the real wc). We can do something similar for handling the actual flags:

fun set_lines(acc: command_line, ct: counter) : command_line =
  let
    val acc_r = ref<command_line>(acc)
    val _ = acc_r->to_count := ct
  in
    !acc_r
  end

With that in place, we can write the actual parser. We don't bother handling various edge cases in this example (e.g. when the user specifies both -l and -w) as it is tedious and not particularly illuminating.

fun process(arg: string, acc: command_line) : command_line =
  case+ arg of
    | "-l" => set_lines(acc, lines)
    | "-w" => set_lines(acc, words)
    | "-c" => set_lines(acc, chars)
    | s => set_target(acc, s)
fnx get_cli
  { n : int | n >= 1 }
  { m : nat | m < n }
  .<n-m>.
  ( argc: int n
  , argv: !argv(n)
  , current: int m
  , acc: command_line
  ) : command_line =
  let
    var arg = argv[current]
  in
    if current < argc - 1 then
      let
        val acc_next = get_cli(argc, argv, current + 1, acc)
      in
        process(arg, acc_next)
      end
    else
      process(arg, acc)
  end

We've split out process for readability's sake, but everything else here is fairly standard. We use refinement types (essentially universal quantifiers) in get_cli to check at compile time that all array accesses are safe. Note also the use of .<n-m>. here: the termination metric proves that our parser will terminate.

At this point we're nearly done; we need a few trivial bits of control flow.

fun get_file(f: Option(string)) : string =
  case+ f of
    | Some(x) => x
    | None => (prerr!("Need to specify a filename.\n") ; exit(1))
implement main0 (argc, argv) =
  let
    val cli = @{ file_name = None
               , to_count = unknown
               }
    val _ = if argc = 1 then (prerr!("Need to specify a filename.\n") ; exit(1))
    val parsed = get_cli(argc, argv, 0, cli)
    val file_name = get_file(parsed.file_name)
  in
    case+ parsed.to_count of
      | lines _ => println!(tostring_int(line_count(file_name)) + " " + file_name)
      | words _ => println!(tostring_int(word_count(file_name)) + " " + file_name)
      | chars _ => println!(tostring_int(char_count(file_name)) + " " + file_name)
      | unknown _ => println!("Please provide one of '-l', '-w', or '-c'")
  end

Putting this all together, you should have something like the following:

#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"
#include "prelude/DATS/filebas.dats"
#include "libats/ML/DATS/filebas_dirent.dats"
#include "libats/libc/DATS/dirent.dats"
staload "libats/ML/DATS/string.dats"
staload "libats/ML/DATS/filebas.dats"
staload EXTRA = "libats/ML/SATS/filebas.sats"
datatype counter =
  | lines
  | words
  | chars
  | unknown
typedef command_line = @{ file_name = Option(string)
                        , to_count = counter
                        }
fun {a:t@ype}count(s: string, fcount: FILEref -<cloptr1> stream_vt(a)) : int =
  let
    var ref = fileref_open_opt(s, file_mode_r)
    val x = case ref of
      | ~Some_vt(x) => 
        begin
          let
            var viewstream = fcount(x)
            var n: int = stream_vt_length(viewstream)
            val _ = fileref_close(x)
          in
            n
          end
        end
      | ~None_vt() => (println!("could not open file at " + s) ; exit(1) ; 0)
    val _ = cloptr_free($UN.castvwtp0(fcount))
  in
    x
  end
fun line_count(s: string): int =
  count(s, lam x => $EXTRA.streamize_fileref_line(x)) - 1
fun word_count(s: string): int =
  count(s, lam x => $EXTRA.streamize_fileref_word(x)) - 1
fun char_count(s: string): int =
  count(s, lam x => $EXTRA.streamize_fileref_char(x))
fun set_lines(acc: command_line, ct: counter) : command_line =
  let
    val acc_r = ref<command_line>(acc)
    val _ = acc_r->to_count := ct
  in
    !acc_r
  end
fun set_target(acc: command_line, s: string) : command_line =
  let
    val b = case+ acc.file_name of
      | None _ => true
      | _ => false
    val acc_r = ref<command_line>(acc)
    val _ = if b then acc_r->file_name := Some(s)
  in
    !acc_r
  end
fun process(arg: string, acc: command_line) : command_line =
  case+ arg of
    | "-l" => set_lines(acc, lines)
    | "-w" => set_lines(acc, words)
    | "-c" => set_lines(acc, chars)
    | s => set_target(acc, s)
fnx get_cli
  { n : int | n >= 1 }
  { m : nat | m < n }
  .<n-m>.
  ( argc: int n
  , argv: !argv(n)
  , current: int m
  , acc: command_line
  ) : command_line =
  let
    var arg = argv[current]
  in
    if current < argc - 1 then
      let
        val acc_next = get_cli(argc, argv, current + 1, acc)
      in
        process(arg, acc_next)
      end
    else
      process(arg, acc)
  end
fun get_file(f: Option(string)) : string =
  case+ f of
    | Some(x) => x
    | None => (prerr!("Need to specify a filename.\n") ; exit(1))
implement main0 (argc, argv) =
  let
    val cli = @{ file_name = None
               , to_count = unknown
               }
    val _ = if argc = 1 then (prerr!("Need to specify a filename.\n") ; exit(1))
    val parsed = get_cli(argc, argv, 0, cli)
    val file_name = get_file(parsed.file_name)
  in
    case+ parsed.to_count of
      | lines _ => println!(tostring_int(line_count(file_name)) + " " + file_name)
      | words _ => println!(tostring_int(word_count(file_name)) + " " + file_name)
      | chars _ => println!(tostring_int(char_count(file_name)) + " " + file_name)
      | unknown _ => println!("Please provide one of '-l', '-w', or '-c'")
  end

You can compile this with

 $ patscc wc.dats -DATS_MEMALLOC_LIBC -o ats-wc -cleanaft -O2 -mtune=native

And run it with

 $ ./ats-wc wc.dats -l
 117 src/wc.dats

And that's it! We've written a fast, functional implementation of a common tool in 117 lines. It's certainly not complete, but I hope this gives some insight into writing useful programs in ATS.