ATS is known for its sophisticated type system, but it also has a template system that has been the focus of recent work. Rather than going into technical details or comparing templates to other forms of generic programming, I wanted to give an example.
Code Counting
Suppose we want to count lines of code, à la cloc. Briefly, this means detecting various different programming languages and then examining file contents to count the number of lines, comments, and blanks.
A naïve approach would be to define a type
vtypedef file = @{ lines = int, blanks = int, comments = int, doc_comments = int }
and functions
fn read_file(fp: string) : string
fn count\_haskell(file\_contents: string) : file
fn count\_j(file\_contents: string) : file
…
This is unnecessarily slow, particularly in a code-counting tool like cloc: it will allocate each time a file is opened. Instead, we can define a set of function templates for each programming language that count lines of code from a stream of characters, viz.
fn {a:vt@ype} advance\_char$lang (char, &a >> \_, &file >> _) : void
fn {a:vt@ype} free$lang (a) : void
fn {a:vt@ype} init$lang (&a? >> a) : void
The workhorse here is advance_char$lang: it takes a character, a reference to
a value of type a, and a reference to a value of type file. For each programming
language we define a custom parse state a, and implement advance_char$lang
for that particular a.
As an example consider the implemenation of advance_char$lang for
Egison in
SATS/lang/egison.sats:
datavtype parse\_state\_egi =
| line\_comment
| regular
| post\_newline\_whitespace
fn free\_st\_egi(parse\_state\_egi) : void
overload free with free\_st\_egi
and DATS/lang/egison.dats:
staload "SATS/file.sats"
staload "SATS/lang/egison.sats"
staload "SATS/lang/common.sats"
implement free\_st\_egi (st) =
case+ st of
| ~line\_comment() => ()
| ~regular() => ()
| ~post\_newline\_whitespace() => ()
implement free$lang<parse\_state\_egi> (st) =
free\_st\_egi(st)
implement init$lang<parse\_state\_egi> (st) =
st := post\_newline\_whitespace
implement advance\_char$lang<parse\_state\_egi> (c, st, file\_st) =
case+ st of
| regular() =>
begin
case+ c of
| '\n' => (free(st) ; file\_st.lines := file\_st.lines + 1 ; st := post\_newline\_whitespace)
| \_ => ()
end
| line\_comment() =>
begin
case+ c of
| '\n' => (free(st) ; file\_st.comments := file\_st.comments + 1 ; st := post\_newline\_whitespace)
| \_ => ()
end
| post\_newline\_whitespace() =>
begin
case+ c of
| '\n' => (file\_st.blanks := file\_st.blanks + 1)
| '\t' => ()
| ' ' => ()
| ';' => (free(st) ; st := line\_comment)
| \_ => (free(st) ; st := regular)
end
Tying this all together, we define a template function to count lines of code in a file:
\#define BUFSZ 32768
staload "libats/libc/SATS/stdio.sats"
staload "SATS/file.sats"
staload "SATS/lang/common.sats"
fn {a:vt@ype} count\_for\_loop { l : addr | l != null }{m:nat}{ n : nat | n <= m }( pf : !bytes\_v(l, m) | p : ptr(l)
, parse\_st : &a >> \_
, bufsz : size\_t(n)
) : file =
let
var res: file = empty\_file
var i: size\_t
val () = for* { i : nat | i <= n } .<n-i>. (i : size\_t(i)) =>
(i := i2sz(0) ; i < bufsz ; i := i + 1)
let
var current\_char = byteview\_read\_as\_char(pf | add\_ptr\_bsz(p, i))
in
advance\_char$lang<a>(current\_char, parse\_st, res)
end
in
res
end
fn {a:vt@ype} count\_file\_buf { l : addr | l != null }(pf : !bytes\_v(l, BUFSZ) | p : ptr(l), inp : !FILEptr1) : file =
let
var init\_st: a
val () = init$lang<a>(init\_st)
fun loop { l : addr | l != null }(pf : !bytes\_v(l, BUFSZ) | inp : !FILEptr1, st : &a >> \_, p : ptr(l)) : file =
let
var file\_bytes = freadc(pf | inp, i2sz(BUFSZ), p)
extern
praxi lt\_bufsz {m:nat} (size\_t(m)) : [m <= BUFSZ] void
in
if file\_bytes = 0 then
empty\_file
else
let
prval () = lt\_bufsz(file\_bytes)
var acc = count\_for\_loop<a>(pf | p, st, file\_bytes)
in
acc + loop(pf | inp, st, p)
end
end
var ret = loop(pf | inp, init\_st, p)
val () = free$lang<a>(init\_st)
in
ret
end
Notice that we can define the count_file_buf template in terms of
advance_char$lang<a>. That is, we provide a generic way to stream characters
from a file, and then call count_file_bug<parse_state_egi> (for instance) when
we want to count lines of code in an Egison file.
The full setup is available here.
Note
The error messages related to misusing templates are not particularly refined.
If, for example, we attempt to call count_file_buf<parse_state_egi> without
implementing advance_char$lang<parse_state_egi>, we get
.atspkg/c/src/wc-demo.c:76635:28: error: ‘PMVtmpltcstmat’ undeclared (first use in this function)
76635 | ATSINSmove\_void(tmp937\_\_6, PMVtmpltcstmat\[0](init$lang<S2Ecst(parse\_state\_egi)>)(ATSPMVrefarg1(ATSPMVptrof(tmpref936\_\_6)))) ;
| ^~~~~~~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76635:28: note: each undeclared identifier is reported only once for each function it appears in
76635 | ATSINSmove\_void(tmp937\_\_6, PMVtmpltcstmat\[0](init$lang<S2Ecst(parse\_state\_egi)>)(ATSPMVrefarg1(ATSPMVptrof(tmpref936\_\_6)))) ;
| ^~~~~~~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76635:46: error: ‘init$lang’ undeclared (first use in this function)
76635 | ATSINSmove\_void(tmp937\_\_6, PMVtmpltcstmat\[0](init$lang<S2Ecst(parse\_state\_egi)>)(ATSPMVrefarg1(ATSPMVptrof(tmpref936\_\_6)))) ;
| ^~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76635:56: warning: implicit declaration of function ‘S2Ecst’ \[-Wimplicit-function-declaration]
76635 | ATSINSmove\_void(tmp937\_\_6, PMVtmpltcstmat\[0](init$lang<S2Ecst(parse\_state\_egi)>)(ATSPMVrefarg1(ATSPMVptrof(tmpref936\_\_6)))) ;
| ^~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76635:63: error: ‘parse\_state\_egi’ undeclared (first use in this function)
76635 | ATSINSmove\_void(tmp937\_\_6, PMVtmpltcstmat\[0](init$lang<S2Ecst(parse\_state\_egi)>)(ATSPMVrefarg1(ATSPMVptrof(tmpref936\_\_6)))) ;
| ^~~~~~~~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76635:80: error: expected expression before ‘)’ token
76635 | ATSINSmove\_void(tmp937\_\_6, PMVtmpltcstmat\[0](init$lang<S2Ecst(parse\_state\_egi)>)(ATSPMVrefarg1(ATSPMVptrof(tmpref936\_\_6)))) ;
| ^
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76651:46: error: ‘free$lang’ undeclared (first use in this function)
76651 | ATSINSmove\_void(tmp946\_\_6, PMVtmpltcstmat\[0](free$lang<S2Ecst(parse\_state\_egi)>)(tmpref936\_\_6)) ;
| ^~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76651:80: error: expected expression before ‘)’ token
76651 | ATSINSmove\_void(tmp946\_\_6, PMVtmpltcstmat\[0](free$lang<S2Ecst(parse\_state\_egi)>)(tmpref936\_\_6)) ;
| ^
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c: In function ‘count\_for\_loop\_201\_\_201\_\_6’:
.atspkg/c/src/wc-demo.c:76944:28: error: ‘PMVtmpltcstmat’ undeclared (first use in this function)
76944 | ATSINSmove\_void(tmp934\_\_6, PMVtmpltcstmat\[0](advance\_char$lang<S2Ecst(parse\_state\_egi)>)(tmpref932\_\_6, ATSPMVrefarg1(arg1), ATSPMVrefarg1(ATSPMVptrof(tmpref927\_\_6)))) ;
| ^~~~~~~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76944:46: error: ‘advance\_char$lang’ undeclared (first use in this function)
76944 | ATSINSmove\_void(tmp934\_\_6, PMVtmpltcstmat\[0](advance\_char$lang<S2Ecst(parse\_state\_egi)>)(tmpref932\_\_6, ATSPMVrefarg1(arg1), ATSPMVrefarg1(ATSPMVptrof(tmpref927\_\_6)))) ;
| ^~~~~~~~~~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76944:71: error: ‘parse\_state\_egi’ undeclared (first use in this function)
76944 | ATSINSmove\_void(tmp934\_\_6, PMVtmpltcstmat\[0](advance\_char$lang<S2Ecst(parse\_state\_egi)>)(tmpref932\_\_6, ATSPMVrefarg1(arg1), ATSPMVrefarg1(ATSPMVptrof(tmpref927\_\_6)))) ;
| ^~~~~~~~~~~~~~~
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
.atspkg/c/src/wc-demo.c:76944:88: error: expected expression before ‘)’ token
76944 | ATSINSmove\_void(tmp934\_\_6, PMVtmpltcstmat\[0](advance\_char$lang<S2Ecst(parse\_state\_egi)>)(tmpref932\_\_6, ATSPMVrefarg1(arg1), ATSPMVrefarg1(ATSPMVptrof(tmpref927\_\_6)))) ;
| ^
/home/vanessa/.atspkg/0.3.13/lib/ats2-postiats-0.3.13/ccomp/runtime/pats\_ccomp\_instrset.h:284:39: note: in definition of macro ‘ATSINSmove\_void’
284 | #define ATSINSmove\_void(tmp, command) command
| ^~~~~~~
)
