_tef

Related paper: Context threading

http://www.cs.toronto.edu/syslab/pubs/demkea_context.ps

The gist is you can structure your interpreter to improve branch prediction by keeping your vm & hardware in similar states.

Alternatively, the people who wax lyrical for 60 or so pages don't understand much either, and are compelled to pad out their document.

I remember seeing this a while ago, but I didn't pay much attention to it then, because punishing those who understand the problems with a lengthy verbose soliloquy isn't a good strategy for disseminating information.

:-)

The other problem is that something 60 pages long without any references or citations beyond an occasional casual link to wikipedia, smacks of reinventing the wheel. This would be why he can go for 60 pages without mentioning known terms like "Cybil Attack", or "Onion Routing".

This white paper smells more of bikeshedding - there was no code and right at the bottom of the document, you can see the caveat & apology "This white paper is in no way a complete protocol specification, far from it actually. Its main goal is rather to provide suggestions for solutions for several typical problems [...] which could hopefully work as some kind of reference point for any discussions that may be inspired by it."

I think my favourite part of the paper is where he handwaves PKI & Voting atop of a DHT to 'solve' lots of problems, without realising those are the genuinely hard problems people are still working on.

A close runner-up is in the slides he talks about "no central point of failure" and then explains his "Manual Override Command Support", which is a central point of abuse.

It is nice to see that someone is finally writing code for it, and I wish them luck working out all of the details left out in the paper, especially the organisation and management of addresses.

Because depression doesn't work that way. It isn't a general feeling of malaise, it's somewhat a lack of positive value on everything (ish).

It is a lack of momentum and a heavy inertia to stay miserable and avoid change. It becomes a sunk cost where it's almost impossible to change something small in your life, let alone something big or huge.

Your advice is naive, and tantamount to asking "Have you thought about not being depressed, I hear that could work". If it were as simple as thinking your way of depression, it wouldn't be such a problem.

The best advice I've ever encountered is to take care of the little things, like sleeping on time, remembering to eat every day, doing laundry and getting out of the house. These are often the first things to go and often the hardest to get back into the routine of doing. Once you can manage a day at a time, it's easier to start to try managing a week at a time.

Large changes won't matter if you can't take care of the smaller things in life that support you. Depression isn't one of those things you can snap out of, but one that you can gradually work yourself out of.

It's not fun or easy though.

"you don't have to be mad to work here but ...."

i've found smaller companies are much more tolerant & flexible with nutters (like me).

there seems to be more focus on results than politics. in larger places I've felt more pressure not to rock the boat, and produce the illusion of work, rather than actually delivering things on time. it doesn't seem to matter if you actually do anything as long as you look like you're not doing /nothing/.

and I don't mean a startup. even startups can grow into kafkaesque nightmares because it's the only way they've ever thought to run a company. really, you have to be in a small, autonomous group if you want to get away with not being that normal.

the moral is: being a startup in and of itself is no guarantee of tolerance for off kilter people, the people and culture within the company are important. there is a correlation between small companies/startups and tolerance, but it isn't causation.

one of two videos has a download link for me.

one uploaded in 2008 has a link but not the one from 2006

prolog is an interesting take on programming and by comparison, the style in which you write code is still significantly different to approaches in other languages.

sadly, most people when taught barely get past the 'parents and grandfathers' stage of programming.

why not something else? sure! erlang is actually pretty neat (otp is golden) and was originally implemented in prolog. why not learn a term re-writing language? what about snobol?

why prolog? well,

prolog for me has just been one of the most fun and interesting experiences I have had while programming. good prolog code is elegant in a way i've never seen in other languages and it's a big rush when you crack the puzzle of expressing your problem.

prolog was also used in ibm's watson and shipped as part of nt too :-)

Art of prolog makes an excellent first book, and the Craft complements it well with seasoned advice on elegant and efficient prolog.

As much as I agree with the title I find the contents of the article misleading.

It is almost as if prolog didn't make him a better programmer, given the idea that prolog 'returns values' or uses 'method calls' is 'not even wrong'.

prolog is actually impure logic language, and given the general lack of HOF i'd be reticent in labelling it functional.

it's a declarative language though, and the model you have 'here is a query, what solutions exist' is reasonably accurate

correct.

the pratt parser is just a way of implementing such a parser.

to be technical, it is a form of left-corner parsing

I agree with both of you - parsing isn't that mathematically demanding, and many papers are badly written.

This is why 'parsing techniques' is a joy. It explains with clarity what is often nightmarish to gleam from papers.

I would also like to say that the second edition is one of the finest cs-books I have.

There is an extended bibliography online for the second edition you've linked

ftp://ftp.cs.vu.nl/pub/dick/PTAPG_2nd_Edition/index.html

''' The printed book contains only the about 400 literature references that are referred to in the book itself, all of them with annotations. The complete list of literature references comprises about 1700 entries of which around 1100 are annotated. It can be found here. It consists of augmented versions of the Table of Contents, Chapter 18, the Authors' Index, and the Subject Index, each reflecting in its way the added entries. '''

If you want that sort of succinctness, it is already covered in many compiler text books.

This is to complement the existing literature with a broad and deep coverage of parsing in specific. There is most to parsing than just the front end of a compiler :-)

The second edition is far superior to the first in terms of coverage and depth.

edit: I read a draft copy and after getting sucked into it for a weekend I grabbed the hard copy.

I would like to say: awesome!

And yes most of my left recursion fetish would be covered by an operator precedence parser/left corner parser

ambiguity is useful for error recovery/error detection. also, some languages have ambiguity in their syntax (ML). I don't buy the 'optimization' argument. there is no reason we cannot have our cake and eat it - ambiguity and incremental parsing.

as for incremental parsing in ides, you may enjoy this thesis: http://jeff.over.bz/papers/2006/ms-thesis.pdf

finally;

I think parser-generators are unpopular because people would prefer to just write code, rather than compile something else to automatically generated code that is nigh on unreadable.

I think the popularity of regexes is due in part to the ease of which they can be embedded or used within the host language - either with syntactic sugar, or simply as a library.

combinators (parsec especially) hit a sweet spot of being able to write code that handles parsing succinctly, without having to conflate your build or auto-generate source.

i'd really prefer a library I can load and manipulate the grammar from, over yet another syntax and compiler in my tool chain.

(ps. (i'm saddened by the lack of left recursion support in gazelle))

notably: lpeg uses backtracking over packrat parsing

regular expressions (ala cs) are equiv to finite state machines. regular expressions can't count or match ()'s. ragel allows you to mix in code within the state machine, so it is actually far, far more powerful than a finite state machine.

in http, handling things like 'Content-Length: %d' and then reading a subsequent length is a little harder. as is handling transfer-chunked encoding. http is quite fiendish in places :-)

these are 'data dependent' - the parse stream contains information (i.e length) on the subsequent tokens - although some regexps have back references, these aren't common place in parsing tools/formalisms like LR,LL,LALR,CFG or PEGs.

my point is simply that a lot of the parsing drama of late has revolved around the simple task of parsing a language, rather than parsing network protocols.

there is a larger class of parsing problems that are still to be tackled.

It actually sounds more like cancellation parsing than frost's approach

(which iirc was more that left recursion is bounded by input length)

ragel is for writing state machines and automata in.

many parsers are written as automata, but that does mean it is in the same category as parsing tools such as LR, LL, GLR, PEG or CFG based approaches.

I can't remember off hand if it dealt with nullable terms or hidden left recursion properly either.

don't get me wrong: I like the earley parser :-) I just think the original paper has some omissions and the treatment of earley parsing in 'parsing techniques 2nd ed' is thorough and includes substantial references and explanations of further work.

it isn't cubic time either iirc

and while i'm here - the original earley paper is full of bugs.for a modern treatment you may find aycock & horspool's work on 'practical earley parsing' interesting, as well as the work on the Marpa Parser in perl.

to me: the earley parser and the packrat parser are similar in nature - they are both chart parsers. one is depth first, one is breadth first.

my question: can you engineer an earley parser that supports ordered choice and exploits this to avoid broadening the search too early -- ie can earley parsers support PEGs

I think it is possible and when i'm not drowning in my startup work i'd like to take a longer look at it.

fwiw my terrible attempts at an earley recognizer are here http://pastie.org/private/uezi1mxiur8dymdbh2scw

i've tried to use some ideas from the aycock and the aretz variants of the earley parser - avoiding lists of earley items at a character - instead storing the reductions/completions seperately from the scanning items, and using a driver rather than the predictor/completor loop (still need to add nullable support...)

It has several bad properties too. The algorithm they outline is exponential.

The challenge to make it run in cubic time will certainly turn it into a GLR or an Earley parser. (They can be formed from each other)

To me: it is just another way of looking at Dotted LR-Items used within earley parser. Earley parsers keep a state made up of grammar rules with a dot indicating where in the rule the parser is at.

(I wrote an earley recognizer that uses a derivative style interface to grammar rules.)

It has novelty, and some utility but it is not the holy grail you are looking for.

I have a couple of loosely connected points and links:

You want to buy 'Parsing Techniques 2nd Ed' -- this book is fantastic and will give you the understanding and clarity you seek. It is wonderfully comprehensive.

And schmitz' thesis is an excellent read on tools and techniques to deal with ambiguity http://www.lsv.ens-cachan.fr/~schmitz/papers

and the non-canonical parser that results is quite interesting too :-)

PEGs vs Boolean Grammars: I think adding negation and conjunction to a grammar is the same as positive and negative lookahead

PEGS + Ambiguity: Like other people, I solved this in my last top down parser by attaching both precedences and relations to terms

i.e E[50] :== E[< 50] + E[<= 50]

so you can force a left or right associative operator.

That said, although determinism is nice, I think ambiguous parses are inevitable once you have a sufficient level error handling within the parser

parsing theory is pretty developed and established but in reality many parsers are cobbled together top down parsers.

you can't use existing parse libraries to handle HTTP for example.

(That said, yakker is an approach with earley parsing to handle data dependent grammars)

it is driven by pure sine waves -- you can't have polyphony or voice spectra (easily...)

coffeescript is only a syntactic change and introduces no new semantics.

it will always win in terms of code generated

    print [1,2,3].unique()

I had a go on this.

It was awesome fun.

It happened on a whim - it was noticed the tesla coils were powered by audio, and we could easily get audio output from a kinect.