notes on otuto

these are some brief notes on otuto, a language that i implemented a few years ago, but which is no longer available (unless someone else has the source).

otuto combined ideas from forth (stacks), lisp (code as data), and haskell (pattern matching), but since i am no expert on any of those the resemblance may be minor. i may also be re-inventing the wheel.

the basic idea behind otuto is that two stacks are used to hold data/values and that the contents of these stacks are rewritten by matching against various rules. the state of the program - the two stacks - is written as:

{progn ... prog2 prog1 prog0 | data0 data1 data2 ... datan}

and, as that diagram implies, the stack "on the left" can be considered to contain the program, while the stack "on the right" contains the data (although in practice values pass back and forth between the two). in case it's not completely clear from the numbering, the stacks are written so that the "top" values are either side of the central bar.

a rewrite rule was written as a "before" and "after" set of stacks. so the commmon "dup" operation could be defined as:

{dup | a} => { | a a}

the meaning should be obvious - if the top value of the "program" stack contains the symbol "dup" then remove it and replace the top value of the "data" stack with the same value, repeated.

note that "dup" is a literal match, while "a" is free variable here. a lot of the effort designing otuto went into finding a scheme that allowed both literal matches and free variables with minimal ugly syntax. it involved using "$" in various places and was a bit of an over-complex mess.

pattern matching is restricted to a single entry on the left (program) stack, which makes the matching there work in a similar way to "commands" in more traditional languages.

for otuto to work cleanly it was also important that many values "evaluated" to themselves. for example, for any numeric value:

{x | } => { | x}

this allowed expressions to be "entered" on the left. for example, the following is a possible evaluation sequence:

{ + 2 3 | }
{ + 2 | 3 }
{ + | 2 3 }
{ | 5 }

to support this there was syntax for quoting (again, complex and possibly implicit). the language also supported lists, with the expected nested pattern matching.

finally, otuto also supported a form of metaprogramming - the process described above was actually implemented within otuto by two (mutually recursive) commands that applied patterns to the two stacks (which were two lists on the data stack). this could then be modified to change the evaluation process.

(as far as i remember, rules were not first class (could not be created dynamically) in the first implementation, but that was not meant to be significant - i see no reason why they couldn't be so.)


here is a longer example from the original documentation:

The Queens Problem

Code to solve the Queens Problem (place 8 queens on a chessboard so that no two directly threaten each other).

Including 'oto.meta..concat enables support for concatenative programming (used in the body of the "if" block in report)

include 'oto.meta..concat

{ main } => { queens.start }

Here the semantics of the language are extended to include backtracking. -> marks a return point and <- discards values on the operation stack until a return point is found. All values are discarded too.

(in oto.meta
  { -> }
  { <- }
  { eval [-> o..] v }    => { | [o] [] }      (* return point *)
  { eval [<- -> o..] v } => { | [o] [] }      (* finish return *)
  { eval [<- _ o..] v }  => { | [<- o] v }    (* drop til -> *)
  { eval [<-] [] }       => { | [] [] }       (* done *))

The main body of code, in the queens namespace.

(in queens
  { start } => { new-x | [data 0 []] }
 where

Define a simple structure for the current search state. data is a marker at the start of the list of values. Accessors/modifiers are also defined.

  { data }
  { get-posns [data n p] } => { p }
  { get-depth [data n p] } => { n }
  { set-posns [data n _] p } => { | [data n p] }
  { set-depth [data _ p] n } => { | [data n p] }
  { inc-depth dta } => { set-depth dta + `1 get-depth dta }

The forwards search (backtracking below).

  (* x runs with depth *)
  { new-x dta } => { new-y `0 get-depth dta inc-depth dta }

  (* y involves a search *)
  { new-y 8 x dta } => { <- }
  { new-y i x dta } => { new-y + `1 i x dta -> new-xy | [x i] dta }

  { new-xy p dta } => { repeat extend p dta test-all p get-posns dta }
  { extend p dta } => { append get-posns dta p dta }
  { append [ps..] p dta } => { set-posns dta `[p ps] }
  { repeat dta } => { new-x dta report dta }

Report solution at depth 8 and backtrack.

  { report dta } => { if `[[] [print-posns `dta]] = `8 get-depth dta }
  { print-posns dta } => { <- \n print get-posns dta }

Test the current list of positions. Note backtracking on failure.

  { test-all p1 [] }       => { }
  { test-all p1 [p2 p..] } => { test-all p1 `[p] test p1 p2 }

  { same-row [x _] [X _] } => { if `<- = x X }
  { same-col [_ y] [_ Y] } => { if `<- = y Y }
  { same-dg1 [x y] [X Y] } => { if `<- = + x y + X Y }
  { same-dg2 [x y] [X Y] } => { if `<- = - x y - X Y }

  (* same row not needed as x increments *)
  { test p1 p2 } => { same-col p1 p2 same-dg1 p1 p2 same-dg2 p1 p2 })

Output (lists of (x, y) coordinates of the queens):

$ ./otuto/otuto -i examples queens-2.oto
[[0 0] [1 4] [2 7] [3 5] [4 2] [5 6] [6 1] [7 3]]
[[0 0] [1 5] [2 7] [3 2] [4 6] [5 3] [6 1] [7 4]]
[[0 0] [1 6] [2 3] [3 5] [4 7] [5 1] [6 4] [7 2]]
[[0 0] [1 6] [2 4] [3 7] [4 1] [5 3] [6 5] [7 2]]
[[0 1] [1 3] [2 5] [3 7] [4 2] [5 0] [6 6] [7 4]]
[[0 1] [1 4] [2 6] [3 0] [4 2] [5 7] [6 5] [7 3]]
[[0 1] [1 4] [2 6] [3 3] [4 0] [5 7] [6 5] [7 2]]
[[0 1] [1 5] [2 0] [3 6] [4 3] [5 7] [6 2] [7 4]]
[[0 1] [1 5] [2 7] [3 2] [4 0] [5 3] [6 6] [7 4]]
[[0 1] [1 6] [2 2] [3 5] [4 7] [5 4] [6 0] [7 3]]
[[0 1] [1 6] [2 4] [3 7] [4 0] [5 3] [6 5] [7 2]]
[[0 1] [1 7] [2 5] [3 0] [4 2] [5 4] [6 6] [7 3]]
[[0 2] [1 0] [2 6] [3 4] [4 7] [5 1] [6 3] [7 5]]
[[0 2] [1 4] [2 1] [3 7] [4 0] [5 6] [6 3] [7 5]]
[[0 2] [1 4] [2 1] [3 7] [4 5] [5 3] [6 6] [7 0]]
[[0 2] [1 4] [2 6] [3 0] [4 3] [5 1] [6 7] [7 5]]
...