Script interpreter time-jumping.

I'm writing a "game"-engine for visual novels in python and have the following problem:

My engine includes a script-interpreter for a language without 'if' and 'for' statements. I save the interpreter-state for each line in a cache, so I can jump to a line without executing the whole file up to that point. When the sourcecode changes, the engine sets the cached interpreter-states for the involved lines to None. The engine rebuilds outdated states by going downwards from each None and filling newly calculated states into the cache until the calculated state matches the one that is already in the cache (before overwriting it), because it's safe to assume that all further states are not affected by the change. Example:
1 {}                       a=0
2 {"a": 0}                 b=3
3 {"a": 0, "b": 3}         #comment
4 {"a": 0, "b": 3}         a=1
5 {"a": 1, "b": 3}         c=7
6 {"a": 1, "b": 3, "c": 7} #commentIf line 1 is changed to "a=1" the engine rebuilds lines 1-5. Because at line 5 the calculated state and the cached one are the same. Now there is a problem with that approach. When I have a 5000 line file and I change a variable at the top, the changes propagates through the whole file and the engine starts lagging. A solution I'm considering is using something like {"a": [0]} instead of {"a": 0} and using references to the same 1-element-list from all states wherein the variable in question isn't changed. In the example that "a=0" is changed to "a=1" this would lead to all 0s from 1-4 to be 1s afterwards when actually only one number was changed. The rebuild stops at 2 already because the calculated and cached state match. This is definetly a speed-up, but only works with assignments. If line 3 had something like a=a+10 the rebuild-cursor would never reach the line 3 because the references across states break the assumption mentioned earlier. At least when not used correctly. I can't even make special treatment for this kind of instructions because commands can be user-defined too. A different approach would be to store the data like cache[var][linenr] instead of cache[linenr][var]. I haven't thought about that much yet. Also, I can only support simple types yet, like ints. I need to find a way to have (recursively) versioned python-objects.

It's quite difficult to put all this into words. There is still more, but I don't even know if /prog/ is able to help me so I won't bother to type it down (yet)

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-25.html#%_chap_4

JEWS

>>2
>Wall of text
;_;

>>3
Fuck you

>>2
Lisp is shit.

I suspect >>1 is trolling. If it is doing a diff on the file to know what changed, it could as well just re-execute every instruction. Or is Python that slow?

>>6
I'm not trolling. This software is actually being developed.
Diff is much faster, because implemented in C. But I'm not using diff in that context anyway. My per-line costs are close to the minimum already. But it's still too slow. I really need to reduce the amount of lines being rebuilt or the amount of lines I rebuild per iteration.

>>7
Explain how your program gets to know which lines changed, please. Does it contains an integrated editor?

>>8
Yes, it uses a GTKTextBuffer which sends insert and delete events with iterators at the relevant positions.

>>7
So why did you choose to develop a new language over an existing one like Lua or Python?

>>9
Store with each assignment the relative location of the next assignment to the same variable. When an assignment is modified, propagate the change up to and including that next assignment. If it is changed, continue propagation recursively.

>>10
Being able to revert to earlier states is a very important feature of VNs. The easiest way would be to implement a data-language, but the (future) authors using the engine want a script-language for more freedom. Ren'Py actually uses python for that purpose, by replacing the most popular python-types (like list, tuple, set) by custom types that support rollback. It's very messy. So that's why I didn't choose python.

>Lua
Have you every used that language?!

It's easier to implement my own language, because I can limit its power.

(just to be sure you don't misinterpret what I wrote)
You need to recursively propagate not only for the last assignment, but for any assignment which changed in the live interval!

>>11
When someone inserts a line between the two assignments, all offsets above the inserted line become invalid.

btw: A video of a prototype-version: youtu.be/e6JDAOwbjDo

>>14
all offsets above the inserted line become invalid.
Add the number of instructions inserted to the offset, duh. I thought it was obvious so I didn't specify it.

The (user-written) interpreter is a black box with (state, line) as input and state as output.
I think I'll move away from that, because if the input and output are {"a":1} I can't tell if the 'a' was just left as it is or newly assigned to 1.
I will use a special object that implements __setattr__ to record those actions.
Also I'll record all calls to __getattr__ to find out what variables the output of a single delta depended on so I can skip recalculation of a delta, when I know that none of the variables that were read last time were changed. However, user-code could break this optimization by requesting all variables, even when they aren't used.

It'll take some time until I implement this.

Now, what should I do when objects other than ints and strings get assigned to one of the state-variables?

>>16
I'm not sure I understand what you mean because I'm not familiar at all with Python and your architecture. Are __getattr__ and __setattr__ dictionary hooks? What is a delta? What is user-code, is it written in Python or your interpreter's language?

Now, what should I do when objects other than ints and strings get assigned to one of the state-variables?
Nothing special. Python has dynamic typing, doesn't it?

>>17
In javascript a["b"] and a.b are the same. In python they are seperate and can both be intercepted by a.__getitem__ and a.__getattr__
By delta I was referring to the script-lines. They are "added" to the state of the previous line.
The engine is written in python, the scripts are written in a language that is interpreted by code written by the user.

Assignment is not the problem, what is a problem is that when I do
obj = Obj()
obj.v=1
cache[0]=obj
obj.v=2
cache[1]=obj
that cache[0].v will be 2 because they are references to the same object.

An example for that 'user-written' code is:
def usercode(state, line):
    newstate = {"text": state["text"]}
    cmd, rest = line.split(" ", 1)
    if cmd=="say": newstate["text"] = rest
    return newstate

>>18
obj.v = 2 actually is obj = obj but .v = 2 (pseudo-code). It's the same logic that is behind array SSA form.

>>20
I don't get it.

>>21
obj.v = 2 should be translated to obj = update(obj, {.v: 2}) where update is a pseudo-operation that's the only way to modify a member attribute.

Note that update is a pure function, it doesn't actually modify the object but returns a new one.

>>23
oh that makes sense. That means that I can never give the user-code the real objects but only proxy-objects.

No other way to do it than what you've got, unless you basically want to set up a virtual "file system" for your code.

In that case you have the code that exists in that space, then a pointer to the next code segment. That way, adding new code only changes pointers. The problem still exists where if you change a code to be larger than a certain size segment, you either shift all the existing segments up in pointer count (if the pointer is past that code - not before), or you could instead propagate that code into the next-code pointer, but that has a problem where if you try to share pointer sections (say for searching or other algorithms) it would fuck over those.

Or a third solution would be to skip the segment that's too small, and go to the end of file as there will always be available space, but then you have to run a defragmenter every so often.

Wait... you're developing this shit FROM SCRATCH, i.e. not reverse-engineering some braindead Japanese bullshit but inventing your own braindead bullshit engine?

If your engine lags when you execute a 5000 line file, it's because you're doing stupid shit like this.

use a language made by people who know how to program

I've been reading >>1 plea a couple of times and I still don't get whats going on.

1. You have a `language' you're making that doesn't have if and for (and implies I assume, that there are no alternative primitives): how can it have anymore than one state for each tick of the time line, isn't the `language' equivalent to a linear movie screenplay, how can the visual novels be interactive?

2. Somehow you've crammed in a couple of fibs and an Ackermann every tick, I don't see how scripting the events behind a visual novel can be so slow, does it have a physics engine?

3. Because of slowness you make a precomputed choice-point table, so you can backtrack Prolog-style, for this (supposedly?) choice-point-free language.

4. Changing of the source code is a common use case that needs to be optimized, so you're making a home made diff engine that dynamically patches the choice-point table. wtf?

If the root of 3 and 4's raison d'être is constant time execution costs of running an interpreter in a slow interpreter and not of some algorithms you haven't mentioned. You really should either implement your interpreter in C and FFI it, or implement a meta circular evaluator (at least use a language that allows this) with a couple custom procedures for its environment to maintain speed.

With the latter route, write a translator that translates each line to the equivalent in your language of
(lambda (input-data)
  (your-instructions) ...
  (values new-data (wait-on-input)))
where input-data and new-data are immutable hash-tables and wait-on-input saves the continuation into a lambda and returns from eval, and then call the returned function to resume continuation to go to the next tick. To `backtrack' just cache the continuation functions and execute the one you want (immutable data at that point will be reused and further data will be GC'd) or go clean slate and re-run the script and skip waiting until the wanted location. Even if it passes through 5000 lines this really should be nothing, some Lisps and Schemes are JITted, they may also JIT the sandboxed evaluation, it would be a bonus if your language supports this. Decision points (whether you have them or not) are easily integrated with this approach, just by memoizing user input.

>>12
It's easier to implement my own language
Famous last words.

jews

>>29
First of all, thank you for this serious answer.

About point 1: The scripts-segments *are* linear, but they can be arranged by a higher-level code (in python). (States are not transferred across scenes)

About point 2: The expected user-group has no idea of proper programming and is likely to actually try something similar. I used a profiler and it turned out that the determination of ident-level used 0.5secs per 10000 lines. That's because I haven't separated parsing and execution yet. And I'll store the result of parsing as a lambda. (for performance)

I don't completely understand what you mean by 3. What I precompute are the states at each point in time. They aren't alternatives.

Ad 4. I'm only using 'diff' when reloading the file from disk (and in that case performance doesn't matter). Normally I get insert and delete events from gtk with line-numbers.

I think that the lisp-code you posted is what i'm doing already. Yours is just easier to read and understand. (I need to learn Lisp already)

And the language has to be a custom one, because it's much easier to type:
Karin happy: "Oh, how are you?"
than:
karin.face = "happy"
karin.say("\"Oh, how are you?\"")

>>31
LISP could do that with macros:

  (defmacro p6sub (&body body)
    (let ((auto-arg-list ()))
         (labels ((collect-args (code)
                    (dolist (element code)
                            (cond ((listp element)
                                   (case (car element)
                                         (quote t)
                                         (let (dolist (let-item (cadr element))
                                                      (when (listp let-item)
                                                            (collect-args (cadr let-item))))
                                              (collect-args (cddr element)))
                                         ; ... Insert more cases here for other code constructs.
                                         (t (collect-args (cdr element)))))
                                  ((and (symbolp element)
                                        (char= #\^
                                               (char (symbol-name element) 0)))
                                   (pushnew element auto-arg-list))))))
                 (collect-args body)
                 `(lambda ,(sort auto-arg-list #'string< :key #'symbol-name)
                          ,@body))))

>>32
The Forced Convention of Indenting Code.

>>32
Why do you use more than two spaces of indentation? Disgusting.

>>34
That's a transmission error.

>>32
lisp is shit

>>32
As I said; I can't into lisp.

>>33
>>34
>>35
>>36
HERE WE GO!

>>31
karin.face = "happy"
karin.say("\"Oh, how are you?\"")
Why don't you just:
[code=python]karin.sayWithEmotion("happy", "I'm a huge faggot, please rape my face")[/code]
or:
[code=python]karin.emote(HAPPY).say("I'm a huge faggot, please rape my face")[/code]
Or:
[code=python]# I have no idea if python has operator overloading, but if it does:
karin[happy].say("hax my anus")[/code]
You just at programmings~

>>38
Or, simply,
karin.say("Oh, how are you?", "happy")
Where the function definition is something like this:
def say(self, message, face="normal"):

There are many brands of <a href="http://www.barbourjackets-uk.org/"><strong>barbour fusilier</strong></a> in the market today. Each of the brand promises to bring out something new to the customers.

>>39
karin.setMsg("Oh, how are you?)
karin.setFace("happy")
karin.say()

>>41
Typical OOP bloat
1.you have to make karin thread local anyway
2.every method call adds up.
3.if the idea is to optimize the code an array of pointers is much better
karinPtrArrayDefault={ptrMsg,ptrFace,...} //default
karinPtrArrayMsg={newMsgPtr,newPtrFace} // new pointer values
karinFunc(ArrayPtr){displayKarinArray(ArrayPtr);}

Can someone hook me up with that script that filters the invisible poster? I can't take it anymore.

>>43
Just use the SetFilter command and set it to "/V o i d/gim"
// ==UserScript==
// @id             Shiichan
// @name           Shiichan
// @version        1.7
// @namespace      4chan
// @author         FrozenVoid
// @description    Provides Shiichan enchancements
// @include        http://dis.4chan.org/*
// @run-at         document-end
// ==/UserScript==
//1.7 merged tripfiller code
GM_addStyle(".label,.label,.namelabel,.navlinks,.postername,.postfieldleft,.emailfield,blockquote,.threadlink,h2{display:none;};")
var fullthreads=1;
var maxrows=7;
var maxcols=140;
var nameinplen=42;
var emailinplen=42;
var FORCE_MONOSPACE=0;
var SHOW_FILTERED_SIZE=1;
function rem(x) x.parentNode.removeChild(x)
function tag(name) unsafeWindow.document.getElementsByTagName(name)
function cla(name) unsafeWindow.document.getElementsByClassName(name)
function id(name)  unsafeWindow.document.getElementById(name)
function log(data) GM_log(data)
function tistr(data)  unsafeWindow.document.title=(data).toString()
function geto(obj) XPCNativeWrapper.unwrap(obj)
function sa(obj,att,val) obj.setAttribute(att,val)
function ga(obj,att) obj.getAttribute(att)
function sall(arr,att,val){ for(i in arr)sa(arr[i],att,val);}
function setfilter(data){GM_setValue("filter",data);}
function setfilt(){var data=prompt("Edit filter",GM_getValue("filter",/filter data/gim));
setfilter(data);
}
function getfilter(){return GM_getValue("filter","/123456789/gim");}
GM_registerMenuCommand("SetFilter", setfilt,"s")
var filter=getfilter()
var namefilter=filter;
var a,i,postfilter=filter,linkfilter=filter;
a=tag('textarea');
sall(a,'rows',maxrows);
sall(a,'cols',maxcols);

if(fullthreads){a=tag('a');//fix thread links
for(i in a)if(a[i].name&&a[i].href.search('-')!=-1)a[i].href=a[i].href.replace(/\/\d+\-\d+|\/\d+\-/,'');}

a=tag('blockquote');abl=a.length;
for(var i=0;i<abl;i++){
if(a[i]&& a[i].innerHTML.search(postfilter)==-1){
if(FORCE_MONOSPACE){a[i].innerHTML="<code>"+a[i].innerHTML+"</code>"}
sa(a[i],"style","display:block");}else{
a[i].parentNode.innerHTML+='[Post filtered:'+(SHOW_FILTERED_SIZE?a[i].textContent.length+' bytes]':']')
//view Selection source for hidden comments
}}
a=cla('threadlink');for(i=0;i<a.length;i++){
if(a[i]&&a[i].innerHTML.search(linkfilter)==-1){
sa(a[i],"style","display:block");}}

a=tag('h2');for(i=0;i<a.length;i++){
if(a[i]&&a[i].innerHTML.search(linkfilter)==-1){
sa(a[i],"style","display:block");}}

a=cla('postername');for(i=0;i<a.length;i++){
if(a[i]&&a[i].innerHTML.search(namefilter)==-1){
sa(a[i],"style","display:inline");}}


function filldata(){
var a=tag('input'),c=tag("textarea"),i;
var text=GM_getValue("text",""),name=GM_getValue("name",""),email=GM_getValue("email","");
;
for(i in a){
if(a[i].name=='kotehan'){a[i].size=nameinplen;a[i].value=name}
if(a[i].name=='meiru'){a[i].size=emailinplen;a[i].value=email}}
for(i in c){if(c[i].name=='com')c[i].value=text}}

function setpro(x){
var data=prompt("Edit "+x,GM_getValue(x,""));
GM_setValue(x,data);filldata();}
GM_registerMenuCommand("setText",function(){setpro("text")})
GM_registerMenuCommand("setTrip",function(){setpro("name")})
GM_registerMenuCommand("setMail",function(){setpro("email")})
filldata();

>>44
Why thank you, good sir.