I think perhaps another name for the idea I've been chasing for years is "minimalist semantic web".

I like the Semantic Web idea but I want a *tiny* concretization of it. General enough that it could be program or data text, small and fast enough that it could be direct in-memory data.

Minimalism is a key value, and it's why I, perhaps incomprehensibly to many, reject almost all programming languages as "too big".

I'm looking for not a machine but a grammar. Lambda calculus ain't quite it.

· · Web · 4 · 9 · 11

That is, lambda calculus *might* be it *if* it was augmented with a similar idea to Fexl's of a detectable unique "Void" value that a function can return if there is no mapping for the input argument.

But without a Fexl-style Void, or some alternative equivalent construction, I don't see how lambda calculus can quite encode generalised searchable *relations*.

This is why I talk about the semantics of Null a lot. I think it is vitally important yet often left undefined or forbidden.

Lisp, for example, is not based 100% on lambda calculus, but on Lambda Calculus + Lists (which themselves are Pairs + Nil) + Symbols + Quotes + Macros (and macros are often VERY semantically complicated) + custom readers/writers for everything else, like Vectors, that don't even fit into those categories.

That set of fundamental concepts seems Quite Large to me.


Something *like* RDF, but take a look at the number of serialization formats that RDF has. "Turtle" is probably the simplest, and it's just kind of weird to look at. And then you have to encode things like function calls or even lists into triples, and a list does *not* look pretty encodes as a bunch of triples.

@natecull I don't know if it's just me, but "Lambda Calculus" is a mush phrase to me. Which probably means I don't understand it.

And may be confusing it with Lambda Operators or Lambda Notation or something along those lines.

Could use clarifying.


" don't know if it's just me, but "Lambda Calculus" is a mush phrase to me"

I don't know how to respond to that. By Lambda Calculus I mean very precisely the thing that's named that and which every programmer calls by that name. It's not called "Lambda Operators" or "Lambda Notation".

@natecull Then I guess I need the ELI5 version, because it's impenetrable to me.


Lambda Calculus is the formal system that most of progtamming is based on. Or at least most of "functional programming", the part of programming that derives from Lisp in the 1950s.

There's another chunk of functional programming that's based on "combinatory logic", which is a different but equivalent system to Lambda Calculus, and then on top of that I think the Haskell people are really into Category Theory, which I don't understand at all.


Almost any time someone in programming talks about a "function" (rather than the older term of "procedure"), it means they're thinking about a Lambda Abstraction (the things that Lambda Calculus is based on). Sometimes they're called Closures (which is a lambda plus an "environment", a bunch of name to value mappings).

Most modern languages, even eg Javascript, have some form of lambda in them even if it's not their primary abstraction (like object or method).


Real oldschool Lambda Calculus only has two operations:

* define an anonymous function of one variable
* apply two functions, either a of which might be a variable or might be a newly-defined function you're defining right there.

and it makes (terrible inefficient) numbers out of awkwardly large function applications.

It was invented to solve some logical paradoxes circa 1930, which it failed at, then resurrected in the late 1950s to be part of the core of Lisp.

@natecull I think I'm mostly familiar with the term from Python's Lambda Functions.

(Not that I use or understand these either.)

@dredmorbius @natecull I've been a professional programmer for 14 years and I don't understand that definition, nor do I see how understanding it would have helped me during that time. We don't all have computer science degrees, or create our own languages. I don't think it was your intention to alienate us lesser code-monkeys or to trigger anyone's impostor syndrome, but that's the effect.

@natecull So, im not gunno fite this, but ... if I'm reading correctly, "Lambda Notation" and "Lambda Operators" (or "Lambda Functions") do originate from Lambda Calculus.

@natecull Lisp doesn't just add data, it also adds operations!
- data structures that can be modified (i.e. the whole family of `setf' operators). To model this in λ-calculus you need to pass around the whole heap of objects as an extra variable.
- object identity as a concept and as a test. With λ-calc, two terms with the same definition cannot be distinguished. In Lisp, `(cons nil nil) ≠ (cons nil nil)' because you can modify one without modifying the other.

- more complicated flow control. Things like `return-from' or `throw'/`catch' are still implementable in λ-calc, but you have to completely transform the source code, into continuation-passing style.


Good points on object identity and mutable data structures, yeah. There's rather a lot of non-lambda things even in Lisp. I think continuations were added in Scheme as a way of simulating the dynamic jumping-around-with-state that American AI systems, and European Prolog systems, were doing.

I guess I don't really like continuations as a fundamental feature because it seems like there's weird compilation magic needed to support them. Or at least *I* don't understand that part.

@natecull If you take the Sussman and Steele view, continuations are basically turning the call stack into a first-class citizen.

Suppose you have a fancy machine language where you can implement calls as follows:

stack <- (locals . stack);
locals <- ((return-address label1) (param1 arg1) (param2 arg2));
goto func;
(locals . stack) <- stack;

and return as:

goto (local-var return-address);

Continuations allow you to to the stack/locals manipulation without the gotos or vice versa.

@natecull Namely, `(call/cc f)' is just:

stack <- (locals . stack);
locals <- ((return-address label1) (continuation (label1 . stack)));
goto f;
(locals . stack) <- stack;

and invoking a continuation is just:

(return-address . stack) <- continuation;
goto return-address;

@natecull And if you inline `f' at that point, this reduces to pure stack manipulation:

stack <- (locals . stack);
locals <- ((continuation (label1 . stack)));
... code of f ...
(locals . stack) <- stack;

@natecull BTW, here is tail call optimization in this viewpoint:

// result <- (func arg1 arg2)
stack <- (locals . stack);
locals <- ((return-address label1) (param1 arg1) (param2 arg2));
goto func;
(locals . stack) <- stack;
// return result
goto (local-var return-address);

Delete unused `locals' and `stack':

// return (func arg1 arg2)
locals <- ((return-address (local-var return-address)) (param1 arg1) (param2 arg2));
goto func;

And now tail recursion doesn't need stack space.

@natecull You are correct that you only need to care about this if you want dynamic jumping-around-with-state. But it's not just AI / Prolog systems, this also includes `throw'/`catch' in Java and `return-from' in Lisp.


Right, I don't mean to say that exceptions are unimportant. Just that the "hairy control structure" was a big motivation for the creation of Scheme, as I understand it. I think around that time (mid 1970s) there was a huge amount of interest in the idea of software as lots of communicating processes, I guess with ARPANet happening, which idea also inspired both Smalltalk and Scheme, separately. And I guess Prolog's predicates acting like coroutines had a slightly similar thing.



(which may be an excessively Carl Hewitt-centric account, because he spammed a lot of Wikipedia with his views back in the 2010s)

@natecull So, clearly, not XML or HTML or JSON or any other modern Web formats.


You can answer that question with another one:

Would you choose, as a human, to program directly in XML, in HTML, or in JSON?

Lisp's S-Expressions come so very close to being a suitable universal syntax. But in practice no Lisp actually uses pure S-Expressions because it turns out that there are data types in most Lisps that can't actually be expressed as pure S-Expressions.


All of this came out of me asking over a decade ago:

"Okay so the Semantic Web people are pushing RDF everywhere, and RDF looks like a suitable universal data format. So, uh, if I can indeed express absolutely *everything computable* in this data model, then can I write a program directly in RDF?"

I think the answer to that today even for JSON-LD is still "sadly no".

@natecull Something like RDF, but with facts-about-facts, has been attractive to me for a little bit. I think it would be reasonably good at expressing human knowledge, but not necessarily completely universal.

@natecull Also where the predicates are also entities so you have facts about predicates.


Definitely predicates must be entities in their own right, yes. Everything needs to be the same kind of entity ultimately (but with the ability for meta-statements about entities to express any kind of type theory or schema, as required by higher levels).

One thing that *might* be required is that predicates be somehow certified to only have been created by other predicates. Like how objects can only be created by their class constructor. That's probably important but hard to do.


Another thing I want is for there to be a clear mapping between an assertion of a relationship-rule (as in Prolog) and that assertion or rule being able to be evaluated in place by term-rewriting (so more like how Kanren represents everything as a function).

I'd really like it if Kanren could be somehow completed to become a full language, not just a framework running inside a lower-level language.


One thought I have for possibly solving this is to have Kanren-style relations be functions (as they are in Kanren) that consume an environment.. but then return either a value or an environment or both. So that they could reduce to just "a function that returns a value" in the case of simple function-like relations.

Eg I'd like to query a table and get a table as output PLUS some "assumptions", if any, that that table requires for interpreting. Like variable substitutions.


That way, you could use the same mechanism to ask both "what is the set of values in slot X of object Y" (ie normal function-style lookup/evaluate) AND "what is the result-set of values in slot {UNKNOWN1} of object Y such that (foo Unknown1)" and out would come "bar, if (Unknown1 = baz), bar2 if (Unknown1 = baz2) .." etc.

A little weird, but it's the only way I can see so far to unify relational and functional models, and I'd like to have that.

@natecull I wasn't thinking explicitly about trying to unify code with data; more trying to create a mostly-universal knowledge-modelling system you could put arbitrary information into and have software be able to walk the graph and understand things based on very few hard-coded assumptions. But explicitly combining functional programming with the knowledge model would make low-assumptions semantics a lot easier.

@natecull The primary application I was thinking about was a wiki/encyclopedia thing, where you can simply type facts and have them be automatically digested by the system and dispensed back out as automatically-generated prose articles on any subject in the knowledge base.

@natecull So in the article on cats you might type "cats often chase mice" and then "mice are often chased by cats" could appear without human intervention in the article on mice because the system understands reflexivity.


"The primary application I was thinking about was a wiki/encyclopedia thing, where you can simply type facts and have them be automatically digested by the system and dispensed back out as automatically-generated prose articles on any subject in the knowledge base."

Yes! That's very much one of the things I want, for personal knowledge tracking.

MediaWiki's WikiData project does something similar but omg it seems very complicated and ad-hoc for what it does. Not desktop-friendly

@natecull Basically I want Wikipedia to be a frontend to a simpler Wikidata. But in an elegant and highly self-describing way so it actually provides meaningful increases in semantic value.

@natecull Any system along these lines absolutely needs to be self-defining to the greatest extent possible. The schema should be part of the data, to reduce the number of assumptions the software has to make; including computable expressions of some kind in the data could make that easier, but also raises all kinds of safety considerations.

@natecull I tend to prefer declarative solutions, but maybe that's just a reaction to the many badnesses of imperative programming. Though I do think declarative solutions are usually easier for programs to reason about.

@natecull I think I'm reaching the point where I almost understand what these posts mean after considerable thought and rereading.

@alexbuzzbee @natecull how close does graphql come to this idea? A lot of the core things you mention are there, it would seem.

@loke @alexbuzzbee

I guess I'm thinking about querying graphs (or tables that could be shaped like graphs or trees), so GraphQL is kind of an example of the sort of querying I'd like to do.

But I don't like how GraphQL does it. It seems to have far too much boilerplate.

Prolog or Kanren could do it easily enough I think, because it's easy to map a graph onto a bunch of predicates/assertions.

But what I want is to find the simplest possible form of a graph-type query with unknown values.

@loke @alexbuzzbee

Eg: There should be *one*, and only one, data structure for collection-shaped data.

If that structure is going to be a graph, THEN the query also must be a graph.

I don't think GraphQL queries themselves are expressed as graphs. So already there's a split into two levels of data representation going on.

@natecull @loke @alexbuzzbee GraphQL is just a spec. If the implementation sucks, you can write a new one.

@urusan @natecull @loke This isn't really an implementation problem. The issue is with the basic way GraphQL understands the structure of information. It's better than many but still not a great match for the ideas in this thread.

@urusan @loke @alexbuzzbee

I mean the spec is not sufficient, not the implementation. Because the spec encodes two different fundamental representations of data: graphs and "whatever it is that GraphQL itself is" which is not itself a graph.

I'm not sure why I'm having so much difficulty to get this point across, but it seems like I am.

@natecull @loke @alexbuzzbee Hmm, I do see the problem now. Looks like you'll need to build what you want from more fundamental pieces.

@loke @natecull GraphQL doesn't appear to have facts-about-facts or predicates-as-entities.

It seems to be a field-based data model, rather than the information being primarily encoded in the relationships between different things. Instead of, say, a person record containing a name field, I want an entity that has an is-a relationship with the idea of person-ness and a has-name relationship with some text, and the has-name relationship itself has an in-language relationship with, say, English.

@loke @natecull And then all of these relationships are predicated by separate entities, so "has-name" can have more facts about it, like "is-like has-non-unique-identifier."

Then you get clever and you have things like "has-name has-name 'Has name' in-language 'English'"

@alexbuzzbee @loke

Right. So you could express this several ways in Prolog, though Prolog's syntax sometimes gets in the way of clearest expression:

has-name(has-name, 'Has name', english)

Some of Prolog's 1970s nastiness hits us here, things like reserving capital letters to be variables and not having a good way to express chunks of its own source code (eg to do things like modules and package management in a logically-complete way).

@alexbuzzbee @loke

Another slightly weird thing about Prolog is that statements like the above one are about *names* of predicates, not the predicates themselves. Because it doesn't do Lisp's automatic symbol-lookup, and it doesn't have a built-in way of expressing environments or collections of name/value assignments as data. So everything just gets mashed into one flat namespace, which also isn't quite helpful. Like FORTRAN, it mostly works until you do too much recursion, then it doesn't.

@natecull @loke
The problem with

has-name(has-name, 'Has name', english)

is that it makes in-language special.

in-language(has-name(has-name, 'Has name'), english)

is closer to what I would want (even though I'm almost positive that's Not Prolog). Prolog doesn't have a great way to express it because you need to be able to refer to the same fact multiple times.

@alexbuzzbee @loke


That in-language predicate is okay Prolog, I think. If you wanted to say it in a more "functional" style, like:

in-language(English)(has-name, 'Has name')

then you'd need to go to HiLog syntax, which is only supported by some niche experimental post-Prologs (like XSB I think).

@natecull @loke I think Prolog is probably 70-80% of what you need. Adding a bunch more introspection, cleaning up syntax, making things more consistent would all be necessary at a minimum.

@natecull @loke And of course you need some kind of compact representation that's fast to actually do computation on.

@alexbuzzbee @loke

Yes, I think a Prolog variant of some kind is what I want. I kind of want predicates to also be functions, which is a bit like wanting a circle to be square. It's probably doable somehow though.

Probably in the MicroKanren way, which is that predicates are functions that consume an environment and return an environment including unevaluated functions for the remainder of the search. But that still needs two levels, 'predicates' vs 'raw functions'.

@alexbuzzbee @loke

Prolog managed to reduce that to just one level, the 'predicate', which was awesome BUT, it could only do that by making I/O a side effect.

I/O as a side effect doesn't really cut it these days, for a data construction and querying language.

Show newer
Sign in to participate in the conversation

Server run by the main developers of the project 🐘 It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!