(defmacro my-if (test then &optional (else nil))
(let ((b (gensym)))
`(let ((,b ,test))
(or (and ,b ,then)
(and (not ,b) ,else)))))
Some of the inspiration came from a digital logic course I once took
which reduced everything in a computer to several fundamental gates.
I know it's trivial, but I find this a rather eloquent answer to what
makes Lisp special.
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
Can you come up with an implementation for `or' in an `if'-less Lisp?
Cheers,
--ag
--
Artie Gold -- Austin, Texas
http://it-matters.blogspot.com (new post 12/5)
http://www.cafepress.com/goldsays
> The CLHS states that IF is a Special Operator. But what if there was
> no IF? Don't ask my why I was thinking about this. Just for fun, I
> decided to see if I could use the Macros AND and OR along with the
> function NOT to see if I could emulate IF:
>
> (defmacro my-if (test then &optional (else nil))
> (let ((b (gensym)))
> `(let ((,b ,test))
> (or (and ,b ,then)
> (and (not ,b) ,else)))))
That's neat. Just note that IF is necessarily a special operator.
OR will be defined in terms of IF. (macroexpand '(or a b)) to see.
Regards,
Adam
Justin Dubs
And given that 'and' is also implemented using if, try it without and.
In fact, try it without any control-type forms at all.
(I'm not sure, but it just might be possible, if somewhat hair-raising)
> Artie Gold wrote:
>> Can you come up with an implementation for `or' in an `if'-less Lisp?
> (or a b) == (not (and (not a) (not b)))
Only in logic. Something along these lines ought to do the job, though.
(defmacro or* (a b)
(let ((a* (gensym))
(b* (gensym))
(table (gensym)))
`(let* ((,a* ,a)
(,b* ,b)
(,table (list (cons '(t) ,a*)
(cons '(t . t) ,a*)
(cons '(nil . t) ,b*))))
(cdr (assoc (cons (not (not ,a*)) (not (not ,b*))) ,table :test #'equal))
)))
CL-USER> (or* 'a 'b)
A
CL-USER> (or* nil 'b)
B
CL-USER> (or* nil nil)
NIL
'as
> (defmacro my-if (test then &optional (else nil))
> (let ((b (gensym)))
> `(let ((,b ,test))
> (or (and ,b ,then)
> (and (not ,b) ,else)))))
>
This macro doesn't deal properly with multiple values owing to the way
OR deals with them.
CL-USER 5 > (my-if t (values 2 3) nil)
2
CL-USER 6 > (if t (values 2 3) nil)
2
3
My question would be "why"? It is a speed issue or simplicity? Have
past implementations done it the other way around? Also, sources on the
web that discuss pure Lisp or the 7 needed symbols, always use COND
instead of IF. If COND is described from IF in Lisp implementations,
why isn't IF one of those symbols and not COND?
Jeff M.
Don't forget that OR is used for evaluation control, not just for
computing a boolean result. It must keep evaluating its arguments left
to right until it encounters one which is other than NIL. That value is
then propagated as the result of the OR, and no additional arguments
are evaluated.
As to Artie's question, my implementation would just be:
(defmaro my-or (&body args) `(or ,@args))
He said IF-less Lisp; he didn't say OR-less. :)
For historical reasons. The first lisp was defined with COND, not with IF.
;;****************************************************************************
;;FILE: aim-8.lisp
;;LANGUAGE: Common-Lisp
;;SYSTEM: Common-Lisp
;;USER-INTERFACE: NONE
;;DESCRIPTION
;;
;; Implements the LISP described in AIM-8 in Common-Lisp.
;; Usage: (load "aim-8.lisp")
;; (aim-8:repl)
;; Then at the aim-8 prompt, you have LISP, plus:
;; (DEFINE name sexp) corresponding to =
;; (RELOAD) to reload aim-8 if you edit it.
;; (DUMP-ENVIRONMENT) to dump the defined symbols.
;; (LOAD "path") to load an aim-8 source. Try "aim-8.aim-8".
;;
;;AUTHORS
;; <PJB> Pascal Bourguignon <p...@informatimago.com>
;;MODIFICATIONS
;; 2004-10-24 <PJB> Created.
;;BUGS
;;LEGAL
;; GPL
;;
;; Copyright Pascal Bourguignon 2004 - 2004
;;
;; This program is free software; you can redistribute it and/or
;; modify it under the terms of the GNU General Public License
;; as published by the Free Software Foundation; either version
;; 2 of the License, or (at your option) any later version.
;;
;; This program is distributed in the hope that it will be
;; useful, but WITHOUT ANY WARRANTY; without even the implied
;; warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
;; PURPOSE. See the GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public
;; License along with this program; if not, write to the Free
;; Software Foundation, Inc., 59 Temple Place, Suite 330,
;; Boston, MA 02111-1307 USA
;;****************************************************************************
;;
;; AIM-8 -- 23 MARCH 1959 -- J. MCCARTHY
;; (IN-PACKAGE "COMMON-LISP-USER")
;; (defpackage "LISP-1"
;; (:use "COMMON-LISP")
;; (:export "DEFINE" "LAMBDA" "LABEL"
;; "COND" "AND" "OR" "NOT"
;; "COMBINE" "FIRST" "REST"
;; "NULL" "ATOM" "EQ"
;; "NIL" "T" "QUOTE"));;LISP-1
;;(funcall (LABEL fact (lambda (x) (cond ((= 1 x) 1) (t (* x (fact (1- x))))))) 6)
(DEFPACKAGE "AIM-8"
(:USE "COMMON-LISP")
(:EXPORT "REPL")
(:DOCUMENTATION
"Implements the lisp of AIM-8 -- 23 MARCH 1959 -- J. McCarthy"));;AIM-8
(IN-PACKAGE "AIM-8")
(DEFPACKAGE "AIM-8-USER"
(:USE)
(:IMPORT-FROM "AIM-8"
"DEFINE" "LAMBDA" "LABEL"
"COND" "COMBINE" "FIRST" "REST"
"NULL" "ATOM" "EQ" "NIL" "T" "QUOTE"));;AIM-8-USER
(DEFPARAMETER *ENVIRONMENT* (MAKE-HASH-TABLE :TEST (FUNCTION EQ)))
(DEFMACRO DEF (NAME) `(GETHASH ,NAME *ENVIRONMENT*))
(DEFUN %BOUNDP (NAME) (MULTIPLE-VALUE-BIND (VAL BND) (DEF NAME)
(DECLARE (IGNORE VAL)) BND))
(DEFMACRO DEFINE (NAME VALUE) `(SETF (GETHASH ',NAME *ENVIRONMENT*) ',VALUE))
(DEFUN FDEFINE (NAME VALUE) (SETF (GETHASH NAME *ENVIRONMENT*) VALUE))
(DEFINE NIL ())
(DEFINE F ())
(DEFINE T T)
(DEFINE AND (LAMBDA (A B) (COND (A (COND (B T) (T NIL))) (T NIL))))
(DEFINE OR (LAMBDA (A B) (COND (A T) (B T) (T NIL))))
(DEFINE NOT (LAMBDA (A) (COND (A NIL) (T NIL))))
(DEFINE MAPLIST
(LAMBDA (X F)
(COND ((NULL X) NIL)
(T (COMBINE (F X) (MAPLIST (REST X) F))))))
(DEFINE SUBST
(LAMBDA (X Y A)
(COND ((NULL A) NIL)
((ATOM A) (COND ((EQ Y A) X) (T A)))
(T (COMBINE (SUBST X Y (FIRST A))
(SUBST X Y (REST A))))
)));;SUBST
(DEFUN %SUBST (X Y A)
(COND ((NULL A) NIL)
((ATOM A) (COND ((EQ Y A) X) (T A)))
(T (CONS (%SUBST X Y (FIRST A)) (%SUBST X Y (REST A))))))
(DEFUN %SUBSQ (X Y Z)
(COND ((NULL Z) NIL)
((ATOM Z) (COND ((EQ Y Z) X) (T Z)))
((EQ (FIRST Z) 'QUOTE) Z)
(T (CONS (%SUBSQ X Y (FIRST Z)) (%SUBSQ X Y (REST Z))))));;%SUBSQ
(DEFUN %EVCON (C)
(COND ((%EVAL (FIRST (FIRST C))) (%EVAL (FIRST (REST (FIRST C)))))
(T (%EVCON (REST C)))))
(DEFUN %EVLAM (VARS EXP ARGS)
(COND ((NULL VARS) (%EVAL EXP))
(T (%EVLAM (REST VARS) (%SUBSQ (FIRST ARGS) (FIRST VARS) EXP)
(REST ARGS)))))
(DEFUN %APPLY (F ARGS) (%EVAL (CONS F ARGS)))
(DEFUN %EVAL (E)
(COND
;; begin extensions:
((ATOM E) (COND ((%BOUNDP E) (DEF E))
(T (ERROR "Undefined: ~A" (FIRST E)))))
;; end extensions.
(T (CASE (FIRST E)
((NULL) (NULL (%EVAL (FIRST (REST E)))))
((ATOM) (ATOM (%EVAL (FIRST (REST E)))))
((QUOTE) (FIRST (REST E)))
((EQ) (EQ (%EVAL (FIRST (REST E)))
(%EVAL (FIRST (REST (REST E))))))
((COMBINE) (CONS (%EVAL (FIRST (REST E)))
(%EVAL (FIRST (REST (REST E))))))
((FIRST) (FIRST (%EVAL (FIRST (REST E)))))
((REST) (REST (%EVAL (FIRST (REST E)))))
((COND) (%EVCON (REST E)))
;; begin extensions:
((LOAD) (LOAD (%EVAL (FIRST (REST E)))))
((PRINT) (PRINT (%EVAL (FIRST (REST E)))))
((READ) (READ))
(OTHERWISE
(COND
((ATOM (FIRST E))
(COND ((%BOUNDP (FIRST E)) (%APPLY (DEF (FIRST E)) (REST E)))
(T (ERROR "Undefined: ~A" (FIRST E)))))
;; end extensions.
(T (CASE (FIRST (FIRST E))
((LAMBDA) (%EVLAM (FIRST (REST (FIRST E)))
(FIRST (REST (REST (FIRST E))))
(REST E)))
((LABEL) (%EVAL (CONS (%SUBST (FIRST E)
(FIRST (REST (FIRST E)))
(FIRST (REST (REST (FIRST E)))))
(REST E))))
(OTHERWISE (ERROR "Invalid: ~A" (FIRST E)))))))))));;%EVAL
(DEFUN HELP ()
(FORMAT T "~&You've got:
DEFINE LAMBDA LABEL
COND AND OR NOT COMBINE FIRST REST
NULL ATOM EQ NIL T QUOTE
QUIT"));;HELP
(DEFUN REPL ()
(LET ((*PACKAGE* (FIND-PACKAGE "AIM-8")))
(HELP)
(LOOP
(TERPRI)
(PRINC "AIM-8> ")
(HANDLING-ERRORS
(LET ((SEXP (READ)))
(COND
((EQUAL SEXP '(QUIT))
(FORMAT T "GOOD BYE") (RETURN-FROM REPL))
((EQUAL SEXP '(RELOAD))
(LOAD "aim-8") (REPL) (RETURN-FROM REPL))
((EQUAL SEXP '(DUMP-ENVIRONMENT))
(FORMAT T "~:{~16@A = ~A~%~}"
(LET ((RES '()))
(MAPHASH (LAMBDA (K V) (PUSH (LIST K V) RES))
*ENVIRONMENT*) RES)))
((AND (LISTP SEXP) (EQ (FIRST SEXP) 'DEFINE))
(FDEFINE (SECOND SEXP) (THIRD SEXP))
(FORMAT T "~A" (SECOND SEXP)))
(T
(FORMAT T "~S" (%EVAL SEXP))))))))
(TERPRI)
(VALUES));;REPL
;; (in-package "COMMON-LISP-USER")
;; (aim-8:repl)
#||
(define FF (lambda (X) (COND ((OR (NULL X) (ATOM X)) X) (T (FF (FIRST X))))))
(FF (quote (A B)))
;; A
(FF (quote ((A B) C)))
;; A
(FF (quote (((A) B) C)))
;; A
(ff '(()()(()()())((((a)))b)))
;; NIL
(define ff1 (lambda (X) (COND ((OR (NULL X) (ATOM X)) X)
(T (cond ((FF1 (FIRST X)) (FF1 (FIRST X)))
(t (FF1 (REST X))))))))
(ff1 '(()()(()()())((((a)))b)))
A
v||#
#||
(SUBST (quote TOTO) (quote X) (quote (COND ((EQ X A) A) (T NIL))))
;; (COND ((EQ TOTO A) A) (T NIL))
||#
#||
(define diff
(lambda (y x)
(cond
((atom y)
(cond ((eq y x) (quote one))
(t (quote zero))))
((eq (first y) (quote plus))
(combine (quote plus) (maplist (rest y) (lambda (a) (diff (first a) x)))))
((eq (first y) (quote times))
(combine (quote plus)
(maplist
(rest y)
(lambda (a) (combine (quote times)
(maplist
(rest y)
(lambda (w) (cond ((not (eq a w)) (first w))
(t (diff (first w) x))
)))))))))));;diff
(diff (quote (plus (times 2 x) (times 2 x x))) (quote x))
;; (plus (plus (times zero x) (times 2 one))
;; (plus (times zero x x) (times 2 one x) (times 2 x one)))
|#
;;;; aim-8.lisp -- -- ;;;;
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
If nothing else, for brain-tickling fun.
A language consisting of two rewrite rules called "combinators", where
the two rules are conventionally called S and K, is turing-complete:
(defun S (x y z)
(funcall (funcall x z)
(funcall y z)))
(defun K (x y) x)
You can use S and K to implement anything computable, including IF
and, slightly brain-bendingly, the Y combinator, which implements recursion.
The above may not be quite correct; I'm rather sick at the moment, and
my brain is not working up to even its normal slow capacity. Google for
"combinators" if this sort of thing pushes your fun buttons.
> That's neat. Just note that IF is necessarily a special operator.
> OR will be defined in terms of IF. (macroexpand '(or a b)) to see.
That's true. The macro is quite clever also:
CL-USER> (macroexpand-1 '(or 1))
1
T
CL-USER> (macroexpand-1 '(or (> 4 (random 10)) "more" "less"))
(LET ((#:G75 (> 4 (RANDOM 10)))) (IF #:G75 #:G75 (IF (SETQ #:G75
"more") #:G75 "less")))
T
CL-USER> (macroexpand-1 '(and (> 4 (random 10)) "more" "less"))
(IF (> 4 (RANDOM 10)) (AND "more" "less"))
T
At the machine level, the clever bit is whatever instruction is used
for "Jump Zero" or "Jump Not Zero". In the hardware, you are back to
AND, OR, and NOT. Well almost.
IF is a good operator to place in the Special Operator class.
I didn't think of that test case. I don't have a fix off the top of
my head for it. Maybe that's what's special about IF.
On the face of it, it's not obvious why the VALUES don't propogate up
the stack frame:
CL-USER> (macroexpand '(my-if t (values 1 2) nil))
(LET ((#:G77 T)) (OR (AND #:G77 (VALUES 1 2)) (AND (NOT #:G77) NIL)))
T
CL-USER> (macroexpand '(or (and t (values 1 2))))
(IF T (AND (VALUES 1 2)))
T
CL-USER> (and (values 1 2))
1
2
CL-USER> (or (and t (values 1 2)))
1
2
The problem is that `b' gets evaluated unconditionally -- which is not
what you want.
HTH,
Unfortunatly this fails the critical "destroy-the-world" test:
CL-USER> (or t (destroy-the-world))
T
CL-USER> (or* t (destroy-the-world))
World destroyed!
[Condition of type SIMPLE-ERROR]
(Also, the built-in AND and OR can take more than two operators.)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Unfortunatly this fails the critical "destroy-the-world" test:
CL-USER> (or t (destroy-the-world))
T
CL-USER> (or* t (destroy-the-world))
World destroyed!
[Condition of type SIMPLE-ERROR]
(Also, the built-in AND and OR can take more than two arguments.)
> On the face of it, it's not obvious why the VALUES don't propogate up
> the stack frame:
It's due to the behaviour of OR with multiple values (which are only
returned from the last case of the OR)
CL-USER 6 > (OR (AND t (VALUES 2 3)) (AND (NOT t) NIL))
2
CL-USER 7 > (OR (AND t (VALUES 2 3)) )
2
3
Argh, how embarrassing -- should have known better than to post anything in a
state of insomnia. Anyway here we go again (still haven't had much sleep, so
for saftey critical code best stick with the OR that comes supplied with your
lisp version):
(defmacro or* (a b)
(let ((a* (gensym))
(bf* (gensym))
(b* (gensym))
(table (gensym)))
`(let* ((,a* ,a)
(,bf* (lambda () ,b))
(,table (list (cons nil (lambda () ,a*))
(cons t (lambda () (funcall ,bf*))))))
(funcall (cdr (assoc (not ,a*) ,table)))
)))
(defmacro with-results (() &body body)
(cons 'list (mapcar (lambda (form) `(list ',form '=> ,form))
body)))
(let ((a 1)
(b 0))
(with-results ()
(or* (incf a) (/ (incf b) 0))
(or* nil (incf b))
(or* nil nil)))
=>(((OR* (INCF A) (/ (INCF B) 0)) => 2)
((OR* NIL (INCF B)) => 1)
((OR* NIL NIL) => NIL))
> (Also, the built-in AND and OR can take more than two arguments.)
Sure, but these are left as an excersise to the more devoted reader (hence
"along these lines").
'as
David Steuber schrieb:
> Some of the inspiration came from a digital logic course I once took
> which reduced everything in a computer to several fundamental gates.
> I know it's trivial, but I find this a rather eloquent answer to what
> makes Lisp special.
For more inspiration have a look at this (3.1)
...............(copy&paste).................
The fifth chapter of my book GENE EXPRESSION PROGRAMMING: MATHEMATICAL
MODELING BY AN ARTIFICIAL INTELLIGENCE is now available to browse online
at:
http://www.gene-expression-programming.com/gep/Books/index.asp
Chapter 5: DESIGN OF NEURAL NETWORKS
1. Genes with multiple domains for neural network simulation
2. Special search operators
2.1. Domain-specific transposition
2.2. Intragenic two-point recombination
2.3. Direct mutation of weights and thresholds
3. Solving problems with GEP neural networks
............
3.1. Neural network for the exclusive-or problem
............
3.2. Neural network for the 6-multiplexer
4. Evolutionary dynamics of GEP-nets
(Author at:)
GEP: Mathematical Modeling by an Artificial Intelligence
http://www.gene-expression-programming.com/gep/Books/index.asp
Modeling Software
http://www.gepsoft.com/gepsoft/
...................(end).............
Found in comp.ai.genetic
lin
Pascal Bourguignon schrieb:
> ;;****************************************************************************
> ;;FILE: aim-8.lisp
> ;;LANGUAGE: Common-Lisp
> ;;SYSTEM: Common-Lisp
> ;;USER-INTERFACE: NONE
> ;;DESCRIPTION
Thank You. I missed this.
lin
(defmacro mv-or (&rest forms)
(cond
((null forms) ())
((null (cdr forms)) (car forms))
(t (let ((sym (gensym)))
`(let ((,sym (multiple-value-list ,(car forms))))
(if (car ,sym)
(values-list ,sym)
(mv-or ,@(cdr forms))))))))
I have a small question. Why did you write your code all in caps? Do you
still write it that way? Why? (oops, make that small *questions*)
Merry christmas,
--
LuĂs Oliveira
Reply-To: luismbo (@) netcabo (.) pt
Equipa Portuguesa do Translation Project
http://www2.iro.umontreal.ca/~pinard/po/registry.cgi?team=pt
> Pascal Bourguignon skribis:
> > (DEFUN HELP ()
> > (FORMAT T "~&You've got:
> > DEFINE LAMBDA LABEL
> > COND AND OR NOT COMBINE FIRST REST
> > NULL ATOM EQ NIL T QUOTE
> > QUIT"));;HELP
>
> I have a small question. Why did you write your code all in caps? Do
> you still write it that way? Why? (oops, make that small questions)
>
Just a guess, but I'd bet that was copied/pasted from a document and
not hand-typed :)
Jeff M.
--
http://www.retrobyte.org
mailto:mas...@gmail.com
> ourguignon skribis:
> > (DEFUN HELP ()
> > (FORMAT T "~&You've got:
> > DEFINE LAMBDA LABEL
> > COND AND OR NOT COMBINE FIRST REST
> > NULL ATOM EQ NIL T QUOTE
> > QUIT"));;HELP
>
> I have a small question. Why did you write your code all in caps? Do you
> still write it that way? Why? (oops, make that small *questions*)
You quoted the wrong part:
> ;; AIM-8 -- 23 MARCH 1959 -- J. MCCARTHY
^^^^
--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962:DO20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/