Lisp BigO

How fast is:
 
(cdr list...)

O(1)

mov eax, [eax+3]

Are you familiar with a CONS CELL?

>>4
of course not

does lisp optimize for tail recursion?

>>3
U MENA mov 4(r0), r0

>>6
Scheme does. For CL it's upto the implementation. Every implementation worth using naturally does.

It's just a pointer de-reference. If this were C, it could be seen as list->cdr, where cdr could translate to some offset like +4. In x86 assembly it could look like:
mov reg1, [reg2+4] or lea reg1, [reg2+4].
Obviously O(1).

>>4
A cons cell is just a pair of 2 values, the car and the cdr, usually to be thought of a type-tagged structure of 2 elements (sometimes compressed into a register-sized object for extra performance).

s/>>4/>>5//

>>9
U MENA movl 4(r0), r1 or moval 4(r0), r1

>>10
so:

struct simple_con {
  void *car;
  void **cdr;
}

>>13

this could work:


struct simple_con {
  void *car;
  struct simple_cons *cdr;
};

although people sometimes put other things in the cdr, like numbers or strings.

>>14
struct simple_cons {
  union {
    struct simple_cons *car;
    intptr_t intcar;
  };
  union {
    struct simple_cons *cdr;
    intptr_t intcdr;
  };
};
If intptr_t and pointer to struct are the same size, this could work.

>>15

yeah, I should have clarified. In dynamic languages, primitives are often wrapped inside of tagged objects. So an int is actually something like:

struct fixnum {
  enum object_type = TYPE_FIXNUM;
  int value;
};

And then this object would be allocated on the heap, possibly using reference counting, or just depending on garbage collection. So in this case, storing a primitive in the cdr is just storing a pointer to something other than a cons cell. So it might be more accurate to just do:

struct simple_cons {
  void *car;
  void *cdr;
};

ENTERPRISE CONS


/*
 *  Cons.java
 *
 *  Copyright 1997 Massachusetts Institute of Technology.
 *  All Rights Reserved.
 *
 *  Author: Ora Lassila
 *
 *  $Id: Cons.java,v 1.2 1998/01/22 13:08:38 bmahe Exp $
 */

package org.w3c.tools.sexpr;

import java.io.PrintStream;
import java.util.Enumeration;

/**
 * Basic class for implementing linked lists a la Lisp.
 */
public class Cons implements SExpr {

  private Object car;
  private Object cdr;

  /**
   * Initializes a Cons cell with the left and right "subtrees".
   */
  public Cons(Object left, Object right)
  {
    this.car = left;
    this.cdr = right;
  }

  /**
   * Initializes a Cons cell with a left subtree only.
   * Right subtree will be set to <tt>null</tt>.
   */
  public Cons(Object left)
  {
    this.car = left;
    this.cdr = null;
  }

  /**
   * Returns the left subtree (i.e. the head) of a cons cell.
   */
  public Object left()
  {
    return car;
  }

  /**
   * Returns the right subtree (i.e. the tail) of a cons cell.
   */
  public Object right()
  {
    return cdr;
  }

  /**
   * Returns the tail of a cons cell if it is a list.
   * Signals an error otherwise (no dotted pairs allowed).
   *
   * @exception SExprParserException if the tail is not a Cons or <tt>null<tt>
   */
  public Cons rest()
    throws SExprParserException
  {
    Object r = right();
    if (r == null)
      return null;
    else if (r instanceof Cons)
      return (Cons)r;
    else
      throw new SExprParserException("No dotted pairs allowed");
  }

  /*
   * Returns an enumeration of the elements of the list.
   */
  public Enumeration elements()
  {
    return new ConsEnumeration(this);
  }

  public void printExpr(PrintStream stream)
  {
    printList(stream, true);
  }

  private void printList(PrintStream out, boolean first)
  {
    out.print(first ? "(" : " ");
    SimpleSExprStream.printExpr(left(), out);
    Object r = right();
    if (r == null)
      out.print(")");
    else if (r instanceof Cons)
      ((Cons)r).printList(out, false);
    else {
      out.print(". ");
      SimpleSExprStream.printExpr(r, out);
      out.print(")");
    }
  }

}

class ConsEnumeration implements Enumeration {

  private Cons current;

  public ConsEnumeration(Cons head)
  {
    this.current = head;
  }

  public boolean hasMoreElements()
  {
    return current != null;
  }

  public Object nextElement()
  {
    Object element = null;
    try {
      element = current.left();
      current = current.rest();
    }
    catch (SExprParserException e) {
      // current is a dotted pair
      current = null;
    }
    return element;
  }

}

>>16
No it isn't. You're still clueless. Cripes. Go scrub another toilet you fucking idiot.

>>18
yeah, I should have clarified. In dynamic languages, primitives are often wrapped inside of tagged objects. So an int can sometimes be implemented in the following manner

>>19
Please shut up, go leave this joint, and actually read a book. Instead of like, ya know, just picking up bits and pieces from google.

>>13
Both would be void*, although technically the inner details differ per implementation, saying that a cons has any properties than being a pair of 2 other objects (be they whatever you want, numbers, atoms, symbols, conses, structures, etc).
When you interpret/treat a cons as a list, then the car is supposed to be the first element (whatever that may be), and the cdr is supposed to be the rest of the list. A proper list terminates when cdr points to an object called '() or NIL or () (just a symbol named nil, nothing more; this applies for CL, for scheme it's only '()). An improper list does not follow the previous rule, examples could be circular lists or merely putting some other object than '() in the final cdr(after traversal). Improper lists tend to be printed like: (a . b) for (cons a b), while the proper list '(a b) could be generated (among other equivalent code) by (cons 'a (cons 'b nil)) (A side-note: I didn't quote nil because it's self-evaluating, that is, the value of nil is 'nil itself, same goes for t).
The closest I can think for how to write a cons-like thing would be:

tagged_struct cons
{
    LispObject car;
    LispObject cdr;
}
Where LispObject is some tagged object by itself, but its dimensions are to remain a mystery (until some implementation decides how it wants to handle it, but you could imagine it could use some 1-2 bits for type-tagging, thus you could end up with fixnum integers being encoded in a register-sized object, while some other object might be  a full pointer or(|)'d with a tag). tagged_struct is to be taken to be some other LispObject as well. Of course, since such implementations are messy to do in C in simple ways, despite being what most Lisp implementations do in practice(for performance reasons), you could always imagine something like:
struct cons
{
    enum uint tag = TAG_CONS;
    LispObject *car;
    LispObject *cdr;
}


>>14
That's coming close to looking like a list, but lists are just conventions in Lisp, they're not the only thing cons does, but then you also said so.

>>20
excuse me, but if you can provide an alternative implementation that can support constructs such as the following

a = "lol I'm a string!";
print(a);
a = 1337;
print(a);

without wrapping primitives inside of objects that have something like a type tag, or a vtable pointer, then I would like to see it. And you can't optimize it to something like:

print_string("lol I'm a string");
print_int(1337);

because knowing predicting the type of a will, in general, reduce to the halting problem.

Should check my writing before posting:
*saying that a cons has any properties than being a pair of 2 other objects (be they whatever you want, numbers, atoms, symbols, conses, structures, etc) would be wrong.
*enum tag = TAG_CONS

>>22

because knowing predicting the type of a will, in general, reduce to the halting problem.

No it doesn't. Also, what you just rattled about doesn't reduce to the halting problem you fucking clueless dweeb. Holy shit you're dumb. Please just shut up and actually read a fucking book.

>>22
Lisp isn't dynamically typed in that sense you're talking about. Each object is type-tagged and types are clear at all times. Dynamic typing means that you can assign any type to some variable. There is no type prediction at runtime, it's just trivial type dispatching (where relevant, see typecase in CL). Static languages where a variable can only have a single type just eliminate the need of a type-tag by either doing type inference or asking the user to provide the types for the compiler (which are still checked, if a compiler is worth its salt).

Suppose that we have a method of always inferring the type of a variable in a dynamic language. And suppose we would like to know if an algorithm, A will halt or not. We can construct a new algorithm, B

function B()
  if(halts(A))
    a = "lol, I'm a string"
  else
    a = 1337
  end
  print(a)
end

We use the method to find out what the type of a will be when it is printed. If a is a string, then A halts. If a is an int, then A will not halt.

>>26
Again, you have zero clue what you're talking about. Now tell me what you do for a living? Given the fact you seem totally clueless about what you're talking about, I'm willing to bet you do tech support at the very best.

>>27
*as to what*

>>26
Did anyone claim type inference for dynamicly typed languages? Compilers tend to do it for trivial cases, but of course it won't do it for any non-trivial cases. Also, a static language (like ML) could just solve this problem by making a's type like this: type string_or_int = S of string | B of int;;, no problem there, it's limited enough for type-inference, but not free enough for dynamic typing.

>>27

yeap, you're right, I did it the wrong way. Hold on...

>>30
No. The only thing you need to do is shut up.

>>29

mr >>27-san didn't like my example of wrapping primitives in tagged objects, so I was just suggesting that type inference is not possible in general. That proof is wrong though, let me try again...

>>27
No... he's right. By this time you guys are arguing about static type inference in a dynamically typed language, which is insane on its face, but >>26-kun isn't full of shit, just irrelevant.

>>32
And you still haven't told us what you do for a living. Given your subpar technical responses on here, again, I'm willing to bet you work some shit hourly general labor labor.

naw, wait, I think the proof is correct. >>27-san, what do you find wrong with the proof?

>>35
He missed two cases,

>>36
I must know...

>>26
Suppose that we have a method of always inferring the value of a variable in a static language. And suppose we would like to know if an algorithm, A will halt or not. We can construct a new algorithm, B

function B()
  if(halts(A))
    a = 1
  else
    a = 0
  end
  print(a)
end

We use the method to find out what the value of a will be when it is printed. If a is 1, then A halts. If a is 0, then A will not halt.

>>29
Heh, the ML solution involves type tags anyway.

>>37
You need the additional case(s) because it's proof by contradiction. However, the minimum wage dipshit that posted the proof only supplies a really sloppy version of one case.

>>38
You need the other case in order to arrive at the contradiction you dipshit. Cripes. Please shut up and go read a book.

ENTERPRISE JAVA SOLUTION


public static void print(Object o) {
  System.out.printf("%s",o.toString());
}

>>40
yeah it was sloppy. Lemme try again.

Suppose for the sake of contradiction that we have the ability to always predict the type of a variable in a dynamic language. We will reach a contradiction by showing that the haling problem is decidable. Suppose that halts is a function that takes an algorithm as its input and will return true if A will halt, and false if A will not halt. Note that the halts function need not halt itself. Let A be an arbitrary algorithm. Define B to be the following:

function B()
  if(halts(A))
    a = "lol I'm a string"
  else
    a = 1337
  end
  print(a)
end

We can now implement a special Halts function, that will halt on all inputs:

function Halts(A)
  function B()
    if halts(A) then
      a = "lol I'm a string"
    else
      a = 1337
    end
    print(a)
  end
  a_predicted_type = predict_type_when_printed(B, 'a')
  if a_predicted_type == 'string' then
    return true
  else
    return false
  end
end

Halts will halt on all inputs, as the only routines it only calls the check_the_type function, which is assumed to be decidable. Halts correctly decides when algorithms will halt or not because halts correctly indicates when an algorithm will halt or not (or does it)***. So Halts is a solution to the halting problem which halts on all inputs, which implies that the halting problem is decidable, and we have reached a contradiction. Therefore the initial assumption that predicting a type of a variable in a language is decidable, must be false.

I think that would do it, although, *** what if halts(A) doesn't halt? Then its return value is not defined right? So what would be the behavior of the check_type function, when it is checking the type of a variable at a point in the algorithm that can never be reached? There's probably a better way of doing this.

It might be better to first show that determining whether a statement is reached or not is undecidable, and then use that instead. Then you could reduce it to determining whether the statement that changes a from an int to a string is executed or not.

>>43
And this still doesn't support any of your idiotic assertions. Please do us all a favor and go kill yourself.

>>45
got banned from irc again huh

>>46
/prog/ has an irc?

oh lordy i can only imagine the retardation in that room, kodak, frozenvoid,tripfags

>>47
Tom Dewey, is that you?

 https://plus.google.com/105135920512989534124/posts/5Sa8idZTd25

>>45

Alright, I'll do it better this time.

Part one, showing that determining whether or not a statement is executed is undecidable. Suppose for the sake that determining whether or not a statement is executed is decidable. We will reach a contradiction by showing that the halting problem is decidable. Here is the solution:

function halts(A)
  function B()
    A()
    execute_special_statement()
  end
  statement_would_be_executed = inspect_B_and determine_if_execute_special_statement is executed
  return statement_would_be_executed
end

If A halts, then execute_special_statement will be executed, and halts(A) will return true. If A does not halt, then execute_special_statement would never be executed, and halts(A) will return false. Because the process of determining whether execute_special_statement will halt or not is assumed to be a decider, then we have that halts is also a decider. By producing a solution to the halting problem that halts on all its inputs we have shown that the halting problem is decidable, which is a contradiction. Hence, the problem of determining whether a statement is executed or not must be undecidable.


Part 2: Showing that perfect type prediction is undecidable. Suppose for the sake of contradiction perfect type prediction is decidable. We will reach a contradiction by showing that determining whether or not a statement is executed is decidable. Let A be an arbitrary algorithm, with a() being an arbitrary statement within A.

function A()
 ...
 a()
 ...
end

We will produce an algorithm, Executes(A,a) that will return true if a() is executed when A is ran, and false if a() is not executed when A is ran, and we will show that Executes halts on all inputs.

We will produce a new algorithm from A, called B, defined as follows:

function B()
  my_var = "lol I'm a string"
  <first chunk of code from A>
  {
    my_var = 1337
    a()
  }
  <second chunk of code from A>
  print(my_var)
end

note that my_var is a string when it is printed if and only if a() is never executed, and my_var is an int if and only if a() is executed.

function Executes(A,a)
  let B be defined in terms of A and a, as above
  my_var_type_when_printed = predict_type_when_printed(B, 'my_var)
  if my_var_type_when_printed == 'int' then
    return true
  else
    return false
  end
end

Executes is a decider, because it relies only on type prediction, which is assumed to be decidable. Executes correctly determines when a is executed within A, because my_var becomes an int if and only if a() is executed within A. So Executes is a solution to the problem to checking whether a statement is executed or not, that halts on all inputs, which shows that the problem of determining whether a statement is executed or not, is decidable, which is a contradiction. Therefore, the initial assumption of type prediction being decidable must be false.

>>47

yeap, just like every other irc channel, right?

>>47
There were/are a handful of /prog/-related channels. The few that I lurk in don't seem to have too much visibile stupidity, nor are they frequented by those characters you mention, and even if some occurs, it's not like it's hard to ban or ``mute'' someone(either ban, or +m and +v rest of the people). However, like all IRC channels, there is persistent identity (unless you try hard to avoid that, but won't really work if you're the only one interesting in doing that, in which case, just using some other protocol might be better), which leads to a different kind of community than anonymous BBSes, at best it only has people who go to both in common, but as forms of communication they are far too different to maintain a ``culture'' unaltered.

>>48
No, and i most certain don't use any social networking sites at all yet alone spyware sites.


go back to /g/ you ``faggot''.

Can (reverse <list>) be implemented using tail recursion? If yes, show how.

Answer: Yes.
(define my-reverse (lambda (l)
    (define f (lambda (l a)
        (if (null? l)
            a
            (f
                (cdr l)
                (cons (car l) a)))))
    (f l '())))

>>49
(define halts (lambda (a)
    (define f (lambda ()
        ((a) (execute-special-statement)))
    (set! statement_would_be_executed
        (and
            (inspect B)
            (determine-if-execute-special-statement-is-executed)))))
It's in Lisp. Lisp can solve the halting problem. The GC runs out of memory, and halts.

>>52

let reverse l =
    let rec rev l' l = match l with
    | [] -> l'
    | x::xs -> rev (x::l') xs
    in rev [] l;;

Now with 93% less parens.

I would write, it except it already exists: (reverse list)

>>55
It still has too many parens.

>>52
(define (reverse xs) (foldl cons '() xs))

>>56
What about #'reverse?