Lambda the Ultimate

Mark Guzdial:

Live coding is rich with interesting research issues because it's exploring such a different space than much of what we do in computer science. It's about expression, not engineering. It's about liveness, not planfulness. It's about immediate creation of an experience, not later production of an artifact. That makes it worth exploring.

More: http://cacm.acm.org/blogs/blog-cacm/168153-trip-report-on-dagstuhl-seminar-on-live-coding/fulltext

Dave Griffiths:

One of the most important for me was the framing of livecoding in terms of the roots of software engineering. Robert Biddle, Professor of Human-Computer Interaction at Carleton University put it into context for us. In 1968 NATO held a ‘Software Components Conference’ in order to tackle a perceived gap in programming expertise with the Soviet Union. This conference (attended my many of the ‘big names’ of programming in later years) led to many patterns of thought that pervade the design of computers and software – a tendency for deeply hierarchical command structures in order to keep control of the arising complexity, and a distrust of more adhoc solutions or any hint of making things up as we go along. In more recent times we can see a fight against this in the rise of Agile programming methodologies, and it was interesting to look at livecoding as a part of this story too. For example it provides a way to accept and demonstrate the ‘power to think and feel’ that programming give us as humans. The big question is accessibility, in a ubiquitously computational world – how can this reach wider groups of people?

More: http://www.pawfal.org/dave/blog/2013/09/dagstuhl-collaboration-and-learning-through-live-coding/

I was looking for work on GADTs in the presence of subtyping and found this 2013 paper GADTs meet subtyping of Gabriel Scherer and Didier Rémy.

Abstract. While generalized algebraic datatypes (GADTs) are now considered well-understood, adding them to a language with a notion of subtyping comes with a few surprises. What does it mean for a GADT parameter to be covariant? The answer turns out to be quite subtle. It involves fine-grained properties of the subtyping relation that raise interesting design questions. We allow variance annotations in GADT definitions, study their soundness, and present a sound and complete algorithm to check them. Our work may be applied to real-world ML-like languages with explicit subtyping such as OCaml, or to languages with general subtyping constraints.

The running example of the paper is (can you guess?) an expression type. One thing that I was looking for specifically that I didn't find addressed in the paper is how to interpret e.g. even exp, where even is a subtype of int (in a more dependently typed language). Any thoughts on this or another other aspect of the paper?

XKCD comic on functional programming. Overlay money quote:

Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.

If you've used a popular OO language chances are you've dealt with iterators.
As it stands a language like C++ supports three - Normal, Bidirectional and
Random Access. While this seems enough, the usual developer only makes use
of the normal iterator. I certainly think theres room for improvement

For example if I wanted to append to a list while traversing it back and fourth,
I'd need to write additional code. One concept to this is a scan style iterator:

template 
  operator ++ ()
    m.fwd = m.pos == m_cont.size() - 1 ? 0 : m_pos == 0 ? 1 : m_fwd; 
    return m_fwd ? *m_cont[(m.pos++)] : *m.cont[(m_pos--)];  

The key to this iterator is that whenever the upper bounds or lower bounds is met the iterator simply traverses in its the opposite direction. Decent in situations where one would want to compare array values having added or removed new ones - the drawback however is knowing when to stop. In addition, one must be somewhat aware of its length throughout. Otherwise it can lead
to unexpected results.

Another example would be the nthElement iterator. This basically says that after each iteration we sort its indice in the array. Consquently sample dataset:

set = [n, n - 1, n + 1]
*set ++; // returns n 
set.at(0) // returns n - 1 
// [n - 1, n, n + 1]

Lastly consider a usage iterater. In a nutshell this says every time a resource uses an indice it's usage count increments. This practice involves keeping a pointer to the next ideal location in the array. Consider:

dataset = [1,2, .. , n]
consume(dataset[1])
*dataset ++; // returns 2 given we've used its indice the most

In this example the array itself needn't be rearranged the iterator could simply keep a pointer to the next location.

Anyway for brevity that's it for now.
I would appreciate feedback on this.

In the seven years since I first began tinkering on what would eventually become Babel, the Internet has exploded with things called Babel. It is, unfortunately, a very popular name for things related to language. So, I've renamed the syntax layer of the language to Bipedal, while the VM is still called "Babel" or "the Babel-core".

I spoke on Babel at StrangeLoop 2013 in St. Louis on the 18th. The video will be available sometime in the next few months.

Bipedal

Bipedal is a front-end for the Babel programming langage core. Babel is essentially the VM on which Bipedal runs.

Bipedal progamming language is a general-purpose, untyped, stack-based high-level language. Despite being stack-based, it is not concatenative. It is not pure, as many operators can have side-effects. The syntax-layer is as transparent as possible, so when you look at Bipedal, you're looking at a nearly 1:1 translation to Babel bytecode.

Blitz Syntax Overview

comment:    -- this is a coment  
immediates: 'string' "string\n"  12345  0x123aced   
identifiers: non_alpha<>chars_permitted!_but-no-spaces:quotes|or|parens  
code: { "Hello, world" << }  -- << is the print operator  
list: ( 1 2 3 )  
s-expr:   
     [code "Hello, world" <<]    -- same as above  
     [list 1 2 3]                -- same as above  
     [ptr 1 [ptr 2 [ptr 3 nil]]] -- same as (1 2 3)  
     [val 1 2 3]   -- array/vector

There is more to the syntax, but this is enough to introduce some of the key concepts of the language. You can check out more examples at RosettaCode.

Bipedal as High-Level Language

There are two strikes against Bipedal's use as a HLL: 1) it is stack-based and some people are of the view that stack-based languages are only suited to intermediate-languages, 2) it is untyped. I have attempted to address each of these problems in my design of Bipedal/Babel.

Stack-noise reduction

Babel actually maintains two stacks: up-stack (ustack) and down-stack (dstack). Let the notation

x y z|

represent a stack where x has been pushed first, z last, with '|' visually marking the TOS.

Now, let us define star_n as a combinator that will print an asterisk n times, where n will be passed on TOS. One way to write the code for this is as follows:

[star_n { { '*' << } swap times }]

The order of operands for the times operator is "{ code } N times", where N is some number. Since n is being passed on TOS, this creates stack-noise where we must swap the code to be executed with the number of times it is to be executed, already on TOS.

Another way to solve this in Babel is to use the up (->) and down (<-) operators:

[star_n { <- { '*' << } -> times }]

This has an equivalent effect. A view of the stack images:

          dstack  ustack    
           n|       |       | 
            |       |n      | t
  { '*' << }|       |n      v
{ '*' << } n|       |

In this case, it is not clear that up/down are an improvement over swap - in fact, we have used an additional operation to accomplish the same task. However, the up and down operators allow the stack to be "taken apart" and processed piece-by-piece, for any number of "arguments" passed to a particular operator. To illustrate this, consider the following function in the notation of C:

foo(a, b, c)

The arguments are pushed on the stack and then foo is called. If it is possible to perform all processing on a, then b, and then c, then we can apply the following schema using the up/down operators to process foo in a similar way in Babel:

[foo { <- <-            -- (a is now TOS)  
        operate_on_a  
        ->               -- (b is now TOS)  
        operate_on_b  
        ->               -- (c is now TOS)  
        operate_on_c }]

Of course, this pattern will not solve all stack-noise problems, as it can be the case that values on the stack need to be accessed in some arbitrary order with repetitions, such as: a c b c b a c b. The up/down operators are unlikely to reduce stack noise over against the more traditional stack-rotations in this case.

So, Babel permits the use of a 'let' construct to allocate local variables:

[foo {(a b c)   
     { a c +  
     b c /  
     b a c *  
     b - - - }   
     let }]

This construct should not be confused with the let form in Lisp because it does not perform any kind of "binding" - a, b and c in this case are just pointers and the let operator merely saves/restores the pointers (using the rstack).

Another tool for tackling stack noise is the nest operator. Nest allows the construction of a stack-discipline using the following rules:

• Current stack is saved on entry to a nested-context, except TOS which is popped off current stack and becomes TOS of the new stack

• Prior stack is restored on exit from a nested context, except TOS which is popped off the nested stack and pushed onto the restored stack

  [bar { 'a' 'b' { << 'c' 'd' } nest }]

Invoking bar will cause 'b' to be printed to STDOUT and the following will be left on the stack:

'a' 'd'|

Nest allows a nested-section to monopolize the stack. This is useful if you want to generate a bunch of results on the stack and then collect them together into a list (you can use the collect pseudo-operator for this).

Using nest in combination with let will give something roughly analogous to an ordinary function-call stack discipline:

[foo { { (a b c) { <code> } let } nest } ]

Bipedal has a pseudo-operator called args to perform this:

[foo {(a b c) { <code> } args}]

The args pseudo-operator also assigns the elements of the list on TOS (assumed) to a, b and c.

Typing

Babel does not have any built-in type system, beyond some rudiments to differentiate between pointers and non-pointers. To me, "type" means one of two, completely different concepts:

a) The format of data. ASCII is a type specification, XML is a type specification, JPEG image format is a type specification. When you say, "this is type string", it is difficult to say what exactly you mean without talking about the format in which the string data is kept.

b) Data-flow connectors, i.e. "you can't put a square peg in a round hole", or "you can't put an int in a char" (usually). Of course, typing systems can convey much more information, but it is my contention that there is no reason why this information must be conveyed through types - for example, the "is-a" and "has-a" relationships.

What Babel implements instead of types is a tag - a tag is a hash (typically, from hashing a string) that can be attached to an otherwise untyped data-structure. Of course, tagged things can be composed, so you can have "types all the way down", if you need it. That is, you could track the fact that a string is a string, a number is a number (and its size) and so on.

What you don't get (automatically) in Babel is any kind of inference. However, you can implement your combinators in such a way that typing is always tracked through tags.

Support for prevalent data forms, I/O

Babel has built-in support for operating on UTF-8 encoded strings, numerics, arrays, lists, hash-tables, binary and n-ary trees. Bipedal files are UTF-8 formatted. File and console I/O are supported.

Unique or Notable Features

The Babel Virtual Machine is ultra-lightweight, making launching of nested virtual machines very cheap. In Babel, the VM is intended to be the natural unit of abstraction. There is no OO support built-in. The advantages of VM abstraction over OO include that the VM can be interrupted, hibernated, forked, and has configurable resource limits (such as memory-allocation, time, file-access privileges, etc.) Other unique or notable features of Babel include:

• It is easy to containerize and launch nested Babel programs

• Built-in crypto makes it easy to enforce a "white-list" code execution policy, reducing the risks associated with executing remote code. The idea is to invite the community of users to write their own, distributed library and to choose their own, trusted sources.

• Your data structures are all stored in an underlying, uniform bstruct structure, making it trivial to save and restore them to and from disk, to make deep copies of them, to delete all memory associated with them, and so on.

• You can easily compress and encrypt your program data objects, (or whole Babel programs).

• Visualizing your data is uniquely easy with Babel's built-in support for generating Graphviz dot files. These can be post-processed with the dot tool to generate graphical snapshots of your data. This speeds up debug and helps the programmer fully absorb the semantic significance of the syntax.

• Babel provides both Lisp-style lists and array structures, permitting you to organize your data in a manner to maximize both flexibility and performance. Modern computer architecture is array-based and can perform array lookups in constant time rather than linear time for list- traversal. But for data that is constantly changing size or continually undergoing complex permutations, lists are a clear performance winner by permitting you to perform more of your operations in-place.

• The Babel namespace is modeled on a Unix-style directory structure, making it possible to nest data and code in arbitrarily deep and complex structures. Manipulating namespace paths permits implementation of OO-style templates, polymorphism and more.

But We Already Have Factor

My answer to this is that, while Babel is a "practical" stack-based language, it's just a completely different flavor of programming language. It's difficult to meaningfully compare very complex things like programming languages, but perhaps it could be put most succinctly this way: Babel is the Perl5 to Factor's Python. Minus Perl's labyrinthine syntax, of course.

Another way of comparing the difference is that the Babel binary is right around 100K as of this writing; it may grow as large as 200K by the time Babel is at revision 1.0, but this will mostly be the result of linking in some support for encryption and compression operators. The Babel-core is essentially finished. Babel takes a more minimalist "swiss-army-knife" approach versus the more "kitchen-sink" approach of Factor, which has a 425K core plus an incredible 66M image file of Factor library code.

Conclusion

Your feedback is welcome. Babel isn't quite ready for prime-time, but it's getting closer every day. If you have a Windows box with Cygwin and ActivePerl, you can just clone Babel from github, run make.pl and you're ready to roll. You don't need a compiler as the repo has a copy of tcc and will compile from that. If you want to try Babel, please do not hesitate to contact me and I'll help you with any questions you may have.

As seen many places by now, no doubt: The Slow Winter by James Mickens.

I've written a short piece, illustrating the use of coroutines to build up UIs compositionally, at my blog.

I'd be curious if anyone here knows of prior research in this direction. I think there is some similarity between this approach, and immediate-mode GUI, discussed previously here. I believe that immediate-mode GUI could be seen as a special case of coroutine UI.

The Common Lisp reader has a feature known as The Readtable which can be used to configure an ad hoc but interesting assignment, to individual characters, of a syntax type or reader macro.

I'm interested in historic and current experience with these features. I'm especially interested in experience that does not make use of the reader macro feature but that uses the mutability of the "syntax type" of characters in interesting ways.

How good or bad an approach to lexical analysis is this? How general purpose has this approach proved to be in a practical rather than theoretical sense? Has Common Lisp's list of character syntax types been compelling extended?

The more general question I'm contemplating asks what good alternatives there are to regular expressions for specifying lexical syntax. Common Lisp syntax tables have some appeal to me because the character syntax types reflect how a person might describe a lexical syntax to another person: "These characters can begin an identifier. This other, overlapping set of characters can be constituents of an identifier. This is the single-escape character for identifiers."... and so forth.

I'm wondering about the possibility of a system for defining lexers in those kinds of familiar terms.

(Turon has been mentioned before on LtU, it appears.)

Aaron Turon's PhD thesis lists 3 bullet points (heavily boiled down here since copy-paste from the pdf goes wrong): Visual artifacts for understanding; Declarative synchronization; Monadic reagents.

I'm making this new programming language Ya. I'm not sure I'm right writing to you, yet I just don't know what to do to make people know that new programming language Ya exists. If you know what I should do - please help me. Thank you. Pavel Senatorov, Ya-Lang.com .