Kevin Reid's blog

I'm having severe getting-around-to-actually-doing-the-work problems; I am far behind schedule. I think the problem is framing this as “work” rather than just another of the projects that I've found interesting and tinkered with. (I also blame Team Fortress 2 and Rosetta Code for providing attractive distractions...)

I've ported the “Ref” facility from E; this is necessary as CapTP is built on Ref semantics (promises, proxies, broken refs). I hope to very soon get the actual CapTP connection module up, then (as I wrote before) “define, document and implement a CapTP-over-HTTP protocol”.

(I previously mentioned implementing the Surgeon (serialization tool) but I then remembered that that's actually irrelevant to CapTP.)

Also: working without Internet access removes a whole lot of potential distractions — and one’s access to online documentation. Luckily I had some source code around which provided examples.

Common Lisp provides compile-file whose purposes is to convert a CL source file into an (implementation-defined) format which usually has precompiled code and is designed for faster loading into a lisp system.

compile-file takes the pathname of a textual lisp source file. But what if you want to compile some Lisp code that's not in a file already, perhaps because you translated/compiled it from some not-amenable-to-the-Lisp-reader input syntax, or because it contains unREADable literals? You can use a "universal Lisp file", which I know two ways to create (use whichever you find cleaner):

(cl:in-package :mypackage)
#.mypackage::*program*

or

(cl:in-package :mypackage)
(macrolet ((it () *program*))
  (it))

Suppose this is in "universal.lisp". Then to use it:

(defvar *program*)

(defun compile-to-file (form output-file)
  (let ((*program* form))
    (compile-file #p"universal.lisp"
                  :output-file output-file)))

This is just a minimal example; you'll also want to appropriately handle the return value from compile-file, provide an appropriate pathname to the universal file, etc. For example, here's an excerpt of the relevant code from E-on-CL, where I have used this technique to compile non-CL sources (emakers) into fasls:

(defparameter +the-asdf-system+ (asdf:find-system :e-on-cl))
(defvar *efasl-program*)
(defvar *efasl-result*)
...
(defun compile-e-to-file (expr output-file fqn-prefix opt-scope)
  ...
  (let* (...
         (*efasl-program*
           `(setf *efasl-result*
                  (lambda (...) ...))))
    (multiple-value-bind (truename warnings-p failure-p)
        (compile-file (merge-pathnames
                        #p"lisp/universal.lisp"
                        (asdf:component-pathname +the-asdf-system+))
                      :output-file output-file
                      :verbose nil
                      :print nil)
      (declare (ignore truename warnings-p))
      (assert (not failure-p) () "Compilation for ~A failed." output-file))))

(defun load-compiled-e (file env)
  (let ((*efasl-result* nil)
        ...)
    (load file :verbose nil :print nil)
    (funcall *efasl-result* env)))

Note that the pathname is computed relative to the ASDF system containing the universal file; also note the use of a variable *efasl-result* to simulate a "return value" from the compiled file, and the use of a lambda to provide a nonempty lexical environment, both of which are features not directly provided by the CL compiled file facility.

I have moved my web site to a new location: http://switchb.org/kpreid/.

I have done this because Apple has announced they are shutting down homepage.mac.com. While they offer a replacement, I do not want to have to change my URLs ever again, so I bought a domain name.

As well as moving the files I have updated my picture, changed some of the URL layout, updated some miscellaneous information, added an “About me” section for the front page, and fixed broken external links. Please let me know if I missed anything...

or even just critique it without respect to what's new.

I'm not making progress as fast as I would like; mostly due to assorted distractions rather than Doing The Work.

That said, I've gotten both ends of serialization implemented, at least for non-circular cases: the deJSONTreeKit and deSubgraphKit have both builder and recognizer implementations. (For a terminology introduction, see the serialization paper.)

Next up is the surgeon (high-level serialization interface), and designing uncallers suitable for JavaScript. I definitely need to increase my rate of progress to get this done on schedule.

I completed enough of the E-on-JavaScript improvements, and wrote the beginnings of one Data-E kit in Cajita, together with the Updoc tests for it, and a Makefile to cajole the JavaScript and "animate" the Updoc - convert it into a HTML page that actually runs the tests.

I also improved various readme files and pages, hopefully such that someone else can get it all installed on their own system starting from my project page without too much prior knowledge.

Near-term plan: Put aside the EoJS, and get the Data-E kits working; then the surgeon; then the CapTPConnection; then define, document and implement a CapTP-over-HTTP protocol.

I have begun the work on my GSoC project, Caja-CapTP.

I am currently working on improving E-on-JavaScript in order to be able to use its Updoc facility as the test framework for the Caja-CapTP code.

(If you don't know, Updoc is a test system which works by rerunning a recorded or made-up interactive session and confirming that the output is the same as before. The advantage of this system is that you can write test cases very simply as sequential code without gobs of assertFoo() for every particular attribute you think of testing.)

You can see my commits to EoJS at CIA.vc.

I am also learning more about exactly how Cajita works in areas such as library loading; the documentation in this area needs improvement, which I am going to work on myself and/or ask the Caja developers to clarify.

I get the feeling the textbook writers had a list of everyday objects which they randomly picked from to avoid saying “an object” in each exercise. The results are mostly just distracting or mildly amusing, but sometimes they're a bit too much:

— Halliday, Resnick, Walker, Fundamentals of Physics, 8th ed., page 215

(This is (finally, now that the semester is over and I have some free time, heh) one of those posts-related-to-schoolwork I mentioned before.)

Does the infinite series converge?

First, rewrite it to have n = 1 as , and discard the constant term since it does not affect convergence. The terms of this series are strictly less than those of ; therefore, there is some x such that

Let k be the upper bound of the sum as we take the limit: .

Since is a continuous function of p, for any k there is some p greater than 1 such that

Since is a p-series which converges, i.e. has a finite sum, and the series under consideration has a lesser sum by the above inequality, it converges.

Furthermore, the above may be generalized to a proof that any series whose terms are eventually less than those of the harmonic series converges.

---

However, it is invalid, and in fact diverges.

I managed to convince myself and my calculus teacher with it, but we realized it must be invalid after he presented a counterexample to the general case. I then realized which step was invalid.

---

You can't use the same k for all three series in the second inequality; each infinite sum has its own independent limit, and what this proof is doing is along the lines of ∞ - ∞ = 0 — assuming that “two infinities are the same size”. Or rather, the inequality itself (among partial sums) is true, but that fact has nothing to do with the properties of the true infinite series.

I would be mildly interested in a more formal description of this sort of failure: how the k inequality is true yet the independent series do not have the same relation.

---

Update: I have received many informative comments and replied to some; one pointed out an earlier mistake: is bogus because we can't compare the series until we know they converge.

I have been accepted to Google Summer of Code 2009!

I just recently found out that LJ is displaying ads on my journal-or-blog-whichever — I hadn't previously noticed as it doesn't when I'm logged in (which seems a bit deceptive). I had previously understood that with a basic account there would be no ads.

Your opinion on the matter? Have the ads bothered you? Is there actually a way to turn them off that I haven't noticed? Should I find other hosting for my blog?

(I expect most of my readers are actually via feeds and don't see them...)

While setting up my new laptop, I found this situation:

Up until now, I've pretty much had an Online Life and an Offline Life (not much of one), and not made any connections between them. It's time to change that.

I'm 25, and my current phase of the Standard Life Plan, in which I am running a bit late, is “college”. I am currently attending Mohawk Valley Community College in New York, and planning to transfer to a four-year school, with the goal of a bachelor's degree in computer science.

It's taken me far too long to get around to posting this. A short todo list of further items:

1. Update my web site.
2. Post about transfer.
3. Post about employment.

(One of the reasons for this post is to provide context for if I later post something related to schoolwork; another is getting around to the third item on this list.)

So. In JavaScript, an “object” is a set of “properties”: associations from strings to values. A method is just a property whose value is a function. Functions are called like “foo()”, properties are accessed like “bar.foo”, and methods are called like “bar.foo()”. Looks straightforward enough, right?

Now, how does a method access the state of its object? Without inheritance, you could just have the method functions of a given object all close over some variables; but JavaScript does have prototype inheritance, so the necessary access is provided by binding the variable “this”, in the method body, to the object the method was invoked on.

And when does this happen? When you use the method call syntax. bar.foo() is not the same as

var m = bar.foo;
m();

(It is the same as m.call(bar) — call is a method on function objects which invokes them with this bound — but that's beside the point.)

So, the syntax is non-compositional.

Not only that, but it is enthusiastically so: bar.foo() is the same as (bar.foo)() — the parentheses do not break up the method call construct!

Something I've wished for several times recently is a database-document program.

By "document" I mean that the database is a single file, which I can move, copy, etc., as opposed to living in a database server which has to stay up, uses accounts and ACLs, needs special backup procedures, and so on. It doesn't need to support humongous data sets — fits-in-memory and even linear searches are fine.

I am aware that people use spreadsheets for such purposes, but I would like to have named, typed, and homogeneous columns, easy sorting/filtering/querying, etc. which I assume I'm not going to find there. Relational would be nice too.

It must be GUI, and run on Mac OS X, but it doesn't have to be thoroughly native — I can stand the better sort of Java or perhaps even X11 app.

And finally, it should have a file format that either is obvious how to parse, or has a specification, or is supported by many other programs.

Does such a thing exist?

(If not, I might write it.)

some type *foo;
size_t count = ...;

...

foo = malloc(count * sizeof * foo);

This is not a complete tutorial; it is intended to collect the information that I needed to get started and didn't find obvious, particularly explaining the operations needed to compile a program, and the most basic of syntax, operators, and IO operations to use microcontroller-specific operations from C/avr-gcc/avr-libc. It does not cover designing circuits or choosing a programmer.

Needed software

Get avr-gcc, avr-binutils, avr-libc, and avrdude. If you're on Mac OS X, all three are available through MacPorts.

Setup

Create ~/.avrduderc to specify what kind of programmer you have and where it's connected. Mine looks like this:

  default_serial = "/dev/cu.KeySerial1";
  default_programmer = "stk500v1";

default_serial is the device for the serial port the programmer is attached to; default_programmer is the type of programmer; see the manual section on command line options for programmer type names. You can also specify these on the command line, but I figure since these are specific to your computer it's better to leave them unspecified in makefiles.

Writing code

• char is 8 bits and int is 16.
• The entry point is the normal int main(void); you don't have to do any special initialization.
• Special registers are exposed as variables — e.g. PORTD = 0 to do output.
• All normal variables take up scarce RAM — for constant data, use the facilities in <avr/pgmspace.h> to store it in program space.
• Basic IO: Each port has three registers. For some port x, DDRx specifies direction: a 1 bit makes the corresponding pin an output, whereas 0 makes it an input. Reading PINx takes input from the pins; writing PORTx sets output. If DDRx has a 1 bit, then PORTx controls internal pullups on those pins.
• For further info on the functions of the chip, read the datasheet for it; the translation into C is mostly straightforward.
• The avr-libc manual contains info on its avr-specific features.
• The avr-libc demo projects are informative and well-explained.

Compiling

  avr-gcc -mmcu=at90s8515 -Werror foo.c bar.c -o foo.elf

Substitute the part number of your target chip for at90s8515. I use -Werror to reduce the chances I'll run broken code on real hardware.

  avr-objcopy -O ihex foo.elf foo.hex

This step discards the metadata the .elf file contains, leaving just the code, suitable for programming.

Programming (downloading)

avrdude -p 8515 -U flash:w:foo.hex

Substitute the part number of your target chip for 8515.

I've seen it said that one should not use Wikipedia because at any given moment, a page might be wrong. But what's that error rate, versus the error rate of your own memory of miscellaneous not-significant-to-you-at-the-time information?

If the latter is ≥ the former, then even if Wikipedia is worthless for reliable information, it is still then useful to browse it randomly, or in a topic area of slight interest, because afterward you have increased your total knowledge while not increasing your error rate per fact.

“Language-independent” just means they invented a new language.

Apple's Sampler is a profiler based on the principle of periodically collecting the entire call stack of the executing threads, then summarizing these stacks to show what occurs frequently; primarily, as a tree, rooted at the bottom of the stack, where each node shows the number of times that call sequence was found on the stack.

SBCL's sb-sprof is a profiler which also collects call stacks, but its summary report is much less useful to me as it does not provide the per-branch counting; just top-of-stack frequencies and a caller/callee graph.

Therefore, I examined Sampler's file format and wrote code to generate it from sb-sprof's record.

The file is mixed text/binary, LF line endings. The grammar, as far as I've determined it, is:

  "@supersamplerV1.0" LF
  "@symboltableV1.1" LF
  (TAB int32<id> TAB int32<unknown> 
   TAB text<symbol> 
   TAB text<library-path> TAB text<library-path> LF)*
  "@end" LF
  (
    "@threadV1.0" TAB int16Hex<thread-id> LF
    (
      TAB int32<1> int32<0> int32<1> int32<count of stack-frame> (int32<stack-frame>)* LF
    )*
  )*
  "@end" LF

where by "int32" I mean a big-endian 32-bit (unsigned?) integer (i.e. four not-necessarily-ASCII bytes), and by "int16Hex" I mean a 16-bit integer in hexadecimal (i.e. four ASCII bytes).

"id" is an arbitrary identifier for this symbol. "unknown" is occasionally nonzero, but I don't know what it means. "symbol" is the name of a function/method found on the stack. "library-path" is the pathname to the object file it was loaded from (relative in the case of a standard framework, e.g. "Carbon.framework/HIToolbox.framework/HIToolbox").

"thread-id" is an identifier for the thread, which should occur as an "id" in the symbol table; the upper 16 bits evidently must be 0. Thread symbol table entries have a name and library path which is the string ("Thread_" int16<thread-id>); I have not confirmed whether this is necessary.

Each entry in a @thread block is one sampling of the whole stack of that thread. I do not know what the 1, 0, and 1 mean, but the fourth integer is the number of frames on the stack; immediately after are that many integers, each of which is an id from the symbol table.

Files generated from this structure are accepted by Sampler, but not always by Shark; I don't know why, and my attempt at tracking it down made it seem to depend on the size of the trace file.

Here is code to generate such a file from sb-sprof data; it should be loaded in the SB-SPROF package: ( SB-SPROF to Sampler )

This code generates a noninteractive Sampler-style tree report from SB-SPROF data. ( SB-SPROF tree report )

For those wondering about the problem I was trying to solve with a zipper: After all the advice and some consideration, I decided to go with “option #2”: a whole-tree processing step which adds equal labels to corresponding variable uses and bindings. I’ve implemented all of the analysis I described in the original post using this system.

(However, the code isn't quite finished (as I discovered some problems with a different aspect of it) so it's not in any public repository yet.)