omphalos / inductive.js Goto Github PK

View Code? Open in Web Editor NEW

25.0 6.0 2.0 677 KB

Inductive programming in JavaScript

License: MIT License

JavaScript 99.96% Shell 0.04%

inductive.js's Introduction

inductive.js

This is an experimental library which uses unit tests to autogenerate working code.

Example:

specify('myFunc',
  given(2, shouldReturn(4)),
  given(3, shouldReturn(9)),
  use('*'));

/* This code is autogenerated:
function myFunc(arg0) {
  return (arg0 * arg0)
}
*/

As the unit tests change, the output code automatically changes:

specify('myFunc',
  given(2, shouldReturn(8)),  // 4 changed to 8
  given(3, shouldReturn(27)), // 9 changed to 27
  use('*'))

/* This code is autogenerated:
function myFunc(arg0) {
  return (arg0 * (arg0 * arg0))
}
*/

It works by doing a breadth-first, brute force search over strongly typed abstract syntax trees and returns the first one that satisfies the unit tests.

The use function gives inductive.js building blocks to choose from as it searches for a solution. In this case we've given it the multiplication operator. It combines these building blocks with the function's arguments to create candidate test programs.

Ideally, we wouldn't need a use function, but the search space of all possible JavaScript programs is too large to be practical.

Still, even with this limitation, inductive.js has benefits over conventional unit tests:

We only need to write and maintain one version of the code, instead of having to simultaneously update code and tests whenever we make a change.
Inductively generated code is generally more reliable because we have a programmatic guarantee that we haven't included code that isn't related to a test.

Inductive.js can handle non-toy problems as well. For example, I/O operations like AJAX are handled using mocks. Additionally, specifications are composable, so inductive.js can generate programs of any size or complexity.

Value

The main value of inductive.js is software verification. The solver uses a strong type system that all programs runs through as they are generated.

Additionally, inductive.js code is immutable by default, which decreases the likelihood of software errors.

Finally, all code is tied programmatically to unit tests. This provides a much stronger guarantee than conventionally-tested code.

Quick Start

First:

npm install inductive.js

Then create a file called helloworld.i.js:

// Load the DSL:
require('inductive.js').globals()

// Specify our program:
var helloWorld = specify('helloWorld',
  givenNoArgs(
    shouldReturn(undefined),
    mock('console.log',
      verify('hello world'))),
  use(
    'console.log',
    value('hello world')))

run(helloWorld)

// Generate the .js file:
saveAll()

Run the spec:

node helloworld.i.js

This autogenerates the code:

function helloWorld() {
  return console.log('hello world');
}

helloWorld();

We can now run the auto-generated program:

node helloworld.js

Docs

Complete docs are forthcoming. In the meantime, the testSolves.i.js file contains many examples. The buildingBlocks.js file contains the default list of building blocks that you can include with the use command. The wiki contains some general info as well.

License

MIT

inductive.js's People

Contributors

Stargazers

Watchers

Forkers

silky cxm01

inductive.js's Issues

strongly typed AST

I actually renamed the other question, but I was looking at the verbosity levels because I was really trying to get a dump of the strongly-typed ASTs to see how everything hangs together, could you maybe provide a pointer how to do that ?
I realize that there are different kinds of ASTs depending on the stage of the solver - I am mainly interested in the BFS implementation that traverses the AST to compare candidate trees.

In particular, I would like to learn how new objects/types are represented at the AST level.

Thank you

template/macro syntax for as()

Could you briefly explain how the macro expansion works in some of the more esoteric cases, e.g:
@Map<('a | undefined)>[@String]

Explain build system

Very interesting ideas in inductive paradigm. I am just getting started. I tried to make an add function after the helloworld example. But I don't understand the error. A better explanation of the execution model / build system might help. Thanks!

require('inductive.js').globals()

var adder = specify('adder',
  given(1, 2, shouldReturn(3)),
  use('Number+')

run(adder)

saveAll()

Error: Cannot run a Specification that takes arguments: run adder

verbosity handling

It seems it's using magic numbers for now (setOptions({ verbosity: 10 })) - wouldn't it make more sense to var verbosity = require('lib/verbosityLevel.js') and then use the key of the object as the value for the hash, i.e.:

setOptions({ verbosity: verbosity.solutionAst })

i.e. to make things more self-explanatory ?

Parallelization discussion

Referring to the BFS talks, I would like to look at the solver and specifically investigate how much work it would be to get a list of all "independent" specifications - i.e. those not used anywhere else, and then hand those off to the solver separately, i.e. using an array of specifications and a forEach call to invoke the solver as a callback

Once that works, I would like to investigate doing that in parallel using a pool of worker threads.

The final step would be doing this recursively for specifications that depend on other specifications, i.e. investigating if there is any global solver state that needs access serialized, or preferably turning everything into a map/reduce style workflow that can be processed in functional programming style or using some kind of message-passing to run the solver async.

Pseudo code:

var specs = getSpecifications()
specs.forEach( function(spec) {
invokeSolver(spec);
});

self-documenting DSL idea for buildingBlocks.js

When I looked at buildingBlocks.js, I realized that it would be really useful if each buildingBlock could have an optional "description" string, that would make it possible to obtain context sensitive help for APIs that are not yet sufficiently documented elsewhere - in fact, each building block could even contain an actual example, so that this could be used for interactive troubleshooting - e.g. the register() helper at the top of buildingBlocks.js could then also add documentation related info for each building block added via express() to the object, so that this could be used for better troubleshooting, and even to help create/update documentation procedurally - i.e no DRY, because the docs would be part of the code, kinda like Python docstrings

breadth first search ?

In the docs you said inductive.js is running a BFS (breadth-first search) - and I checked the solver and was wondering if there is any kind of scheme, or even just idea, to run a parallel search to use multiple cores, i.e. using something like parallel.js to run a bidirectional search using two threads,
what do you think ?

I have some non-trivial specs to solve and would be interested to learn about leveraging multicore hardware - for instance, I have access to a 12-core system with 48 gb of RAM and would like to use that hardware to help speed up the solver.

reusing specified code as building blocks for other specs ?

Hi,

thanks for providing this, it's really awesome - I skimmed through the buildingBlocks.js and the tests and could not find an answer to my question: is there a way to reuse a spec as the building block for another spec, i.e. so that specs can be incrementally "solved" ?

Besides, is there a way let it use named arguments ?

Thanks