cdiggins.com

It took me a surprsingly long while to actually getting around to writing a quick sort program in Cat. Quick-sort is a particularly interesting program for functional stack-based languages because it demonstrates how compact they can be.

Here is the implementation of quick sort from the Cat standard library in the new version 0.12.0:

  define qsort : (list -> list) {
    [small]
    []
    [uncons under [lt] curry split]
    [[swap cons] dip cat]
    bin_rec
  }

Joy aficionados might notice that this is slightly longer than the Joy version. This is due to the fact that Cat is less permissive than Joy, one of the inevitable costs of having a type system.

About the Version 0.12.0 Release

Apart from having a working quick sort implementation there are several new additions to Cat. Thanks to over 400 test cases the stability is becoming quite good, and I am able to focus more on making language enhancements. Here are some of the new features:

• The syntax now allows mixing of symbols, letters and numbers to create new identifiers. Thanks to Bryan Burgers for the suggestion.
• There is now a byte data type, and basic operations available on it. The byte primitive function converts integers into bytes.
• Binary literals (e.g. 0b1001) and hexadecimal literals (e.g. 0xf1a9) are now supported.
• You can convert numbers into binary string representations using bin_str or into hexadecimal string representations using hex_str.
• There are now two kinds of lists in the implementation: mutable lists which have expensive copy operations but inexpensive modification operation. Immutable lists (the default) have cheap copying semantics but expensive modification semantics.
• The byte_block function constructs a mutable array of bytes, which offers the same semantics as any other list, but optimized for bytes.
• The binary recursion operator bin_rec is now supported.
• A generalized fold operation, gfold, is now available
• The split function which splits a list into two parts according to a predicate function

Thanks to encouragement from Scott Prouty there is now some basic IO functionality.

• temp_file creates a new uniquely named temporary file and returns its name
• file_reader opens a binary stream reader from a file name
• file_writer opens a binary stream writer from a file name
• read_bytes reads a byte_block of a specified size from a binary stream reader
• write_bytes writes a byte_block to a binary stream writer
• close_stream flushes, closes, and disposes a stream

Things are also progressing very well on the type checker and the foundation code is all in place. If all goes well I may be able to declare a version 1.0 release at the end of the month of May with full static type-checking.

This entry was posted on Tuesday, May 1st, 2007 at 7:02 pm and is filed under Everything. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.