Lambda the Ultimate

An old paper on boxer that I found while reviewing related work for a paper I'm writing, abstract:

Boxer was designed as a successor to Logo, with the same educational goals in mind. Whereas Logo has incrementally added features over the years, Boxer changes the
core computational structures of the language and environment. The aim is to make
learning easier and more rewarding, especially over the long term.

As an early graphical language, it is quite interesting. It is one of the first works I know of that dive into concreteness (they call naive realism):

Here, the idea is that the user of a computer system can pretend that what appears on the screen is the computer system. That is, you don’t need to do a lot of mental work interpreting an abstract presentation that relates only indirectly to the fact of the matter (as, for example, imagining something called a variable that is changed or accessed by commands). Instead, naive realism means that everything in the system must have a visual presentation that allows easy interaction with it, including creating it, changing it, moving it, and deleting it.

As well as one of the first languages to use spatial relationships in programming (the only other I know being...agent sheets):

Boxer uses space and spatial relations systematically to represent aspects of “abstract” computation. In particular, Boxer has a wonderfully transparent hierarchical structure of boxes inside of boxes that represents huge ranges of computational meanings.

But what I really like is this notion of pokability:

Logo has always, unfortunately, distinguished in one way or another the mode of creating procedures from the mode of executing them...you cannot easily—or at all!—see the effects of a procedure at the same time that you look at its form. This makes learning by inspecting difficult; you have to flip back and forth between different areas to see a procedure and its effects. In addition, it rules out a mode of learning by interacting with pieces of code, which is very powerful and characteristic of Boxer. For example, if you look at a line of code in Boxer and wonder what it will do, you can just double-click on that line, and it will be executed. This also turns out to be an extremely powerful debugging technique. If something goes wrong, you can just step through the process by executing one line at a time. That is, the inherent inspectabiliy of Boxer is extended with “pokability.”

And so on....

I've recently made an observation about syntax that has provided the first compelling reason I've seen to *NOT* use the traditional fully-parenthesized prefix syntax of Lispy languages. Instead, it looks like a better option for avoiding deeply nested syntax is the argument-parenthesized prefix syntax of Algol-like languages, along with an infix dot as syntax for an infix field-dereference operator for objects.

The rationale is that with these two syntax additions, you are able to avoid a lot of nesting levels when programming in a functional style -- and nesting levels are often one of the things people find confusing to keep track of.

When programming in a functional style, you usually want a "functional OO" style, ie, all operations on objects return new objects rather than modifying extant objects in place. This is frequently referred to as "monadic" programming, but IMO that terminology mainly gives rise to confusion.

So let's look at a straight Lispy syntax for a compound operation involving three method calls with two arguments each:

((getmethod
   ((getmethod
      ((getmethod object method1) arg11 arg21) 
         method2) arg12 arg22) 
            method3) arg13 arg23)

Here the syntactic nesting is six paren-levels. The same operation with the dot for an infix field-dereference (eg, getmethod) operator gives this:

(((object.method1 arg11 arg21)
      .method2 arg12 arg22)
         .method3 arg13 arg23)

which is three paren-nesting levels and three infix dereference operators, and seems easier for humans to parse. Now, if we switch the lispy fully-parenthesized prefix notation for the Algol-ish argument-parenthesized prefix notation, we get:

object.method1(arg11 arg21)
   .method2(arg12 arg22)
      .method3(arg13 arg23) 

Which is still the same six levels of semantic nesting, but no longer syntactically nested in parentheses at all. And this seems easiest for humans to parse, because the whole syntax for each operation "extends" the syntax for previous operations instead of having to be nested inside it.

Argument-parenthesized notation is just as 'regular' as fully-parenthesized, so macrology/call syntax can work the same way. The "infix dot" can be a reader macro as typical for lisps giving a fully-regular syntax. So, although the usual downside of losing lispy syntax is loss of ability to manipulate the code as data, I'm not seeing it here.

Just an observation at this point, but did I miss anything important?

During the design of the programming language which allows formal verification I had to design concurrency features as well. In order to define concurrency properly in the setup of formal verification some form of process algebra is needed. The process algebra and statemenst about properities of processes had to be integrated into the programming language.

The following paper describes how I intend to integrate concurrency into the programming language. I used Tony Hoare's CSP model (communicating sequential processes) as the basic theory.

Since the design of the programming language is still an ongoing activity any comments are welcome.

Michael Hansen presents the ACT-R cognitive architecture, a simulation framework for psychological models, showing how it could be used to measure the impact of various programming paradigms.

Video

This describes an interesting attempt to formalize comparison of programming languages from point of view of cognitive psychology. There are also some some interesting references from the presentation.

(define x 0)
(define p
  (delay
    (if (= x 5)
      x
      (begin
        (set! x (+ x 1))
        (force p)
        (set! x (+ x 1))
        x))))

(force p) => ??
x => ??

1. Ought the above be legal with specified results, legal with undefined results, or is it an error?
2. If it is an error, must an implementation detect and report the error via the exception mechanism, or may the dread curse of nasal demons be invoked?
3. If it is legal, with specified meaning, then what specific meaning ought it to have?
4. If it is legal, then may force return while the remainder of the computation caused by the force completes in another thread (making x subject to a possible race condition)?
5. If it is made legal, is there any legitimate use for it? (ie, is there any useful purpose the language would fail to serve if it were banned)?

Long ago, when I started programming, I used whatever editor was built into an IDE.

When I began programming without using an IDE, (which I did because I started using languages for which no IDE was available) I usually used an editor called Brief. Brief was a good editor, and had a lot of functionality, even rudimentary macros. I had tried emacs and very much disliked it for its flouting of user-interface conventions, non-standard keybindings, ridiculously awful help system interface with no obvious way to get back to the buffer you were working on, etc.

When I started professionally dealing with Lisp code, I had to learn Emacs; there was simply no other accepted solution for Lisp code. I worked on several programs using Brief, but there was an actual policy decision that in interests of uniformity and mutual readability of code, everyone had to use the same editor. After a few weeks of hating Emacs more and more intensely, I finally habituated to the backwards-martian interface, and ever since then it has been the easiest and most productive editor for me to use. In fact I often use it even when a nice IDE using some other editor is available.

But nearly everyone who is new to Emacs hates it passionately, just as I did when I was new to it. When you tell them that even basics like "cut" and "paste" have non-standard keybindings, their next question is usually something like 'why the hell are we using this piece of crap.' In the absence of a job requirement or similar pressure, few persist in learning it.

Now comes an observation. I have looked at hundreds of thousands of lines of Lisp code in dozens of dialects, and the indentation style (with the sole exception of McCarthy's initial papers on Lisp) indicates that everyone who writes it, without exception, is either using Emacs, or using something that implements *exactly* the same automatic indentation algorithm. And I don't know of anything else (bar deliberate Emacs clones like ZILE which get just as much UI hate, and for the same reasons, as Emacs itself) that implements *exactly* the same indentation algorithm that Emacs' lisp-mode uses.

Conclusion: (at least) 95% plus of the people writing Lisp code in the world, in all dialects, are using an editor to which the mainstream response is ... um, unenthusiastic at best.

Lisp users consider Lisp (in many dialects) to be a truly excellent language, and cannot understand why it isn't more popular. Other people sometimes try it, and I have heard more than one abandon Lisp because of Emacs hate. ie, the perception that you can only work on it using Emacs, combined with the perception that Emacs "sucks, hard." It is hard to avoid believing that Emacs hate may be one of the major forces holding Lisp back.

So, when I am faced with newbies whom I want to sell on the language itself, what useful, completely-featureful, programmers' editor with a standard UI can I use to demonstrate the language without alienating them? What editor should I be learning if I don't want to scare or alienate or intimidate or just distract people from the language or program itself?

What editor would a Lisp IDE developed by people who cared deeply about acceptance of the UI by the mainstream use? what features would allow some UI-standards compliant text editor to fully replace Emacs for Lisp programming purposes? And does anything out there actually have them?

Ray

(edited: de-capitalized things because capital letters apparently upset someone.)

I have to say up front that I am not a big fan of recursive function calls. I have created them only about 10 times in 35 years of professional computer programming. My plan was to not allow recursion in my language but I have come to realize that some algorithms are best described in this manner.

In C, recursion is implemented by putting all local variables and the return address on the stack. This causes a few problems for me in that if you don't stop the recursion then you blow up the stack. The number of local variables and the stack size determine when the dreaded "stack overflow" occurs which is not acceptable in my system as it must recover from all errors and continue to run. You also have to make sure your function unwinds the stack before you can exit and errors at arbitrary stack levels cause even more headaches.

I am well aware of optimizations for tail recursion which turns recursive syntax into just an internal loop but my problem is actually with implementing real recursion.

My functions are implemented as rows of a table where calling a function is done by stacking the calling row. Each function includes a symbol table so there is more setup for a function than in C. All my function code is always reentrant so subsequent calls are quite quick. Once setup, these functions stick around until they timeout. Putting hundreds or thousands of copies of these functions in my function table or allowing a recursive function to jeopardize my call stack is not an option for me.

A recursive call is a combination of stacked variables and a return address. I would be interested if anyone here has seen a simple language syntax that implements this functionality without actually using a function call. I would also like to have the programmer be able to directly test the level of the stack in their algorithm. Stack lists are an elementary variable in my language as are Maps that can contain any number of any type of variable. I could push a Map and a return address on a stack, for instance.

My system uses message passing in it's highest level abstractions and this does provide concurrency, however, the Actor Model is only a specific instance of message passing. The Actor Model has the following characteristics:

(these quotes are from Wikipedia)

1. send a finite number of messages to other actors
2. create a finite number of new actors
3. designate the behavior to be used for the next message it receives

The use of the word "finite" is redundant when used in a CS context as everything is finite except for a bug called an infinite loop. Although my message passing can create new "actors" and send multiple synchronous or asynchronous messages, it is only through changing the persistent state of my actors that one message can effect another (point 3). In general, my system tries to keep interaction between messages to the same "actor", to a minimum.

The Actor Model specifically says that messages can arrive in arbitrary order while my system will always deliver messages to the same actor in the order they were sent.

The Actor Model didn't guarantee that the recipient of the message actually exists or that they got the message. My system makes sure that the message can be delivered before it is sent or an error message is the result.

The Actor Model didn't queue multiple messages addressed to a single actor. Without this system guarantee, how would you know if your messages that normally work, would always work regardless of the work load? With the Actor Model, you would have to create your own protocol to make it useable. My system queues all messages sent to all actors.

In the Actor Model, the "return address" for a message was left up to the person sending the message. The Actor Model only incorporated messages in 1 direction rather than having automatic return messages and the choice of "synchronous or asynchronous" messages. My system incorporates 3 different kinds of message right in the syntax of the language so that it is obvious what kind of message is being sent.

The Actor Model, as defined by Mr Hewitt in 1973, said it was "inspired by physics including general relativity and quantum mechanics". I created all the rules of my message passing without any knowledge of the Actor Model or in fact what kind of message passing other languages use. My inspiration was just common sense and programming experience. I am not taking credit for inventing message passing but I am saying that message passing is a normal and obvious Computer Science concept rather than a Mathematical one, regardless of who first published the idea (sort of).

My recommendation is that the word "Message Passing" be used rather than the "Actor Model" when talking about message passing and concurrency UNLESS all the features of the Actor Model are used.

The objective of the OCaml-Java project is to allow seamless integration of OCaml and Java. Its ocamljava compiler can generate Java archives to be run on any Java virtual machine. This possibility will allow to leverage Java libraries from purely OCaml code. Moreover, the OCaml-Java runtime does not need to rely on a global runtime lock, meaning that concurrent programming is now possible in a single OCaml process.

However, versions 1.x should be regarded as mere prototypes, due to terrible performance and huge memory consumption. The upcoming 2.0 version fixes a number of issues, and greatly improves both CPU usage and memory footprint.

Bloom attempts to remove traditional mismatches between distributed software and platforms. Definitely a systems-oriented programming language (in the sense that this is what systems does these days). Interesting features copied and summarized from their site:

• disorderly programming: Much of the pain in traditional distributed programming comes from programmers bridging from an ordered von Neumann programming model into a disordered distributed systems reality that executes their code. Bloom was designed to match–and exploit–the disorderly reality of distributed systems. Bloom programmers write programs made up of unordered collections of statements, and are given constructs to impose order when needed.
• a collected approach: Taking a cue from successfully-parallelized models like MapReduce, SQL, and Key/Value stores, the standard data structures in Bloom are disorderly collections, rather than scalar variables and structures. These data structures reflect the realities of non-deterministic ordering inherent in distributed systems. Bloom provides simple, familiar syntax for manipulating these structures.
• CALM consistency: Bloom enables powerful compiler analysis techniques to reason about the consistency of distributed code; e.g. it can point out lines of code where a coordination library should be plugged in if you want to ensure distributed consistency.

Currently realized as an embedded Ruby DSL.