Lambda the Ultimate

Subtext was (I think) going to give us a UI for dealing with the complexities of conditional logic. Whenever I read about more-than-single-dispatch, a spreadsheet UI comes to mind. Nice to know others have thought of it, and also complained about it. From Object-Oriented Multi-Methods [pdf] in Cecil, 1992:

Hebel and Johnson developed a special browser to manage the highly-stylized double dispatching code for arithmetic over numbers and matrices in Smalltalk-80 [Hebel & Johnson 90]. Their browser presents a two-dimensional spreadsheet-like view of all combinations of numeric and matrix argument types for a particular arithmetic message, with each entry reporting whether the corresponding argument type combination defines a method or merely inherits one from either the receiver inheritance chain or the argument inheritance chain. Programmers can manipulate implementations of arithmetic messages through the interface provided by the browser, and it will in turn generate many of the double dispatching functions automatically. While this browser makes double dispatching more manageable, it does not completely solve the problems with double dispatching. Users who examine numeric classes through the normal Smalltalk-80 browser still are confronted with a large number of (automatically-generated) dispatching routines. Additional browsers would be required for other kinds of messages (such as the displayOn message) to receive the same sorts of benefits. In effect, their browser partially simulates the functionality of multiple dispatching in the programming environment; we argue instead for uniform language support of multiple dispatching. Nevertheless, their interface might be useful even for a multiple-dispatching language such as Cecil to help display and organize multi-methods.

Is anybody these days working on some UI avalon panacea along these lines per chance?

Greetings Folks,

I've posted here in the past about a compiler framework I'm writing. I've also been *trying* to write a Compiler Compiler (with respect to the tokenizer/parser automation), the issue I've run into is the area of Named Captures. When I started this project, I didn't know a whole lot about parsers in general, but I've learned quite a lot in the process.

A little context might prove helpful:
The program uses a single file format to define rules:

ExternAliasDirective                       ::=
    "extern" "alias" Identifier:AliasName;   ;

and Tokens:

Identifier := 
    '@'? IdentifierOrKeyword;

UnicodeEscapeSequence :=
    "\\u" HexChar{4};

IdentifierOrKeyword :=
    IdentifierStartCharacter IdentifierPartCharacter*;

IdentifierStartCharacter :=
    LetterCharacter                         |
    '_'                                     |
    UnicodeEscapeSequence                   ;

IdentifierPartCharacter :=
    LetterCharacter                         |
    CombiningCharacter                      |
    DecimalDigitCharacter                   |
    ConnectingCharacter                     |
    CombiningCharacter                      |
    FormattingCharacter                     |
    UnicodeEscapeSequence                   ;

LetterCharacter :=
    [:Lu::Ll::Lt::Lm::Lo::Nl:];

CombiningCharacter :=
    [:Mn::Mc:];

DecimalDigitCharacter :=
    [:Nd:];

ConnectingCharacter :=
    [:Pc:];

FormattingCharacter :=
    [:Cf:];

Tokens allow for more flexibility in the actual patterns, such as character ranges (which can contain Unicode classes). Tokens aren't recursive so they can refer to other tokens, so long as the other tokens, within the tokens scope or the token itself, doesn't refer back to itself.

For brevity if you have a large number of tokens that you want to classify under a single name (like 'keywords') you can simply create an alternation between the terminals, giving each a name, and so far it's smart enough to detect these groups and create proper state machines for them (they're a little different in that they don't have repetitions, character ranges, or refer to other tokens.)

LinqKeywords                               :=
             "ascending":Ascending;         |
                    "by":By;                |
            "descending":Descending;        |
                  "from":From;              |
                "equals":Equals;            |
                  "into":Into;              |
                  "join":Join;              |
                   "let":Let;               |
                 "group":Group;             |
               "orderby":OrderBy;           |
                 "where":Where;             ;

If a language only refers to an alternation, like the one above, by the classification name (such as 'LinqKeywords') only one 'symbol' for the language is created; however, if one of the named elements is referenced, each of the items from the classification are given their own symbol. Differentiation between which was actually selected is still possible, but for the sake of the parser, the data is irrelevant. This is important for context awareness, since if you require 'as' to be present at a given point, but 'ascending' is another part of the possible symbols, LinqKeywords won't even enter the picture because it's not relevant.

I have enough information from the file format to make these relationships, and build the state machines for the lexical analysis phase. The issue is: the lexer has no captures, and thus, if I was even able to get the parser working, without a viable means to capture the information it's validating.

Does anyone here have any suggestions on where to go next? I'm using a deterministic state machine for the lexical analysis phase, it does the usual set comparisons necessary to differentiate which path to follow, the context associated to the symbols in play is available, but the issue is I don't know how to properly represent repetitions, and the like. Is my approach wrong, or is a non-deterministic approach more feasible?

For further context: I used the standard programming language means of defining a string to represent a simple terminal symbol because I'm self-taught, and when I started this project (a ... while ago,) it seemed the most 'natural'. Case sensitivity is easily represented by using '@' before the string to denote case is unimportant. For a state machine this representation is trivial.

Edit: I guess information about goals is helpful.
This project aims to do the following:
Generate a lexer which properly creates tokens of the kinds provided. Create an object model to represent the structure of rules, and generate a LL(*) parser which can construct the object model in the way it was defined. I've handled left recursion on my own successfully, so the main issue is figuring a way to automate it all. A friend of mine suggested writing a parser from scratch and then build a mental map of how I could do it through automation. I thought this is a good idea, but the language I'm working on has 181 token symbols and 277 rules. Suggestions on starting smaller (such as what language, what test would be helpful to this end)?

Edit 2: As far as automation goes, I'm not unfamiliar with the process, I've written a program to generate a ECMA-335 compliant metadata parser (minus Blob signatures, that had to be done by hand) because the format was straight forward, and the variable sizes of the fields within the tables was handled through a simple state machine created by analyzing the references within the tables and assigning each potentially variable-length reference type a significant bit in the state machine's internal state.

Hi all!

A while back I posted about a language I was designing called Aml. It is a language for exposing user-created domain-specific languages. Currently the language's implementation is far along enough to start being worth taking a look at and critiquing its semantics. Please take a look at it here - http://www.2shared.com/file/jJkwy2LL/Aml_0043.html. The open source repository is here - https://github.com/bryanedds/aml. Feel free to critique anything about it. Hate my code? Terrible use of an ML-derived language? Retarded syntax or semantics? It's all welcome, please!

Aml itself is a lisp-style language with a lot of foundational functional programming features, as well as basic imperative features (for the rare times you might need them). You can augment Aml with your own domain-specific language semantics by writing an Aml Language Module in F#.

Aml was designed to solve the problem of having to write each domain-specific language from scratch. It includes all the features you would expect from a stripped-down general purpose language, and allows you to write only the 'sub-interpreter' (AKA, Aml Language Module) needed to interpret code specific to your domain.

One could say that lisp already solves this problem, but Aml hopes to do this specific task better than lisp since writing domain specific languages in Aml is done with F# rather than with macros. Also it's deployable to .NET out of the box. In fewer words, Aml is the free foundation you need to get your domain-specific language up and running with absolutely minimal development time on .NET, and without hassling with macro debugging!

The one domain-specific language I've been building for Aml is a declarative object language that uses declarative attributes to implement interactive applications like UIs and simulations. Unfortunately, I made a muck of the original implementation, so it is now being rewritten. So if anyone remembers me talking about DOL, that was it. It is now being rebuilt as DAL (declarative attribute language) and should be a pretty killer little language for games and such once I get it done (probably take another month)... That is, if .NET's garbage collector pauses will be tolerable as not to drop the frame rate intermittently (fingers crossed).

Please take a bit of time to read the AmlSpec.rtf file in the Documentation folder, read the Stdlib Aml code in the Stdlib folder, and run AmlRepl.exe to play with the language. Any feedback at all is welcome, and I would love to answer any questions!

PS -

The best current way to read / edit Aml files is to -

1) Install 'TextPad 7'
2) Copy 'Aml.syn' from the 'aml/Plugins/TextPad' directory to the 'Program Files (x86)/TextPad 7/Samples' directory.
3) In TextPad 7, 'Cofigure' -> 'New Document Class', type 'Aml' for 'Document class name', and finally type '*.aml' for 'Class members'.
4) Restart TextPad 7 and open the Aml files in the 'aml/AmlRepl/AmlRepl/Stdlib' directory.

Voila! Nice syntax highlighting!

Endofunctions are functions f of type A->A where A can be any type. Since all functions are potentially partial functions we can use endofunctions to model linked structures.

E.g. if we have an object which has an optional reference to an object of the same type, the optional reference can be viewed as a partial function f of type A->A. If the reference to the next object is void (there is no next object because we are at the end of a linked list or we have reached the root of a tree following the parent links) then the corresponding function f is undefined for this specific object.

The paper "Endofunctions, cycles and chains" describes endofunctions and derives assertions about endofunctions which are important to reason about linked structures. It is based on the papers "Complete lattices and closure systems" and "Closures and fixpoints".

The Scheme Language Steering Committee (SLSC) has announced a vote on whether the ninth draft R7RS produced by Working Group 1 should be endorsed by the SLSC.

Votes are due by the end of Sunday, May 13, 2013. For full instructions on how to vote, with explanation of what the vote is about, please see this posting to scheme-reports, which is reproduced here for your convenience.

--------

The Scheme Language Steering Committee (SLSC) is pleased to
request your vote on whether the ninth draft R7RS produced by Working Group 1 should be endorsed by the SLSC. Your vote is due by the end of Sunday, May 13, 2013.

The purpose of this ballot is for you to register your views about the work of Working Group 1. In particular, you are being asked whether the ninth draft of R7RS-small, Chibi Scheme, the sample implementation, and the test cases satisfy the requirements of the WG1 charter (excluding the section labeled "Timeline"). Please send your vote to the scheme-reports mailing list between Friday, April 19, 2013, and the deadline of Sunday, May 13, 2013, inclusive.

Please use the following form when you post your vote:

--------

Full name (required): Insert your name here.

Location (optional): Insert your physical location here.

Affiliation (optional): Insert your institutional affiliation, if any, here.

Contact details (optional): Insert any contact details here. The email address from which you post the ballot will be assumed to be a primary contact method, unless overridden here. You can use a temporary email account if you don't want your main email address revealed.

Statement of interest (not required if you registered for the R6RS ratification or the 2009 Steering Committee election): Insert at least 75 words of original content explaining your interest in Scheme and the Scheme standard and your stake in the outcome of the ratification process.

Vote (required): Insert "yes" or "no" here.

Rationale (optional): Insert your explanation of why you voted the way you did here. Anyone voting "no" is particularly encouraged to complete this section.

This ballot is a variant of the registration and ballot forms used for the R6RS ratification process and for the Steering Committee election. Both registration and voting are combined into a single form. Note that the entire contents of the ballot will be published.

--------

The Scheme Language Steering Committee
Will Clinger
Marc Feeley
Chris Hanson
Jonathan Rees
Olin Shivers

Teaching garbage collection by implementing GCs can imply heavy curricular dependencies. We've worked at shrinking them so the material can be used in any number of contexts, and this material is being used by several universities that use PLAI. We have a pedagogic paper about our approach, which we've summarized in a blog post (with a link to the full paper).

In PLDI this year: Ben Titzer, "Harmonizing Classes, Functions, Tuples, and Type Parameters in Virgil III" [pdf]

Given a fresh start, a new language designer is faced with a daunting array of potential features. Where to start? What is important to get right first, and what can be added later? What features must work together, and what features are orthogonal? We report on our experience with Virgil III, a practical language with a careful balance of classes, functions, tuples and type parameters. Virgil intentionally lacks many advanced features, yet we find its core feature set enables new species of design patterns that bridge multiple paradigms and emulate features not directly supported such as interfaces, abstract data types, ad hoc polymorphism, and variant types. Surprisingly, we find variance for function types and tuple types often replaces the need for other kinds of type variance when libraries are designed in a more functional style.

A paper I just finished on live programming (and submitted to the normal place for publication), abstract:

Programming today involves code editing mixed with bouts of debugging to get feedback on code execution. For programming to be more fluid, editing and debugging should occur not only at the same time, but also in the same space to quickly make use of the resulting live execution feedback. This paper describes how live feedback can be woven into the editor by making places in code execution, not just in code, navigable so evaluation results can be probed directly within the code editor. A pane aside the editor also traces execution with entries that are similarly navigable, enabling quick problem diagnosis. Both probes and traces are refreshed continuously during editing, and are easily configured based on debugging needs. We demonstrate the usefulness of this live programming experience with a prototype.

I've also cut a couple of videos for the paper, though they might require reading up to Section 3 in the paper to make sense of them:

• Using LPX to write a square root function.
• Using LPX to write a Fibonacci function.

I promise to do better on the videos in the future :) Also, consider checking out the "It's Alive" paper, I'm surprised no one commented on it yet, but its been really slow on LtU lately! For historical reference, this is the main follow up to my previous live programming paper, but much of the thinking has changed significantly.

Edit2: a brief history of progress live programming as I see it now (note that this is controversial depending on how you define "live programming" or "progress"):

Liveness was applied to UI applications (VisiCalc) long before it was applied to programming. VisiProg might be the first language to explore liveness in programming (85), though I would argue that Sutherland's SketchPad (63), a more limited "language" to be sure, precedes it by about 30+ years, and is the first example of liveness applied to UI or programming. But VisiProg definitely gets the cake for being the first to clearly point out the property; while VisiProg, at least in its XED implementation, appears to be textual.

A bunch of visual languages afterwards support liveness without really calling it such; Tanimoto (91) coins the term liveness to describe what they are already basically doing. Maloney and Smith re-coin the term liveness a few years later (95), independently of Tanimoto, to describe basically the same property in Self's Morphic. Burnett elaborates on Tanimoto's liveness in a nice VPL paper (98). In the mean time, REPLs and fix-and-continue environments abound in the Lisp and Smalltalk communities, but these are hardly live in the sense used here (though they also focus on early feedback).

Hancock is the first to really put the pieces together in his dissertation (03), coining the term "live programming" for the first time and applying the concept to an almost non-visual language (Flogo II). He focuses on the nature of the feedback, going beyond just seeing the result evolve in real time through a mechanism he refers to as "live text". Edwards (04) coincidentally does something very similar with his example-centric programming environment, using different terminology, and a focus on continuously executing examples.

Recently, Bret Victor revived interest (well, at least mine) in this area starting with his Inventing on Principle talk ('12). Although he eschews labels, many of his examples focus on getting better more timely feedback about program modifications, and is quite similar to the goals of live programming. His Learnable Programming essay further elaborates on these topics.

A paper by Burckhardt et al that will appear at PLDI 2013. Abstract:

Live programming allows programmers to edit the code of a running program and immediately see the effect of the code changes. This tightening of the traditional edit-compile-run cycle reduces the cognitive gap between program code and behavior, improving the learning experience of beginning programmers while boosting the productivity of seasoned ones. Unfortunately, live programming is difficult to realize in practice as imperative languages lack well-defined abstraction boundaries that make live programming responsive or its feedback comprehensible.

This paper enables live programming for user interface programming by cleanly separating the rendering and non-rendering aspects of a UI program, allowing the display to be refreshed on a code change without restarting the program. A type and effect system formalizes this separation and provides an evaluation model that incorporates the code update step. By putting live programming on a more formal footing, we hope to enable critical and technical discussion of live programming systems.

Rust 0.6 is released. Rust is a systems programming language with a focus on safety, performance and concurrency.