Tim@UPENN.CSNET (Tim Finin) (01/28/86)
SEMI-APPLICATIVE PROGRAMMING: AN EXAMPLE
N.S Sridharan
BBN Labs, AI Department, Cambridge MA
3pm Thursday, January 30, 1986
216 Moore, University of Pennsylvania
Most current parallel programming languages are designed with a sequential
programming language as the base language and have added constructs that allow
parallel execution. We are experimenting with an applicative base language
that has implicit parallelism everywhere, and then we introduce constructs that
inhibit parallelism. The base language uses pure LISP as a foundation and
blends in interesting features of Prolog and FP. Proper utilization of
available machine resources is a crucial concern in functional programming. We
advocate several techniques of controlling the behavior of functional programs
without changing their meaning or functionality: program annotation with
constructs that have benign side-effects, program transformation and adaptive
scheduling. This combination yields us a semi-applicative programming language
and an interesting programming methodology.
In this talk we give some background information on our project, its aims and
scope and report on work in progress in the area of parallel algorithms for
context-free parsing.
Starting with the specification of a context-free recognizer, we have been
successful in deriving variants of the recognition algorithm of
Cocke-Kasami-Younger. One version is the CKY algorithm in parallel. The
second version includes a top-down predictor to limit the work done by the
bottom-up recognizer. The third version uses a cost measure over derivations
and produces minimal cost parses using a dynamic programming technique. In
another line of development, we arrive at a parallel version of the Earley
algorithm.