sslug-teknik team mailing list archive

[Mads Bondo Dydensborg <madsdyd@xxxxxxxxxxxx>]

On 4 Feb 2000, Henning Niss wrote:

> "Keld Laursen" <kl@xxxxxxxxxx> writes:
> 
> > > ``kernesprog'' (the Bare language); de foreskriver faktisk den
> > > halerekursive version.
> > 
> > Og hvad er så en halerekursiv funktion?
> 
> Det er faktisk et rigtigt godt spørgsmål (i.e., det er svært at
> definere helt præcist). Intutitivt er det dog ikke så svært (synes jeg
> :-)). 
> 
[..]
> 
>   fun accfak (n, acc) = if n = 0 then acc else fak (n-1, n * acc)
> 
> I denne version returnerer vi umiddelbart efter det rekursive kald og
> funktionen er således halerekursiv.

Og, som det vil fremgå for den opmærksomme læser, så var den funktion jeg
angav faktisk _ikke_ halerekursiv, på trods af at jeg faktisk skrev det.

Flov er jeg i dag. Well, ML er blevet lidt rustent.

Den funktion jeg oprindelig angav:

fun fak 0 = 1
  | fak n = n * fak (n - 1)

burde nu også kunne optimeres af en fornuftig oversætter. (Ikke
Henning? Eller tager jeg fejl igen?) Nogen af de der ML oversættere er
djævelsk smart.

> 
> Halerekursion er interresant fordi alle moderne oversætter for
> funktionssprog optimerer koden (man behøver ikke opsætte stackframes
> og hvad har vi). Når man programmere i sådant et sprog er det en
> vigtig optimering man kan lave som programmør.
> 

Jep. Men, jeg synes også det er værd at bemærke at ML oversættere som
regel kan lave nogle meget smart ting, så længe man ikke bruger
referencer. Netop fordi der ikke er sideeffekter kan meget gøres.

Et problem med den slags sprog er typisk at der er garbage collection -
det vil sige at det kan være svært at forudsige hvor lang tid noget tager,
fordi garbagecollectoren kan afbryde mit i det hele. Mads Tofte (direktør
for ITU) har dog gjort meget med sine "ML Regioner", og har matematisk
bevist en masse pæne egenskaber for den type oversættelse af ML. 

Meget interessant.

Mads

-- 
Mads Bondo Dydensborg.                               madsdyd@xxxxxxxxxxxx
If you're a command-line user (that is, someone who knows how to read and
type, rather than a 2-year-old who knows only how to point), Linux is potent, 
flexible and totally accessible. And if you must point, Linux offers X-windows.
                               - Ed Quillen, Denver post.