 |
status privacy contact |
|
|
Collaborative articulation of how abstraction and language is employed in the computational manifestation of numbers -- including analysis of the role of syntax, semantics, and meaning in the specification and use of software interfaces.
Recent Items Archives |
2007-11-10Miser Project: Repaving Kick-Off
Technorati Tags: Miser Project, site repaving, web presence, site infrastructure, Progressive Development I mentioned that there is an important need for housekeeping when I proposed Whither Peano. The site has become seriously out of step with regard to my latest approach to organization and construction. In addition, I need to make a systematic review of the site to correct any broken links that resulted from moving to a site with case-sensitive HTTP resource names. There must be some broken links as well as outdated material. I will be repaving. It won't have anything to do with the technical content, but it will show up as editorial changes to the content. Also, new technical content will be provided under the new regime. As repaving progresses, you will see evidence of it in the pages that you visit and especially if you happen to visit any of the construction structure of the site. The construction structure, as for all of my sites, has materials that account for the construction of the site itself. One project in that material will be the repaving project. There will be ways to see what the current stage is and also see where the changes are occurring. Although it is not critical to the technical content, these changes do support the accountability, dependability, and transparency that I want to provide in every aspect of the Miser Project. There will be occasional progress reports. This activity will not inhibit the posting of more technical articles on the themes of Numbering Peano. Sometimes I may appear to be A.W.O.L. when I am actually down in the sewers fixing the plumbing. The model for the updated organization is exhibited in the ODMdev: ActiveODMA Development Framework site's Construction Structure. I shall introduce a corresponding structure and organization for the Miser Project. What I call Smart Librarianship Rules apply to this change. The idea is that, when changing a system of organization (such as a catalog system), new material (accessions) are brought in under the new scheme, with older materials converted as it becomes important, possibly because of intended new usage or updates. Other changes are left to opportunistic treatment on a whenever-I-get-around-to-it basis. The first changes provide an on-ramp for the progressive introduction of further changes. For the Miser Project, there is urgent need to revise two major portions of the site on which most other material depends: the front porch consisting of those pages at the root of the http://miser-theory.info/ URL, and the Construction Material section having all of the bits used in carrying out the repaving. The first is the anchor for expanding changes to the construction structure and the content materials requiring the next-immediate attention. The second can be done piece-meal, but it must start out organized well enough that major disruptions in this material will not be coming later. In particular, a document for tracking the repaving itself is maintained in the Construction Material section, which also holds templates used on pages throughout the site. The first changes only deal with plumbing of the site. Another change, after the plumbing is refitted, is to provide Creative Commons license information on the pages of the site, in the same way as done for ODMdev. I might stick with the Attribution 2.5 for now just to have the changes be accomplished as quickly as possible. Because the changes are piece-meal, there is a problem about knowing the status of changes in different parts of the site. I also need to tell quickly where the repaving is completed. This is accomplished by leaving placeholders in various construction structure and construction work-item pages on the site. This is for my own sanity in noticing where there are opportunities to do a little repaving while I am working on a portion of the site, and to know that I don't have anything new to do in other places. My urgency about this is my pent-up urge to create a large number of new items for Miser Project. I need a way to avoid rework for the new material and to accomplish the repaving while there is not so much existing material to repair. Comments: Post a Comment 2007-11-07Hark! Is That an Idiom That I See Before Me?
I mentioned, in Miser Hacks II, that I fancy having abundant idiomatic usage of the Miser Ob structures and the constants that elicit particular operations of the standard Miser machine. This was my justification for having the primitive functions on obs be total in Miser Hacks I. This is a desirable quality of a machine-language organization and design: having instructions and fundamental data elements that can be used in a variety of ways that allow introduction of unexpected computational flexibility. And, as a practical development, oMiser is a synthetic computing machine. Even though it is constructed atop a conventional digital computer platform, attention to the opportunity for valuable idioms in the "machine language" for Miser matters from the standpoint of economical expression and efficiency of operation. Alan Perlis woke me up to idioms in programming in a conference-break conversation about work on APL idioms reported with one of his students. In this case, the language was APL, a language whose functional and operator characteristics provided an abundance (including map-reduce and others) of the kind we seek for Miser programming. A common idiom, one that programmers of the earlier Fortran systems knew by heart is on the lines of the statement
for computing the remainder of the division of I by J. I'm not going to explain this beyond pointing out that it once worked in Python and it still works in C and C++ except now we have the more-explicit
There are many programming idioms and they are to be treasured. As one can see, idioms can cost something in understandability. Yet when you know the idiom, you can spot it's usage immediately. One which I use regularly is
for the number of containers of size J that are required to hold I objects. In a way, programming-language idioms (including machine-language ones) are miniature implementation patterns for common situations. They presage the higher-level understanding of design patterns and they are a significant element in fluency of master programmers. An example of an idiom in oMiser is a common choice for representing small numbers. In Frugalese, the structure
where there are exactly n occurrences of individual ob-B (with n = 0 OK), is equivalent to the ob
And that ob (called ob-n for short), taken as a program, has the useful result that
where there are exactly n ob.b operations on the right. For those playing along at home, here are related characteristics that are part of why it works that way:
[Update 2007-11-29: I realized that the original brief sequence was a little too brief. I added some intermediate steps and adjusted the notation a little to at least make this coherent no matter how opaque it remains. I will provide a more-complete definition of ob.ap(f, x) in a forthcoming post, and the "Frugalese" notation being used will also be unfolded in later posts.] That is, the structure, ob-n is a program (or a sequence) of n ob.c's that has the effect of diminishing any ob (treated as a sequence) by removing the first n beads but no more than there are. Because all singletons have ob.b(x) = x, the technique is assured not to remove a terminal singleton (such as the ob-ARG individual at the end of some ob-m). That is,
where m ∸ n (read: m dot-minus n) is the diminish operation for non-negative natural numbers, resulting in max(0, m-n). [Note: dot-minus is a special Unicode character that may not render in your browser. See if it makes a difference to force the encoding to be understood as Unicode UTF-8.] This is part of a Miser idiom for small numbers and using them for counting down (and decapitating obs taken as sequences). So we will often see operations of the following sort:
and constructions that are tantamount to
When you consider how unnatural Miser is as even a machine language, it is no wonder that without little idioms that are easily reused (and Miser makes reuse amazingly easy) no programs of reasonable complexity could be created "by hand", as when creating the first programs for making writing the programs easier. Because oMiser is such a rudimentary applicative system, kept that way to see how we can first comprehend and then transcend its puristic sandbox with xMiser extensions, it is appropriate to end with another Perlis epigram (but not the last word on the subject): "Purely applicative languages are poorly applicable." [update 2007-11-29: I added some intermediate steps in the ob.ap process so that the evaluation of an ob-n application can be followed, although the unfamiliarity of the Frugalese notation may take some giving up of preconceptions about how to read these formulas. I have to reread them regularly to remind myself that I got it right, and that is what led to this "improvement." I also tweaked one of my sentences about the value of idioms, because I was here and I could.] Comments: Post a Comment 2007-11-05Whither Peano?
Technorati Tags: Miser Project, Numbering Peano, SeaFunc, Chris Diggins, Charles Petzold, Computer Science, Functional Programming, Computation Theory, Henry Baker, Chicken Scheme I have been very neglectful of Numbering Peano and the other elements of the Miser Project. Although I continue to make notes and follow other activities, I am much too silent and there is no velocity to the work. I also have other commitments, and those are challenging for me, even though they will train me when it comes time to lay down some code for a reference implementation or three of the Miser engine. I trust that the heavy lifting done there, on practical middleware and its deployment, will provide for a sound implementation of distributed-Miser operation. A RenaissanceAmid all of that, it is the Miser Project that arouses my passion, even if only for episodes connected to inspiration generated through interactions over the work of others. Charles Petzold's Annotated Turing announcement has been one of those inspiring situations. I intend to take that as a lever for re-launching activity on Miser and visibility on Numbering Peano. How will I balance that? Every day, the Miser Project will be my after-dinner dessert. It is my reward for completing my other commitments and re-energizing with attention to the Miser Project. I don't know if there will always be visible output, but my intention is that there will be some sort of post almost daily. Sometimes the posts aren't here but on a blog, such as Professor von Clueless, or on a site such as TROST or nfoWare. However it shows up, it will be building toward delivery of working Miser Project software. I notice that the sand runs out of my hour glass in the evening and I don't have the energy for some of my other commitments. Yet work on the Miser Project is, at this point, energizing. When it ceases to be inspiring and energizing I will re-assess how to maintain the momentum. There are parts that are difficult for me and I will need to be sharp and alert to work on them. That will probably require some fresh-faced morning-hour concentration. I will adapt. HousekeepingThere are some housekeeping chores that need to be done here. The bits of the site, and the blog too, have some dry rot and repairs are required. Some of this is related to a change of hosting services which, along with big improvements and great economy, introduce case-sensitive folder and resource (web-page) names. See also, 2007-11-10 Miser Project: Repaving Kick-Off. I need to be diligent about the housekeeping so that the site works with all of the refinements that I have learned and developed on sites that are more current. I want to get that done here while the amount of material is modest. Ultimately, the housekeeping will spill over to my Orcmid's Lair site, since my bibliographic compilations are there. Those have been neglected too, especially regarding materials on mathematical logic and programming systems, especially functional-programming. Some related housekeeping involves uploading photographs from events that are connected to the work here. Focus on ContentSpeaking of bit rot, the oMiser Sketch is in terrible shape and there are some serious errors in the content, ones that will derail a newcomer to the material. I have also refined my ideas about some parts, and that is being reflected in posts here. But it is time to merge all of my pent-up changes into a refactored, simplified sketch. That will also involve moving material to sections of the site where it can be given focused treatment and expanded supporting development. The idea is that the sketch will shrink to sketch-sized digestible material as an appropriate overview of material that is expanded elsewhere. I also want to start merging in references to related material, attention to other blogs and work such as that of Christopher Diggins on his cat language and his provision of interesting tools. It will also be interesting to get to the point where I can adapt Henry Baker's Cheney copy technique as it is incorporated in Chicken Scheme, returning me to techniques first explored in the original Heathkit H-8 demonstration of a prototypical Miser implementation almost 25 years ago. These are all pent-up affections that I need to channel along with many of the additional ideas that arise each time I expand on any single one of them. My job jar is already larger just because I finally set down an account of Miser Hacks II. But What About Numbering Peano?The last hints about the original inspiration for this blog were published in 2004:
There is more to be done here, especially without wending such a turtuous route. The idea is to make a very simple demonstration of how we are able to manifest abstractions in the behavior of computer programs, and how interface contracts support that. There is much to be learned from this simple example and its progressive development, and I won't resist the opportunity to resurrect it for very long. And Focus, How About Focus?This blog has been a catchall for abstraction- and computation-theoretical material in an odd combination. I don't mind that so much. There is room under the /astraendo marquee for other blogs beside Numbering Peano. I can imagine ones for /Turing, /Church (maybe), and /Gödel, as peer branches for Peano (here, /pn). There could even be a wiki or two. I'm not in a hurry about any of that. [update 2007-11-10: I added a link to the just-starting repaving activity in the Housekeeping discussion.] Comments: Post a Comment 2007-11-04Miser Hacks II: A Hole to Bind Them
Technorati Tags: orcmid, Andrew Appel, FLoC2006, Miser, Lisp, primitive operations, computational model, abstract data, array theory, axiomatic data structures, Trenchard More ContextIn Miser Hacks I: Floating Along the Ground (2006-08-21), I described how the Miser Ob data type has an equivalent structure to the fundamental data structure of Lisp. Lisp has a supply of atoms, the cons[x;y] pair operation, and the access functions car[z] and cdr[z]. In Lisp, the structure is completed by equal[x;y] and by atom[x], the "oracle" that informs us when some z is not a cons[x;y] and for which car[z] and cdr[z] are consequently undefined (and, in modern implementations, these are invalid operations). Lisp is defined with another oracular operation, eq[x;y] that for atoms, reports whether or not x and y are determined to be the same atom (or not). Lisp is computationally universal and profoundly interesting by virtue of a specified universal function by which all computable functions on these structures can be carried out using programs coded in such structures. Miser uses a similar approach, having a supply of individuals and corresponding functions ob.c(x, y), ob.a(z), and ob.b(z), with "=" for equality among obs. (There is a function ob.d(x, y) that determines equality/inequality within the computational model of the system. That is different than "=" since there are no obs that are recognized as true/false although there are idioms that tend to serve that purpose. That's another hack to be described, and it is an elegant one although I once muddied it by adding more hack than needed.) The Story So FarFor Miser Ob, the functions ob.a and ob.b are total. Whether or not ob z can be formed by some ob.c(x,y), ob.a(z) and ob.b(z) always determine obs. The Miser individual is the counterpart of the Lisp atom. It is the case that z is an individual if and only if ob.a(z) = z. Technically, the oracular power necessary to distinguish atoms has been moved entirely to "=" in Miser. This works because it is impossible, in Miser, that there be any z such that ob.c(z, x) = z, even when ob.a(z) = z. So we can define our equivalent of atom[z] as simply
If is-individual(z), it is also the case that z = ob.b(z), but z = ob.a(z) is sufficient to discriminate all individuals. In Miser Hacks I, I argued that having a structural distinction that discriminates atoms (i.e., individuals) entirely within the system is no more of a problem than having to condition certain statements and derivations depending on the presence of atoms. The guarding of deductions about Miser with is-individual conditions is no different than the need to be guarded with atom conditions in Lisp. Clinging to IdiomsI claim that having structural features for discrimination is advantageous in the ease with which useful idioms become available, idioms that don't require us to have to be cautious against performance of undefined or invalid operations. So I am clinging to this idiomatic power in Miser. There will be many manifestations of such idioms. An example of an idiomatic usage of Lisp is in the notion of list. In pure Lisp with no additional types (pretty much ditto for oMiser), there are only atoms and cons pairs. The fundamental data structure is a binary tree. (We ignore the prospect of cycles among cons-pairs, permitted in Lisp but impossible in Miser.) The representation of lists in Lisp is by transiting the cdr-path all the way until an atom (the NUL) is reached. At each point, starting with the whole list, and excluding the terminal atom, the list elements are the car-values at each cons-pair node along that cdr-taken path. That is so useful it is the default sense of the Lisp data structure in common usage. It is the typical representation of Lisp symbolic expressions (SEXPRs). Singletons and EnclosuresIn my preference for idiomatic cases and my yearning for additional representation opportunities, I take advantage of another structural distinction in defining the Miser Ob structure.
Individuals are singletons. In the diagram, the ob identified as x and found at both ob.a(z) and ob.a(ob.b(z)) is an individual and a singleton. This is a structural quality. The names chosen for these qualities has to do with an intended usage, but it is not necessitated by the structure. So we are fashioning idioms and metaphors already. Enclosures. The other kind of singleton is an enclosure. An enclosure satisfies the condition is-enclosure(z) = is-singleton(z) and not is-individual(z) where is-singleton(z) = (ob.b(z) = z) as expected. In the diagram, ob.b(z) is the enclosure, y, defined as ob.e(x). Now, just as for individuals, it is impossible for there to be an ob.c(x, y) such that Making enclosures with ob.e. We've managed to finesse where individuals come from (there being guaranteed to be at least one, designated ob-null), and here comes a completely-separate breed of ob. The Miser function ob.e(x) takes any ob and provides an enclosure of it. That is,
Idiomatically, an ob enclosure can be viewed as a container that wraps up an ob and distinguishes it as a singleton. One might choose to use it, in a Miser application, as a way to separate out enclosures for treatments like individuals rather than a continuation of some represented data structure, such as a tree or a list. Also, notice how one might consider to treat individuals as literals: singletons that enclose themselves (metaphorically of course: no individual is an enclosure). The use of enclosures for various practical purposes is not determined by the the Ob-structure theory. Enclosures as QuotationsThere is a place where enclosures (and individuals and ob.c constructions) are interpreted in a particular way. That is in the context of the standard oMiser universal function. That function, ob.ap(f, x), and its companion, ob.ev(f, x, p), treat enclosures as quotations. ob.e(x) is Miser's structural counterpart to the Lisp use of cons[QUOTE; x] in the standard Lisp universal function. To illustrate (but not explain) how this works for Miser,
Other features of oMiser and the Frugal processor (which provides a way to input and operate Miser programs) reinforce the enclosure-as-quotation interpretation. It is not the only interpretation, any more than a Lisp occurrence of the QUOTE atom is compelled to have anything to do with quotation in the context of the Lisp universal function. It is very handy to have a structural form of quotation that is completely separate from the use of atoms or individuals as markers. The use of enclosures in Miser accomplishes that. There will also be use of distinct individuals as special markers in ob.ev operation but those hacks come up later. Other markers are introduced in ad hoc conventions such as ones for ascribing types to enclosures. Those practices are unrelated to the definition of the universal oMiser function and the axiomatic theory of ob structures. Justifying the Hack
The main purpose of enclosures is to provide a structural mechanism that is easily used to control the depth to which various procedures intrude into the structure of an ob (ob.ap and ob.ev procedures being two examples). Enclosures are a simple, primitive device that supports this need for quotation by structural means along. There is precedent for a structural quotation feature. It matters in array theory where one wants sub-arrays or sub-something as elements of the arrays that contain them. In this respect, the Miser nomenclature around individuals and singletons honors the array-theory work of Trenchard More. Another precedent, and the one that I learned first, has to do with stratified strings: strings that can have strings as their individual "beads." This sort of string was defined for ALGOL 60, which introduced a notation for strings as elements (not sub-strings) of containing strings. Although the mechanism did not survive ALGOL 60 where it was seriously under-developed, it offered an existence case for an use of quotation to make string elements out of entire strings. Christopher Strachey developed a general-purpose macro processor (affectionately known as McG in one implementation) that relied upon stratified strings in a way quite similar to the use of enclosure in the Miser universal function. It was recognition of an omission that prevented universality over such strings that started me on the road that led to the current formulation of oMiser. Finally, it is useful in theory-focused settings to notice that introduction of enclosures does not in any way extend the cardinality of Ob, the set of all obs. That is, Ob with enclosures is just as denumerable as Ob without them. In this sense, enclosures do not add any inherent power to Miser, yet they simplify the expression of certain kinds of data representations and provide a simpler expression of a universal function. The way that this miniature feature facilitates expressiveness is an useful subject of study and analysis. Finally, as you can tell, I am infatuated with this feature and will not surrender it lightly. There are enclosures and they harmonize in the play of singletons and individuals and obs composed via ob.c. I like it that way. Gone Too Far Yet?What has me look at enclosure as a Miser hack is the degree to which their possibility complicates reasoning about ob structures, the concern that Andrew Appel raised over having ob.a and ob.b be total and defined on individuals. I don't think it complicates reasoning about the universal function much at all. It singles out quotation for the added attention I think it deserves, and however quotation is handled (such as in Lisp) it has to be singled out in the universal function. It is the means by which data is embedded in procedure embedded in data embedded in ... , and it demonstrates that quite simply. Since this is a fundamental matter in computing and its quasi-linguistic character, enclosures seem like an useful idea. The introduction of enclosures does add cases that must be accounted for in the low-level derivation of proofs about algorithms on obs and the correctness of representations of one kind or another. I haven't found that to be a problem at the low-level so far. I expect that, when one moves up to higher levels of abstraction, any complication due to enclosures becomes irrelevant and disappears. I am open to challenge as I move along. I would be surprised to have to abandon enclosures at some future time. But Wait, There's More!There is another hack that qualifies for my ugliest language-theory hack ever. I was proud of that one too until I found the counter-example that defeated the whole enterprise. To show that I am not totally unwilling to reconsider my pet features, I'll show you the hack I'm too embarrassed to keep around even though no substitute is particularly pleasant. Stay tuned ... I know it's been a long time since Miser Hack I and the inspiration that I took out of FLoC 2006 and the subsequent ICFP 2006 in Portland, Oregon. I have been working along silently and infrequently. Meanwhile, I on a different commitment unrelated to functional programming and applicative systems such as Miser. Some of that work is useful as preparation for a Miser implementation. I think I have found an appropriate way to break out of my silence and proceed in parallel with that other work. This break in my prolonged silence was inspired by Charles Petzold's announcement of his forthcoming book, The Annotated Turing. Without knowing anything about how that work will unfold, I feel kinship with the spirit of that effort and this is my offering from the chorus, uh ... peanut gallery, oh uh ... rooting section. [update 2007-11-12 There is a completely incorrect and misleading statement that I had to repair. I have stricken out the bogus statement and replaced it with an appropriate one around how no ob.c(x, y) can ever be a singleton.] Comments: Post a Comment Petzold Annotates Turing!
Technorati Tags: Charles Petzold, Alan Turing, Turing Machine, Universal Turing Machine, UTM, Church-Turing Thesis, Computation Theory, On Computable Numbers, orcmid Charles Petzold, author of highly-regarded books on programming for Microsoft Windows, is turning his attention to a work of love: creating an annotated treatment of Alan Turing's famous paper that set the foundation for a mathematical theory of computation and what it is possible for a computational mechanism to accomplish. Another highly-respected Petzold book, Code: The Hidden Language of Computer Hardware and Software, illustrates Petzold's devotion to promoting popular understanding of the principles behind computing. Delving into the fundamental theory established by Turing is a welcome sequel. At one point, Petzold lacked a publisher for this project. It is exciting to learn that Wiley is publishing the book, a detour from Petzold's consistent presence as a Microsoft Press author. Wiley Executive Editor Chris Webb has posted more information about the book on his blog. I'm as enthusiastic as Chris is that he is working with Petzold. The Miser Project comes at the principles of computation from the Church- side (or, more precisely, the John McCarthy side)of the Church-Turing thesis, because I find applicative systems more comprehensible and more easily shown to be applicable to conventional computing problems. But that is not to shun the Turing side of the picture and the contribution it made by giving computation an intense definiteness. In fact, it is always important to understand the mutual equivalence in terms of capabilities and other characteristics, the basis for speaking of a Church-Turing thesis in the first place. I look forward to Petzold's posting of further details along with tidbits on the by-ways that don't fit entirely into the coverage of the book but do inspire coverage on his blog.
I notice one gift that I've received from Petzold's newest book project. In my excitement over this development, I am committed to tidying up the Miser Project and Numbering Peano for more regular use and usefulness. Consider it my holiday-season present (along with the Windows Home Server that I am gifting myself here in Orcmid's Liar). I have some other commitments around middleware and ODMA. That means I must throw more coal under all of it and get those boilers steaming. I'm overdue. [update 2007-11-07T11:30 -0800: It appears that Blogger wooziness may have been related to this. It seems to have been fixed. Comments: I just posted a very brief description of the book on my blog: ckwebb.com Chris Webb Executive Editor John Wiley & Sons |
|
Singletons. Any ob, z, for which ob.b(z) = z is a singleton.
|
You are navigating the Miser Project |
template created 2004-05-31-22:34 -0700 (pdt)
by orcmid |