fangang / cf Goto Github PK

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 expression, returning
             a sequence of matches. 
REPL
====
repl.cf contains a tiny repl implemented in cf. It calls the 'tokenize' and
'parse' primitives to evaluate the user input and prints the X and Y stack/queue
after each line. Note that the Y queue will show the 'remaining computation'
of the repl itself. Run with:

  $ ./cf prelude.cf repl.cf
  ok repl.
  Y: prompt . getline [ "bye" = ] [ drop . ] [ tokenize parse . repl . ] cond . 
  X: 
  repl> 

Exit using 'bye'.

Other Stuff
===========
A bunch of useful primitives remain to be written. I want to implement
many of them in the language itself.

I find needing to do the ';' after functions to get their value a bit 
annoying but I'm interested in seeing what can be done with this. This
idea comes from the False language mentioned in the F documentation.

Combinators are generally written by building lists of programs to do
the work. For example, the definition of 'each' from the prelude:

  [[[]]`swap;unit.`,uncons;unit.`,while.drop.] each set

This builds a while expression by taking the definition of 'uncons'
and 'swap' and prefixing them to the program given by the user. So
the translation looks like:

  [1 2 3] [println] each. => [1 2 3] [] [uncons.swap.] while.

'fold' works similar it translates like this:

  [1 2 3] 0 [+] fold => [0 1 2 3 + + + ].

Experimental Object System
==========================
cf includes an experimental protoype based object system. This is
still being designed and written so it is likely to change quite
a bit. The object system is based on that in the Self programming
language.

cf objects can have named slots. Each slot refernces another cf
object. Messages are symbols. The value of a slot is obtained
using the 'lookup' primitive: 

  lookup ( object message -- object list )

The result of lookup is the original object and a list containing
code that when unquoted will send the message to the object. The
list can be unquoted with '.' as normal. So 'lookup .' is to objects
as 'foo ;.' is to standard cf lookup and execution of functions.

Slots can be data or method slots. A data slot holds an initial value
and when a message is sent to it retrieves the value. Data slots are
added with 'add-slot':

  add-slot ( object value name -- object )

  object copy 42 foo add-data foo lookup .
    => 42
  object copy 42 foo add-data 25 over. foo: lookup . foo lookup .
    => 25

There is also an 'add-ro-slot' which adds a read only slot. No setter will
be added for this type of slot.

Parent slots have a name ending in '*'. If a message is not found when
looked up in an object then all that objects parent slots are also searched
for the message. This is how the prototype object system handles inheritance:

  object copy 42 foo add-slot
  object copy swap. parent* add-slot
  foo lookup .
    => 42

Method slots take a list representing the program to run when the
message is sent. When a message is sent that results in a method slot a
frame object is created. This frame object has a parent slot called 'self'
that points to the original object holding the method. Slot values of this
original object can be retrieved by accessing this frame object.

  add-method ( object args code name -- object )
  frame ( -- object )

  object copy [] [ frame message lookup . print ] display add-method
  object copy "hello" message add-slot
  swap. parent* add-slot
  display lookup .
    => "hello"

There is an 'object' primitive that returns the prototypical object. The
'copy' primitive returns a shallow copy of an object.

  object ( -- object )
  copy ( object -- object' )

The get and unquote primitives have been overloaded to work with the object
system. If ';' is called on a symbol, and that symbol is not found in the
environment, then it will be looked up in an object on the stack using
'lookup':

  object copy 25 foo add-slot foo;.
    => 25

If '.' is called on a symbol, and that symbol is not found in the 
environment, then it will be looked up in the frame object using
'lookup'. This makes '.' similar to Self's implicit self sends:

  object copy 25 foo add-slot
  [] [ foo. println ] print-foo add-method
  print-foo;.
    => 25

This works with arguments to methods too:

  object copy 
  [msg] [ msg. println ] print-msg add-method
  "hello" swap. print-msg;.
    => "hello"

Troubleshooting
===============
Error handling started of as being C++ assertions so a lot of
error handling still aborts with a fatal error. 

Most errors that occur as a result of interpreting (programming
errors, stack underflows, type errors, etc) cause the interpreter drop
back to the repl with an error object on the stack. The error object
has the following elements:

  1: The 'error' symbol
  2. The error message
  3. The stack at the time of the error
  4. The queue at the time of the error

From the repl you can manually examine the stacks, modify them
and restart execution. The following can be used to restart
given the stack and queue:

  ok [ ab- ] $

Why?
====
Why write this when concatenative languages like Factor exist
that are full featured with lots of libraries?

I wanted something small to play around with different ideas. Like
a programming puzzle to find different implementations of prelude
functions in different styles.

I wanted a C/C++ program that used small amounts of memory so I
could run it on embedded devices like a phone.

Feedback
========
I host this on githib:
  http://github.com/doublec/cf/tree/master

Feel free to clone, hack away, suggest patches, etc. I can be reached
via email: [email protected]