🚀 go-pugleaf

In article <1316@ucl-cs.uucp>, D.Parrott@cs.ucl.ac.uk writes:
> 
> FLIC is probably the most universal of the intermediate codes because
> it was designed to be.
> ...

> %T DACTL: A computational model and compiler target
>    	  language based on graph reduction
> %J ICL Technical Journal

I would guess (although I don't know for sure) that these schemes are
biased towards lazy, pure functional languages - the mention of
graph reduction above implying this. Compilers for SML (which is neither
lazy nor purely functional) have to use different intermediate languages.
SML/New Jersey and the Edinburgh Kit Compiler use untyped lambda calculus
as an intermediate language - all the language features in ML (including
pattern matching and the modules system) can be compiled down to a pretty
simple intermediate code. In fact, if I dig around, I can probably find the
signature for the Kit Compiler's intermediate form...

    datatype 'a option = NONE | SOME of 'a

    datatype LambdaExp =
        VAR      of lvar		(* lambda variables. *)
      | INTEGER  of int			(* constants... *)
      | STRING   of string
      | REAL     of real
      | FN       of lvar * LambdaExp	(* function-terms. *)
      | FIX      of lvar list * LambdaExp list * LambdaExp
					(* mutual recursive fns. *)
      | APP      of LambdaExp * LambdaExp	(* function application. *)
      | PRIM_APP of prim * LambdaExp	(* primitive function application. *)
      | VECTOR   of LambdaExp list	(* records/tuples. *)
      | SELECT   of int * lvar		(* con/record indexing. *)
      | SWITCH_I of int Switch		(* switch on integers. *)
      | SWITCH_S of string Switch	(* ...strings *)
      | SWITCH_R of real Switch		(* ...reals *)
      | RAISE    of LambdaExp		(* raise exception *)
      | HANDLE   of LambdaExp * LambdaExp	(* exception handling. *)
      | VOID				(* nil, () etc. *)

			(* HANDLE(e1, e2) executes e1; if an exception
			   packet results, e2 is applied to the packet.
			   therefore, e2 must be a FN. *)

    and 'a Switch = SWITCH of {arg: lvar,
			       selections: ('a, LambdaExp) map,
			       wildcard: LambdaExp option
				(* mandatory for REAL or STRING switches. *)
			      }

There's no type information here at all; the compiler works on an abstract
syntax tree which it assumes has typechecked. In fact, the typechecker
has to provide a few hooks for datatype switches and the like.

SML/New Jersey has a second intermediate form, which is essentially 
lambda calculus but without nested applications, which can be used to
build continuation expressions (I'm a little fuzzy on the details).
The are a lot of intermediate passes to do closure analysis, register
allocation, and so on.

-- 
Nick Rothwell,  Laboratory for Foundations of Computer Science, Edinburgh.
                nick@lfcs.ed.ac.uk    <Atlantic Ocean>!mcsun!ukc!lfcs!nick
~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~
 "You ain't seen nothing yet. I can take this floor out too, no trouble."

In article <1316@ucl-cs.uucp> D.Parrott@cs.ucl.ac.uk writes:

>DACTL has similar aims to FLIC but is not restricted to functional
>programming.

That is a  little confusing to  say the least.   Dactl is specifically
aimed at  parallel implementations of declarative  languages.  It is a
language based on the theory of graph-rewriting (graph-rewriting is to
term-rewriting as graph reduction is to string reduction), but with an
explicit  encoding of strategy.   It  is non-deterministic,  and  will
support (almost) all    features  of languages   such  as Standard  ML
(including assignments, and imperative I/O).  Annotations may be used 
to specify such notions as locality etc.

The reference you give is also rather out of date (I think that might even
be to Dactl0 rather than Dactl1 -- the latter is an almost entirely different
language).  Try:

%A J.R.W. Gluert
%A K. Hammond
%A J.R. Kennaway
%A G.A. Papadopoulos
%A M.R. Sleep
%T DACTL: Some Introductory Papers
%R Internal Report SYS-C88-08, University of East Anglia
%D 1987
%Z Language description, implementation overviews.

%A K. Hammond
%T Implementing Functional Languages for parallel machines
%R PhD thesis, University of East Anglia
%D 1988
%Z Implementing SML using Dactl

%A K. Hammond
%T Parallel SML: a functional language and its implementation in Dactl
%I Pitman Press
%D December, 1990
%Z Published version of above -- much more detail on Dactl, with a
   simple introduction and several (largish) examples, including a
   parallel type-inference engine.

%A G.A. Papadopoulos
%R PhD thesis, University of East Anglia
%D 1989
%Z PARLOG/Concurrent Prolog in Dactl, direct implementation of full GHC
   I don't have the title to hand.

Kevin
-- 
This Signature Intentionally Left Blank.	E-mail: kh@cs.glasgow.ac.uk

In article <3054@skye.cs.ed.ac.uk> nick@lfcs.ed.ac.uk writes:
>In article <1316@ucl-cs.uucp>, D.Parrott@cs.ucl.ac.uk writes:
>
>I would guess (although I don't know for sure) that these schemes are
>biased towards lazy, pure functional languages - the mention of
>graph reduction above implying this. 

True for FLIC, but wrong for Dactl.  Dactl is a *very* general 
graph-rewriting language which supports, but does not require, lazy
evaluation.  See my thesis/book for examples of compiling eager
(and lazy and semi-lazy) SML into Dactl.  We have also used Dactl for
compiling Hope+, Common Lisp, and various logic languages.

Kevin
-- 
This Signature Intentionally Left Blank.	E-mail: kh@cs.glasgow.ac.uk

In article <7185@vanuata.cs.glasgow.ac.uk> kh@cs.glasgow.ac.uk (Kevin Hammond) writes:
>In article <3054@skye.cs.ed.ac.uk> nick@lfcs.ed.ac.uk writes:
>
>True for FLIC, but wrong for Dactl.  Dactl is a *very* general 
>graph-rewriting language which supports, but does not require, lazy
>evaluation.  See my thesis/book for examples of compiling eager
>(and lazy and semi-lazy) SML into Dactl.  We have also used Dactl for
>compiling Hope+, Common Lisp, and various logic languages.

In fact, a Hope+ -> DACTL compiler has been written which could produce
either lazy or (eager?) DACTL (Is a language with lazy constructors and
strict functions eager, strict, semi-lazy, semi-strict?).
--
        J.K.
 
John M. Kewley, ICL, Wenlock Way, West Gorton, Manchester. M12 5DR
Tel:   (+44) 61 223 1301 X2138  Email: jk@cs.man.ac.uk / jk@nw.stl.stc.co.uk