Ideas for a startup from Paul Graham: http://ycombinator.com/ideas.html
Two well written books on Forth by Leo Brodie (Starting Forth and Thinking Forth) ignited my desire to explore the territory of concatenative programming languages. In an attempt to understand them better, I decided to implement an interpreter for a Forth like language. I will describe this new language here. It is called Blithe. The interpreter is implemented in Spark. It can be easily ported to other Schemes. A better, complete compiler should be written in a systems language like C. That will be an interesting, rewarding hobby project in it’s own right!
Blithe has heavy influences from both Forth and Lisp. It has postfix notation. While functional languages are based on the application of functions to arguments, concatenative languages are based on the composition of functions. There are no formal function parameters. Instead all functions take a stack as argument and produce a stack as result. A function can take any number of arguments and return any number of values. The output of one function becomes the input of another. This relationship is expressed by juxtapositioning functions. The absence of formal parameters and expression of function composition by juxtapositioning has an important consequence – programs look like English sentences. So it is not without a reason that in Blithe parlance functions are called “words” and code libraries are called “vocabularies”.
Let us get a feel of Blithe by running some small computations. When you fire up the Blithe interpreter, you get a prompt like this:
This is the interactive Blithe shell.
Type `bye' to exit.
Enter the following two lines at the prompt. (=> denotes a result).
"Add two numbers" .
2 3 + .
=> 5
The first line is a comment. Blithe do not have special syntax for comments. All comments are string literals, followed by a dot. The dot makes sure that the string literal is popped from the stack. The real computation comes next. There, you pushed two integers – 2 and 3 – on to the top of the stack. + is the word that adds the top two elements of the stack. When the interpreter encounters a word, it is applied to the values on the stack. A word will consume only the values that it actually needs. The rest of the stack is kept untouched. + will pop the first two integers, add them and push the result to the stack. The special dot operator (.) pops the top element off the stack, printing the result on the shell. (Use ^ or drop if u don’t want to print the value). Blithe comes with quite a few built-in words, including the usual ones for manipulating the data stack. Here are a few common stack operations:
1 2 3 4 5 "Push 5 numbers on the stack" .
depth . "Prints the size of the stack" .
=> 5
.S "Show the stack along with it's size" .
=> 5
swap "Swaps the top two elements" .
.S
=> 5 < 5 4 3 2 1 >
dup "Duplicates the top element" .
.S
6 < 5 5 4 3 2 1 >
rot "Rotates the top element with the third" .
.S
6 < 4 5 5 3 2 1 >
drop "Removes the top element" .
.S
5 < 5 5 3 2 1 >
Blithe can be extended by defining new words. The colon(:) operator is used for this purpose. The definition of a word should be terminated by a semi-colon. Here is a simple word that squares the top element on the stack:
: sqr dup * ;
It duplicates the top of the stack and applies the multiplication function.
5 sqr .
=> 25
100 sqr .
=> 10000
25 sqr
Blithe is an interactive language. You can save the state of the whole Blithe system to a file. You can later continue from that point. This is much similar to using virtual machine images in Smalltalk:
"Save and quit Blithe" .
save
bye
Later, we load the system image and continue from where we stopped:
load
.
=> 625
You can use a word even before it is defined. This facilitates both top-down and bottom-up development. A classic Forth example is an embedded program that controls a washing machine. An over simplified version of this can be coded in Blithe as:
: washer wash spin rinse spin done ;
: wash "Washing ..." . 3 sleep ;
: spin "Spinning ..." . 2 sleep ;
: rinse "Rinsing ..." . 2 sleep ;
: done "Done." . newline ;
Here is a sample run of the program:
"Run the washing machine!" .
washer
Washing ... Spinning ... Rinsing ... Spinning ... Done.
We wrote the high-level word ”washer” first. It is the public interface of the washing machine controller. The component words are defined later. Delay in the actual working of the washing machine is simulated using the “sleep” built-in word. You can also write the software in the reverse order, bottom-up, by defining the component words first.
Words can be grouped under ”vocabularies” (modules, libraries or namespaces in other languages). Let us place the washing machine words in a vocabulary called “washing-machine” so that they won’t conflict with pre-existing words:
"washing-machine" vocabulary
: washer wash spin rinse spin done ;
: wash "Washing ..." . 3 sleep ;
…
The default vocabulary is called “system”. We can switch back to the default vocabulary any time we want, but the words defined for washing machine won’t be visible there:
"system" vocabulary
wash
Error: wash - word not found.
Data types and variables: Blithe has integers, floats, unicode strings and Lisp like symbols. Boolean values are represented by #t and #f. There are C like comparison operators and basic string functions. There are words to do bitwise and arithmetic shift operations.
Symbols are used to represent variable names. A value is assigned to a variable using the ! operator. The value of a variable can be pushed on to the stack using the @ operator.
"Assign a string to a variable" .
"Vijay Mathew" 'name !
"Get back the value of 'name" .
'name @ .
=> Vijay Mathew
Lisp like pairs are supported. They can be used to create complex data structures. The following code constructs a name-age pair and stores it in a variable. Later we extract the pair using the words first and second:
35 "Anna" pair 'name-age !
'name-age @ first .
=> Anna
'name-age @ second .
=> 35
Blithe also makes it easy to document and access help on words.
The following code demonstrates this feature:
"Finds the square of a number." 'sqr doc
: sqr dup * ;
The doc word updates the documentation dictionary by mapping the name of the word to a string. Later this documentation can be accessed using the help word.
'sqr help .
=> Finds the square of a number.
To understand the complete capabilities of Blithe, please look at the source code of the Blithe interpreter (blithe.ss), especially the execute procedure.
References:
Two popular cancatenative programming languages, Factor and Joy.
Let me present a concurrent, message passing programming framework implemented as part of the Spark project. (By the way, Spark is my own Scheme programming environment). I was profoundly influenced by Alan Kay’s short and clear definition of OOP:
OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.
Anyone who is familiar with closures know how to create objects that can “retain, protect and hide state” and respond to “messages”.
Here is an object that models a Bank Account. It can respond to three messages: deposit, withdraw and balance?. Messages are encoded as patterns. We use the match library to decode the messages.
[Note: The samples will work only in Spark]
(import (match))
(define (bank-account)
(let ((balance 0))
(lambda (message)
(match message
(('deposit amount)
(set! balance (+ balance amount))
balance)
(('withdraw amount)
(if (< amount balance)
(set! balance (- balance amount)))
balance)
('balance?
balance)
(_ "Not a valid message.")))))
The bank-account object definition (or ‘class definition’ in Java or C++ parlance) satisfy all the properties as specified by Dr. Kay. It can receive and send messages. It’s state is locally retained, hidden and protected. It does not contain statically bound type information. In other words, you can send the message deposit to any object that can respond to that message. It need not be an instance of bank-account or one of it’s sub-types.
The following code shows how to instantiate a bank-account and send messages to it:
(define account (bank-account)) (account (list 'deposit 1000)) => 1000 (printf "Balance: ~a~n" (account 'balance?)) => 1000 (account (list 'withdraw 100)) => 900 (printf "Balance: ~a~n" (account 'balance?)) => 900
Joe Armstrong’s “Programming Erlang – Software for a Concurrent World” gave me some more ideas about the real capabilities that an OOP language should posses. They can be summarized as:
- The language should be able to create objects with hidden state – Alan Kay
- All computation should take place only by message passing – Alan Kay
- The objects should be concurrent, just like their counterparts in the real world – Joe Armstrong
- The objects should be location agnostic. In other words, the language should make it possible to distribute objects across a network, without considerable programming effort – Joe Armstrong
I decided to implement such an object system in Spark, which will have all the above listed properties. This framework is heavily influenced by what I saw in Erlang. The basic idea is to spawn a tiny process for each object. These processes are not operating system threads and does not have any constraints imposed by the host system. That means, a Spark program can be made out of hundreds of thousands of concurrent objects.
Let us re-implement the bank-account object to support concurrency:
(import (match))
(define (bank-account pid)
(let loop ((balance 0)
(message (receive pid)))
(match message
((from-pid 'deposit amount)
(set! balance (+ balance amount))
(send from-pid balance))
((from-pid 'withdraw amount)
(if (< amount balance)
(set! balance (- balance amount)))
(send from-pid balance))
((from-pid 'balance?)
(send from-pid balance))
(_
(send from-pid "Not a valid message.")))
(loop balance (receive pid))))
The procedures send and receive are used to exchange messages between objects. A short description of the code follows:
The bank-account object receives incoming messages in a loop. pid is a number that uniquely identifies an object within the system. This is passed as the argument of receive to retrieve messages from the object’s mailbox. When a message arrives in the mailbox, it is decoded, an appropriate computation is executed and the result is send back to the requesting object. The sender object (or client) is identified by from-pid which is included as the first element of all messages.
The following sample shows one way to code a client object for the bank-account:
(define client-pid "banking-client")
(define (banking-client)
(lambda (bank-account-pid message-to-send)
(let
((new-pid
(spawn
(lambda (pid)
(register pid client-pid)
(printf "~a: ~a~n" (car message-to-send) (receive pid))
(flush-output)))))
(send bank-account-pid
(cons client-pid message-to-send)))))
Here we introduced a new procedure called spawn. It is used to create a new concurrent object. This object is represented by a closure which takes one argument – the new process id. The client object is wrapped into a procedure that takes the bank-account pid and a message as it’s arguments. We can repeatedly call this procedure, which internally uses a singleton to send messages to bank-account and receive and display the results.
The following code shows how to use the bank-account and the banking-client objects to create a simple banking system:
;; Start the bank account server. (define account (spawn bank-account)) ;; Map the object or process id with a name for ease of identification. (define bank-account-server "bank-account-server") (register account bank-account-server) ;; Do banking. ((banking-client) bank-account-server (list 'deposit 1000)) => 1000 ((banking-client) bank-account-server (list 'withdraw 100)) => 900 ((banking-client) bank-account-server (list 'balance?)) => 900
The register procedure is used to map a name to an object id. Both send and receive can make use of this name as well as the integer id. The bank-account object can serve any number of clients without blocking other computations in the system because it lives in it’s own parallel world.
Now to the most exciting part! We have developed and tested our banking software and now we want to deploy it in a distributed environment. This could be done for various reasons: we may like to run computationally demanding tasks on dedicated hardware or we woud like geographically separated clients to make use of our software as a service etc etc.
Let us see how we can deploy the bank-account object on a different machine, so that it can act as a real network server. To achieve this we need not make any changes to the bank-account object itself! The only thing we need to do is start the built-in remoting service, which will enable the object to receive messages across the network:
;; Start the remoting service on the default port 1383. (remoting!) ;; Create a ''bank-account'' object as usual. ;; Magic! It can now respond to both local and remote messages! (define account (spawn bank-account)) (define bank-account-server "bank-account-server") (register account bank-account-server)
To enable the banking-client to send messages to the remote bank-account, we need to make a few simple modifications. First, we change the call to send, where we append the local host name to the client identifier so that the server can use it to send back the results. The object name will now look like an email address:
;; Change this line in the banking-client procedure.
(send bank-account-pid
(cons (string-append client-pid "@myhost") message-to-send))</pre>
The remote object identifier should also contain the network name of the computer on which it is running. To get back messages from the remote object, we should start the remoting service locally:
(remoting!) (define bank-account-server "bank-account-server@remotehost") ;; new ((banking-client) bank-account-server (list 'deposit 1000)) => 1000 ((banking-client) bank-account-server (list 'withdraw 100)) => 900 ((banking-client) bank-account-server (list 'balance?)) => 900
That’s it! Our OOP framework is able to simulate objects as they exist in the real world. They have local, private state. They can receive and send messages despite being in different geographical locations. What do you think? Ain’t this Object Oriented Programming the way it’s meant to be?
Links and References:
- The Spark concurrent object framework also has basic facilities to support fault tolerance. See http://spark-scheme.wikispot.org/Concurrency for more details.
- Termite – another Scheme for Erlang like distributed programming.
- Alan Kay on Object Oriented Programming.
- A good article on Smalltalk and message passing.
- Wikipedia article on the Actor model .
Programming language specifications often start with a design philosophy. Of all those I have read, I like that of the Scheme language most. You can read it in the introduction of Scheme standard , where it is stated as a single line:
Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.
The argument is that, using a very small number of rules for forming expressions and with a minimal syntax it is possible to support all possible programming paradigms. For instance, if the language has support for higher-order functions, closures and dynamic typing, we can implement object oriented programming without special language level syntactic support. Tail-call optimization elude the need for special looping constructs.
But this ideology has failed to capture the imagination of the majority of professional programmers. Instead the following thinking seems to have imbued their minds:
As more features are piled on top of an already bogged language, the more powerful will it become.
In this article I try to prove that this argument is false and misleading. Adding more syntax and restrictive rules to a language, which has a badly designed core, will only make it weaker and even susceptible to security risks. I will make my point clear with the help of a feature added to the Java programming language – Inner classes.
Inner classes are Java’s answer to Smalltalk’s blocks and Scheme’s closures. Look at the following code snippet:
public class OuterClass {
// Inner class
class AddN {
AddN(int n) { _n = n; }
int add(int v) { return _n + v; }
private int _n;
}
public AddN createAddN(int var) {
return new AddN(var);
}
}
The method createAddN() takes an integer ‘n’ and return an object that adds ‘n’ to a value. That object is defined as an inner class whose local state stores the value of ‘n’. Those who are familiar with Scheme or Common Lisp should be shouting by now: “Hey, this can be done more elegantly and compactly, like this-”
(define (addn n) (lambda (k) (+ n k)))
No new syntax to learn, no special rules to remember.
Agreed.
The problem is Java does not have first-class functions and closures, and the JVM is not designed to support them. But they are really nice features and are the natural solutions for many a programming problem. So as to have these nice features, Java introduced a restrictive rule to the language. The following example will throw more light on this:
public class OuterClass {
public int add10(final int n) {
class Add10 {
int add() { return 10 + n; }
}
return new Add10().add();
}
}
Here we have a method add10(), that contain a local inner class, which is used to add the constant value ‘10′ to a given value. But why the parameter to add10() is declared final? Problem is, the JVM has no idea of inner classes. So the Java compiler will generate a separate class file for the inner class. Now how to pass a local variable declared in Outerclass.add10() method to the Add10 class? The compiler does a trick here. You can find this out by decompiling the OuterClass$1Add10.class file. The compiler quietly adds a variable val$n to the Add10 class. When an instance of Add10 is created, the value of ‘n’ is copied to val$n. The JVM needs a guarantee that the original value of ‘n’ will not change after this copying is done because there is no way for it to keep track of those changes. Requiring the programmer to declare the variable final is the only way out of this problem.
An inner class should be able to read and write all variables of it’s parent class, despite what access modifiers they have. Otherwise, there is no point in making it an inner class in the first place! The following code demonstrates this. Here, the inner class is copying the result of the computation to a private variable of the outer class:
public class OuterClass {
public void add10(final int n) {
class Add10 {
void add() { k = 10 + n; }
}
new Add10().add();
}
private int k = 0;
}
Now we face a new dilemma. If, for the JVM, both OuterClass and Add10 are two unrelated classes, how an instance of Add10 is able to modify a private variable declared in OuterClass? The answer can be found by decompiling both OuterClass.class and OuterClass$1Add10.class files. We see that the compiler has secretly placed a new method with package level access in OuterClass.class file:
int access$002(OuterClass aOuterClass3, int int4) {
this.k = aOuterClass3;
return aOuterClass3;
}
Using this method, not just Add10, but any class in the package can see and modify the private variable OuterClass.k! If you generate a class file with appropriate byte code and place it in the same package as OuterClass.class, you can read from and write to its internal state using these secret access methods!
By adding a new feature Java has broken one of the key premises that identify it as an Object Oriented language, i.e, retention and protection of local state. This may not be a security problem. No one should rely on Object Oriented abstractions for securing their data anyway! But this might still cause problems for certain types of software and is certainly a hole in the language.
Higher-order functions and closures are features to be desired by any modern programming language. Unfortunately, many ‘modern’ programming languages have such rigid a design so that adding a new feature to it often breaks an existing, important feature.
I think this is where comparatively simple languages like Common Lisp and Scheme shine. You can add new syntax, even whole new paradigms, without touching or spoiling the compiler or the runtime system. As an example, read about how the Common Lisp Object System (CLOS) is implemented.
Good languages let you write terse, clean code. Look at the Scheme code snippet I gave at the beginning of this article. Compare that with all the verbosity in Java, just to get the same result. Of course, you will get what you want, only with a fissure in your program!
I have started a rather long process of giving a facelift to the Spark wiki. I am not a good graphics designer. But cosidering the kind of people that will be visiting this wiki, a slick UI is not going to be that important. What I plan to work on keenley is the documentation. We need a good book that explains how to use Spark to solve real-life programming problems.
Here is a quick tip for those who develop Flex applications without Flex Builder. You can still use trace() to write logging/debugging information. For this to work, a file called mm.cfg must be created in C:\Documents and Settings\$USER$\ (/home/user/ in Linux and /Library/Application Support/Macromedia/ in OSX). Make the following entries in this file:
ErrorReportingEnable=1 TraceOutputFileEnable=1
Load the SWF in the standalone FlashPlayer (debug version) and the input of calls to trace() will be pumped to C:\Documents and Settings\$USER$\Application Data\Macromedia\Flash Player\Logs\flashlog.txt (home/username/Macromedia/Flash_Player/Logs/flashlog.txt in Linux and /Users/username/Library/Preferences/Macromedia/Flash Player/Logs/flashlog.txt in OSX).
.. by none other than Boehm! Read the article here.
