Uni-Logo

JavaScript

Recency Types for Analyzing Scripting Languages

Abstract

With the current surge of scripting technologies, large programs are being built with dynamically typed languages. As these programs grow in size, semantics-based tools gain importance for detecting programming errors as well as for program understanding.

As a basis for such tools, we propose a descriptive type system for an imperative call-by-value lambda calculus with objects. The calculus models essential features of JavaScript, a widely used dynamically-typed language: first-class functions, objects as property maps, and prototypes.

Our type system infers precise singleton object types for recently allocated objects. These object types are handled flow-sensitively and change during the objects' initialization phase. The notion of recency provides an automatic criterion to subsume these precise object types to summary object types, which are handled flow-insensitively. The criterion applies on a per-object basis. Thus, the type system identifies a generalized initialization phase for each object during which the change of its value is precisely reflected in the change of its type. Unlike with linear types, summary types may refer to singleton types and vice versa.

We prove the soundness of the type system and present a constraint-based inference algorithm. An implementation is available on the web.

JavaScript Code Database

In order to answer statistical questions about JavaScript code, we collect a lot of JavaScript code from the web, parse it (using Rhino) and save the AST of the source code into an XML Database. Using this database we try to answer questions like:

  • How many programs make use of prototypes? How many programs make use of prototypes for functions?
  • How often is eval used?
  • How many programmers use the first class function of JavaScript?
  • How many programmers access object properties with dynamic computed strings?
  • How often do programmers store data in strings?
  • How often is the with statement used?
  • How often are global variables used?

We developed a web interface to our database. It allows you to ask XPATH expressions.

Implementation

This is a prototype. After installation you can run the tests with the command: 

make test

This includes examples from the paper together with a lot of other unit tests.

Have a look at the file gtest.ml. There you find a set of examples. Add new tests to this file and let the tests run (use make test). This is the suggested way to test how the prototype behaves. The examples show how you can access the results of the analysis.

Installation

The code requires the OCaml compiler in version 3.10.2 or later. You may use your package manager of your distribution to install ocaml and findlib together with ocamlgraph. The following packages are required (use ocamlfind to install them):

  • unix (version shiped with ocaml)
  • ocamlgraph (version 0.99c)
  • proglangUtils

Downloads (New - 23.02.2010)

ProglangUtils

Downloads (Old)
ProglangUtils (Old)