teaching with tributary halting problem

[Geoffery Miller]

I am making a little thing to teach about character codes, mocking up with tributary

http://tributary.io/inlet/5592618

One experience I had using tributary.  Writing the following code was pretty difficult:

while(bd.length < 8) {

    bd = "0" + bd;

}

Of course, tributary is trying to re-run my code for new displays.  But when I did not have the update step completed, the while loop is infinite and would lock up the browser.  Turning off the auto-update helps; removing the function call before the function is ready to be run also works.  

This made me realize tributary as an educational tool for classical programming logic is crippled by this halting problem:

while(true) {

//and then type }

and you're dead, maybe with an unsaved inlet :(

Two thoughts:

1.  If used as a tool for beginners, what loop techniques should be taught in tributary instead (that would still relate to most programming languages e.g. avoiding .forEach())?

2.  Solving this -- maybe an analysis step:

 - Capture new code

 - Parse the submitted code to detect while and for loops.  

 - Add in a cycle depth counter into every loop.

 - Add in a kill loop function (return) at the end of the loop when depth==a lot of iterations.

 - Send modified code to auto-updater

Geo

[Ian Johnson]

first off, this is awesome!

as for the problem, you are right of course. I like how you call it a halting problem, because theoretically this is an impossible problem to solve (turing's halting problem).

however, most of tributary doesn't jive with traditional CS, so we are in luck.

I'm currently working on making it easier to add things like this in, using esprima: http://esprima.org/

you can get the AST (abstract syntax tree) which is basically a javascript object describing the code. Using this you could walk down the tree and modify loops in the way you suggest.

This can also be a problem if you are writing a for loop and accidentally have your termination condition wrong too. I think a depth counter would work well.

I'll update with my redesigns that would make hooking in custom modifications to code much more straightforward in the tributary process.

--
You received this message because you are subscribed to the Google Groups "Tributary" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tributary+...@googlegroups.com.
Visit this group at http://groups.google.com/group/tributary?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Ian Johnson - 周彦

http://enja.org

[Geoffery Miller]

The reference to turing's halting problem was intentional :)

I wrote a tributary illustrating my idea:

http://tributary.io/inlet/5594755

Using a real parser to generate an AST is needed, as you suggest.  Is this a current task you are working on?

Geo

[Geoffery Miller]

Sorry, you said you are working on it.  Reading comprehension.

Is there somewhere on the github project I can look to see this integration?  I'd be interested in hacking at it some.

Geo

[Ian Johnson]

So, you could easily integrate your prototype into this prototype:

http://tributary.io/inlet/5564948

this one is for taking over console.log so that i can inject the output into the code. but it has everything including the code editor setup for you to play with. you mainly want to update the 'replace' function in esprima.js to do stuff when it comes across a while node.

I've found it useful to use esprima's interactive site to understand what javascript turns into when you parse it out:

http://esprima.org/demo/parse.html

(you could for example put in:

"while(true) {}"

and

"var depth = 0; var maxdepth =100; while(true) {}"

to compare the trees and see what you have to do to insert your stuff.

I've been mulling over writing some helper functions for turning a string of javascript into AST nodes that you can directly insert, but haven't done it yet.

hit me up on gchat if you're hacking and run into problems!

[Drew Skau]

It would be really cool to see a depth counter going up next to the loop as the code was executing, especially for slower loops.

[Geoffery Miller]

Awesome.  I'll play around with this.

Geo

[Ian Johnson]

I thought of a way to make prototyping this a little easier:

http://tributary.io/inlet/5597237

i tried out the snippet thing, and cleaned up the way i'm filtering the AST

the next part from here would be to create a block expression for the while statement if it doesn't have it, and then in both cases insert the kill check + statement

[Geoffery Miller]

I am going to start tackling this as a plugin that could be enabled/disabled in the config panel.  Thanks for this inlet (http://tributary.io/inlet/5597237) , it will be very helpful.

An interesting thing about codemirror is that you can intercept an input change before it commits to the text editor.  I am planning on intercepting inputs to flag when there may be a loop, and then when the code is syntactically correct, use the esprima code to inject a depth counter.

https://github.com/georules/tb-halting-plugin

Geo

[Geoffery Miller]

A side note, I am planning on injecting the depth counter silently, which will mean that the code that you see in the code editor will not be code that is running in the display.

Geo

[Ian Johnson]

very cool!

this will be great.

are you thinking of adding a marker or line widget or something to let the user know they created an infinite loop and are being saved?

also, if you look at src/code.js and see the handleParser function, i put that there for the inline-console plugin which uses esprima to parse stuff.

I was hoping to generalize the code from inline-console so that we only need to run through esprima once, but different plugins could insert their own callbacks to modify the AST how they want.

I can help with that soon since you'll be working on it.

On Fri, Oct 4, 2013 at 10:19 AM, Geoffery Miller <geoffer...@gmail.com> wrote:

A side note, I am planning on injecting the depth counter silently, which will mean that the code that you see in the code editor will not be code that is running in the display.

Geo

--

You received this message because you are subscribed to the Google Groups "Tributary" group.

To unsubscribe from this group and stop receiving emails from it, send an email to tributary+...@googlegroups.com.

Visit this group at http://groups.google.com/group/tributary.

For more options, visit https://groups.google.com/groups/opt_out.

[Geoffery Miller]

I was planning on adding a line marker so that when an injected loop is stopped by the depth counter, they can know why.  I figure this is important in case that the depth counter is too small, so that the user can know to manually disable the plugin (if desired).

Very true -- if I can hook into esprima already doing some work, that would be helpful.  I'll look into the inline-console plugin to see what you did there.

Geo