From: gavino
Subject: John Backus and function level programming
Date: 
Message-ID: <51624c3b-f932-4a28-b728-385e06a06c54@w1g2000prk.googlegroups.com>
Hello I was wondering if lispers even implemented the Ideas john
backus had about function level progarmming...there does not seem to
be an implementation of his ideas on the web and since lisp is good at
implementing paradigms of programming I was curious.
http://www.archive.org/details/JohnBack1987

From: Pascal J. Bourguignon
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <7c7i36spoh.fsf@pbourguignon.anevia.com>
gavino <·········@gmail.com> writes:

> Hello I was wondering if lispers even implemented the Ideas john
> backus had about function level progarmming...

There's already higher level functions in lisp.  For example (see the
paper of which the url is given below), insert is reduce, apply-to-all
is mapcar & apply.  So you can easily write your functions in
functional style:


(defmacro compose (&rest functions)
  (labels ((compose-sexp (functions var)
             (cond
               ((null functions) var)
               ((symbolp (car functions))
                (list (car functions) (compose-sexp (cdr functions) var)))
               (t
                (list 'funcall (car functions) (compose-sexp (cdr functions) var))))))
    `(lambda (x) ,(compose-sexp functions 'x))))


(defmacro define (name expression)
  `(progn (setf (symbol-function ',name) ,expression)
          (setf (documentation ',name 'function)
                ',(format nil "~S is a function defined with DEFINE~%Source: ~S"
                          name expression))
          ',name))

;; These ones still use parameters; you only need to write more utility functions
;; to be able to easily write them in functional style too.
(defun transpose    (x) (apply (function mapcar) (function list) x))
(defun apply-to-all (f) (lambda (x) (mapcar (lambda (y) (apply f y)) x)))
(defun insert       (f) (lambda (x) (reduce f x)))


;; Here is inner-product = (insert +) o (apply-to-all x) o transpose

(define inner-product
    (compose (insert (function +))  (apply-to-all (function *))  transpose))

(inner-product '((1 2 3) (4 5 6)))
 --> 32


> there does not seem to
> be an implementation of his ideas on the web 

Yes, some stuff is not on the web, you have to work them out yourself if you want them.


> and since lisp is good at
> implementing paradigms of programming I was curious.
> http://www.archive.org/details/JohnBack1987

Read the corresponding paper:
http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf 
and implement the utility routines that are missing in CL.


-- 
__Pascal Bourguignon__
From: William James
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <gojqhr016l4@enews2.newsguy.com>
Pascal J. Bourguignon wrote:

> ;; Here is inner-product = (insert +) o (apply-to-all x) o transpose
> 
> (define inner-product
>     (compose (insert (function +))  (apply-to-all (function *))
> transpose))
> 
> (inner-product '((1 2 3) (4 5 6)))
>  --> 32

Clojure:

user=> (defn inner-product [x] (apply + (apply map * x)))

user=> (inner-product '((1 2 3) (4 5 6)))
32
From: =?UTF-8?B?QW5kcsOpIFRoaWVtZQ==?=
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <gojtif$65t$1@reader.motzarella.org>
William James schrieb:
> Pascal J. Bourguignon wrote:
> 
>> ;; Here is inner-product = (insert +) o (apply-to-all x) o transpose
>>
>> (define inner-product
>>     (compose (insert (function +))  (apply-to-all (function *))
>> transpose))
>>
>> (inner-product '((1 2 3) (4 5 6)))
>>  --> 32
> 
> Clojure:
> 
> user=> (defn inner-product [x] (apply + (apply map * x)))
> 
> user=> (inner-product '((1 2 3) (4 5 6)))
> 32

It’s not very typical for Clojure users to use Lists here.
(inner-product [[1 2 3] [4 5 6]]) is fine and one quote shorter.


André
-- 
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org/
From: namekuseijin
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <aaaad500-ef9f-4b16-8f95-f501b9ab1a99@41g2000yqf.googlegroups.com>
On Mar 3, 2:48 pm, "William James" <> wrote:
> Pascal J. Bourguignon wrote:
> > ;; Here is inner-product = (insert +) o (apply-to-all x) o transpose
>
> > (define inner-product
> >     (compose (insert (function +))  (apply-to-all (function *))
> > transpose))
>
> > (inner-product '((1 2 3) (4 5 6)))
> >  --> 32
>
> Clojure:
>
> user=> (defn inner-product [x] (apply + (apply map * x)))
>
> user=> (inner-product '((1 2 3) (4 5 6)))
> 32

See, guys?  He's already half way to Lisp from Ruby. ;)

didn't take that long...
From: Xah Lee
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <3eea8482-d453-4bf8-aab6-99f90c8b045e@r15g2000prh.googlegroups.com>
On Mar 3, 5:26 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> gavino <·········@gmail.com> writes:
> > Hello I was wondering if lispers even implemented the Ideas john
> > backus had about function level progarmming...
>
> There's already higher level functions in lisp.  For example (see the
> paper of which the url is given below), insert is reduce, apply-to-all
> is mapcar & apply.  So you can easily write your functions in
> functional style:

Boy, lisp IDIOTS are quick.

Lisp does not do functional level programing. Can't. Nor does almost
all the well known functional langs such as Ocaml, Haskell,
Mathematica.

See:
http://en.wikipedia.org/wiki/Function-level_programming

I learned about it last year. See:
http://groups.google.com/group/comp.lang.lisp/browse_frm/thread/8793538dc0d909d1

I quote:

hard to summarize in one sentence... but basically like functional
programing but with one characteristic formalism that sets it apart,
namely: creation of functions are limited to a particular set of
higher-order functions, and you cannot arbitrary birth functions
(e.g.  the moronicity of lisp's macros).

The force of this particular formalism is that it makes it more
subject to mathematical analysis (and thus makes it more powerful and
flexible), similar to for example to the clear separation of features
in 2nd order logic from first order logic. Wikipedia said it best,
quote:

«This restriction means that functions in FP are a module (generated
by the built-in functions) over the algebra of functional forms, and
are thus algebraically tractable. For instance, the general question
of equality of two functions is equivalent to the halting problem, and
is undecidable, but equality of two functions in FP is just equality
in the algebra, and thus (Backus imagines) easier.»

«Even today, many users of lambda style languages often misinterpret
Backus' function-level approach as a restrictive variant of the lambda
style, which is a de facto value-level style. In fact, Backus would
not have disagreed with the 'restrictive' accusation: he argued that
it was precisely due to such restrictions that a well-formed
mathematical space could arise, in a manner analogous to the way
structured programming limits programming to a restricted version of
all the control-flow possibilities available in plain, unrestricted
unstructured programs.»

--------------------------------

This thread, illustrates, how often comp lang fanatics propagate
patently false things, in their fanaticism. This, includes those
lispers who are regulars at comp.lang.lisp. (other similar issues, is
how lisp syntax is regular, and how lisp are adept at lisp
manipulation)

  Xah
∑ http://xahlee.org/

☄
From: namekuseijin
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <5b017067-a0ec-4082-b4f1-88ec0442cb27@13g2000yql.googlegroups.com>
Codd and Backus were brilliant men, but their ideas are not that much
practical, being set more like a high standard against which to
measure practical implementations of crippled down versions of said
ideas.
From: Pillsy
Subject: Re: John Backus and function level programming
Date: 
Message-ID: <7a2ed3e9-c668-4471-a661-a7f87b9ac3ca@c11g2000yqj.googlegroups.com>
On Mar 3, 10:47 pm, Xah Lee <······@gmail.com> wrote:
[...]
> Lisp does not do functional level programing. Can't. Nor does almost
> all the well known functional langs such as Ocaml, Haskell,
> Mathematica.
[...]
> hard to summarize in one sentence... but basically like functional
> programing but with one characteristic formalism that sets it apart,
> namely: creation of functions are limited to a particular set of
> higher-order functions, and you cannot arbitrary birth functions
> (e.g.  the moronicity of lisp's macros).

This is a silly objection. There are quite a few languages where it's
not all that hard to limit yourself to a small set of operators via
one namespacing mechanism or another. Common Lisp's packages (or
Mathematica's virtually identical "contexts") would certainly be
adequate for the task.

And yeah, you don't need to have DEFMACRO in your function-level
programming package either. Why would you?

Cheers,
Pillsy