Vocabulary Based Programming

I believe programming is easy and programming is natural. Apparently, many people do not think so, and I often ponder why. In doing so, I often compare our natural language with current popular programming languages, and a contrast start to emerge. Our natural language, in addition to basic subject-predicate grammar, evolves by expanding vocabulary, but in typical programming language, the keyword stay fixed, and the expansions happens in nested structures -- chained functions or wrapped classes.

-- What is the difference? Don't we always name our functions and classes?

There is a fundamental difference. The vocabulary in our natural language is semantic based. Each word in our vocabulary is a unit of meaning that is not tied to a context. Yes, all words have a preference in context. For example, "eat", have a context of a person or animal devouring a food item; but we have no problem saying or understanding a sentence such as "the desert eats the lone traveller". We use the word for its own meaning rather than an attribute of certain context. On the other hand, when we name a function or class method, the name is merely an attribute to a larger context. The function is only meaningful with its parameters and body of definition, and a method is only meaningful with its parent class structure. So when we encounter a statement such as desert.eat "traveller", it can mean anything and the only way to figure out what the programmer intended by that statement is to read its entire code base. The name "eat" is not a vocabulary in the programming language, therefore, does not mean anything (at most, only a hint).

There is certain trend in programming language development that leans toward the direction of growing vocabulary. For example, in Haskell, we can write


fold (+) [1,2,3,4,5]
                                
"fold" here is a vocabulary word. Haskell is complete without this keyword, but with it, the code become more straight forward to comprehend (read and write). We should notice that although the definition of "fold" has its context and specific restrictions, our intention of this word is clear and standalone. That is, if we write

fold multiply a_hash
                                
Even though it may not work in vanilla Haskell yet, we have no problem understand its meaning; and we can make it work if we have to; doing such, we expand the usage of this vocabulary and evolve the language -- a process common in our natural language.

However, the current limit of this vocabulary trend is also obvious. First, the new vocabulary word (e.g. "fold") is created by language designer. Second, its usage is strictly defined by the language designer or a few elite programmers. As such, the word "fold" feels more like a keyword than a vocabulary

A vocabulary based programming need give ordinary user the ability to create new words and the ability to expand its usage, with very little barrier. Something like an ad hoc mode, similar to how our kids create and use slangs.

To illustrate my point, let's do a case study.

Straight Insertion Sort

Let's say I am interviewing you, and I start on the paper:


fncode: main
    $define(N) 100
    $local int A[N]
    $for i=0:N
        A[N]=rand()
                                
I'll explain to you this is the start of a C program (with some meta syntax for clarity), and I would like you to continue the code to sort array A. You can use straight C syntax or pseudo code (as long as they are indented inside "fncode: main") and there is no requirement for optimizations (I may even hint you that straight insertion sort will qualify).

Will you be able to pick up the pen and start code or will you pause for a while?

If you only pause for a couple seconds and start to write out, e.g. an insertion sort, with nice indentations, I praise you. You are the candidate to move on. If you pause for extended time, why?

The reason I am interested in asking why is because I know everyone knows how to sort. For example, if I present you a deck of card and ask you to sort them, you will not hesitate to start, not even for a kid. Then what pauses you to write the process out in code?

To understand the puzzle, I would like you to describe in your native language how you would sort the deck of card. Let's compare your description (e.g. in English) with your code (assume you eventually had it).

I have the book The Art of Computer Programming by Prof. Knuth on hand, and following are from the book:

I don't know about you but I find neither the diagram nor the algorithm illuminating. Let's also look at the code from the wikipedia page:


for i = 1 to length(A) - 1
    x = A[i]
    j = i
    while j > 0 and A[j-1] > x
        A[j] = A[j-1]
        j = j - 1
        A[j] = x
    end while
end for
                                
I am more comfortable with this direct code, but how it works is still not obvious (me again).

There is also this new trend in visualizing the algorithm:

Mesmerizing, but does the animation help you write out the code?

Now let's look at your verbal description of how to sort a deck of card:

continuously pick a card from the deck
    insert the card into the hand in order
                            

Straight forward, isn't it? Of course, it is not complete. I'll ask: how do you insert the card in order? You may expand:

compare the card with the ordered card in sequence
find the position to be inserted
shift the card to make space
put in the card
                            

Yes, much more clear. Now any fool can sort the deck. :)

In comparison, the description in code (including the diagram and algorithm) contains limited vocabulary, while the description in English are lead by vocabulary. Like in the popular show, Dora the Explorer, as we read the English description, we retain in our working memory: pick, insert or pick, find, shift, put in.

I find this observation very interesting, and it leads me to start writing code like following:


$for i=0:N
    temp=A[i]
    $call find, A[i]<A[j], j=0:i
    $call shift
    A[j]=temp
                                
You may almost find one-to-one correspondence of this code against our English description, except the action of "pick" and "put" seems so straight forward that I simply wrote the code directly.

Of course such code will not work, yet. Let's complete it


subcode: find(cmp, range)
    $for $(range)
        $if $(cmp)
            break
subcode: shift
    $for k=i;k>=j;k--
        A[k]=A[k-1]
                                

In fact, this will work as is in MyDef. Let me put it together:


page: test, basic_frame
    $define(N) 10
    $local int A[N]
    $loop(N) A[i]=rand()

    $for i=1:N
        $if A[i]<A[i-1]
            #-- pick
            temp=A[i]
            $call find, A[i]<A[j], j=0:i
            #-- shift
            $for k=i:j:-1
                A[k]=A[k-1]
            #-- put in
            A[j]=temp

    $loop(N) $print $A[i]

subcode: find(cmp, range)
    $for $(range)
        $if $(cmp)
            break
                                
There are a few small changes (not that the original won't work, but sometime it is natural to refine as we write): There is no need to pick the first card in code, so the loop starts at 1 instead of 0; added a comparison to see if the new card is already in order; merged the "shift" code into the main code as the word "shift" does not feel general enough and the code seems clear on its own (to help, I added the comment); on the other hand, "find" seems general enough to represent a wide code pattern and I am considering moving into my definition library as I am writing this. I also changed N to 10 and added the print loop so I can demo. (Oh also loop and print are also vocabularies that I already had in my library.)

$ mydef_page -mc test.def
PAGE: test
    --> [./test.c]
$ gcc -o test test.c && ./test
424238335
596516649
719885386
846930886
1189641421
1649760492
1681692777
1714636915
1804289383
1957747793
                                

Discussion

We should contrast this against the traditional way of writing functions or even classes. If we write code as:


for(i=1;i<N;i++){
    temp=A[i];
    find();
    shift();
    A[j]=temp;
}
                                
It will not work. For functions, we need worry about interfaces and passing parameters. The function (particular in our example) is meaningless without seeing how the parameters are passed in and returned. When we interrupt to write out the interface, the power of vocabulary disappears. Further, people would question whether the overhead of functions are justifiable in this particular example.

In the example of using MyDef, we write out the vocabulary according to our semantic intention even when the code does not exist yet. We use it for what we mean, not for what code we'll write (which was not born yet). The vocabulary does not incur any overhead, although in situations, we may implement certain vocabulary using functions or library calls but that is not restricted by the use of vocabulary on its own. Further, we can see how some word will start to stick, like "find", where I, or other programmer, may start to use it more and more often, at which point, it may become as natural as the word "fold" in Haskell. In particular, the implementation of the word (note that I use "implementation" rather than "definition"), albeit takes in context, is rather abstract -- it is not intrinsically restricted by data types and variable scopes, even though the language is strict about them.

Compare to the traditional keyword such as "fold" in Haskell, we do not learn the vocabulary before we start to use them. We create the vocabulary as we use them -- a much closer parallel as we do in our natural language. With the help of MyDef, or some similar meta-layer programming environment, there is little barrier in implementing and spreading the vocabulary. The same vocabulary, e.g. "find", could even spread across language -- they just need to be implemented. Good (useful) vocabulary will start to stick and grow as an evolution like process rather than being designed by a language designer or committee. Natural selection will win.

EDIT: I would also like to point out the benefit of using vocabulary based programing in the aspect of code reuse. Let's say now we were tasked to sort a list of strange data structures. If our algorithm are lead by vocabulary, we can write the exact same program: pick, find, shift, put in. All we need is to implement specific code for the new data structure, which is necessary no matter what. In a sense, we won't re-write the algorithm, we only need implement the new specific part. No overhead of abstraction is necessary. In my own practice, I do not always stick to vocabulary just like I showed in the example; although I always start with vocabulary, I often swap in the actual code when the code is trivial enough and the vocabulary is not sticky enough. It is a dynamic balance that will vary from programmer to programmer.

[ To clarify, MyDef is merely a meta-layer (similar to macro layer as in C) that translates from what you want to write into what you would write. It is independent of the programming language but may contain features that are langauge specific. It is not traslating from one language to another language as typical programming language would do. In the example presented in this article, we wrote C in MyDef. MyDef only traslates the macros (including the vocabularies and their implementations), but pass through the rest of the code for the C compiler to judge. Although I would like you to try MyDef, the purpose of this article is to discuss an idea. ]

[ Try MyDef Demo ]

[X]

Recent Posts