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

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

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?

View on HN

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).

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.]

  (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!

]

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.

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)

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 ..

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

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! :-)

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?"

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.

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?

You're over-thinking this. My comment was a response to the idea that every lisp can that but there's no single standard.

My awkward phrasing was a reference to about 1:53 in this: http://www.youtube.com/watch?v=bCWA7uevo_Q

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)."

Before you go far and wide on speculation alone, you might stop and reread what has been posted so far, again. Both me and lnostdal submitted working CL solutions.

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?"

  ;; if you know the slot names
  (slot-value object 'slot-name) ==> value
  (setf (slot-value object 'slot-name) new-value)

  ;; if you don't.
  ;; let's define a class hierarchy first
  CL-USER> (defclass foo () ((a) (b)))
  #<STANDARD-CLASS FOO>
  CL-USER> (defclass bar (foo) ((c) (d)))
  #<STANDARD-CLASS BAR>
  CL-USER> (defclass baz (bar) ((e) (f)))
  #<STANDARD-CLASS BAZ>
  
  ;; use COMPUTE-SLOTS to get the class's slots
  CL-USER> (closer-mop:compute-slots (find-class 'baz))
  (#<STANDARD-EFFECTIVE-SLOT-DEFINITION A #x1A0F62C5>
   #<STANDARD-EFFECTIVE-SLOT-DEFINITION B #x1A0F6305>
   #<STANDARD-EFFECTIVE-SLOT-DEFINITION C #x1A0F6345>
   #<STANDARD-EFFECTIVE-SLOT-DEFINITION D #x1A0F6385>
   #<STANDARD-EFFECTIVE-SLOT-DEFINITION E #x1A0F63C5>
   #<STANDARD-EFFECTIVE-SLOT-DEFINITION F #x1A0F6405>)

   ;; if you have an object and not a class, do the same
   CL-USER> (closer-mop:compute-slots (class-of (make-instance 'baz)))
   (#<STANDARD-EFFECTIVE-SLOT-DEFINITION A #x1A1202A1>
    #<STANDARD-EFFECTIVE-SLOT-DEFINITION B #x1A1202E1>
    #<STANDARD-EFFECTIVE-SLOT-DEFINITION C #x1A120321>
    #<STANDARD-EFFECTIVE-SLOT-DEFINITION D #x1A120361>
    #<STANDARD-EFFECTIVE-SLOT-DEFINITION E #x1A1203A1>
    #<STANDARD-EFFECTIVE-SLOT-DEFINITION F #x1A1203E1>)

I don't think so. c[a|d]+r is already too confusing with the builtin functions when there are more than a few [a|d]'s. There are better ways to get at items in a list.

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

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)))

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)

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/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

Reply on news.ycombinator.com