Replying in this msg to Ray and then Joerg:

R A Brown, On 20/04/2012 16:33:
> I assume the algorithm is that given on 19th April:
> "Abstracting away from problems of local ambiguity
> resolution, the sentence is parsed left-to-right one word at
> a time. With the current word, you either (i) take the top
> item off the stack and integrate it with the current word
> (and then try to repeat the process), or, if (i) is
> impossible, (ii) add the current word to the stack and read
> in a new current word."
>
> So, the first word can't be combined with the top item of
> the stack because the stack is empty, so I push it onto the
> stack.
> I move to the second word and, if I can integrate it with
> the word at the top of the stack, pop off that word and make
> the integration. However, two things are -not_ explained:
> - firstly, how do I know if the two words are to be
> integrated or not? Not a trivial question if you actually
> writing a program to implement this 'algorithm.'

That's part of the local ambiguity resolution  that is abstracted away from. To deal with local ambiguity  you have to allow for parallel parses, or backtracking, or whatever. My point is that there's evidence for the involvement of stacks in psycholinguistic parsing, not that stacks on their own are sufficient.

> - secondly, what happens to the integrated item? Does get
> pushed back onto the stack or is pushed onto a different
> stack which gradually builds up the sentence or is it placed
> in a parse tree, or what?

Pushed back onto the stack. Each item on the stack is a tree fragment.

> Presumably the algorithm is completed when the last word has
> been processed. But where is the result?

It's the Current Item when the last word has been processed and the stack is empty.
  
> Also, as Logan pointed out, if all we are doing is comparing
> an item with something we've just store and going no deeper
> than say, two levels, what's the point of using a stack.

I don't understand. Where is the comparing and the going no deeper than two levels?
  
>> Are we talking at cross-purposes?
>
> It is possible, I suppose. Maybe you could explain how this
> algorithm works with the the sentence I gave in the "natural
> language processing" thread yesterday:
>
> et nouus accenso fungitur igne focus
>
> et = and
> nou-us = new-NOM.SG.M
> accens-o = kindle\PRF.PTCP.PASS-ABL.SG.M
> fung-itur = perform-3SG.PRS.IND.DEPONENT
> ign-e = fire-ABL.SG(M)
> foc-us = hearth-NOM.SG.M
>
> Standard 'Leipzig glossing' one; the (M) is put in brackets
> after the gloss on _igne_ since -e in itself could be any
> gender. DEPONENT is not an abbreviation; it a passive
> termination used with an active meaning.
>
> "and a new hearth performs a kindled fire", i.e. "a new
> hearth has a fire lit on it"

This is a rather distracting choice, since it's syntactic analysis is rather controversial. I guess you picked this example because you want to assign it a structure with ineluctably crossing branches (which would then stymie the LIFO parse). But, as we've discussed in the past, I would be inclined to treat each of _nouus, accenso, igne, focus_ as dependents of _fungitur_. (I guess it's obvious to you how a LIFO parse would handle that, but if it's not then I can run through it.)

> [snip]
>>> Obviously - I assume - that is not what you mean. But,
>>> if there are no operators, how is the stack used or,
>>> more importantly, why use a stack at all?
>>
>> As you'll probably remember, Fith has a class of words
>> called (IIRC) 'stack operators',
>
> 'stack conjunctions' actually

Aha! Sorry for my share in having confused you, then!
  
> The postfix expression 1 2 3 x + 4 5 ÷ -
> is easily evaluated as 6.2 using a stack. It needs no more
> complicated structure than that.
>
> The more familiar 1 + 2 × 3 - 4 ÷ 5 evaluates also to 6.2 -
> IF one is familiar with the conventional order in which to
> evaluate operators. Many adults, however, would finish up
> with the result 1 (go figure).
>
> For the poor computer to evaluate 1 + 2 × 3 - 4 ÷ 5 it will
> have to use a parse tree. As I see it, reading each item
> simply from left to right and at each item, either pushing
> it onto the stack or popping the top of the stack off and
> combining it with the current item is not going to work (or
> at best evaluate to 1).
>
> Maybe you can show me differently.

When you get to 3 you've hit a local ambiguity; you don't know whether to merge it with 1+2× or to add it to the stack. If you go for the parallel-parse solution to local ambiguity, you'd create two parses, one for each option, and keep on multiplying the number of concurrent parses each time you hit a local ambiguity. Once you'd read in the final item, you'd find that all but one of the parses crash. I have no knowledge or opinions about how psycholinguistic parsing deals with local ambiguity.

It is perhaps significant that semiinnumerate adults apply the parse that yields 1: it's the parse that I'm predicting is the psychologically least taxing.
  
>> Incremental increases in psycholinguistic processing
>> difficulty demonstrably correlate with incremental
>> modifications of tree shape. As I explained in a
>> previous message, a prime theoretical candidate to
>> explain this phenomenon involves the hypothesized use of
>> a stack: given the premise that the probability of an
>> item fading from memory while it is on the stack is a
>> function of the time it is on the stack and of the number
>> of items on the stack, then the theory does an excellent
>> job of predicting the observed correlations between
>> processing difficulty and tree shape.
>
> I'm confused. Trees and stacks ain't the same animals.

The hearer hears a sequence of words and has to apply some sort of psycholinguistic processing (that probably involves stacks) to arrive at a structure in which words are integrated into a single tree.

> Also "the probability of an item fading from memory while it
> is on the stack is a function of the time it is on the stack
> and of the number of items on the stack" surely in itself
> suggests that the human mind does not use a stack structure.

?? When coupled with facts about the degree of psycholinguistic difficulty hearers have in parsing different sentences?

> The point is surely that Fithians simply do not have that
> problem; what is on that stack stays on that stack until
> such time as it is popped off.
>
> All mere experience as a computer scientist has led me to
> believe that language has to be handled by parse _trees_ or
> pattern matching or some mix of both - certainly by
> something rather more sophisticated than a stack!
>
> Jeffrey's experiment with Fith was to produce a language
> would could be handled solely by using a stack structure
> without the recourse to trees or anything more complicated.
> I know of no model that will let English be processed
> simply by using a stack any more than 1 + 2 × 3 - 4 ÷ 5 by
> using *only* a stack.

AFAIK nobody has claimed that English can be parsed using only a stack or that what makes Fith remarkable and worthy of interest is that its syntax is sufficiently simple for it to be parsable using only a stack. If anybody were to make either claim, I'd disagree with them. (For clarity's sake, I would not agree that the simplicity of Fith syntax makes it especially interesting; there are plenty of conlangs with comparably simple syntax. It's only the complexities arising from certain of the stack conjunctions that are interestingly weird.)
  
Jörg Rhiemeier, On 20/04/2012 16:37:
> Hallo conlangers!
>
> On Fri, 20 Apr 2012 12:55:09 +0100 And Rosta wrote:
>
>> R A Brown, On 20/04/2012 08:38:
>> [...]
>>>> Fith is weird because of its list operators, not because
>>>> of the LIFO ordering of the list.
>>>
>>> I disagree. What would be weird IMHO is employing a stack
>>> (LIFO) structure and have no operators. How would we use a
>>> the stack? Communicator A pushes each word/utterance onto a
>>> stack; when s/he has finished, listener B then pops them
>>> off? That would be silly: it would simply mean that speaker
>>> has to finish, then the listeners understands only when s/he
>>> has the items in reverse!!!
>>>
>>> Obviously - I assume - that is not what you mean. But, if
>>> there are no operators, how is the stack used or, more
>>> importantly, why use a stack at all?
>>
>> As you'll probably remember, Fith has a class of words called (IIRC)
>> 'stack operators', some of which do counternatural stuff like
>> reordering items on the stack. There's general agreement among us
>> all that it's certain of these stack operators that make Fith weird.
>
> They at least contribute to its weirdness.  Another "weird" thing,
> likewise banned from Shallow Fith, is lingering - pushing something
> onto the stack in order not to use it until much later.

Lingering per se is not weird; it's a function of the processing ability of speakers rather than of the grammar, and natlangs could be lingered in too. But what is unnatural is the variety of lingering that allows one sentence to be discretely embedded within another. Even in that case, though, if you take the view that langue generates the set of sentences, then the fact that some sentences do or don't happen to get embedded discretely within others is a matter of parole rather than langue, and speakers who choose to linger in Fith could equally well choose to linger in English.

Therefore if Miles Forster were excited about exploring whether he is capable of lingering, he needn't learn or recreate Fith; he could attempt it in any language.
  
>> These operators are distinct from the basic syntactic operation of
>> combining two items into one. The algorithm I gave in response to
>> George's question applies equally to English and to Fith, and it
>> uses this basic operation.
>>
>> Fith without its operators would still be parsed using this basic
>> operation of combination.
>
> I don't really understand what you mean.  I think that you have
> misunderstood some things.  Stacks aren't really useful in parsing
> languages; programming language parsers operate with syntax trees,
> not with stacks (except for those languages that have been *designed*
> for being parsed with stacks, such as Forth), and I am pretty certain
> that syntax trees are also used in parsing human languages with a
> computer (I don't know for sure because I never was involved with
> natural language processing).  The neurological patterns that build
> up in our brains when we understand language are probably much more
> like syntax trees than stacks!

The patterns that build up are like trees, but the process by which sequences of words are built into trees uses stacks. -- That is the claim, based on the evidence available to us.

> If stacks were used by human beings to parse languages, why, then,
> is there *not a single natlang* that allows for lingering and
> similar tricks?

Arguably all natlangs allow it. The reasons why it doesn't occur in usage would have to do with severe memory limitations  and also functional considerations.

>>>> The LIFO ordering is in fact human-language-like, and
>>>> FIFO (or anything else) would be much more
>>>> counternatural.
>>>
>>> I think that statement is quite controversial. Personally,
>>> i see nothing in human language processing which leads me to
>>> think that either LIFO or FILO is any more or less human
>>> like.
>>
>> (Is LIFO different from FILO?)
>
> It would be the same, but I think "FILO" is a typo for "FIFO".
>
>> I don't think the mere fact of your skepticism renders it
>> controversial, especially in the context of the meagre amount
>> of informed knowledge we have collectively adduced in our
>> discussions, all of what little evidence has been adduced
>> during which has been supplied by me.
>
> Sh, be careful.  Ray knows *a lot* about linguistics (though he,
> like me, is on the other side of the generativist/functionalist
> divide), and also quite a bit about computers - he has degrees
> in classical philology *and* computer science.  I have a hunch
> that both Ray and I (who has a degree in computer science as
> well) understand computers and parsing algorithms better than
> you do ;)

I have no doubt about that, or that there are many other areas of linguistics that one or both of you (and many others on the list too) know much more than me about. Even in those areas where you are an autodidact, I read your thoughts with interest and appreciation.

But the crux of this current discussion is a matter of psycholinguistics. I have already declared, quite sincerely and accurately, my lack of expertise in this area, but I have adduced the only evidence that has so far been adduced (namely, a feeble appeal to authority, and some quite compelling empirical evidence). I claim not that what I've said about psycholinguistic parsing is correct, but rather than on the basis of the evidence brought to the discussion so far, the provisional conclusion must be that what I've said is correct, since the evidence adduced all points in the same direction.

>> With regard to LIFO versus FIFO, if you have the auxiliary
>> assumption (as I do) that only the top/first item on the
>> processing list is accessible to the processor, then it
>> seems to me (tho admittedly it boggles my mind and maybe
>> I'm being obtuse) that FIFO ordering of the processing list
>> is incompatible with natural language word order -- it would
>> yield ineluctably tangling branches, no?
>
> I agree with you that FIFO lists (queues) are not useful in
> analyzing natural languages - but nor are stacks.  You need
> syntax trees.

Does your "analysing natural languages" include psycholinguistic parsing? If it doesn't then your point isn't relevant. If it does, then disagreeing with me -- however agreeable you find it to do so -- in the face of the available evidence is not a profitable contribution to the discussion.

>>> The mere fact that most of find using infix notation
>>> in mathematics more "natural" than either prefix or postfix
>>> seems a fair indicator to me that probably neither LIFO and
>>> nor FIFO are more akin than the other to the working of the
>>> human brain.
>>
>> It seems to (again, a possibly obtuse) me that head--dependent
>> ordering and the LIFO/FIFO ordering of the processing list
>> (with the auxiliary assumption about only the first item being
>> accessible) are orthogonal.
>
> Head/dependent ordering is a parameter that can be switched;
> both the head and the dependents are co-ordinate nodes in the
> syntax tree, as you as a Chomskyan linguist certainly know.
> It seems likely to me that stack-based languages with a word
> order different from Fith could be constructed as well.

Good.

BTW, it's odd to find myself called a Chomskyan for the second time in a week. The first time it happened I responded that I wasn't, but was nevertheless mildly flattered by the accusation. If neither me nor Chomsky would consider me to be a Chomskyan, are there nevertheless certain criteria that would lead you still to consider me a Chomskyan? For example, I would happily confess to being a Structuralist of some ilk: would you consider all Structuralists to be Chomskyans? (Was Saussure a proto-Chomskyan?)

>> [...]
>>> What seems to me misleading is to suggest a stack can with
>>> used without any operations being performed. What on earth
>>> is the point of using a stack unless for the trivial task of
>>> reversing things?
>>
>> Hopefully things are clearer now that I've pointed out the
>> distinction between Fith's processing list operators and basic
>> parsing operations. (I was talking about the former; you
>> thought I was talking about the latter, it seems.)
>
> Fith's way of parsing the language is utterly different from the
> human way, that's the point and nothing else.  You have been
> entertaining the notion that the human language centre used
> stacks to parse natural languages, while both Ray and I (and
> probably most others in this thread) doubt that.
>
> Even without the stack operators, Fith would not behave like a
> human language - lingering would still be possible *without
> limits*.  Lingering has *nothing* to do with _shen_, _du_ and
> their ilk - it is a consequence of the stack-based parsing
> method itself.

It's not only a consequence of the stack-based parsing method. The limits or limitlessness of lingering depends on the capacity and durability of working memory.

>>> Also I am baffled by "... its vulnerability to the
>>> limitations of short-term memory is in fact key evidence for
>>> its involvement in psycholinguistic parsing."
>>>
>>> Surely on reason for using a stack is that things can be
>>> stored lower in the stack which will eventually, during the
>>> stacks use, find itself as the top item and is popped off
>>> again. Long term retention of an item which eventually
>>> resurfaces would IMO be some evidence that a stack structure
>>> is being used.
>>
>> Incremental increases in psycholinguistic processing difficulty
>> demonstrably correlate with incremental modifications of tree
>> shape. As I explained in a previous message, a prime theoretical
>> candidate to explain this phenomenon involves the hypothesized
>> use of a stack: given the premise that the probability of an
>> item fading from memory while it is on the stack is a function
>> of the time it is on the stack and of the number of items on the
>> stack, then the theory does an excellent job of predicting the
>> observed correlations between processing difficulty and tree
>> shape.
>
> You mean, an imperfect implementation of a stack with a finite
> storage capacity, which drops the bottom element(s) when it
> overflows to make room for new elements on the top.

An implementation using really crap hardware/wetware. But -- relying only on introspection here and not on experimental results -- I don't think it's as simple as just losing the bottom item when the stack gets too full; I think the breakdown happens in less systematic ways.

--And.