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 .s .c
#t
> a b equal .s .c
#t
> "hello" def c
> a c eq .s .c
#f
> a c equal .s .c
#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
> value double1 def double2
> value double1 value double2 eq .s .c
#t
> [2 *] def double3
> value double1 value double3 eq .s .c
#f

(The compiler definition value is used to put the procedure object on the stack without executing it. This 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:

> value double1 value double2 equal .s .c
#t
> value double1 value double3 equal .s .c
#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 .s .c
20 20
> value double1 value double4 equal .s .c
#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 value double1 value double4 equal-p .s .c
> #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 .s .c
6
> 2 3 mult2 .s .c
12
> 2 3 value mult1 value mult2 equal-p .s .c
#t
> [+] def add1
> 2 3 add1 .s .c
5
> 2 3 value mult1 value add1 equal-p .s .c
#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 .s .c
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! .s .c
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 optimise 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 re-implemented 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 .s .c
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 .s .c
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 .s .c
70
> 100 c set
> c .s .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 .s .c
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 .s .c
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 .s .c
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 .s .c
30

Virtual Machine definitions

Just 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
> .s
2 4 6 8 10

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.

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
> .s ; print the result which is now on the top of the stack.
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
> .s
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
> .s .c
24

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

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
> .s .c
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 .s .c
20 10
> 100 p2.new-point p3 @
> p3.x p3.y .s .c
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 .s .c
20 10
> 100 pp1.new-point pp2 @
> pp2.x pp2.y .s .c
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 .s .c
20 100
> pt2.x pt1.y .s .c
200 10

This is a quick overview of the composite data types in Motto.

The data stack

Any value typed at the REPL is automatically pushed to the stack. Here are some basic stack operations:

> 10 20 30 .s ;; Push three numbers to the stack and `show` them
10 20 30
> .p ;; Pop the stack
> .s
10 20
> .c ;; Clear the stack
> 100 20 78 32 12 [*] reduce
> .s .c
59904000
> ;; Find the mean of all numbers on the stack:
> 6 11 7 length c @ [+] reduce c / .s .c
8
> red green blue
> ;; Check if the stack contains a particular value:
> red contains display
#t
> ;; The stack can be used as a key-value store:
> name: sam age: 20
> name: get display
sam
> age: get display
20

The stack does away with the need to pass arguments explicitly to procedures. Procedures can leave any number of results on the stack. As an example, let us define a procedure for computing the mean of a list of numbers:

> [length count @ [+] reduce-intact count quotient] mean @
> 6 7 11 mean display .c
8
> 10 20 30 40 50 60 mean display .c
35

Mean is one of many averages that can be derived from a sequence of numbers. We can also define procedures to compute other averages like median, mode and range. There can be a single procedure that is used to aggregate all these averages together:

> [[gt] sort
   length len @
   len 2 quotient mid @
   len is-odd ? [mid at] [mid at mid at + 2 quotient]]
  median @

> [most-occurs] mode @

> [[max] reduce-intact mx @
   [min] reduce-intact mn @
   mx mn -] range @

> [median avg_median @
   mean avg_mean @
   mode avg_mode @
   range avg_range @
   .c
   median: avg_median
   mean: avg_mean
   mode: avg_mode
   range: avg_range]
  averages @

> ;; tests
> 1 2 4 4 5 8 9 averages .s .c
median: 4 mean: 4 mode: 4 range: 8
> 80 100 62 180 21 55 averages .s .c
median: 71 mean: 83 mode: 21 range: 159

Each average could be retrieved separately using get:

> 3 5 12 averages
> median: get display
5
> mean: get display
6
> range: get display
9
> mode: get display
3
> .s .c
median: 5 mean: 6 mode: 3 range: 9

fetch is similar to get, but after retrieving the value, it removes the mapping from the stack. In the last post we saw how to use get to implement a procedure that take keyword arguments. Here we will redefine that procedure to use fetch so that the arguments are actually consumed by the procedure. In fact, having an extended form of fetch that can return a default value will be more useful here:

> ;; Extended form of `fetch` that accepts a default value.
> [key @ default @ key fetch dup key eq default swap if] fetch-d @

> ;; Procedure to compute distance between two points. If an argument is not
  ;; specified, it will default to 0.
> [0 x2: fetch-d 0 x1: fetch-d - 2 expt
   0 y2: fetch-d 0 y1: fetch-d - 2 expt
   + sqrt] distance @

> x1: 10 x2: 5 y1: 100 y2: 120 distance .s .c
20.615528128088304
> x1: 10 x2: 5 distance .s .c
5

Pair and List

As the name suggests pair is a composite of two values.

> 10 20 pair .s
(10 . 20)
> dup first .s
(10 . 20) 10
> swap second .s
10 20

It is possible to construct a list by making a pair point to another:

> 10 20 30 40 50 [pair] reduce
> .s
(10 20 30 40 . 50)

Motto has a built-in list type. The values on the stack can be wrapped up in a new list using the list procedure:

> 10 20 30 40 50 list lst @
> lst .s
(10 20 30 40 50)

> list-length .s .c
5
> lst list-first lst list-rest .s .c
10 (20 30 40 50)
> lst list-reverse .s .c
(50 40 30 20 10)

> hello lst list-push .s .c
(hello 10 20 30 40 50)
> hello lst list-append .s .c
(10 20 30 40 50 hello)

> [2 * display #\space display] lst list-for-each .s .c
20 40 60 80 100

> ;; The `map` function from Lisp:
> [list-for-each list] list-map @
> [2 *] lst list-map .s .c
(20 40 60 80 100)

Array

Arrays are more efficient than lists for some operations, especially for accessing an arbitrary element. There are two ways to create an array. Either by using the array procedure or by typing in an array literal:

> a b c d array .s .c
#(a b c d)

> ; An array literal.
> #(1 2 3 4 5) .s .c
#(1 2 3 4 5)

> a b c d array arr @
> 0 arr array-at .s .c
a
> hello 0 arr array-set .s .c
#(hello b c d)
> arr .s .c ; array-set modifies the array.
#(hello b c d)
> #(1 2 3 4) #(hello world) array-append .s .c
#(1 2 3 4 hello world)
> array-length .s .c
6

String

Strings are sequences of characters.

> "hello, world" s @
> 1 s string-at .s .c
#\e
> 3 5 s substring "lo" string-eq .s .c
#t
> 3 5 s substring "LO" string-eq .s .c ; `string-eq` is case-sensitive.
#f
> 3 5 s substring "LO" string-ci-eq .s .c
#t

> ; split the string using comma as the delimiter.
> #\, s string-split .s .c
("hello" " world")
> ; use space as the delimiter.
> #\space s string-split .s .c
("hello," "world")

> ; search for a substring.
> "hello" s string-find .s .c
0
> "hullo" s string-find .s .c
#f
> "hEllo" s string-find .s .c
#f
> "hEllo" s string-ci-find .s .c
0
> "llo" s string-find .s .c
2

Map

Map is a data structure that acts like a dictionary, where a value is associated with a key. symbols and keywords are the most natural candidates for keys.

> name: mat age: 45 map m @
> name: m map-at .s .c
mat

> ; `map-at` will raise an error if the key is not found.
> salary: m map-at .s .c
#<$error #3 tag: value-not-found message: "Value not found.">

> ; `map-get` allows to pass a default value for a missing key.
> 1450 salary: m map-get .s .c
1450
> salary: 5000 m map-put
> 1450 salary: m map-get .s .c
5000

A map can stand-in for the switch-case control structure found in many imperative languages:

> [signal @
   red [stop! .s .c] green [go! .s .c] yellow [be ready .s .c] map signals @
   ["not a valid signal" error .s .c] signal signals map-get !]
  signal-action @

> red signal-action
stop!
> yellow signal-action
be ready
> green signal-action
go!
> black signal-action
#<$error #2 tag: error message: "not a valid signal">
> red signal-action
stop!

This post will introduce the atomic data types in Motto.

Numbers

Various types of numbers supported by Motto are – complex, real, rational and integer.

> 3+4i ;complex
> 3.14 ;real
> #e1e10 ;real
> 6/10 ;rational
> 300 ;integer

There are predicates that can recognize the accurate type of a number:

> -2.5+0.0i is-complex .s .c
#t
> -2.5+0.0i is-real .s .c
#f
> 6/10 is-rational .s .c
#t
> 3 is-integer .s .c
#t

A number can have these radix prefixes: #b (binary), #o (octal), #d (decimal), and #x (hexadecimal). With no radix prefix, a number is assumed to be decimal.

Some operations with numbers:

> 34 number-to-string .s is-string .s .c
34
#t
> ;convert to base 2 representation.
> 2 34 number-to-string-r .s .c 
100010
> ;convert a string in base 16 representation to an integer.
> 16 "#xFFE" string-to-number-r .s .c 
4094 
> 10 factorial .s .c
3628800     
> 100 sqrt .s .c
10
> ;generate a random number between 1 and 10.
> 10 random-integer .s .c 
8
> ;generate a random number between 0 and 1.
> random-real .s .c 
.8574025375628211

A division by zero will return the special symbol +nan.0 which means “Not A Number”. Any arithmetic operation with this value will return +nan.0. The symbols +inf.0 and -inf.0 represent positive and negative infinities.

Boolean

The literals #t (true) and #f (false) are used to represent Boolean values. Procedures that return Boolean values are known as predicates. There are built-in predicates for comparing two objects on the stack:

> 4 3 gt .s .c ;greater than.
#t
> 4 3 lteq .s .c ;less than or equals.
#f
> 10 10.00001 eq .s .c ;equality
#f
> red red eq .s .c ;eq works for symbols too.
#t 
> "red" "red" eq .s .c ;but not for strings.
#f 
> "red" "red" string-eq .s .c 
#t

The if procedure can be used to conditionally execute code based on a Boolean value at the top of the stack. For example, the following procedure will print stop if the signal is red:

> [start stop rot red eq if .s .c] manage-traffic @ 
> red manage-traffic                              
stop 
> green manage-traffic
start

When manage-traffic is invoked the first time, there are four values on the stack:

red start stop red

The call to rot will transform the stack like this:

start stop red red

Now eq will leave #t on the stack:

start stop #t

As the top value is #t, if will leave stop on the stack and drop start. If the top value is #f, it will drop the next value (stop) instead. (I will discuss control structures in detail in a future post.).

Character

A character literal is preceded by #\. Characters are Unicode encoded. As Motto internally uses the Scheme read procedure to parse its input, it can recognize special character literals like #\space and #\newline.

> #\a #\a char-eq .s .c
#t
> #\a #\A char-eq .s .c
#f
> ;compare by ignoring case.
> #\a #\A char-ci-eq .s .c 
#t
> ;get the UNICODE encoding of the character.
> #\c char-to-integer .s .c 
99

Symbol

A symbol is a unique identifier. It can be used as constants, variable names etc. The following code block declares a list of symbols to represent the months in a year.

> [jan feb mar apr may jun jul aug sep oct nov dec] months @
> months .s .c 
jan feb mar apr may jun jul aug sep oct nov dec

It is easy to check the stack for a particular symbol using the contains predicate:

> [months 12 at 13 remove-at contains no yes rot if println .c] is-month @
> [display newline] println @
> jan is-month
yes
> aug is-month
yes
> blah is-month
no

Symbols with a colon at the end are called “keywords”. (A colon by itself is not a keyword, it is a symbol.). Keywords are similar to symbols but are self evaluating and distinct from the symbol data type. They can be used for specifying key-value pairs and to pass named arguments to procedures:

> name: sam age: 34
> name: get display ; get helps us to retrive a value mapped to a key.
sam
> age: get display
34

The following procedure which computes the distance between two points on a Cartesian Plane accept keyword arguments, so the order in which the arguments are passed becomes irrelevant:

> [x2: get x1: get - 2 expt y2: get y1: get - 2 expt + sqrt] distance @  

> x1: 10 y1: 20 x2: 34 y2: 21 distance display .c
24.020824298928627
> x1: 10 y2: 21 x2: 34 y1: 20 distance display .c
24.020824298928627

The next post will explore the composite data types in Motto.

Motto is a practical syntax weak language in the tradition of Forth and Lisp. This post introduces the kernel of Motto where syntax is used only for identifying literals.

You can evaluate simple program statements in the Motto REPL:

motto v0.0

> "hello, world" .s
hello, world
> ; this is a comment.
> 34 6.23 
> #\a #\b #\c ;characters
> #t #f ;boolean values
> .s
> hello, world 34 6.23 a b c #t #f
> .c

Values we enter at the REPL is pushed to a data stack. The command .s shows the stack and .c clears it. You can also type commands or procedures that does something with the values on the stack. Procedures leave their result(s), if any, on the stack. For example, the built-in arithmetic procedures +, -, /, and * – consume two numbers from the stack and push the result back to the stack:

> 4 5 + .s
9
> 10 * .s .c
90
> 45 2 rem .s .c
1
> 45.89 5 / .s .c
9.178
> 943423792472394723947234927 323231313 * .s .c ;numbers could become very large!
304944111156291662875737288173669151

In short, programming in Motto is based on a simple rule: Push values to the data stack and issue commands (procedures) that does something with those values.

A basic type in Motto is the symbol. A symbol is the same as a string, but is not enclosed in double quotes. The following are all valid symbols:

> red green blue |a symbol with spaces|

A symbol is unique within the Motto virtual machine. So it can be used as a descriptive identifier for a literal. A value on the stack is bound to a symbol so that it can be recalled later using this descriptive name. The bind procedure (represented by a @) binds a value to a symbol:

> 3.14159265 PI @

Here the value 3.14159265 is bound to the symbol PI. We can use this symbol wherever we need the value of pi. For example, the following statement calculates the area of a circle with radius 100.897:

> PI 100.897 dup * * .s
31982.055975130526

The dup procedure duplicates the top of the stack. The actual code that gets executed here is 3.14159265 100.897 100.897 * *.

Execution can be delayed by enclosing program statements in square brackets. Such suspended pieces of code are called code blocks:

> ["hello, world" .s .c]

The above statement creates a code block. If you display the stack now, you can see the compiled version of this code block sitting on the stack:

> .s
#<$proc #2 env: #f binding-env: #<$env #3 parent: #<$env #4parent: #f definitions: #<table #5>> definitions: #<table #6>> opcode: ((1 . "hello, world") 32 31)>

The bang procedure (represented by !) is used to execute a code block that sits at the top of the stack:

> !
hello, world

Code blocks are first class types like strings and numbers. So they can be bound to symbols. A code block that is bound to a symbol is called a procedure. Let us define a procedure that calculates the area of a circle. This procedure will consume the top value on the stack and use it as the radius:

> [dup * PI *] area-of-circle @
> 45.78 area-of-circle .s .c
6584.17626524826
> 100.897 area-of-circle .s .c
31982.055975130526

Notice that a procedure is automatically executed by Motto. We need the bang procedure only for executing unbound code blocks.

In future posts I will cover:

1. data types – number, character, boolean, string, list, array, map etc.
2. procedural abstractions – recursion, closures.
3. dynamically extending the compiler and virtual machine.

Before we conclude, here is a glimpse of the higher-order programming facilities provided by Motto:

> ;computing area of many circles in one go...
> 45.32 12.78 90 78 [area-of-circle] apply .s
6452.524683657361 513.1113009762599 25446.900465000002 19113.4496826
> ;...add them together...
> [+] reduce .s
51525.98613223362

This post describes a simple job scheduler. Each job description consists of a procedure and some ticks into the future. The scheduler will pick up the job after the given ticks (seconds) and run the procedure. A job description is represented using the following structure. (All code in Spark-Scheme.):

(define-struct job (run-at proc))

There is a fixed size vector that is used to store the jobs.

(define max-jobs 10)
(define jobs (make-vector max-jobs ()))

The index on which a job get stored is calculated as:

(remainder (+ (current-seconds) ticks) max-jobs)

The job is added to a list at the resulting index. The following procedure contain the complete logic for scheduling a job:

(define (schedule-job ticks job-proc)
  (let* ((run-at (+ (current-seconds) ticks))
         (job (make-job run-at job-proc))
         (index (remainder run-at max-jobs))
         (q (vector-ref jobs index)))
       (vector-set! jobs index (cons job q))))

The scheduler wakes up for each second and run all the jobs scheduled for that second. If the current list has jobs that are scheduled to run in the future, they are left back to be executed later:

(define (scheduler)
  (sleep 1)
  (run-jobs (current-seconds))
  (scheduler))

(define (run-jobs now)
  (let* ((index (remainder now max-jobs))
         (q (vector-ref jobs index)))
    (let loop ((old-q q) (new-q ()))
      (if (not (null? old-q))
          (let ((job (car old-q)))
            (if (run-job job now)
                (loop (cdr old-q) new-q)
                (loop (cdr old-q) (cons job new-q))))
          (vector-set! jobs index new-q)))))

 (define (run-job job now)
   (if (<= (job-run-at job) now)
       (begin
         (thread (job-proc job))
         #t)
       #f))

The scheduler runs in its own thread:

(define (run-scheduler)
  (thread scheduler))

A test run of the scheduler:

> (run-scheduler)
> (schedule-job 5 (lambda () (printf "group1 job1~n") (flush-output)))
> (schedule-job 5 (lambda () (printf "group1 job2~n") (flush-output)))
> (schedule-job 15 (lambda () (printf "group3 job1~n") (flush-output)))
> (schedule-job 10 (lambda () (printf "group2 job1~n") (flush-output)))
;; after 5 seconds:
group1 job1
group1 job2
;; after 10 seconds:
group2 job1
;; after 15 seconds:
group3 job1

Reference: The Design and Implementation of the FreeBSD Operating System.