HNHacker News
TopNewBestAskShowJobs

k4st

148 karma · joined February 20, 2007

Present: C++ Developer at Hex-Rays SA. Formerly: Staff Engineer at Trail of Bits. Personal website: http://www.petergoodman.me GitHub profile: https://github.com/pgoodman
submissionscomments
k4st··on Lytro cameras are ready for preorder.
I HATE when a website tries to prevent me from leaving with the back button.
k4st··on Mobile UI Patterns
Hrmm.. looks like some free AT&T advertising.
k4st··on Peter Norvig on a 45-year-old article about a checkers-playing program
Great article, with the exception that code indentation does not appear to have made it through the editing process.
k4st··on Lost skills: What today's coders don't know and why it matters
I think that it's useful to distinguish between code that one has an intimate knowledge of / intuitive sense of and code where one does not fully understand.

For example, I find printf-like debugging and using stack traces from Valgrind to be very useful for debugging my own code; however, at work, when I have no idea where the problem is, something like gdb or the debugger of Visual Studio really comes in handy.

k4st··on The Luna Programming Language
@tjholowaychuk: Check out context threading (http://www.cs.toronto.edu/syslab/pubs/demkea_context.ps) by Prof. Angela Demke Brown as an alternative to direct threading.
k4st··on Cellular Automaton Music Generator
http://earslap.com/projectslab/otomata/?q=06122n3x4j5d6o7t8q...

Very fun!

k4st··on Rdd.me – Readability Powered URL Shortening Service
For me the link redirects to a NYTimes login page. Maybe you are already logged into NYTimes, and NYTimes claimed their domain through Readability's service?
k4st··on List Comprehensions in C
I implemented a rather nice C++ pattern matching facility for productions of context-free grammars in my undergraduate thesis project (http://www.grailplus.org). It is able to do some really fancy stuff and I think that is one were using C++ then one could use some similar techniques for creating list comprehensions. Here's how I envision it working:

First, the variables used in the comprehension would be defined locally, with the right types.

Second, we would need an overloaded template function, named something like "constructor" to abstractly represent a constructor for some arbitrary object. Here is how the constructor function works: for N arguments, all taken by reference, it allocates an array of N void * pointers (or sufficiently large slot sizes + proper alignment to hold any pointer type), and returns a pointer to the first slot in that array as some member in an instantiated template, where one of the parameters of the template contains all the info of the types of the constructor parameters. It also initializes each slot of the array to be the address of the local variable passed in to the constructor function by reference. So, if the following is my setup:

   int foo;
   float bar;
   constructor<std::pair>(foo, bar)
returns an object of type Constructor<std::pair, Slot<Base<int>,float> >, where the object contains a pointer to the first slot in the array. This type and the array contain all the info we need to construct an std::pair<int,float>.

The comprehensions would likely require an new iteration mechanism. This was the case in my thesis project, as a cursor-based iterator, while being able to represent the iteration aspect of this, is unable to fully represent the pattern-matching/destructuring bind operations. The tricky part is to make it so that one can advance multiple loops in sequence.

When we know that we can enter the body of the inner loop that would normally represent the innermost loop in an imperative implementation of the same operation being performed by the comprehension then we can use the pointer table to bind values to local variables, and then use a compile-time created function from the Constructor type to yank out those values all at once, impose the proper types using a cast on the void * pointers, and then construct the thing we want to add into our final list.

k4st··on Ask HN: What are you working on?
I'm working on an open-source framework, and a series of command line tools built on top of the framework, for symbolically manipulating context-free grammars, non-deterministic pushdown automata, and non-deterministic finite automata. All of it is implemented in C++. I have done some neat things like implement CFG production pattern matching using an EDSL that lets me express foreach loops in C++. I'm currently looking for people interested in contributing / using the code.

The project page is http://www.grailplus.org.

k4st··on Parsing ought to be easier
Parser composability is trivial with Pratt parsers. One need only introduce the idea of denotation groups/categories, and allow one to specify a specific category along with a precedence. Add to this the ability to do ordered choice on denotations based on the first token(s) of the led/nud and you've got yourself a nice system :D
k4st··on Ultima Underworld bugs
Thank you, that brightened my morning up :D
k4st··on Regex Visualization: give it a regex and see the state diagram
This is nice for visualizing an NFA and the minimized DFA for asome regular expression (note: regular!!): http://osteele.com/tools/reanimator/. The aforementioned tool also lets you give input and highlights the current states of each FA.
k4st··on My Facebook Interview Experience
It depends on exactly what you're trying to optimize and what the requirements are. While it's not necessarily the best solution for a Facebook style problem (where you actually want to aggregate the results, where other concerns would be pagination of said results, permissions, etc.), an interesting algorithm to look at when you want to traverse a graph up to a certain depth looking for some specific "target" is iterative deepening. In basic terms, it is a depth-first search up to depth N inside a loop that increments N on each iteration.
k4st··on Yacc is dead
I can imagine one practical reason is that a lot of stuff (e.g. type information, variable bindings) goes top-down, but bottom-up parsers reduce rules in the opposite direction and so it takes extra effort to make the mental model of programming fit with the reduction strategy of bottom-up parsers.
k4st··on Yacc is dead
I haven't finished the paper yet, but this type of technique excites me as well. Recently, I did an assignment on the paper "memoization in top-down parsing" by Mark Johnson. Have you seen this paper, and do you think that there are any similarities between the derivatives of a CFG and continuations of parsing procedures (for variables and their related productions)?
k4st··on You asked for it, HN: Hipmunk adds Multi-City Searching and more
I wonder if they can get around that by knowing the information, but not explicitly displaying it. For example, if one does a search and Hipmunk knows that Southwest has a plane scheduled at that time then they can provide a link to the Southwest website and a suggestion that "Southwest might have a time that's good for you." with a little "[?]" box beside it explaining that Southwest prohibits Hipmunk from explicitly displaying their info.

Obviously, another way would be Hipmunk getting authorization to use Southwest's data from Southwest.

k4st··on Logicly - the digital logic simulator
Not related to post, but that is a really beautiful web application.
k4st··on Illegal prime
A more relevant example, as mentioned in a linked article, is that the binary data of images such as child pornography and state secrets are also numbers and as such may be considered illegal.
k4st··on Ruby Block Styling (Homoiconic/Reg Braithewaite)
You can do it in C:

    #include <stdio.h>
    int main(void) {
        int a, b, c;
        int d = (a = 1, b = 2, c = 3, a + b + c);
        int e = (({int f = 1; e = f;}), e += 1);
    
        printf("d is %d \n", d);
        printf("e is %d \n", e);
    
        return 0;
    }
Edit: I just realized how strange the line e = ... is. I wonder if it yields different results with different compilers.
k4st··on How the design of a BMW Motorcycle affects your App
My original macbookpro is still alive and well and withstood very heavy use. Granted, I needed to replace the battery a few times, originally because mine was within the serial # range of defective batteries, but each time those changes were covered by my warranty. The computer is now almost four years old.

I suspect that you can find someone with an anecdote describing a perfectly functioning mac and one that exploded. The same such anecdotes likely also exist for people running Thinkpads, Latitudes, et al.

k4st··on Rewriting PHP
The following is a comment I made on Reddit (http://www.reddit.com/r/programming/comments/7aiex/php_forke...) some time ago on the subject of PHP being forked:

As I tend to work with php a lot I often think about how to make PHP better and given that I like functional programming, more functional. Here are a few of the ideas I've thought up:

Putting a $ in front of a symbol, e.g. $var is equivalent to defining and requiring that variable to be within, and only within, the current lexical scope. Given that within PHP, if/for/while/switch statements don't create new lexical scopes, everything would still work as is. The benefit would be to say that $ is no longer required such that variables could now be accessed without $, as is the case with functions. A symbol without a $ would be one that goes to each parent scope and either looks for the existence of a symbol. This is consistent with how current PHP functions works because currently all PHP functions belong to the global namespace, ie: they all are part of the root scope. So, this establishes that variables don't need to be preceded by $, and that $ is an operator that says look at the local symbol table for variables.

The above model sets the stage for variables being passed down through child scopes and functions as well. That would all for proper closures that don't require parent scope variables to be used be explicitly defined. This also means that functions defined within functions (legal PHP) would not be put into the global namespace (this is inconsistent with previously versions of PHP).

Finally, most symbols will either be values (in the cases of scalars, arrays, etc), instances (in the case of class instances), references, resources (function resources, other resources), or a few other data types that PHP currently supports. So, the symbol 'substr' is a function resource to the substr() function and '$substr' is only defined within the root scope as the same function resource. The idea of function resources is consistent with how PHP 5.3 implements anonymous functions.

ex) If within the current scope one defines '$substr', then both 'substr' and '$substr' will point to that something else within the current scope and all subscopes.

ex) If '$substr' is not defined in the current scope and one redefines 'substr' in the current scope then the actual 'substr' reference is changed for all scopes after that.

</braindump>

k4st··on Parsers and Combinators
This is interesting to me. I recently wrote an interpreter for a parsing language (similar to the one in the article) in common lisp and also a recursive descent parser generator for an almost identical language (to my previous one).

I went back a few articles and found this: http://alexicalmistake.com/2008/06/scheme-parser-combinators..., to which I've concluded that I might be using combinators in my interpreted parsing language because every operator (such as 'repeat' or 'find-next') returns a function that performs the operations, but I am still a bit unclear.

If anyone is interested, I wrote a bit about them and gave an example of the parse tree created here: http://ioreader.com/2009/01/01/common-lisp-recursive-descent... As I am new to common lisp (reading ANSI CL, actually, although I've been playing with things not yet mentioned in the book!), the code leaves a lot to be desired.

Otherwise, very interesting article. These are the subjects that interest me most and approachable articles like these help me a lot.

k4st··on I haven’t given up on PHP — yet
Controller route prefixing seems suspicious. Do you include every controller at runtime and use php reflection with some regular expressions to parse all of their prefixes only to figure out what single route to use?
k4st··on Dropbox, why it rox and how I (and others) use it.
Every time I come across a neat paper online, I download a PDF of it and then put it up onto Dropbox so I don't lose it.
k4st··on PHP Design - Biggest Database Oversights
Yes! I'm copying and pasting some code from various areas.

Here is an old and slightly modified mysql result set iterator that fits the purposed of the newer code that makes this example nice: http://codepad.org/nmD4pDES

Here is a windowing iterator, it gives the person the ability to shift and pop elements from the inner iterator, thus narrowing the field that the iterator goes over: http://codepad.org/IsE5U7cw

We can now do the following... http://codepad.org/nP0EEKxT

k4st··on Is Canada becoming a digital ghetto?
I should have been specific to Canada's two bills, C-60 and C-61, which both attempted to ratify Canadian IP law to the WIPO treaties. The U.S. already ratified to those treaties, which got them the DMCA.

Clearly our cellular plans suck, but the U.S.'s intellectual property laws remain more restrictive than ours (for now).

k4st··on Is Canada becoming a digital ghetto?
Does that mean that the U.S. is already a digital ghetto?
k4st··on PHP Design - Biggest Database Oversights
As I commented on the blog, he fell into the trap of needlessly looping over sets of data.

1) Loop over MySQL result set in GetArray

2) Loop over array of results to format them in GetVideos

3) assumed loop over results to eventually display them to the user.

All three steps could be accomplished at the same time by simply using iterators.

k4st··on New honeycomb tire is 'bulletproof'
I remember seeing this on Reddit or Digg some time ago (maybe one or two years ago) and was hoping I would eventually hear something about it again.

The one deterrent I can see to adoption is that police might not like it. No longer would they be able to shoot someone's tires out or put spikes out on a road to slow them down.

k4st··on 10 Advanced PHP Tips To Improve Your Programming
For some reason I thought that the ereg_* functions were deprecated; that's not the case. I was wrong in saying they should never be used; however, it remains the case that preg_* is usually faster.
← PreviousPage 3 of 4Next →