5 ms·

Is it possible to write c...r in lisp, for any combination of letters a and d?

13 points by DaveKruglinsky 17y ago

Hello, lispers! Is it posible to write macro (or something) in lisp, such that any 'call' which has shape like (caddaddr x) automatically expands into (car (cdr (cdr (car (cdr (cdr x)))))) Naturally, this should work for any possible combination of letters a and d. Is that possible?

dfox 17y ago
All reasonably effective ways of doing this involve hacking ugly special case into compiler and evaluator. But as purely academic exercise this can be done (for common lisp) by handling undefined-function condition and invoking appropriate restart (which is unfortunately implementation-specific).
- mahmud 17y ago
  Why? I already wrote the stub code for this in another reply. He just needs a define-deconstructor macro. Any C[A|D]+R function that isn't already defined by CL can be defined as a macro. [Edit: I see that he said any call .. well, he will have to define the function before hand before he calls it. That's just common sense. Apologies dfox.]
smanek 17y ago
I could write a function that automatically defines functions of the form you want, but it would have to define them one at a time. The problem is that it could only define a finite number of functions. It's pretty straightforward to do what you want by writing a reader macro, but then you have to prefix your sexp with some special macro character. If the prefix is a deal breaker there may be some deep read-macro voodoo that could do what you want but, but before doing research, I have to ask the obvious question: "Why?". Incidentally, pg's On Lisp has a decent intro to reader macros (http://www.bookshelf.jp/texi/onlisp/onlisp_18.html http://www.bookshelf.jp/texi/onlisp/onlisp_18.html)
- mahmud 17y ago
  Code or it didn't happen ;-) Come'on, it's a nice trivia question. Let's light this joint up with parentheses folks! Schemers, Clojeristas ..
- DaveKruglinsky 17y ago
  Why? Paul Graham says that "Programming languages teach us not to want what they cannot provide". I'm just curious if this is the case with lisp and c[a|d]+r
  - mahmud 17y ago
    No it's not. If there is anything Lisp provides out of the box, it's support for non-builtin language features. A friken paradox, enjoy it! :-)
    - philh 17y ago
      So far there's only one solution: "this can be done (for common lisp) by handling undefined-function condition and invoking appropriate restart (which is unfortunately implementation-specific)." Which makes it sound like there is in fact no way to do this in standard CL, to say nothing of other lisps. Untested perl code to do this (taking a cons to be a [car, cdr] array reference): AUTOLOAD { unless ($AUTOLOAD =~ m/::c([ad]{1,})r$/) { die "Attempted to call undefined function $AUTOLOAD"; } my $ads = $1; my $cons = shift; while (my $c = chop $ads) { $cons = $cons->[$c eq 'a' ? 0 : 1]; } return $cons; } Example of a situation this feature might be useful: "I have this object with lots of properties which I don't necessarily know what they are. How do I define getter/setter methods on them?"
      - bvttf 17y ago
        More appropriately, there's no standard way to do this with CL. One might ask the same about threads. What are threads? We just don't know.
        mahmud 17y ago
        What do you mean there is no standard way to do this? There is a MetaObject Protocol which is supported by most platforms, and for those that don't have it, there is the widely portable CloserMOP. Threads are not "standard" but the last thread-less Common Lisp just got them this month. Every maintained Common Lisp implementation today has Threads; and all support Bordeaux-Threads. Show me a single mainstream language where threads are "standardized" other than Java?
mahmud 17y ago
(defun charfn (char) "maps a character to a function" (case char ((or #\A #\a) #'car) ((or #\D #\d) #'cdr) (t (error "unknown character-function type ~a" char)))) (defun fn-list (decon-name) (mapcar #'charfn (butlast (rest (coerce (symbol-name decon-name) 'list))))) ;;; syntax (defmacro defdecon (fn-name) `(defun ,fn-name (args) (funcall (arnesi:compose ,@(fn-list fn-name)) args))) ;;; play with it ;; test cases (funcall (arnesi:compose 'car) (list 1 2 3)) => 1 (funcall (arnesi:compose 'caar) (list (list 1) 2 3)) => 1 ;; the base works, let's test the syntax; NB, redefining a builtin will not work (defdecon caaaaar) ; define first (caaaaar (list (list (list (list (list 1 #\c) #\b) #\a) 2) 3)) ==> 1 :-) just off the top of my head in 8 minutes. make it to a reader macro if you so wish. [Edit: cat >> nfs://cltl3.alu.org/todo.txt * CASE with custom tests * COMP^H^H^H^HArnesi FFS! ]
rincewind 17y ago
In Clojure: possible but ugly. Use destructuring in production instead. (defn make-xrs [n] (if (= n 0) {"ar" first, "dr" rest} (let [last (make-xrs (dec n))] (into last (for [[name fun] last [name2 fun2] {"d" rest "a" first}] [(str name2 name) (comp fun2 fun)]))))) (for [[name fun] (make-xrs 10)] (eval `(def ~(symbol (str "c" name)) ~fun)))
- philh 17y ago
  That lets you write c[ad]{1,10}r, or c[ad]{1,n}r with O(2^n) initialisation time. OP wanted to be able to write c[ad]+r. Also, that eval could be replaced with (untested) (intern *ns* (symbol (str "c" name)) fun)
lnostdal 17y ago
quick and dirty; i'm not even sure it is correct: (defmacro blah (arg body) (with-input-from-string (stream (reverse (string arg))) (dolist (char (loop :for char = (read-char stream nil) :while (and char (or (char= char #\A) (char= char #\D) (error "BLAH: Only A or D is accepted."))) :collect char)) (case char (#\A (setf body `(car ,body))) (#\D (setf body `(cdr ,body))))) body)) CL-USER> (let ((data '((42)))) (blah aa data)) 42 CL-USER> ..manipulate the reader using read-macros (see TCR's new named-readtables library) if you want anything fancier. check out this btw.; http://groups.google.com/group/comp.lang.lisp/msg/d2425c92cef7465c http://groups.google.com/group/comp.lang.lisp/msg/d2425c92ce... edit: the web still doesn't work as i want it to work .. i'm not going to bother fixing the whitespace etc. here
jashkenas 17y ago
Here it is in Ruby. LISP_METH = /^c[ad]+r$/ def method_missing(name, *args) meth = name.to_s raise NoMethodError, "undefined method '#{name}'" unless meth =~ LISP_METH list = args.first calls = meth.split('')[1..-2].reverse calls.each {|call| list = (call == 'a' ? list.first : list[1..-1]) } list end cadr [1,2,3] # => 2 caaddddr [1,2,3,4,[9,8,7]] # => 9 cadadr [1,[9,[100],8,7],3,4] # => 100
neonscribe 17y ago
If I recall correctly, UTLISP on the CDC-6600 did this up to six levels. UTLISP stored 3 18-bit pointers in a 60 bit word, plus flag bits. The three pointers were called the CAR, CDR and CSR. CONS only took two arguments, but you could set the CDR using RPLACS (analogous to RPLACA and RPLACD). All 729 functions C[ADS]{1,6}R were available, but not by having 729 actual function definitions, which would have been a significant waste of address space and core in those days. The undefined function handler would check the name of the function being called and construct the definition on the fly for interpreted code, while the compiler would do something similar during compilation. This trick dates back to the 1970s or possibly even the late 60s. I think it was also used in other early Lisp implementations.

dfox 17y ago

All reasonably effective ways of doing this involve hacking ugly special case into compiler and evaluator. But as purely academic exercise this can be done (for common lisp) by handling undefined-function condition and invoking appropriate restart (which is unfortunately implementation-specific).

mahmud 17y ago
Why? I already wrote the stub code for this in another reply. He just needs a define-deconstructor macro. Any C[A|D]+R function that isn't already defined by CL can be defined as a macro. [Edit: I see that he said any call .. well, he will have to define the function before hand before he calls it. That's just common sense. Apologies dfox.]

smanek 17y ago

I could write a function that automatically defines functions of the form you want, but it would have to define them one at a time. The problem is that it could only define a finite number of functions. It's pretty straightforward to do what you want by writing a reader macro, but then you have to prefix your sexp with some special macro character. If the prefix is a deal breaker there may be some deep read-macro voodoo that could do what you want but, but before doing research, I have to ask the obvious question: "Why?". Incidentally, pg's On Lisp has a decent intro to reader macros (http://www.bookshelf.jp/texi/onlisp/onlisp_18.html http://www.bookshelf.jp/texi/onlisp/onlisp_18.html)

mahmud 17y ago
Code or it didn't happen ;-) Come'on, it's a nice trivia question. Let's light this joint up with parentheses folks! Schemers, Clojeristas ..
DaveKruglinsky 17y ago
Why? Paul Graham says that "Programming languages teach us not to want what they cannot provide". I'm just curious if this is the case with lisp and c[a|d]+r
- mahmud 17y ago
  No it's not. If there is anything Lisp provides out of the box, it's support for non-builtin language features. A friken paradox, enjoy it! :-)
  - philh 17y ago
    So far there's only one solution: "this can be done (for common lisp) by handling undefined-function condition and invoking appropriate restart (which is unfortunately implementation-specific)." Which makes it sound like there is in fact no way to do this in standard CL, to say nothing of other lisps. Untested perl code to do this (taking a cons to be a [car, cdr] array reference): AUTOLOAD { unless ($AUTOLOAD =~ m/::c([ad]{1,})r$/) { die "Attempted to call undefined function $AUTOLOAD"; } my $ads = $1; my $cons = shift; while (my $c = chop $ads) { $cons = $cons->[$c eq 'a' ? 0 : 1]; } return $cons; } Example of a situation this feature might be useful: "I have this object with lots of properties which I don't necessarily know what they are. How do I define getter/setter methods on them?"
    - bvttf 17y ago
      More appropriately, there's no standard way to do this with CL. One might ask the same about threads. What are threads? We just don't know.
      - mahmud 17y ago
        What do you mean there is no standard way to do this? There is a MetaObject Protocol which is supported by most platforms, and for those that don't have it, there is the widely portable CloserMOP. Threads are not "standard" but the last thread-less Common Lisp just got them this month. Every maintained Common Lisp implementation today has Threads; and all support Bordeaux-Threads. Show me a single mainstream language where threads are "standardized" other than Java?

mahmud 17y ago

(defun charfn (char) "maps a character to a function" (case char ((or #\A #\a) #'car) ((or #\D #\d) #'cdr) (t (error "unknown character-function type ~a" char)))) (defun fn-list (decon-name) (mapcar #'charfn (butlast (rest (coerce (symbol-name decon-name) 'list))))) ;;; syntax (defmacro defdecon (fn-name) `(defun ,fn-name (args) (funcall (arnesi:compose ,@(fn-list fn-name)) args))) ;;; play with it ;; test cases (funcall (arnesi:compose 'car) (list 1 2 3)) => 1 (funcall (arnesi:compose 'caar) (list (list 1) 2 3)) => 1 ;; the base works, let's test the syntax; NB, redefining a builtin will not work (defdecon caaaaar) ; define first (caaaaar (list (list (list (list (list 1 #\c) #\b) #\a) 2) 3)) ==> 1 :-) just off the top of my head in 8 minutes. make it to a reader macro if you so wish. [Edit: cat >> nfs://cltl3.alu.org/todo.txt * CASE with custom tests * COMP^H^H^H^HArnesi FFS! ]

rincewind 17y ago

In Clojure: possible but ugly. Use destructuring in production instead. (defn make-xrs [n] (if (= n 0) {"ar" first, "dr" rest} (let [last (make-xrs (dec n))] (into last (for [[name fun] last [name2 fun2] {"d" rest "a" first}] [(str name2 name) (comp fun2 fun)]))))) (for [[name fun] (make-xrs 10)] (eval `(def ~(symbol (str "c" name)) ~fun)))

philh 17y ago
That lets you write c[ad]{1,10}r, or c[ad]{1,n}r with O(2^n) initialisation time. OP wanted to be able to write c[ad]+r. Also, that eval could be replaced with (untested) (intern *ns* (symbol (str "c" name)) fun)

lnostdal 17y ago

quick and dirty; i'm not even sure it is correct: (defmacro blah (arg body) (with-input-from-string (stream (reverse (string arg))) (dolist (char (loop :for char = (read-char stream nil) :while (and char (or (char= char #\A) (char= char #\D) (error "BLAH: Only A or D is accepted."))) :collect char)) (case char (#\A (setf body `(car ,body))) (#\D (setf body `(cdr ,body))))) body)) CL-USER> (let ((data '((42)))) (blah aa data)) 42 CL-USER> ..manipulate the reader using read-macros (see TCR's new named-readtables library) if you want anything fancier. check out this btw.; http://groups.google.com/group/comp.lang.lisp/msg/d2425c92cef7465c http://groups.google.com/group/comp.lang.lisp/msg/d2425c92ce... edit: the web still doesn't work as i want it to work .. i'm not going to bother fixing the whitespace etc. here

jashkenas 17y ago

Here it is in Ruby. LISP_METH = /^c[ad]+r$/ def method_missing(name, *args) meth = name.to_s raise NoMethodError, "undefined method '#{name}'" unless meth =~ LISP_METH list = args.first calls = meth.split('')[1..-2].reverse calls.each {|call| list = (call == 'a' ? list.first : list[1..-1]) } list end cadr [1,2,3] # => 2 caaddddr [1,2,3,4,[9,8,7]] # => 9 cadadr [1,[9,[100],8,7],3,4] # => 100

neonscribe 17y ago

If I recall correctly, UTLISP on the CDC-6600 did this up to six levels. UTLISP stored 3 18-bit pointers in a 60 bit word, plus flag bits. The three pointers were called the CAR, CDR and CSR. CONS only took two arguments, but you could set the CDR using RPLACS (analogous to RPLACA and RPLACD). All 729 functions C[ADS]{1,6}R were available, but not by having 729 actual function definitions, which would have been a significant waste of address space and core in those days. The undefined function handler would check the name of the function being called and construct the definition on the fly for interpreted code, while the compiler would do something similar during compilation. This trick dates back to the 1970s or possibly even the late 60s. I think it was also used in other early Lisp implementations.