Notes toward a Dataspace

Nate Cull's secondary Livejournal

This journal currently focuses on confusing and contradictory mental sketches for an extended programming thought-experiment I call "Dataspace": a kind of mutant hybrid of RDF, Prolog, Xanadu and parallel-programming Lisp. It does not currently have a clearly defined syntax or semantics or implementation, but it does have quivering rage and a blind gnawing hunger. If you value your sanity, run.

Roughly: functional reactive programming for a Semantic Web-style big ol' soup of hyperdata.

My home page (possibly even more disturbing) is at natecull.org.

This Month

Oct. 13th, 2009 @ 09:40 pm Common Sense and Direct Logic

I'm reading this paper at the moment. A lot of my thinking echoes some of these ideas. I'm particularly interested in what happened to Ether and the idea of 'viewpoints' in logic as it seems relevant to making Prolog-like languages fully recursive. I like the idea of removing 'disjunction introduction' as a way of solving the Principle of Explosion .

Also I very much agree with this statement:

The approach which is currently standard in mathematics is the Tarskian framework of assuming that there is a hierarchy of metatheories in which the semantics of each theory is formalized in its metatheory [Tarski and Vaught 1957]. According to Feferman [1984a]: “…natural language abounds with directly or indirectly self-referential yet apparently harmless expressions—all of which are excluded from the Tarskian framework.”
Large software systems likewise abound with directly or indirectly self-referential propositions in reasoning about their use cases, documentation, and code that are excluded by the Tarskian framework. Consequently the assumption of hierarchical metatheories is not very suitable for Software Engineering.

This is pretty huge when you think about it.

Talkback
6 comments Leave a comment Permanent Link

Oct. 12th, 2009 @ 05:29 pm Swarm

Ian Clarke's Swarm, based on Scala's "delimited continuations" looks interesting. Sort of distributed OO where instead of sending a message to a remote object, you send your whole runtime state to the remote system...

Talkback
Leave a comment Permanent Link

Aug. 20th, 2009 @ 11:24 am Functions, Dictionaries, Extended Sets, Relations

Some more mad-scientist data representation theory musings.

1. An extended set is a binary (two-column) relation where
1a. The second column can contain nulls (to represent the 'classical' set membership condition)
1a. Either column can contain either atoms or xsets (which is more general than standard Codd-type relations, but some Date-style relations allow subrelations)
1b. Possibly the first column may need to contain nulls also, since a very common operation we'll want to do on such sets in order to make Joylog work - the set equivalent of stack shuffling - is 'invert', ie, swap the two columns... or possibly do something trickier... but obviously if we invert an xset with classical membership: { cat dog^black dog^white } we'll end up with one where null is the first value: { NULL^cat black^dog white^dog }. So generalised nulls might be required.

2. An extended set or binary-relation-with-nulls can be represented as a dictionary where:
2a. The value can be null (to represent classical set membership)
2b. The value can be an atom (which is the same thing as a dictionary with one member )
2c. The value can be a dictionary (representing all possible values / membership-conditions of the key.
2d. There are no conditions on what the key is, ie, it can be a dictionary and not just an atom.
2e. If we allow generalised nulls, the key may also be null.

3. A dictionary is the same as a function except that:
3a. It is fully defined by its extension instead of its intension.
3b. It is finite and non-recursive.
3c. It can be manipulated by means of common operations like 'get list of keys', 'get list of values' and 'invert'.

4. A function can be defined by:
4a. Lambda calculus (which requires a notion of local variable name binding)
4b. Combinatorial logic as in SKI calculus (which requires a global name dictionary for root-level combinators but not a local one)
4b. Joy (which seems to be almost but not quite like combinatorial logic - compositional rather than applicational).

What I'm interested in right now is blurring the boundary between dictionary and function.

5. Can dictionaries do things or provide guarantees which Lambda/SKI/Joy functions can't?

5a. Can we 'invert' a function? Can we 'get list of keys' for a function?
5b. Can we, in other words, treat the extension* of a function like a dictionary - infinite and recursive if necessary - and perform operations on it?

* At the moment I'm not interested in allowing other functions to 'read the source' (the intension) of a function. For security reasons this seems like a bad idea. It's a capability which is needed at some level in a system (for implementing, eg, OO inheritance), but I think we can do that by defining another function which provides both the source and the extension of a function.

6. If a type is a dictionary is a function, does it mean that:
6b. Taking the 'list of keys' of a function/dictionary is the same as getting 'the domain'?
6c. Taking the 'list of values' of a function/dictionary is the same as getting 'the range'?

This is the idea which lies at the heart of Dataspace, I think. Use a very simple functional language to define 'computed dictionaries' - their extensions - and then compose these dictionaries such that they get recalculated in realtime as the functions they compose over change.

7. Why can't we do these operations in existing functional languages?
7a. What's the simplest possible self-consistent way of allowing a function to become aware of another function's domain and range, or of converting a function's domain/range set to an iterable structure like a list?
7b. Is this some form of type reflection?

Say we have a dictionary: { a = b, c, d = { e, f } }

If we were to get the domain and range of this dictionary, we'd get:

{keys = { a, c, d }, values = { b, d, { e, f } }

More to the point, if we were to convert a dictionary to an iterable list-like structure we might get:

{key = a, value = b, rest = {
key = c, rest = {
key = d, value = { key = e, rest = {key = f}}}}}

This looks sort of like an evaluation function which is able to provide an argument as well as a value... is this the missing part? The normal Lisp or even Joy evaluator won't provide a 'rest' or 'key'... but what if we defined a 'meta-eval' which does?

This seems sort of like requiring that all functions have an 'iterable type' associated with them. Or an 'iterable domain' (and maybe 'iterable range'). Dictionaries, of course, have this as standard. But this doesn't seem to have usually been defined for functions - even in languages which do strict typing....

I think this is because strict-typing languages still think in terms of 'set' and 'type' being completely different entities, and not wanting to expose types as first-class data structures to the runtime. Because of Russell's Paradox? But I'm sure this will work. Prolog proves that something like this can work and be very simple. It just hasn't been fully explored yet.

I think we can generalise Prolog if we make types *literal* dictionaries/functions AND define a 'meta-eval' which exposes this type-like metadata via list-like iteration operators. And I think it won't explode in a smoking heap of self-reference if we do that.

Granted I'm willing to accept a bit of Prolog-like non-logical-ness, such as insisting on a strict ordering of 'set' membership, if that makes enumeration of recursive sets doable. I think that's roughly like what McCarthy came up with with Lisp's original 'cond'. Possibly also what Russell came up with with his original 'type' idea which is just a measure of nestedness. I think this is also related to the insight of Joy that things work out a lot simpler if we impose linearity on the evaluation of functions so that we have a stack-like sequence of data rather than name binding. I also think this is related to the problem of multiple namespaces and how to represent name-binding within a logic system itself, which crosses into General Semantics and the idea of 'consciousness of abstraction'. There's an irreducible element of reflection which needs to be added into a logical system to let it become fully self-describing.

It looks like we could reduce 'meta-eval' to two functions:

* domain - returns a set (function/dictionary with all values = null) of a function/dictionary's domain (keys/arguments)

* iterate - returns 'first' and 'rest' mappings of a function/dictionary, where 'first' is a subset function/dictionary with only one key/argument and rest is a first/rest pair (or a subset to which we can re-apply iterate?). This corresponds to partial evaluation, coroutine 'yield', or to Prolog backtracking.

Talkback
1 comment Leave a comment Permanent Link

Aug. 18th, 2009 @ 02:29 pm Joylog: Beginnings

I think I'll call my compositional Prolog 'Joylog'.

The curent outstanding issues with the algebra are:

1. Do we want blocks to be automatic unions, or to be just raw extended sets? I'm tending toward the latter, since I think we can wrap any but it probably depends on what's most likely to be used

2. Does the nil result set mean true or false? Do we need a #false symbol like Scheme, and if so, how does it behave if we compose it with other set members?

3. This is basically a functional representation of logic, and as such, seems obvious. Surely it's been done before? If so, by who, and why hasn't this obvious path been pursued further?

I don't mind being obvious... I'm just wondering if there's a huge unrecognised gotcha here.

Recapping: The basic idea (if I understand what I'm doing correctly) is to take Prolog-style relations, break them into nested binary relations, and from there into functions. So, eg:

(
(child amy beth)
(child beth carol)
(child beth chris)
)

is an extended-set like structure - a set (expressed as a list) of assertions (also expressed as lists), and roughly like a relation where nulls may exist but only at the end of rows.

This set-of-lists structure can be remapped into a list-of-sets:

(child (
(amy beth)
(beth carol)
(beth chris)
)

which throws away a level of set wrapping to give us in effect a dictionary structure (ie, each row/list of our 'relation' can be interpreted as a dictionary or function). Which means we can do queries on it.

We can continue the remap-and-throw-away-set-wrapping recursively, getting:

(child (
(amy beth)
(beth (carol chris))
)

so we now have a multilevel dictionary structure, which expressed in, say, JSON would look like:

{child: {amy: beth, beth: {carol: nil, chris: nil)}}

but with a cleaner syntax.

(If we do this automatic remapping, like JSON we have dictionaries where the key must be an atom. This is an important limitation and may be too restrictive in the long run, but makes the syntax simpler in the easy cases.)

To this we add a functional/compositional (Joy-like) evaluation operation, where instead of any literal (atom or set/relation/dictionary) we can have a sequence of function applications (possibly starting from and/or setting the 'environment', which is a special function/dictionary). Since our fundamental data object (the set/dictionary) is equivalent to a function, this seems like it would work.

Oh, and to get the equivalent of Prolog's variable unification, what we do instead is apply functions to the result set. So instead of saying 'X has child 'beth': unify and solve for X', we say 'apply function 'invert' to function 'child' to 'beth', to give me the set-of-all-Xs. No unification or variable binding required - just functional application and set manipulation.

Again, this seems obvious - the equivalence of logic and lambda - so I'm not sure why this isn't used more. Are there performance or representation problems with doing this?

There is something subtle going on, I think. These function-like sets don't act quite like lambdas, or even Joy combinators/quotations, when evaluated. This is the fundamental difference between a Prolog-like evaluation model and a Lisp-like one: Joylog sets/dictionaries/functions literally return their entire argument/value mapping set when evaluated. Lisp/Joy functions wait for one argument (or stack) and return one value... these don't. They act as generators/coroutines, and that's important - it means they're self-describing, to a degree, and they also sort of 'carry their own type with them' (since type IS the argument/value set). Which is how Prolog predicates work too.

IE: if I call a Lisp function (frob x), depending on what x I pass I'll get a y in return. Just one, and I have no way of knowing what the other valid values of X are - there could be an infinity of possible values, and short of brute force trying all of them, I don't have access to that information. That's why we have type signatures, to add in some of that 'argument/value set' information which is lost.

Now this one-value-at-a-time, closed box no peeking restriction isn't inherent in the mathematical definition of 'function', which is just a many-one mapping and imposes no restrictions on what that mapping *means*. It's an artifact of the Lisp evaluator (possibly even of lambda calculus) and the 'subroutine' call model which does one thing at a time instead of working in sets. Set languages like APL worked differently and didn't have that problem.

Prolog relaxes this. I have a Prolog predicate Frob(X,Y) I don't so much 'call it' asinstantiate it as a generator of (X,Y) tuples, which are then fed to other predicates and variable bindings which act as filters. So it generates its own type set, and that's why it can be 'run in reverse', which is a really weird feature of Prolog.

This reversability isn't inherent in *logic* so much as in mathematical functions. So: the Joylog approach is to try to get the best of both worlds: the simplicity of functional composition together with the spam-the-whole-set approach of logic. We can have 'functions' which ARE content-addressable dictionaries, which can be operated on by other functions, taken apart and remixed at will.

It's weird as heck but I think it might work.

I think it does however rely deeply on a coroutine/continuation evaluation model: ie, every function must basically be a (computable) type. If I say 'X is the set of cardinal numbers' then that's what it is, both a function and a type - an infinite set. This probably falls apart when it comes to the reals and other left-recursive sets, so there are limits - in other words, to evaluate a set like that you have to wait for some further input before you start the infinite spamming. This is less of a problem in database and knowledge representation programming though since our universes of discourse tend to be finite sets. But many second-order functions are infinite, so there's some cleverness needed in the evaluator to know when it needs to wait and when it can just start spamming.

One would think that Haskell is already doing this (since it allows infinite datasets), but it doesn't seem to be quite thinking in this way. It seems overly complicated for something which is very very simple.

For instance: a 'for loop' is really just a subset of the integers. Which is the same thing as a type. A good programming language should make no distinction between these three concepts at all.

Talkback
Leave a comment Permanent Link

Jul. 21st, 2009 @ 01:34 pm A Compositional Prolog

Here's a small step forward, I think, towards my original several-year-old goal of creating a 'compositional Prolog': a Prolog-like logic language without variable assignment, based on composition of binary relations. There are still some warts to work out to do with the precise semantics and how to implement an evaluator, but its starting to feel a bit clearer. If I achieve nothing else from this whole wild ride, this alone might be useful.

We'll start with the classic ordinary Prolog example: 'child' and 'descendent' (or 'parent' and 'ancestor'). My definitions are a little funky to illustrate how to port between the two languages; choosing meaningful predicate names gets tricky when everything's a binary rather than n-ary relation.

child(alan, bob). ; Alan's child is Bob.
child(bob, chris).
child(chris, dave).

descendant(A, D) :- child(A,D). ; All children are descendants
descendant(A, D) :- child(A,X), Descendant(X,D). ; All descendants of children are descendants

Notice that here we're having to name variables and create a new entity, X, as the intermediate person. We can get rid of all this if we move to a compositional, set-based style.

1. This is an S-expression based language so we start with Lisp-style atoms (words or numbers) and lists.

2. After atoms and lists, we have one special symbol and three types of lists:
a. The first level of list nesting is a 'block': either an atom or a list phrases
b. The second level of list nesting is a 'phrase' either an atom or a list or blocks
c. Any atom or list preceded by ` is a 'query' - a sequence of applications of blocks in a compositional style, evaluating to a block.

d. 'Applying' one block to another means:
d.1. Breaking each block into phrases
d.2. For each left phrase, matching every right phrase to it, and replacing with the rest of the left phrase.
d.3. Compiling all the resulting phrases back into a block.

e. Since a block means 'all of the contained phrases are asserted', blocks can be read in any form but are normalised after reading in the following ways:
e.1. Any phrases for a block which start with the same atom are collected into a subblock
e.2. A block which consists of a single phrase is the same as the contents of that phrase

f. An environment is defined, which initially is set to the 'root' of the assertion database (later we'll try to define ways of manipulating this environment). ` accesses this environment.

g. A number of predefined function-like blocks are defined in the root environment which let us do operations on blocks (or on the phrases they contain).

With this, here's how we'd write the Prolog child/descendant example. We'll assume an invisible set of parentheses defining this set of phrases as a block.

(child alan bob) ; the child of alan is bob
(child bob chris)
(child chris dave)

(descendant `child) ; all children are descendants
(descendant `(`descendant `child)) ; and all descendants of children are descendants

The first thing we notice is that by (e) we can rewrite all the declarations in the normalised form as:

(child ((alan bob) (bob chris) (chris dave))) ; this is the set of children
(descendant (`child `(`descendant `child)) ; this is the set of descendants: all children plus all descendants of children

which is what Prolog does when it compiles a rulebase anyway: bundles all predicates up together. We've erased the difference between predicates and values.

In other words, this is two phrases:
* 'child' means the block of assertions us that 'alan' means 'bob', 'bob' means 'chris', and 'chris' means 'dave'. It doesn't care about the semantics, just this declaration.
* 'descendant' means the block of two assertions:
** everything from 'child'
** and the result of applying 'child' to 'descendant'

What this gives us is a way of describing recursive sets of lists (all sharing at the moment a common name-to-value environment), which is something similar to both SQL-type relations, and to Dave Childs' extended sets... but I'm not quite sure yet, formally, in what ways it's the same and what ways it's different.

Applying ordinary finite (and even recursively-defined) blocks seems intuitively to work, though I haven't quite figured out how to write an efficient evaluator. But writing it out longhand:

1. `(`descendant alan) ; find all descendants of alan ==
2. ( `(`child alan) `(`descendant `child alan) )
3. ( bob `(`descendant bob) ) ; and so on until we terminate in a recursive loop

I think that works, roughly. It seems fairly logical.

What if we want to find a parent? In Prolog we'd have:

parent(P,C) :- child(C,P).

Here we use a concatenative-language trick and use a 'swap' operator. I'll call it 'inverse':

(parent `(`inverse `child))

Inverse takes a block and swaps the first two levels of assertions, so if this were to literally do it:

1. `(`inverse `child)
2. `(`inverse ((alan bob) (bob chris) (chris dave)))
3. ((bob alan) (chris bob) (chris dave))

which is the definition of 'parent': the inverse relation of 'child'.

So far so good. Now, some of the outstanding tricky problems I don't yet know how to solve:

1. What's the difference between 'true' and 'false' and 'nil' if you have a query that matches its source completely? Ie:

`( (child alan bob) (child alan) ) would return 'bob'. But:
`( (child alan bob) (child alan bob) ) -- what is the result, is it () or (()) ?

Prolog would return 'true', but we haven't defined a 'true' value. I'm toying with (()), but that seems problematic for a number of reasons. Locking down 'true' and 'false' seems important and non-trivial - Scheme and Lisp, for instance, argue over whether 'false' is the same as 'nil' or not.

What should be the result of sending True a query? What should be the result of using True as a query?

4. This all seems to hinge on a block being 'a set of assertions' which can be rewritten - but is this valid? Does it allow us to create all meaningful data structures? Is it fully homoiconic?

5. Can we write all meaningful 'function-like blocks' or set-type operations such as 'swap' as blocks using the phrase-matching rule, or do we have to treat blocks as special units which aren't automatically rewritten in these cases?

6. How do we manipulate environments, or write macro-like operations?

7. What logic/algebra does this describe? Is it a form of modal logic? Is it equivalent to relational theory, or different? Is it equivalent to extended set theory, or different? Is it equivalent to first-order logic, or different? Is 'applying blocks' the same thing as applying functions, or different?

Talkback
Leave a comment Permanent Link

Jul. 8th, 2009 @ 02:26 pm Resculpting the Mashed Potatoes

9/10 of all knowledge seems to be learning the names of things. The other 1/10 is finding the similarities between things which have different names but are in fact the same thing.

I feel like the Close Encounters guy. "This means something... but I don't know what". I apologise for not being able to communicate clearly what it is I'm seeing; I get frustrated and dump that frustration on to others. This is my fault and I need to do better. There is much I need to learn. I've put off learning GUI programming because it instinctively 'felt wrong' at a deep, gut level; but I have to wade into that pool and *try* to understand so I can communicate. And then try to test my ideas.

I think what I am advocating is (1) the good old fashioned message queue concept, but (2) implemented at the language level.

(1) is mostly boring and ordinary and how all modern windowed systems work
(2), however, doesn't seem to exist anywhere. And yet it seems the natural, obvious thing to do.

( Read more... )

Talkback
Leave a comment Permanent Link

Jun. 23rd, 2009 @ 05:12 pm Reifying the Event Stream

I've been poking at PLT Scheme, as it appears the most immediately accessible Lisp/Scheme that comes close to meeting the bare minimum requirements for a modern system (editor and GUI). The first experience was... deeply unpleasant, as the documentation is not up to date and the whole package seems to go out of its way to exude a 'we're a teaching language, not a real language - if you want to write actual programs, go away' vibe, but with some help I've managed to get to graphical Hello World.

Now I just need to navigate the Byzantine complexity which is MrEd, the PLT GUI toolkit. It looks powerful, but power is not really want I want; sanity is. However, no current GUI toolkit is sane so I guess I have to wrestle with the beast.

Looking at the GUI docs reminds me how mysterious most GUI systems are: combining an event loop/queue/dispatcher system with an object/class system. I think part of my deep sense of unease/revulsion with this model is that these two things shouldn't have been merged together in the first place.

The notion of an event stream is good, I think; that comes from message passing, and gets us FRP. But I suspect where GUI/OO systems derived from Smalltalk went wrong is probably around Smalltalk-80 and/or Scheme: as an efficiency measure, and probably because of Scheme, it was discovered that you could speed up the OO messaging passing paradigm enormously by abstracting out the literal stream of event messages into a sequence of function calls.

And I think that was one of the big mistakes. The other was the hard-coded class hierarchy, and the merging of the two concepts of 'message/event' and 'routing a message to the right component' into 'polymorphic class/method-based dispatch'.

See, if you unbind these two ideas, and get back to this fundamental FRP-like concept that the universe through which the physical computer moves is a timelike stream of events which exist as reified processable objects - which is the core idea of 'message passing' - then you separate the notion of *message* from the notion of *function call* or 'execution event'. A message becomes just that: a bit of *data* which can be treated like any other data. And can be operated on via pure functions; recursive pure functions, if you must, but still without side effects, because all the 'side effects' *are* the reified event stream.

(Sidenote: This is also roughly the same discovery behind Joy's transparent, runtime-manipulable quotations. A quotation is essentially a reified event stream. An opaque lambda... isn't.)

Even in Scheme, see, you can't really treat 'the invocation or evaluation of a function' as a bit of data. You can sorta, kinda, do it via the continuations, dealing with the whole call stack as one entity; but that's ugly, messy, and not very well standardised. And misses the whole point of the sheer beauty of all programs being operations over event or message streams. It misses the symmetry between 'instruction or call being executed by a CPU' and 'message or packet travelling over a wire', the symmetry between space and time.

To try to unpack further what I mean: look at today's big Web servics. Look at Facebook and Twitter. What do you see there, on the main page? An event stream, reified as data. You see a spacelike view of timelike events. And this is what makes these services so powerful. You have this 'lifestream' of events, existing just as messages, which can then be processed as events or stored as data, or transferred between any combination of the two.

That's what the message passing desktop, before Smalltalk-80 and Scheme shrunk OO into the much narrower idea of 'polymorphic execution of methods', should have been. It's what we have to get back to.

We have to unwind our tightly-bound object systems which have abstracted away all the actual message passing into fast local calls of compiled native code - and turn them back into streams of *actual* messages, which can then be intercepted, filtered, duplicated, routed, stored, remixed... everything else follows from this axiom, which we've broken.

The early research Smalltalks in the 70s had this property, of messages being actual messages, I believe. The Internet has it at the TCP/IP level. This was a key insight that launched the Actors model, that messages/events are real data-level things that can be operated on. But for whatever reason - efficiency, I guess? - we threw that insight away.

Reify the event stream. All else follows. Then you will get a humane, scalable, morphable environment, whether on the desktop, within the 'program', or at the Internet level. Don't hide your event queue away, as current GUIs do, in a non-programmer-accessible 'toolkit' or 'framework'. Keep it very simple and basic. Events are data. Everything that can happen is something that can be remembered, recreated and reasoned about.

The big unease I have with current GUIs is that they present me, the user, with a shiny polished facade; but it's only a facade. I'm at the mercy of the Application Developers who polish it to grudgingly give me access. Beneath the facade, all these messages are being passed, and these streams of events are the *real* data I want to access; but the GUI toolkit paradigm, in the OO mode, does its level best to abstract away and hide that information - even from the priviledged Application Developers themselves. So neither the user nor the programmer can store or replay system events, without manually reifying (via the various patterns like Observer or Undo); and we all fundamentally lose self-identity and control. Things happen on our system, but we don't know why and we can't control them. We can't sniff the wire and see what's going past. Data is hidden from us.

The Unix IO stream model had this property; an IO stream is a reified event stream. That's why programming in shell script, with pipes, is so natural but GUI programming with callbacks is so ugly.

Will there be a performance cost to reifying the events? Maybe, but I think it's time we paid it. And since these events are usually passed at the language level - at least in OO languages, in Scheme we might be able to rescue the event queue from its burial in the object system, but only by rewriting it - we really need to get into language design (and simplification, not complication) to fix this.

That's my manifesto so far. The next part is that the second mistake - the rigid class hierarchy - follows from not understanding that 'polymorphic dispatch' is just a very small special case of 'dispatch and routing' which itself is just an application of the much more useful 'filter over the event stream'.

And a filter is a function, and a stream is a sequence of tokens. You can see where I'm going with this, I hope. There's a direct one-to-one correspondence between 'program text as sequence of tokens' and 'program execution as sequence of messages / reified events'. Do it: close the loop.

Give us generic filters, and we don't *need* classes, polymorphism, single, multiple inheritance, generics, mixins, as language features... all of that we can build ourselves, from pipe networks.

I think. Organising a message schema ontology without inheritance; that's the next big challenge.

Talkback
Leave a comment Permanent Link

Jun. 16th, 2009 @ 04:52 pm Refactoring: Tube

Reading the Yahoo Concatenative group reminds me how little I actually understand about the formal foundations of concatenative languages.

The little language I'm playing with - let's call it Tube - is trying to express my half-formed intuition that for the purposes of modelling input/output in a pure-functional manner, what seems to fit best is a concatenative language with not a stack, but a pipe or stream. Also, with at least one explicit 'force eval' symbol to designate 'apply function'.

The 'not using a stack' bit is quite strange in the concatenative world, but there are experimental little languages out there (like, say XY, which I don't pretend to understand) which do similarly odd things.

The main quality I think I want to get from this is the ability for something like lazy evaluation of an I/O stream. So, eg, we get something like this:

output1 output2 output3 . [ program ] input1 input2 input3 input4

where '.' is the 'force eval' symbol. '.' means 'evaluate the next symbol as a program, and let it add whatever it produces to the stream'. And 'inputX' and 'outputX' are literal symbols. The result of partially applying this might be:

output1 output2 output3 output4 . [ new-program ] input3 input4

Intuitively, what this means is we have a program which, like a knot on a thread, 'slides along the data stream', and either evaporates completely into literals, or turns into a sequence of literals plus a recursive continuation.

In any case, it's all just one stream of data that happens to include computation. It's a logical timeline, past to future. Output is consumed from the left, and input is appended to the right. It looks very elegant and adapted to processing real-time streams of data: we don't have to wait for it all to come in (as on a stack) before we start processing, and there need be no particular coupling between incoming and outgoing data. In fact we really make no distinction between 'communication stream' and 'program' at all. Computation could occur at any point along the line. The only rule that actors reading the stream have to respect is that if you see a ., you must stop and compute before continuing.

For instance, a character-to-line parser might look something like this:

[ This is line 1 ] [ This is line 2 ] . [ char-to-line-parser ] L i n e _ 3 _ CR L i n e _ 4

I think this idea is useful, but I can't yet prove why. I'd also like to know if this comes out as much the same language as XY, or not. It does seem to be roughly continuation-passing style as XY is and has a similar idea of 'pushing to the queue'.

If on top of this we add some variant of ':' for 'eval against environment', then possibly we lose some useful features of concatenative-ness, but then again perhaps not. I can see how we could define a program in low-level primitives and write the rest of the language as an interpreter. It's probably time to start building an interpreter and playing with this for real.

The point of all this (and there is a point, sort of) is that given a language like this: what's the equivalent of a REPL or I/O shell for it? A program in Tube is nothing more than a filter over a stream, which means for ALL I/O it needs a canonical 'input stream' and 'output stream'.

This is defined under the Unix shell for text I/O (if we ignore Standard Error), but to integrate a language like this into the GUI world... we need some kind of 'universal event stream' model.

And that's what I'm REALLY interested in.

Theoretically, we could take this right down to the hardware: a box with RAM or hard drive and a single network port for 'in' and 'out' should be describable, trivially, as a Tube program. (*) But things should get interesting if we can go a couple steps up and isolate out specific stream-transforming functions within a host or OS or user session or program. At that point we might have a hospitable, fully parallel system that's nice and simple to program in.

* Though for an interactive host like a PC with screen and keyboard as well, presumably we'd want to multiplex network and local I/O into one stream. So we might have eg, something like this:

net-out: packet1 net-out: packet2 screen-out: image1 net-out: packet3 . [ desktop-OS ] net-in: packet1 keyboard-in: buffer1 mouse-in: click1

and so on. Is this a solution, or even useful? Not sure, but at least it seems interestingly different.

Talkback
21 comments Leave a comment Permanent Link

Jun. 12th, 2009 @ 01:11 pm From Strategic Computing to Recreational Symbolic AI

For people like me who are obsessed with trying to understand the causes of the 'AI Winter' and why languages like Lisp and Prolog vanished so rapidly, the history of the US Strategic Computing Initiative makes fascinating reading. This is a book I may end up buying, but for now I'm just glad Google Books has as much of it online as they do.

One of the survivors of that era, Cyc, seems to be becoming both Wikipedia and Semantic Web aware, which is probably a good thing.

Cyc is one of the reasons that I am disenchanted with the current state of Interactive Fiction - Inform 7 in particular - because it reminds me powerfully of the AI dreams I had in my teens, and how little we seem to have progressed since then.

When I was around 13, I wrote my first natural-language parsing experiment (in IBM PC BASIC) that was able to take declarative sentences like 'the book is on the table' and answer queries like 'where is the book?' It was a huge buzz and, together with playing Adventure and Scott Adams and Infocom, opened a door in my mind to what a suitably smart computer could do. It really boggles me that Interactive Fiction today doesn't even attempt to provide that kind of parsing suport.

At a bare minimum, I want to write AI NPC agents which are able to manage their own world knowledge stored in declarative rules of the same form that Inform 7 uses to write the world. They need to be able to explore, remember facts, infer rules, and construct data structures representing what they think the rules of their universe are. This means I want a declarative relational/functional language, capable of being modularised at a very fine granularity and potentially distributed over the web (to, say, connect to things like OpenCyc), which is what I'm struggling to express here.

This language needs to be somewhat like Prolog, and somewhat like Scheme. But neither seem to have got the foundations quite right yet. Prolog particularly suffers from the one-big-shared-namespace problem.

The minimum sort of thing I want to express is:

1. The rules of (standard game model) are: { bunch of assertions, possibly out on the Web }
2. The specific rules of this game are { bunch of assertions, possibly including/overriding 1 }
3. Character A's personal knowledge is { bunch of assertions, possibly including/overriding 2 }

These all need to interrelate so they must share a common syntax and semantics.

Note that 3 is going to be constructed and managed at runtime, so we can't have any dependencies on a magic compile-time syntax like I7. It's all got to be uniform structured data. Compile for efficiency if we MUST, but the programmer can't be asked to care - that's purely a machine issue.

The question I keep going around to the point of frustration is: do I want a functional (Lisp, Scheme, Joy) or a relational (Prolog, SQL, RDF) model?

The thing is, even functional languages have to have extra-functional elements (like lambda) to create name bindings - ie, definitions, relations or assertions. And relational languages have to have some way of expressing a query lookup or function application - even Prolog's logical variables get resolved to their value at some point, which is where they become functions.

The shocking thing is that Prolog's namespace deficiencies come straight from first-order logic, which doesn't understand namespaces. I *think* Kripke tried to introduce the idea, but not in a particularly easy to follow way. Meanwhile McCarthy started playing around with recursive functions and lambda and (cond) and IPL and created his own thing, Lisp. And then Lisp lead to Planner, Simula led to Smalltalk, which plus Planner led to Actors which led to Scheme. Then we had DL/1 and CODASYL and Codd's relational algebra/calculus and SQL. So we seem to have a case where the straightforward and obvious needs of computer knowledge representation have outstripped formal logic, so suddenly we're in a realm without decent formal foundations. This seems to be a rather large problem and explains why the database and OO industries went off in so many different directions - and are still a big noisy Babel.

If we look at Extended Sets, it seems like the core of an assertion - or relation, or binding - is a pair of (key, value) or something similar, with no other constraints. And a query is something like (set, key). But we can stack up assertions into a set, while we can't quite do that with queries. Or can we?

When we come to encoding 'the book is on the table' as an assertion, what we mean is something like: 'the thing known as BOOK in namespace X implies, among other facts: { relation known as ON in namespace Y, thing known as TABLE in namespace Z } '.

When we ask 'what is the book on?' we mean something like: 'an unknown set satisfies { implies { ON in Y, TABLE in Z}}; substitute in that unknown set'.

So we can get by with one variable, I think. If we use logical variables like Prolog, we're still using one temporary variable, but we're immediately binding it to a local namespace so we can refer to it elsewhere. We need to generalise this lookup-and-bind mechanism somehow.

In functional programming, we tend to use syntactic forms which abstract out that 'unknown set' identifier - and we tend to use scalar variables rather than set variables.

Hmm.

It still seems hard to cleanly identify the difference between 'X is the case' and 'is X the case?' The natural form for the first in relational style is just (X). The natural form for the second in functional style is also just (X). In either case, we seem to have to have a magic out-of-band symbol which means either 'ASSUMING-THAT X' or 'VALUE-OF X'.

This is where my '.' and ':' notation of lambda/mu functions seems to come in, I think, because . literally does mean 'value-of' and : literally means 'assuming-that'. I don't know that we can reduce beyond that. Set and get, write and read, in and out. A pair.

A set is logically an AND. { a, b, c } means (a AND b AND c) or (AND a (AND b c)). The associative property is what gives a set its random-access character.

Namespaces come out as assertions themselves: 'BOOK in X' is the same thing as 'X asserts BOOK' or (X, BOOK).

An IF/THEN/ELSE or COND statement is an exclusive OR. (IF X THEN Y ELSE Z) is the same as (XOR (AND X Y) Z). Can't say this easily in Prolog at all without using cuts. Presumably this is because of its representation of NOT. What Prolog - and standard first-order logic - tends to give us is IMPLIES rather than XOR, which is IF/THEN without the ELSE.

An OR is... I'm not sure. A way of specifying incomplete knowledge, which is kind of bizarre in the real world. 'I know for absolute certain that either or all of X, Y, Z, but I'm really vague on the specifics'. A way of describing multiple solution sets. Potentially a very useful construct which is really hard to enter as raw data in Prolog: 'The murderer is X, Y or Z'.

NOT is the big beasty bear for Prolog and the root of much of its evil, because it assumes open-world semantics. NOT X is not the same as 'current environment does not contain or cannot prove X'. Possibly proper treatment of NOT is closely tied in to inheritance of environments and the whole idea of multiple namespace logic. X at one level can be superseded by NOT X at another level, and that gives you a non-monotonic logic. Which is perfectly okay, I think, as long as we're clear about there being more than one namespace (or time or place), which standard logic isn't.

Thinking about xsets, it seems that a Prolog-like set language *without backtracking* is the natural result. If X can have multiple values associated with it (xset rather than dictionary semantics), then looking up X naturally means 'for all values of X'.

What I'm really trying to invent, I think, is a simplification of CycL, which runs into much the same problems with needing to extend first-order logic to be useful, and its microtheories are somewhat similar to namespaces, so maybe I should just study up on that again. But I think it can be done better. Also, I've been nervous about Cyc because of the possibility of encountering copyright-restricted material which would make it impossible to fully open-source a system derived from it.

Hopefully that's no longer an issue - but the license doesn't entirely make me happy.

"YOU may use, copy, modify, incorporate or create derivatives of and distribute all or portions of the SOFTWARE. YOU may not reverse assemble, reverse compile, or otherwise translate the Software."

Yeah, um, wtf? Fortunately CycL itself seems to be under the Apache 2.0 licence, so hopefully...

Talkback
Leave a comment Permanent Link

Jun. 9th, 2009 @ 10:27 am Dividing the Indivisible

I'm reading François-René Rideau of TUNES and find myself agreeing with a lot of his comments on language/OS design (but not on economics or politics, sorry). Eg: http://fare.livejournal.com/139755.html

Found via his Livejournal: this paper on historical data models.

I particularly like this comment on Lisp's central state as its major limitation. It's the problem I see with 'packages' too. Packages share too much state; they are not network-scalable. The True Language has to be able to work at all scales, from 'programming in the large' to 'programming in the small', probably with just one unit of abstraction. Whenever we invent these multiple different types of abstractions: lambdas vs objects vs files vs modules vs packages vs namespaces - we're overcomplicating something that is actually really simple.

And the problem is that when you add complexity you are actually reducing the expressiveness of your language not increasing it. The problem we have is a lack of a sufficiently expressive core meta-language for representing interdependent, time-space distributed data linked by functional relations. This is not just a perceptual issue. It's not a matter of aesthetics or which language we 'prefer' to code in. It's more fundamental than that. It's that we don't have a way of talking about the relationship of one set of changing, computed data with another - not in a well-defined, recursive way. And until we find that language, we'll be unable to reason sensibly about the problem, instead creating chaos, dividing something which is not divisible - creating artificial distinctions.

Let me try to say that again in the hope it will make sense: creating a new entity type means creating a distinction. A distinction is a barrier to communication, it does not add 'richness'. The best language is one which has the fewest number of core entities rather than forcing them to multiply. The challenge for the future is to remove elements from our languages which are obscuring our vision, not to add them. Whenever we look at our languages or OS environments and see lots of not-quite-the-same things: files, objects, pointers, streams, components, processes, threads, interrupts - we should intuitively realise that something here is very broken and needs to be fixed - or at the very least, if we must tolerate a broken foundation in the short term as an expedient measure to bootstrap our real next system, a unifying layer must be written to expose all of these entities as one correctly defined abstraction.

However, when we start raising this question, we usually get derailed because there is a very strong, pervasive philosophy in both the science and industry of computing at the moment which claims not only that 1) fixing this problem of fragmented languages is fundamentally impossible ('you can't satisfy everyone at once'), but 2) that it is actually desirable ('there's more than one way to do it', 'use the right tool for the right job').

The first objection would be correct if we were simply incapable of even imagining all these different systems. But obviously, since we built them, we are. All these apparently mutually exclusive approaches have been produced in the first place by people using the same mental 'operating system' toolset - human thought. So why can't we formalise *how* we built them and what they do, in a single mechanical language?

The second would be correct if all of those 'right tools' were mutually convertable. But they're not. That's what makes them different tools - not just different applications of the same tool, which is what I'm arguing for - in the first place.

And so we're stuck at this philosophical impasse.

It is annoying that those of us who seem to see this problem in the current situation seem to be stuck at the 'unfocused rant' stage - I know I am and I know it sucks. I can *almost* feel what it is I'm trying to say, but it's enormously frustrating to not be able to put the pieces together.

All I can say is that there's a new paradigm trying to emerge which seems to me to be based on:
* typelessness (or types as first-class functions)
* 100% pure-functionality with I/O handled via functional reactivity (ie, functions over time-varying signals rather than constants)
* massively distributed, parallel, concurrent object-like modules
* completely extensible syntax
* data-centrality and declarative semantics

All of these pieces have to coexist because they work together as a coherent framework, and without them all you don't have the model. We don't yet have a language, or even a paradigm, which brings all of these together. It has to be 100% pure-functional, and that requires functional reactivity or dataflow.

However, all the dataflow languages I've seen (such as Labview, Pure Data or Yahoo Pipes) seem to be weirdly bound to a visual paradigm and have no serialisation as a language; while the FRP frameworks (Cells, Flapjax, FrTime) are all built on top of existing, non-pure-functional languages. Cells particularly requires CLOS, which makes a number of inappropriate assumptions (like a hard class/object divide); Flapjax is limited to the browser; etc.

It has to be declarative, not imperative, and so C, C++, Java, Scheme, Lua, Factor, Io and Common Lisp fail because of their lack of guaranteed purity.

It has to be parallel and concurrent at the instruction level. Erlang has some of this property, but is not pure functional.

It has to be modular at a very atomic level - no shared namespaces, no special 'package' mechanism other than 'object' - which suggests a small prototype OO language like Javascript, Self or Io, but most OO languages make a point of not being at all functional, let alone pure-functional. Where they have lambdas, they are added on as an additional abstraction, which breaks the one-abstraction concept.

It has to NOT have hardcoded types at a level separate from functions, because that makes it impossible to model the real world of network-distributed messages where new message 'types' are created on-the-fly and at 'runtime' - because on the Internet, it's always runtime somewhere. You can never 'escape the program' by creating another meta-level, and that's what type systems try to do. So Haskell fails here.

For the same reason, you need to provide everyone - user, data modeller, application developer, language developer - with exactly the same toolset, language and level of expressive power, and that means full metaprogrammability. Natural languages provide this feature: anyone can make a new word, at any time, just by using it. A computer language equal to the challenge of describing a time-varying, computed, mutable yet functional web of arbitrary data also requires the same ability. Forth, Factor and Lisp have this feature, but not the others.

Some signs of hope: Google Wave, Yahoo Pipes, Flapjax, JavaFX, Joy, Lua, Xanadu, Prolog, SQL Views, RDF.

But none of these approach closure; they all fail to 'close the loop', to reduce the problem to one entity. They're all partial, incomplete, and mutually contradictory. They divide the problem space into 'programming in the large' vs 'programming in the small', into 'code' vs 'data', 'client' vs 'server', 'desktop' vs 'net', and refuse to look at the whole, accepting contradictions (in the postmodernist vein) as required, inescapable, and necessary. But that approach means to accept defeat right from the beginning. If you have a mutal contradiction you have nothing at all. No common, complete data-description environment that can make statements - and formal guarantees - about the connection between Internet-distributed, computable data sets.

This language exists. And I don't yet know what it is. But I am sure that it is not quite reducible to any of the current mainstream paradigms, but is capable of expressing all of them. And it will be very, very simple.

Edit: I'm really echoing David Bohm's thoughts from Wholeness and the Implicate Order where he makes much the same point about language (in the context of the fragmentation of the scientific disciplines).

One of the fixes Bohm suggests is to use verbs rather than nouns to emphasise the process nature of spacetime. I think this is roughly analogous if not identical with the idea of composability of functions, as we see for example in operational transformation, where a document consists of transformations over the empty document, or in concatenative languages, where even data literals are functions over a stack (or a stream). All of these possess the property that we can merge two entities - objects or processes - and get a new one. This property is vitally important to 'remixing' and repurposing of data across the Internet, or for automatically translating from one data format to another without prior knowledge of its 'type'.

Object orientation as we have today fundamentally doesn't work here because it still keeps an artificial idea of object identity - whereas in the real universe identity is a very problematic thing - and because of this, objects are very brittle and aren't composable like functions are. But they could be made composable if they were turned into pure functions. That's basically my core idea: object-like functions, expressed as declarative statements of function application, which exist somehow in the computational ether and 'magically' update themselves to reflect as their sources change (where 'change' is really with respect to the observer; in reality, a single 'changing' object is a series of immutable objects seen in succession as the observer shifts in space or time; the same 'delta' mechanism produces both 'inheritance', if the shift is in space, and 'mutation', if the shift is in time).

This seems like a very easy concept to describe, but in practice most of our functional languages tend to make the assumption (for efficiency) that the environment of a function will never change once the function is created; they provide lookup access and binding (like lambda calculus), but no way for a function to truly operate upon its own environment (not to mutate, because that's a contradiction, but to provide a successor). But of course if you have a long chain of mutations or transformations, it gets increasingly inefficient over time, so you need such a built-in way of pruning that delta chain. A concatenative language such as Joy seems to almost solve this problem by making 'programs' first-class, runtime-modifiable lists. But it fails to achieve closure because it doesn't define a canonical mapping of environments to programs - 'define' is not itself a program.

Factor, as a practical implementation of Joy, takes the concatenative idea but takes the Lisp route of turning everything into an operation on a Big Shared State - the system image - which is precisely the Wrong Thing to do and won't scale to the Internet. Yes, you can run a server on it. But that's answering the wrong question; I want a network which doesn't even have the *concept* of 'server'.

Then we get into single vs multiple inheritance, and static vs dynamic scoping, which are contradictory ways of looking at this 'delta' mechanism and neither of which seem quite appropriate as a fundamental, low-level formal language feature.

This is what I'm trying to describe with my inappropriately-named 'mu functions' - the concept still needs work, I think, but it seems almost there. And yet...

Talkback
Leave a comment Permanent Link

Recent Entries \| Archive \| Friends \| User Info \| Previous 10 \| Top

Notes toward a Dataspace

Reinventing the Intertubes