---

I'm developing a programming language called Kernel. Kernel is a conservative, Scheme-like dialect of Lisp in which everything is a first-class object.

"But," you may ask, "aren't all objects first-class in Scheme?" (I'm glad you asked.) No, they aren't. Special-form combiners are second-class objects. To borrow a phrase from the original description of first- and second-class objects by Christopher Strachey, they have to appear in person under their own names. (There are also several other kinds of second-class objects in Scheme, but special-form combiners are the most commonplace.)

---

What is the theoretical significance of the kernel language? What is an example of a 2nd-class object in Scheme? What is the practical advantage of all objects being first class in Scheme? Does this sound like Smalltalk a bit?

Fexprs have had a bad reputation thanks to the paper "The Theory of Fexprs is Trivial." However--and this is what I've gleaned just by reading John Shutt's more propaganda-ish statements, not hard math--that paper was based on a particular formulation of fexprs, which doesn't apply to Kernel.

I think Kernel's main contribution is the idea of passing the calling environment in each fexpr call, so that it can evaluate its parameters in the correct environment and preserve lexical scope. On top of that, Kernel has some nuances to its scoping/assignment rules that oughta make it possible in most cases to determine if a variable is a constant, even if we're passing environments around to fexprs all over the place. Once we know something's a constant, we can constant-fold it and (hopefully!) turn fexpr calls that use 'eval into eval-free code, just as if the fexpr were a macro.

I say "oughta" and "hopefully" because I haven't mulled over the details enough myself to be confident.

---

"What is an example of a 2nd-class object in Scheme?"

Special-form combiners? :-p

What that means is things like "if" and "set!". You can't pass the "if" operator as a parameter to a function in Scheme, but in Kernel there are no exceptions like that. The "$if" variable holds an fexpr, and you can pass that fexpr to other places.

Another example used by the Kernel R-1RK is infinite lists. In Scheme, you can pass a cyclic list around in variables, but you can't actually use it as a list because standard list utilities like 'map, 'length, and 'apply don't work with it. Even if you wrote a library that did handle infinite lists, other peoples' libraries would still lag behind. (I'm not really convinced that this makes infinite lists second-class in Scheme. IMO, it just makes them less useful than finite lists.)

Another example is register use. Do you manually pass machine registers to Scheme procedures so they know which ones they're allowed to clobber? No? Well, you don't do it in Kernel either. :)

---

"What is the practical advantage of all objects being first class in Scheme? Does this sound like Smalltalk a bit?"

I don't see an inherent advantage, so I'm probably the wrong person to ask, for Kernel's sake. :-p To me, "first-class object" is redundant, just emphasis to distinguish objects from other things that you might think are objects but aren't.

Given a choice between two languages, where the only practical difference is that one language doesn't let you do as much with certain values (objects), the other language has a clear practical advantage. But sometimes "practical difference" depends on your point of view. To another person, given the same pair of languages, they might say the only practical difference is that one language has features they don't want or need, that actually make it harder for the language and its community to evolve in the way they prefer.

I've been working in the same language for almost 30 years and we seem to have much less/lofty discussions.

I don't see the purpose of 'best. I don't see a bigger purpose in most of Arc. If what Arc gives me isn't what I need, I reinvent it.

(In fact, I think if we try to keep working on the same language, rather than tearing it down and reinventing it, we're worrying about at least some kind of "support" and stifling our development. But too much tearing down can be destructive too, of course. :-p I appreciate that you're applying a scientific-ish mindset to this.)

There are a few ways to cut through this Arc ennui:

- If Arc gives me tools I can use to reinvent things, those tools are extra-relevant, since even if I don't like them I'll use them on my way to replacing them. This is not something 'best does for me.

- Sometimes we may want everyone in the language community to use the same variant of something, so that the tools we build around that thing can work together. Are we trying to optimize 'best in the compiler/runtime? Nope. Do people often extend 'best with extra capabilities? Nope. Even if these things were true, are we even having an issue with people reinventing 'best all the time? Nope, I don't think so.

For example, in Clojure, I can just build my project by excluding the function in question and replace it with my version. Anyone else that wants to use Clojure doesn't need to worry about another persons great idea.

; example

  (ns a-project.core
    (:refer-clojure :exclude (best))
    (:gen-class))
  
  (defn best []
    ...)

  (ns your-project.core
    (:refer-clojure :exclude (best))
    (:use [a-project :only (best)])
    (:gen-class))
   
   (defn do-my-stuff []
    (best ....))

  (def reduce (func xs)
    (whenlet (x . xs) xs
      (foldl func x xs)))

Alternatively we could have this...

  (def reduce (func xs)
    (iflet (x . xs) xs
      (foldl func x xs)
      (func)))

---

Hi engineers,

http://www.infoq.com/presentations/Simple-Made-Easy

I found this talk by Rich Hickey pretty... well, wholesome. He does a good job of talking about design issues that I think would strike close to home for many of us at FunMobility, regardless of which project we're working on. ^_^ Watch it at your own leisure; I won't mind if you skip it. In fact, I don't want to distract you from your work. XD

_Summary_: The easiest system to build is often completely different from the simplest system to understand. This is because many of our tools tend to drive us toward complexity, either by making it easier for us to build it, or by making it easier for us to recover if something goes wrong. The tools are useful, but they're not a substitute for a well-conceived design. If we separate parts of the program so that they don't depend on each other, we can understand them well in isolation, and if we also make them similar to each other, we can understand them in groups. He goes into several examples that he hopes will illustrate how one might systematically apply this philosophy to individual cases that come up in practice.

_For some context, Rich Hickey is the designer of Clojure_, a JVM language whose goal in life is to be the basis for very modular JVM programs. He heavily favors functional programming and disfavors type systems, which makes him like lisp variants more than other languages. But in this talk, I think he still manages to talk about the underlying issues he cares about without straying too far into these particular details. This is probably because he's not recommending we use a particular tool, like Clojure. He's examining ways (well, one big vague way) to improve programs regardless of what tools we use for them.

http://www.reddit.com/r/programming/comments/lirke/simple_ma...

If two parts of the program observe the system at the same time but see different states, that's called inconsistency. Consistency is difficult to achieve in a distributed program, thanks to the fact that "observation" isn't necessarily instantaneous or reliable. Per the CAP theorem (http://en.wikipedia.org/wiki/CAP_theorem), to achieve full consistency in a distributed program you have to sacrifice availability or partition tolerance. These three properties are inherently complected.

Things that are consistent are simpler than things that are not.

I was more specifically referring to the part at 31:17 where he had Inconsistency vs. Consistency on the slide and he explained the complexity as "taking a set of things that stand apart and trying to think of them all at the same time." He finished that line of thought with "And anybody who's tried to use a system that's eventually consistent knows that."

Because of the variants? The only mention of fold I found was this one:

Rich Hickey (at 30:33): "Imperative loops--fold, even, which seems kinda higher-level? Still has some implications that tie two things together... whereas set functions are simple."

I thought he was referring to the way the calls to the folded function are all lined up in a dependency chain, just like they'd be lined up if you were using an iterative loop.

  (state before the iteration, input to this iteration)
    -> state after the iteration

  (def foldl (first rest func)
    (ret result first
      (each elem rest
        (zap func result elem))))

With "set functions," you can determine certain properties about the result if you know some subsets' results:

- The result of (some odd (join '(17) foo)) is t, because (some odd '(17)) is t.

- The result of (keep odd (join '(17) foo)) has at least the element 17 in it, because (keep odd '(17)) has that element in it.

Rich Hickey's main point is that these "simple to reason about" properties help humans. But they also mean that if we know enough about these function calls statically (which we never do, in Arc), we might be able to turn them into constants without knowing the value of 'foo, or at least we might be able to parallelize them. These set functions may be implemented as special cases of fold, but fold doesn't have the same reasoning potential in the general case.

Look around minute 40. He says they complect what to compute and how to compute it, which I took to mean the need to specify foldl/foldr.

"Loops and fold! Loops are pretty obviously complecting what you're doing and how to do it. Fold is a little bit more subtle, 'cause it seems like this nice 'somebody else is taking care of it,' but it does have this implication about the order of things. This left-to-right bit."

I can see how you'd get that. I think our interpretations are related. As far as how they're related goes...

The underlying issue may be that introducing non-commutativity makes an operation more cumbersome when used with sets, and introducing non-associativity makes it even worse.

- Commutative and associative: If you apply '* or 'max pairwise to a set, you can only get one result. (It's possible to implement 'some this way, and a 'keep that returns an unordered bag.)

- Associative: If you apply 'compose or 'join pairwise to a set, you can get many results, but you can choose between them by putting the items in a list. (It's possible to implement 'keep this way.)

- Commutative: If you apply XOR pairwise to a set, you can get many results, but you can choose between them by placing the items on the leaves of a rooted binary tree.

- Neither: If you apply 'cons pairwise to a set, you can get many results, but you can choose between them by placing them on the leaves of a rooted binary tree with a distinction between left children and right children.

  arc> (isnt 'zip (isnt 'nada 'nil))
  t
  arc> (isnt (isnt 'zip 'nada) 'nil)
  nil

Here's another:

  arc> (is 'zip (is 'nada 'nil))
  nil
  arc> (is (is 'zip 'nada) 'nil)
  t

If anyone called 'best on an infinite list, I'd expect it to diverge regardless of how it was implemented. You never know if something's the maximal/minimal element unless you've checked all the others.

(If 'best operated on heaps or something, then you might be able to say "this potentially infinite substructure has no better candidates" because the heap structure makes guarantees like that.)

Anyway, #2 is still irrelevant because it's trivial to fix:

   (def best (f seq)
     (reduce (fn (a x)
  -            (if (f a x) a x))
  +            (if (f x a) x a))
             seq))

Here's a fix for #1 as well, along with a return to the original variable names:

   (def best (f seq)
     (when seq
       (reduce (fn (wins elt)
                 (if (f elt wins) elt wins))
               seq)))

This is something I cared about when working on Penknife that I now realize I don't actually use. (In fact, I don't use 'rotate or 'swap at all; it only comes up in 'zap.) My current way of thinking is that I wouldn't bother to fix it. I'd put a note in the documentation instead, or else detect unsupported usage and raise an error. And then I guess I'd make sure to apologize for that caveat every time I talked about the utility. :-p

If you want to fix it, I've found it's pretty elegant to have a (place ...) form that gives you a getter and a setter.

  (mac rotate args
    `(fn-rotate ,@(map [do `(place ,_)] args)))

Indeed:

  mac shift $args ; multiply-evals to maintain places
    `(= ,@(zip-flat $args cdr.$args))

  ; infinite nil generator
  = nils '(nil)   cdr.nils nils

  mac wipe places
    `(= ,@(zip-flat places nils))