Lambda the Ultimate

My doctoral dissertation is now publicly accessible at
http://www.archive.org/details/TheoreticalFoundationsForPracticaltotallyFunctionalProgramming

I believe it may be of interest to many here.

For those with an interest in the lambda-calculus there's lots of lambda-goodness, too much to summarise here, but includes:
- Functional representations of data and operators on them, beyond Church encodings (Chpt 5): See where Characteristic Predicates and Combinator Parsers 'come from', and how they and many like can be derived
- Typing functions on Church Numbers (Chpt 4, and appendix)

There's also some rather deep foundational discussions
- What actually is 'interpretation' (Chpt 7)
- Turing-Complete computation without using tests
- Language-extension done via definitions, vs via interpetation (Chpt 6)
- That the bit (ie binary) isn't the smallest unit of information

if one had to pick one language to write a program that would then be translated into any other language at random, what would be the best language to pick.
(obviously not all conversions could be done efficiently !)

Obviously as a c++ programmer i'm asking this with various dividing lines in mind.. pure vs impure functional, garbage-collection vs manual, static vs dynamic types.

maybe the question is nonsensical but i'm sure this forum will have interesting insights. :)

I've been reading about programming language implementation for a while now as a hobby. Last week I had the knowledge, time and energy to implement in C an interpreter for a portion of Scheme. I'd long wanted to do just that. It was definitely the biggest thrill I've had in programming to implement an interpreter and see it run while interacting at the REPL. :-)

Then suddenly I had a "now what?" moment. Even though I didn't implemented an efficient interpreter, I now understand the basic, general principles of language implementation (interpreter or compiler.) Clearly I'm not a highly skilled language implementer after my little bits of book reading and experimentation. Even so, the big mystery of programming languages seems mostly gone. It is a strange feeling after years of thinking programming languages were something the gods handed down to some mortal on a hill.

Programming languages are certainly the part of computing that interest me the most. That said, I don't think I'd ever find a job that suits my life better than my current web programming job. From what I understand programming language implementation jobs are rare anyway. Stopping work to indulge in grad school for five years is not an option. Maybe when I retire. Developing a hobby language that fits the bill of dynamic languages like Scheme/Perl/Python/Ruby seems like an unnecessary reinventing of the wheel.

I'm not sure what will be next for me and programming language hobby time. Anyone else have similar experience wondering what to do with newly acquired abilities?

Registration is now open for the Workshop on Non-Traditional Programming Models for High-Performance Computing (part of the Los Alamos Computer Science Symposium). The symposium and workshop will be held in Santa Fe, New Mexico on October 13-14, 2009.

The goals of the workshop are two-fold:

1. To begin to identify, specify and capture in writing, the problematic issues and barriers inherent in today's scientific software construction process.
2. To expose attendees to non-traditional programming models with the express purpose of igniting thought and discussion on the future of large-scale scientific programming.

The one-day workshop will consist of three sequential tracks, each lead by a moderator/facilitator. The tracks will include a small number of speakers who will each present a short position paper outlining their thoughts on current problems and how specific non-traditional techniques may be applied to address these issues. Following the presentations, the moderator will lead a discussion with the audience on the ideas presented by the speakers. Both the position papers and the captured discussion will be published on the workshop web site. It is our hope that the output of this workshop, perhaps refined, can act as input to a future meeting or workshop on this topic.

(at the web site, click on the workshop title to display the preliminary agenda)

The Event Calculus is a formalism coming from the AI community that's been applied to a variety of areas, such as common sense reasoning, natural language, and robotics. See Erik Mueller's book "Commonsense Reasoning" for an exhaustive discussion. I also think it's a promising formalism for dealing with (soft real time) event driven systems generally. My work has led me to develop a system using the Discrete Event Calculus (DEC) as a programming language and I'm wondering who else would be interested.

In a nutshell, the event calculus is a logic over two kinds of terms - events and fluents. Fluents are terms that either do or do not Hold for stretches of time (i.e., they are true at some times and false at others). Events Happen at various times and can Initiate or Terminate fluents. An Event Calculus program is a set of rules each of whose LHS is a condition over events and fluents and whose RHS is (mostly) an Initiate or Terminate predicates (there are a few other possibilities). DEC is the version of the Event Calculus which has discrete time (things happen in time steps). Up to this point, (D)EC has been used statically by creating a set of rules and then either doing model checking, planning, or otherwise determining if some property holds true in the future of the model.

Over the last few years I've been involved in a startup to enable NPCs in various environments to engage in meaninful dialog. Because of the context that can go into understanding an expression, I ended up using DEC as a programming language because it allows reasoning over past and present, as well as who's doing what right now. The system executes a time step at a time (basically a frame at a time). Events in the outside world are converted to events that Happen at that time step in the simulation, and some of the events generated in the simulation are in turn transmitted to the outside world as commands.

There's a draft paper describing this at http://www.paideiacomputing.com/EventCalculusGames.pdf

An example of it working is at http://paideiacomputing.com/videos. In the second movie (Simon Says), the NPC is entirely driven by a DEC program.

been reading up a bit on functional languages lately out of interest (99% a c/c++ programmer myself)

I was curious if any of the multi-paradigm languages distinguished 'Functions'(without side-effects) from 'Procedures'(with side-effects) as a means of cleanly separating pure functional code from the rest... is this a common/usefull concept or not?

obviously in c++ i'm used to the idea of const pointers to have some concept of what gets modified but there's always globals & over-rides there...

Recently I posted a blog entry about some work I was doing on a novel object system, which I called Categories. That post generated a burst of commentary in a couple of places; one relevant comment suggest that I should post something about Categories here.

I thought, "that's a good idea; why didn't I think of it?" I've been reading LtU for years. What better place to find people who will tell me all the things that are wrong with Categories?

The main point of the Categories object system is to clearly and cleanly separate representation, behavior, and taxonomy. I wrote an article entitled "Protocols" eighteen years ago that explained why one might want to do this, and suggested that most object systems conflate at least two of them.

By "representation" I mean the concrete layout of data in storage. Behavior is the set of operations that are defined over some data. Taxonomy is the collection of representations into categories, and the superset/subset relations among those categories. My claim is that these three concepts are logically distinct, and that, although most object systems don't do it, it's possible to treat them distinctly.

Why should anyone care? The article linked above provides one argument. Another way to look at it is suggested by a comment from Joe Armstrong in Peter Seibel's new book, Coders At Work:

“Because the problem with object-oriented languages is they’ve got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana and the entire jungle.”

The fact that I want the behavior of a shape doesn't necessarily mean that I want the fields that some other programmer used to represent it. Pretty often, I want the behavior of an existing class without the representation; or I want the representation, but not the taxonomy. Haskell gets it right, in my estimation. In Haskell, representation is handled by datatypes; behavior by functions; and taxonomy by typeclasses.

I love Haskell, but I'm a Lisp-hacker by nature. If there's a way to do my work in a Lisp, that's what I'll do.

When I found myself dissatisfied with Clojure's treatment of types and polymorphism, and I started coding around the parts I didn't like, I ended up writing an implementation of types and polymorphic functions that pretty closely tracked the ideas in that old article. This bit of work I named "Categories".

Categories is a library written in Scheme and in Clojure. It implements a treatment of types and polymorphic functions that sharply distinguishes representation, behavior, and taxonomy.

Representation is handled by elements called, oddly enough, "representations". A representation is a concrete specification for storing data. In the Scheme version, for example, fixnums and vectors are representations.

Behavior is handled by functions. A function is an applicable object that accepts zero or more values as input parameters, and computes and returns zero or more values as outputs. Functions are polymorphic. A function examines its inputs and, based on some computed characteristic of them, chooses some concrete piece of code, called a method, to run.

Taxonomy is handled by domains. A domain is a description of a set of types, the relations among them, and the rules that functions use to select methods based on the types of their inputs.

Types are sets of values. Concrete types are aliases for representations. Abstract types are nothing more than names, commonly used in Domains to collect and organize related concrete types. As an example, Gambit has built-in fixnum ad bignum datatypes. The Gambit implementation of Categories has concrete and types that are aliases for these representations, and an abstract type that the default domain defines as a supertype of both.

This arrangement of elements accomplishes what I wanted: it completely separates representation, behavior, and taxonomy. Okay; so what? Is there anything else good about it? Is separating those concerns actually good in practice? What's it like to use it?

Obviously, I'm biased. It's what I wanted, so I like it. It's also very young; the present code is the result of tinkering around for five months. The API is still moving around some, and the working code is still likely to have significant bugs at any given moment.

Keeping those caveats in mind, I have been using Categories in production code for a few months, and there are definitely things I like about it. I like it well enough that, when I began work on a new project in Scheme, leaving my Clojure work aside for a bit, I missed Categories and ended up porting it from Clojure to Scheme.

It's very easy to build whatever abstract types I want. I simply alias the needed representations and use a domain to collect the resulting types into a convenient arrangement. If that arrangement turns out to be inconvenient later for some other API, nothing is lost; it's quite easy to make another domain that is as similar or different as I need. Once created, domains are invisible, except when creating new functions. The function constructor takes a domain as a parameter, and the new function remembers it. Later rearrangements of the domain's types are automatically visible in all existing functions defined on that domain, but have no effect on functions defined with different domains.

Like Haskell, Categories enables you to define data layouts, functions, and classes of types completely independently. Like CLOS, it also enables you to arrange for 'inherited' behavior, if that's what you want. A domain can tell you whether a method is applicable to a sequence of argument values, and, given two applicable methods, it can tell you which one is more specific to the particular argument values. Categories can therefore support CLOS-style next-method dispatching--if you want it. The API is there to provide that kind of dispatching; you can use it or not, as you see fit.

As I say, Categories is still very young, and it seems like every day I still see another way to improve the API or the implementation. You can't get the newest working code; I'm in the middle of refactoring domains again. Older versions are available, but probably less interesting at this point. It might be a week or so before I have a working release.

Feel free to tell me where I'm out of my mind, though, and if you want a look at the code, ask me in a couple of weeks; by then I'll likely have something packaged that's usable.

We all know that, in many languages, null is very semantically overloaded. Has anyone attempted to separate and enumerate its various meanings? A few spring immediately to mind:

• Empty list, set, dict., etc. (one or many?)
• No object
• No value
• Uninitialized

What others are there?

(I am a long-time, on-and-off lurker, first-time poster. Etiquette corrections are welcome.)

I'm pleased to announce the Eastwest programming language and structure editor. This is a research project aimed at exploring how structure editors can help with functional programming. Eastwest introduces the concept of "token type", which is a useful way of handling bindings in structure editors. For beginners, the most interesting feature of Eastwest is that the type of an expression is always displayed at the top of the screen. Eastwest takes into account the type of an expression when displaying suggestions. Arguments can be placed anywhere inside function names which can be written in any character set thus opening the possibility of making source code resemble human language. The structure editor can handle thousands of nodes. Since it is impossible to copy/paste source code, I've created a series of videos showing how to use the structure editor and the language.

the project can be found at
http://sites.google.com/site/rathereasy/eastwest
the video tutorials can be found at
http://sites.google.com/site/rathereasy/eastwest/tutorial
You can download and try it out at
http://sites.google.com/site/rathereasy/eastwest/get-it-

Eastwest is based on the O'caml Structure Editor Toolkit (OSET), which can be found at
http://sites.google.com/site/rathereasy/oset

If anyone knows of any similar projects, please let me know.

World’s first formal machine-checked proof of a general-purpose operating system kernel from Planet Haskell.

Some previous work has been mentioned here before, but I don't think there has been a story on any of the previous work.