Yin Wang

> The way you've asked this it will lead people to think you're asking for very powerful static checking

That's exactly what I'm asking for :-). It should be possible to create restricted types that are checked at runtime. For example, the fabs function would return a float which is guaranteed to be >= 0. The sqrt function would require the argument to be positive.

float x;
... // arbitrary code
sqrt(x); // warning, possible invalid argument

float y;
y = fabs(...); // y is now float<positive>
sqrt(x); // no warning

float z;
z = -1.0;
sqrt(z); // error: invalid argument, argument z of type float
// fails constraint z > 0. z is constant -1.0

It is an error if the compiler can prove it to be wrong. It would probably be a warning if the compiler can't prove it to be safe - but you could optionally make it an error (to prove critical code). There are some cases where it won't work - a la solve_halting_problem() - but you could add little proofs to help it. For example, you could declare that sin(x) is `float<positive>` if `x > 0 || x < pi`.

This may sound crazy, but I think the parts are already out there. C#'s non-nullable types are a very weak version of this (the compiler can infer if something could possibly be null, and complains if you assign it to a non-nullable type). Many compilers also track uninitialized variables, and only let you assign to them, not from them. They are also effectively a…

I'm working on what I call "semantic version control". Namely, instead of diffing and merging text, the goal is to parse the program and diff/merge the AST.

EDIT: A better way to state the goal: I want to take advantage of the underlying structure of a computer program to inform the diff/merge. The first step just happens to be diffing ASTs, but I go beyond this.

I already have some neat features--for example, I can detect moves fairly robustly. That is, if you move a function, I can see that as a single action even if you modify the function a little bit when moving it (e.g. rename the parameters). Also, there is already more information for resolving conflicts in a three-way merge.

Unfortuntely, the performance is currently horrible, which makes it completely unusable. Once I fix that (I just need to memoize the diff function properly) and fiddle around with some of the algorithms a bit, I'll have something interesting (I hope :)). After that, I'll probably add a UI.

Also, I should add that I'm not the only person with this idea. A lot of the early design and features are based on YDiff[1], although I used no code from there. The merging and some of the other stuff I'm working on right now is more original though (I think).

[1]: http://yinwang0.wordpress.com/2012/01/03/ydiff/

Hey, glad you are working on this. I have later given a talk on structural version control together with demos of structural editing and ydiff. Here are the slides:

http://yinwang0.wordpress.com/2012/02/12/structural-version-control

I think structural version control can open lots of possibilities that are not accessible by text-base version control systems. I'm not really focused on this area, but I'd be happen to to see more people getting interested in this and work on it.

As for the performance of diffing, I think the bottleneck is with detection of moving. That's something that text-based diff doesn't do at all, so not a big drawback. But with structural editors, those moves can be instantly detected and logically merged by the editors. That's too far into the future though. But I think structural diffing without move detection can be of good use already.

Another direction that's possible to detecting moving more efficiently is to use hashing, the same trick used to eliminate redundant expressions in a compiler.

Too late, someone already did that and measured the overhead of up to five interpretations layers: "Scheme benchmarking with a meta-circular" interpreter http://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking/ Archive: http://web.archive.org/web/20140105145428/https://yinwang0.wordpress.com/2013/11/04/scheme-benchmarking/ HN discussion: https://news.ycombinator.com/item?id=7045734 (25 points, 443 days ago, 9 comments) (The main critic is that it should compare more scheme implementations.)

Many modern schemes (and similar languages like Racket and Clojure) have many optimization, use bytecode and jit compiling, so the abstraction overhead is not as big as in the naive versions. And you get nice code and powerful macros in exchange.

IIRC Stalin is faster than C in some benchmarks, but the compiling time is very big. "Stalin: a global optimizing compiler for Scheme" https://github.com/barak/stalin HN discussion: https://news.ycombinator.com/item?id=8214343 (85 points, 220 days ago, 70 comments)

Thanks for sharing. The first article is really interesting. The author worked 3 months as an intern at Google, and his much under-appreciated works saved Steve Yegge's Grok team that has been struggling for years.

EDIT: Found another gem from the same author: http://yinwang0.wordpress.com/2012/04/09/reinvent-y/

> Today I found that I forgot how to derive the defintion of the Y combinator. I learned it several years ago from an online article, but now the search term “Y combinator” gives me all the news about startups (sigh).

hmm interesting, just read another article on Grok yesterday posted by a previous intern of that team.
(sadly it's in Chinese, but it covered the detail of Python Indexer's implementation)
http://blog.sina.com.cn/s/blog_5d90e82f010191rh.html

EDIT:
Another article on the analyzer by this author, in English.
http://yinwang0.wordpress.com/2010/09/12/pysonar/