cf programming language

cf is a simple concatenative programming language written in C++. It is based on the languages XY [1] and F [2] written by Stevan Apter.

It originally started out as an implementation of F, written in C, hence the name 'cf'. I later moved to C++ and changed things a bit to try out some ideas.

This isn't really intended to be a usable language in itself. The code is meant to be hacked and modified to add features and make it easy to try out concatenative language ideas.

[1] http://nsl.com/k/xy/xy.htm [2] http://nsl.com/k/f/f.htm

License

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE DEVELOPERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Building

You'll need the following:

1. A C++ compiler. I used gccc 4.3.3 to build it and it worked fine.
2. libgmp [3] for 'big numbers'
3. Boost [4] for various library features I use.
4. gc C++ garbage collector [5]

'cf' uses 'gc', a C++ garbage collector. The git repository for 'cf' has 'gc' included as a submodule. When first getting the 'cf' source code via git you should do the following:

$ git submodule init $ git submodule update

To build 'cf' run 'make'. This produces 'cf', 'testcf' and 'leakcf' executables. Run 'cf' to get a simple command line repl and 'testcf' to run some tests to see if things are working. 'leakcf' will run, load some test files, execute a garbage collection and exit. It's useful for testing for leaks under valgrind.

[3] http://gmplib.org/ [4] http://www.boost.org/ [5] http://github.com/doublec/gc

Running

Run the 'cf' command. It optionally taks a list of filenames as arguments. These files are loaded, in order, and evaluated. For example, 'prelude.cf' provides some standard library functions. I recommend using rlwrap, or similar, to get command line editing:

$ rlwrap ./cf prelude.cf Loading prelude.cf -> ok

Data entered at the 'ok' prompt is pushed onto the stack, and pressing enter evaluates the program:

ok 25 5 + fac. 265252859812191058636308480000000 -> ok

'fac' is the factorial function implemented in prelude.cf.

Quick Overview

I'll add more detailed information here later, for now reading the information in [1] and [2] should enable a quick overview.

Basically the running system is composed of an environment, E, a stack X, and a queue Y. A 'program' is a series of functions and literals entered at the prompt as above.

When a program is evaluated, each item is prepended to the queue Y. The system then runs, taking the item at the front of the queue and evaluating it.

Literals (Numbers, Strings, Symbols) are immediately pushed onto the stack X. Primitives and shuffle patterns are executed immediately and the results can affect E, X or Y.

Primitives are the only symbols that are immediately executed. Symbols can be set to values and the value is obtained using the ';' primitive. If this value is a list it can then be further evaluated as a program using the '.' primitive. If '.' is used on a symbol then it's value will be obtained (if it has one) and '.' called again on that value. This makes the use of ';' optional in a lot of common cases.

Comments are anything between ** and **. For example:

ok [1 2 +] myfunc set ** set the 'myfunc' symbol to the list 1,2 and + ** ok myfunc ** push the 'myfunc' symbol on the stack ** ok ; ** get the value of it ([1 2 +]) ** ok . ** execute the list as a program ** ok println ** print the result ** => 3

Literate Files

A form of literate programming is supported, based on that of Literate Haskell: http://haskell.org/haskellwiki/Literate_programming

Any file that ends with the extension .lcf is a literate cf file. All lines starting with '>' are treated as code, everything else is a comment. For example:

"The sum of 1 + 2 is " write 1 2 + .

To facilitate use in LaTeX documents, all code between \begin{code} and \end{code} are also treated as code:

\begin{code} "This is evaluated as code" . \end{code}

See the examples in literate.lcf. They can be run with:

$ ./cf prelude.cf literate.lcf

Primitives

Look up cf.cpp in the XY() constructor for the list of primitives. Currently they are:

•    - Addition
  

•    - Subtraction
  

•    - Multiplication
  

% - Division ^ - Power _ - Floor set - set a symbol to a value ; - get the value of a symbol . - Execute a program on the stack ) - Process a pattern and store the result on the stack X ( - Process a pattern and prepend the result to the queue Y ` - dip operator | - Reverse a list ' - quote $ - stack operator $$ - stackqueue operator = - equals < - less than <= - less than or equal to

   - greater than

= - greater than or equal to not - if true, return false and vice versa. @ - retrieve nth item from a list (2 [1 2 3 4] @ => 3) . - print the topmost item on the stack print - as '.' but don't do a newline write - write the topmost item on the stack count - return the length of the list tokenize - given a string, return a list of the cf tokens. parse - given a list of tokens, return a list of cf objects getline - get a line of input from the user millis - returns number of milliseconds since 1970/1/1. enum - given a number, returns a list of elements from 0 to n-1. clone - creates a copy of the object on the stack to-string - leaves a string representation of the object on the stack split - ( string seperators -- seq ) splits a string sdrop - ( seq n -- seq ) removes n items from the sequence stake - ( seq n -- seq ) returns a sequence with the first n elements foldl - ( seq seed q -- seq ) left fold foldr - ( seq seed q -- seq ) right fold if - ( bool then else -- ) ? - ( seq elt -- index ) find gc - ( -- ) Perform garbage collection

Numbers can be floats or integers. Integers can be of any length. For example:

ok 1000 fac. println ...a really big number...

Shuffle patterns can be used to move things around on the stack. These are templates for stack operations:

ok 1 2 3 abc-cba => 3 2 1

There is Pattern support as per F [2]. Patterns, ( and ) operate the same as in F as far as I know:

ok [1 2 [3 4 5]] [ [a b [c C]] c C [a b] ] ) => 3 [4 5] [1 2]

$ works the same as in F [2]. It takes a program on the stack. That program will be evaluated with X and Y on the stack. It should return a new X and Y. This powerful operator can be used to do anything, including modify the future of the computation - it can implement partial and full continuations.

$$ is a helper function for $. It takes and X and Y on the stack and replaces X and Y with these.

` is dip. For example:

Joy/Factor: 1 2 3 [ - ] dip => -1 3 cf: 1 2 3 [-]`

' is the quote operator. It takes the next item on the Y queue, puts it into a one elements list and pushes it on the X stack.

1 2 '+ => 1 2 [+]

, is the join operator. It appends things to lists. Given two lists they are appended. Given two non-lists a two element list is made containing them. Given a list and a non-list, the non-list is added to the list. eg:

[1 2] [3 4], => [1 2 3 4] 1 [2 3 4], => [1 2 3 4] [1 2 3] 4, => [1 2 3 4] 1 2, => [1 2]

Non-Primitives

See 'prelude.cf' for the current non-primitives. Some of these include:

dup - 1 dup. => 1 1 drop - 1 2 drop. => 1 swap - 1 2 swap. => 2 1 uncons - [1 2 3] uncons. => 1 [2 3] cons - 1 [2 3] cons. => [1 2 3] first - [1 2 3] first. => 1 rest - [1 2 3] rest. => [2 3] clear - Clears the X and Y stacks. Useful at the REPL. queue - Move the top stack item to the tail of the queue. >r in forth/factor unqueue - Move the tail of the queue to the top of the stack. r> in forth/factor stack - push a list cotaining stack contents on the stack unstack - replace the stack with the contents of the list on the top of the stack cond - conditional: 5 [0 >] [ drop. "is true" ] [drop. "is false"] cond. while - 1 [10 <] [1 + a-aa .] while. do - 10 [ "hello" println ] do. map - [1 2 3] [1 +] map. => [2 3 4] each - [1 2 3] [println] each. fold - [1 2 3] 0 [+] fold. => 6 unfold - 1 [10 >] [] [1 +] unfold => [1 2 3 4 5 6 7 8 9 10] cleave - 1 [1 +] [2 +] cleave => 2 3 time - [100 fac.drop.] time. => 7 fac - 5 fac. => 120 fac2 - same as 'fac' but uses a fold/unfold and is much slower. match - ( regexp string -- seq ) matches string against the regular expressio