cdiggins.com

Recently I submitted a small informal survey to the concatenative mailing list about concatenative languages. The results were interesting, and I thought I would share them here:

> - I feel the advantages of concatenative languages are ..

This is an interesting list that I can’t effectively summarize:

- syntactic simplicity x3
- easy to implement x2
- semantic closeness to a machine model x2
- generally good referential transparency x2
- conciseness of expression x2
- quick and continuous refactoring,
- incrementally implementable
- easy experimentation with language design
- powerful
- highly interactive
- fun
- dataflow notation
- very short read-eval-print loop
- natural modularization
- theoretically interesting and intellectually stimulating
- immediate testability

> - I feel that the most powerful advantage of concatenative languages
> is …

I think one word sums up the responses: simplicity.

- easy to refactor code
- syntactic simplicity
- close to the hardware
- immediate feedback
- immediate testability
- ease of syntactic transformation

> - My positive experiences with concatenative languages have been …

This was a tricky question for people to answer because it was subjective and open-ended. It did reveal something I think: Forth has already proven itself a particularly effective language for embedded programming development. Also I think it reveals that learning about concatenative languages is intellectually enriching.

- learning about Forth;
- challenging myself to do anything productive with dc;
- having a wonderful time playing with Factor.
- programming in Forth
- scientific and embedded programming in Forth
- reading about Joy
- large scale instrustrial software development with Forth
- learning about the fundamental issues of computer science

> - My negative experiences with concatenative language have been …

Many of the negative experiences mentioned were primarily language specific. However, I think the results suggest that maybe people find concatenative languages somewhat hard to use. However, this could also be due to preconceptions.

- fragmentation of the Forth community
- distinguishing compile-time from run-time and definition-time execution in Forth
- lack of a type system in Forth
- Trying to program in Joy
- Lack of acceptance of Forth by clients
- programming complex algorithms without named parameters

> - I feel that for concatenative languages to gain more mainstream
> success will require …

In summary: better tools and find a niche.

- development and maturation of one or more programming environments
- that it is clearly demonstrated what they are good for.
- a solid high-level language with multiple successful implementations or platforms
- choose a niche (e.g. embedded programming)
- a major breakthrough in ease of programming
- the identification of a lively niche where they provide great leverage
- education as to the advantages
- overcoming the aversion to postfix syntax.
- integration of ideas from modern programming language theory
- better tools

> - I consider a language to be concatenative when it has the following
> properties …

So I’ll summarize with my own personal definition inspired by the other contributions: a concatenative language is a language where the concatenation of terms (i.e. justaxposition or sequencing) denotes the function composition operator instead of function application.

- token-oriented, combinator-based postfix syntax with relatively shallow nesting;
- semantics defined primarily by function composition rather than by [nested] function application;
- an execution model of passing state from function to function.
- concatenation of source text denotes new programs
- where concatenation means function composition
- Concatenation is just about everything.

I recently started developing the syntax for a model-based language I am working on and I found myself basically writing down the specification for the Scala language!

This prompted me to go back and visit the Scala site (http://www.scala-lang.org) which I hadn’t done in a while and see how things are going. I am very happy to report that the language specification has been stable for quite some time, and that the documentation is steadily improving. Furthermore Scala is now being used in several programming language courses (http://www.scala-lang.org/community/say.html#courses). However, what I am particularly pleased about is the library support of Actor based concurrency. Actor concurrency is the model used by the increasingly popular language Erlang.

So it turns out everything that I wanted and expected in a high-level language is already in Scala: object oriented programming support, lots of libraries, easy-to-use support for concurrency, easily extended, support for mixins, type-inference, familiar syntax, no superflous features, and deep support for functional programming. I have to say that above all what makes me happiest about Scala is not the inclusion of features but that the features supported is a consistent and coherent set that makes sense for software design.

I have just released version 0.18.2 of the Cat programming language. This is a relatively stable build.

Cat is a statically typed concatenative language, based closely on the Joy programming language. Cat includes a term rewriting optimzation system called MetaCat. The primary release of the Cat source code is written in C#, but is entirely public domain, and is cross platform compatible using Mono. The home page for Cat is at http://www.cat-language.com.

Release notes for 0.18.2:

• fixed a bug with the function inline expander
• MetaCat macros are loaded at runtime
• MetaCat rules now use “rule { … } => { … }” syntax instead of “macro …”
• MetaCat stack variables can now have types in some cases (e.g. rule { dip $B:(’a -> ‘b) $a dip } => { $a compose dip $B })
• the standard library has been extended.
• the type system is more permissive of recursive forms
• new primitive: unpush : (( -> ‘A ‘b) -> ( -> ‘A) ‘b)
• known bug: some ill-typed recursive programs are not caught by the type-checker
• known bug: some recursive programs overflow the stack during type-checking

I recently made a new release of Cat. This version has better type handling for recursive functions, more tests and some bug fixes. What is particularly interesting though is the addition of a new experimental primitive tenatively called “unpush”.

With the introduction of ”unpush” Cat 0.18.1 now can implement fully typed tuples. The method is quite unconventional because “unpush” takes ordinary functions, that don’t consume anything, and deconstructs them. In other words “unpush” has type “(( -> ‘A ‘b) -> ( -> ‘A) ‘b)”. By deconstructing these functions, we can get at the values contained within them. In most cases “unpush” is able to simply examine the contents of a function and extract the last instruction. In degenerate cases (like [1 dup]), the function must be first evaluated to find the top value. This is inefficient, but being a rare case we don’t care so much.

In practice this means that “unpush” behaves like “uncons” in Joy:

[1 2 3] unpush => [1 2] 3

So why not say it is precisely the same thing as “uncons”? Well there is a limitation, we can not add or remove items from a tuple dynamically, otherwise the type would become unknown until run-time. This is why I will still be leaving a distinction between a list and a tuple in the language. This could actually turn out to be the foundation for a strongly-typed object system in Cat which I will explore in later posts.

The Structure and Interpretation of Computer Programs, a.k.a SICP, is a well-known and highly regarded computer-science text which uses the Scheme programming language. Chris Rathman is working on an interesting project to translate programs in the SICP to other languages. What is particularly interesting for Cat lovers is that Cat is now included, see http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages.

I find writing research articles is very hard. I believe though that there is a technique to it, and with enough practice and rejection I will figure it out. I have no shortage of ideas, but I still need a lot of work at writing good research articles.

Today though it dawned on me that there is a very important question that must be answered by an article: “Why hasn’t anyone published this idea yet?”. If you have a new idea or approach, you have to explain not only why it is a good idea, but why no one hasn’t published it before. The assumption is almost that if an idea isn’t in the literature already there is a good reason for that. It is the author’s responsibility to explain to the reader what that reason is.

Hopefully this little realization will help me write better articles, and maybe someone else as well.

I normally see about 5-10 downloads of Cat a day, but the other day I received 200 downloads in 12 hours! Google analytics isn’t really being helpful in figuring out what happened. Perhaps it was simply an overzealous robot? I like the idea that there might soon be a whole bunch of new Cat programmers out there.

In other Cat news I found a new concatenative language inspired in part by Cat called Sept by Stephane Arnold. It is quite exciting to see that Cat is having a positive impact on other languages.

I have also been recently thinking about minimal higher-order stack-based architectures, inspired by Chuck Moore’s writings about minimal instruction set architectures. Recent discussions on the Concatenative yahoo group on the subject have been quite informative and interesting. I nearly have a machine design, but it will take some time to refine and test.

At school I am working on a library dynamic configuration of FPGAs with Etienne Bergeron, writing compilers in Scheme, and taking a probability and statistics course (against my better judgement). I am also working on a formal paper on Cat for PLDI with my colleague David Haguenauer.

Recently I was pointed in the direction of Action Semantics for executable UML by Abdelwahab Hamou-Lhadj. I am waiting for Amazon to deliver this book on the subject of executable UML, recommended by Abdelwahab. I am quite excited to explore the topic further, because I am very interested in topics related to software engineering. Some of my fellow students seem to be dismissive of software engineering, but I suspect that is due in part to the competitive nature of research work. 

There is so much to do, and so little time. Hopefully once I am done with classes, I’ll be able to start getting more work done. I really need to make an official Cat release and start writing some more tools for it.