Plan to throw one away
garethrees.org
Plan to throw one away
1–10 of 88 posts
Re: Plan to throw one away
#2This makes me want to write a JS interpreter... Sweet read!
Re: Plan to throw one away
#3Cool read, however, I feel the need to point out that 20 years ago, javascript in the server wasn't "too soon", it already existed.
In 1995 Netscape had the Netscape Enterprise Server[0] that ran javascript for server-side scripting. Actually, the two books I used, back in the day, to learn Javascript was the client- and the server-side javascript guides published by Netscape.
[0] https://en.wikipedia.org/wiki/Netscape_Enterprise_Server
Re: Plan to throw one away
#4Are Lex and Yacc still the state of the art 20 years later?
Re: Plan to throw one away
#5Are Lex and Yacc still the state of the art 20 years later?
I'm not sure how they've aged (I've only really used ANTLR) but I think this one of those situations where 95% of the importance is using the right kind of tool for the job, even if the tool itself is a little rusty.
Re: Plan to throw one away
#6> The failure to store a represention of the parsed code was disastrous because it meant that in order to evaluate an expression or statement for a second time, the engine had to parse it a second time.
Ha! They must have learned how to write an interpreter from Herbert Schildt:
http://www.drdobbs.com/cpp/building-your-own-c-interpreter/1... [1989]
In this piece of amusement, the Little C program is a giant null-terminated string, and the "instruction pointer" is of type char * . You get the picture.
> When I did come to write a garbage collector I used the mark-and-sweep algorithm. But something puzzled me, and I couldn’t find an answer in any of the textbooks I looked at: how was I supposed to schedule the collections? In a classic description of a garbage collector, you wait until memory runs out and then you collect the world. But this leads to bad behaviour on modern systems, because of swapping, and because other processes need memory too. You need to schedule collections well before memory is full. But when exactly? I still don’t know of a comprehensive solution to this problem.
In a nutshell, you let your run-time pretend that it's running in a small machine, until it is too close to huffing and puffing too hard and then you say "hey I lied, you're actually in a bigger machine: have some breathing room". This rubbery constraint keeps it behaving reasonably nicely, rather than "Wee, I have 4GB of free RAM to stomp over with strings and cons cells before ever calling GC!"
What you have to do is pick some heap size (that is typically substantially smaller than the amount of RAM). You let the GC whack against this artificial threshold, and if that gets too excessive, according to some measure, you increase it. E.g. if after a full GC you have less than some fudge threshold free, call the OS for more memory to integrate into the object heap.
The threshold is calculated in some way that the image doesn't have to execute numerous frequent GC's before it triggers the request for more space (it doesn't have to whack too hard and wastefully against the artificial limit).
Also, ephemeral GC will help, and ephemeral GC can have its own threshold against frequent ephemeral GC's. When not enough space is liberated by ephemeral, you schedule a full. Then if that doesn't liberate enough space, add more. Since ephemeral is fast (doesn't scan the full heap), you can work a bit closer to the heap limit (since you can suffer frequent ephemeral GC's better than frequent full GC's).
And, of course, the parameters controlling these behaviors are exposed in some way so users can tweak them. Command line arguments, env vars, local config file, system config file, run time global variable/API, ...
Re: Plan to throw one away
#7Are Lex and Yacc still the state of the art 20 years later?
I'm not sure how they've aged (I've only really used ANTLR) but I think this one of those situations where 95% of the importance is using the right kind of tool for the job, even if the tool itself is a little rusty.
The only thing that lets old tools get rusty is a lack of maintenance or improper storage. Software does not need to suffer from either and plenty of 'old' tools are still in maintenance. Kernels, compilers, file-systems and network stacks originally written decades ago are still in common use today. Flex and Bison are still being maintained and still have major releases. Whether they are still 'state of the art' is another question entirely but they're definitely being used and they are more than ok for quite a few jobs.
Re: Plan to throw one away
#8[deleted]
Re: Plan to throw one away
#9Are Lex and Yacc still the state of the art 20 years later?
Be prepared to just use the generated tables and forget the generated code:
The generated code is not so great if you have an event driven environment: I mean I want to push 50 bytes into the compiler, instead of having it request the next input character. This means it's not so great for a repl, unless some other pre-parser gives complete translation units to lex/yacc.
I think Yacc has a pretty primitive conflict resolution strategy: (pick shift unless otherwise indicated by precedence declarations). If code could resolve the conflict then you could handle a lot of newer syntax: for example, in "a-b" vs. "a -b", you could use the whitespace to distinguish between prefix (reduce) or infix (shift).
It would be nice (I know someone who has done this..) if there was an option to degenerate into using backtracking to resolve conflicts. It means try all possibilities (split the stack at each conflict) and keep only those results which produce an error free full parse. If there is more than one full result, only then do you have a real conflict.
I'm not sure if other parser generators are any better, but there are improvements which could be made.
Re: Plan to throw one away
#10Are Lex and Yacc still the state of the art 20 years later?
The freeware versions have improved a bit.
For exmaple, Both Bison and Berkeley Yacc (the new one maintained by T. E. Dickey) support reentrant parsing, which works hand-in-glove with likewise support in GNU Flex.
A parser that whacks around global variables (like parser generated by classic Yacc) is going to be a nonstarter in any modern language which gives programs run-time and compile-time access to the parser (code can execute while parsing and call yyparse). Not to mention if there are threads.
Bison has support for "push parsers" which are state machines called for each token, rather than functions that retain control until they parse an entire unit:
http://www.gnu.org/software/bison/manual/html_node/Push-Decl...