Combo Programming Language

From OpenCog
Jump to: navigation, search

Note that this page refers to what the Combo language could or should be, not what is implemented right now. For a good doc about it's current state you can look at doc/comboreduct/ComboReduct.pdf of the OpenCog project.

For more specific use cases of Combo as it should be, see Combo in OpenCog.

Overview

Combo is the language in which grounded OpenCog schemata and predicates are written. The primary design constraints are to allow complex programs to be represented concisely, and to be ammenable to evolutionary programming (MOSES) and probabilistic reasoning (PLN) methods. This has led to a unique style of programming:

  • The fundamental unit of programming is the function (a lambda-abstraction). Within function definitions however, combinators (abstract tree rewriting rules) are used, rather than lambda abstractions.
  • There is a mixture of typed and untyped operators, and an efficient novel "sloppy evaluation" scheme is used when evolved programs are being evaluated which may not be correctly typed. This is equivalent to a greedy search for a nearby correctly typed program.

Basic Expressions

Expressions in Combo are binary trees, with application nodes (@) in all of the internal nodes, and all operators and values living in the leaves. Thus, all operators are curried (take their arguments one at a time). For example, the expression (5+3)*8 is written in Combo as @(@(*,@(@(+,5),3)),8). As a tree, this is written as:

    @
   / \
  @   8
 / \
*   @
   / \
  @   5
 / \
+   3

More conveniently, @ signs are omited, and expressions are written in left-associatively, so a b c d means @(@(@(a,b),c),d). This corresponds to the tree:

      @
     / \
    @   d
   / \
  @   c
 / \
a   b

Parenthesis are used to indicate a different evaluation order, e.g., a b (c d) means @(@(a,b),@(c,d)). This is the tree:

     @
    / \
   /   \
  @     @
 / \   / \
a   b c   d 


So the expression above, @(@(*,@(@(+,5),3)),8), is written as * (+ 5 3) 8.

To make sure its clear, try and draw the tree and write the explicit (@ notation) and standard arithmatic notation expressions for: + 4 (- (+ 6 3) (- (* 2 2) 1)). Compute the result separately in all of the notations (they should be the same ;->). Answers here.

Combinators

A complete overview of the theory and practice of combinator logic is beyond the scope of this document; see for example < archive link > http://web.archive.org/web/20000616135240/http://cs.oberlin.edu/classes/dragn/labs/combinators/combinators.html . Briefly, combinators are abstract tree rewrite rules. This means that the result of evaluation of a combinator on its arguments can be specified independantly of the actual arguments.

See the first two sections of < archive link > http://web.archive.org/web/20000305172315/http://www.cs.oberlin.edu/classes/dragn/labs/combinators/combinators2.html for a more extensive description and examples.

Now let's work through an example that mixes combinators, standard arithmetic operators, S (B + (+ x)) (* x) (* x x), where x is some number.

Which one of these is easier to follow?

S (B + (+ x))          (* x) (* x x)  =>
   B + (+ x) (* x x)   (* x  (* x x)) =>
     + (+ x (* x x))   (* x  (* x x)) =>
     + (+ x x^2)       (* x  (* x x)) =>
     + x+x^2           (* x  (* x x)) =>
     + x+x^2           (* x  x^2)     =>
     + x+x^2           x^3            =>
     x+x^2+x^3
S (B + (+ x)) (* x) (* x x) =>
B + (+ x) (* x x) (* x (* x x)) =>
+ (+ x (* x x)) (* x (* x x)) =>
+ (+ x x^2) (* x (* x x)) =>
+ x+x^2 (* x (* x x)) =>
+ x+x^2 (* x x^2) =>
+ x+x^2 x^3 =>
x+x^2+x^3

Combo Operators and Constants

We are now at a point where we can give a specification for all of the operators and types that can live in the leaves of Combo trees.

Combinators

S f g x => (f x) (g x)
K x y   => x
I x     => x
B f g x => f (g x)
C f x y => f y x
W f x   => f x x
D f     => f f
E f x y => f (y x)
P x f   => f x

All of these are standard except for E= and =P.

Floating Point Numbers

can be put in the leaves and we will use the usual notation, like 4.43, 376, or -7.

Numeric Operators

+, -, *, /, %, log, floor

all have their standard meanings. In addition, pand, por, pnot are probabilistic logical operations; pand a b => a*b, por a b => a+b-a*b, pnot a => 1-a.

Random Numbers

random

produces a random number in [0,1].

Conditional Operators

<, <=, >, >=

Any number >0.5 is evaluated as true, anything else is evaluated as false. Canonical values are true=1, false=0.

Logical Operators

{| border="1"
|-
&&, |||, !
|}

as in C,.

Control Structures

  • ifelse t x y returns x if t evaluates to true else y.
  • until t f x returns res = f(f(...f(x)...)) with the minimal number of applications of f to x such that t(res) is true (possibly zero).

For example, until (< 100) (* 2) 1, evaluates to 128.

Lists

Lists are untyped; any valid expression can be placed in a list.

  • nil is the empty list.
  • cons x list concatenates an element x= to a list =list.

For example, the list (1, 2, S) can be constructed with cons 1 (cons 2 (cons S nil))).

List Manipulation

  • isEmpty list returns true if the given list is empty and else false,
  • hd list of a list gives the first element of this list or returns false,
  • tl list of a list gives the tail of the list,
  • nth list n gives the nth element of the list starting with =1=,
  • rev list reverses the list,
  • append list1 list2 appends two list,
  • map f list applies the given function to all elements of the list (i.e., map(f,(x1, x2, ..., xN)) => (f(x1), f(x2), ..., f(xN)), where list=(x1, x2, ..., xN).
  • foldl f x list returns res = f(f(...f(f(x, x1), x2)...), xN), where list=(x1, x2, ..., xN).
  • iota n given a number n returns the list (1, 2, ..., n).

For example, foldl * 1 (iota n) return n!.

Fractional parts of whole arguments =n= are dropped.

Characters and Strings

Characters can appear in single quotes (e.g., 'a'), and are a separate type. Strings are lists of characters. For convenience, "foo" is equivalent to the list ('f', 'o', 'o').

toString x returns a string representation of any item in the language.

Equality

== x y

can be used to test for equality between any two items in the language (note that === is the equality operator for floating point numbers only).

Functions

Function can be defined and invoked by name in Combo code. Recursive and mutually recursive functions are legal. Functions are defined giving their name, arity, and tree. Within the tree, arguments can be accessed with $n, where n is between 1 and the arity, inclusive. The syntax is

name(arity):=tree

Only one function can be defined with a given name.

For example, the classic recusive computation of Fibbonaci numbers can be written as:

fib(1) := ifelse (<= $1 2) 1 (+ (fib (- $1 1)) (fib (- $1 2)))

Definition and invocation of trinary plus:

triplus(3):=+ $1 (+ $2 $3)

triplus (triplus 1 2 3) 4 5

Constants

Constants are defined similarly to 0-ary functions, for example:

onePlusone := + 1 1

The difference is that constants are only evaluated once, when they are parsed, whereas 0-ary functions are evaluated each time they are called. For example:

randomPlusOneFunc(0):=+ 1 random
randomPlusOneConst:=+ 1 random

randomPlusOneFunc returns a different random number in [1,2] each time it is called, while randomPlusOneConst returns the same random number in [1,2] each time its called.

Evaluation Order

You may have noticed in the evaluation of the many of the examples given above above that at any given step, their are multiple evaluations (reductions) that we could perform. On the first step of S (B + (+ x)) (* x) (* x x) for example, we evaluated the S combinator on its arguments, but could just have easily have started with the * in (* x x). At first glance, this might seem to introduce ambiguity into the language; if we choose different evaluation orders we might obtain different results. Happily, it is fairly easy to prove that this is not the case; any two evaluation orders will return the same result, with two exceptions.

The first in random numbers, since a random number generator as defined above is not a function in the functional language (or mathematical) sense. For example, S + I random => +(random,random); but is it the same random number, or two different ones?

The second is programs that do not terminate; this is more of a problem than it appears to be at first glance, since recursive functions have non-terminting evaluation orders (find them!). Also, we want to be able to specify that in conditional and looping operations, no more evaluations are performed than necesary.

To avoid ambiguity and unreasonable non-termination, evaluation in Combo is always eager, and proceeds left-most-lower-most first, with the exception of ifelse, until, &&, |||=, which behave like their C counterparts, and combinators and function definitions, which are lazy. Adding grounded combinator tree procedures to the OpenCog Core is another exception; this is a properly understood as a kind of function definition (see Combo in OpenCog).

For example, the computation of the third Fibonacci number, using the fib function defined above, is:

fib 3
(((ifelse ((<= 3) 2)) 1) ((+ (fib ((- 3) 1))) (fib ((- 3) 2))))
(((ifelse (<=(3) 2)) 1) ((+ (fib ((- 3) 1))) (fib ((- 3) 2))))
(((ifelse 0) 1) ((+ (fib ((- 3) 1))) (fib ((- 3) 2))))
((+ (fib ((- 3) 1))) (fib ((- 3) 2)))
((+ (fib (-(3) 1))) (fib ((- 3) 2)))
((+ (fib 2)) (fib ((- 3) 2)))
((+ (((ifelse ((<= 2) 2)) 1) ((+ (fib ((- 2) 1))) (fib ((- 2) 2))))) (fib ((- 3) 2)))
((+ (((ifelse (<=(2) 2)) 1) ((+ (fib ((- 2) 1))) (fib ((- 2) 2))))) (fib ((- 3) 2)))
((+ (((ifelse 1) 1) ((+ (fib ((- 2) 1))) (fib ((- 2) 2))))) (fib ((- 3) 2)))
((+ 1) (fib ((- 3) 2)))
(+(1) (fib ((- 3) 2)))
(+(1) (fib (-(3) 2)))
(+(1) (fib 1))
(+(1) (((ifelse ((<= 1) 2)) 1) ((+ (fib ((- 1) 1))) (fib ((- 1) 2)))))
(+(1) (((ifelse (<=(1) 2)) 1) ((+ (fib ((- 1) 1))) (fib ((- 1) 2)))))
(+(1) (((ifelse 1) 1) ((+ (fib ((- 1) 1))) (fib ((- 1) 2)))))
(+(1) 1)
2

Sample Code

//////////////////////////////// Unlisty Examples //////////////////////////////// 

// cons up a list of some numbers
(cons 9.3 (cons -8.5 (cons 42 nil)))

// n! for 1<=n<=5
map (B (foldl * 1) iota) (iota 5)

// 2^8
foldl (B K (* 2)) 1 (iota 8)

// n^2 for -3<=n<=2
map (W *) (map (C - 4) (iota 6))

// define modulo (note that using the built-in % also works)
mod(2):=ifelse (= $2 0) $1 (ifelse (>= $1 0) (until (> $2) (C - $2) $1) (until (<= 0) (+ $2) $1))

// 11 % 3
mod 11 3

// define recursive fibonacci
fib(1) := ifelse (<= $1 2) 1 (+ (fib (- $1 1)) (fib (- $1 2)))

// 8th fibonacci
fib 8

// define some functions that call other functions
intpow(2) := foldl (B K (* $1)) 1 (iota $2)
powsum(2) := foldl (C (B + (intpow $1))) 0 (iota $2)
powseq(2) := map (intpow $1) (iota $2)

// invoke them
intpow 2 3

powsum 2 4

powseq .5 5

// "efficient" computation of power function in C style
cond(3) := ifelse (% $2 2) (cons $1 (cons (- $2 1) (cons (* $3 $1) nil))) (cons (* $1 $1) (cons (/ $2 2) (cons $3 nil)))
// power x n -> x^n
powerC(2) := (nth (until (B (= 0) (C nth 2)) (foldl I cond) (cons $1 (cons $2 (cons 1.0 nil)))) 3)

// "efficient" computation of power function in functional style
power(2) := (ifelse (= $2 0) 1 (ifelse (= (% $2 2) 1) (* $1 (power $1 (- $2 1))) (power (* $1 $1) (/ $2 2))))
//////////////////////////////// Listy Examples //////////////////////////////// 

//palindromes! pal (a,b,c) -> (a,b,c,b,a)
pal(1):=(append $1 (tl (rev $1)))

//flattens a list of lists
flatten(1):=foldl append nil $1

//all interpolations of an element in a list; e.g., a (b1,b2) returns ((a,b1,b2),(b1,a,b2),(b1,b2,a))
interp(2):=ifelse (isempty $2) (cons (cons $1 nil) nil) (cons (cons $1 $2) (map (cons (hd $2)) (interp $1 (tl $2))))

//all perumations of a list
allPerms(1):=ifelse (isempty $1) (cons nil nil) (flatten (map (interp (hd $1)) (allPerms (tl $1))))

//all subsets of a list
allSubsHelper(2):=(append (map (cons $1) $2) $2)
allSubs(1):=ifelse (isempty $1) (cons nil nil) (allSubsHelper (hd $1) (allSubs (tl $1)))

//all permutations of n elements of a list for all n in {0,...,listSize}
//e.g., enumeratePerms (1,2) -> ((1, 2), (2, 1), (1), (2), ())
enumeratePerms(1):=flatten (map allPerms (allSubs $1))

// merge-sort!
merge(2):=ifelse (isempty $1) $2 
                 (ifelse (isempty $2) $1 
                         (ifelse (< (hd $1) (hd $2)) 
                                 (cons (hd $1) (merge (tl $1) $2))
                                 (cons (hd $2) (merge $1 (tl $2)))))

firstN(2):=ifelse (= $2 0) nil (cons (hd $1) (firstN (tl $1) (- $2 1)))
lastN(2):=rev (firstN (rev $1) $2)

//subList x y (a1,..,an) -> (ax,...,ay)
//this is inefficient so the supercompiler will have some work to do ;->
subList(3):=lastN (firstN $3 $2) (- (+ $2 1) $1)

{| border="1"
|-
mergeSort(1):=ifelse (||| (isempty $1) (= (length $1) 1)) $1 
|}

                     (merge (mergeSort (subList 1 (floor (/ (length $1) 2)) $1)) 
                            (mergeSort (subList (+ 1 (floor (/ (length $1) 2))) (length $1) $1)))

//example of pal
pal (iota 5)

//examples of permutations, subsets, and ordered pemutations
allPerms animals
allSubs animals
enumeratePerms animals

//example of mergeSort
mergeSort (map random (iota 5))


Problem Answers

Answers

     @
    / \
   /   \
  @     @
 / \   / \
+  4  /   \
     /     \
    /       \
   /         \
  @           @
 / \         / \
-   @       @   1
   / \     / \
  @   3   -   @
 / \         / \
+   6       @   2
           / \
          *   2

Explicit @ notation: @(@(+,4),@(@(-,@(@(+,6),3)),@(@(-,@(@(*,2),2)),1)))

Standard notation: 4+((6+3)-((2*2)-1)

Result: 10

-- Main.MosheLooks - 21 Nov 2004