kirshenb@hplabsz.HPL.HP.COM (Evan Kirshenbaum) (10/04/90)
In article <34487@cup.portal.com> pgl@cup.portal.com (Peter G Ludemann) writes: >> I would like to point out that there is no such thing as >Can we change the subject a bit? How about list structures >which can be as easily accessed from the end as from the front? >That, to me, is the big advantage of arrays; not the performance >improvement. Does anyone have a nice notation for getting the >last element of a list as opposed to the first element? > Once upon a time, I was playing with the design of a language based on prolog, and one of the extensions was exactly this. The notation I used was: [A,B,C] a sequence containing exactly A, B, and C [A,...] a sequence starting with A [A,..As] a sequence with head A and tail As [...,L] a sequence ending in L [..Ls,L] a sequence ending in L with everything up to it Ls [...,X,...] a sequence containing X [..Pre,..Mid,..Post] a sequence partitioned into Pre, Mid, and Post [...,X,...,Y,...] a sequence in which X occurs before Y I called ..X a splice (... was equivalent to .._), and it was an actual object in the sequence (although you couldn't get one outside of a sequence). Unifying a sequence that contained splices was possibly nondeterministic, but was reasonably easy to implement. Multiple solutions were obtained on backtracking. This allowed you to define append(Xs,Ys,[..Xs,..Ys]). member(X,[...,X,...]). last(L,[...,L]). If you unified [..ButLast,Last] with [..Pre,X,..Post] you got ButLast = Pre = Post = [], Last = X and ButLast = [..Pre,X,..As], Post = [..As,L] My system also contained a notion of anonymous variables, so sequences with anonymous splices were relatively cheap as well (no structures needed to be consed). Evan Kirshenbaum HP Laboratories 3500 Deer Creek Road, Building 26U Palo Alto, CA 94304 kirshenbaum@hplabs.hp.com (415)857-7572
duchier@cs.yale.edu (Denys Duchier) (10/04/90)
In article <6009@hplabsz.HPL.HP.COM> kirshenb@hplabsz.HPL.HP.COM (Evan Kirshenbaum) writes: > I called ..X a splice (... was equivalent to .._), and it was an > actual object in the sequence (although you couldn't get one outside > of a sequence). Unifying a sequence that contained splices was > possibly nondeterministic, but was reasonably easy to implement. > Multiple solutions were obtained on backtracking. This allowed you to > define > append(Xs,Ys,[..Xs,..Ys]). > member(X,[...,X,...]). > last(L,[...,L]). This is not exactly a novel idea. In PLANNER [Hewitt circa 67 -- I think] it was called a segment variable. The problem with segment variables is that unification not only may have several solutions, but occasionally infinitely many of them. Consider: [..X foo] to be unified with [foo ..Y] The set of unifiers for this example is: { X = Y = [] } { X = Y = [foo] } { X = Y = [foo foo] } { X = Y = [foo foo foo] } ... Nonetheless, segment variables are very convenient, and I still use them in my work. --Denys
kirshenb@hplabsz.HPL.HP.COM (Evan Kirshenbaum) (10/05/90)
>This is not exactly a novel idea. Never claimed it was new. The original poster asked for a notation. > The problem with segment >variables is that unification not only may have several solutions, but >occasionally infinitely many of them. Consider: > > [..X foo] to be unified with [foo ..Y] > >The set of unifiers for this example is: > > { X = Y = [] } > { X = Y = [foo] } > { X = Y = [foo foo] } > { X = Y = [foo foo foo] } > ... Actually, [..X, foo] unified with [foo, ..Y] would yield X = Y = [] and X = [foo, ..A], Y = [..A, foo] I don't remember the proof offhand, but if neither sequence is circular, there is always a finite number of unifiers. The problem occurs when you try to unify X:[a,..X] with [...,E,...] (infinitely many unifiers) or [...,L] (no unifiers, but it's hard to prove that). Evan Kirshenbaum HP Laboratories 3500 Deer Creek Road, Building 26U Palo Alto, CA 94304 kirshenbaum@hplabs.hp.com (415)857-7572
duchier@cs.yale.edu (Denys Duchier) (10/05/90)
In article <6015@hplabsz.HPL.HP.COM> kirshenb@hplabsz.HPL.HP.COM (Evan Kirshenbaum) writes: > > [..X foo] to be unified with [foo ..Y] > > > >The set of unifiers for this example is: > > > > { X = Y = [] } > > { X = Y = [foo] } > > { X = Y = [foo foo] } > > { X = Y = [foo foo foo] } > > ... > > Actually, [..X, foo] unified with [foo, ..Y] would yield > X = Y = [] > and > X = [foo, ..A], Y = [..A, foo] This can't be right! ..A must be constrained to be a sequence of foo's only. --Denys