sexpressions, sexpr, sex!

Andrew Bromage bromage@cs.mu.OZ.AU
Thu, 22 Jun 1995 15:32:46 +1000 (EST)


G'day.

I wrote:

> functors (or constructor functions, or structured types,
> or whatever you want to call them)

Rainer wrote:

> until now i understood `functor' as sth that operates on a function and
> yields a new function.  is this completetely off the road?

Ah.  Yes, I can see how that could be confusing.  Let me explain...

My use of the word "functor" comes from logic programming.  Perhaps
"constructor function" is a better term because it better describes
what is going on.

A constructor function is simply a function which constructs a data
item.  A cons cell, for example, can be identified exactly with the
function that constructs it.  In Haskell, you would write:

data SExpr	= Atom String
		| Cons SExpr SExpr

This is equivalent to declaring two functions:

	Atom :: String -> SExpr

		This is a function which takes a string and
		returns an s-expression.

	Cons :: SExpr -> SExpr -> SExpr

		This is a function which takes two s-expressions
		and returns an s-expression.

Now constructing data items is one thing, but how would you extract
items from this?

	car :: SExpr -> SExpr
	car (Atom a) = Atom "nil"
	car (Cons e1 e2) = e1

	cdr :: SExpr -> SExpr
	cdr (Atom a) = Atom "nil"
	cdr (Cons e1 e2) = e2

Haskell handles extraction by pattern matching on the constructor
function.

> andrew, you seem to know ml, haskell and prolog.

Like any would-be academic, I have a large set of opinions about
all of them, not all of them complimentary.  :-)

I used to be a functional programmer (Miranda, Haskell/Gofer, ML,
you name it) but for my thesis I'm doing logic programming.  I
know Prolog backwards (it makes more sense that way), and I have
a brief familiarity with Goedel.

Just for fun, I'm learning Sather at the moment.  Looks fun.

> maybe you can provide or
> point to a short, but technical description of these?

Is this for our consumption or for the web page?

A good description of the first incarnation of Miranda is in the
appendix to Simon Peyton-Jones' excellent book, "The Impementation
of Functional Programming Languages".  (Miranda is not the same as
Haskell, since Haskell has a more sophisticated type system and
(IMO) a better module system, but the basic concepts are the same.)

My favourite WWW repository for functional programming was at JCU,
but unfortunately it isn't being maintained now.  Nevertheless, it's
worth a peek.  The Haskell page is:

	http://www.cs.jcu.edu.au/ftp/web/FP/hcs/current.html

The ML page is:

	http://www.cs.jcu.edu.au/ftp/web/FP/ml.html

Various LP homepages seem not to be responding, but here's some
stuff from the FAQ:

<<
The draft ISO standard for Prolog is available by anonymous ftp from
   ai.uga.edu:/pub/prolog.standard/ [128.192.12.9]
An unofficial summary of the draft ISO Prolog standard is available
from the same location as isoprolog.tex or isoprolog.ps.Z.  Send mail
to Michael Covington <mcovingt@ai.uga.edu> for more information about
his summary of the standard. For more information about the ISO Prolog
standard itself, write to Roger Scowen, ISO/IEC JTC1 SC22 WG17 (Prolog)
convener, DITC/93, National Physical Laboratory, TEDDINGTON, Middlesex
TW11 0LW, UNITED KINGDOM, call +44-81-943-6956, fax +44-81-977-7091,
or send email to rss@seg.npl.co.uk.

Richard O'Keefe's 1984 Prolog standard draft is available by anonymous
FTP from 
   ftp.ecrc.de:/pub/eclipse/std/plstd.doc
>>

Not exactly "short but technical" descriptions, but they'll do as
first approximations.

Cheers,
Andrew Bromage