Per a suggestion by Jake Kirilenko, I'm looking at the combinator parser library called ostap. Instead of lazy evaluation it uses "explicit usage of closure." Hopefully it will help me better understand why the library I wrote doesn't work right.

I haven't worked on my lazy list library in a while, but here's the most recent incarnation:

http://www.msu.edu/~shawjef3/lazylist3.ml

The difference is that the list itself is lazy rather than just the tail. It doesn't seem to change anything with regards to the parser combinator's stack overflow.

Here's the combinator parser code that goes with the above library. Yes, it still overflows sometimes.

http://www.msu.edu/~shawjef3/combparslazy3.ml

The reason I made the lazy list library was so I could write a combinatorial parser that wouldn't get stuck on infinite recursion. This is a problem that I thought lazy evaluation would solve since it seems to work in Haskell. It isn't working out quite the way I hoped...

source: http://www.msu.edu/~shawjef3/lazylist.ml

Today I'm working on making caml work with lazy lists. Lazy evaluation is the default in haskell and its lists are lazy. However, in Caml, laziness has to be "turned on" with the lazy keyword or the use of the Lazy module. http://caml.inria.fr/pub/docs/manual-ocaml/libref/Lazy.html
My initial goal is to make something like the following work in Caml. It is intended to be a list containing the entire Fibonacci sequence.

let fib = let rec aux a b = a::(aux b (a+b)) in (aux 0 1)

Ocaml attempts to create the entire list at once, but this causes a stack overflow. If we can properly use the lazy keyword and Lazy module, something like the following should work:

#List.hd fib;;
- : int = 0
#List.hd fib;;
- : int = 0
#List.hd (List.tl fib);;
- : int = 1

I repeated "List.hd fib" to show that, unlike streams, lazy list functions are not destructive.

You cannot use the built-in caml list type. The reason is that you need the list to be constructed in a lazy way, something like:

# let lazycons a b = lazy (a::b);;
val lazycons : 'a -> 'a list -> 'a list lazy_t = <fun>

Notice that the second argument requires that the list be *fully constructed*. To use :: on a lazy list you have to do ::(Lazy.force b), which defeats the purpose of using lazy lists in the first place. Therefore we have to make a custom list type.

type 'a t = Cons of 'a * ('a t) Lazy.t | Nil

let cons a b = Cons (a,b)

The type of cons for lazy lists is
- : 'a -> 'a t Lazy.t -> 'a t = <fun>

Now for hd and tl and nth:

# let hd l =
match l with
   Nil -> failwith "Lazylist.hd"
 | Cons (a,b) -> a;;
   val hd : 'a t -> 'a = <fun>
# let tl l =
match l with
   Nil -> failwith "Lazylist.tl"
 | Cons (a,b) -> Lazy.force b;;
   val tl : 'a t -> 'a t = <fun>
# let rec nth l n =
match l with
   Nil -> failwith "Lazylist.nth"
 | Cons (a,b) ->
if n=0 then a else
  if n>0 then nth (Lazy.force b) (n-1) else
    invalid_arg "Lazylist.nth";;
         val nth : 'a t -> int -> 'a = <fun>

Now for a proper handling of the fibonacci sequence!

# let fib =
let ( >> ) = cons in
let rec aux a b =
 a >> lazy (aux b (a+b))
in
 (aux 0 1);;
       val fib : int t = Cons (0, <lazy>)
# hd fib;;
- : int = 0
# hd fib;;
- : int = 0
# tl fib;;
- : int t = Cons (1, <lazy>)
# hd (tl fib);;
- : int = 1
# nth fib 10;;
- : int = 55

YAY!

Now for some warnings. Some functions over lazy lists might not ever return a result! For instance,

Lazylist.iter (Printf.printf "%i\n") fib

will output to stdout ALL of the numbers in the Fibonacci sequence, until the int type overflows and the list becomes meaningless. At that point it will simply output thousands and thousands of integers for ever and ever.

Likewise, Lazylist.mem or Lazylist.exists might search forever without ever finding an end of the list or an appropriate member.

Another thing to keep in mind is that functions over lazy lists don't need to be tail-recursive to remain small in memory. This makes the code for certain functions more clear.

By the way, if anyone could help make the "partition" function lazy, please let me know. Perhaps other functions could be made lazy that I missed.

Enjoy!

Jeff

This data set finally gave brute enough information to find the program I was looking for.

./brute 10000000000 0 10 10 10 21 11 261 19 262 19 263 19 3 10 4 10 5 10 6 10 7 10 8 10 9 10 100 14
161923501: 5<d*+q

The brute force program generator has a way of finding "dirty tricks" to solve for your data set.

For instance, I wanted it to come up with a program that would add 100 and take the square root. More or less:

function a -> sqrt (a+100)

Here are some dirty tricks:

brute 10000000000 0 10 5 10 21 11
6840772: 5m5<+

translation into ocaml: function a -> (a mod 5) + 10

Here's another try, with the additional in/out pair (261,19):

brute 10000000000 0 10 5 10 21 11 261 19
78030700: >4+q8+

translation: function a -> sqrt ((a*2)+4)+8

Sure, these work for the data I gave it, but neither are what I wanted: 5<d*+q.

Sometimes, instead of using OCaml's string type, you want to use character lists. The problem is, many basic string functions do not have analogous functions for character lists in the standard library. This solves that problem:

http://www.msu.edu/~shawjef3/charstring.ml
http://www.msu.edu/~shawjef3/charstring.mli

I made an interpreter to test programs written in this little rpn language.

source: http://www.msu.edu/~shawjef3/lrpn.ml
windows binary: http://www.msu.edu/~shawjef3/lrpn.exe

Usage:
lrpn program stackval1 stackval2 ... stackvaln

For example, add 1 to each member of a 2-member stack.

lrpn 1+s1+s 5 6

yields:

6 7

Sometimes you will need to quote your program. For instance, "~1&" won't work on windows due to the shell thinking you are sending it commands. However quoting fixes that.

lrpn "~1&" 1

yelds 0, telling you that 1 is an odd number.

I added a function, prog2int, to brute_big.ml. Its purpose is to say what number corresponds to a program. For instance,

# prog2int lrpnwords ['1';'+';'s';'1';'+';'s'];;
- : string = "128766050"

I also added an optional argument to "discover", so that you don't always have to begin a search at 0.

discover ~minnum:(Big_int.big_int_of_string "120000000") ~maxnum:(Big_int.big_int_of_string "150000000")

would give a range that could find ['1';'+';'s';'1';'+';'s'].

Jeff

source: http://www.msu.edu/~shawjef3/brute_big.ml
windows executable: http://www.msu.edu/~shawjef3/brute_big.exe

Compile command: ocamlopt -o brute_big nums.cmxa brute_big.ml

Inspired by a discussion at http://wiki.tcl.tk/12199, I decided to mimic Richard's brute force self-programming RPN bytecode computer in ocaml. The version I wrote behaves in roughly the same manner, but instead producing all the possible programs ahead of time, it does it as it on the fly. I also check the program for any stack problems before testing it further.

For instance, duplicating the first item on the stack when the stack is empty would produce an ocaml exception. Any programs that would do this are ignored.

The language's words are

d duplicate first element
s swap the first two elements
r remove the first element
+ add
* multiply
/ divide
- negate (not subtraction)
< left bit shift
> right bit shift
| bitwise or
& bitwise and
~ bitwise negation
q square root
m modulo

and the integers 0 to 9.

The usage for the compiled program is:

brute_big (maximum number of tests) input1 output1 input2 output2 ... inputn outputn

If (maximum number of tests) is not given, the program will test the first 10,000 programs against the io requirements. Note that the compiled program only allows for the stack to begin and end with one element. If you use the "discover" function from the ocaml toplevel you can give it more complex requirements, such as [([1;2],[2;3]);([2;3],[3;4]);([34;55],[35;56])]. This, I hope, would give you a program which would add 1 to each of the elements on a stack with size 2.

(the command to use in the toplevel would be

discover (eval littlerpn) lrpnwords [([1;2],[2;3]);([2;3],[3;4]);([34;55],[35;56])];;

or, if you wanted it to search for the first 100,000 programs,

discover ~maxnum:(Big_int.big_int_of_string "100000") (eval littlerpn) lrpnwords [([1;2],[2;3]);([2;3],[3;4]);([34;55],[35;56])];;

Note that I have not found the program to do this yet. The program is >10,000,000. I would expect it to be something like 1+s1+s.)

It comes up with some interesting things, for instance, I asked it to create a program to test if a number is even or odd (output 1 means even, 0 means odd).

brute_big 10 1 11 0 444 1 2343 0

produced "~1&". In ocaml this would be "function a -> (lnot a) land 1".

Another one I tried was seeing if it could duplicate

function a -> (a mod 3)+10

brute_big 10000000000000 0 10 1 11 2 12 3 10 4 11 5 12 6 10

I expected "3m1+9+", and (after a long wait) that's what I got! There are other possible programs that would work, such as "3m55++", but "3m1+9+" occurs first in the testing. Modifying the array lrpnwords will change the order in which programs are tested. By default it is set to

let lrpnwords = [|'d';'s';'r';'+';'*';'-';'/';'<';'>';'|';'&';'~';'q';'m';'0';'1';'2';'3';'4';'5';'6';'7';'8';'9'|]

If we were to reverse the order of the integers, the program would probably have given "3m9+1+". If the integers came before '+', then it probably would have given "3m19++".

You can try more random looking mappings to see what wild programs it will create. For example,

brute_big 10000000000000 100 10 65 15
6456014: 4|9<m

Jeff