[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: "Steve Dekorte" <address@hidden>, "Michael Vanier" <address@hidden>*Subject*: RE: s-exprs + prototypes*From*: "Anton van Straaten" <address@hidden>*Date*: Sat, 21 Jun 2003 19:48:55 -0400*Cc*: <address@hidden>*Importance*: Normal*In-reply-to*: <461D95AC-A3F3-11D7-B979-000393ACB27C@dekorte.com>*Sender*: address@hidden

Steve Dekorte wrote: > ST does lock you into a particular object system, but ST is a language, > not a paradigm. There are more general object models (such as > prototypes) that are more flexible than traditional class-based models. Prototypes may be more flexible than classes in some ways, but if that's the only model that a language provides, it still locks you into a particular object system. BTW, just to clarify terminology, the sense I was using 'paradigm' is that class-based object models are one paradigm, and prototype-based models are another. They might both be sub-paradigms of a more general object paradigm, but that's not really important here. > I see the OO paradigm of communication via messages between things > that encapsulate data as more general than lists. The two aren't directly comparable, since they don't fill corresponding roles. Encapsulation of data and/or behavior behind an interface of some kind is very important, but it's not specific to OO. In fact, it's important to lists too - see below. > Everything is an object, not everything is list. Surely you see the relativeness of statements like this. Lambda calculus says that everything is a function, for example - and follows through on that in a way that no computer language does. Everything could be a list if you wanted it to be, but neither Lisp nor Scheme claim this. Lists are simply a core data structure that are a good fit for recursive processing and for expressing a variety of more complex structures, including trees. It's useful to see lists in terms of their interface, rather than being distracted by what their implementation might happen to be. The traditional list interface is designed specifically for recursive processing: the core interface, derived from the interface to a pair, consists of only two operations, [first | car | head] and [rest | cdr | tail]. This interface is quite central to most functional languages - it's not specific to s-exp languages, and there are reasons for that. A good intro to an interface-based notion of lists - or actually the pairs from which lists are constructed - can be found in SICP section 2.1.3, "What is meant by data?": http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.3 A relevant quote: "We never actually said what a pair was, only that the language supplied procedures cons, car, and cdr for operating on pairs. But the only thing we need to know about these three operations is that if we glue two objects together using cons we can retrieve the objects using car and cdr. That is, the operations satisfy the condition that, for any objects x and y, if z is (cons x y) then (car z) is x and (cdr z) is y. Indeed, we mentioned that these three procedures are included as primitives in our language. However, any triple of procedures that satisfies the above condition can be used as the basis for implementing pairs. This point is illustrated strikingly by the fact that we could implement cons, car, and cdr without using any data structures at all but only using procedures." The code which SICP gives is only a step removed from a canonical definition of cons, car & cdr in the lambda calculus - since "using only procedures" pretty much defines lambda calculus. Here's a similar implementation in Javascript, using LC-style boolean values as selectors for the head and tail fields of a pair (as opposed to the 0 and 1 used in the SICP example): TRUE = function (x) { return function (y) { return x } }; FALSE = function (x) { return function (y) { return y } }; pair = function (x) { return function (y) { return function (z) { return z (x) (y) } } }; head = function (p) { return p (TRUE) }; tail = function (p) { return p (FALSE) }; // try it: p1 = pair (6) (9); head (p1); // 6 tail (p1); // 9 My point in presenting this is to show just how simple the pair "data structure" is. The above definition is self-contained, and can be transliterated into a mathematical definition. The definition relies on no language features other than function definition and invocation (top-level variable definition can be implemented via function parameters, although I haven't done that above). No conditional expressions are used, or data types or values other than functions. From an information-theoretic perspective, this is as simple as a compound structure gets, i.e. its definition is as short as it's possible for the definition of a compound structure to be. That makes sense - since a pair relates two values, what compound structure could be simpler? So, pairs, as one of the simplest possible compound data structures, are very suitable as a basis for other structures, including lists and trees, and are particularly suited to the kind of recursive processing that functional languages do. Given all this, a question that could be asked, which I do mainly rhetorically and for thought-provoking purposes, is why a language would implement something as simple as a pair in terms of a much more complex structure, such as an OO object or class? Isn't that a little like implementing a scooter by strapping a platform with handlebars to the top of an SUV? > 2. Lists aren't the only choice for the base of a uniform system. > > Why not use a tree as the unifying structure, for example? This would > seem more suitable since code is semantically a tree, not a list of > lists. ... > Well, a tree often has information at the node, while a list does not. Pairs support the kind of tree node you've just described directly: they have a head or car field to represent the node contents, and a tail or cdr field to represent the branches from that node. I think you'll find if you specify the tree structure you have in mind, and design it for easy and consistent recursive processing, you'll end up with something a lot like pairs & (nested) lists. And if you map that onto a representation for source code, you'll end up with something a lot like s-exps. Anton

**Follow-Ups**:**RE: s-exprs + prototypes***From:*Avi Bryant <avi@beta4.com>

**Re: s-exprs + prototypes***From:*Matt Hellige <matt@immute.net>

**Re: s-exprs + prototypes***From:*Steve Dekorte <steve@dekorte.com>

**Re: s-exprs + prototypes***From:*Michael Vanier <mvanier@cs.caltech.edu>

**References**:**Re: s-exprs + prototypes***From:*Steve Dekorte <steve@dekorte.com>

- Prev by Date:
**Re: s-exprs + prototypes** - Next by Date:
**Re: s-exprs + prototypes** - Previous by thread:
**Re: s-exprs + prototypes** - Next by thread:
**Re: s-exprs + prototypes** - Index(es):