Leaf

Sorting a file: A real program in Leaf

Finally, a big step for Leaf: something that could be called an actual program. Over the weekend I finished a program that loads a file, sorts the lines, and writes it to the console. It may not sound like much, but it represents a significant milestone for the language.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
var main = -> {
    var args = sys.get_args()
    var in_file = args#0

    var qi = shared_file.open_read(in_file)
    var s = qi.read_text()

    var all = split( s, '\n' )
    std.quicksort_comp( all, 0, all.size -1, string_less )

    for i in std.range(0,all.size) {
        std.print( [ all.data#i, "\n" ] )
    }
}

All those functions are also written in Leaf, though deep in the code are a few embedded OS calls.

Things todo

The code is littered with a variety of things that still need to be done, or aren’t done well. Let’s look at a few of them.

The function quicksort_comp should really just be called quicksort. Parametric overloaded functions, exported from a library, aren’t quite working right. This version takes a comparator, string_less. Note there is no standard string type at the moment, so we need a custom comparator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
defn string_less = ( a : arraychar」, b : arraychar ) -> ( :boolean) {
    var at = 0
    loop at < a.size and at < b.size ? {
        //TODO: shouldn't need {}'s on return
        code_val(a#at) < code_val(b#at) then { return true }
        code_val(a#at) > code_val(b#at) then { return false }
        at = at + 1
    }

    return at >= a.size
}

shared_file is also part of a TODO at the top of the file:

1
2
//TODO: sys.file needs to be a "service" type that implies "shared"
alias shared_file : sys.file shared

By default all types are assigned by reference in Leaf, which is certainly not desired for file — it doesn’t even make sense. I will introduce a service type for this, which will be a class that is automatically shared, and cannot be copied. This is how Leaf will expose the difference between types that are fundamentally values or fundamentally wrappers around resources.

That last bit with the loop could probably be cleaned up already. I’d make a join function to concatenate all the elements and then do one print statement.

Standard library

Leaf is still basically missing any kind of standard library. The bits that make up the above program will start being migrated to this effort. Keep in mind that virtually everything needs to be programmed, consider that innocent call to split above:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
defn split = ( s : arraychar」, c : char ) -> {
    var o : std.vectorarraychar」」 shared

    var at : integer = 0
    var last = at

    loop at < s.size ? {
        do s#at ==  c ? {
            o.push( arrsub(s, last, at - last) )
            last = at + 1
        }

        //TODO: incr/decr operators, or at least +=, -=
        at = at + 1
    }

    return o
}

defn arrsub = ( s : arrayany」, offset : integer, length : integer ) -> {
    var o = arraytype_infer(s#0)」(length)

    for i in std.range(0,length) {
        o#i = s#(i+offset)
    }

    return o
}

The file.read_text required creating a buffer class to accumulate all the data in the file. The vector class also had to be written, but is extremely minimal now.

What isn’t Leaf?

sys.file, std.print , and std.quicksort are written in Leaf. Ultimately these must talk to the operating system. I’m using LibC to do the actual OS level activities, but trying to keep the number of calls to a minimum, as it will all affect portability.

Calling a LibC function is done with an @import declaration of the function.

1
@import("open") multi os_open : ( pathname : raw_array<:abi_char:>, flags : abi_int, mode : abi_int ) -> ( : abi_int ) raw no_throw

The LibC functions ultimately used in this example are:

  • File functions: open, close, read
  • Memory functions: malloc, free
  • Console functions: putchar
  • argv and argc use a special linking mechanism instead of being arguments to main
  • A minimal C++ exported function to get _errno since there is no support for this directly in Leaf yet

The biggest layer between the high-level example and these low-level functions is unicode handling. All UTF-8 decoding and encoding is being handled in Leaf code. Those functions are not pleasant: they are a collection of bitcode operations.

I’ll start cleaning up the TODOs now.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s