Projekt LambdaCan

Link: http://alum.wpi.edu/~tfraser/Software/Arduino/lambdacan.html

Lambda Calculus i en Can(Arduino board mountedin can)

(Arduino board mountedin kan)
Du kan få suppe i en dåse. Du kan få brød i en dåse (*). Nu den lange ventetid er forbi! Du kan endelig få Lambda Calculus i en dåse.

Projekt LambdaCan er en underholdende øvelse i absurditet. Det gennemfører en reducering (tolk) til Lambda Calculus, et formelt system (programmeringssprog) udviklet af Alonzo Church i 1930’erne til at angribe den dybeste matematisk problem af dagen. Dette var Entscheidungsproblem, spørgsmålet om, hvorvidt der findes en algoritme i stand til at beslutte sandheden eller falskhed af alle udsagn i matematik.(Components used in Project LambdaCan)

Projekt LambdaCan tager dette værktøj for at udforske de mest dybtgående matematiske problemer og implementerer det på en microcontroller bedre egnet til de mest hverdagsagtige opgaver, som at løbe en automat eller mikrobølgeovn. Og det stikker microcontroller i en dåse, som du kan oprette forbindelse til din pc ved hjælp af et USB-kabel.

Selvfølgelig den ekstreme overliggende involveret i at støtte smerteligt abstrakte Lambda Calculus notation gør LambdaCan kamp for at beregne aritmetiske så simpelt som 11 + 12 = 23. microcontroller ville virke meget bedre, hvis programmeret i sin modersmål. Desuden selve ideen om at tilslutte en LambdaCan coprocessor i en typisk pc til at udføre beregninger er absurd, da pc’en uden tvivl kunne håndtere meget større beregninger hurtigere på egen hånd.

Men … hey, det er Lambda Calculus i en dåse!

Byg din egen LambdaCan(LambdaCan in action)

(Komponenter, der anvendes i Project LambdaCan) LambdaCan er hovedsagelig en Arduino Diecimila bord monteret i en hoste dråbe kan bruge epoxy kit. Den Diecimila bord bruger en Atmel ATmega168 microcontroller med 16KB af flash RAM og 1 KB af SRAM. Det er en favorit af microcontroller hacking samfund med masser af gratis software support tilgængelig online. Her er de trin:
Download LambdaCan software her. Følg anvisningerne i tarball’en til at bygge det og uploade det til Diecimila bestyrelse.
Skær et hul i dåsen for Diecimila USB-stik til at stikke igennem.
Sæt Diecimila bord i en lille plasticpose. Dække bundkanterne af dåsen med epoxy kit. Mens kit er stadig blød, mash plast-pakket Diecimila bord ind i det, indtil bestyrelsen er på plads med sin USB-stik stikke ud af hullet i dåsen. Plastposen vil holde klæbrige epoxy ud af dit bord. Fjern pladen og lad epoxyen kit hærde. Kassér plastpose.
Spraymaling dåsen. Lad det tørre.
Sæt Diecimila bord i dåsen. Den hærdede expoy kit bør sikre, at det forbliver i den korrekte position. Tæt dåse. Færdig!
FYI:
Du kan åbne dåsen, hvis du har brug for at ramme bestyrelsens reset-knap.
Da vi brugte epoxy kit kun at hærde i en form til at acceptere bestyrelsen og ikke at lime pladen på plads, hvis du vil du kan fjerne brættet og bruge det til noget andet senere.
Brug LambdaCan

(LambdaCan i aktion)
For at bruge LambdaCan, starte dine foretrukne GNU / Linux-maskine og derefter sætte LambdaCan ind på en ledig USB-port. Løbe

skærm / dev / ttyUSB0 9600
i en skal til at interagere med LambdaCan. Alternativt kan de instruktioner, der følger med den kilde, fortælle dig, hvordan man opbygger en POSIX version af den software, som du kan køre i en skal uden at behøve det LambdaCan hardware.
Syntaksen for Lambda Calculus er meget enkel: det har variabler som x og funktioner som (\ xx). Denne funktion, for eksempel, har et argument x og returnerer værdien af ​​dette argument — det er identiteten funktion. I Kirkens oprindelige syntaks, ville \ være en lambda. Perioden er lidt syntaktisk sukker at gøre funktionen mere læsbar ved visuelt at adskille parametre fra kroppen. Lambda Calculus omfatter også anvendelser af funktioner. For eksempel, ((\ xx) A) gælder ovenstående identitetsfunktion til argumentet A. Reduktion udtryk, i det mindste i de enkleste tilfælde, beløber sig til syntaktisk erstatte argumenter for formelle parametre i funktion organer, som så:

>> ((\x.x) A);;
-> A
\>

For at reducere, vi matcher argumentet A med den formelle parameter x, og derefter erstatte alle forekomster af x i kroppen med A. -> symbol angiver et trin af nedsættelse, \> symbolet angiver ingen yderligere reduktion er mulig.

Her er den formelle grammatik LambdaCan bruger. Bemærk, at du kan sætte mellemrum og linjeskift hvor som helst du vil, men du skal ende dit input med ;

START    ::= FORMULA ';;'

FORMULA  ::= VARIABLE
         |   '(' FORMULA FORMULA ')'
         |   '(' '\' VARIABLE '.' FORMULA ')'

VARIABLE ::= [A-Z,a-z]

I det mest basale form, er der ingen tal eller strenge i Lambda Calculus --- kun funktioner. Men du kan opfinde konventioner om, hvordan man indkode numre som funktioner. En sådan konvention kaldes "Kirkens numrene" koder numre som følger:

0 = (\s.(\z.z))
1 = (\s.(\z.(s z)))
2 = (\s.(\z.(s (s z))))

Hvert nummer er repræsenteret ved en særskilt funktion af to argumenter: s og z. Antallet af anvendelser af s koder den numeriske værdi: nul for 0, en for en, to for 2 og så videre. Ved hjælp af denne konvention, du koder operationen M + N som følger:

(\M.(\N.(\s.(\z.(M (s (N (s z))))))))

Så når bedt om at beregne 1 + 1 = 2, producerer LambdaCan følgende output:

>> ((
>> (\M.(\N.(\s.(\z.((M s) ((N s) z))))))
>> (\s.(\z.(s z))))
>> (\s.(\z.(s z))))
>> ;;
-> ((\N.(\s.(\z.(((\s.(\z.(s z))) s) ((N s) z))))) (\s.(\z.(s z))))
-> (\s.(\z.(((\s.(\z.(s z))) s) (((\s.(\z.(s z))) s) z))))
-> (\s.(\z.(((\s.(\z.(s z))) s) ((\z.(s z)) z))))
-> (\s.(\z.(((\s.(\z.(s z))) s) (s z))))
-> (\s.(\z.((\z.(s z)) (s z))))
-> (\s.(\z.(s (s z))))
/>
Nodes used:
        40
Vars used:
        MNsz

Her er 11 + 12 = 23, en beregning, der bruger næsten alle de LambdaCan s tilgængelige hukommelse:

((
(\M.(\N.(\s.(\z.((M s) ((N s) z))))))
(\s.(\z.(s (s (s (s (s (s (s (s (s (s (s z))))))))))))))
(\s.(\z.(s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))))
;;

-> ((\N.(\s.(\z.(((\s.(\z.(s (s (s (s (s (s (s (s (s (s (s z))))))))))))) s) ((N s) z))))) (\s.(\z.(s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))))
-> (\s.(\z.(((\s.(\z.(s (s (s (s (s (s (s (s (s (s (s z))))))))))))) s) (((\s.(\z.(s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))) s) z))))
-> (\s.(\z.(((\s.(\z.(s (s (s (s (s (s (s (s (s (s (s z))))))))))))) s) ((\z.(s (s (s (s (s (s (s (s (s (s (s (s z))))))))))))) z))))
-> (\s.(\z.(((\s.(\z.(s (s (s (s (s (s (s (s (s (s (s z))))))))))))) s) (s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))))
-> (\s.(\z.((\z.(s (s (s (s (s (s (s (s (s (s (s z)))))))))))) (s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))))
-> (\s.(\z.(s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s (s z)))))))))))))))))))))))))
/>
Nodes used:
        124
Vars used:
        MNsz

Hent

LambdaCan kilde, buildable for både Arduino Diecimila og POSIX:

lambdacan-v2.0.tar.gz

Bemærkninger:

(*) På brød i en dåse: ja, betyder det eksisterer. I begyndelsen af 90'erne min college bofæller og jeg kom i besiddelse af en dåse mærket "Brown brød i en Can". Har aldrig forestillet sådan en fødevare, vi undrede på det i vantro i mange måneder før noget ængsteligt åbner dåsen for at se, hvad det egentlig indeholdt. Forudsigeligt, det var en lille loaf rugbrød. Vi overhældt brødet i alkohol, satte den i brand, og smed den flammende masse ud af vinduet. Hele denne episode gav mening for os på det tidspunkt.
Jeg porteret koden fra en tidligere Lambda Calculus reducering jeg havde lavet til en ældre Zilog bord, her. Det tog nogle væsentlige ændringer for at gøre det passer ind i Atmel ATMega168 s 1KB af SRAM.

 

Comments are closed.