arrays and lamda terms

Claus Reinke claus.reinke@talk21.com
Tue, 4 Feb 2003 20:04:32 -0000


This is a multi-part message in MIME format.

------=_NextPart_000_0034_01C2CC88.A20BDC20
Content-Type: text/plain;
	charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable


  Is it possible to encode an array using lamda terms only, and recover =
the term specified by an index term in O(1) time (in other words in one =
step reduction, without cheating using several steps behind the scenes)? =

depends a bit on your definitions, doesn't it? if you take lambda with =
unary abstractions only,
it is going to be rather difficult; if you take lambda with n-ary =
abstractions, it is going to be
rather easy, assuming you mean constant-steps, not single-step =
(typically, access to function=20
parameters is implemented via a single instruction, directly indexing =
into some parameter=20
structure, which is little different from array access - you can play =
with the idea in Haskell,=20
so it's not even off topic;-).

hth,
claus

------=_NextPart_000_0034_01C2CC88.A20BDC20
Content-Type: text/html;
	charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Dwindows-1252">
<META content=3D"MSHTML 6.00.2712.300" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2></FONT>&nbsp;</DIV>
<BLOCKQUOTE dir=3Dltr=20
style=3D"PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; =
BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
  <DIV><FONT face=3DArial size=3D2>Is it possible to encode an array =
using lamda=20
  terms only, and recover the term specified by an index term in O(1) =
time (in=20
  other words in one step reduction, without cheating using several =
steps behind=20
  the scenes)? </FONT></DIV></BLOCKQUOTE>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>depends a bit on your =
definitions, doesn't=20
it? if you take lambda with unary abstractions only,</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>it is going to be rather =
difficult; if you=20
take lambda with n-ary abstractions, it is going to be</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>rather easy, assuming you =
mean=20
constant-steps, not single-step (typically, access to function =
</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>parameters is implemented =
via&nbsp;a=20
single&nbsp;instruction, directly indexing&nbsp;into </FONT><FONT =
face=3DArial=20
size=3D2>some parameter </FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>structure, which is little =
</FONT><FONT=20
face=3DArial size=3D2>different from array access - you can play with =
the=20
</FONT><FONT face=3DArial size=3D2>idea in Haskell, </FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>so it's not even off =
topic;-).</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2></FONT>&nbsp;</DIV>
<DIV dir=3Dltr><FONT face=3DArial size=3D2>hth,</FONT></DIV>
<DIV dir=3Dltr><FONT face=3DArial =
size=3D2>claus</FONT></DIV></BODY></HTML>

------=_NextPart_000_0034_01C2CC88.A20BDC20--