9 ms·

The Scheme Machine (1994) [pdf]

78 points by steven741 8y ago

mepian 8y ago
Here's a similar older project done at MIT AI Lab, another Scheme CPU called the Scheme86: https://dspace.mit.edu/handle/1721.1/6468 https://dspace.mit.edu/handle/1721.1/6468
- convolvatron 8y ago
  don't forget what must by definition be the first scheme hardware design (lambda: the ultimate opcode) http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-514.pdf http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...
  - wrycoder 8y ago
    And the follow-on implementation: The Scheme-79 Chip https://dspace.mit.edu/handle/1721.1/6334 https://dspace.mit.edu/handle/1721.1/6334 There is also the assq chip, meant as a co-processor for Scheme-81 chip design (which doesn't appear to have an AI Memo), as told by the fascinating Phil Agre (later of Red Rock Eater News Service fame): https://dspace.mit.edu/bitstream/handle/1721.1/41168/AI_WP_225.pdf https://dspace.mit.edu/bitstream/handle/1721.1/41168/AI_WP_2... I'm sorry I missed out on this: https://www.artsy.net/artwork/gerald-sussman-scheme https://www.artsy.net/artwork/gerald-sussman-scheme
gnulinux 8y ago
Quick question: why did we stop producing lisp machines, or any other machine more closely related to Lambda calculus model of computation than a Turing machine? Is it merely cultural, or are there technical reasons as to why we stopped producing them competitively?
- antt 8y ago
  In short Moore's Law. Between 1970 and 2010 if you could design special purpose hardware that ran 10 times faster than the state of the art you would need to get it to market in volume in under 3 years. If you took any longer the general purpose CPUs from Intel would by that point be within spitting distance of your superior architecture, at a fraction of the cost. That's what happened to Symbolics, general purpose PC's could run their software faster than the dedicated machines they designed.
  - shawn 8y ago
    Also Lisp sucks in large groups. The simplicity is both its biggest strength and weakness. There are fewer smart people by definition, and the smartest people tend to want to make money. The net result is that you end up with blub powering the world. Luckily, there’s a way out: have your lisp machine transpile to blub.
    - antt 8y ago
      The smartest people I know are not making any money. It is the mediocrities with delusions of grandeur that do.
    - gnulinux 8y ago
      > the smartest people tend to want to make money. Citation needed. This is the exact opposite of my experience in life so far. Anecdotal maybe, but I met quite a few people from >10 different countries.
    - deleted 8y ago
      [deleted]
  - chr15p 8y ago
    Also if you make hardware absolutely optomised for Lisp then all the C, FORTRAN, and Cobol (this was the 1970's!) programmers aren't particularly interested because it does nothing for their code. So the Lisp machines were targeting a fairly small segment of the market that might have exploded into the mainstream but didn't, so they had less income to reinvest and therefore struggled to maintain their lead over the general purpose/mass market hardware vendors.
- lispm 8y ago
  The target markets were too small (or even were shrinking) to justify the investments necessary to keep the architectures going. Keep in mind that all in all only around 10k machines were produced over the technology lifetime (75-92). That's not a large number. Lisp machines started with hand-made CPUs and ended with special micro-processors (TI, Symbolics, ...). The jump to Lisp-supporting newer RISC (or similar) architectures did not happen, because the main sponsors (DARPA, Military, etc.) did no longer saw them as interesting - applications could run on workstations and high-end PCs. Next-gen CPUs were in the making in end 80s / early 90s (Symbolics, Xerox, LMI, SPUR...) but they did not reach the market - money was running out. The whole thing had its last incarnation in commercial emulators: Medley (the Interlisp-D from Xerox) for Intel+SPARC and Open Genera (Symbolics) for DEC Alpha.
- imode 8y ago
  Because the Lambda calculus is, in large part, rather messy to implement when it comes to physical computing. When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds of structures that are being rewritten. Anything involving trees/terms in general seems to be rather messy in terms of physical computation, because there's no straightforward way to represent a manipulatable tree regardless of the medium. Part of the reason TM-like computing devices sprung up is because strings, i.e linear sequences of symbols, are surprisingly easy to represent and manipulate physically. Turing himself appealed to physical intuition in his original paper. Just my thoughts as a person who's tried to bootstrap his own LC-based computing environment. I did succeed, but I'm not entirely happy with the results.
  - gnulinux 8y ago
    I'm under the impression that LC is closer to how humans think of computation, and it seems that even though it's easier to implement TM as a bare-metal machine, isn't it a trade-off? If humans mostly produce LC-like high-level code, then compile them to TM-like machine code, wouldn't it be better at some point to produce LC-like machines? Because even though they're slower at face value, wouldn't it be faster on "human software". This comment assumes 'humans mostly produce LC-like high-level code', but I think this is valid; other than C, I cannot think of a language in which programmers don't use lambdas, higher-order functions ubiquitously. It seems like our CPUs are optimized for C, but I'm curious how would it change if we optimize them for javascript, python or haskell...
    - imode 8y ago
      Here's a test: do you think in terms of step-by-step instructions to solve a process? There are ways of composing Turing Machines much like composing functions to yield higher abstraction levels in the Lambda Calculus. It comes in the form of building up larger forms of instructions out of simpler machines. I don't think humans think in a LC-like manner, I think we think compositionally: small parts make up big parts, use the parts you make to make bigger parts. Whether those come in the form of a physical machine or an applicative system doesn't matter, what matters is how you string primitives together. Check this[1] out. This walks you through building up a more usable language out of the rough-and-ready Turing Machine. There are many ways to go about this idea of composition, but this is a good introduction. https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30d62dafb6edfcfb9121ced906116.pdf https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30...
- rjsw 8y ago
  One road not taken would have been to port the Lisp Machine software to a commercial CPU, not on top of a multitasking Operating System. Then add a native compiler. A fast 68020 plus a custom MMU would have been competitive with the microcoded machines. A unikernel like MirageOS is basically an OCaml Machine, except that you don't develop software within it. Someone could create a Lisp on Xen equivalent.
  - lispm 8y ago
    The view at Symbolics was mostly (AFAIK) that 32bit were not enough for their software - their microprocessor was a 40bit + 8bit ECC architecture. They also ported their software to the DEC Alpha, because that was a 64bit machine. But generally I would agree that the 68020 + MMU would be mostly okay - given that MCL then ran fine under 68030 + 68040. But the MCL runtime was quite a bit weaker: cooperative multitasking, less CLOS and a less capable memory management.
  - jecel 8y ago
    The very last version of the Symbolics machine wasn't hardware but instead was a virtual machine running on the Alpha processor. So I would say it was a road that was taken, though it was not a success (probably bad timing since I agree it was a good idea). http://pt.withy.org/publications/VLM.html http://pt.withy.org/publications/VLM.html
    - rjsw 8y ago
      The VLM doesn't have a native (to Alpha) compiler.
- isthatart 8y ago
  My guess is that because the accent was put on serial computations. I may be wrong but for for me the big selling point of a(n ideal) lisp machine is that if made right you could cut the machine in half and get two lisp machines. Conversely, two lisp machines working together are a bigger lisp machine, while two Turing machines working together are not a Turing machine. Maybe now is the time for these machines, or better machine parts randomly assembled by the big blind watchmaker [0] over the web. [0] https://en.wikipedia.org/wiki/The_Blind_Watchmaker https://en.wikipedia.org/wiki/The_Blind_Watchmaker
  - chriswarbo 8y ago
    > two Turing machines working together are not a Turing machine They can be. For example multi-tape turing machines can be nice for modelling certain problems (e.g. "monotone turing machines", with a read-only tape, a write-only tape and a normal read/write tape appear a lot in algorithmic information theory). > if made right you could cut the machine in half and get two lisp machines I get where you're coming from in theory, but that's quite far removed from the common usage of the term "lisp machines" (i.e. those which were sold in the 80s), which weren't particularly different from other computers of the time, except for being optimised (in tandem with the OS) for particular workloads (i.e. Lisp programs).
    - isthatart 8y ago
      True for both comments. In the case of the "ideal" lisp machine, in my mind should be something which rewrites local patterns in memory, randomly, in many places. It is possible, theoretically. Multiheaded TMs can also be seen in the same way, provided the state of the heads are also actually on the tape. Both models are particular rewrite systems and among them the lambda calculus based one is simpler (has fewer rewrites) than the TM one. Now that we really feel the need for decentralized computing, maybe some simple generic hardware (much simpler than a TM style processor) could be more fit than what we have now.
- patrickg_zill 8y ago
  The reason is that LISP implementations that ran on "bog standard" hardware such as Motorola 68K, Intel 386 (and higher, but the 386 was released in 1985) and Sun's SPARC machines, could run reasonably well, while also being able to run compilers for other languages and a whole host of other apps. (Yes, there was a C compiler for the LISP machines from Symbolics.) So given the choice between "mainly LISP" and "LISP, C, Pascal, etc." from larger vendors that were virtually guaranteed to be around in 5 years, it was a rational choice to choose the bog-standard machines.
  - sedachv 8y ago
    > Yes, there was a C compiler for the LISP machines from Symbolics. Symbolics had C, Fortran, Pascal, and Prolog compilers. Scott L. Burson (on HN as ScottBurson) wrote a C compiler that ran on Symbolics and also TI and LMI machines (https://cliki.net/Zeta-C https://cliki.net/Zeta-C). So there were two C compilers for the Lisp machines.
- kazinator 8y ago
  > why did we stop producing lisp machines They were expensive and didn't run Unix or MS-DOS.
  - convolvatron 8y ago
    they did work ok in an unix environment. they had ethernets, you could run them with NFS, you could telnet into them sorta. but they were expensive. like really expensive. not just a few 10s of k to buy, but you basically had to have a really fat support contract to keep them running. and they were really single user, so to have a lab supporting 8 users was a well over a million dollar investment. a deskside sun with terminals or pizza box sun 3s as stations was alot cheaper. and they were fragile. i'm pretty sure one of the ones we had was wire wrapped. and they were slow. I may be misremembering, but the flashing status line at the bottom of the monitor would sometimes say the equivalent of 'i am performing a floating point operation now'. we would often reboot them overnight (it took a couple hours) so we could run for a while in the morning before the GC started bogging everything down. the little one they came out with near the end, I think it was the 3620, was largely unusable. the difference was so marked in the end that if you wanted a lisp and didn't want the ferrari model, you could get a mac or a sun and run lucid or allegro and such for basically 1/10th the cost. and it would be faster. just an additional historical note, the other vertical they had besides DoD AI was graphics. for an additional 20k (I think) you could get a 24 bit frame buffer with a nice trinitron monitor and they had some really pleasant software to work with.
    - gnulinux 8y ago
      > they were really single user How is this a limitation in the hardware? Operating system could switch between tasks using context switching right? Or are you suggesting these machines didn't have any mechanism to make sense of time/ticks or didn't have interrupts?
      - rjsw 8y ago
        They had a single address space, tasks were more like threads in a modern system. The MIT/LMI/TI ones didn't take interrupts, the microcode needed to poll the interrupt register at suitable points.
- DonaldFisk 8y ago
  These articles explain the demise of Symbolics: https://danluu.com/symbolics-lisp-machines/ https://danluu.com/symbolics-lisp-machines/ http://web.mit.edu/6.933/www/Symbolics.pdf http://web.mit.edu/6.933/www/Symbolics.pdf Some of the reasons given were unique to Symbolics, others more general. LMI went under earlier, and the other two Lisp machine manufacturers (TI and Xerox) stopped manufacturing them but they had other products.
imode 8y ago
For all those downvoting my comments, why? Am I not contributing to the discussion?
- wrycoder 8y ago
  I'm thinking that your extraordinary rudeness to Carl Hewitt, one of our elders, on the Actor thread was not appreciated.
  - imode 8y ago
    I'm sorry, but he's a crank, as called by somebody else in said thread. Down vote me if you want, it's a shared opinion, regardless of Carl's cult of personality. Very childish.

78 points by steven741 8y ago

Here's a similar older project done at MIT AI Lab, another Scheme CPU called the Scheme86: https://dspace.mit.edu/handle/1721.1/6468 https://dspace.mit.edu/handle/1721.1/6468

convolvatron 8y ago
don't forget what must by definition be the first scheme hardware design (lambda: the ultimate opcode) http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-514.pdf http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...
- wrycoder 8y ago
  And the follow-on implementation: The Scheme-79 Chip https://dspace.mit.edu/handle/1721.1/6334 https://dspace.mit.edu/handle/1721.1/6334 There is also the assq chip, meant as a co-processor for Scheme-81 chip design (which doesn't appear to have an AI Memo), as told by the fascinating Phil Agre (later of Red Rock Eater News Service fame): https://dspace.mit.edu/bitstream/handle/1721.1/41168/AI_WP_225.pdf https://dspace.mit.edu/bitstream/handle/1721.1/41168/AI_WP_2... I'm sorry I missed out on this: https://www.artsy.net/artwork/gerald-sussman-scheme https://www.artsy.net/artwork/gerald-sussman-scheme

gnulinux 8y ago

Quick question: why did we stop producing lisp machines, or any other machine more closely related to Lambda calculus model of computation than a Turing machine? Is it merely cultural, or are there technical reasons as to why we stopped producing them competitively?

antt 8y ago
In short Moore's Law. Between 1970 and 2010 if you could design special purpose hardware that ran 10 times faster than the state of the art you would need to get it to market in volume in under 3 years. If you took any longer the general purpose CPUs from Intel would by that point be within spitting distance of your superior architecture, at a fraction of the cost. That's what happened to Symbolics, general purpose PC's could run their software faster than the dedicated machines they designed.
- shawn 8y ago
  Also Lisp sucks in large groups. The simplicity is both its biggest strength and weakness. There are fewer smart people by definition, and the smartest people tend to want to make money. The net result is that you end up with blub powering the world. Luckily, there’s a way out: have your lisp machine transpile to blub.
  - antt 8y ago
    The smartest people I know are not making any money. It is the mediocrities with delusions of grandeur that do.
  - gnulinux 8y ago
    > the smartest people tend to want to make money. Citation needed. This is the exact opposite of my experience in life so far. Anecdotal maybe, but I met quite a few people from >10 different countries.
  - deleted 8y ago
    [deleted]
- chr15p 8y ago
  Also if you make hardware absolutely optomised for Lisp then all the C, FORTRAN, and Cobol (this was the 1970's!) programmers aren't particularly interested because it does nothing for their code. So the Lisp machines were targeting a fairly small segment of the market that might have exploded into the mainstream but didn't, so they had less income to reinvest and therefore struggled to maintain their lead over the general purpose/mass market hardware vendors.
lispm 8y ago
The target markets were too small (or even were shrinking) to justify the investments necessary to keep the architectures going. Keep in mind that all in all only around 10k machines were produced over the technology lifetime (75-92). That's not a large number. Lisp machines started with hand-made CPUs and ended with special micro-processors (TI, Symbolics, ...). The jump to Lisp-supporting newer RISC (or similar) architectures did not happen, because the main sponsors (DARPA, Military, etc.) did no longer saw them as interesting - applications could run on workstations and high-end PCs. Next-gen CPUs were in the making in end 80s / early 90s (Symbolics, Xerox, LMI, SPUR...) but they did not reach the market - money was running out. The whole thing had its last incarnation in commercial emulators: Medley (the Interlisp-D from Xerox) for Intel+SPARC and Open Genera (Symbolics) for DEC Alpha.
imode 8y ago
Because the Lambda calculus is, in large part, rather messy to implement when it comes to physical computing. When we look at what computation is, physically, we find it's a lot like a Turing machine underneath (physical rewriting systems), albeit with different kinds of structures that are being rewritten. Anything involving trees/terms in general seems to be rather messy in terms of physical computation, because there's no straightforward way to represent a manipulatable tree regardless of the medium. Part of the reason TM-like computing devices sprung up is because strings, i.e linear sequences of symbols, are surprisingly easy to represent and manipulate physically. Turing himself appealed to physical intuition in his original paper. Just my thoughts as a person who's tried to bootstrap his own LC-based computing environment. I did succeed, but I'm not entirely happy with the results.
- gnulinux 8y ago
  I'm under the impression that LC is closer to how humans think of computation, and it seems that even though it's easier to implement TM as a bare-metal machine, isn't it a trade-off? If humans mostly produce LC-like high-level code, then compile them to TM-like machine code, wouldn't it be better at some point to produce LC-like machines? Because even though they're slower at face value, wouldn't it be faster on "human software". This comment assumes 'humans mostly produce LC-like high-level code', but I think this is valid; other than C, I cannot think of a language in which programmers don't use lambdas, higher-order functions ubiquitously. It seems like our CPUs are optimized for C, but I'm curious how would it change if we optimize them for javascript, python or haskell...
  - imode 8y ago
    Here's a test: do you think in terms of step-by-step instructions to solve a process? There are ways of composing Turing Machines much like composing functions to yield higher abstraction levels in the Lambda Calculus. It comes in the form of building up larger forms of instructions out of simpler machines. I don't think humans think in a LC-like manner, I think we think compositionally: small parts make up big parts, use the parts you make to make bigger parts. Whether those come in the form of a physical machine or an applicative system doesn't matter, what matters is how you string primitives together. Check this[1] out. This walks you through building up a more usable language out of the rough-and-ready Turing Machine. There are many ways to go about this idea of composition, but this is a good introduction. https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30d62dafb6edfcfb9121ced906116.pdf https://pdfs.semanticscholar.org/presentation/98e5/6df9c1c30...
rjsw 8y ago
One road not taken would have been to port the Lisp Machine software to a commercial CPU, not on top of a multitasking Operating System. Then add a native compiler. A fast 68020 plus a custom MMU would have been competitive with the microcoded machines. A unikernel like MirageOS is basically an OCaml Machine, except that you don't develop software within it. Someone could create a Lisp on Xen equivalent.
- lispm 8y ago
  The view at Symbolics was mostly (AFAIK) that 32bit were not enough for their software - their microprocessor was a 40bit + 8bit ECC architecture. They also ported their software to the DEC Alpha, because that was a 64bit machine. But generally I would agree that the 68020 + MMU would be mostly okay - given that MCL then ran fine under 68030 + 68040. But the MCL runtime was quite a bit weaker: cooperative multitasking, less CLOS and a less capable memory management.
- jecel 8y ago
  The very last version of the Symbolics machine wasn't hardware but instead was a virtual machine running on the Alpha processor. So I would say it was a road that was taken, though it was not a success (probably bad timing since I agree it was a good idea). http://pt.withy.org/publications/VLM.html http://pt.withy.org/publications/VLM.html
  - rjsw 8y ago
    The VLM doesn't have a native (to Alpha) compiler.
isthatart 8y ago
My guess is that because the accent was put on serial computations. I may be wrong but for for me the big selling point of a(n ideal) lisp machine is that if made right you could cut the machine in half and get two lisp machines. Conversely, two lisp machines working together are a bigger lisp machine, while two Turing machines working together are not a Turing machine. Maybe now is the time for these machines, or better machine parts randomly assembled by the big blind watchmaker [0] over the web. [0] https://en.wikipedia.org/wiki/The_Blind_Watchmaker https://en.wikipedia.org/wiki/The_Blind_Watchmaker
- chriswarbo 8y ago
  > two Turing machines working together are not a Turing machine They can be. For example multi-tape turing machines can be nice for modelling certain problems (e.g. "monotone turing machines", with a read-only tape, a write-only tape and a normal read/write tape appear a lot in algorithmic information theory). > if made right you could cut the machine in half and get two lisp machines I get where you're coming from in theory, but that's quite far removed from the common usage of the term "lisp machines" (i.e. those which were sold in the 80s), which weren't particularly different from other computers of the time, except for being optimised (in tandem with the OS) for particular workloads (i.e. Lisp programs).
  - isthatart 8y ago
    True for both comments. In the case of the "ideal" lisp machine, in my mind should be something which rewrites local patterns in memory, randomly, in many places. It is possible, theoretically. Multiheaded TMs can also be seen in the same way, provided the state of the heads are also actually on the tape. Both models are particular rewrite systems and among them the lambda calculus based one is simpler (has fewer rewrites) than the TM one. Now that we really feel the need for decentralized computing, maybe some simple generic hardware (much simpler than a TM style processor) could be more fit than what we have now.
patrickg_zill 8y ago
The reason is that LISP implementations that ran on "bog standard" hardware such as Motorola 68K, Intel 386 (and higher, but the 386 was released in 1985) and Sun's SPARC machines, could run reasonably well, while also being able to run compilers for other languages and a whole host of other apps. (Yes, there was a C compiler for the LISP machines from Symbolics.) So given the choice between "mainly LISP" and "LISP, C, Pascal, etc." from larger vendors that were virtually guaranteed to be around in 5 years, it was a rational choice to choose the bog-standard machines.
- sedachv 8y ago
  > Yes, there was a C compiler for the LISP machines from Symbolics. Symbolics had C, Fortran, Pascal, and Prolog compilers. Scott L. Burson (on HN as ScottBurson) wrote a C compiler that ran on Symbolics and also TI and LMI machines (https://cliki.net/Zeta-C https://cliki.net/Zeta-C). So there were two C compilers for the Lisp machines.
kazinator 8y ago
> why did we stop producing lisp machines They were expensive and didn't run Unix or MS-DOS.
- convolvatron 8y ago
  they did work ok in an unix environment. they had ethernets, you could run them with NFS, you could telnet into them sorta. but they were expensive. like really expensive. not just a few 10s of k to buy, but you basically had to have a really fat support contract to keep them running. and they were really single user, so to have a lab supporting 8 users was a well over a million dollar investment. a deskside sun with terminals or pizza box sun 3s as stations was alot cheaper. and they were fragile. i'm pretty sure one of the ones we had was wire wrapped. and they were slow. I may be misremembering, but the flashing status line at the bottom of the monitor would sometimes say the equivalent of 'i am performing a floating point operation now'. we would often reboot them overnight (it took a couple hours) so we could run for a while in the morning before the GC started bogging everything down. the little one they came out with near the end, I think it was the 3620, was largely unusable. the difference was so marked in the end that if you wanted a lisp and didn't want the ferrari model, you could get a mac or a sun and run lucid or allegro and such for basically 1/10th the cost. and it would be faster. just an additional historical note, the other vertical they had besides DoD AI was graphics. for an additional 20k (I think) you could get a 24 bit frame buffer with a nice trinitron monitor and they had some really pleasant software to work with.
  - gnulinux 8y ago
    > they were really single user How is this a limitation in the hardware? Operating system could switch between tasks using context switching right? Or are you suggesting these machines didn't have any mechanism to make sense of time/ticks or didn't have interrupts?
    - rjsw 8y ago
      They had a single address space, tasks were more like threads in a modern system. The MIT/LMI/TI ones didn't take interrupts, the microcode needed to poll the interrupt register at suitable points.
DonaldFisk 8y ago
These articles explain the demise of Symbolics: https://danluu.com/symbolics-lisp-machines/ https://danluu.com/symbolics-lisp-machines/ http://web.mit.edu/6.933/www/Symbolics.pdf http://web.mit.edu/6.933/www/Symbolics.pdf Some of the reasons given were unique to Symbolics, others more general. LMI went under earlier, and the other two Lisp machine manufacturers (TI and Xerox) stopped manufacturing them but they had other products.

imode 8y ago

For all those downvoting my comments, why? Am I not contributing to the discussion?

wrycoder 8y ago
I'm thinking that your extraordinary rudeness to Carl Hewitt, one of our elders, on the Actor thread was not appreciated.
- imode 8y ago
  I'm sorry, but he's a crank, as called by somebody else in said thread. Down vote me if you want, it's a shared opinion, regardless of Carl's cult of personality. Very childish.