Does Daml perform any tail call optimizations

The questions around recursion here made me wonder if Daml performs any tail call optimizations?

3 Likes

Short answer, Yes. :slight_smile:

Since around November 2020, with this PR:

We have some test cases here:

For implementation details see:

6 Likes

@Nick_Chapman This is awesome. I’ll try to grok the Speedy scala. But in the meantime what about allocations that occur at the tail position?

my_map : (a -> b) -> [a] -> [b]
my_map f [] = []
my_map f (h::t) = f h :: my_map f t
2 Likes

Unfortunately my_map is not tail recursive, so no tail call optimization will apply. The speedy execution stack will grow to the length of the input list. Fortunately, the speedy execution stack lives on the JVM heap, so there will be no JVM stack overflow. (Never overflowing the JVM stack during Daml execution is a property the speedy engine aims to ensure!)

As far as I am aware, the only way to code a tail-recursive definition of list mapping is to make two passes over the list. Something like this (and assuming reverse is tail recursive):

myMapAcc : [b] -> (a -> b) -> [a] -> [b]
myMapAcc acc _ [] = reverse acc
myMapAcc acc f (h::t) = myMapAcc (f h :: acc) f t

myMap : (a -> b) -> [a] -> [b]
myMap f xs = myMapAcc [] f xs
1 Like

Thank you!

ATS Forever!!!

1 Like

Just for fun, you can also implement a tail-recursive map using foldl as follows:

map : (a -> b) -> [a] -> [b]
map f xs = reverse $ foldl (\t h -> f h :: t) [] xs

(This unpacks to the same as @Nick_Chapman’s code, but perhaps a little more efficient because foldl is a built-in.)

Or more point-free:

map : (a -> b) -> [a] -> [b]
map f = reverse . foldl (\t h -> f h :: t) []
1 Like

For even more fun, and contrary to my earlier reply, it is possible to define a tail recursive version of map, which makes just a single pass over the list. And we can still use foldl if we want:

onePassMap : (a -> b) -> [a] -> [b]
onePassMap f xs = foldl (\t h -> t . (f h ::)) identity xs []

This is pretty silly, and if you squint you can still see a 2nd pass :slight_smile:

2 Likes

I see 2nd passes everywhere! :crazy_face:

1 Like

It looks like your my_map function is tail recursive modulo cons, which, if i am not mistaken, would be tail-call optimized in Haskell.

1 Like