haskell - Is it usual for interaction nets to leave piles of redundant fans? -

-

i'm compiling lambda calculus terms interaction nets in order evaluate them using lamping's abstract algorithm. in order test implementation, used church-number division function:

div = (λ b c d . (b (λ e . (e d)) (a (b (λ e f g . (e (λ h . (f h g)))) (λ e . e) (λ e f . (f (c e)))) (b (λ e f . e) (λ e . e) (λ e . e)))))

dividing 4 4 (that is, (λ k . (div k k)) (λ f x . (f (f (f (f x)))))), net:

enter image description here

(sorry awful rendering. λ lambda, r root, d fan, e eraser.)

reading term back, church number 1, expected. net inflated: has lot of fans , erasers serve no obvious purpose. dividing bigger numbers worse. here div 32 32:

enter image description here

this again reads one, here can see longer tail of redundant fan nodes. question is: is expected behavior of interaction needs when reducing particular term or possible bug on implementation? if isn't bug, there way around that?

yes, usual (but there techniques lessen presence)

abstracting details of implementation interaction nets, , hypothesis of soundness of abstract algorithm div, seems fine me.

  • no further interaction can applied output show, in spite of chi's claim, because none of pairs d-e can interact through principal port.

  • this latter kind of reduction rule (that not allowed in framework) may improve efficiency , sound in particular cases. basically, involved fan must not have "twin", i.e. there must exists no d' in net such annihilation d-d' can happen. more details, @ the optimal implementation of functional programming language, chapter safe nodes (which available online!), or @ original paper came:

    asperti, andrea, , juliusz chroboczek. "safe operators: brackets closed forever optimizing optimal λ-calculus implementations." applicable algebra in engineering, communication , computing 8.6 (1997): 437-468.

  • finally, read-back procedure must intended not sort of external cost reduction precedure, rather deferred cost of computing duplication , erasure. notice, such cost negligible, if want test efficiency in real-world scenario, sum both sharing reduction , read-back reduction.


Comments

Post a Comment

Popular posts from this blog

python - pip install -U PySide error -

-
does know how avoid following error when running pip install -u pyside per official website instructions here: https://pypi.python.org/pypi/pyside/#installing-pyside-on-a-mac-os-x-system note have done brew install qt successfully. you using pip version 7.0.3, version 7.1.2 available. should consider upgrading via 'pip install --upgrade pip' command. collecting pyside using cached pyside-1.2.4.tar.gz installing collected packages: pyside running setup.py install pyside complete output command /applications/anaconda/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-build-cpxemt/pyside/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-0r7hri-record/install-record.txt --single-version-externally-managed --compile: ...
Read more

arrays - C++ error: a brace-enclosed initializer is not allowed here before ‘{’ token -

-
simple question: i'm trying initialize array within c++ class declaration: using namespace std; #include <string> class myclass{ public: string myarray[] = {"a","b","c"}; }; and i'm getting error: error: brace-enclosed initializer not allowed here before ‘{’ token no, without complied c++11 compiler, cannot initialize member array in declaration. have initialize array member in constructor. , don't use open array if know number of elements initialize array.
Read more

cytoscape.js - How to add nodes to Dagre layout with Cytoscape -

-
i trying add nodes dagre graph through cityscape.js. problem nodes not painted. code have: cy.add({ group: "nodes", data: { id:"n0",name:"n0",weight: 75 }, }); $.ajax(url).done(function(jsontree){ var newnodes=[]; for(var i=1;i<6;i++){ //var child = jsontree.result[i]; newnodes.push( { group: "nodes", data: { id: "n"+i, name:"n"+i}}, { group: "edges", data: { id: "e"+i, source: "n0", target: "n"+i } } ); } cy.add(newnodes); any ideas? have used loaded function reload graph not work. not know if have use specific function reload graph. thank in advance. you need add positions new nodes. cytoscape.js docs : it important note positions of newly added nodes must defined when calling cy.add(). nodes can not placed in graph without valid position — otherwise not displayed. yo...
Read more