“Procedures returning procedures” is an important idiom of Motto. Consider a simple procedure called complement that takes a predicate p and returns its inverse. The following code snippet demonstrates how complement could be used:

> [2 remainder 0 eq] def is-even
> 10 is-even
#t
> 3 is-even
#f
> @is-even complement def is-odd
> 3 is-odd
#t
> 2 is-odd
#f

Here we used complement to produce a new procedure which gives exactly the opposite result of is-even. complement itself is defined as:

> [def p [p not]] def complement

Another example:

> [def vowel a e i o u list vowel swap list-contains] def is-vowel
> @is-vowel complement def is-consonant
> a is-vowel
#t
> b is-vowel
#f
> b is-consonant
#t

Note: The value of a procedure can be extracted by preceding its name with an @. This is an alternative to value procedure-name.

Reference: On Lisp.

What does it mean when we say two objects are equal? It could mean that both objects point to the same location in memory or it could mean that both objects have the same structure. In Motto, the eq procedure defines the first type of equality and equal defines the second:

> "hello" def a
> a def b
> a b eq
#t
> a b equal
#t
> "hello" def c
> a c eq
#f
> a c equal
#t

Here both a and b point to the same location in memory. So eq return true. c, though structurally similar to a, points to a different location. So a c equal return true and a c eq return false.

As procedures are first-class objects in Motto, they too can be compared for equality:

> [2 *] def double1
> @double1 def double2
> @double1 @double2 eq
#t
> [2 *] def double3
> @double1 @double3 eq
#f

(If we prefix a procedure name with @, the procedure object bound to that name will be pushed to the stack. This is a short-hand for the compiler definition value and is similar to the #' operator in Common Lisp.).

As we can see, eq is consistent in its behaviour. What about equal? Let us try equal with the above procedures. It should return true for all comparisons as all the three procedures have the same internal structure:

> @double1 @double2 equal
#t 
> @double1 @double3 equal
#t

If we compare double1 to a procedure with the same behaviour but with slight structural changes, equal will return false:

> [def a 2 a *] def double4
> 10 double1 10 double4
20 20
> @double1 @double4 equal
#f

In a strict mathematical sense two functions are equal if for all possible inputs they produce the same output. This definition also assumes that the functions do not cause any side effects. It is easy to define a predicate for comparing two procedures in the context of a particular input:

> [def proc1 def proc2
   [proc1] reduce-intact def result1
   [proc2] reduce-intact def result2 
   .c ;; Clearing the stack is optional.
   result1 result2 equal] def equal-p
> 10 @double1 @double4 equal-p
> #t

equal-p take the definitions of two procedures and applies them to the values on the stack. If the results produced are the same, equal-p will return true. The test should be repeated with all possible inputs (if possible) to establish that the procedures are equal indeed.

A few more usage samples of equal-p:

> [*] def mult1
> [def n def e [n 0 gt] [e n 1 - set n] loop] def replicate
> [replicate [+] reduce] def mult2    
> 2 3 mult1
6
> 2 3 mult2
12
> 2 3 @mult1 @mult2 equal-p
#t
> [+] def add1
> 2 3 add1
5
> 2 3 @mult1 @add1 equal-p
#f

This post looks at how the performance of deeply recursive procedures can be improved in Motto.

Let us start with the simple implementation of a procedure to calculate Fibonacci numbers:

> [def n n 0 eq ? 0 [n 1 eq ? 1 [n 1 - fib n 2 - fib +]]] def fib
> 5 fib
5
> 10 fib
55 
> 20 fib
6765

20 fib makes more than 20000 recursive calls. On my machine, It took almost 700 milliseconds to run. There are three ways to make this run faster.

Iteration

A dramatic improvement in speed can be achieved by using iteration:

> [def n 
   0 def a 
   1 def b 
   0 def i
   [i n lt] [a def tmp 
             b set a 
             b tmp + set b 
             i 1 + set i] loop
  a] def fib
> [20 fib] time!
2 ms real time
...
6765

Memoization

If the algorithm is not amenable to iteration, we can cache the results. Subsequent calls can return the result from the cache and avoid a costly re-computation. Here we optimize the fib procedure by storing all computed Fibonacci numbers in a map.

> mk-map def fib-memo
> [-1 swap fib-memo map-get] def get-fib
> [fib-memo map-put] def set-fib
> 0 0 set-fib
> 1 1 set-fib    

> [def n 
   n get-fib -1 eq ? 
   [n n 1 - fib n 2 - fib + set-fib n get-fib] 
   [n get-fib]] def fib

;; tests.

> [20 fib] time!
3 ms real time
...
> [20 fib] time!
0 ms real time
...

The number of recursive calls came down to 38 for the first instance and there were none for the second. Of course, the cache takes up additional memory and that is the price paid for the increased speed.

Virtual Machine definitions

If you want a fast recursive procedure, without trading memory, you can add fib as a Virtual Machine definition. That means you have to write the procedure in Scheme and make it callable from Motto:

> (define (fib n)
    (cond 
      ((= n 0) 0)
      ((= n 1) 1)
      (else
        (+ (fib (- n 1)) (fib (- n 2))))))

 > ;; Make `fib` accessible to Motto programs.
 > (def 'fib
     (lambda (vm stack)
       (stack-push (stack-pop stack) (fib (stack-top stack)))))
 > [20 fib] time!
 23 ms real time
 ...

If you have programmed in Java, you can think of this as making a safe JNI call, i.e, calling a fast low-level routine without the risks of segmentation faults, VM crashes etc.

The implementation of Motto require some improvements to make recursive calls more efficient. Having a mutable data stack will help a lot. The entire VM, or at least parts of it should be reimplemented in a systems language. But its another project, another story!

As the syntax of a Motto program is dictated by the programmer himself, it is easy to transform it to support languages other than English. The following example re-defines some built-in Motto procedures in Greek and use them to write a simple program.

First we need the Greek versions of def, eq and display:

> (cdef 'ορίζουν (lambda (self)
              (list (c-push (get-symbol (compiler-input self)))
                    (c-def))))

> [eq] ορίζουν ίση
> [display] ορίζουν οθόνη

Next we define a new procedure that will say a greeting based on an English input. If the input is “hi” it will print the Greek equivalent of “hello”, otherwise it will print the Greek equivalent of “bye”:

> [hi ίση ? γειά-σου αντίο .s .c] ορίζουν χαιρετώ

> hi χαιρετώ
γειά-σου
> see-you χαιρετώ
αντίο

I don’t know Greek. So I used on Google for translation. If you know Greek and find some problem with the translation used here, please let me know.