This post explore some interesting ways procedures can be used to express algorithms and data abstractions in Motto programs.

Recursion

The following procedure solves the Towers of Hanoi problem with recursion:

> [c @ b @ a @ n @ 
   [n 1 - a c b hanoi
    Move disk from pole  a  to  b .s .c
    n 1 - c b a hanoi]
   n 0 gt when] 
   hanoi @

> 3 1 2 3 hanoi
Move disk from pole 1 to 2 
Move disk from pole 1 to 3 
Move disk from pole 2 to 3 
Move disk from pole 1 to 2 
Move disk from pole 3 to 1 
Move disk from pole 3 to 2 
Move disk from pole 1 to 2

The omnipresent stack makes it easy to visualize the shape of a recursive procedure. Let us try this with the classic factorial example:

> [.s n @  [n n 1 - fact *] n n 1 eq if] fact @

> 4 fact
4
4 3
4 3 2
4 3 2 1
24
> .c

> 10 fact
10
10 9
10 9 8
10 9 8 7
10 9 8 7 6
10 9 8 7 6 5
10 9 8 7 6 5 4
10 9 8 7 6 5 4 3
10 9 8 7 6 5 4 3 2
10 9 8 7 6 5 4 3 2 1
3628800
> .c

It is possible to prevent the stack from growing n steps deep by making the procedure iterative:

> [.s n @ f @ [f n * n 1 - fact-helper] f n 1 eq if] fact-helper @
> [1 swap fact-helper] fact-iter @

> 4 fact-iter
1 4
4 3
12 2
24 1
24
> .c

> 10 fact-iter
1 10
10 9
90 8
720 7
5040 6
30240 5
151200 4
604800 3
1814400 2
3628800 1
3628800
> .c

For repeatedly executing a piece of code we can also use the loop procedure. This will execute the code block on the top of the stack until the second value on the stack becomes false:

; Print "in loop" until user enter `quit`.
> [read quit eq not] ["in loop" display newline] loop
hello
in loop
blah
in loop
quit

Closures

A procedure is associated with an environment that contain references to non-local variables. A procedure together with such a referencing environment is known as a closure. The following is a simple example of a closure:

> [x @ y @ []] point @

A call to point will leave an empty procedure on the stack. Though this procedure contains no code to execute, it has an environment that refers to the values of x and y. The Motto virtual machine has an instruction called probe that allows us to access the variables in a closure. This instruction is invoked using a special dot notation.

> 10 20 point p @
> p.x p.y
20 10

A closure can also get computations done using its local state. The following updated version of point can construct new points by adding a value to its current coordinates:

> [x @ y @ 
   [a @ y a + x a + point2] new-point @ 
   []] 
  point2 @

> 10 20 point2 p2 @
> p2.x p2.y
20 10
> 100 p2.new-point p3 @
> p3.x p3.y
120 110

Closures can be used to implement abstract types. An abstract type reveals only its interface and hides all internal implementation details. This makes it easy to switch a type implementation without changing other parts of the program. In the above example, the point2 type has a simple interface: x, y and new-point. A new implementation of this type might choose to use a pair instead of two separate variable to store the coordinates, without disrupting the interface.

> [pair xy @ 
   [xy second] x @ 
   [xy first] y @
   [a @ xy first a + xy second a + point3] new-point @
   []] point3 @

> 10 20 point3 pp1 @
> pp1.x pp1.y
20 10
> .c
> 100 pp1.new-point pp2 @
> pp2.x pp2.y
120 110

A generic constructor procedure can be used to initialize the actual point type based on some input from the user:

> ;; Constructs a `point2` if user-input is `1`.
  ;; Constructs a `point3` on any other input.
> [ptype @ [point3] [point2] ptype 1 eq if] mk-point @

> 10 20 1 mk-point pt1 @
> 100 200 2 mk-point pt2 @
> pt1.x pt2.y
20 100 
> pt2.x pt1.y
200 10