[mod.ai] Seminar - Semi-Applicative Programming

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.