Over the last couple of weeks a lot of redesign and reimplementation has happened in Motto .
All posts tagged "motto" and "motto-tips" are now irrelevant. (They might contain useful information, but most of the code samples will not work). I plan to upload new documentation/screencasts to the Motto web site itself.
Python has a max function for the list type. Here is how you would use it:
max([3, 2, 1, 5, 0]) => 5
max can take an optional key argument which specifies a one-argument
ordering function:
max([3, 2, 1, -5, 0], key=abs) => -5
Here max is asked to use the absolute value of the elements to find
the maximum. The absolute value
of -5 is 5 thus making -5 the highest value in the list.
Motto do not have a built-in max function
for lists. It has
a max that return the largest of two numeric values:
3 5 max => 5
Using max along with the list-reduce procedure will give us a
list-max similar to that in Python:
[def lst @max lst list-reduce] def list-max 3 2 1 5 0 list list-max => 5
It is possible to write a more generic procedure that takes the
ordering function too as an argument.
Let us call it list-pick:
[def ord-fn def lst @ord-fn lst list-reduce] def list-pick 3 2 1 5 0 list @max list-pick => 5 3 2 1 -5 0 list @max list-pick => 3 [def a def b a abs b abs gt ? a b] def abs-max 3 2 1 -5 0 list @abs-max list-pick => -5
The switch statement is a selection control construct found in
popular programming languages.
The following C++ code snippet demonstrates the syntax of switch in
that language:
#include <iostream> enum TrafficSignal { RED, GREEN, YELLOW }; void respond_to_signal (TrafficSignal ts) { switch (ts) { case RED: cout << "stop!" << endl; break; case GREEN: cout << "go!" << endl; break; case YELLOW: cout << "caution!" << endl; break; default: cout << "invalid signal." << endl; } } int main () { respond_to_signal (YELLOW); // => caution! respond_to_signal (RED); // => stop! respond_to_signal (GREEN); // => go! respond_to_signal (static_cast (100)); // =>invalid signal. return 0; }
Is it possible to translate this code to
Motto, a language weak in syntax?
One solution is to exploit the built-in map data structure:
> red stop! green go! yellow caution! map def traffic-signals > [invalid-signal swap traffic-signals map-get] def respond-to-signal
More than 17 lines of C++ code was compressed to just 2 lines and it works well:
> yellow respond-to-signal caution! > red respond-to-signal stop! > green respond-to-signal go! > blah respond-to-signal invalid-signal
Now let us consider a problem from the realm of Objects – designing an Object
Factory. An initial
implementation in C++ will depend on the switch statement to choose
the right factory, based on some unique identifier:
ShapesFactory* get_factory (ShapeId s)
{
switch (s)
{
case CIRCLE:
return CircleFactory::get_instance ();
break;
case SQUARE:
return SquareFactory::get_instance ();
break;
default:
throw "Invalid object id."
}
}When a new shape is added to the system the code should be modified and recompiled. If faced with a similar problem a Motto programmer would think of a map of object ids to constructors. The program need not be recompiled to support new classes. New object factories can be registered with the factory as the program runs. Here is an implementation of this idea:
;; A ShapesFactory. [mk-map def shapes ;; Method: register. ;; Maps an object id with a constructor. ;; Returns true on success, false if the object id ;; is already registered. [def class def id id shapes map-at is-error ? [id [class] shapes map-put #t] #f] def register ;; Method: create. ;; Accepts an object id and returns a new object ;; by invoking the appropriate constructor from the map. [shapes map-at dup is-error ? [.p #f] [!]] def create []] def ShapesFactory ;; A global `factory` object to be used by all ;; shape classes. ShapesFactory def factory
This is how new Shape classes are registered with the factory:
;; Various Shapes classes:
[def r
[circle] def type
[pi r r * *] def area
[]] def Circle
1 def CIRCLE
CIRCLE @Circle factory.register #t assert ;; assert will fail if the
;; object id is not unique.
[def s
[square] def type
[s s *] def area
[]] def Square
2 def SQUARE
SQUARE @Square factory.register #t assert
;; Check if the factory construct correct objects:
10 CIRCLE factory.create def c
25 SQUARE factory.create def s
c.type display-nl ;; => circle
s.type display-nl ;; => square
c.area display-nl ;; => 314.1592653589793
s.area display-nl ;; => 625
;; New classes can be registered on-the-fly.
[def h def w
[rectangle] def type
[w h *] def area
[]] def Rectangle
3 def RECTANGLE
RECTANGLE @Rectangle factory.register #t assert
10 20 RECTANGLE factory.create def r
r.type display-nl ;; => rectangle
r.area display-nl ;; => 200Lack of syntax is not a weakness. It can lead to elegant solutions!
This post is about lazy evaluation in Motto. As everything else, lazy evaluation can be accomplished without adding new syntax to the language. Code blocks and the bang (!) procedure is all that we need. As an example, consider the following procedure that generates an infinite sequence of numbers:
> [def n [n n 1 + integers]] def integers
integers is a procedure that returns a
procedure.
The returned procedure, when executed, will leave a copy of the
argument on the stack and call
integers again with the argument incremented by 1. This will leave
a new procedure on the stack
that will return this incremented value and so on. All this happens
with no explicit management and
modification of state. Let us see how integers can be used to
produce a sequence, given a value to
start with:
> 10 integers ! ! ! ! ! ! .p 10 11 12 13 14 15 > .c ;; or using the `times` procedure: > 0 integers [!] 10 times .p 0 1 2 3 4 5 6 7 8 9
The following procedure shows how we could transform a lazy sequence by filtering out elements using a predicate:
> [def predic
[! def n def i self def next-i
i predic ? [i @n] [@n next-i]]] def filter
;; Filter even integers out:
> 0 integers @is-odd filter def p [p] 10 times .p
1 3 5 7 9 11 13 15 17 19
> .c
;; Filter odd integers out:
> 0 integers @is-even filter def p [p] 10 times .p
0 2 4 6 8 10 12 14 16 18(This example is based on the code in Section 4.2.5 of R7RS.).
“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.
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
...
6765If 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.
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!
If you have programmed in an imperative programming language, you might have noticed the absence of an assignment operator in Motto. This is because the kernel of Motto is a purely Functional language. The Motto virtual machine has the capability to update a variable. It is just not exposed to the outside world. Before I show you how to expose it, let me explain why Motto cannot have an assignment operator based on its simple stack-based programming model.
A symbol bound to a value, is evaluated to that value:
> 100 a @ > a 100
As a Motto procedure always follow its arguments, we cannot have an “assignment” procedure because
all it will see on the stack is the value, not the symbol. So we need to add a facility to handle
this special case. We need a procedure that precedes its argument or at least one of its arguments.
This can be accomplished by writing a compiler definition, i.e, a procedure executed by the compiler.
This procedure will read the symbol from the input and emit virtual machine instructions to assign
the previous value on the stack to that symbol. As this special procedure is executed by the compiler, it has to be
written in the language the compiler itself is written. The Motto compiler and virtual machine is
written in Scheme, a dialect of Lisp.
Especially, we use a Scheme implementation called Gambit-C
which has the ability to generate highly-optimized executable programs for a variety of platforms.
Let us call our assignment procedure set and add its definition to the Motto compiler:
> (cdef 'set (lambda (compiler)
(list (c-push (get-symbol (compiler-input compiler)))
(c-set))))cdef maps the Scheme symbol set to a Scheme procedure (a lambda form).
The Motto virtual machine consumes lists of instructions.
Here the compiler will read a symbol from the input stream and emit the instruction to push
that symbol to the stack. This instruction is followed by a set bytecode which will assign
the value already on the stack to the symbol:
> 140 set a > a 140
In fact, Motto comes pre-packaged with set and a few other useful compiler definitions:
> 20 def b ;; defines a new variable. > 50 def a ;; re-defines the existing variable `a`. > a b + def c > c 70 > 100 c set > c 100
The use of def and set becomes more evident when we have to deal with non-local variables:
> 100 def x > 200 def y > [x y .s .c] ! 100 200 > x y 100 200 > ;; In the following code block, `set` will update the global variable `x`, while ;; `def` will declare a new local variable `y`. > [300 set x 500 def y x y .s .c 600 set y x y .s .c] ! 300 500 300 600 > ;; `x` was changed by the procedure, while `y` stays intact ;; as the procedure modified its local definition of `y`. > x y 300 200
There are compiler definitions to load and compile Motto source code files. For example, here is a simple Motto script – hello.m:
;; file: hello.m [hello world .s .c] def say-hello
This can be imported to the interpreter:
> import "hello.m" > say-hello hello, world
The interpreter will compile the script before executing it. The script can be explicitly compiled and stored in an object file for faster loading:
> compile "hello.m" > import "hello.mo" > say-hello hello, world
Another useful compiler definition is probe which can be used to look-up a value in an
anonymous closure:
> 100 200 [def x def y []] ! dup probe x swap probe y 200 100
Compiler definitions can be used to optimize some computations by executing them at compile-time and inserting the result into bytecode. An example can be seen here. Most of the basic operations in Motto are compiler definitions. You can extend the compiler with your own definitions or change the behavior of existing definitions. For example, arithmetic procedures can be re-defined to make Motto do infix arithmetic:
> (cdef '+ (lambda (compiler)
(list (c-push (get-number (compiler-input compiler)))
(c-arith '+))))
> 10 + 20
30Just like the compiler, the virtual machine can also be extended with definitions written in Scheme.
These definitions are executed at runtime, like normal Motto procedures. A virtual machine definition
is a lambda expression that takes two arguments:
the current instance of the virtual machine and a reference to the data stack. This lambda should
return a new data stack. A virtual machine definition is introduced using the def Scheme procedure.
The following sample shows a VM definition that squares all numbers on the stack. It first converts
the stack to a list and uses the Lisp map function to produce a list of squares. This list is then converted
to a stack and returned. (Conversions between the data stack and Scheme lists are not expensive,
because the current implementation of Motto uses a Scheme list as its data stack!).
> (def 'sqr-all
(lambda (vm stack)
(list->stack (map (lambda (x) (* x 2))
(stack->list stack)))))
> 1 2 3 4 5 sqr-all
2 4 6 8 10As 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.
This post explore some interesting ways procedures can be used to express algorithms and data abstractions in Motto programs.
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 2The 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
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
