3 ms·

Well, you can define pairs like this (as long as you've got lexical scope): (setq cons (lambda (x xs) (lambda (msg) (if (eq m

Well, you can define pairs like this (as long as you've got lexical scope): (setq cons (lambda (x xs) (lambda (msg) (if (eq msg 'car) x xs))) (setq car (lambda (xs) (xs 'car))) (setq cdr (lambda (xs) (xs 'cdr))) That only uses 'setq, 'lambda, 'if, 'eq, and quoted symbols. That pretty much gives you the untyped lambda calculus, plus some side effects. Throw in the appropriate macros and you've got the core of Scheme and Arc, without any I/O or efficient data representations. You can take this pretty far. Essentially, you just need 'lambda and application. You could use church numerals for numbers, monads for side effects, the y-combinator for recursion, etc.

mahmud 17y ago
Under which lisp implementation do those forms work? The definitions for CAR and CDR are identical and they don't make much sense (set the symbol 'car to the value of a function that takes angument xs, which is a function, and applies that to the symbol 'car) And the definition for CONS is equally opaque. How would you use those functions, CONS, CAR and CDR? Since you pretty much nailed the uses of church numerals, monads and the y-combinator, I know you know what you're talking about, it just that Lisp's semantics is confusing me (it has common lisp keyword SETQ but none of its behavior)
- mquander 17y ago
  Those look correct to me. The function returned by cons is just a switch that holds two values in a closure, and interprets what you pass it as a signal to determine which to retrieve. You could just as easily rewrite it to pass it 0 or 1 instead of car and cdr. If you evaluate (car (cons 1 2)) and (cdr (cons 1 2)) on paper using substitution, you'll see how it works.
  - dkersten 17y ago
    Exactly. SICP shows some similar code, though I don't remember which part..
- twilightsentry 17y ago
  Oops; I meant to write those in CL, but I forgot about functions having their own namespace (been playing too long in a lisp-1). It should work in CL if you use FUNCALL. If mquander's explanation isn't enough, you might look at it using terms from the OO world: CAR takes a pair object and calls its 'car method.
  - mahmud 17y ago
    So you mean a meta-circular OOP implementation, where the hosting language already has car, cdr and cons. Alright. I thought what you wrote was supposed to be a primitive implementation of the functions.
    - twilightsentry 17y ago
      No, not really, unless you're running the code in a metacircular interpreter. Imagine encoding the pair ('hello . 'world) into a function. You might say: (lambda (msg) (if (eq msg 'car) 'hello 'world)) You could get 'hello by applying that function to the 'car symbol, or 'world by applying it to anything else. Wrapping that in another function lets us generalise to any CAR/CDR. (lambda (car-value cdr-value) (lambda (msg) (if (eq msg 'car) car-value cdr-value)))

mahmud 17y ago

Under which lisp implementation do those forms work? The definitions for CAR and CDR are identical and they don't make much sense (set the symbol 'car to the value of a function that takes angument xs, which is a function, and applies that to the symbol 'car) And the definition for CONS is equally opaque. How would you use those functions, CONS, CAR and CDR? Since you pretty much nailed the uses of church numerals, monads and the y-combinator, I know you know what you're talking about, it just that Lisp's semantics is confusing me (it has common lisp keyword SETQ but none of its behavior)

mquander 17y ago
Those look correct to me. The function returned by cons is just a switch that holds two values in a closure, and interprets what you pass it as a signal to determine which to retrieve. You could just as easily rewrite it to pass it 0 or 1 instead of car and cdr. If you evaluate (car (cons 1 2)) and (cdr (cons 1 2)) on paper using substitution, you'll see how it works.
- dkersten 17y ago
  Exactly. SICP shows some similar code, though I don't remember which part..
twilightsentry 17y ago
Oops; I meant to write those in CL, but I forgot about functions having their own namespace (been playing too long in a lisp-1). It should work in CL if you use FUNCALL. If mquander's explanation isn't enough, you might look at it using terms from the OO world: CAR takes a pair object and calls its 'car method.
- mahmud 17y ago
  So you mean a meta-circular OOP implementation, where the hosting language already has car, cdr and cons. Alright. I thought what you wrote was supposed to be a primitive implementation of the functions.
  - twilightsentry 17y ago
    No, not really, unless you're running the code in a metacircular interpreter. Imagine encoding the pair ('hello . 'world) into a function. You might say: (lambda (msg) (if (eq msg 'car) 'hello 'world)) You could get 'hello by applying that function to the 'car symbol, or 'world by applying it to anything else. Wrapping that in another function lets us generalise to any CAR/CDR. (lambda (car-value cdr-value) (lambda (msg) (if (eq msg 'car) car-value cdr-value)))